本文次要介绍事务、一致性以及共识，首先会介绍它们怎么在分布式系统中起作用，而后将尝试形容它们之间的内在联系，让大家理解，在设计分布式系统时也是有肯定的“套路”可寻。最初将介绍业界验证分布式算法的一些工具和框架。心愿可能对大家有所帮忙或者启发。

1. 前文回顾

在上一篇中，咱们次要介绍了分布式系统中常见的复制模型，并形容了每一种模型的优缺点以及应用场景，同时论述了分布式系统中特有的一些技术挑战。首先，常见的分布式系统复制模型有3种，别离是主从复制模型、多主复制模型以及无主复制模型。此外，复制从客户端的时效性来说分为同步复制&&异步复制，异步复制具备滞后性，可能会造成数据不统一，因为这个不统一，会带来各种各样的问题。

此外，第一篇文章用了“老板安顿人干活”的例子比喻了分布式系统中特有的挑战，即局部生效以及不牢靠的时钟问题。这给分布式系统设计带来了很大的困扰。仿佛在没有机制做保障的状况下，一个奢侈的分布式系统什么事件都做不了。

在上一篇的最初，咱们对分布式系统零碎模型做了一些假如，这些假如对给出前面的解决方案其实是十分重要的。首先针对局部生效，是咱们须要对系统的超时进行假如，个别咱们假如为半同步模型，也就是说个别状况下提早都十分失常，一旦产生故障，提早会变得偏差十分大。另外，对于节点生效，咱们通常在设计零碎时假如为解体-复原模型。最初，面对分布式系统的两个保障Safty和Liveness，咱们优先保证系统是Safety，也就是平安；而Liveness（活性）通常在某些前提下才能够满足。

2. 本文简介

通过第一篇文章，咱们晓得了留待咱们解决的问题有哪些。那么这篇文章中，将别离依据咱们的假如去解决上述的挑战。这些保障措施包含事务、一致性以及共识。接下来讲介绍它们的作用以及内在联系，而后咱们再回过头来扫视一下Kafka复制局部的设计，看看一个理论的零碎在设计上是否真的能够间接应用那些套路，最初介绍业界验证分布式算法的一些工具和框架。接下来，持续咱们的数据复制之旅吧！

3. 事务&内部一致性

说到事务，置信大家都能简略说出个一二来，首先能本能做出反馈出的，应该就是所谓的“ACID”个性了，还有各种各样的隔离级别。是的，它们的确都是事务须要解决的问题。

在这一章中，咱们会更加有条理地了解下它们之间的内在联系，具体看一看事务到底要解决什么问题。在《DDIA》一书中有十分多对于数据库事务的具体实现细节，但本文中会弱化它们，毕竟本文不想具体介绍如何设计一款数据库，咱们只需探索问题的自身，等真正寻找解决方案时再去具体看设计，成果可能会更好。上面咱们正式开始介绍事务。

3.1 事务的产生

零碎中可能会面临上面的问题：

  1. 程序依靠的操作系统层，硬件层可能随时都会产生故障（包含一个操作执行到一半时）。
  2. 应用程序可能会随时产生故障（包含操作执行到一半时）。
  3. 网络中断可能随时会产生，它会切断客户端与服务端的链接或数据库之间的链接。
  4. 多个客户端可能会同时拜访服务端，并且更新对立批数据，导致数据相互笼罩（临界区）。
  5. 客户端可能会读到过期的数据，因为下面说的，可能操作执行一半应用程序就挂了。

假如上述问题都会呈现在咱们对于存储系统（或者数据库）的拜访中，这样咱们在开发本人应用程序的同时，还须要额定付出很大代价解决这些问题。事务的外围使命就是尝试帮咱们解决这些问题，提供了从它本人层面所看到的安全性保障，让咱们在拜访存储系统时只专一咱们自身的写入和查问逻辑，而非这些额定简单的异样解决。而说起解决形式，正是通过它那赫赫有名的ACID个性来进行保障的。

3.2 不厌其烦——ACID个性

这四个缩写所组成的个性置信大家已造成本能反馈，不过《DDIA》一书中给出的定义的确更加有利于咱们更加清晰地了解它们间的关系，上面将别离进行阐明：

A：原子性(Atomicity)：原子性理论形容的是同一个客户端对于多个操作之间的限度，这里的原子示意的是不可分割，原子性的成果是，假如有操作汇合{A,B,C,D,E}，执行后的后果应该和单个客户端执行一个操作的成果雷同。从这个限度咱们能够晓得：

  1. 对于操作自身，就算产生任何故障，咱们也不能看到任何这个操作集中间的后果，比方操作执行到C时产生了故障，然而事务应该重试，直到咱们须要等到执行完之后，要么咱们应该复原到执行A之前的后果。
  2. 对于操作作用的服务端而言，呈现任何故障，咱们的操作不应该对服务端产生任何的副作用，只有这样客户端能力平安的重试，否则，如果每次重试都会对服务端产生副作用，客户端是不敢始终平安的重试的。

因而，对于原子性而言，书中形容说的是能在执行产生异样时抛弃，能够间接终止，且不会对服务端产生任何副作用，能够平安的重试，原子性也成为“可终止性”。

C：一致性（Consistency）：这个名词有太多的重载，也就是说它在不同语境中含意会截然不同，但可能又有分割，这就可能让咱们陷入凌乱，比方：

  1. 数据复制时，正本间具备一致性，这个一致性应该指上一章中提到的不同正本状态的统一。
  2. 一致性Hash，这是一种分区算法，集体了解是为了可能在各种状况下这个Hash算法都能够以统一的形式发挥作用。
  3. CAP定理中的一致性指的是前面要介绍的一个非凡的外部一致性，称为“线性一致性”。
  4. 咱们稍后要介绍ACID中的一致性，指的是程序的某些“不变式”，或“良好状态”。

咱们须要辨别不同语境中一致性所表白含意的区别，也心愿大家看完明天的分享，能更好地帮忙大家记住这些区别。话说回来，这里的一致性指的是对于数据一组特定陈说必须成立，即“不变式”，这里有点相似于算法中的“循环不变式”，即当外界环境发生变化时，这个不变式肯定须要成立。

书中强调，这个外面的一致性更多须要用户的应用程序来保障，因为只有用户晓得所谓的不变式是什么。这里举一个简略的小例子，例如咱们往Kafka中append音讯，其中有两条音讯内容都是2，如果没有额定的信息时，咱们也不晓得到底是客户端因为故障重试发了两次，还是真的就有两条截然不同的数据。

