分布式系统一致性与共识

发表于2019-08-28更新于2021-01-22

目录

  1. 分布式系统可以提供的若干保证和抽象机制
    1.1 共识算法的意义
  2. 如何在分布式系统中做到原子性
    2.1 可线性化
    2.2 顺序化 
     2.2.1 [顺序、因果、全局序号的关系](#2.2.1)  
 2.2.2 [全局关系的广播](#2.2.2)
  3. 分布式系统的能力边界
    3.1 分布式事务
    3.2 容错的共识
  4. ShareNote

分布式系统可以提供的若干保证和抽象机制

共识(分布式一致性)算法的意义

对于大多数的多副本的数据库（N>=2)的情况下，它至少达到了最终的一致性。但是因为只是最终，但是到达最终的状态的时间是未知的。
最终一致性的多副本数据状态（如Aurora、Riak、Cassandra）的不一致对于应用开发者是比较棘手，因为很多底层保证一致的东西需要挪动到应用层上面去添加规则来继续保证。并且导致测试和验证都会变得异常的困难

基于上面的问题，我们可能需要找到一个更加强一致性的模型来进行构建，可以把应用层可能遇到的数据库不一致的问题封装起来。虽然可能会付出其他的代价（如性能下降、容错性差）

与事务隔离的级别的差别

共识与事务隔离都有类似与副本的概念（事务隔离是使用乐观锁（MVCC） 共识是使用多副本）
共识：更加强调是针对延时和故障协调副本之间的关系。
事务隔离：处理并发事务的各种临界的条件

如何在分布式系统中做到原子性

可线性化

（此部分主要是DDIA第9章节的内容）
定义： 让一个分布式的系统看起来像一个单副本的系统，并且所有的操作都是原子的。

一个非线性化的例子

对于上面这个图的简要描述：
因为使用了多节点非强一致性的数据库，当Referee修改数据库的情况下，因为集群内同步的时间不一致，导致可能Alice先查的的Slave-1 已经修改了，但是Bob查询的Slave-2的库上面还没有修改，导致Alice和Bob获取到的结果不一致。这种场景对于一些一致性需求比较强的情况下不能接受。

线性化的例子的直觉表达

线性化的简洁但是事实上的描述： 让分布式系统具有寄存器的语义。
对于这个部分，我们详细去探讨一下
一般我们的对于读写请求并发（在客户端的角度）是这样的:
定义一个前提， 下图中的一个框是指客户端从发出请求到接收到返回值的整个过程
单个框可以理解为 客户端发出请求-> 服务器端接受并且处理请求-> 服务器端返回结果-> 客户端在应用级别收到返回
下面可能出现框比较长的情况是在上一篇文章（分布式系统简介以及其问题）的假设所提及的情况，此处不再复述。

分布式系统中的寄存器： 线性化数据库中的相同的主键。（此处为X)

此处对于寄存器有两类的操作：

  1. read(x) 读取主键为X的值，数据库返回值v
  2. write(x,v) 客户端把X的值更新为V，数据库返回值为r(成功或者失败)

对于上图在read和write重合的过程中，read的结果可能有2种情况：

  1. read在write完成之前结束(返回0)
  2. read在write完成之后结束 (返回1)

但是这个描述的粒度还是比较大，为了把系统线性化的更好的描述，我们添加下面的约束

约束为，在写操作的过程中，肯定有某一个时间点，存储上面的x的值会出现冲0到1的跳变。
对于上图， 客户端A在某个节点能够读到X的值为1，那么因为客户端B的读操作是晚于客户端A读的发生的，因此
客户端B获取到的值也必然是1（如果不是1，则不是可线性化的系统）。

但是上面的讨论颗粒还是太大了，此处我们加入进去存储，以及存储接收到的操作来整体观察线性一致。
我们此处引入一个概念

1
CAS(compare and swap):一个原子的比较设置操作。编程语言中一般都要实现此概念，此处不详细叙述

并且添加一个假设：即使客户端可能还没有收到成功的响应，但是分布式的存储已经全部同步成新的值。
上图中每个操作都有竖线，表示可能的执行的时间点，把这些点连接起来，最终结果必须是一个有效的寄存器读写顺序。
可线性化的要求： 按时间箭头向前移动，不能向后移动。
可以看到上图中，最后客户端A的操作在c的Cas操作完成后，x的值已经变成了4，但是如果发现读的值为2的话，按时间线的理解就是错误了。因为根据可线性化的要求，cas操作已经执行了，并且时间只能向前走的情况下，客户端A的读操作必然是需要返回4的。

1
2
3
4
5
//可线性化和可串行化的对比
#### 可线性化
对寄存器（单个对象）的最新值保证。他不要求将操作组合到事务中，可能会出现写倾斜的问题（如果不采取手段去解决的问题）
#### 可串行化
是事务的隔离属性。每个事务可以读写多个对象，用于确保事务执行的结果与串行执行相同。即使穿行执行的顺序和实际执行的顺序并不一定相同（可能实际上的执行是并行执行事务，但是对外暴露的结果是一致的就可以）

需要用到线性化的使用场景

  1. 加锁与主节点选举
    对于主从复制系统的选主问题，可以通过基于Etcd或者ZooKeeper来进行抢锁操作控制选主
  2. 约束与唯一性保证
    应用中对同一个资源（如用户名）的唯一性的约束。（可以延展到数据表的主键约束）
  3. 多信息源的时间依赖
    对于一些异步任务系统虽然采用了最终一致性，但是可能也是会因为实现产生数据的依赖问题。

如何实现一个线性化系统

对比多种可能使用的方案来确定

在考虑容错的基础上，必须考虑复制的机制。我们可以对比多种复制方案来看看那种可以实现线性化

  1. 主从复制。（部分线性化）
    因为所有写入操作都是从主节点继续，并且把操作同步到从节点上面。但是问题可能出现在实现的问题上：
    1. 实时同步可能会出现问题
    2. 可能会因为快照隔离设计出现问题
  2. 共识算法（可线性化）
    类似于主从复制，但是通过一些手段来防止脑裂和过期的副本
  3. 多主复制（不可线性化）
    当允许并发写入的时候，如果进行异步复制的话，可能会出现数据的冲突。
  4. 无主复制（可能不可线性化）
    类似于Dynamo的机制，即使使用了Quroum机制，但是如果选取的Quroum不一定是满足的情况下，可能会出现非线性化的处理

此处提出一个问题，是否只要有Quroum机制（就必定可以支持线性一致呢？）
答： 不一定。用下面的例子进行解释

对于上图中，即使是使用了Quroum，但是没有共识算法的支持，还是可能会出现类似于之前Alice和Bob遇到的情况的问题。但是这个选取的直接是一个Quroum，但是是因为缺少共识，并且网络出现问题才会导致这样的情况出现。

线性化的代价

线性化出现代价的最主要的原因还是因为网络的不确定性。

我们先用主从的架构来讨论这个问题，当网络发生分区的情况，主从不能够继续同步操作，可能会导致从库不可用。
但是这个是我们需要实现线性化所带来的不可用

