白话一致性协议 - Paxos、Raft和PacificA[1]

书接上文 - Multi Paxos

在上一篇文章中,我们提到了Basic Paxos和Multi Paxos的异同。在Paxos Made Simple论文中,作者提到了Multi Paxos的一种实现。这个实现允许我们对一个连续的数据流(也可以称为复制日志,replicated log)达成共识,从而实现节点状态的一致性复制。

确定性状态机

我们可以将系统中的每一个节点抽象为一个有着确定性状态机,即给定多个状态一致的状态机,在执行同一个命令之后,其状态仍保持一致。(可以想一想编译原理里面的DFA)

Leader - 系统中唯一的proposer

如果系统中存在有多个proposer,那么就很可能会出现多个提案相互干扰的情况。虽然根据证明,最终这些提案都会收敛到一致,但是性能会非常低下。所以我们可以在系统中通过选举,选出一个leader做为主proposer(distinguishied proposer),所有的提案都由leader提出。

这样一来,在绝大多数情况下都不会出现提案相互干扰的情况。只有在leader切换的瞬间,可能会出现相同编号的不同提案,但是我们的算法可以很好的处理这种情况。

分布式系统中的“TCP”

类似于TCP协议中序列号,Multi Paxos中的每一个命令都有一个递增的编号。即我们前一个执行的命令是100号,那么下一个执行的命令一定是101号 …

more ...

白话一致性协议 - Paxos、Raft和PacificA[0]

一致性协议 - Paxos

在分布式系统当中,我们往往需要保持节点之间的一致性。在绝大多数情况下,我们需要让系统中的节点相互协调通力合作,有可能的让系统正确的工作。但是,由于分布式系统本身的特性,需要我们在不可靠的硬件上尽可能的构建可靠的系统。所以,看似简单的一致性问题成为了分布式系统领域的一个重要的课题。

Paxos算法是Leslie Lamport于1990年提出的一种一致性算法。也是目前公认解决分布式一致性问题最有效的算法之一。

Paxos算法的目标是在一个不可靠的分布式系统内,只通过网络通信,能够快速且正确地在集群内部对某个数据的值达成一致。并且保证不论发生任何异常,都不会破坏系统的一致性。

Paxos算法

另一种(简化了的)形象的问题描述 - 买车位

某小区的一些居民在抢车位,而车位只有一个。居民们达成协议,只要一个报价获得半数以上居民认可,那么提出这个出价的居民则获得了车位的所有权。

居民之间非常友善,如果知道了车位已经有了买家,就不会继续出价购买,并且会帮忙传播这个信息。

居民们都是遵纪守法的好公民,在整个过程中都只会如实的与其它用户分享信息。信息的分享是在网上,通过一对一的私密聊天进行。但是小区的手机信号非常差,我们不能保证通信的质量,一些信息可能会丢失,有的居民可能会掉线。但是居民不会失去记忆,并且通信的内容是完整的,不会被篡改的。

划重点:

  1. 车位有且只有一个,所以一个车位不能同时有两个拥有者
  2. 车位可以暂时没有拥有者,但是需要尽快选出一个 …
more ...

Windows Azure Storage Made Simple

加机器就是一把梭

没有什么问题是加一千台机器解决不了的,如果有,就再加一千台。
—— 《21天精通分布式系统》

分布式系统在设计之初,是为了解决单机系统的可用性和可扩展性问题的。

举个例子,单机系统就是雇一个小弟替你干活,但是这个小弟不太靠谱,偶尔泡个病号不上班,偶尔工作太多一个人干不过来。

分布式系统就是雇一群小弟帮你干活,偶尔有一两个小弟泡病号,我们会有富裕的人力顶上,工作太多我们可以继续拉新的小弟入伙,美滋滋。

这个比喻很好的描述了单机系统和分布式系统之间的关系。所以一种可能的分布式系统就是这个样子的:

我们将相同功能的服务器组成一个整体,通过一个load balancer对外提供服务。

这样的系统初步解决了我们的问题,在面对可扩展性和可用性的问题时,我们会:

  • 容量不足就加机器
  • 单机挂掉了就把流量调度到其它的节点上

不过单纯的加机器并不能完全满足我们的需要。对于CPU密集型的服务,增加副本数可以有效的均摊计算压力,但是对于存储密集型的服务,我们需要增加分库逻辑才能有效的增加系统的计算能力。

例如我们有100G的数据,但是数据库的容量最多只支持50G。这样无论怎么样增加副本都不能解决问题。如果我们将100G的数据均分,存储在两个50G的分库上,我们就可以支持单机系统容纳不了的数据了。

我们还可以把多个这样的分布式子系统组合起来,就可以组成一个小有规模的分布式系统了。现在我们在使用的一些服务,仍在使用这种模型。

上面分布式模型虽然有效,但是引入了一个严重的问题:因为节点之间是隔离的,并且只能通过消息传递进行通信与协调,所以基本无法完全保证副本之间保持一致的内部状态。

这就是所谓的一致性问题。

补充一点理论知识

CAP理论 …

more ...