如果想进行辨别，能够在用户程序生产后走自定义的去重逻辑，也能够从Kafka本身登程，客户端发送时减少一个“发号”环节表明音讯的唯一性（高版本中Kafka事务的实现大抵思路）这样引擎自身就具备了肯定的本人设置“不变式”的能力。不过如果是更简单的状况，还是须要用户程序和调用服务自身独特保护。

I：隔离性（Isolation）：隔离性实际上是事务的重头戏，也是门道最多的一环，因为隔离性解决的问题是多个事务作用于同一个或者同一批数据时的并发问题。一提到并发问题，咱们就晓得这肯定不是个简略的问题，因为并发的实质是时序的不确定性，当这些不确定时序的作用域有肯定抵触（Race）时就可能会引发各种各样的问题，这一点和多线程编程是相似的，但这外面的操作远比一条计算机指令工夫长得多，所以问题会更重大而且更多样。

这里给一个具体的实例来直观感触下，如下图展现了两个客户端并发的批改DB中的一个counter，因为User2的get counter产生的时刻在User1更新的过程中，因而读到的counter是个旧值，同样User2更新也相似，所以最初应该预期counter值为44，后果两个人看到的counter都是43（相似两个线程同时做value++）。

一个完满的事务隔离，在每个事务看来，整个零碎只有本人在工作，对于整个零碎而言这些并发的事务一个接一个的执行，也好像只有一个事务，这样的隔离成为“可序列化（Serializability）”。当然，这样的隔离级别会带来微小的开销，因而呈现了各种各样的隔离级别，进而满足不同场景的须要。后文会具体介绍不同的隔离级别所解决的问题。

D：持久性（Durability）：这个个性看似比拟好了解，就一点，只有事务实现，不论产生任何问题，都不应该产生数据失落。从实践上讲，如果是单机数据库，起码数据已被写入非易失性存储（至多已落WAL），分布式系统中数据被复制到了各个正本上，并受到正本Ack。但理论状况下，也未必就肯定能保障100%的持久性。这外面的状况书中有具体的介绍，这里就不做反复的Copy工作了，也就是说事务所保障的持久性个别都是某种衡量下的后果。

下面四个个性中，实际上对于隔离性的问题，可能是问题最多样的，也是最为简单的。因为一味强调“序列化”可能会带来不可承受的性能开销。因而，下文将重点介绍一些比可序列化更弱的隔离级别。

3.3 事务按操作对象的划分&&平安的提交重试

在介绍前面内容前，有两件事须要当时做下强调，别离是事务操作的对象以及事务的提交与重试，分为单对象&&多对象。

单对象写入：这种书中给出了两种案例。

  1. 第一个是单个事物执行一个长时间的写入，例如写入一个20KB的JSON对象，假如写到10KB时断掉会产生什么？

    a. 数据库是否会存在10KB没法解析的脏数据。
    b. 如果复原之后数是否能接着持续写入。
    c. 另一个客户端读取这个文档，是否可能看到复原后的最新值，还是读到一堆乱码。

  2. 另一种则是相似上图中Counter做自增的性能。

这种事务的解决办法个别是通过日志回放（原子性）、锁（隔离性）、CAS（隔离性）等形式来进行保障。

多对象事务：这类事务实际上是比较复杂的，比方可能在某些分布式系统中，操作的对象可能会跨线程、跨过程、跨分区，甚至跨零碎。这就意味着，咱们面临的问题多于上一篇文章提到的那些分布式系统特有的问题，解决那些问题显然要更简单。有些零碎罗唆把这种“锅”甩给用户，让应用程序本人来解决问题，也就是说，咱们可能须要本人解决因没有原子性带来的两头后果问题，因为没有隔离性带来的并发问题。当然，也有些零碎实现了这些所谓的分布式事务，后文中会介绍具体的实现伎俩。

另一个须要特别强调的点是重试，事务的一个外围个性就是当产生谬误时，客户端能够平安的进行重试，并且不会对服务端有任何副作用，对于传统的真的实现ACID的数据库系统，就应该遵循这样的设计语义。但在理论实际时，如何保障下面说的可能“平安的重试”呢？书中给出了一些可能产生的问题和解决伎俩：

  1. 假如事务提交胜利了，但服务端Ack的时候产生了网络故障，此时如果客户端发动重试，如果没有额定的伎俩，就会产生数据反复，这就须要服务端或应用程序本人提供可能辨别音讯唯一性的额定属性（服务端内置的事务ID或者业务本身的属性字段）。
  2. 因为负载太大导致了事务提交失败，这是贸然重试会减轻零碎的累赘，这时可在客户端进行一些限度，例如采纳指数退却的形式，或限度一些重试次数，放入客户端本人零碎所属的队列等。
  3. 在重试前进行判断，尽在产生临时性谬误时重试，如果利用曾经违反了某些定义好的束缚，那这样的重试就毫无意义。
  4. 如果事务是多对象操作，并且可能在零碎中产生副作用，那就须要相似“两阶段提交”这样的机制来实现事务提交。

3.4 弱隔离级别

事务隔离要解决的是并发问题，并发问题须要探讨两个问题时序与竞争，往往因为事物之间的操作对象有竞争关系，并且又因为并发事务之间不确定的时序关系，会导致这些所操作的有竞争关系的对象会呈现各种奇怪的后果。

所谓不同的隔离级别，就是试图去用不同的开销来满足不同场景下对于时序要求的严格水平。咱们可能不肯定晓得具体怎么实现这些事务隔离级别，但每个隔离级别解决的问题自身咱们应该十分清晰，这样才不会在各种隔离级别和开销中比拟轻松的做衡量。这里，咱们不间接像书中一样列举隔离级别，咱们首先论述并发事务可能产生的问题，而后再去介绍每种隔离级别别离可能解决那些问题。

脏读

所谓脏读，指的就是用户能不能看到一个还没有提交事务的后果，如果是，就是脏读。下图展现了没有脏读应该满足什么样的承诺，User1的一个事务别离设置x=3、y=3，但在这个事务提交之前，User2在调用get x时，须要返回2，因为此时User1并没有提交事务。

