如何利用分布式算法理解分布式存储

阅读前提：已经明白 paxos 和 raft 的工作原理，下文不会仔细介绍其工作原理。

本文主要讲述通过理解算法设计能更好地理解分布式存储系统。

分布式算法是指 Paxos 与 Raft，本文主要也围绕这两种展开讨论。

分布式存储是指 Mysql 多/单主从模式、Redis 主从/集群、kafka 中的分布式存储，还有一些分布式数据库如 oceanbase、spanner 等。

1、算法历史

paxos 论文发表于 1990 年，因为作者文风怪异，没多少人看懂作者想表达的问题。过了好几年，偶尔有人看懂了，作者就又在 1998 年重新发表了。直到 2006 年谷歌发表相关论文后，才慢慢进入大众视野。而 Raft 协议在 2013 年发表，paxos 和 raft 中间还出现了 zab 协议（zookeeper 中的分布式协议）。各自也衍生了一些其他版本。有意思的是，Raft 翻译过来就是木筏和救生艇的意思，而 Paxos 是个岛屿。Paxos 被诟病的就是晦涩难懂，大概的意思就是 use raft to save people from paxos.

2、算法要点

paxos，多主分布式数据同步算法。主要解决整个分布式系统中消息的顺序和同步问题。涉及的环节有提案、决议、消息同步等。

基本过程：参与的节点在提出新方案之前，先提出提案意向，获得超半数接受者同意后可以提出新提案，否则需要先完成已存在的提案。提出新提案后让其他节点投票，提案方在获得半数以上投票后，提案内容就被整个系统认可，然后继续同步给没有该数据的节点。

关键点：1、先提意向，同意后再提新方案 2、先确定已有提案

缺点：1、多主导致算法复杂和低效（意向和方案需要两次半数投票），以及 2、可能存在提案阶段的死循环问题（同时有多个节点先后提出意向，后者意向覆盖了前者意向，前者提案被拒绝后又提出新意向，然后后者提案被拒绝又提出新意向，并一直循环）。

参考链接：https://icyfenix.cn/distribution/consensus/paxos.html

multi-paxos：相比 paxos 增加一个 leader 节点选举环节，此后所有提案都经由 leader 节点转发并提出。

raft：属于 multi-paxos 的一种，有具体的算法和细节实现，比如 leader 选举的方案更加具体，消息（日志）的数据结构包含 leader 的任期 term。term 用于换主后数据恢复和同步。

优点：单主，效率较高（选主后，可以少一个提意向的投票阶段，只有 leader 能提方案），算法具体。

缺点：数据恢复阶段可能会丢失上任 leader 节点的最后一条消息。（这个可以由具体算法决定，比如 kafka 不丢已有的前任消息）

要点：1、需要理解 paxos 的基本原理 2、需要理解 raft 中 term 的作用。（跟 zookeeper 和 kafka 的 epoch 概念类似）3、理解各自算法会产生的问题和处理。

我主要通过《深入理解分布式算法》以及《凤凰架构》（电子版 https://icyfenix.cn）这两本书配合搜索引擎进行学习和理解。通过多个作者的文章结合去理解会容易一些。

3、消息格式

除了这些外，还要介绍一个概念，状态同步方式，即同步的消息格式 state machine system 和 primary backup system。

前者以命令作为消息传递，只要执行相同的命令，各节点就能达到相同的状态。paxos、raft 用的前者

后者以命令产生的数据结果作为消息传递，好处是不用每个节点都执行命令。zookeeper 用后者

可以阅读这篇文章进一步理解： https://www.cnblogs.com/lizhaolong/p/16437198.html

以为例 Mysql，binlog 在单主模式下提供了 statement-base 和 row-base 两种格式进行数据同步，分别对应 state machine system 和 primary backup system。在单主情况下，可以自由选择，各有优劣（参考链接 https://dev.mysql.com/doc/refman/8.0/en/replication-sbr-rbr.html）并且 mysql 提供了混合模式 mixed。

而在多主情况下，只能使用 state machine system 的方式。这也是为什么 Msyql 在双主模式下用的是 GTID。

4、特征提取

从 2 与 3 中提取出有用的特征

1、架构方式：多主，单主

2、commit 规则：如半数确认

3、选主规则：leader 选举，如以最长日志作为选择标准

4、数据恢复规则：结合任期和消息

5、同步的消息格式：state machine system、primary backup

6、已确认和未确认消息：节点数据不一样，主节点数据会领先，半数投票者也会数据领先其他节点

7、其他

5、如何结合算法理解分布式存储系统

首先基本所有的分布式存储系统都离不开 Paxos 和 Raft，如果搞明白这两种基础的算法理论，那么对入门所有的分布式存储系统都有帮助。然后就是利用每个特征去理解具体的系统。

1、架构方式：这个最重要的基础，如果是多主，那么一般都是用 Paxos 去实现，同步的消息格式也只能用 state machine system。用这个前提就可以大概了解系统的架构，比如 redis 集群与 kafka 集群模式，虽然存在多个“主”，但是每个分区/组只有一个主，所以并不是多主。

2、commit 规则：比如 mysql、redis、kafka 中都可以在 leader/master 利用异步复制，先返回成功给客户端，再进行各节点数据同步，而不同的同步方式，对数据恢复时的影响可以参考 raft 算法的细节。还有半复制和全复制等机制等。

3、选主：如果是单主，肯定是需要选主和对应的规则。

4、数据恢复：kafka 引入 epoch 概念，跟 raft 的 term 是一个意思。

5、同步格式，比如 mysql、redis 就会提供这些选项。

很难把所有情况都类比出来（比如节点数据的刷盘策略也是存储系统的设计关键点。而刷盘策略跟 commit 规则类似，也会影响数据恢复）。但是通过以上几点可以看出，分布式存储系统的难点/关键点/差异点都是比较清晰的，通过理解关键点就可以更好地理解各个存储系统并根据业务需要进行选型。

PS：这个主题写下来超过了我的预想，很难在短的篇幅里面把事情说清楚，又很难通过文字去表达我在这学习和深究过程中知识碰撞的喜悦。其实我是想表达一种理论和实际应用相结合的一种奇妙过程。算了。