关于rocksdb:RocksDB剖析系列-Logstructured-mergetree

B+ Tree 的毛病

B+ 树最大的性能问题是会产生大量的随机 IO，随着新数据的插入，叶子节点会缓缓决裂，逻辑上间断的叶子节点在物理上往往不间断，甚至拆散的很远，但做范畴查问时，会产生大量随机读 IO。
对于大量的随机写也一样，新插入的数据在磁盘上的地位可能相隔很远，会产生大量的随机写 IO。

相比 B + Tree，LSM-Tree 可能会损失一部分读性能，但换来了微小的写性能的晋升。

LSM-Tree 原理

Memtable

当一个 Memtable 被写满时，它将变为 immutable 的，前面进来的数据将写入一个新的 Memtable。而后盾线程将会将 Immutable Memtable flush 进一个 SST 文件，并在 flush 好后将该 Memtable 销毁

数据结构

可抉择的数据结构

• SkipList (Default)
• HashLinkList
• HashSkipList
• Vector

Memtable 默认采纳跳表实现
而哈希跳表我之前没有接触过，后果搜寻后发现是先对哈希值取模放入对应的桶中，再在每个哈希桶中保护跳表构造。
这样的话应该会晋升随机单个查问的速度，而范畴查问应该会变慢一点。

此外，依据官网文档，只有 SkipList 反对并发插入。

Flush

三种状况下会触发 flush 操作

1. 当某一个 Memtable 的大小超出了ColumnFamilyOptions::write_buffer_size
2. 当所有列族的 Memtable 的总大小超出了 DBOptions::db_write_buffer_size，或者DBOptions::write_buffer_manager 收回了 flush 的信号。这种状况下 size 最大的那个 Memtable 将被 flush
3. WAL 的大小超过了DBOptions::max_total_wal_size。这种状况下最老的 Memtable 将被 flush，以便清空它相应的 WAL 中的局部。

Write Ahead Log

RocksDB 的每次更新都会写入两个地位：内存中的 memtable（稍后将 flush 到 SST 文件）和磁盘上的预写日志（WAL）。而当 Memtable 中的数据 flush 后，WAL 中对应的数据将被删除

WAL 被用作故障后复原数据，它默认是开启的。也能够通过配置敞开它。