避免脏读的意义：

  1. 如果是单对象事务，客户端会看到一个一会行将可能被回滚的值，如果我须要根据这个值做决策，就很有可能会呈现决策谬误。
  2. 如果是多对象事务，可能客户端对于不同零碎做拜访时一部分数据更新，一部分未更新，那样用户可能会手足无措。

脏写

如果一个客户端笼罩了另一个客户端尚未提交的写入，咱们就称这样的景象为脏写。

这里同样给个实例，对于一个二手车的交易，须要更新两次数据库实现，但有两个用户并发的进行交易，如果像图中一样不禁止脏写，就可能存在销售列表显示交易属于Bob但发票却发给了Alice，因为两个事务对于两个数据的雷同记录相互笼罩。

读偏差（不可反复读）

间接上例子，Alice在两个银行账户总共有1000块，每个账户500，当初她想从一个账户向另一个账户转账100，并且她想始终盯着本人的两个账户看看钱是否转胜利了。不巧的是，他第一次看账户的时候转账还没产生，而胜利后只查了一个账户的值，正好少了100，所以最初加起来会感觉本人少了100元。

如果只是这种场景，其实只是个临时性的景象，前面再查问就会失去正确的值，然而如果基于这样的查问去做别的事件，那可能就会呈现问题了，比方将这个记录Select进去进行备份，以防DB解体。但不巧如果前面真的解体，如果基于这次查问到的数据做备份，那这100元可能真的永恒的失落了。如果是这样的场景，不可反复读是不能被承受的。

更新失落

这里间接把之前那个两个用户同时依据旧值更新计数器的例子搬过去，这是个典型的更新失落问题：

写偏差 && 幻读

这种问题形容的是，事务的写入须要依赖于之前判断的后果，而这个后果可能会被其余并发事务批改。

实例中有两个人Alice和Bob决定是否能够休班，做这个决定的前提是判断以后是否有两个以上的医生正在值班，如果是则本人能够平安的休班，而后批改值班医生信息。但因为应用了快照隔离（前面会介绍）机制，两个事务返回的后果全都是2，进入了批改阶段，但最终的后果其实是违反了两名医生值班的前提。

造成这个问题的根本原因是一种成为“幻读”的景象，也就是说两个并发的事务，其中一个事务更改了另一个事物的查问后果，这种查问个别都是查问一个聚合后果，例如上文中的count或者max、min等，这种问题会在上面场景中呈现问题。

  • 抢订会议室
  • 多人游戏更新地位
  • 惟一用户名

下面咱们列举了事务并发可能产生的问题，上面咱们介绍各种隔离级别所能解决的问题。

隔离级别&&简略实现伎俩/问题脏读脏写读偏差更新失落写偏差(幻读)
读已提交(行锁 or 记住旧值)YYNNN
可反复读(快照隔离，CAS)YYYMaybeN
可串行化(2PL乐观锁 or SSI乐观锁)YYYYY

3.5 本章小结

事务用它的ACID个性，为用户屏蔽了一些谬误的解决。首先，原子性为用户提供了一个可平安重试的环境，并且不会对相应的零碎产生副作用。一致性可能在肯定水平上让程序满足所谓的不变式，隔离性通过不同的隔离级别解决不同场景下因为事务并发导致的不同景象，不同的隔离性解决的问题不同，开销也不同，须要用户按需决策，最初持久性让用户安心的把数据写进咱们设计的零碎。

总体而言，事务保障的是不同操作之间的一致性，一个极度完满的事务实现，让用户看上去就只有一个事务在工作，每次只执行了一个原子操作。因而，咱们称事务所解决的是操作的一致性。这一章中，咱们更多议论的还是单机范畴的事务。接下来，咱们会把问题阈扩充，实际上分布式系统也有这样的问题，并且分布式系统还有相似的复制滞后问题，导致就算看似是操作的是一个对象，也存在不同的正本，这会使得咱们所面对的问题更加简单。下一章，咱们重点介绍另一种一致性问题以及解决。

4. 外部一致性与共识

4.1 复制滞后性的问题

这里咱们首先回到上一篇中讲的复制的滞后性，滞后性所带来的的一个最直观的问题就是，如果在复制期间客户端发动读申请，可能不同的客户端读到的数据是不一样的。这外面书中给了三种不同类型的一致性问题。咱们别离来看这些事例：

第一张图给出的是一个用户先更新，而后查看更新后果的事例，比方用户对某一条博客下做出了本人的评论，该服务中的DB采纳纯的异步复制，数据写到主节点就返回评论胜利，而后用户想刷新下页面看看本人的评论能引发多大的共鸣或跟帖，这是因为查问到了从节点上，所以发现方才写的评论“不胫而走”了，如果零碎可能避免出现下面这种状况，咱们称实现了“写后读一致性”（读写一致性）。

下面是用户更新后查看的例子，下一张图则展现了另一种状况。用户同样是在零碎中写入了一条评论，该模块仍旧采纳了纯异步复制的办法实现，此时有另一位用户来看，首先刷新页面时看到了User1234的评论，但下一次刷新，则这条评论又隐没了，如同时钟呈现了回拨，如果零碎可能保障不会让这种状况呈现，阐明零碎实现了“枯燥读”一致性（比方腾讯体育的比分和详情页）。

除了这两种状况外，还有一种状况，如下图所示：

这个问题会比后面的例子看上去更荒谬，这里有两个写入客户端，其中Poons问了个问题，而后Cake做出了答复。从程序上，MrsCake是看到Poons的问题之后才进行的答复，然而问题与答复恰好被划分到了数据库的两个分区（Partition）上，对于上面的Observer而言，Partition1的Leader提早要远大于Partition2的提早，因而从Observer上看到的是现有答案后有的问题，这显然是一个违反自然规律的事件，如果能防止这种问题呈现，那么可称为零碎实现了“前缀读一致性”。

在上一篇中，咱们介绍了一能够检测相似这种因果的形式，但综上，咱们能够看到，因为复制的滞后性，带来的一个结果就是零碎只是具备了最终一致性，因为这种最终一致性，会大大的影响用户的一些应用体验。下面三个例子尽管代表了不同的一致性，但都有一个共性，就是因为复制的滞后性带来的问题。所谓复制，那就是多个客户端甚至是一个客户端读写多个正本时所产生的的问题。这里咱们将这类一致性问题称为“外部一致性（内存一致性）”，即表征因为多个正本读写的时序存在的数据不统一问题。

4.2 外部一致性概述

