网易视频云：分布式系统的三类一致性挑战与解决方案

　　数据多副本间的一致性

　　存储系统是千差万别的，可能拿来存放视频这种动辄几个G的大文件，也可能存放几KB的KV键值对数据，还可能是MySQL这种关系型的数据库。虽然上层数据结构千差万别，在保证数据多副本一致性方面，都逃不出一个基本方式，即状态机复制（state machine replication）。参考有限状态机的行为，只要是固定的一串输入内容，输出必然是相同的。因此问题就变成一定要保证所有副本服务器的输入内容必须一致，那所有副本回放完这串日志后，内部存储的数据也必然是相同的。

　　要做好状态机复制，需要干两个事情。第一个是需要保证消息全序（total order），所有的消息都必须是有严格先后顺序的，要达到这个目标就必须保证一个时间内只有一个指挥官在发出指令，否则多个副本各说各话，完全不知道先做哪个后做哪个。这就涉及到存储系统必须要干的事情：“选主leader”。第二件事情，是要开发出一个比较牛逼的算法，能够保证无论发生什么异常，各个副本获得的日志都是严格一致的。最容易想到的，是让leader服务器把命令向所有的副本都下发一遍，大家都返回ok了之后，这次请求才算完。这样是否就算严格一致了？其实是不行的，在一些异常情况和leader服务器切换时，会有很多问题。其实，要解决这个问题也不用多费脑筋了，业界已经有了共识：paxos算法。基于这个算法能够保证任何情况下都能副本间一致，而且经过优化后可保证大部分情况下只要一轮通信就能达成一致，性能也能接受。一切都完美，对于一个一致性算法真不能要求他更多了。Paxos有个小问题是不能保证消息全序，不过这个事情并不难搞。我们新版本分布式文件系统用的算法PacificA、zookeeper用的ZAB，都解决了这个事情。这些都算是在某些更严格要求场景下的Paxos特例。

　　基于状态机复制来做数据多副本的一致性，要面临的一个困难是性能可能达不到要求。主要是两方面，一个是底层的日志复制协议吞吐量不够高。这个在我们的分布式文件系统中就遇到过，因为日志本身就包含了数据内容，而文件系统的数据量很大，即使做了多条日志合并打包发送后，性能仍旧不好。要彻底解决这个事情，需要在leader服务器上做pipeline，即不等副本返回响应就立即发送下一批日志。说起来简单，但实现起来难度比较大，尤其是和各种异常场景混杂在一起后算法的正确性需要仔细论证。我们在分布式文件系统设计时经过了一番激烈讨论，最后还是放弃了。因为工程上的工作量较大，并不是理论上搞不定，google分布式数据库的paxos算法实现中就包含了pipeline机制。另一个问题是上层服务器在回放日志时，为了保证消息全序，必须使用单线程回放，导致回放性能达不到要求。这个事情在数据库里面特别明显，只要线上写压力偏大，MySQL的从节点就会跟不上。MariaDB和淘宝都对此做了优化，但跟数据库的一些自有特性纠缠在一起，要彻底搞定还是比较难。因此，基于状态机复制的这个现实，在最上层做适当的分区，采用并行复制组来提升整体吞吐量是有必要的。

　　最后讨论一下基于状态机复制机制实现系统的可用性问题。Paxos算法本身是有容错的，挂掉一个底层节点不会造成数据无法写入。整套机制的单点在于用于消息排序的leader服务器。Leader服务器如果宕机，就需要重新执行选主算法，中间会有一段时间不可用。因此，基于状态机复制来实现的存储系统，可用性注定是没法做到非常高的。另外，如果考虑到跨机房多副本部署，机房间网络出现问题会出现网络分区的情况，此时存在单点的系统可用性会更低。其实大部分情况没那么苛刻。如果真要对这个问题求解，Amazon的dynamo系统算是一个解决方案。Dynamo为了提升可用性，放宽了对数据一致性的要求，消息完全不排序，而是通过一个向量时钟（vector clock）的算法追踪消息的路径进行智能排序。通过这个算法，99.9%的请求最后都没有问题，但确实会有极个别请求会出现无法判断先后次序的冲突情况，此时只能把这个问题丢给苦逼的程序猿来解决。