先引入一个概念：CAP理论

1
CAP : 在同一个时间内，当网络出现分区的情况下，不可能获得兼容可用性和一致性。

CAP理论的推理：不要求线性化的应用更能够容忍网络分区。

但是为了线性化，我们可能要牺牲性能和延迟。
那么我们是否有方法可以做到线性化但是减少性能的牺牲呢？

顺序保证

我们刚刚在讨论线性化的时候使用到了寄存器的概念，那么顺序、可线性化、共识之间是否存在的某种关系呢？

顺序、因果、全局序号的关系

顺序和因果的关系

因果关系对所发生的事件添加了排序， 一件事情会导致另外一件事情，这些的因果关系依赖链条定义了系统中的因果顺序。如果符合因果关系所规定的顺序，我们称之为因果一致性。（快照隔离，在从数据库中读数据的情况下，查询到的诗句，也可以查到这个数据之前发生了什么的操作事件）

因果顺序并非全序

全序关系是可以支持两个不同的实体直接进行比较（如自然数集5和13的比较）
但是部分集合的对比不一定符合全序，集合{a,b} 与 集合{b,c}是无法进行对比的

因此，提炼到可线性化和因果关系中
可线性化是存在全序的操作关系，因为暴露对外的行为是与单副本无异，并且每个操作都是原子的。可以分出先后
因果是偏序的操作关系，对于并发的两个操作无法比较的情况下，就会发生冲突，对于可以比较的情况下，与线性无异。
那么可以这样说，可线性化一定意味着因果关系，因为可线性化是全序的操作。
但是可以这样理解，线性化并非是保证因果关系的唯一的途径。我们可以有其他手段去满足因果一致性而避免线性化所带来的问题。
因果一致性是被认为是不会由于网络延迟而显著影响性能，并且可以对网络故障容错提供容错的最强一致性的模型。
因为实际上很多的应用所需要的是因果一致性来保证应用的正确性。

捕获因果依赖关系

如果只要解决并发操作的先后依赖关系。这里其实只需要由偏序的关系即可。
我们常见的数据库的版本技术就是一个解决这个问题的方案之一
为了确定数据库的因果关系，数据库需要知道应用读取的是哪个版本的数据。

序列号排序

那么，这样的情况下，我们是否需要显式的跟踪所有的因果关系呢？
为了性能的考虑，我们可以通过序列号和时间戳（尽量不使用物理时钟）来进行对事件排序，这样在保证性能的同时，也能够保证所有操作在全局的关系。但是要保证每个序列号必须唯一，并且可以比较。
我们可以按照与因果关系一致的顺序来创建序列号： 如果操作A发生B之前，那么A一定在全序顺序中出现在B之前
这样的全局排序可以捕获所有的因果信息，并且加强了比因果关系更为严格的顺序性

那么对于不存在唯一的主节点（多主或者无主），那么我们能怎样生成上面所提及的序列号呢？
有实践中可以采用以下方法：
1. 每个节点单独生成自己的一组序列号。假设有两个节点，一个生成奇数，一个生成偶数
2. 把Timestamp添加到操作中（之前生产中有用此种方式）
3. 预先分配序列号的区间范围。（A节点分配1-1000，B节点分配1001-2000）

但是这三种实际上生成的唯一的，近似增加的序列号。但是实际上序列号和因果一致不是完全因果一致的。
为什么不是因果一致呢?
对于情况1，每个节点处理的速率是由不一致的，只要两个节点处于处理速率不一致的情况下，分配的ID必然和实际的顺序关系无法对应
对于情况2， 墙上时钟发生偏移的情况
对于情况3， 如果sharding的路由发生了变化之后，那么之前1-1000的因果关系就不存在了。

那么我们是否没有办法可以在非强主的情况可以获取一个序列号与因果一致可以对应上的吗？

我们还有一个方法！！！此处大神来了Leslie Lamport的Lamport TimeStamp可以解决这个问题

LamportTimeStamp

每个节点一开始的时候都会有一个唯一的标识符（每次初始为0）， 然后每个节点都有一个计数器来记录各自处理的请求总数。到此与之前的时间戳的并无差别，但是Lamport这里处理的亮点出来了，每个节点和每个客户端都会跟踪迄今为止最大的计数器值，并且在每个请求中附带该最大计数器值。当节点收到某个请求的时候，如果发现请求内的最大计数器值大于自身的计数器值，会更新自己的计数器值（Raft中是通过投票和心跳的RPC来同步这个计数器的值，在Raft的概念里面叫做Term，后面讲解Raft的时候会进一步解析，此处只是一个插叙）。

LamportTimeStamp好像是解决了分布式系统顺序号和因果一致的关系，但是是已经足够解决分布式系统中常见的问题了吗？
问题如下：
一个系统的用户名只能由唯一的用户持有，两个用户并发地向系统同时进行注册，我们必须要保证一个成功，一个失败
虽然看上去我们是可以把两个请求通过编号把两个并发的请求变成了一个有顺序的问题，但是实际上要保证上面的是唯一的有两个前提：
1. 节点收到用户请求的时候需要马上判断请求时成功还是失败
2. 必须要收集系统的所有创建用户的请求，比较序号
但是这个显然是不可能的，只要网络出现问题了，我们就无法做到上面的两个问题。

那么我们如果要知道全局关系是否确定，就需要提到后面的一个概念，全序关系广播

全局关系的广播

继续先从一个主从复制的系统开始说起，主节点接受写请求并且变成顺序的操作。
但是在分布式系统领域，如何扩展系统的吞吐量使之突破单一主节点限制以及处理主节点失效时的故障切换。这类的问题被称为全序关系广播或者原子广播。
全序关系广播： 通常指节点之间交换信息的某种协议。有两个特性
1. 可靠发送（没有消息丢失，如果消息发送到某一个节点，它一定要发送到其他的节点）
2. 严格有序（消息总是以相同的顺序发送到每个节点）

使用全序关系广播

Zookeeper和Etcd的共识服务就实现了全序关系广播。（那么全序关系广播和共识之间的关系？）

全序关系广播就是数据库所需要，每条消息表达数据库的写请求，而且每个副本段相同的顺序处理这些写请求，那么所有副本可以保持一致。这个也被称为状态机复制。

全局关系广播的另一个要点，顺序在发送消息时已经是确定的，如果消息发送成功，节点不允许追溯将某条消息插到先前的位置上。只能进行追加，这样全序关系广播比时间戳的排序要求更强
应用场景：
1.我们可以使用全序关系广播来实现可串行化的事务。（每个消息表示为一个确定性质的事务，并且作为存储过程来执行）
2.提供Fencing令牌锁的服务（把取锁的请求变成一个消息追加到日志中，序列号直接可以变成令牌返回）

全序关系广播来实现线性化存储

