你好，我是陈浩网名猪耳朵house.在课程之前呢，我先给你提醒一下，这节课呢会出现很多的图片啊，为了方便你更好的理解我讲的内容，建议你打开文稿，听我讲解。
而且本节课呢我会推荐大量的英文文章啊，看着文稿也能让你更容易理解和对应。
好了，正式开始我们今天的课程，我们在之前的系列文章分布式系统架构的本质中说过，分布式系统的一个关键技术是数据调度。
因为我们需要扩充节点，提高系统的高可用性，所以呢必须要冗余数据节点。
那建立数据节点的覆盖看上去容易，但是其中最大的难点啊就是分布式一致性的问题。
那下面呢我会和你聊一聊数据调度世界中的一些技术点和相关的技术论文。
那对于分布式的一致性问题呢，相信你在前面啊看过好几次文中的这张图。
从图中呢我们可以看出pixel算法的重要程度。参考资料:https://51gx.top/detail/259
还有人说啊分布式下真正的一致性算法只有pixel.那pixel算法呢是莱斯利兰伯特在一九九零年提出来的一种基于消息传递，并且呢具有高度容错特性的一致性算法。
但是这个算法太过于晦涩了啊，所以一直以来呢都属于理论上的论文性质的东西。
那它进入工程圈的源头呢，是google的一个分布式锁服务。
Travel lock啊用在了big table里面，直到google发布了这两篇论文啊，pixoas才进入到工程界的试验中来。
那第一篇呢是big table, a distributed story system for structure data.那第二篇呢是the travel lock service for loosely coupled distributing systems.那google与big table相起名的还有另外两篇论文啊，分别是在google file system,还有MAREDCE simplified data processing on large clusters.不过呢这一篇论文中啊并没有讲太多的pixel算法细节上的内容，反而在论文pixel smith life和nature narrow perspective.啊，这里面提到了很多功能实践的细节，如google实现python的时候呢，遇到的各种问题和解决方案，讲述了从理论到实际应用，这两者之间啊巨大的鸿沟，尤其是在满地都是坑的分布式系统领域。
那这篇论文啊没有过多的讨论拍克算法本身，而是在讨论如何将理论应用到实践，如何弥补理论在实践中的不足啊，如何取舍，如何测试。
那这些在实践中的各种问题啊，才是工程的魅力。
所以建议啊你也读一读pixel算法的原版论文啊，我在这里就不贴了，因为一来啊比较晦涩，二来呢也不易懂。
那这里呢我推荐一篇比较容易读的neoggorims ms actuals.那这篇文章啊还有一些小动画帮你读懂。
那还有一篇可以帮助你理解的文章呢，叫做pixils by examples.那如果你要自己实现pixel算法啊，这里也有几篇文章供你参考。
那第一篇呢是pixel s made coat,作者是马克罗普迪米，它实现了一个pixel的开源库live pixels.这第二篇呢是pixel for system builders.他从一个系统实现者的角度啊，讨论了实现pacels的一些具体问题，比如leader选举数据和消息类型，还有流控等等。
那第三篇呢是pixel made moderately complex.那这篇文章啊比较新是二零一一年才发表的。
文中介绍了很多实现的细节，并且啊提供了很多伪代码，一方面呢可以帮助你理解pixels,那另一方面呢也可以据此啊实现一个pixels.最后第四篇呢是paxel made practical,那这篇文章主要介绍如何采用paxel来实现replication.那除了马克罗普利米的那个开源实限之外呢，到github上去找一下，你还会看到一些其他的项目啊，分别是playing paxels、 implementations、 python and java,还有a go implementation of the paxels algorithm.那zookeeper呢有和paxels非常相似的一些特征，比如领导、选举、填号等等。
但是它本质上不是paxels协议，比是自己发明了zp协议。
那有兴趣的话可以读一下这篇论文，叫做zap high performance broadcast for primarily backup systems.那前面讲的google file system MAFREDS和big table啊并称为古三篇。
那基本上来说呢，整个世界的工程系统啊，因为这三篇文章才开始向分布式系统演化。
而云计算中的很多关键技术也是因为这三篇文章才得以成熟。
后来呢雅虎公司啊也基于这三篇论文啊，开发了一个开源软件叫hadoop.因为python的算法太过于晦涩了，而且在实际的实践上有太多的坑，而且呢不太容易写。
对，所以呢有人搞出来另外一个一致性的算法叫raft.那它的原始论文呢是in search of the understandable consensus algorithm extended version.那翻译成中文就是寻找一种易于理解的raft算法。
那这篇论文的译文啊，在info q上啊叫做raft一致性算法论文译文啊，推荐你读一读。
那raf算法和pixel啊在性能和功能上是一样的，但是它和paxel算法的结构不一样。
那这就使得raf算法更容易理解啊，并且更容易实现。
那么raft是怎么做到的呢？是这样的，raft把这个一致性的算法呢分解成了几个部分。
那一个呢是领导选举，一个是日志复制，那一个呢是安全性啊，还有一个啊是成员变化。
那对于一般人来说呢，raf的协议比pencils学习曲线更低，也更平滑。
那rap协议中呢有一个状态机，每个节点呢会有三个状态，分别是leader、 candidate和follower.那follower呢只响应其他服务器的请求。
那如果没有收到任何信息啊，它就会成为一个candidate啊，并且开始进行选举。
那收到大多数人同意选票的人呢就会成为新的leader.那一旦选举出了一个leader,他呢就会开始服务客户端的请求。
每一个客户端的请求呢，都会包含一个要复制到状态机执行的指令。
那leader呢首先要把这个指令追加到log中啊，形成一个新的entry.然后通过panda entries RPC并行的把这个entry发给其他的服务器。
那如果其他服务器没有发现问题，那复制成功之后呢，会给leader一个表示成功的ACK.那leader受到大多数ACK之后呢，应用这个日志啊，返回客户端执行的结果。
那如果follower崩溃或者丢包leader呢会不断重试pand entries RPC.那这里呢我推荐了几个不错的raf s算法的动画演示，并且啊在文中附上了链接。
那后面呢业内又搞出来了一些工程上的东西啊，比如amazon dyamal DB.那他的论文dynamo amazon higher available key value store的影响力啊也很大。
那这篇论文中呢讲述了amazon的dynamo DB是如何满足系统的高可用、高扩展和高可靠要求的那其中呢还展示了系统架构是如何做到数据分布和数据一致性的那GFS采用的是查表式的数据分布，而dynamo DB呢采用的是计算式的啊，也是一个改进版的，通过虚拟节点减少增加节点带来数据迁移的一致性哈希。
那另外呢这篇论文还讲述了一个NRW模式，用于让用户可以灵活的在CAP系统中选取其中两项。
那这里呢用到了vector clock啊，也就是向量时钟来检测相应的数据冲突。
那最后呢还介绍了使用hand off的机制，对可用性的提升。
那这篇文章中呢有几个关键的概念，一个呢是vector clock,那另一个呢是gossip协议。
那提到向量时钟呢，就需要提一下逻辑时钟。
所谓逻辑时间呢，也就是在分布式系统中呢为了解决消息有序的问题。
由于在不同的记忆上有不同的本地时间，那这些本地时间的同步啊很难搞，会导致消息乱序。
那于是呢派xel算法的发明人兰伯特就搞了一个向降时钟。
每个系统啊都维护一个本地的接数器。
那这个呢就是所谓的逻辑时钟，那每执行一个事件啊，都对这个计数器做加一的操作。
当跨系统的时候呢，在消息体上附着本地计算器。
当接收端收到消息的时候呢，更新自己的计收器啊，也就是调整自己的时钟。
那逻辑时钟呢就可以保证如果事件a先于事件b那么事件a的时钟呢一定小于事件b的时钟，但是反过来则无法保证啊，因为反过来没有因果关系，所以向量史中呢就解释了因果关系。
向量时钟啊维护了一个数据更新的一组版本号。
版本号呢其实就是使用逻辑时钟。
那假如一个数据需要存在三个节点ABC上，那么这个向量维度啊就是三在初始化的时候呢，所有节点对于这个数据的向量版本就是a零、b零c零a一b零、c零。
然后呢向其他节点复制这个版本。
那它在语义上表示为我当前的数据是由a的结果更新的。
而在逻辑上呢，就可以根据分布式系统中的数据更新的顺序，找到相关的因果关系。
那这其中的逻辑关系呢，你可以看一下马萨诸塞大学的课程，distributed operating system中的第十节clock cicrereanization这篇讲义。
关于vector clock,你可以看一下why vector clocks are easy,还有why vector clocks are hard啊，这两篇文章。
那另外呢dynamo DB中啊使用到了gossip协议啊来做数据同步。
那这个协议的原始论文呢叫做efficient recogciation and flow control for antiecrophy protocols.那gossip算法也是cosandra使用的数据复制协议。
那这个协议呢就像八卦和谣言传播一样啊，可以一传十十传百的传播开。
那这个协议看似简单，细节上呢就非常麻烦。
那根据这篇论文呢节点之间啊存在三种通信方式。
那第一种呢是push方式a节点啊，将数据的key value version和对应的版本化推送给b节点。
那b节点呢更新a中比自己新的数据。
那第二种呢是曝房式a只将数据key和version推送给b那b啊把本地比a新的数据key value version推送给AA呢在更新本地。
那第三种呢是push push方式，那与铺呢类似只多了一步a呢再将本地一笔b新的数据推送给DB呢，再更新本地。
如果把两个节点数据同步一次定义为一个周期，那么在一个周期内呢，铺是需要通信一次，铺呢需要两次，铺是铺啊，则需要三次。
从效果上来讲呢，铺是铺肯定是最好。
那理论上呢在一个周期内啊就可以使两个节点完全一致。
那直观感觉上呢也是push铺的收敛速度最快。
那另外呢每个节点上又需要一个协调机制，也就是如何交换数据能达到最快的一致性啊，也就是消除节点的不一致性。
那刚刚所讲的是瀑等等等，是通信方式，而协调呢是在通信方式下的数据交换机制。
那协调所面临的最大的问题啊，就是一方面需要找到一个经济的方式，因为不可能每次啊都把一个节点上的数据啊发送给另外一个节点。
那另一方面呢，还需要考虑相关的容错方式，也就是因为网络问题不可答的时候怎么办？那一般来说呢有两种机制，那一种呢是以固定概率传播的NTI androy机制。
那另一种呢是仅传播新到达数据的rumor mondering机制。
那前者呢有完备的容错性，但是需要更多的网络和CPU资源。
而后者呢则反过来不耗资源，但是在容错上难以保证。
那antiantrophy的机制呢又分为精确协调和整体协调这两种。
那精确协调希望的是在每次通信周期里啊都非常精确的消除双方的不一致性。
那具体表现呢就是互发对方需要更新的数据，因为每个节点都可以读写，所以这就需要每个数据啊都要独立维护自己的版本号。
而整体协调和精确协调不同，整体协调呢不是为每个数据都维护单独的版本号，而是每个节点上的数据啊统一维护一个版本号啊，也就是一个一致的全局版本。
那这样与其他结果交换数据的时候呢，就只需要比较节点版本。
而不是数据个体的版本啊，那这样呢会比较精细一些。
那如果版本不一样，则需要做精确协调。
因为篇幅问题啊，这里就不多说了。
你呢可以看一看原始的论文，还可以去看一看cassandra中的源码，或者呢到gata上搜一下其他人的实现。
那多说一句，cassandra的实现呢是基于整体协调的push pool模式。
那关于gossip的一些图示化的东西呢，你可以打开文中的链接啊，看一下动画gossip、 visualization.那以上呢讲的都是一些基本概念相关的东西。
那下面呢我们来谈一谈数据库方面的一些论文。
那第一篇论文呢讲的是AWS, arura叫做amazon aura design considerations for high output clounitive relation data vises.那aura呢是AWS,像mysql的计算和存储分离之后啊，计算节点scale up存储节点scale out.并且呢把它的redo log独立设计成一个存储服务，把分布式的数据方面的东西啊全部甩给了底层存储系统，从而提高了整体的吞吐量和水平的扩展能力。
那oora呢要写六份拷贝，但是它只需要把一个corome中的日志写成功啊就可以了。
那从文中的这张图啊可以看到它把存储符啊做成了一个跨数据中心的服务，从而提高数据库的容灾，降低性能的影响。
那对于存储服务的设计呢，核心的原理啊就是latency一定要低。
毕竟写六个copy啊，是一件开销很大的事儿。
所以基本上来说呢，orura用的是异步模型，然后拼命的做并行处理，其中用到的也是高c的协议。
我在文中呢给你展示了一张图，从这个图中呢我们可以看到完成前两步啊就可以ACK给调用方。
也就是说呢，只要数据在本地落地了就可以返回成功了。
然后呢，对于六个副本，那这个log会同时发送到六个存储节点。
只需要有大于四个成功的ACK啊，就算写成功了。
在第四步呢，我们可以看到用的是gossip协议。
然后第五步啊产生cathe页便行查询。
第六步呢在s三做snapshot啊，类似于checkpoint.那第二篇比较有代表性的论文呢是google的spanner googles globally distributed database.那spanner呢是google的全球分布式数据库。
那它的扩展性呢达到了令人咋舌的全球级可以扩展到数百万台机器数以百计的数据中心，还有上万亿的行。
那更给力的是，除了夸张的扩展性之外呢，它还能同时通过同步复制和多版本来满足外部的一致性。
那可用性呢也是很好的。
我在文中呢给你放了一张span server的架构图，我们可以看到每个数据中心呢都会有一套closers.那这是第二代的GFS.每个机器呢有一百到一千个tablet,也就是相当于数据库表中的行级。
那物理存储呢就是数据文件，比如一张表呢有两千行，然后有二十个tablet.那么每个tablet分别有一百行数据。
在tablet的上层呢通过pixelas协议进行分布式跨数据中心的一致性数据同步。
那pixel呢会选出一个replicica做leader,那这个leader的寿命啊默认是十秒，十秒之后重选。
那leader呢就相当于复制数据的master.那其他的rapdly card数据呢，都是从他那里复制的，读请求啊，可以走任意的rapuid卡。
但是写请求呢只有缺leader,那这些rapiid卡统称为一个pacforce group,那group之间呢也有数据交互的传输。
那google定义了最小传输复制单元，directory是一些有共同前缀的key记录。
那这些key呢也有相同的raplid卡配置属性。
那文中这里呢同样有一张示意图，方便你理解。
那目前呢基spanner论文的开源实现有两个，那一个呢是google自己的人出来做的，coco o是DB.那另一个呢是国人做的太DB.正如我在之前的分布式系统的本质，文章里所说到的，分布式服务的调度啊，需要一个分布式的存储系统来支持服务的数据调度。
而我们可以看到各大公司都在分布式的数据库上做各种各样的创新。
啊，他们呢都在使用底层的分布式文件系统来做数据引擎，把存储啊和计算分离开来。
然后呢使用分布式一致性的数据同步协议的算法来在上层啊提供高可用、高扩展的支持。
啊，这一点来看啊，可以预见到过去的分库分表，并通过一个数据访问的代理服务的玩法，应该在不久后就会过时啊，就会成为历史。
那真正的现代化的分布式数据存储啊，就是oura和spanner这样的方式。
那通过上面的这些论文呢，还有相关的工程实践和开源项目。
相信啊可以让你在细节方面对分布式中最难的数据调度方面有更多的认识。
那文末呢有分布式系统架构本质系列文章的目录啊，方便你查找自己关注的内容。