实际上，外部一致性并不是分布式系统特有的问题，在多核畛域又称内存一致性，是为了约定多处理器之间合作。如果多处理器间可能满足特定的一致性，那么就能对多处理器所解决的数据，操作程序做出肯定的承诺，利用开发人员能够依据这些承诺对本人的零碎做出假如。如下图所示：

每个CPU逻辑外围都有本人的一套独立的寄存器和L1、L2Cache，这就导致如果咱们在并发编程时，每个线程如果对某个主存地址中变量进行批改，可能都是优先批改本人的缓存，并且读取变量时同样是会先读缓存。这实际上和咱们在分布式中多个客户端读写多个正本的景象是相似的，只不过分布式系统中是操作粒度，而处理器则是指令粒度。在多处理器的内存一致性中，有上面几种常见的模型。

能够看到，这些一致性束缚的外围辨别点就是在产生并发时对程序的束缚，而用更业余一点的词来说，线性一致性须要的是定义“全序”，而其余一致性则是某种“偏序”，也就是说容许一些并发操作间不比拟程序，按所有可能的排列组合执行。

4.3 触类旁通：分布式系统中的外部一致性

如下图所示：

分布式中的外部一致性次要分为4大类：线性一致性-->程序一致性-->因果一致性-->处理器一致性，而从偏序与全序来划分，则划分为强一致性（线性一致性）与最终一致性。

但须要留神的是，只有不是强统一的外部一致性，但最终一致性没有任何的偏序保障。图中的这些一致性理论都是做了一些偏序的限度，比奢侈的最终一致性有更强的保障，这里其余一致性性的具体实例详见《大数据日知录》第二章，那外面有比拟明确对于这些一致性的解说，本章咱们重点关注强统一。

4.4 咱们口中的“强一致性”——线性一致性

满足线性一致性的零碎给咱们这样一种感觉，这零碎看着只有一个正本，这样我就能够释怀地读取任何一个正本上的数据来持续咱们的应用程序。这里还是用一个例子来具体阐明线性一致性的束缚，如下图所示：

这里有三个客户端同时操作主键x，这个主键在书中被称为寄存器（Register），对该寄存器存在如下几种操作：

  1. write(x，v) =>r示意尝试更新x的值为v，返回更新后果r。
  2. read(x) => v示意读取x的值，返回x的值为v。

如图中所示，在C更新x的值时，A和B重复查问x的最新值，比拟明确的后果是因为ClientA在ClientC更新x之前读取，所以第一次read(x)肯定会为0，而ClientA的最初一次读取是在ClientC胜利更新x的值后，因而肯定会返回1。而剩下的读取，因为不确定与write(x,1)的程序（并发），因而可能会返回0也可能返回1。对于线性一致性，咱们做了上面的规定：

在一个线性一致性零碎中，在写操作调用到返回之前，肯定有一个工夫点，客户端调用read能读到新值，在读到新值之后，后续的所有读操作都应该返回新值。（将下面图中的操作做了严格的程序，及ClientA read->ClientB read->ClientC write-ClientA read->clientB read->clientAread）这里为了清晰，书中做了进一步细化。在上面的例子中，又减少了一种操作：

  • cas(x, v_old, v_new)=>r 及如果此时的值时v_old则更新x的值为v_new，返回更新后果。

如图：每条数显代表具体事件产生的时点，线性一致性要求：如果连贯上述的竖线，要求必须依照工夫程序向前推移，不能向后回拨（图中的read(x)=2就不满足线性化的要求，因为x=2在x=4的左侧）。

4.5 什么时候须要依赖线性化？

如果只是相似论坛中评论的先后顺序，或者是体育比赛页面刷新页面时的来回跳变，看上去并不会有什么致命的危害。但在某些场景中，如果零碎不是线性的可能会造成更重大的结果。

  1. 加锁&&选主：在主从复制模型下，须要有一个明确的主节点去接管所有写申请，这种选主操作个别会采纳加锁实现，如果咱们依赖的锁服务不反对线性化的存储，那就可能呈现跳变导致“脑裂”景象的产生，这种景象是相对不能承受的。因而针对选主场景所依赖的分布式锁服务的存储模块肯定须要满足线性一致性（一般而言，元数据的存储也须要线性化存储）。
  2. 束缚与唯一性保障：这种场景也是不言而喻的，比方惟一ID、主键、名称等等，如果没有这种线性化存储承诺的严格的程序，就很容易突破唯一性束缚导致很多奇怪的景象和结果。
  3. 跨通道（零碎）的工夫依赖：除了同一零碎中，可能服务横跨不同零碎，对于某个操作对于不同零碎间的时序也须要有限度，书中举了这样一个例子。

比方用户上传图片，相似后端存储服务可能会依据全尺寸图片生成低像素图片，以便减少用户服务体验，但因为MQ不适宜发送图片这种大的字节流，因而全尺寸图片是间接发给后端存储服务的，而截取图片则是通过MQ在后盾异步执行的，这就须要2中上传的文件存储服务是个可线性化的存储。如果不是，在生成低分辨率图像时可能会找不到，或读取到半张图片，这必定不是咱们心愿看到的。

线性化不是防止竞争的惟一办法，与事务隔离级别一样，对并发程序的要求，可能会依据场景不同有不同的严格水平。这也就诞生了不同级别的外部一致性级别，不同的级别也同样对应着不同的开销，须要用户自行决策。

4.6 实现线性化零碎

阐明了线性化零碎的用途，上面咱们来思考如何实现这样的线性化零碎。

依据上文对线性化的定义可知，这样零碎对外看起来就像只有一个正本，那么最容易想到的形式就是，罗唆就用一个正本。但这又不是分布式系统的初衷，很大一部分用多正本是为了做容错的，多正本的实现形式是复制，那么咱们来看看，上一篇分享中那些常见的复制形式是否能够实现线性系统：

  1. 主从复制（局部能实现）：如果应用同步复制，那样零碎的确是线性化的，但有一些极其状况可能会违反线性化，比方因为成员变更过程中的“脑裂”问题导致生产异样，或者如果咱们应用异步复制故障切换时会同时违反事务个性中的长久化和外部一致性中的线性化。
  2. 共识算法（线性化）：共识算法在后文会重点介绍，它与主从复制相似，但通过更严格的协商机制实现，能够在主从复制的根底上防止一些可能呈现的“脑裂”等问题，能够比拟平安的实现线性化存储。
  3. 多主复制（不能线性化）。
  4. 无主复制（可能不能线性化）：次要取决于具体Quorum的配置，对强统一的定义，下图给了一种尽管满足严格的Quorum，但仍然无奈满足线性化的例子。