全序关系广播是基于异步模型，保证消息以固定顺序的可靠发送，但是不保证消息何时发送成功，但是可线性化更多地强调读取时能看到最新的写入值。
我们可以通过追加的日志的方式使得使用全序关系广播在写入的方式上与可线性化做到一致
1. 在接受请求的本地节点中追加一条消息，指明写入的信息
2. 读取日志，广播到其他节点，等待回应
3. 如果回复中有冲突，则失败，返回错误给客户端；否则返回成功给客户端
通过日志追加可以把并发有效的转换为多条的日志来保证因果顺序关系。但是读取却还没做到这个语义
为了读取可以与可线性化一致，有以下方法可以解决这个问题：
1. 把读的请求也变成日志的方式追加到排序广播，通过变成日志的情况下可以确定了顺序的问题。（ETCD采用的是这种方式）
2. 如果可以以可线性化的方式获取最新日志的消息位置，则查询位置，直到该位置之前的所有条目读发送给你，再进行读取（ZooKeeper使用的方式）
3. 可以从同步更新的副本中进行读取，保证每次读的是最新的值。

所以最终可线性化的原子地对寄存器做CAS的操作与全序关系广播其实等价于共识的问题。

分布式共识的能力边界

共识： 使得分布式系统中就某件事情达成一致
共识的使用场景：
1. 主节点选举（防止脑裂问题）
2. 原子事务的提交（跨节点或分区的数据库，事务在部分节点成功，部分节点失败，需要进行回滚）
我们先从事务的原子性开始，讨论2PC（2阶段提交），之后再会谈及其他更好的共识算法的实现（ZooKeeper， Raft）

分布式事务

事务原子性的目的：
一个多笔写操作的事务在执行过程中出现意外情况，为上层应用提供一个简单的语义，全部成功或者全部失败
单机原子提交：
数据库把事务写入持久化部分，然后把提交记录追加写入到磁盘的日志文件中。所以在单节点上面，事务提交非常依赖与数据持久写入磁盘的顺序关系
1. 先写入数据，再提交记录
2. 事务提交或者中止的关键点在于磁盘完成日志的时候，在完成写之前崩溃的情况下，事务需要中止；如果日志在完成写入后发生崩溃，事务被安全提交

但是对于分布式多节点，处理方法有所差别，原因可能是以下这几个问题引起的
1. 某些节点发现不满足要求中止了事务，但是部分节点通过并且提交
2. 部分请求可能在网络不稳定的情况下丢失，超时而中止；但是其他请求可能成功提交
3. 节点可能在写入日志前崩溃，而且在恢复后回滚（原来数据没有成功，回滚可能会出现问题）
如果一部分节点提交了事务，但是部分节点放弃了事务，会导致集群中节点信息的不一致，而且事务一旦被提交，即使事后发现其他节点中止，也无法撤销本节点的事务

事务提交后不能撤销的原因：
一旦数据提交，就会被其他事务可见，然后客户端（应用层）就会做出相应的反应，这个是构成读-提交隔离的基础。但是如果允许撤销的话，那么所有之后的读-提交级别的任务，然后会产生多级的级联式追溯和撤销。导致系统压力巨大甚至崩溃。并且不能保证数据是否能够准确落盘。

因为不允许撤销事务，因为如果一个错误的事务被提交了，必然需要一个新的事务来抵消它的影响，但是这个需要应用层来进行处理，就不符合我们需要给应用层提供的原子性。

2PC

两阶段提交（2PC）是一种在多个节点上实现事务原子提交的算法。要么全部提交，要么全部不提交。

2PC的流程（为什么可以解决上面单阶段提交的问题）
  1. 应用启动分布式事务的时候，先去像协调者获取事务ID（全局唯一）
  2. 应用程序在每个参与的节点启动单节点事务，并且把事务ID附加到到参与者的事务上。如果这个阶段发生异常，可以协调者和其他参与者可以安全中止
  3. 应用程序准备提交事务时，协调者回向参与者发送携带事务ID准备请求，只要有一个发现失败的情况下，通知全部放弃事务
  4. 参与者收到请求后，确保自己时候可以提交事务（包括硬件故障和软件故障的确认），然后检查是否有冲突或者违规。一旦返回是，节点会承诺提交事务。（保证了参与者不会撤销事务）
  5. 当协调者收到所有的参与者返回后，要决定是否提交事务，并且把此决定写入到硬盘的事务日志（WAL）中，防止掉电后可能出现的异常
  6. 协调者向参与者发送提交/放弃 事物的请求，只要是提交，每个参与者会重试到成功为止(包括了进程崩溃的重试、节点重启等情况)

所以他是在保证了上面的一个重要前提，只要提交了就不能撤回。
在参与者在返回给协调者的时候保证了单向性
并且协调者确定提交了之后也是保证了不可逆，因此保证了2pc可以不会出现那些异常的情况。

但是2PC的单点在于协调者的问题（虽然可以采用共识层来写协调者保证高可用）但是整个过程中的热点也会出现在协调者上面。

实际生产上面的分布式事务

异构分布式事务

虽然分布式事务因为这样可能会有阻塞而导致性能和吞吐量的下降，但是是否没有折中的方法来使用类似的语义呢？
目前更多的是采用了异构的方法（如数据库+MQ）的执行异构的分布式事务

对于异构形式的分布式事务，当且仅当数据库中处理消息的事务成功提交，消息队列才会标记该消息处理完毕。
但只要其中一个出现失败的情况，两个部分都必须进行中止的操作。

保证消息可以有效处理有且仅有一次

目前有XA的异构的分布式事务的标准。

支持容错的共识

共识问题的形式化描述： 一个或者多个节点可以提议某些值，由共识算法来决定最终的值。

基于上面的描述共识算法必须满足以下的性质：
1. 协商一致性（所有节点都接受相同的决议）
2. 诚实性（所有节点不能反悔，对某项提议不能有两次决定）
3. 合法性（决定了值V, 那么V肯定是由某个节点提议的）
4. 可终止性（如果节点不崩溃最终一定可以达成协议）

协商一致性和诚实的属性定义了共识算法的核心思想：决定一致的结果，并且一旦决定就不能改变。
合法性是为了排除一些无意义的方案，
可终止性是容错的体现，避免了整个系统的空转
根据之前提及的： 可终止性是活性， 其他三个是安全方面的属性。

因为共识算法的目的是解决在大多数节点正常的情况下正确运行才能确保终止性。

共识算法和全序广播的关系

共识算法(如Raft、Paxos、Zab)等都不是直接采用上述的形式化模型。而是决定了一系列的值，然后采用全序关系广播算法来进行实现。

全序关系广播要点： 消息按相同的顺序发送到所有的节点，有且只有一次。
这样的方式相当于多轮的共识过程。在每一轮，节点会提出之后需要发出的信息，然后决定下一个顺序。

对于上面的提到的四个性质：

  1. 由于协商的一致性，所有节点决定以相同的顺序发送相同的消息。
  2. 由于诚实性，消息不会重复
  3. 由于合法性， 消息不会被破坏，也不是凭空捏造
  4. 由于可终止性，消息不会丢失

Epoch 和 Quorum