　　对异常情况实现的复杂性决定了这个方案并不流行，起码在国内真正用的人不多。不知道当时Amazon的工程师为何选了这个方案。结论是，如果系统经过了非常仔细考虑，要实现极高可用率的存储系统，也是有可能实现的。前提是降低了数据一致性后，客户端必须做容错。

　　分布式事务带来的问题

　　在之前做分布式数据库时，遇到了数据一致性的另一个问题。这个问题的起因是数据库中有一个事务的概念，其中的原子性需要保证事务中多条记录的修改或者同时成功，或者同时失败。这个问题的解决主要是依靠两阶段提交算法。算法的核心逻辑比较简单，由一个事务协调器发起两轮操作命令，第一轮prepare命令询问各个参与者是否同意本次操作，如果都同意则发起第二轮commit命令，在各个参与者服务器上真正提交本次事务。

　　两阶段提交算法能够保证事务中多条记录之间的一致性，在实现时被人诟病最多的是算法的活性存在较大问题。线上运行时，事务参与者各服务器出现宕机或者网络出现波动，都有可能导致某些数据库上出现悬挂的中间状态事务，即事务永远处于prepare状态中。而根据两阶段提交的语义，此时事务包含的所有数据行都会被锁住。更悲剧的问题在于，我即使做一个脚本定期扫描各数据库上的prepare悬挂事务，我也不敢做出任何后续处理，因为无论是把这些事务提交或者回滚，都有可能出现数据不一致。为了弥补这个缺憾，学术界提出了一个三阶段提交的办法，在commit之前再插入一个预提交的状态，处于预提交阶段的事务如果在等待一段时间超时后仍然没有收到后续指令，可以按照事先的约定自行提交或回滚。整个事情的核心在于引入了超时，灵感可能来源于分布式领域的一个著名定理：FLP定理 - 对于一个只是依靠消息通讯的异步系统来说，如果出现了服务器异常，无论依靠什么精妙的算法，都有可能导致本次请求的各参与方处于永久不一致的状态。两阶段提交的问题也属于异步系统的范畴中。而定理有一个明白的前提，就是大家不能依靠时间来做任何的超时假设。另一个更简单粗暴的方法，我让事务各参与者永远不会失败，事情不就结了吗？具体做法就是把各服务器全部用paxos协议来实现，而paxos本身是具有一定容错性的。这个方案目前看起来还更靠谱一些，Google已经把它做出来并大规模应用了。其实很多年前，数据库和分布式领域的两位图灵奖得主Jim Gray和Leslie Lamport就合作研究过这个方案，并专门发表了论文。

　　其实，两阶段提交模型在理论上也还没有达到完美的程度。回顾事务的ACID属性，有一个要求是原子性，一个事务要么回滚，要么提交，在任何情况下都不允许出现一个事务所做的修改只有一部分可见的情况。而在两阶段提交中，如果在两个节点分别执行commit操作，用户执行了read操作，完全有可能只能看到事务执行结果的一半。对此情况目前无能为力，只能自我安慰：此次操作我们是保证最终一致性的。记得我们当初在开发分布式数据库云服务时，这个问题导致了一个更棘手的场景。当时想开发一个数据库备份功能，用户点击备份后就把底层所有节点数据自动备份下来。由于上文所论述的无法获取全局一致性视图的问题，可能我们备份的数据只有一个事务的一半。这会导致更严重的问题，备份的数据一旦拿来做恢复，会导致那些残缺的事务永远处在部分更新的状态中。在目前底层基于MySQL的架构下，这个问题已经很难解决了。我们来看一下Google是如何做的吧。首先还是需要有一个地方做消息排序，每个消息分配一个递增的全局日志号。然后在底层存储节点的每条数据中记录该次更新的日志版本号。当用户来查询时，首先获取到当前最新的全局日志版本号，然后在每个节点中根据该日志号来进行查询，就能保证返回给用户的数据是一个全局一致的视图。

