LSM🌲之Go与Badger

Go 与 Badger#

上回我们说到 LSM🌲在 HDD 上由于出众的写入性能和优化后可以接受的读取性能，在 B🌲混战的数据库领域获得了一席之地，新型数据库因为 LSM🌲相关的技术好学好写，并发性好等一系列原因纷纷转头到 LSM🌲相关的存储后端.

书承上回，由于 HDD 是转着写的，所以随机访问性能比顺序访问慢了 100 倍…

但，有一个跨时代的发明出现了～！

他，就是一直在涨价，通过减低使用寿命减价的存储介质 SSD!

通过上回的文章，我们了解到 LSM🌲快的原因主要有几点:

新来的先到内存去
顺序写入磁盘
定期整理磁盘

第三步决定了冷数据从磁盘读取的速度，但代价就是必须对数据分 level, 比如 10M 是一个 level, 100M 是另一个 level, 从小的 level 在不断的整理的时候 level 变大的过程叫compaction, 升级的公式大部分 LSM 都是以下公式:

sizeof( L+1 ) = 10 * sizeof( L )

当一个 Level 撑不下这个 Level 装的信息的时候需要整理到更大的 Level 和别人合并的时候这个叫做写放大 (毕竟多写了 N 遍)

同理，当我在找一个 key 的时候，这个 key 存储在不同的 level 上的时候我会找很多次，这个就叫做读放大(毕竟多读了 N 遍)

所以… 优化的空间就是使用 SSD 比 HDD 高效的随机读取性能去优化 LSM🌲从而降低读放大和写放大.

但是写放大这个步骤会大幅度缩短 SSD 的寿命，所以我们要利用高效的随机读取能力的时候减少写放大.

Badger 横空出世#

创始人：老子是 Go 用户，老子要写 DB, 一看 RocksDB, 可以是可以，但是我咋得开 CGo, 一开 CGo Goroutine 就被 pthread 拖慢成了💩, 诶，咋还有内存泄漏？！垃圾 C 艹 (本人也赞同), 老子拿 Go 重写 (本人也赞同，毕竟 RocksDB 的开发者连怎么写 CMake 都不知道)

大概 Badger 只提供了如下功能

Get, Set, Delete, and Iterate functions. On top of it, it adds CompareAndSet and CompareAndDelete atomic operations

相较于 RocksDB, Badger 从一开始就对事物做出了一定的考量，使得写数据库更简单.

Badger 和 HDD 上的 LSM🌲的区别#

把 KV pair 分开存储，Key 存在一个 LSM🌲上，而 Value 存在 WAL 上 (原文 value log), 这样 LSM🌲的大小就变成了 RocksDB 的一半，从而降低了写放大的性能损耗，第二点就是通过使用 SSD 的随机读取功能直接从 WAL 里取出来值.

实现细节#

KV 分别存储#

由于原教旨 LSM🌲的主要的成本就是compaction, 在这期间要进行离线排序，所以产生了迭代，但是往往是对 Key 排序，Value 在这个过程中不会更改，所以 Badger 分配了 Key 和 Value 的存储，这样降低了一大半无用的 Value 被排序浪费的内存.
第二，Badger 把 Value 的位置用delta encoding AKA 指针的方式存储在了 Key 的右边，这样就可以告诉 SSD 这个 key 对应了什么位置的 Value, 同时通过限制单个文件的大小提升了缓存的性能，假设一个 key 16 byte 一个指针 16byte 就可以在一个 64M 的文件中存储超过 200 万行的 KV.

写放大缩小#

因为降低了 Value 部分存储在 LSM🌲的大小，所以 Value 这部分就不会产生写放大，也不会随着 Key 到处乱窜，
如果我们假设 Value 大小 1kb, 16byte 还是 key 的大小，那么写放大仅仅有

(10*16 + 1024)/(16 + 1024) ~= 1.14

也就是仅仅放大了一点点🤏
这体现在性能上就是写入速度是 RocksDB 的 N 倍，N 取决于 Value 产生的写放大落入磁盘的时间.

读放大缩小#

还是因为 Value 没在 LSM, 所以 LSM 的大小大幅度缩小，这还意味着产生的层级变少了，进而在内存中存储的部分就变多了，通过 bench 发现 RocksDB 在值固定在 1kb, 有两千两百万行数据的时候 RocksDB 用了 72gb 的数据集存在了 LSM 树上，而 Badger 这边只存 Key 和偏移，所以仅仅存了 1.7G, 全部在内存里…

所以读取速度吊打了 RocksDB 3.5 倍….
迭代速度… 那就是 3.5*N

具体 bench mark 大概是这样吊打的#

由于篇幅有限#

更多内容请参看

下期预告… 可能采访一下老迟看看俺们 Agate 有什么更先进的地方