主要读了Database internal的LSM Tree相关部分,顺便完成了对6.824 lab2的优化.自己最近感兴趣的点主要就是存储以及分布式系统,这周准备带着看一下leveldb中LSM Tree相关实现,完成6.824 的lab 3.

LSM Tree

LSM Tree主要的优点在于写入速度很快(SSD sequential write速度和mem的random write相当),缺点则是读和空间放大比较严重.

自己目前还没有看过任何LSM Tree的实现,只通过Database Internal了解过一点简单的LSM原理,包括但不限于以下知识点:

  • LSM Tree是什么(memtable, memtable)?为什么用它?
  • LSM Tree怎么做read/write/delete?
  • …怎么优化冗余的键值对?
  • …怎么优化读放大?

raft优化

由于是二刷6.824,这一次完成lab2一共大概花了4天时间(通过所有测试),但是优化代码花了一周时间.

虽说是优化,其实只是面向测试样例的一些简单调优,并没有对raft算法本身做巨大改动.主要的测试指标为:rpc数量以及测试完成时间.

完成优化之后lab2共计耗时5分30秒左右(100次运行平均),此处给出2B以及2C的测试数据:

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
48
49
50
Test (2A): initial election ...
  ... Passed --   3.1  3   60   15080    0
Test (2A): election after network failure ...
  ... Passed --   5.0  3  142   26268    0
Test (2A): multiple elections ...
  ... Passed --   6.4  7  577  105547    0
Test (2B): basic agreement ...
  ... Passed --   0.3  3   16    4107    3
Test (2B): RPC byte count ...
  ... Passed --   0.5  3   48  153102   11
Test (2B): agreement despite follower disconnection ...
  ... Passed --   2.9  3   81   20270    7
Test (2B): no agreement if too many followers disconnect ...
  ... Passed --   3.3  5  191   37753    3
Test (2B): concurrent Start()s ...
  ... Passed --   0.6  3   20    5614    6
Test (2B): rejoin of partitioned leader ...
  ... Passed --   4.5  3  159   33320    4
Test (2B): leader backs up quickly over incorrect follower logs ...
  ... Passed --   9.3  5 1354  946435  102
Test (2B): RPC counts aren't too high ...
  ... Passed --   2.0  3   46   13453   12
Test (2C): basic persistence ...
  ... Passed --   4.0  3  103   23403    6
Test (2C): more persistence ...
  ... Passed --  13.6  5  835  176284   16
Test (2C): partitioned leader and one follower crash, leader restarts ...
  ... Passed --   1.1  3   35    8487    4
Test (2C): Figure 8 ...
  ... Passed --  34.7  5 1014  184489   32
Test (2C): unreliable agreement ...
  ... Passed --   2.4  5  978  311040  246
Test (2C): Figure 8 (unreliable) ...
  ... Passed --  36.7  5 5282 11695881  168
Test (2C): churn ...
  ... Passed --  16.4  5 4607 2857762  767
Test (2C): unreliable churn ...
  ... Passed --  16.1  5 2179  874603  374
Test (2D): snapshots basic ...
  ... Passed --   1.8  3  173   69754  251
Test (2D): install snapshots (disconnect) ...
  ... Passed --  43.4  3 1583  427709  388
Test (2D): install snapshots (disconnect+unreliable) ...
  ... Passed --  45.7  3 1819  455134  344
Test (2D): install snapshots (crash) ...
  ... Passed --  34.5  3  889  272795  377
Test (2D): install snapshots (unreliable+crash) ...
  ... Passed --  37.3  3 1041  294722  355
PASS
ok      6.824/raft      325.832s

我采取了如下的一些手段实现上述两个指标的优化:

  • “批”处理start请求.leader维护一个$nextInd$至$nextInd+x$的窗口,只有在这个窗口内的start请求才会被立即发送.我在实验过程中注意到,经常会出现同时start若干个请求,我一开始的实现是对于每一个start请求都立刻进行一轮AE,但实际上没有必要.好处是,如果出现瞬时较多的start请求,会保证一个窗口内的请求立刻被处理(没有真正的批处理带来的一定时延),而剩余的请求则做batch处理(这些请求本身就已经不会被立刻处理了,直接作batch),保证了不会同时产生太多的AE rpc;坏处是对于窗口之外的请求会存在比较高昂的失败代价.
  • heartbeat优化.实际上没有必要专门使用empty AE rpc去做heartbeat,如果在heartbeat timeout结束之前已经发送了AE请求,实际上可以不发送heartbeat.这样做可以减轻网络带宽压力.
  • 使用Cond减少for check带来的开销.对于appCh的提交我使用了sync.Cond,只有在commitInd可能发生变化的时候才检查是否需要提交到appCh上.

实验整体感觉不难,主要的坑点在于多线程无法调试(实际生产环境中就是分布式集群了,但是可以在一个机器上调试),遇到的主要的问题有:

  • 2D实验中的Snapshot和CondInstallSnapshot产生的隐蔽的死锁
  • rpc上下文切换后带来的隐蔽错误(处理rpc回复时的rf的各个信息都已经被更新过了,可能有问题!)
  • …

对了,还看了 Don’t look up,美国老完蛋了.