etcd/raft code walkthrough

我照着 raft 论文重新过了一遍 etcd/raft 的代码,主要的文件是 etcd 下面的 raft.go。对照这个代码重新梳理一遍也算是深入理解一下 raft 算法。接下来会包含两个视频一个是选举相关的内容,一个是日志复制的内容,我 walktrough 的时候默认是大致读过论文的,对一些机制和字段都有了解,没有具体解析每个字段的来历,并且把一些问题按照代码的顺序重新理了一遍。

第一部分是关于选举的,raft 本身是一个 quorum based 的算法,一致性要靠“大多数人”的同意,并且为了简单和不必要的竞争,raft 只有一个主节点,在收到大多数人的投票以后成为主节点。

第二部分是关于日志复制的,raft 需要让主节点把客户端的请求复制到大多数节点上才能算达成一致,并且 commit,下面介绍的是复制的机制,并且 ConfChange 和 Snapshot 也是走这个流程达成一致的。

之后的 walkthrough 应该会慢慢补上,关于一些其他的逻辑和具体的一些函数的细节部分会在后面放出。

mvcc

v2 版本的实现存在 watcher 丢失或者丢失事件的问题,导致客户端要重新获取一遍。新版本是有本地嵌入式的数据库来避免这些问题。
mvcc 是 etcd v3 版本的存储实现主要有两个部分,一个是 backend 的 boltDB 和内存索引 key index。

BoltDB 是一个 B+ 树的嵌入式 KV store,相对于 leveldb 适用于写多读少的情况,我之前的文章简单介绍了一下 leveldb 的设计,BoltDB 比较适合读多写少,或者存在大范围 scan 的情况下比较合适,还有类似 levedb 的产品 badger,是纯 Go 实现的,在多写的情况下 leveldb 的衍生品表现更好。

BatchTx 就是收集很多的 call,然后在一个 Update 里面完成。

backend 里面存的 key 是 revision ,其中 main revision 是事务编号,sub revision 是事务中操作的编号,etcd 在 boltdb 上还做了一层缓存,所以多了一些锁机制。
内存索引中存的是真正的 key 到 revison 的索引。

key_index -> tx_buffer -> boltdb.tx

调用路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
kv:
WriteView 是一些直接操作
ReadView
Read() TxnRead
Write() TxnWrite 是拿到对应的 transaction
revision:
main
sub
kvstore:
readView readView{kv} 用了 Read() Read/Write 是 kvstore 自己实现的用于拿 backend 的和自己的各种锁。(kvstore\_txn.go)
writeView writeView{kv} 用了 Write()
treeIndex:
keyIndex
writeView:
拿到 kv 的 Write(storeTxnWrite): 首先查 tw.s.kvindex.Get 然后再 backend.Tx UnsageSeqPut,然后更新 keyindex,append changes,处理 lease (old detach new attach)
readView
storeTxnRead: keyindex Revisons -> tx.UnsafeRange
lessor lesor(重音在后面)
leaseBucket 在单独的一个 bucket 里面

Donate comment here