　　新形势下的新挑战

　　上文提到分布式领域数据一致性的几个主要问题，基本上都有了结论，并且有大量现成的第三方编程库可以用，程序猿和攻城狮们都觉得好幸福。悲剧的是这个世界好像永远都不如人所愿，看看Google的分布式数据库演进就知道了。先是搞了Bigtable，接着搞了Megastore，最后又搞了Spanner。估计去采访Jeff Dean，他也会满腹牢骚：难道真是我天生爱折腾吗，还不是被逼的。Bigtable做完后分布式数据库的基本样子就定下来了，Megastore属于google在修炼神功过程中走火入魔的产品，Spanner被业界认为是第一个全球数据库。全球数据库的意思，是世界上任何一个人发了一条消息，我就能立马看到并保证数据的严格一致。举个例子，这个事情如果换在我们这边该怎么做呢？第一步就是在杭州中心机房建一个数据库，把这个产品先做出来。后来有客服反馈说，非洲人民抱怨发消息太慢，需要被关怀。好吧，那就在香港拉一条专线，把所有的国外请求都代理过来，降低网络上的时延。恩，确实有改进，但是每次服务器请求还是在百毫秒以上，用户用起来还是觉得不爽。然而目前我们找不到更好的办法了，会面临一个两难问题 - 如果要提高用户体验，就需要在非洲部署一套数据库，但如果某个操作需要同时读写两个库中的数据，根据前面的讨论，分布式事务的强一致性还需要有一个地方集中分配全局更新日志号。Spanner的想法非常的创新，利用了真实世界的时间戳来充当全局日志号。Google在全球每个机房中同时部署了GPS+原子钟，保证全球各地的时钟误差能够控制在一个合理范围内（ε，小于5ms）。当每个paxos复制组更新数据时，只要严格控制前后两个事务的更新时间小于2ε，就意味着事务相互之间无重叠，时间戳是单调递增的，此时时间戳就能完全替代日志号来做事务版本控制。当产品需要做跨地区的两阶段提交时，确实需要联系两个paxos复制组，暂时卡住数据更新并协调一个时间戳作为全局日志号。但跨机房的两阶段提交毕竟是一个很少概率发生的事情，基于时间戳来设计事务并发控制机制，确实能够使得绝大多数的更新操作能够在非常短时间内完成。

　　Spanner的设计，核心思想就是依靠物理时钟来代替全局日志号，这个想法看似简单，在此之前在架构师眼里这事情完全是不可想象的。三十年前Leslie Lamport有一篇专门论述时间和消息顺序的文章，被认为是分布式领域最重要的一片论文，就专门指出了无法依靠全局时间的原则。确实，在现实世界里，绝对时间是不存在的，即使费了九牛二虎力气把两台机器的时间校准到分毫不差，根据相对论，只要机房管理员哪天不小心把一台机器移了一下位置，时间又不一样了。因此之后这么长时间里，在数据存储这种要求强一致的系统中，再没有人拿时间戳来设计系统。Google这种完全反经典的做法，如果没有强大的工程能力做后盾也是白搭。如果单纯依靠时间校准NTP协议，是无法在全球范围内把时间误差缩短到5ms之内的，世界上也只有少数几个公司能够在所有机房里安装GPS天线。自去年起，就开始有一个风潮，国内的顶尖互联网公司开始走向国外。形势逼人，要在全球范围内提供优秀的用户体验，这可能会是摆在一线互联网公司面前的下一个难题。NOS已经关注到这个问题，并开始寻求解决方案，而作为更底层组件的数据库，这方面的要求更高。打破经典不走寻常路，好像一直是国人的一个长项，哪天国人也能设计出比肩Spanner的优秀全球数据库，也未可知。