实现线性化的代价——是时候退场了，CAP实践

在上一次分享中，咱们讲过，分布式系统中网络的不可靠性，而一旦网络断开（P），正本间肯定会导致状态无奈达到线性统一，这时候到底是持续提供服务但可能失去旧值（A），还是死等网络复原保障状态的线性统一呢（C），这就是驰名的CAP了。

然而其实CAP实践的定义面还是比拟窄的，其中C只是线性一致性，P只代表网络分区（彻底断开，而不是提早），这外面理论有相当多的折中，就能够齐全满足咱们零碎的需要了，所以不要科学这个实践，还是须要依据具体的理论状况去做剖析。

层层递进--实现线性化零碎

从对线性一致性的定义咱们能够晓得，程序的检测是实现线性化零碎的要害，这里咱们跟着书中的思路一步步地来看：咱们怎么能对这些并发的事务定义出它们的程序。

a.捕获因果关系

与上一次分享的内容相似，并发操作间有两种类型，可能有些操作间具备人造逻辑上的因果关系，还有些则没法确定，这里咱们首先先尝试捕捉那些有因果关系的操作，实现个因果一致性。这里的捕捉咱们理论须要存储数据库（零碎）操作中的所有因果关系，咱们能够应用相似版本向量的形式（遗记的同学，能够回看上一篇中两个人并发操作购物车的示例）。

b.化被动为被动--被动定义

下面被动地不加任何限度的捕获因果，会带来微小的运行开销（内存，磁盘），这种关系尽管能够长久化到磁盘，但剖析时仍然须要被载入内存，这就让咱们有了另一个想法，咱们是否能在操作上做个标记，间接定义这样的因果关系？

最最简略的形式就是构建一个全局发号器，产生一些序列号来定义操作间的因果关系，比方须要保障A在B之前产生，那就确保A的全序ID在B之前即可，其余的并发操作程序不做硬限度，但操作间在处理器的绝对程序不变，这样咱们岂但实现了因果一致性，还对这个限度进行了加强。

c.Lamport工夫戳

下面的构想尽管比拟现实，但事实永远超乎咱们的设想的简单，下面的形式在主从复制模式下很容易实现，但如果是多主或者无主的复制模型，咱们很难设计这种全局的序列号发号器，书中给出了一些可能的解决方案，目标是生成惟一的序列号，比方：

  1. 每个节点各自产生序列号。
  2. 每个操作上带上工夫戳。
  3. 事后调配每个分区负责产生的序列号。

但实际上，下面的办法都可能毁坏因果关系的偏序承诺，起因就是不同节点间负载不同、时钟不同、参照系不同。这里咱们的并发大神Lamport退场了，他老人家借鉴了一个Lamport逻辑工夫戳，完满地解决了下面的所有问题。如下图所示：

初识Lamport工夫戳，还是研究生分布式系统课上，过后听得云里雾里，齐全不晓得在说啥。明天再次拿过去看，有了上下文，略微懂了一点点。简略来说定义的就是应用逻辑变量定义了依赖关系，它给定了一个二元组<Counter, NodeId>，而后给定了一个比拟形式：

  1. 先比拟Counter，Counter大的后产生（会承诺严格的偏序关系）。
  2. 如果Counter雷同，间接比拟NodeId，大的定义为后产生（并发关系）。

如果只有这两个比拟，还不能解决下面的因果偏序被突破的问题，然而这个算法不同的是，它会把这个Node的Counter值内嵌到申请的响应体中，比方图中的A，在第二次向Node2发送更新max申请时，会返回以后的c=5，这样Client会把本地的Counter更新成5，下一次会增1这样应用Node上的Counter就保护了各个正本上变量的偏序关系，如果并发往两个Node里写就间接定义为并发行为，用NodeId定义程序了。

d. 咱们能够实现线性化了吗——全序播送

到此咱们能够确认，有了Lamport工夫戳，咱们能够实现因果一致性了，但依然无奈实现线性化，因为咱们还须要让这个全序告诉到所有节点，否则可能就会无奈做决策。
举个例子，针对惟一用户名这样的场景，假如ABC同时向零碎尝试注册雷同的用户名，应用Lamport工夫戳的做法是，在这三个并发申请中最先提交的返回胜利，其余返回失败，但这外面咱们因为有“上帝视角”，晓得ABC，但理论申请自身在发送时不晓得有其余申请存在（不同申请可能被发送到了不同的节点上）这样就须要零碎做这个收集工作，这就须要有个相似协调者来一直询问各个节点是否有这样的申请，如果其中一个节点在询问过程中产生故障，那零碎无奈释怀决定每个申请具体的RSP后果。所以最好是零碎将这个程序播送到各个节点，让各个节点真的晓得这个程序，这样能够间接做决策。

假如只有单核CPU，那么人造就是全序的，然而当初咱们须要的是在多核、多机、分布式的状况下实现这个全序的播送，就存在这一些挑战。次要挑战是两个：

  • 多机
  • 分布式

对于多机，实际上实现全序播送最简略的实现形式应用主从模式的复制，让所有的操作程序让主节点定义，而后按雷同的程序播送到各个从节点。对于分布式环境，须要解决局部生效问题，也就是如果主节点故障须要解决主成员变更。上面咱们就来看看书中是怎么解决这个问题的。

这里所谓的全序个别指的是分区外部的全序，而如果须要跨分区的全序，须要有额定的工作。

对于全序播送，书中给了两条不变式：

  1. 牢靠发送：须要保障音讯做到all-or-nothing的发送（想想上一章）。
  2. 严格有序：音讯须要按完全相同的程序发给各个节点。

实现层面

咱们对着下面的不变式来谈谈简略的实现思路，首先要做到牢靠发送，这里有两层含意：

  1. 音讯不能丢
  2. 音讯不能发一部分

其中音讯不能丢意味着如果某些节点呈现故障后须要重试，如果须要平安的重试，那么播送操作自身失败后就不能对系统自身有副作用，否则就会导致音讯发送到局部节点上的问题。上一章的事务的原子性恰好就解决的是这个问题，这里也就衍射出咱们须要采纳事务的一些思路，但与下面不同，这个场景是分布式系统，会发到多个节点，所以肯定是分布式事务（耳熟能详的2PC肯定少不了）。

