我最近看到一篇关于分布式系统中强一致性模型的很棒的博客。真的没有理由不分享它。最近比较空闲，就简单翻译一下，一个是为了精读，一个是为了更友好的分享。会随机插入一些个人补充，评论区的精彩讨论也会有选择性地翻译。原文在这里：https://aphyr.com/posts/313-st...odels网络分区是大概率会发生的。交换机、网络接口控制器（NIC，NetworkInterfaceControllers）、主机硬件、操作系统、硬盘、虚拟机、语言运行时，更不用说程序语义本身，所有这些都会导致我们的消息延迟和丢失、重复或重新排序。在一个不确定的世界中，我们希望程序保持直觉的正确性。是的，我们想要直觉上的正确性。然后做正确的事！但什么是正确的做法？我们如何描述它？在本文中，我们将研究一些“强”一致性模型并了解它们如何组合在一起。正确性（Correctness）其实有很多方法可以描述一个算法的抽象行为——但是为了统一起见，我们说一个系统是由状态和一些导致状态转换的操作组成的。在系统运行期间，随着操作的发展，它将从一种状态移动到另一种状态。比如单处理器历史，我们的状态可以是一个变量，操作可以是读写这个变量。在这个简单的Ruby程序中，我们多次读取和写入一个变量，将写入表示为输出。x="a";putsx;putsxx="b";putsxx="c"x="d";putsx我们已经对程序的正确性有了一个直观的概念：上面的程序应该输出“aabd”。为什么？因为它们是按顺序发生的。首先我们写入值a，然后读取值a，然后读取值a，写入值b，等等。一旦我们将变量写入某个值，比如a，那么读取操作应该返回a，直到我们再次更改变量。读取的值应始终返回最近写入的值。我们称这种系统——单值变量——单寄存器（不仅仅是硬件层面的寄存器，而是像寄存器一样工作）。我们从编程的第一天起就接受了这种模型，它就像一种习惯一样自然——但它不是变量工作的唯一方式。可以用任何值读取变量：a、d，甚至是月亮。在这种情况下，我们说系统不正确，因为操作不符合我们的模型期望它们工作的方式。这就引出了系统正确性的定义：给定一些涉及操作和状态的规则，随着操作的演进，系统将始终遵循这些规则。我们称这样的规则为一致性模型。我们用简单的英语陈述寄存器的规则，但它们也可以是任意复杂的数学结构。“读取两次写入前的值，将值加三，如果结果为4，读取操作可能返回cat或dog”，这也可以是一致性模型（作者只是针对表名一致性的阐述模型原理，下同）。也可以是“每次读操作都会返回0”。我们甚至可以说“根本没有规则，所有的行为都是允许的”。这是任何系统都可以轻松满足的最简单的一致性模型。更正式地说，一致性模型是所有允许操作的记录集合。当我们运行一个程序时，经过集合中允许的一系列操作后，具体的执行结果总是一致的。如果程序不小心执行了不在集合中的操作，我们就说执行记录不一致。如果任何可能的执行操作都在允许的操作集中，则系统满足一致性模型。我们希望实际系统满足这样一个“直觉上正确”的一致性模型，这样我们就可以编写出可预测的程序。并发历史假定一个用Node.js或Erlang编写的并发程序。有多个逻辑线程，我们称之为“多进程”。如果我们用2个进程运行这个并发程序，每个进程都访问（读取和写入）同一个寄存器，那么我们认为的寄存器系统的不变性（指顺序不变性）就会被覆盖。多处理器历史的两个工作进程分别称为“top”和“bottom”。顶级进程尝试执行写入、读取、读取。Bottom进程尝试同时执行read、writeb、read。因为程序是并发的，两个进程之间的交错操作会导致多个执行顺序——而在单核场景下，执行顺序永远是程序中指定的逻辑顺序。图例中，top写a，bottom读a，top读a，bottom写b，top读b，bottom读b。但是并发使得一切行为都不同。我们可以默认考虑每个并发程序——一旦执行，操作可以以任何顺序发生。一个线程，或者说一个逻辑进程，在执行记录级别有一个约束：属于同一个线程的操作必须按顺序发生。逻辑线程对允许操作集中的操作施加部分顺序保证。（一个逻辑线程是一个执行实体，即使编译器重新排列指令，单个线程中同步工作流的顺序也不会颠倒。但是不同线程之间的事件顺序无法保证。）即使有上述保证，从个别进程来看，我们的寄存器不变性也被打破了。Top写入a，读取a，然后读取b-这不再是它写入的值。我们必须使一致性模型更加宽松，才能有效地描述并发性。现在，一个进程可以从任何其他进程读取最近写入的值。寄存器成为两个进程之间的协调场所：它们共享状态。光锥>读写不再是瞬时过程，而是类似于光传播->反射面->反向传播的过程。光锥历史的现实往往不是那么理想：在几乎每个实际系统中，进程之间都有一定的距离。不缓存的值（指不被CPU的本地缓存缓存），通常在距离CPU30cm的DIMM内存条上。光需要一整纳秒才能传播这么长的距离，而实际的内存访问速度将比光速慢得多。位于不同数据中心的计算机上的值可能相距数千公里——这意味着传播时间为数百毫秒。在不违反物理定律的情况下，我们无法更快地传播数据。（违反物理定律，更不用说现代计算机系统了。）这意味着我们的操作不再是即时的。某些操作可能快得足以被认为几乎是瞬时的，但一般来说操作是耗时的。我们调用对变量的写入；写入传播到内存，或传播到另一台计算机，或传播到月球；内存改变状态；确认被发回；所以我们知道操作确实发生了。在并发读取位置之间传递消息的延迟会在操作记录中产生歧义。消息传播的速度可能会导致意外事件序列的发生。上图中，当bottom发起读请求时，值为a，但在读请求传播过程中，top将值写为b——写操作意外地先于读请求到达寄存器。底部最终读取b而不是a。该记录打破了我们的寄存器并发一致性模型。Bottom在发起读请求时并没有读到它的值。有人可能会考虑使用完成时间而不是调用时间作为操作的实时时间，但反过来想，这也是行不通的：当读请求在写操作之前到达时，进程将读取a当当前值为b时。在分布式系统中，耗时操作被放大，我们必须让一致性模型更宽松：允许这些不明确的命令发生。我们如何确定宽松程度？我们必须允许所有可能的订单吗？也许我们无论如何都应该施加一些合理性限制？Linearizabilityfiniteconcurrencybounds通过仔细检查，我们发现事件的顺序是有界的。在时间维度上，消息不能反向发送，所以第一个到达的消息会立即到达数据源。一个操作只有被调用才能生效。同样，通知完成的消息不能回发，这意味着操作完成后不能生效。如果我们假设每个进程都有一个全局状态；继续假设与这个全局状态交互的操作是原子的；那么我们就可以排除很多可能的记录。每个操作在调用和完成之间的某个时间点自动生效。我们称这样的一致性模型为线性一致性模型。尽管这些操作都是并发且耗时的，但每个操作都以严格的线性顺序发生在某个地方。线性化完全可见“全局单点状态”不一定是单节点。同样，操作不一定都是原子的，状态也可以跨多台机器分片或分多个步骤完成——只要从流程的角度来看，外部记录的行为等同于一个原子的单点状态。通常一个可线性化的系统由许多较小的协调进程组成，这些协调进程本质上是线性的，而这些协调进程又由更细粒度的协调进程组成，直到硬件提供可线性化的操作。线性化是一种强大的武器。一旦操作完成，它或它之后的状态将对所有参与者可见。因为每个操作都必须在其完成时间之前发生，而以后调用的任何操作都必须在调用时间之后发生，即在原始操作本身之后。一旦我们成功写入b，每个后续读取请求都可以读取b，或者如果发生更多写入，则可以读取b之后的某个值。我们可以通过利用线性化原子性约束来安全地修改状态。我们定义了一个类似CAS（compare-and-set）的操作，当且仅当寄存器中有某个值时，我们才可以向它写入一个新值。CAS操作可以作为实现互斥量、信号量、通道、计数器、列表、集合、映射、树等的基础，使这些共享数据结构可用。线性一致性保证更改的安全交错。此外，线性化时间界限确保所有更改在操作完成后对其他参与者可见。然后线性一致性禁止过时读取。每次读取都会读取调用时间和完成时间之间的状态，但绝不会读取读取请求调用之前的状态。线性一致性也禁止非单调读，比如先读一个新值，再读一个旧值的读请求。由于这些强约束的存在，线性化系统变得更容易推理，这也是为什么许多并发编程模型被建立作为选择它的基础。Javascript中的所有变量都是（独立）可线性化的，其他是Java中的易变变量、Clojure中的原子和Erlang中的独立进程。大多数编程语言都实现了互斥量和信号量，它们也是可线性化的。强约束假设通常会产生强约束保证。但是，如果我们不能满足这些假设怎么办？（线性一致性模型提供了这样的保证：1.对于观察者来说，所有的读写都在单调递增的时间轴上串行推进。2.所有的读总是返回最近的写操作的值。）顺序一致性（sequentialhistory）如果我们允许流程在时间维度上发生移位，使得它们的操作可能在调用之前或完成之后生效，但仍然保证一个约束——在任何流程中的操作必须按照流程中定义的顺序发生（即，由编程定义的逻辑顺序）。这样我们就得到了一个稍微弱一点的一致性模型：顺序一致性。顺序一致性比线性一致性允许产生更多的记录，但它仍然是一个有用的模型：我们每天都在使用它。例如，当用户将视频上传到Youtube时，Youtube将视频放入处理队列并立即返回该视频的网页。我们不会立即看到视频，上传的视频将在完全处理后的几分钟内上线。队列将同步（取决于队列的具体实现）按照它们入队的顺序从队列中移除项目。许多缓存和顺序一致性系统的行为一直都是。如果我在Twitter上写一条推文，或者在Facebook上发帖，需要一定的时间才能逐层穿透缓存系统。不同的用户会在不同的时间看到我的信息，但是每个人看到我的动作的顺序都是一样的。此帖一经查看，不会消失。如果我写了多个评论，其他人会按顺序看到它们，而不是乱序。（顺序一致性放宽了对一致性的要求：1.操作不要求按实时顺序发生。2.不同进程之间操作的顺序不强制，但必须是原子的。3.单个进程内的操作顺序必须与编码时相同。）偶然一致性（Casualconsistency）我们不必对流程中的每个操作都施加顺序约束。只有因果关系的操作必须按顺序发生。同样以帖子为例：帖子下的所有评论必须以相同的顺序显示给所有人，只有帖子可见后，帖子下的回复才能可见（即帖子和帖子下的评论有因果关系）。如果我们将这些因果关系编码为“我依赖操作X”之类的内容，作为每个操作的显式部分，数据库可以延迟这些操作，直到它们的依赖关系就位。因果一致性比同一进程中每个操作的严格顺序一致性（即顺序一致性）更宽松——属于同一进程但具有不同因果链的操作可以按相对顺序执行（即通过因果关系隔离，操作没有因果关系的可以并发执行），这可以防止许多不直观的行为发生。可序列化一致性（Serializableconsistency）可序列化历史如果说操作记录的发生等价于某个单一的原子序列，而与调用时间和完成时间无关，那么我们得到一个一致性，称为串行一致性模型。这个模型比你想象的更强大也更脆弱。序列一致性受到弱约束，因为它允许多种类型的记录在没有时间或顺序限制的情况下出现。在上图中，消息似乎可以任意发送到过去和未来，因果关系也可以交错。在串行数据库中，即使在时间0，x还没有被初始化，像readx这样的读事务是允许执行的。或者它会被推迟到无限遥远的未来。write2tox之类的写事务可以立即执行，也可能永远不会执行。例如，在串行系统中，有这样一个程序：x=1x=x+1putsx这个程序可以输出nil、1或2，因为操作可以以任意顺序发生。这是一个非常弱的约束！这里你可以把每一行代码看成一个操作，所有的操作都执行成功了。另一方面，串行一致性也有很强的约束，当它需要一个线性顺序时，它可以拦截很大一部分操作记录。看下面的程序：printxifx=3x=1ifx=nilx=2ifx=1x=3ifx=2这个程序只有一种输出可能。它并没有按照我们写的顺序输出，而是x会从nil变化：nil->1->2->3，最后输出3。由于串行一致性允许任意重排操作顺序（只要操作顺序是原子的），在实际场景中用处不大。大多数声称提供串行一致性的数据库实际上提供了强串行一致性，它与线性一致性具有相同的时间界限。使事情复杂化的是，大多数SQL数据库声称的串行一致性级别比它们实际执行的要弱，例如可重复读取、游标稳定性或快照隔离。（关于线性一致性和串行一致性，看似很相似，其实不然。串行一致性是数据库领域的一个概念，是针对事务的，描述的是一组事务的执行效果相当于某个serial没有顺序的概念，线性一致性来自于并行计算领域，它描述了对某个数据结构进行操作的顺序特性，串行一致性是对多个操作、多个对象的保证，总体上没有要求对于操作的顺序；线性一致性是对单个操作和单个对象的保证，所有操作都遵循实时的时间顺序，详见：http://www.bailis.org/blog/lin...lity/)consistency一致性是有代价的之前说过“弱”一致性模型比“强”一致性模型允许更多的操作记录发生（这里强弱是相对的e).例如，线性化保证操作发生在调用时间和完成时间之间。但是，需要协调才能实现对排序的强制约束。粗略地说，执行的日志记录越多，系统参与者必须进行的通信就越仔细和频繁。也许你听说过CAP理论。CAP理论指出，给定Consistency、Availability和Partitiontolerance，任何系统最多只能保证以上三项中的两项，不可能同时满足这三项。物品。这是EricBrewer对CAP猜想的非正式表述，以下是准确的定义：一致性（Consistency）表示线性化，具体可以是一个可线性化的寄存器。寄存器可以等价于集合、列表、映射、关系数据库等，因此该理论可以扩展到各种可线性化的系统。可用性意味着向非故障节点发出的每个请求都将成功完成。因为网络分区可以持续任意长的时间，所以节点不能简单地将响应推迟到分区结束。分区容忍度（Partitiontolerance）是指容易发生分区。在网络可靠时提供一致性和可用性是微不足道的，但在网络不可靠时几乎不可能。但是，网络并不总是完美可靠的，所以我们不能选择CA。所有实际可用的商业分布式系统最多只能提供AP或CP保证。familytree也许你会说：“等等！线性化不是一致性模型的最终解决方案！我可以围绕CAP理论提供顺序一致性、串行一致性或快照隔离！”是的，CAP理论只是声称我们无法构建一个完全可用的线性化系统。但问题是我们有其他证据表明我们无法利用顺序化、序列化、可重复读取、快照隔离、游标稳定性或任何其他比这些更强的约束来构建完全可用的系统。在PeterBailis的HighlyAvailableTransactions论文中，标有红色阴影的模型不能完全可用。如果我们放宽可用性的定义，只要求客户端节点始终可以与同一台服务器通信，那么就实现了某种一致性。基于此，我们可以提供因果一致性、PRAM（pipelinedrandomaccessmemory）一致性和“readwhatyouwrite”一致性。如果我们需要完全可用性，我们可以提供单调读取、单调写入、读取提交、单调和原子视角等。这些一致性模型由分布式存储系统提供，例如Riak和Cassandra，具有低隔离设置的ANSISQL数据库。这些一致性模型不保证线性顺序，而是在批任务或网络场景中提供部分顺序保证。只能保证部分排序，因为它们允许更丰富的记录。混合方法（Ahybridapproach）weaknotunsafe有些算法依赖线性化来提供安全性。例如，当我们要构建一个分布式锁服务时，我们需要线性化。如果没有硬时间边界，我们可以持有未来锁或过去锁。另一方面，许多算法根本不需要线性化。即使只提供“弱”一致性模型，具有最终一致性保证的集合、列表、树和映射等结构也可以安全地表示为CRDT（交换复制数据类型）具有更强约束的一致性模型需要更多的协调——需要更多的消息传递以确保操作以正确的顺序进行。这不仅意味着较低的可用性，而且还会导致更高的延迟。这也是现代CPU内存模型默认不可线性化的原因，除非明确指定。（x86-64架构的CPU通常使用Sequentialconsistency作为默认的内存顺序），现代CPU会在内核之间重新安排内存操作，甚至更糟。尽管（程序的行为）更难推理，但性能提升是惊人的。在地理分散的分布式系统中，数据中心通常有几百毫秒的延迟，通常与CPU场景类似，成本也差不多。因此，在实践中通常采用混合数据存储，在数据库之间混合不同的一致性模型，以平衡冗余、可用性、性能和安全性等目标。在可能的情况下，为可用性和性能选择“弱”一致性模型。必要时选择“强”一致性模型，因为有些算法对操作顺序有严格的要求。我们可以将大量数据写入S3、Riak、Cassandra等数据库，然后将指向数据的指针线性写入Postgres、ZooKeeper或etcd。一些数据库允许多种一致性模型共存，例如关系数据库中的可调整隔离级别，以及Cassandra和Riak中的线性化事务，从而减少使用的系统数量。但底线是：谁要是说它的一致性模型是最优解，那肯定是头大猪。接下来是精彩的解说时间ColinScott：当你提到“属于同一进程但不同因果链的操作”时，你是否对潜在的因果关系做出了更保守的假设（之前发生过）？我正在努力找出一个案例，当两个潜在的因果关系（A必须在B之前发生）操作同时来自同一台机器时会发生什么？Aphyr（作者）：虽然来自同一进程的操作在节点上按顺序发生，但它们不需要在所有地方按顺序发生。顺序一致性（Sequentialconsistency）做出这样的约束，但因果一致性（Casualconsistency）则没有。只有显式因果关系在因果一致的系统中是顺序不变的，而隐式因果关系在顺序一致的系统中是有保证的。（因为都来自同一个进程，以pid区分）AurojitPanda：其实你对ColinScott的回复和你文章中的一致性级别图是矛盾的。PRAM一致性模型约定：所有节点都以相同的顺序观察来自给定节点的写入(Lipton,Sandberg1988)。而你描述的因果一致性是比PRAM一致性弱的一致性模型，不是经典的因果一致性模型。而你描述中出现的隐式因果关系也是PRAM一致性模型约束的一部分。如果因果一致性强于PRAM一致性，则PRAM一致性应与任何使用因果一致性的因果一致性系统一起实现，以正确排序单个节点的写入操作，以便其他节点的观察结果一致。Aphyr（作者）：请参考：https://projects.ics.forth.gr/…s.pdf详细解释为什么因果一致性比PRAM强。具体来说，具有因果关系的操作可以在中间节点之间传递，但是PRAM没有对因果一致性的传递性做任何定义。Prakash：关于“在您的序列一致性示例中，各种if假设如何约束顺序？”的问题。您的回答提到“这些操作的发生顺序只有一种可能”。而我的问题是，当我们考虑在并发环境下执行某些操作时，如何做到“序列化只有一种可能”呢？例如，我们有不同的线程，其中一个检查x的值是否为3并打印，另一个将x的值设置为2。你能解释一下这个场景下顺序是如何维护的吗？Aphyr（作者）：串行操作记录实际上会转化为单线程下的操作记录，而单线程下的操作记录就是我们之前讨论中起作用的状态转移方程。如果身份函数是您的模型，则操作记录中的任何可能路径都是有效的，并且它们不会更改状态。为了让某些操作记录永不序列化（限制可能导致状态转移的非法操作的发生），需要声明一些相当于单线程执行的操作是无效的。这是强制某些操作具有顺序原因的条件语句(if)。
