序 replication是一系列的通信问题 怎样的排列顺序和模式才能提供好的性能和可用性？ 在网络分区故障发生时，如何容错呢？ 通信模型 通常，通信模式会有两种，同步和异步。就上图而言，步骤是这样的 同步 客户端发生请求 服务器处理请求 返回客户端结果 优点： 强大的持久性保证（strong durability guarantee） 缺点： 系统性能受最慢的服务器影响 无法容忍服务器丢失 受网络延迟影响大 异步 客户端发送请求 返回客户端结果 服务器处理请求 优点： 可以容忍网络分区和网络延迟 probabilistic durability guarantees 缺点： 无法保证所有节点数据一致 保持可用性 复制算法 复制算法有很多分类标准 同步或者异步 single copy system或者multi-master systems single copy system 能够避免数据分歧，而multi-master system则有可能造成数据分歧。 single copy system behave like a single system, even if parts of node failed....

这篇文章会按这样的顺序来简单介绍raft算法： 第一部分 从整体上看raft算法是基于怎样的context（原论文的词汇，我的理解其实就是类似与数据结构一样的东西），即 replicated state machine上运行 假设在没有任何异常情况（没有任一一个节点挂掉，没有网络故障，所有节点的log正常插入，且follower与leader一致）下的集群是怎样运转的。 在进入第二部分之前，会简单介绍raft中的基础概念和基础结构 第二部分将会把假设的理想情况，即没有任何异常的条件去掉，看看在有节点异常挂掉或者由网络故障导致的节点失联，或者有节点之前挂掉后重连，结果log与leader的log有冲突的情况下，raft算法会怎样工作，其实主要是靠： leader election log replication 第三部分会基于第二部分继续探究，这样raft是不是就能确保一致性了呢？No，No，No，其实还没有，所以这部分会探讨safety: election restriction committing entries from previous terms safety argument follower and candidate crashes timing and availability 第四部分cluster membership changes 第五部分Log compaction 1. Overview raft是一个解决日志一致性和分区容错的算法。这个算法依赖于replicated state machine这个数据结构，而replicated state machine本身也由这样三部分构成：...

Time and order 单机上，程序都是按照一定的顺序一个一个执行。而分布式系统希望能像单机一样执行程序，因此，顺序对于分布式系统而言是很重要的。 同时顺序这么重要是因为它能很容易的预测系统执行的正确性： 执行相同的操作 即使这里有多台计算机，也按相同的顺序执行 但是因为操作是在多个不同节点上进行，因此不同节点间需要准确的时间或者其他形式的通信来确保顺序的正确。 全序和偏序 分布式系统自然状态下是偏序的 分布式系统全序： 若使用通信，代价昂贵 时间同步困难且难以维持 时间 通常可以通过时间来定义操作的顺序 程序中，时间和时间戳的三种使用场景： order duration interpretation 时间的速率相同吗？ 对于人而言，更容易想象推理一件事接着一件事发生的情景，如果说按事情发生的时间排序，人可能更容易推理全序关系，不擅长推理偏序关系。 但是，分布式系统设计需要尽量避免对时间和顺序的强假设，因为这个假设越强，这个系统能容纳的错误越少，对时钟要求就越高，所付出的代价就越高。但是如果降低对时间和顺序的假设，就可以更好利用资源做分布式计算。 有三种答案： global clock Yes local clock no,but no clock no synchronous system model has a global clock parially synchronous model has a local clock asynchronous system model doesn’t have clock Time with a “global-clock” assumption 系统拥有一个全局时钟，即每个节点的时间都是相同。 这个假设很好，但是实际本身实现还是有误差，例如NTP同步也会有难以避免的延迟。 除此之外，还会有外界其他因素的影响： 时钟漂移 用户意外改变机器上的本地时间 新加入的机器时间不一致 但这个假设本身是很好的，可以自由使用时间戳来确定全局顺序。使用了这个假设的如：Cassandra， Spanner。前者使用时间戳来解决写入冲突，用较新的时间戳覆盖旧的。后者会同步时间，但也会考虑最坏的时钟漂移。...

序 more abstraction: 从组成结构上，A具有的B都有，A并没有添加其他任何新的部分,但是对事物的描述更加准确和易于管理 通过移除一些不重要的部分，使得概念更容易理解 那么，分布式系统的最小集描述是怎样的呢？怎样的系统会被认为是分布式的呢？ System Model 一般情况下，分布式系统的运行情况是这样的： 程序同时地运行在独自的节点上 程序间通过网络通信，但可能因此导致不确定性事件和消息丢失 没有共享内存和共享锁 上述情景意味着： 每个节点同时执行程序 存储在本地的数据: 节点可以更快的访问它们的状态，但是任何关于全局状态的信息可能不准确（即过期） 节点可以单独挂掉并且单独地从宕机中恢复 消息可能会发生延迟或者丢失 每个节点的时间可能会不一致 系统模型列举了与特定系统设计相关的许多假设。 系统模型就是关于实现分布式系统的环境和设施的一组假设。 这些假设包括： 每个节点具有怎样的能力且它们会怎样挂掉 如何操作节点间的通信链接和通信链接会怎样挂掉 整个系统的特点 一个健壮的系统模型使用最不严格的假设（weakest assumptions）：针对这种系统模型的算法需要考虑各种不同的环境可能发生的错误，并容忍这种错误，因为这中模型要求很少（very few and very weak assumptions） 另一方面，也可以创建一个系统模型with strong assumptions nodes in system mode 节点作为一台可以计算和存储的主机： 具有执行程序的能力 可以将数据存储到内存中或者稳定的状态 时钟 节点失败 大多数crash-recovery failure model: nodes can only fail by crashing, and can recover after crashing at some later point....