浅谈分布式算法

前言

近期在考虑实现一个基于diff模式的笔记存储算法，具体是这样的：客户端触发存储逻辑时，首先会将文本T与前一次存储的文本S进行diff比较，生成一个patch，这个patch应用在文本S上，就能生成文本T，也因此，笔记的存储不再是单纯的将文本存在数据库中，而是一个类似于git的带有版本号的log，通过历史log生成最终的文本。

这个好处是不用担心笔记数据丢失，因为不存在删除和覆盖写入操作。

说了这么多，还没有说到分布式，这篇文章简单的介绍一下分布式，是因为我上面说到的存储最终希望能够采用分布式的方式去实现，笔记存储的数据结构其实就是一个带版本号的log，如果数据量比较大，最理想的方式是横向扩展服务器结构，也就是通过增加服务器来进行扩容，而不需要写任何代码。

限于精力有限，只能带大家了解一下分布式的基本算法，不过相信这些对于以后在思考服务器结构时会起到比较大的影响。

本篇是看了MIT6.824分布式课程前几章后的一点感想，欢迎拍砖~

分布式

说起分布式，很多人并不陌生，只要是我们常用的app，因为用户量巨大，分布式是用户数据存储和计算的一个重要解决方案。有人可能觉得分布式会很难，毕竟处理这样大量的数据需要非常高的性能和稳定性，而且对于宕机这种在一般服务器上极小概率发生的事情，在分布式整体集群中是家常便饭的必现问题。另外一个问题是多个服务器节点协同工作，需要极好的协调同步的能力。可是等会大家就知道，分布式算法的基础是很简单的，即使对于raft这种比较好的一致性算法，可能只需要一个下午时间就能理解整个流程，相较于算法竞赛中的网络流之类的较为麻烦的算法，分布式的这些算法是比较简单的。

分布式算法

分布式服务器的设计很多时候容易被程序员混淆，在我的理解上面，分布式服务器是能够横向扩展的，对于只是将功能分到不同模块的多进程做法，并不是分布式的做法。但是在具体架构的时候又需要将功能划分为多个模块，每个模块可能是分布式结构，这个要具体问题具体分析。分布式通常分为分布式计算和分布式存储两大块，这两块的算法有比较大的差异，可以说是相互独立的。

分布式计算

分布式计算的目的是为了能够将一个涉及到大量数据的任务分配给不同的节点，每个节点处理一小部分数据，最终汇总输出结果。

我们可以通过MIT6.824课程的第一章来了解Google的MapReduce算法，这个算法便是一个典型的具有高实践意义的算法，因为Google最早就是通过这个算法来处理巨量数据的。大数据中Hadoop便是MapReduce与HDFS的合体，当然，经过十几年的发展，现在会有一些更好的分布式计算比如Spark，但是学习MapReduce的原理可以作为我们了解分布式的一个小小的敲门石。

MapReduce算法比较简单，只有2个函数，map和reduce，map函数负责处理数据，将处理的结果放在一个kv也就是map容器中（最终可能是输出到文件中），处理完成后，再由reduce函数汇总（规约）这个map中的数据，完成最终的输出。

这个过程因为比较简单，因此实现的时候不容易出现问题，启动一个master管理进程负责分配任务，启动N个worker进程请求任务，worker进程完成map和reduce，所有节点协作进行任务处理。

具体可以看课程视频和做lab练习，一节课80分钟，教授会讲解很多细节问题。

MapReduce这么简单，却支撑了整个互联网的大数据计算，大繁至简，说的就是这个道理吧。

分布式存储

上面提到Hadoop，Hadoop将MapReduce和HDFS结合起来，处理计算和存储，这里面HDFS是分布式存储，分布式存储可能比分布式计算要麻烦很多，因为要和很多现实问题关联起来，分布式计算就是CPU计算，即使机器出问题了受影响的节点需要完成的任务重新发给另外一个机器即可轻松解决，然而分布式存储就不同了，存储需要考虑数据同步、磁盘保存等一系列的操作系统底层问题。