另外一条是严格有序，实际上咱们就是须要一个能保障程序的数据结构，因为操作是按工夫序的一个Append-only构造，恰好Log能解决这个问题，这里引出了另一个常会被提到的技术，复制状态机，这个概念是我在Raft的论文中看到的，假如初始值为a，如果依照雷同的程序执行操作ABCDE最初失去的肯定是雷同的后果。因而能够设想，全序播送最初的实现肯定会用到Log这种数据结构。

e.线性系统的实现

当初假如咱们曾经有了全序播送，那么咱们持续像咱们的指标--线性化存储迈进，首先须要明确一个问题，线性化并不等价于全序播送，因为在分布式系统模型中咱们通常采纳异步模型或者半同步模型，这种模型对于全序关系何时胜利发送到其余节点并没有明确的承诺，因而还须要再全序播送上做点什么才真正能实现线性化零碎。

书中依然举了惟一用户名的例子：能够采纳线性化的CAS操作来实现，当用户创立用户名时当且仅当old值为空。实现这样的线性化CAS，间接采纳全序播送+Log的形式。

  1. 在日志中写入一条音讯，表明想要注册的用户名。
  2. 读取日志，将其播送到所有节点并期待回复 （同步复制）。
  3. 如果表名第一次注册的回复来自以后节点，提交这条日志，并返回胜利，否则如果这条回复来自其余节点，间接向客户端返回失败。

而这些日志条目会以雷同的程序播送到所有节点，如果呈现并发写入，就须要所有节点做决策，是否批准，以及批准哪一个节点对这个用户名的占用。以上咱们就胜利实现了一个对线性CAS的写入的线性一致性。然而对于读申请，因为采纳异步更新日志的机制，客户端的读取可能会读到旧值，这可能须要一些额定的工作保障读取的线性化。

  1. 线性化的形式获取以后最新消息的地位，即确保该地位之前的所有音讯都曾经读取到，而后再进行读取（ZK中的sync()）。
  2. 在日志中退出一条音讯，收到回复时真正进行读取，这样音讯在日志中的地位能够确定读取产生的工夫点。
  3. 从放弃同步更新的正本上读取数据。

4.7 共识

下面咱们在实现线性化零碎时，实际上就有了一点点共识的苗头了，即须要多个节点对某个提议达成统一，并且一旦达成，不能被撤销。在事实中很多场景的问题都能够等价为共识问题：

  • 可线性化的CAS
  • 原子事务提交
  • 全序播送
  • 分布式锁与租约
  • 成员协调
  • 唯一性束缚

实际上，为以上任何一个问题找到解决方案，都相当于实现了共识。

两阶段提交

a. 实现

书中间接以原子提交为切入点来聊共识。这里不过多阐明，间接介绍两阶段提交，依据书中的形容，两阶段提交也算是一种共识算法，但实际上在事实中，咱们更违心把它当做实现更好共识算法的一个伎俩以及分布式事务的外围实现办法（Raft之类的共识算法实际上都有两阶段提交这个相似的语义）。

这个算法实际上比拟奢侈，就是两个阶段，有一个用于收集信息和做决策的协调者，而后通过奢侈的两个阶段：

  1. 协调者向参与者发送筹备申请询问它们是否能够提交，如果参与者答复“是”则代表这个参与者肯定会承诺提交这个音讯或者事务。
  2. 如果协调者收到所有参与者的区确认信息，则第二阶段提交这个事务，否则如果有任意一方答复“否”则终止事务。

这里一个看似非常简单的算法，平平无奇，无外乎比失常的提交多了个筹备阶段，为什么说它就能够实现原子提交呢？这源于这个算法中的约定承诺，让咱们持续拆细这个流程：

  1. 当启动一个分布式事务时，会向协调者申请一个事务ID。
  2. 应用程序在每个参加节点上执行单节点事务，并将这个ID附加到操作上，这是读写操作都是单节点实现，如果产生问题，能够平安的终止（单节点事务保障）。
  3. 当利用筹备提交时，协调者向所有参与者发送Prepare，如果这是有任何一个申请产生谬误或超时，都会终止事务。
  4. 参与者收到申请后，将事务数据写入长久化存储，并查看是否有违规等，此时呈现了第一个承诺：如果参与者向协调者发送了“是”意味着该参与者肯定不会再撤回事务。
  5. 当协调者收到所有参与者的回复后，依据这些复原做决策，如果收到全副赞成票，则将“提交”这个决定写入到本人本地的长久化存储，这里会呈现第二个承诺：协调者肯定会提交这个事务，直到胜利。
  6. 假如提交过程出现异常，协调者须要不停重试，直到重试胜利。

正是因为下面的两个承诺保障了2PC能达成原子性，也是这个范式存在的意义所在。

b.局限性

  1. 协调者要保留状态，因为协调者在决定提交之后须要担保肯定要提交事务，因而它的决策肯定须要长久化。
  2. 协调者是单点，那么如果协调者产生问题，并且无奈复原，零碎此时齐全不晓得应该提交还是要回滚，就必须交由管理员来解决。
  3. 两阶段提交的筹备阶段须要所有参与者都投赞成票能力持续提交，这样如果参与者过多，会导致事务失败概率很大。

更为奢侈的共识算法定义

看完了一个特例，书中总结了共识算法的几个个性：

  1. 协商一致性：所有节点都承受雷同的提议。
  2. 诚恳性：所有节点一旦做出决定，不能反悔，不能对一项提议不能有两次不同的决定。
  3. 合法性：如果决定了值v，这个v肯定是从某个提议中得来的。
  4. 可终止性：节点如果不解体肯定能达成决定。

如果咱们用这几个个性比照2PC，实际上却是能够认为它算是个共识算法，不过这些并不太重要，咱们重点还是看这些个性会对咱们有什么样的启发。

前三个个性规定了安全性（Safety），如果没有容错的限度，间接人为指定个Strong Leader，由它来充当协调者，但就像2PC中的局限性一样，协调者出问题会导致系统无奈持续向后执行，因而须要有额定的机制来解决这种变更（又要依赖共识），第四个个性则决定了活性（Liveness）之前的分型中说过，安全性须要优先保障，而活性的保障须要前提。这里书中间接给出论断，想让可终止性满足的前提是大多数节点正确运行。

