本文从普遍认为的分布式系统中最重要的数据一致性说起。内容适合>=0年技术相关经验的人。一、数据一致性问题分析1、为什么需要分布式系统？任何可以持续使用和发展的东西，必然有它的价值，分布式系统也是如此。我认为分布式系统产生的主要目的是“快速”和“海量”。这个“快”可以分为两个方面：系统处理速度快，开发速度快（持续时间短）。缩短整体耗时。例如：本来一个人做一件事需要两分钟。然后我雇了两个人来帮助我完成每个部分，所以理想情况下它可以在一分钟内完成。当然，这两个方面中的第二个在某种意义上是可以克服的，但是第一个是无法克服的。因为没有一个程序或者计算机的性能是无限的，如果有，那么分布式系统也不会像现在这么普遍（很多时候能用钱解决的问题都不是问题）。“海量”是因为没有无限大的硬盘，所以我们需要将数据存储在不同的硬盘上以满足需求。这些硬盘可能在不同的主机、不同的机房、不同的地区（未来可能在不同的星球）。2分布式系统的副作用所谓万事万物都是矛盾统一体，都有两个方面。分布式系统在带来上述好处的同时，也带来了业界普遍认为的最大问题——数据一致性问题。系统是给人用的，构成使用场景的概念叫业务。业务是核心。对于一个系统来说，业务的发展最终还是要以数据为基础。我可以慢一点，我可以低一点，我可以把它搞得很复杂，这些我都可以承受。但唯一不能容忍的就是数据问题——数据错误、数据不一致等等。分布式就是分工协作，一个人只负责一件事情的一部分。这样的例子在生活中比比皆是。以聚会为例：有人准备食物，有人准备酒水，还有人准备场地布置。每个人都可以同时做这些事情，但是如果有一个环节断了，或者不符合晚会的主题，那就是失败了。（不知道为什么，我脑海里浮现的是一场发布会，大家齐声欢呼，把高脚杯里的二锅头一饮而尽……）。再举一个电商场景的程序例子：这里的四个操作是从目标的角度来看的。其实顺序并不重要。重要的是要么全部成功，要么全部失败。从本质上讲，这个问题类似于人与人之间的沟通问题。与通信唯一不同的是，对于程序来说，并不总是需要得到响应，没有响应也是一致的。当一个东西被分成100份时，是很可怕的。从概率的角度来看，达成共识的概率是2/5050。这里给出的程序示例并不严谨，因为在实际的分布式系统中，除了“写”操作外，还有“读”操作，所以一致性问题比这更复杂，会做更详细的解释之后。3数据不一致的原因那么是什么原因导致数据不一致呢？一个原因是编程问题（代码写错了）。这个很容易理解，也很容易想到解决方案——多做测试，验证是否符合预期。常见的单元测试、接口测试、自动化测试、集成测试等，都是为了更低成本地将bug无限接近于0，这也为“测试工程师”这个岗位创造了更大的作用。但是，假设真的没有bug，还是会出现数据不一致的情况。因为软件运行在硬件上，所以也有硬件因素。对于我们这里的大多数人来说，我们对硬件的控制不如对软件的控制。其中，最严重的是网络问题。网络是一个比其他组织更大、更复杂的组织，随着LAN和WAN范围的扩大，未知因素将变得更加严重。想象一下，每台主机只是大型网络中的一个小连接点。它携带的链接越多，就越容易出现问题。可能有些朋友会有疑惑。其他的，比如硬盘驱动器和停电，也可能会导致问题。为什么网络问题最严重？事实上，硬盘和电源就像你身体的一部分，比如手和脚。互联网是人与人之间的沟通渠道，比如手机通话。虽然你没有主动挂断电话，但在整个通话过程中，有很多被打断的可能。被第三方截获。相信大家也能认同，手机出现异常的概率远高于自己的手脚。由于现实中网络的特点，经常会遇到延迟、丢包、乱序等问题。为了解决这些问题，从1969年互联网刚出现时（美国军方根据ARPA制定的协议用网络连接了4所大学）到现在，在过去的几十年里，出现了很多理论和解决方案。这些都会在后面的文章中为大家一一梳理。这部分先跟大家分析什么是一致性。4一致性详解什么叫达成共识？说起来很简单——任何时间、任何地点看到的同一件事，是完全一致的。比如一场足球比赛，无论我们是在现场还是在电视机前，看到足球从球员A传到球员B，信息都是一样的。但严格来说，这并不是真的一致，因为电视需要通过卫星信号、网络传输等方式接收到这些信息，我们看到的时候，肯定比现场的人晚。即便是在场的人，根据所处的位置，理论上看到的信息也会有延迟差异，但是因为光速很快，相差几百米之内，延迟小到感觉不到根本。可以得出结论，当考虑时间维度时，并没有真正的一致。而且，我们不需要在分布式系统中实现真正的一致性。因为越接近一致性，系统就相当于重新统一为一个整体。在某个时刻，只能做一件事，完全失去了分布式系统的两个目的之一“快”的优势。因此衍生出多种一致的变体，适用于不同的场景。为了便于理解，我们按从低到高的严格程度来说话。大多数情况下，为了尽可能“快”，系统中使用的方案大多是所谓的最终一致性，即在一定条件下容忍不一致，优先保证局部一致性，然后通过一个一系列复杂状态同步实现全局共识。最终一致性有许多可实现的分支。这里有几个常见的。因果一致性：只需要保证具有因果关系的操作序列。比如朋友圈的回复功能。问“吃饭了吗？”必须在回答“你吃过了吗”之前来过。阅读您所写的内容以保持一致性：文字看起来很笨拙，但很容易解释。比如你在朋友圈下回复一句话，其他朋友不需要马上看到你的回复，但你必须马上看到，否则回复到哪里去了？会话一致性：与某人的聊天可以理解为一个会话。虽然聊天也有一定的因果关系，但在大多数场景下更多的是逻辑顺序。比如你解释一个事情，它分为3条信息：first...，then...，finally...。如果不保证这里的一致性那么可能会变成：last...,first...,then....比局部一致性更严格的是全局顺序一致性[1]，保证所有进程看到的全局执行顺序一致，每个进程本身的执行顺序与实际一致发生的顺序。注：文中[1-6]可在文末找到相应的参考资料，如上文提到的足球比赛。比如实际发生的事情是①梅西传球给C罗，②C罗把球传给梅西，那么大家看到的顺序应该是这样的。就算现场观众看到了②，电视机前的我们还没有看到①，不过没关系，这件事发生的先后顺序全世界都是一样的。更严格的说，就是在全局顺序一致性的基础上，增加一个相对时间一致性的要求，业界称之为线性一致性[2]。还是用上面梅西和C罗传球给对方的例子来比喻。就相当于梅西将球传给C罗之后，整个球场都“暂停”了，等待着所有观赛的人去接球。在这个传球信息之后，C罗就可以进行下一次回传。这里需要一个神（全球时钟）来“暂停”。这是我们实际能做的极限。在满足此类需求的系统中，最著名的当属Google的Spanner。不同级别的一致性总结如下：2.通过共识达成数据一致性上一节我们已经分析了数据一致性问题，那么如何解决故障导致的不一致问题呢？通过共识达成。因此，这部分将重点放在“共识”这一点上。1什么是“共识”？为什么会这样？一致性问题其实是一个“结果”，本质上是数据冗余造成的。如果没有冗余，就不会有一致性问题。分布式系统中各个子系统之所以能够相互协作，是因为相同的数据作为“令牌”是冗余的。否则，我连你都不认识，何必跟你合作？所以如果这个“令牌”变了，你必须通知我，否则我不认识你了。就这种“令牌”变化达成共识的过程称为“共识”。所以：一致性是结果，共识是实现这个结果的过程，或者说是手段。在分布式系统中，冗余数据的场景不仅限于此，因为系统越大，越不能容忍某个子系统失效后的蝴蝶效应，所以往往做成高可用。小明一号倒下了，还有成千上万的小明X坚守在岗位上，理想状态下24小时提供服务。高可用的本质是存储相同数据的多份副本，对外提供服务。比如每个小明X号都有一个《按摩指法白皮书》，谁请假都可以享受到其他小明X号提供的同样的按摩服务。但是如果这本书改了，就得通知大家，因为这是服务的整体和源头，所以数据冗余的问题在高可用的集群中更加突出。事实上，如果分布式系统中的每个节点都能保证即时响应和无故障运行，达成共识是很容易的。就像我们人类一样，只需要在一定范围内咆哮，通过稳定的空气传播。相关人员是否收到消息并做出回应，几乎可以“瞬间”完成。但正如上文所说，这样的系统只是在想象中，经常会出现请求响应延迟、网络中断、节点失效，甚至恶意节点故意破坏系统的情况。这就引出了经典的“拜占庭将军问题”[3]。2拜占庭将军问题我们一般把“拜占庭将军问题”分为两种情况：拜占庭错误。表示通过伪造信息的恶意响应而导致的错误。非拜占庭错误。发生错误而没有响应。这个问题的核心在于：分布式网络中如何解决某个变化以获得一致的执行结果是多方认可的，同时这个信息是确定的、不可逆的。比如如何让所有的小明X号都收到?而不是其他的，并且把原来的一个销毁。许多“共识”算法都是从这个问题中衍生出来的。解决“拜占庭错误”的称为拜占庭容错（BFT）算法，解决“非拜占庭错误”的称为崩溃容错（CFT）算法。从这两个名字也可以看出本质的工作就是“容错”。有些小伙伴在日常工作中可能并没有那么强烈的“容错”重要性意识——它不会产生BUG或异常数据吗？但在航天领域，一个小小的失误就可能导致整个发射失败，代价非常高昂。巨大的。如果想深入了解“拜占庭将军问题”，可以自行查阅相关资料，这里就不展开了，在文末附上我们刚刚标注的论文.“拜占庭错误”在我们常见的软件开发中一般不会考虑，但对于区块链项目来说却是必然。但是，在主流的分布式数据库中，比如TiDB的Paxos算法，CockroachDB的Raft算法，都可以看到“非拜占庭错误”。虽然我们所有人都在日常编码中，但了解数据库的底层原理并不是必须的。但是只要来到应用层面的高可用，至少“非拜占庭错误”是一个必须要面对的坎。BFT算法BFT算法有两个分支。“基于确定性”和“基于概率”。先说“确定性”：这类算法是指一旦对某个结果达成共识，就不可逆转，即共识就是最终的结果。其代表作是PBFT（PracticalByzantineFaultTolerance）算法[4]。由于有了央行的背书（区块链数字票据交易平台），名气更大了。算法原理如下图所示：▲图片来源于网络，版权归原作者所有3位都是“老师”，值得注意的是3号指挥官造反了。整个过程是这样解释的：“请”：总司令对军长下达命令，“办吧！”。“预准备”：指挥员向三个师长广播命令。“备”：各师长收到同意后，将“收到”发给军长和另外两个师长。“commit”：每个师长收到2f个师长的“received”请求（军长不准备），向军长和另外两个师长发送“随时开始”。（f为可以容忍的拜占庭节点数）“回复”：每个师长收到2f+1条“随时开始”消息后，可以认为总司令的命令已经到了“开始”随时”相关师长之间的信息。如果真的想深入了解PBFT，内容还是很多的，这里就不继续展开了。感兴趣的朋友可以在文末参考文献处自行查阅论文。先说“基于概率”：这类算法的共识结果是暂时的。随着时间的推移或某种强化，共识结果被推翻的概率越来越小，成为??事实上的最终结果。其代表作是PoW（ProofofWork）算法，曾经高达20000美元一枚的比特币就是基于这个算法。算法原理用“修仙”做一个简单的比喻（比特中的实际算法比这个复杂得多）：自己努力修炼，让一半以上的仙人认可你的修为，同意你成仙.然后你就变成仙女了。并参与判断其他人未来能否成为“仙女”。如果想通过贿赂来实现，随着团队人数的增加，贿赂的成本也会增加，可以认为行贿的人越少，被误判的概率就越低，最终就越高贿赂的代价。可信的。被误判概率的公式为：0.5^number，若number=6，则误判概率为1.5625%。如果数字=10，则已经是0.09765625%，呈指数下降。值得注意的是，“基于确定性”和“基于概率”对非合作节点的标准不同。前者最多能容忍1/3，后者则不到1/2。4CFT算法就是上面提到的CFT算法解决的是在分布式系统有故障但没有恶意节点的场景下达成共识的问题（即消息可能丢失或重复，但没有错误消息）。“拜占庭将军问题”的提出者LeslieLamport在他的另一篇论文[5]中也提出了与此类似的“Paxos问题”。论文中将这个问题比作一个故事，如下：希腊Paxon岛的“执法者”在“议会大厅”投票通过“法律”，通过“服务员”传递纸条来交换信息，每个“执行者”都会把通过的“法律”记录在自己的“账户”里。问题是“执行者”和“服务器”不可靠，他们随时会因为各种事情离开“议会大厅”，新的“执法者”随时可能进入“议会大厅”进行合法投票，用什么样的方式才能让投票过程正常进行，所通过的“法律”不会冲突。——百度百科这里的关键对象是在我们的系统中，可以类比为：议会大厅=分布式系统执行者=某个程序服务器=RPC通道账号=数据库法=一改操作LeslieLamport自己也提出了解决这个问题的算法问题-Paxos算法[6].这个算法的关键是refl受以下三个定义的影响：每一个“零钱”都有一个唯一的编号，可以用来辨别新旧；“执行者”只能接受比已知“变化”更新的变化；这两个“变化”必然涉及同一个“执行者”。这3点只是保证一致性最关键的部分，整个内容还有很多。感兴趣的朋友可以在文末参考部分自行查阅论文。“Paxos”算法是一个leaderless算法，实现起来比较复杂，所以产生了很多变种来简化它。其中最著名的应该是2013年问世的“Raft”，“Raft”算法是一种领导力算法。共识由以下两个过程保证：只有一个活着的领导者，领导者负责跟随者的数据同步；如果leader“掉线”，每个follower都可以成为candidate，最终比较谁的term最新，谁就是新的leader。此项是每个节点内部维护的自动递增数。虽然follower投票是先到先得，但同一任期的多位候选人仍会获得相同的票数（称为“分裂投票问题”），并会进行新一轮投票，直到胜者已定。由于Raft使用随机定时器来增加任期，网络不稳定，再次遇到相同票数的概率大大降低。整个过程比较复杂。有一个Raft算法动画推荐给大家。有兴趣的可以看看：http://thesecretlivesofdata.com/raft/。顺便说一句，大家经常使用的Zookeeper中的“ZAB”（ZooKeeperAtomicBroadcast）算法也是一种CFT算法，它是基于FastPaxos算法实现的。5结论回过头来看，我们发现如果想要更严格的一致性，就需要增加相互通信确认的次数，但这会导致性能低下，就像PBFT和Paxos一样。但是分布式系统就是这样。处处需要平衡，找到最合适的才是最重要的。说完数据层面的“共识”问题，下回再说说“分布式事务”问题，围绕常见的CAP和BASE理论展开。