分布式存储又可以分为分布式文件存储和分布式数据存储，数据存储又要分为结构话数据和非结构化如kv数据存储，其实不用考虑怎么分或者受限于已有的数据机构。用的比较多的大概就是文件、数据库、kv数据库几个类型，因为数据的格式多种多样，很多都是自定义的有利于优化的数据结构。HDFS是文件类型的分布式，我上面提到的diff的log数据结构可以是我自定义的，也可以基于kv这种已有的数据结构实现。mysql这种结构也可以用kv数据结构实现，所以大概了解一下分布式存储存的数据格式就可以。

分布式文件存储可以看Google的gfs论文，Google算是分布式的带头大哥，感觉整个分布式都是他家搞出来的，而且每次都以详细的论文方式给别人使用，现在看看整个互联网的开源系统，有一种被Google吞了的感觉，除了Linux不是Google的，安卓系统、chrome浏览器还有最近比较火的flutter，这些系统技术难度极高，但是又是整个互联网生态最重要的基础部分，所以Google想倒闭都很困难，就像一棵大树，Google是把树根都给占了。

大部分人学编程，跟着google搞就行，因为它已经给你写好了目前已知的最好的解决方案。

吐槽完了继续来看分布式kv存储，分布式kv存储最基础的部分是要解决一个一致性问题，什么是分布式一致性问题？其实可以简单理解为内部节点的数据要保持一致，不能说a节点的字段x的值是1，另外一个节点b的字段x的值是2。

课程中重点是讨论raft一致性算法，这个算法相对于大名鼎鼎的Paxos算法更加简单和清晰，因为Paxos算法实在是太晦涩，大家貌似都能看懂这个算法，但是在实现的时候写着写着就不一样了，结果每个人都写出了不一样的一致性算法，所以你写好了可能也会很难知道自己写的对不对，对于程序员来说这实在是比较恐怖的一个事情，因为不确定就得悬着心运行分布式系统。

raft算法就不会出现这种问题，运行效率也可以，和其他的一致性算法性能差不多，所以课程里面主要是讲解这个算法。

raft算法理解起来还是需要花点时间的，因为实现起来可能需要一两千行代码，但是每段逻辑比较清晰，把每个函数理解清楚就可以了。

raft算法将服务器节点分为3类：leader、候选者、follower（追随者）。最开始的时候，所有节点都是follower，follower发现没有leader，于是自发成为候选者，大家都很积极，纷纷向其他节点请求选票。节点收到选票后，如果发现自己有一半人的选票，就自立为leader，开始收发消息和同步数据。注意这里是一半的节点，个人感觉这是一个很精巧的想法，因为不需要发消息同步别的节点我已经成为leader了，也不用担心别人会成为leader。其他节点成不了leader，不久后就收到leader的心跳，整个局势就固定下来了。

raft选举算法解决了去中心问题，leader宕机后重新选举，一切都很好恢复。另外一个问题是节点数据同步的问题，节点leader收到客户端发来的数据后，就将这个数据转发给其他节点，如果有一半以上的节点确认收到数据，那么leader才会commit这个数据，这个机制是一致性的保证，不过这个涉及到很多细节问题，特别是leader宕机数据未commit等极端情况的处理。

raft算法主要就是选举和数据分发，看起来是不是也挺简单，但是如果要写一个正确的raft算法还是要花时间去实现的。

总结

如果没有MapReduce和raft这些算法，自己去实现分布式的计算和存储，可能不怎么现实，看起来简单的东西，可能是数学行业几十年的沉淀与研究产生的结果，而且分布式算法并没有出现百花齐放的状况，也可以说明研究一种算法就已经很困难，就如Paxos的设计者，他是将分布式问题抽象为数学问题才能够提出这套理论，所有的这些，都是因为想法要被证明为正确是极为困难的。在分布式领域，Paxos的设计者还设计了一个PLA+语言，专门用于这个领域的设计工作。