共识算法与全序播送

理论在最终设计算法并落地时，并不是让每一条音讯去依照下面4条个性来一次共识，而是间接采纳全序播送的形式，全序播送承诺音讯会按雷同的程序发送给各个节点，且有且仅有一次，这就相当于在做多轮共识，每一轮，节点提出他们上面要发送的音讯，而后决定下一个音讯的全序。应用全序播送实现共识的益处是能提供比单轮共识更高的效率（ZAB, Raft，Multi-paxos）。

探讨

这外面还有一些事件能够拿进去做一些探讨。首先，从实现的角度看，主从复制的模式特地实用于共识算法，但在之前介绍主从复制时，但光有主从复制模型对解决共识问题是不够的，次要有两点：

  1. 主节点挂了如何确定新主
  2. 如何避免脑裂

这两个问题实际上是再次用了共识解决。在共识算法中，实际上应用到了epoch来标识逻辑工夫，例如Raft中的Term，Paxos中的Balletnumber，如果在选举后，有两个节点同时宣称本人是主，那么领有更新Epoch的节点入选。

同样的，在主节点做决策之前，也须要判断有没有更高Epoch的节点同时在进行决策，如果有，则代表可能发生冲突（Kafka中低版本只有Controller有这个标识，在前面的版本中，数据分区同样带上了相似的标识）。此时，节点不能仅依据本人的信息来决定任何事件，它须要收集Quorum节点中收集投票，主节点将提议发给所有节点，并期待Quorum节点的返回，并且须要确认没后更高Epoch的主节点存在时，节点才会对以后提议做投票。

具体看这外面波及两轮投票，应用Quorum又是在应用所谓的重合，如果某个提议取得通过，那么投票的节点中肯定加入过最近一轮主节点的选举。这能够得出，此时主节点并没有发生变化，能够平安的给这个主节点的提议投票。

另外，乍一看共识算法全都是益处，但看似好的货色背地肯定有须要付出的代价：

  1. 在达成一致性决定前，节点的投票是个同步复制，这会使得共识有丢音讯的危险，须要在性能和线性始终间衡量（CAP）。
  2. 少数共识架设了一组固定的节点集，这意味着不能随便的动静变更成员，须要深刻了解零碎后能力做动静成员变更（可能有的零碎就把成员变更外包了）。
  3. 共识对网络极度敏感，并且个别采纳超时来做故障检测，可能会因为网络的抖动导致莫名的有效选主操作，甚至会让零碎进入不可用状态。

外包共识

尽管，能够依据下面的形容本人来实现共识算法，但老本可能是微小的，最好的形式可能是将这个性能外包进来，用成熟的零碎来实现共识，如果切实须要本人实现，也最好是用通过验证的算法来实现，不要本人天马行空。ZK和etcd等零碎就提供了这样的服务，它们不仅本人通过共识实现了线性化存储，而且还对外提供共识的语义，咱们能够依靠这些零碎来实现各种需要：

  1. 线性化CAS
  2. 操作全序
  3. 故障检测
  4. 配置变更

4.8 本章小结

本章破费了微小力量解说了分布式系统中的另一种一致性问题，外部一致性，这种问题次要是因为复制的滞后性产生，首先咱们介绍了这种问题的起源，而后映射到分布式系统中，对不同一致性进行分类。

对于外面的强一致性，咱们进行了具体的探讨，包含定义、应用场景以及实现等方面，并从中引出了像全序与偏序、因果关系的捕获与定义（Lamport工夫戳）、全序播送、2PC最初到共识，足以见得这种一致性解决起来的复杂性。

5. 再谈分布式系统

至此，咱们从复制这一主题登程，探讨了分布式系统复制模型、挑战、事务以及共识等问题，这里联合两篇文章的内容，我尝试对分布式系统给出更细节的形容，首先形容个性和问题，而后给出特定的解决。

  • 与单机零碎一样，分布式系统同样会有多个客户端同时对系统产生各种操作。每个操作所波及的对象可能是一个，也可能是多个，这些客户端并发的操作可能会产生正确性问题。
  • 为了实现容错，分布式系统的数据个别会有多个备份，不同正本之间通过复制实现。

  • 常见复制模型包含：

    • 主从模式
    • 多主模式
    • 无主模式

  • 而从时效性和线性一致性登程，可分为：

    • 同步复制
    • 异步复制
  • 异步复制可能存在滞后问题，会引发各种外部一致性问题。

  • 分布式系统相比单机零碎，具备两个独有的特点。

    • 局部生效
    • 短少全局时钟

面对这么多问题，如果一个现实的分布式数据系统，如果不思考任何性能和其余的开销，咱们冀望实现的零碎应该是这样的：

  1. 整个零碎的数据对外看起来只有一个正本，这样用户并不必放心更改某个状态时呈现任何的不统一（线性一致性）。
  2. 整个零碎如同只有一个客户端在操作，这样就不必放心和其余客户端并发操作时的各种抵触问题（串行化）。

所以咱们晓得，线性一致性和串行化是两个正交的分支，别离示意内部一致性中的最高级别以及外部一致性的最高级别。如果真的实现这个，那么用户操作这个零碎会十分轻松。但很遗憾，达成这两方面的最高级别都有十分大的代价，因而由着这两个分支衍生出各种的外部一致性和内部一致性。

用Jepsen官网对这两种一致性的定义来说，外部一致性束缚的是单操作对单对象可能不同正本的操作须要满足工夫全序，而内部一致性则束缚了多操作对于多对象的操作。这类比于Java的并发编程，外部一致性相似于volatile变量或Atomic的变量用来束缚实现多线程对同一个变量的操作，而内部一致性则是相似于synchronize或者AQS中的各种锁来保障多线程对于一个代码块（多个操作，多个对象）的拜访合乎程序员的预期。

然而须要留神的是，在分布式系统中，这两种一致性也并非齐全孤立，咱们个别采纳共识算法来实现线性统一，而在实现共识算法的过程中，同样可能波及单个操作波及多个对象的问题，因为分布式系统的操作，往往可能是作用在多个正本上的。也就是说，相似2PC这样的分布式事务同样会被用来解决共识问题（尽管书中把它也成为共识，但其实还是提供了一种相似事务原子性的操作），就像Java并发编程中，咱们在synchronize办法中也可能会应用一些volatile变量一样。

