ShardedKV 介绍 有关 shardkv，其可以算是一个 multi-raft 的实现，只是缺少了物理节点的抽象概念。在实际的生产系统中，不同 raft 组的成员可能存在于一个物理节点上，而且一般情况下都是一个物理节点拥有一个状态机，不同 raft 组使用不同地命名空间或前缀来操作同一个状态机。基于此，下文所提到的的节点都代指 raft 组的某个成员，而不代指某个物理节点。比如节点宕机代指 raft 组的某个成员被 kill 掉，而不是指某个物理节点宕机，从而可能影响多个 raft 的成员。 ...
介绍 在lab2的Raft函数库之上，搭建一个能够容错的key/value存储服务，需要提供强一致性保证。 强一致性介绍 对于单个请求，整个服务需要表现得像个单机服务，并且对状态机的修改基于之前所有的请求。对于并发的请求，返回的值和最终的状态必须相同，就好像所有请求都是串行的一样。即使有些请求发生在了同一时间，那么也应当一个一个响应。此外，在一个请求被执行之前，这之前的请求都必须已经被完成（在技术上我们也叫着线性化（linearizability））。 kv服务支持三种操作：Put, Append, Get。通过在内存维护一个简单的键/值对数据库，键和值都是字符串； ...
介绍 linearizable read 简单的说就是不返回 stale 数据，具体可以参考Strong consistency models Read Index 机制就是 Leader 在收到读请求时进行如下几步： 如果 Leader 在当前任期还没有提交过日志，先提交一条空日志 Leader 保存记录当前 commit index 作为 readIndex 通过心跳，询问成员自己还是不是 Leader，如果收到过半的确认，则可确信自己仍是 Leader 等待 Apply Index 超过 readIndex 读取数据，响应 Client etcd不仅实现了leader上的read only query，同时也实现了follower上的read only query，原理是一样的，只不过读请求到达follower时，commit index是需要向leader去要的，leader返回commit index给follower之前，同样，需要走上面的ReadIndex流程，因为leader同样需要check自己到底还是不是leader ...
如果允许提交之前任期的日志，将导致什么问题? 我们将论文中的上图展开: (a): S1 是leader，将黄色的日志2同步到了S2，然后S1崩溃。 (b): S5 在任期 3 里通过 S3、S4 和自己的选票赢得选举，将蓝色日志3存储到本地，然后崩溃了。 (c): S1重新启动，选举成功。注意在这时，如果允许提交之前任期的日志，将首先开始同步过往任期的日志，即将S1上的本地黄色的日志2同步到了S3。这时黄色的节点2已经同步到了集群多数节点，然后S1写了一条新日志4，然后S1又崩溃了。 接下来会出现两种不同的情况: (d1): S5重新当选，如果允许提交之前任期的日志，就开始同步往期日志，将本地的蓝色日志3同步到所有的节点。结果已经被同步到半数以上节点的黄色日志2被覆盖了。这说明，如果允许“提交之前任期的日志”，会可能出现即便已经同步到半数以上节点的日志被覆盖，这是不允许的。 (d2): 反之，如果在崩溃之前，S1不去同步往期的日志，而是首先同步自己任期内的日志4到所有节点，就不会导致黄色日志2被覆盖。因为leader同步日志的流程中，会通过不断的向后重试的方式，将日志同步到其他所有follower，只要日志4被复制成功，在它之前的日志2就会被复制成功。（d2）是想说明：不能直接提交过往任期的日志，即便已经被多数通过，但是可以先同步一条自己任内的日志，如果这条日志通过，就能带着前面的日志一起通过，这是（c）和（d2）两个图的区别。图（c）中，S1先去提交过往任期的日志2，图（d2）中，S1先去提交自己任内的日志4。 假如 s1 提交的话，则 index 为 2，term 为 2 的 entry 就被应用到状态机中了，是不可改变了，此时 s1 如果挂了，来到 term5，s5 是可以被选为 leader 的，因为按照之前的 log 比对策略来说，s5 的最后一个 log 的 term 是 3 比 s2 s3 s4 的最后一个 log 的 term 都大。一旦 s5 被选举为 leader，即 d 场景，s5 会复制 index 为 2,term 为 3 的 entry 到上述机器上，这时候就会造成之前 s1 已经提交的 index 为 2 的位置被重新覆盖，因此违背了一致性。 ...
Mulit Raft Group 通过对 Raft 协议的描述我们知道：用户在对一组 Raft 系统进行更新操作时必须先经过 Leader，再由 Leader 同步给大多数 Follower。而在实际运用中，一组 Raft 的 Leader 往往存在单点的流量瓶颈，流量高便无法承载，同时每个节点都是全量数据，所以会受到节点的存储限制而导致容量瓶颈，无法扩展。 ...
介绍 对Raft Figure2 中需要持久化的字段进行保存。 完成persist()和readPersist()函数，编码方式参照注释 优化nextIndex[]回退方式，否则无法通过所有测试 提示: ...
介绍 snapshot是状态机某一时刻的副本，具体格式依赖存储引擎的实现，比如说：B+树、LSM、哈希表等，6.824是实现一个键值数据库，所以我们采用的是哈希表，在Lab 3可以看到实现。 ...
前言 论文 博士论文 博士论文翻译 官网 动画展示 Students’ Guide to Raft （重要） MIT6.824 本篇是实验的前言, 先对论文里面提到的RPC做个大概的梳理和介绍。 Raft 原理可以参考这篇Raft Figure2 Raft 实现的核心在这个图，想要正确实现Raft 必须对这个图有深刻理解，在这里我们对图上的各个RPC 进行介绍和阐述。 ...
介绍 查看Raft0 流程梳理 整体逻辑, 从 ticker goroutine 开始, 集群开始的时候，所有节点均为Follower， 它们依靠ticker()成为Candidate。ticker 协程会定期收到两个 timer 的到期事件，如果是 election timer 到期，则发起一轮选举；如果是 heartbeat timer 到期且节点是 leader，则发起一轮心跳。 ...
流程梳理 相关的RPC 在Raft0 中已经介绍, 这里不再赘述。 启动的Goroutine： ticker 一个，用于监听 Election Timeout 或者Heartbeat Timeout applier 一个，监听 leader commit 之后，把log 发送到ApplyCh，然后从applyCh 中持久化到本地 replicator n-1 个，每一个对应一个 peer。监听心跳广播命令，仅在节点为 Leader 时工作, 唤醒条件变量。接收到命令后，向对应的 peer 发送 AppendEntries RPC。 日志结构 ...