对于共识算法来说，都采用了一个弱化的保证，定义了一个世代编号（Epoch）来确保每个世代里面，主节点是唯一的。
如果发现当前主节点失效的情况，节点开始选举新一轮的主节点，Epoch号递增。在主节点做出任何决定的时候，都需要检查是否由比它更高的Epoch号码。
主节点必须从Quorum中收集投票，并且把提议传送到各个节点中，等待节点的返回，当只要没有更高的Epoch主节点
时，才会对当前的提议进行投票。

此处其实是由两个操作组成：1. 选举主节点； 2.对主节点的提议进行投票

注意的一点： 参与两轮的Quorum必须要由重合，这样才能保证主节点没有更高的Epoch，保证正确性。

与2PC的差别， 2PC是需要协调者向每个参与者做出“是”的返回才能进行，而共识算法可以通过直接以集群的多数来确定是否通过决议

共识算法的局限性

共识算法虽然为分布式系统带来了好处，为一切不确定的系统带来了安全属性和容错性。并且可以通过全序关系广播以容错的方式实现线性化的原子操作。

但是共识也是有代价的：

  1. 节点投票是一个同步复制过程，性能可能需要妥协（但是可以通过减少选举的频率来减少整个开销）
  2. 共识体系需要严格的多数节点才能执行，换句话来说，最少需要3个节点才能运行
  3. 多数的共识算法假定了一组固定的参与投票的节点集（主要是为了理解的方便）
  4. 共识算法需要依靠超时来对节点失败进行检测，但是可能会出现因为网络原因的误判导致经常切主，数据搬移多，对外的性能降低。
  5. 网络的影响较大，如果出现频繁切主的情况，可能会有长时间出现无法正常对外进行服务

基于共识算法的成员与协调服务

对于像ZooKeeper、Etcd这些分布式键值对的服务，暴露的API与数据库是十分类似的，但是为什么我们需要在共识层上面去构建这些服务呢？

作用

这些分布式键值对数据库主要是针对保存少量，可完全载入内存的数据。采用容错的全序广播算法在所有节点上复制数据使得可以实现高可用的目标。

  1. 线性化的原子操作
    多个节点同时去获取锁，只有一个会成功，共识协议会保证操作满足原子性和线性化，即使节点出现部分失败的情况
  2. 操作全序
    之前分布式系统问题的文章有提及过Fencing令牌的问题，
  3. 故障检测
    客户端会与这些服务保持一个长连接，如果长时间重连失败的情况下，会把该客户端拥有的资源全部释放
  4. 更改通知
    客户端可以通过读取服务来发现其他的客户端的行为

对外的功能

  1. 节点任务分配
    计算作业调度系统(Yarn)，分区资源调度（如Multi-Raft中的ShardMaster)
  2. 服务发现
    解决云环境中服务启停而注册到的服务变更(consul提供的服务)
  3. 成员服务
    节点是否可用并且获取主节点

如何验证一个线性化系统

（此部分会结合Mit6.824和PingCap tikv 的线性化验证的代码阅读和文章来描述）

ShareNote

  1. Dynamo
  2. Riak
  3. Cassandra
  4. 数据密集型应用系统设计

MIT6.824 Lab2 实现及解析

发表于2019-08-28更新于2021-01-22