而2PC不是分布式事务的全副，可能某些跨分区的事务同样须要用基于线性一致性的操作来满足对某个对象操作的一致性。也就是说想残缺的实现分布式的零碎，这两种一致性相互依赖，彼此互补，只有咱们充沛理解它们的核心作用，能力熟能生巧地在实战中利用这些看似干燥的名词。

6. 士别三日，当另眼相看--再看Kafka

理解完下面这些一致性，咱们再回过头来看看Kafka的实复制，咱们大抵从复制模型、外部一致性、内部一致性等角度来看。Kafka中与复制模式相干的配置大抵有上面几个：

  1. 复制因子（正本数）
  2. min.insync.replicas
  3. acks

用户首先通过配置acks先大体晓得复制模式，如果ack=1或者0，则示意齐全的异步复制；如果acks=all则代表齐全的同步复制。而如果配置了异步复制，那么单分区实际上并不能保障线性一致性，因为异步复制的滞后性会导致一旦产生Leader变更可能失落曾经提交的音讯，导致突破线性一致性的要求。

而如果抉择ack=-1，则代表纯的同步复制，而此时如果没有min.insync.replicas的限度，那样会就义容错，多正本原本是用来做容错，后果则是有一个正本出问题零碎就会就义掉Liveness。而min.insync.replicas参数给了用户做衡量的可能，个别如果咱们要保障单分区线性一致性，须要满足少数节点失常工作，因而咱们须要配置min.insync.replicas为majority。

而针对局部生效的解决，在实现复制时，kafka将成员变更进行了外包，对于数据节点而言，托管给Controller，间接由其指定一个新的主正本。而对于Controller节点自身，则将这个职责托管给了内部的线性存储ZK，利用ZK提供的锁于租约服务帮忙实现共识以达成主节点选举，而在高版本中，Kafka去掉了内部的共识服务，而转而本人用共识算法实现Controller选主，同时元数据也由原来依赖ZK变为自主的Kraft实现的线性化存储进行自治。

而在内部一致性领域，目前低版本Kafka并没有相似事务的性能，所以无奈反对多对象的事务，而高版本中，减少了事务的实现（详见blog）。因为对象逾越多机，因而须要实现2PC，引入了TransactionCoordinator来承当协调者，参考下面2PC的根本流程。

一个大抵的实现流程根本如下：首先向协调者获取事务ID（后文统称TID），而后向参与者发送申请筹备提交，带上这个TID，参与者当初本地做append，如果胜利返回，协调者长久化决策的内容，而后执行决策，参与者将音讯真正写到Log中（更新LSO，与HW高水位辨别）。然而上文也讲了2PC实际上是有一些问题的，首先2PC协调者的单点问题，Kafka的解决办法也比较简单，间接利用本人单分区同步复制保障线性一致性的个性，将协调者的状态存储在外部Topic中，而后当协调者解体时能够立即做转移而后依据Topic做复原，因为Topic自身就单分区而言就是个线性存储。

另外，就是2PC的协调者实质是个主从复制的过程，因为TransactionCoordinator原本就挂靠在Broker上，所以这个选举仍然会委托给Controller，这样就解决了2PC中的比拟辣手的问题。而对于事务的隔离级别，Kafka仅实现到了“读已提交（RC）”级别。

7. 分布式系统验证框架

在分布式畛域有两把验证分布式算法的神器，其中一款是用于白盒建模的工具TLA+TLA Homepage，对于TLA+，强烈推荐看一看Lamport老人家的视频教程视频教程（带翻译），或去看一看《Specifing Systems》。咱们会晓得，这个语言不光能定义分布式算法，应该说是能够定义整个计算机系统，如果把握了应用数学定义零碎的能力，能够让咱们从代码细节中走进去，以状态机的思维来对待零碎自身，咱们可能会有不一样的感悟。TLA+的外围是通过数学中的集合论，数理逻辑和状态搜寻来定义零碎的行为。咱们须要正确的对咱们的零碎或算法做形象，给出形式化的规约，而后应用TLA+进行验证。

另一款则是黑盒Jepsen Homepage，其外围原理则是生成多个客户端对一个存储系统进行失常的读写操作并记录每次操作的后果，在测试两头引入故障，最初依据检测这些操作历史是否合乎各种一致性所满足的规定。咱们简略看下它的架构，而后本文将大抵演示它的应用办法。

Jepsen次要有上面几个模块形成：

  1. DB Node（引擎自身的节点，存储节点）。
  2. Control Node管制节点，负责生成客户端，生成操作，生成故障等，其与DB Node通常是SSH免密的。
  3. Client客户端用于进行失常读写操作。
  4. Generator用来生成打算。
  5. Nemesis故障制造者。
  6. Checker用来进行最初的一致性校验。

咱们团队应用Jepsen测试了Kafka零碎的一致性，其中Kafka客户端与服务端的配置别离为：同步复制（ack=-1），3复制因子（正本数），最小可用正本为2（min.insync.isr）。在该配置下，Jepsen内置的故障注入最初均通过了验证。

8. 小结

咱们的数据之旅到这里就要告一段落了，心愿大家通过我的文章理解常见分布式系统的外围问题，以及面对这些问题所谓的事务，一致性和共识所能解决的问题和内在联系，可能在适当的时候正当的应用校验工具或框架对咱们的零碎的正确性和活性进行校验，这样就达到两篇系列文章的目标了。

分布式系统是个“大家伙”，心愿今后可能跟大家一起持续致力，先将其“庖丁解牛”，而后再“一一击破”，真正可能掌控一些比较复杂的分布式系统的设计。最初感激团队中的小伙伴们，能将这样的思考系统化的产出，离不开组内良好的技术分享文化和浓重的技术气氛，也欢送大家退出美团技术团队。

9. 作者简介

仕禄，美团根底研发平台/数据迷信与平台部工程师。

浏览美团技术团队更多技术文章合集

前端 | 算法 | 后端 | 数据 | 平安 | 运维 | iOS | Android | 测试

| 在公众号菜单栏对话框回复【2021年货】、【2020年货】、【2019年货】、【2018年货】、【2017年货】等关键词，可查看美团技术团队历年技术文章合集。

| 本文系美团技术团队出品，著作权归属美团。欢送出于分享和交换等非商业目标转载或应用本文内容，敬请注明“内容转载自美团技术团队”。本文未经许可，不得进行商业性转载或者应用。任何商用行为，请发送邮件至tech@meituan.com申请受权。