Data Structures That Power Your Database

基础
为了取得好的写性能，采用append only的方式
为了取得好的读性能，外加索引
然鹅索引会降低写性能（不是顺序写）

Hash Indexes

将kv log同步到hashtable，读走内存
如何应对不断追加的log？按size分segment，对写满的segment做compaction，合并key
由于segment在compaction之后会变小，还可以将多个seg merge在一起。
每一个seg上维护一个hashtable，查的时候先去最新的，如果不存在依次向后查。
虽然我知道他可能是想引出lsm，不过截至到这里为啥不只维护一个hashtable?多个hashtable，旧的可以持久化，恢复起来比较快

• file format to byte

• 不真实delete key，改为打一个特殊的标记，真实delete违背了appendonly的原则

• crash recovery

  • hash index持久化，这里回避了一个问题，对于旧的seg是没问题的，但是对于新的不断在追加的seg，hash持久化要如何保证不会影响写性能不持久化← ←

• partially written records: checksums

• concurrency control: 单线程写，多线程读

append only的优势

• hdd和ssd顺序写性能都好于随机写

• 并发和crash recovery都比较容易，eg:不需要担心更新到一半挂了，可是这个例子用checksum不是也能解吗

• 碎片少

限制

• 如果hashtable非常大，内存放不下，落盘性能很差

• 没办法范围查找

SSTables and LSM-Trees

sstable = sorted string table, kv sorted by key

1. merging，用类似归并排序的方式，每个seg都是有序的，性能很好。如果有key出现在多个seg，取时间最靠前的。

2. 只需要维护很少的key，对于查找，先用hashtable确定范围，然后在scan

3. 索引之间的内容可以做压缩，减少磁盘空间和io量，如果是全量做压缩，scan的时候要先解压在找吗，如果只是对每个kv的v做压缩，考虑实际情况v可能比较小，效果存疑

Constructing and maintaining SSTables

如何构造sst

• 内存维护一个数据结构为平衡树的memtable，handle写

• 当memtable大小超过阈值时，持久化为seg，此时seg已经是有序的了

• 对于读请求，先去memtable找，然后按照新旧程度去各个seg找

• merge and compaction process做seg的合并

如何防止宕机后memtable丢失，可以同时维护一份append only log

Making an LSM-tree out of SSTables

LSM-tree : Log-Structured Merge-Tree

Performance optimizations

查找不存在的记录慢：加布隆过滤器。
compated and merged策略：size-tiered， leveled-tiered

B-Trees

Making B-trees reliable

主要问题发生在写多页的时候: 处理方式和sstable差不多,write ahead log
并发操作：加latch

B-tree optimizations

• 在故障恢复上，使用cow代替wal，在一个其他的节点写，然后改指针，并发控制也可以用这个做。但是会有很多碎片吧。

• 不存储完整的键。mysql的前缀索引？

• 顺序写上的优化，不过it’s difficult to maintain that order as the treegrows,lsm的方案会容易很多

• 叶子节点上加指针

• fractl tree借用了lsm的思路

Comparing B-Trees and LSM-Trees

Advantages of LSM-trees

write amplification 写放大，对ssd影响更大。
受限于磁盘的写是瓶颈
当写带宽还可以的时候，由于顺序写的原因， 写性能会好于b-tree
ssd内部会有log-structed的算法来把随机写转换为顺序写，但是lsm-tree依然会有更好的表现。

Downsides of LSM-trees

compaction非常占磁盘带宽，会使响应时间偶尔彪高