目录

  1. Raft论文阅读
  2. 实现细节 
     2.1 [Raft整体流程](#2.1)    
 2.2 [Raft状态机维护](#2.2)  
 2.3 [Raft代码实现](#2.3)

论文阅读及问题

论文各个章节主要解析

  1. 总体介绍，解析创造Raft的原因，并且简单描述Raft与Paxos的不同点
  2. 简单介绍一下副本状态机这个概念
  3. 简单描述Paxos的问题（包括了不好理解以及工业化上面的问题）
  4. 阐述Raft为什么比Paxos好理解
  5. Raft的算法的详细描述以及边界条件
  6. Raft集群出现成员变动的时候如何处理
  7. Raft的日志压缩和快照
  8. Client与Raft集群的交互方式

实现的时候，重点要看Figure2中所提及的条件。

代码实现

Raft整体流程

此处只是一个比较简单的忽略具体可能出现错误细节的描述。
本质上Raft就是一个通过一个维护一个协程里面的状态机，并且通过其他做网络请求的协程达成大部分节点在共识的算法。
具体可以看这里的演示动画

Raft状态机的转换

此处是一个简单状态机的描述，具体转换的原因也已经在图上面有标出来。

Raft代码的实现

代码实现在这个Lab中实际上分为了3part

  1. PartA 完成选举
  2. PartB 完成日志
  3. PartC 完成持久化的工作，并且处理共识的边界条件

PartA 的实现

跟随论文中提及的RequestVote RPC 以及 AppendEntries RPC 实现即可
此处可以只需要完成心跳发送后可以保证非主节点不超时，不会使得Term有变动即可。

一个注意的点，发送这两个RPC的时候，都是需要并行发送的，因此每个请求需要使用一个GoRoutine去进行实现。
下面代码就是发送AppendEntries的代码的实例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
logs := make([]Log, 0)
tmpIndex := min(max(0, rf.nextIndex[number]-1), rf.logs[rf.getLen()].Index)
if tmpIndex < rf.logs[rf.getLen()].Index {
    logs = rf.logs[tmpIndex+1-firstIndex:]
    //DPrintf("server %d is Leader, tmpIndex is %d, firstIndex is %d, len of log is %d, commited index is %d",
    //	rf.me, tmpIndex, firstIndex, len(rf.logs), rf.commitedIndex)
}
args := AppendEntriesArgs{Term: rf.currentTerm, LeaderId: rf.me,
    PrevLogTerm: rf.logs[tmpIndex-firstIndex].Term, PrevLogIndex: tmpIndex,
    Entries: logs, Leadercommited: rf.commitedIndex}
//  使用Goroutine来发送请求
go func(args AppendEntriesArgs, number int) {
    reply := AppendEntriesReply{}
    ok := rf.sendAppendEntires(number, &args, &reply)
    rf.mu.Lock()
    defer rf.mu.Unlock()
    if !ok {
        DPrintf("allAppendEntries server %d call remote %d rpc AppendEntries failed", rf.me, number)
    }
    if args.Term != rf.currentTerm {
        return
    }
    if reply.Term > rf.currentTerm {
        //rf.mu.Lock()
        rf.state = Follower
        rf.currentTerm = reply.Term
        // TODO why Term voliate needed to persist?
        rf.persist()
        //rf.mu.Unlock()
        return
    }
    if reply.Success == true && rf.state == Leader {
        if len(args.Entries) > 0 {
            rf.nextIndex[number] = args.Entries[len(args.Entries)-1].Index + 1
            rf.matchIndex[number] = rf.nextIndex[number] - 1
            if rf.matchIndex[number] > rf.commitedIndex {
                rf.updateCommit()
            }
        }
    } else if rf.state == Leader {
        if rf.nextIndex[number] > reply.PrevIndex+1 {
            rf.nextIndex[number] = reply.PrevIndex + 1
        } else {
            rf.nextIndex[number] = max(rf.nextIndex[number]-1, 1)
        }
    }
}(args, number)

并且注意实现的时候的锁的使用，保证每次使用锁都有加锁和解锁的操作成对出现，否则可能会出现一些比较奇怪的情况。

PartB的实现

此处需要接受模拟从客户端的请求进来然后把Log先放到本地的Log上面，然后把Log同步到其他的节点上面去进行共识的达成。

首先的条件，需要确保Start函数接受请求的时候必须是Leader的角色，否则不会接收请求。（论文中有提及，此处Raft集群中非Leader节点不会把日志写入的请求转发到Leader节点上，这个是为了维护的方便来做的）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func (rf *Raft) Start(command interface{}) (int, int, bool) {
	index := -1
	term := -1
	isLeader := true
	// Wanring: do not double add lock for GetState function
	rf.mu.Lock()
	defer rf.mu.Unlock()
	term, isLeader = rf.GetState()
	if isLeader {
		index = rf.logs[rf.getLen()].Index + 1
		//oldLogLen := len(rf.logs)
		rf.logs = append(rf.logs, Log{command, term, index})
		//DPrintf("server %d is Leader. new log has been appended, old length is %d, now is %d.  index number is %d, commitedindex is %d",
		//	rf.me, oldLogLen, len(rf.logs), index, rf.commitedIndex)
		if len(rf.chanNewLog) == 0 {
			rf.chanNewLog <- 1
		}
		rf.persist()
	}
	return index, term, isLeader
}

重点处理的地方是nextIndex和MatchIndex 的计算以及维护的问题

Apply的实现

因为对于外部客户端的行为来说，Start函数是一个异步的函数, 所以实际上客户端是通过等待Make函数中输入的ApplyCh来确定能够apply成功，保证对外的原子性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
func (rf *Raft) doApply() {
	for {
		rf.mu.Lock()
		st := rf.state
		rf.mu.Unlock()
		if st == Killed {
			return
		}
		select {
		case <-rf.chanCommit:
			for {
				rf.mu.Lock()
				if !(rf.lastApplied < rf.commitedIndex && rf.lastApplied < rf.logs[rf.getLen()].Index) {
					rf.mu.Unlock()
					break
				}
				FirstIndex := rf.logs[0].Index
				if rf.lastApplied+1 >= FirstIndex {
					index := min(rf.lastApplied+1-FirstIndex, rf.getLen())
					msg := ApplyMsg{CommandValid: true, Command: rf.logs[index].Command, CommandIndex: rf.lastApplied + 1}
					rf.lastApplied++
					rf.mu.Unlock()
					//can't lock when send in channel, dead lock
					// canApplychan is to block the new
					rf.chanCanApply <- 1
					rf.chanApplyMsg <- msg
					<-rf.chanCanApply
					rf.mu.Lock()
				}
				rf.mu.Unlock()
			}
		}
	}
}

PartC的实现

此处首先需要添加状态机的持久化的方法，并且需要在启动的时候添加一个读取旧的持久化状态机的方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
func (rf *Raft) InstallSnapshot(args *InstallSnapshotArgs, reply *InstallSnapshotReply) {
	rf.chanCanApply <- 1
	rf.mu.Lock()
	reply.Success = false
	persistFlag := 0
	if args.Term < rf.currentTerm {
		reply.Term = rf.currentTerm
		rf.mu.Unlock()
		<-rf.chanCanApply
		return
	}
	if rf.currentTerm < args.Term {
		rf.currentTerm = args.Term
		rf.ClearChan()
		rf.voteFor = -1
		rf.state = Follower
		persistFlag = 1
	}
	reply.Term = rf.currentTerm
	// similar to appendEntries receive call
	rf.chanAppendEntries <- 1
	firstIndex := rf.logs[0].Index
	nowIndex := args.LastIncludeIndex - firstIndex
	if nowIndex < 0 {
		if persistFlag == 1 {
			rf.persist()
		}
		reply.PrevIndex = firstIndex
		rf.mu.Unlock()
		<-rf.chanCanApply
		return
	}
	rf.logs = args.Logs
	rf.lastApplied = args.LastIncludeIndex
	rf.commitedIndex = args.LeaderCommitIndex
	rf.persister.SaveStateAndSnapshot(rf.getPersistByte(), args.Snapshot)
	msg := ApplyMsg{CommandValid: false, Snapshot: args.Snapshot}
	rf.mu.Unlock()
	rf.chanApplyMsg <- msg
	<-rf.chanCanApply
	reply.Success = true

}

1
2
// 启动的时候添加这个方法把Snapshotload出来
rf.readPersist(persister.ReadRaftState())

并且需要注意在投票部分需要根据Safty那里提及的一个重要的地方，如果RequestVote RPC里面的日志Term与目前的Term不是一致的情况下，不能通过数票数的方法来进行计算。这个是为了整个集群的正确来考虑的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
func (rf *Raft) updateCommit() {
	N := rf.commitedIndex
	FirstIndex := rf.logs[0].Index
	for i := max(rf.commitedIndex+1, FirstIndex+1); i <= rf.logs[rf.getLen()].Index; i++ {
		num := 1
		for j := range rf.peers {
			if j != rf.me {
				if rf.matchIndex[j] >= i {
					/*
						this part is paper 5.4.2 limit, only can count replicate when log's term
						is equals to currentTerm
					*/
					if rf.logs[i-FirstIndex].Term == rf.currentTerm {
						num++
					}
				}
			}
		}
		if num > len(rf.peers)/2 {
			N = i
		}
	}
	if N > rf.commitedIndex && rf.state == Leader {
		rf.commitedIndex = min(N, rf.logs[rf.getLen()].Index)
		rf.chanCommit <- 1
	}
}

分布式系统概念简介及其问题的描述

发表于2019-08-21更新于2021-01-22

目录

  1. 什么是分布式系统
  2. 分布式系统能够解决什么问题
    2.1 服务器的性能扩展方案
    2.2 分布式系统的特点
    2.3 分布式系统解决的问题
  3. 分布式系统的问题
    3.1 网络问题
    3.2 时钟问题
    3.3 节点问题
  4. 在不可靠硬件构建可靠软件需要满足的条件和假设
    4.1 真相由多数决定
    4.2 理论系统模型与现实
  5. ShareNote

#什么是分布式系统

分布式系统

1
2
3
// Definantion from IBM Site 
A distributed computer system consists of multiple software components that are on multiple computers, but run as a single system. The computers that are in a distributed 
system can be physically close together and connected by a local network, or they can be geographically distant and connected by a wide area network. A distributed system can consist of any number of possible configurations, such as mainframes, personal computers, workstations, minicomputers, and so on. The goal of distributed computing is to make such a network work as a single computer.

简述：
分布式的计算机系统是由多台形式的计算机（包括服务器、个人电脑、工作站、嵌入式系统的形式）组成的，但是对外表示成一个完整功能的系统。对于分布式系统的使用者，可以把一个大型的分布式系统看作一个黑盒来进行使用。

#分布式系统能够解决什么问题

2.1. 服务器的性能扩展方案

对于一个系统来说，如果当需要计算的问题太过庞大的时候，会有两种思路来进行算力的添加

1.Scale UP（纵向扩展）
纵向扩展:企业后端大型服务器以增加处理器等运算资源进行升级以获得对应用性能的要求。
这种是比较传统的思路，具有以下特点：
1. 扩容的成本较高。能够支持纵向扩展的系统都需要服务商进行服务的支持，需要购买特殊的硬件。而不是使用能够通用的硬件来进行扩容
2. 延迟低，单点吞吐量大。本质上是单点的系统，可以减少了很多网络上面的开销，所以延迟一般会比分布式系统的延迟更低。而且单节点如果在没有超过负荷的情况下，因为硬件堆积在上面，单节点的性能一般会比分布式的单节点性能更强。
3. 备份成本高，遇到不可恢复的故障时可能要中断一定时间的服务。如果对于纵向扩展的设备需要进行灾备的情况下，可能需要同时购入相同配置的硬件通过配置主备来继续容灾，而不能通过像分布式系统在多个地域继续节点部署和配置添加达到冗余的程度。
实例的系统： 传统的SAN(storage area network)系统

2.Scale Out(水平扩展)
水平扩展：企业可以根据需求增加不同的服务器应用，依靠多部服务器协同运算，借负载平衡及容错等功能来提高运算能力及可靠度。
这是从谷歌的三篇经典的分布式论文（bigtable、distributed filesystem、 mapreduce)提炼出来的特点：
1. 成本低，扩展性好。使用的是市面上可以购买的通用的服务器配件，并且可以根据需求进行硬件的升级即可提升整体的性能（如存储服务器上面，把HDD更换为全闪存的NVME SSD，立刻可以在读写的吞吐量和时延上面获得具体的提升）
2. 弹性好。可以通过配置动态的增删服务器，可以动态的对业务使用的服务器资源具有更好的调配，并且可以通过弹性的配置获得根据地理位置的容灾以及数据冗余功能（如金融企业中的两地三中心的需求）
3. 处理单节点无法处理的问题。（最重要）

2.2 分布式系统的特点

  1. 扩展性强(Scalability)
  2. 有冗余(Redundancy)

2.3 分布式系统解决的问题

分布式系统最重要解决的问题是：

  1. 处理单机无法计算的问题。
    因为问题能够被分治成为了更小的问题，使得更弱的节点也可以进行计算
  2. 同样的工作量下，减少计算使用的时间。
    因为部分计算是可以并行来继续执行的，只要调度得当的情况下，可以减少单机系统中出现的等待的情况。
  3. 在有限的成本内，可以通过多区域部署服务来降低该地区的服务的时延。

分布式系统的问题

（此部分有部分会引用到数据密集型应用系统设计（DDIA）的第8章部分的内容）
软件工程的世界里面没有银弹，分布式系统并不是所有问题的最优解。它在解决上述问题的情况下也引入了下面的多种问题
此处需要引入一个部分失效的概念： 

1
部分失效：在分布式系统中，可能会出现系统的一部分工作正常，其他部分出现难以预测的故障。

对于互联网服务的分布式系统的假设

  1. 需要7*24的可用状况，所以不能有服务不可用的状态
  2. 采用通用的硬件，故障率会较高，成本较低
  3. 采用IP和以太网的技术，网络可靠性不如专有网络(Fiber Channel等。。。)

因为上面的三个原因可能引申出来的另外的假设

  1. 系统越大，局部组件失效的概率越大。（长时间的运行时间，失效、修复、再失效是正常的状况而不能当为异常的情况去考虑）
  2. 由于局部失效的概率高，因此需要必须容忍部分节点失败，并且能够保持对外提供可用的服务

所以实际上我们目前大部分的分布式的系统是需要在不可靠的硬件上面通过软件容错来构建可靠的系统。

所以分布式系统遇到的问题可以分为三个大类

  1. 网络类问题
  2. 时钟问题
  3. 节点软件和硬件的问题

网络问题

对于上面的假设（主要是成本考虑）来说，一般都会采用无共享的方式来构建集群。

由于通常使用的都是以太网来构建，而且以太网是异步的网络。可能会出现下面的这些情况

  1. 请求丢失
  2. 请求再队列等待，无法发送（网络问题或者接收方繁忙在内核的队列中等待）
  3. 远程接收节点失效（节点崩溃）
  4. 远程节点无法响应
  5. 远程节点有返回，但是返回过程中丢失
  6. 远程节点处理请求，但是在返回时候被延时处理（优先级问题， 或者网络问题或则和发送方阻塞了）

此处需要多引入一个新概念，网络分区

1
网络分区（Network Partition）：当网络的一部分由于网络故障而与其他部分隔开，称之为网络分区或者网络分片

在工程的实践中，网络故障(丢包、链路中断、路由问题、物理设备损坏)的概率是远比想象中高， 因此在基于我们假设的前提的环境下面，必须要把网络分区和网络故障接入到软件中进行容错。

对于如何处理检测是否故障，需要判断的一个问题是，是节点服务上面出现了真实的故障，还是网络的不可靠导致的服务失效的表现。

1
2
3
4
5
6
在实际生产的实践中有这样的方法来快速的在本应用层（网络正常的情况下）来进行简单的判断
1. 通过服务注册的心跳来注册自己的服务存活，并且把死亡状态的服务实例剔除出可用服务中
2. 检测进程是否崩溃，如果崩溃发送一个信号。（或者在我的工作经历中，使用一个进程去定时检测进程是否存活，失败了发送信号使得资源进行重启的尝试，并且上报告警）
3. 通过交换机去查询网络的状况
4. 通过中间件的自身监控（如Rabbitmq的web界面）来监控中间件的执行状况
5. 定期去尝试访问网络是否通达

但是最终我们唯一能够完全判断故障的方法只有超时，来保证节点是不可用的状态（为了保证网络的不可靠问题）。

超时引入的问题

我们如何能够判断什么时候才是最好的超时的判断间隔呢？

对于上面的这个问题， 我们引入两个问题的前置的讨论

  1. 是什么导致我们会出现网络的不稳定
  2. 如果出现超时之后，会有怎样的影响，会导致什么样的后果

网络不稳定的原因

根本的原因： 在设计目前的TCP/IP的协议和方法的时候，我们的目的是为了尽可能高的提高资源的利用率
设计的思想： 通过动态分配和竞争的机制使得动态决定那个包被发送，但是这样的方法必然会引入排队的机制 

1
2
3
4
// 出现网络不稳定的原因可能如下
1. 对于交换机的角度，会有多条等待队列来进行数据报文的转发，如果符合过重，则需要等待轮询机制来等待发送的机会，并且如果数据量过多的情况下，也有可能出现数据报文被丢弃，然后被不断重试的现象
2. 在服务器的处理中，因为Linux内核处理接收到的报文也是类似于交换机的处理模式，通过队列来对接受到的包进行排序以及复制到用户态，因此也是需要一定的时间需要处理
3. 在TCP的协议中的重传的机制也会根据返回的报文的控制字段来减小发送窗口的大小来减少对接受方的压力，可能导致排队会提前到发送方的等待队列中。并且重传机制会进行多次的重试，引入了隐形的超时时间

调用超时（网络超时）可能会导致的后果

主要的影响是发生了责任的转移，可能带来可能的影响

  1. 命令的重复执行
  2. 数据迁移
  3. 当整个系统处于高负荷的状态，可能会把其他正常的部分通过转移职责导致整个系统被拖垮

因此我们必须很小心调整这个超时的阈值,如果在以前的情况下，可能需要系统管理员对于在生产环境的情况下调整一定的参数来慢慢测试得出一个最优值。
但是在最近的组建的实现中有两种新的思路

1
2
1. 通过内部的一个故障检测器来计算成功率来进行对超时阈值的控制（Akka， Cassandra， Hytrsix中有使用此种方法）
2. 通过对数据的采集清洗和分析（AIOPS）（可能是APM(Application Performance Metric)的埋点采集数据以及对监控数据的整体清洗通过一些机器学习的模型来计算出超时的阈值）

时钟问题

分布式的系统的时钟问题也是一个非常值得重视的问题，后面会有我自己的工作案例来说明可能出现的情况的严重性。

其实对于时间我们一般分为两种的应用方式

  1. 在一段时间内的统计数据（时间段）
  2. 某些时间点是否有指定动作完成或某个历史行为的发生的时间点

服务器时间的维护方式以及问题

每个机器的时间可以通过两种方式来共同维护

  1. 本地时间（通过主板的石英振荡器来维护）
  2. 通过与一个准确的时间获取源来定是同步时间（NTP和Chrony就是服务于方面的协议）

这两种的结合不一定能够保证这样的可信赖的分布式集群中的时间就必然是同步的

  1. 本地时间本来每个节点都可能会出现偏差
  2. 同步时间的时候必须通过网络来进行同步，而在我们上面提及的假设中，网络是不可靠的，因此可能会出现失败的情况。
  3. NTP如果发现时间差别太大（实际生产中是时间差>=10分钟的情况下）的话会拒绝同步（但是Chrony并没有此问题）
  4. 闰秒的问题

当然可以像Google维护Spanner集群那样采用高精度的原子钟加上GPS定位来保证错误在一定的可接受范围内运行（一般误差的单位为5微妙）。但是不是每个分布式系统都能够有如此之高的维护成本去使用这种方式来

时钟的概念

时钟可以分解为两个时钟的概念

  1. 物理时钟
    物理时钟:包括了两种一个是墙上时钟，一个是单调时钟。可以理解为可以通过系统时间相关的API进行获取的时钟。
  2. 逻辑时钟
    逻辑时钟：可以理解为分布式系统中全局的单调递增的事件ID，事件发生顺序与此相同。

物理时钟

需要先引入一个时间调整的概念：

如果把时间以时间轴的方式来进行表达，往时间变大的方向调整为向前调整，往时间变小的方向调整的是向后调整。
只要发生了时间的变动，我们都可以称之为服务器发生了时间跳变。

1. 墙上时钟

根据日历返回当前的时钟，就是我们平时在Linux上直接使用date命令或者语言内置的时间相关的api的输出。
这种时钟可以与时间同步服务器后同步后进行修改，可能会出现向前调整或者向后调整的可能性

2. 单调时钟

用于： 适合测量持续的时间段
单调时钟的特性：
1. 保证只会向前调整
2. 不需要进行同步

计算和调整的方式

在一个时间点进行对单调时间的获取，然后完成某项工作后，再去检查时间。但是这段时间的差值并没有太大的意义。

时间与事件的顺序问题

当两个客户端对于一个分布式的数据库（非Raft或者Paxos类型，如Riak）分别进行写入的情况下（此处假设先写入的客户端为A，晚写入的客户端为B）

当B虽然在发生的时间比A要晚，但是B在集群中同步完成的时间比A要早的情况写。即对外部来说A还未写入成功的情况下，先执行了B的操作，可能导致B的操作丢失（如果B的操作是依赖于A先写入的操作）。
上面是一个非常经典的关于分布式集群时间与事件的顺序问题。然而这种问题即使在时间同步服务精度再再提高的情况下，也无法保证它的执行的顺序与时间是一致的。

工作上发生过与物理时间相关的问题

问题1： 发生时间跳变后，导致任务的调度器不再调度任务的情况 

现象的描述： 
调度器默认应该定时把任务调度到线程上面，但是查看日志后发现任务并没有被调度   
原因解释：    
时间发生了向后的跳变，但是跳变的幅度大于调度的间隔，导致系统中认为调度成功，之后就没有追踪下面的状态（因为当时那部分代码的实现是再调度的时候修改调度的时间为last调度时间）    
解决方法：    
把时间从墙上时间更换为单调时间，然后添加检查执行的间隔即可。

问题2：同步时间后，由于时间差溢出导致结果溢出的问题

现象描述：
从Ceph Mgr获取单个采集数据的情况下，然后发现数据变得异常的大，是一个int64是随机数
原因解释：
因为采用的是墙上的时候，但是发生了时间的向后调变，导致计算出来的值发生异常
解决方法：
把墙上时间更换为单调时间

逻辑时钟

做法： 需要一个全局的单调递增的ID。
但是是否可以使用同步后的时间来做呢？
答： 不可以。因为还是时间精度的不确定性。

节点本身的问题（硬件和软件）

比较极端但是可能出现率比较高的场景是进程出现暂停的情况

  1. 带GC的编程语言的GC(Garbage collection) halt
  2. 虚拟化环境的虚拟机的暂停
  3. 电脑发生休眠或者断电
  4. 上下文切换的情况下卡住了
  5. 执行同步磁盘的操作的时候（如fsync操作）
  6. 接收到信号导致进程退出的情况下

#在不可靠硬件构建可靠软件需要满足的条件和假设

此部分为DDIA第8章的描述总结，可以理解成为读书笔记

真相由多数决定（重要的判定条件）

节点不能通过自己的信息来判断自身的状态。因为节点可能出现失效、假死、甚至无法恢复的状况.可能出现的场景如下

1
2
3
1. 节点成功收到请求，但是因为路由问题，无法进行返回，超时后而被判失效
2. 半断开的节点发现自己的信息没有被其他节点所确认，意识到自己网络出现问题
3. GC halt导致无法接受请求，但是对于应用来说，切回到工作状态时候，自身状态没有变化

以上的多种情景都是实际出现问题，但是自身的状态并不会改变，因为没有收到其他节点的通知，它会一直维持原来的状态。
所以分布式的算法依赖节点间的相互投票与最小投票数（使用Quorum机制，m>=(n+1)/2）进行对比来产生结果,由于一个集群不会存在两个多数在同事做出相互冲突的决定，减少对特定节点的依赖。

基于上面所提及节点不能通过自己的信息来判断自己的状态，我们讨论一个比较常见的问题，主节点与锁是比较常见的使用方法

1
2
3
可能的出现的场景
1. 只允许一个节点作为数据库分区的主节点（Multi-Raft是其中的一种实现）
2. 只允许一个事务或者客户端持有特定资源的锁，以防止同时并发写入带来的数据被破坏的问题

如果由自己的状态决定可能会出现的问题

但是此处我们的假设时在分布式系统中，那么有可能出现节点中间出现了角色的切换，但是如果不加以对状态的判断，可能会出现这样的问题
问题描述

客户端写入存储的时候需要先从分布式服务中获取锁，有两个客户端在线，客户端A先从服务中获取锁，然后发生了进程halt状态（可能是GC或者其他的原因）
如果不加判断的情况下，在客户端A halt的状态的情况下，客户端B获得锁并且写入存储成功，然后客户端A从Halt状态中回复正常，客户端A认为锁还在，然后写入存储，
如果两个客户端写入的是同一个文件的话，数据可能会出现问题。

解决上面的问题

对于上面的问题，我们可以使用一个Fencing令牌来解决这个问题。(此机制到后面的文章还会继续详细讲解)

我们在客户端A获取锁的时候给令牌赋予一个值，为33。 在客户端B获取锁的时候赋予一个令牌值34。
当B写入完成后，存储会把已写入令牌改为34，下一次分发的令牌为35， 这样的话，如果A带上33的令牌写入的时候直接被拒绝，能够保证一致性。
实际上上面这种方法不仅加上了一个令牌，而且在服务器端会有一个关于令牌的校验。这种做法非常常见。

理论系统模型与现实

对于一个在现实中能够容错的分布式系统，我们需要对预期的系统错误证明形式化的描述。我们通过定义部分的系统模型来形式化描述算法的前提条件。

计时模型

#### 同步模型 假定有上界网络延迟和上界进程的暂停和上界时钟误差。（但是这个模型一般不存在，因为以太网的不可靠性，除非使用更加稳定的网络介质，并且使用高精度时间设备同步） #### 部分同步模型 大多数情况下像一个同步系统运行，但是会有超出网络延迟，进程暂停和时钟漂移的上界。这个就是比较现实的模型，就是上面我们提到的真实环境可能出现的情况的总和。而且大部分时间比较稳定，小部分时间会有背离，但是发生背离就会出现三者中的组合的情况出现。 #### 异步模型

节点失效模型

#### 崩溃-中止模型 节点以一种特定的方式发生故障，故障后，出现系统崩溃，并且节点不会再添加进入集群中，无法恢复 #### 崩溃-恢复模型 节点可能会在任何时候发生崩溃，并且会在未知的时间长度来进行恢复。但是节点上只要持久性存储的数据都可以在恢复之后得以保存，内存的状态会消失。 #### 拜占庭失效 在非可信任的集群中进行共识的计算，可能会出现作弊、欺诈的操作（区块链上面的假设的环境） 所以满足我们实际生产环境（互联网或者企业内部的环境）的是 部分同步模型+ 崩溃恢复模型的组合。

我们目前的分布式的环境是 崩溃-恢复模型+ 部分同步的模型

分布式共识算法的正确性必须要有以下的性质

  1. 唯一性
    两个令牌不能获得相同的值
  2. 单调递增
    如果请求x返回令牌tx， 请求y返回了令牌ty, 且x在y开始之前先完成，tx < ty
  3. 可用性
    请求令牌的节点如果不发生崩溃最终一定能收到响应（无论是对应用来说正确或者错误的回答）

分布式共识算法的安全性和活性

在正确性中其实可以再进行细分分为安全性和活性（理解上，并非准确的定义，准确的定义可以查看FLP的理论）：
安全性： 没有发生意外
活性： 预期的事情一定会发生（最终会发生）

如果违反了安全的属性，我们可以找到发生特定时间的时间点。但是违反安全属性的事件发生，必定不可逆，数据丢失。
活性的话无法明确具体发生的时间点，但是希望再未来某个时间点能够达到要求。

ShareNote

PS: 文章中部分的图来源是来自于《数据密集型应用系统设计》，为PDF翻译的截图，截图的引用在此处。如果涉及到版权的问题，请通知我，我会使用工具继续重画。

  1. IBM Defination of Distributed System
  2. 数据密集型应用系统设计
  3. FLP Impossibility
  4. 拜占庭错误
  5. 拜占庭容错
  6. Riak

MIT6.824课程的简介以及学习的原因

发表于2019-08-20更新于2021-01-22

MIT6.824

MIT6.824是一门对于分布式系统的讲解和实验的课程。

课程自述

1
2
3
4
5
6
7
6.824 is a core 12-unit graduate subject with lectures, readings, programming labs, an optional project, a mid-term exam, and a final exam.
It will present abstractions and implementation techniques for engineering distributed systems.
Major topics include fault tolerance, replication, and consistency. Much of the class consists of studying 
and discussing case studies of distributed systems.

翻译：
6.824是一门集合了讲座、阅读、编程实验、附加课程、中期考试和期末考试的课程。他会展示能够为构建一个分布式系统的抽象和实现的技巧。本课程主要讨论的是容错、副本冗余、以及一致性相关的问题。大部分的课程都是由学习和讨论分布式系统的案例来组成的。

因此MIT6.824是一门学习分布式系统的一门比较好的课程。

所需能力

完成了整个实验之后，我总结了一下学习整个过程所需要的基础的能力（在后面的文章中也会继续提及到，此处只是为了做一个简单的Summary）

  1. 阅读论文的能力
    阅读论文不仅仅是快速阅读论文，掌握大意的能力，并且需要当实现遇到问题时，回顾论文是否能够找出代码实现中与论文描述的细节中是否一致的能力

  2. 根据日志进行Debug的能力
    因为在此实验中，Debug是不可能使用Ide来进行大量的打点操作来进行Debug。（实验中会有多个实例并且可能会出现多个并发操作的情况）因此需要学会在运行项目给的测试中去尝试打有用的Log来进行Debug。

此外，还需要在脑中浮现出一个整个代码运行的逻辑图和实际代码执行的走向图的对比（如果暂时没用这种能力的话，可以先用纸和笔全部把它画出来。俗话说的好：好记性不如烂笔头），这样能快速定位到代码的问题可能会在哪一部分出现问题。

  1. 耐心&细致
    因为这其实是我第二次做这个实验，第一次只是做完lab2就已经放弃了。究其原因，一个很重要的部分是之前并没有仔细的阅读lab代码中的上面的很多注释和MITLab实验页的上面的Hint和注意的点。所以先把那些全部看完,然后全局思考完成之后再开始动手写代码的实现。

并且遇到困难的时候，跑到失败的TestCase上面去详细的Debug问题是什么原因。本实验中可能出现很多的实现问题是与锁和Go Channel的使用相关的问题。

课程中需要实现的代码

  1. 完成简易版的MapReduce
  2. 根据论文完成Raft的协议的实现（工业版的实现可以查看（2）Tikv和（3）Etcd上面的实现）
  3. 基于2中的Raft共识层，实现一个简易版的带副本冗余的KV数据库
  4. 基于2中的Raft共识层，实现一个带调度的Multi-raft的简易实现

ShareNote:

  1. HomePage for MIT6.824
  2. tikv
  3. etcd
  4. 知乎上关于分布式课程的推荐
  5. 知乎上关于学习MIT6.824的建议