hmm，如果我早一年读过着本书，去年面试的时候就不会挂在两个系统设计上了。
这章还是很hardcore的，从一个简单的问题开始，带我们了解各种DB的index原理。

Chapter 3： Storage and Retrieval

先来设计个database吧

要求：
给你一个只追加的filesystem
实现提供set，get操作的database

方法：
set就把key和value都追加的一个文件末尾，另起一行，用csv格式。
get的时候从文件里读，key可能有多行，最后一行有key的那个value拿出来，就是最后的修改。

分析：
其实很多DB的思想就是这样，这些记录的都是log，（如果听过redo log，undo之类的就很容易了解这个了）。这个log是十分重要的一块，就是靠他们来保证crash的时候也能正确的恢复。
这个DB在set的时候十分高效，只需要顺序写log。
但是在get的时候十分慢，需要scan所有的数据，然后找到最后一个出现的key，用他的值。
所以我需要优化这个get的性能，就需要有index（索引）。index是额外的数据结构，从primary data里面抽出来去加速query。get加速了，但是在write的时候，需要维护这个index，自然就很难比直接在file尾部追加更快，所以这就是一个trade-off：好的index能加速读，但是降低写的新能，所以db默认不是index所有，需要开发者来定义合理的index。

Hash index来优化读新能

V1.
假设内存足够大，能容纳所有的key，也简单，hash记录下来key->data在文件里的offset。
对于get，在hash里面找，找到的话就去file对应的offset里面去找，并读出来返回。
对于set，先追加到文件里面，然后给hashmap里面更新这个key对应的offset。

但是一直写，disk还是会爆的。怎么优化?删掉那些已经被复写的key-value
V2.
我们不再单独写一个file，我们把一个file给分成若干个segment，每当一个file写打过一定数量，我们就关闭这个file，另外新起一个file。每个file我们叫segment。
在后台，我们可以跑起来一个线程，专门做压缩。首先，你一个file里面可能key出现多个，那就把早的给删除掉，就只留最后一个key，这样每个segment就变小了。其次，我们不仅可以只删除，还可以合并，这样两个segment之间还可能会删掉一下重复的，因为后面写的数据肯定新，所以在合并的时候也容易，这样将合并出来的写成新的segment，替换掉原先的若干个已经被处理的segments。
现在每个segment都维护一个自己的hashmap。
当get来的时候，从最新的hashmap往老的hashmap一直查。因为后台线程保证segment不会特别多，所以看hashmap也不会太多。
set来的时候就和之前一个样。

hash 上的优化

V3.
File format
不用csv，直接用二进制形式，前面用四个byte做长度，后面跟着这个长度的raw string。
Deleting records
用个特殊标记标记当前key被删除，则之后再merge的时候可以把之前的记录都直接丢掉。
Crash recovery
现在你可以根据segment files扫一遍，然后重新再内存里建立这样的hash maps。问题是重启的时候如果segment file太大的，load时间很长。Bitcask是在hashmap做snapshot，然后直接把snapshot存到硬盘上。recover的时候只需要从硬盘直接load那个对应map。
Partially written records
加checksum来看数据完整性，吧checksum也写进segment file里面
Concurrency control
写的时候肯定只能做单线程来写。读的时候可以多线程来搞。

小节

刚开始看这个只追加写的file的时候，觉得运行效率或者对硬盘的利用率都是问题，但是当到达V3的时候，觉得也是个不错的solution。其实bitcask就是用这一套逻辑来做。
几个重要的点：
1.追加的顺序写性能是比随机写的效率要高的，再磁盘硬盘上是十分明显的，即使SSD,顺序写也依然比随机写要好。
2.concurrency和crash recovery很简单。因为毕竟是单线程，对于B树为基础的，要支持并发，就需要考虑很多edge case，比如在写的时候crash掉了，就可能存在数据有一半是更新的，另一半还没有更新。（我觉得这里只讨论了简单性。其实并发是是利用多线程来提高效率，难度增大，但是并不是坏事）
3.不断的这种merge file不会有fragment（硬盘碎片，再B树基础的，如果一个data file存不下一些修改，会使用新的heap file，来来回回，就会导致很多空位，实际数据只有1G，但是占用空间可能是2G）

V3并不完美。
1.如果key太多。内存装不下，hash就显得比较无能为力。你可以选择使用硬盘版本的hash，但是那个效率不会太好，毕竟硬盘的io和内存差好几个数量级，即使是SSD，仍然差很多。
2.range query的支持很差。想要query key是1-1000，还是需要一个个找。但是这种应用场景再实际中是很多的。

如果我面试的时候能答到这个地步，我觉得我当时就应该过了。==|

SSTable 和 LSM-Tree

V4
现在我调整一下前面segment file，我们把segment file里都按照key来排序，保证segment file里面是有序的，即每次写segment file都是追加写有序的key value。（后面解释怎么保证有序）这种file就叫做Sorted String Table。
SSTable有啥好处呢？
1.我们依然需要V3的那种合并操作，但是现在的SST合并会很简单，因为都是顺序的，所以用多路归并算法即可，注意头部多个相同的时候，选择最近的文件取值写进合并的sst，其他的直接丢弃。这是相当高效的。（之前的合并其实需要hash map的帮助，hash的说法O（1）但是如果了解一些hash的内部实现，再rehash的时候还是耗费时间的，常数起码比这个归并大）
2.每次查找一个key的时候，不需要在内存里保存所有的key，而是需要保存一个稀疏的index，跳着来，比如每100个key存第一个key，你存 了handbag，handsome，你需要找handful在这两个key之间，那你即可从handbag的位置开始往后面扫100个以内，找到就找到，找不到就没有。这样的每100个就是一个块，块内部不可以二分查找，因为每个record的size不一样。
3.对这样的一个块，可以压缩存储，一方面是省了disk，另一方面再写下去的时候也是省IO的。看着不起眼，后面会提到 写放大 问题，这个在postgresql里面就比较明显，之前看了我司关于mysql和postgresql选择问题，其中就有一点是写放大。

现在来说下怎么保证每次写的时候都是顺序写入SST。方案就是在每次来write的时候并不直接写SST，而是存在内存的ordered数据结构中，红黑树，AVL都是，c++里的map，java里面的treemap都是有序的。但是不要是hashmap。。。
1.当写的时候，存进内存的数据结构，这个叫memtable。
2.当memtable足够大的时候，就直接新建一个memtable用来继续接受请求，然后把当前的这个memtable就顺序的写进一个新的SST。
3.当读操作过来，现在当前memtable里面找，然后进最近的on-disk sst里找，然后一个一个往下找。（这里其实忽略一个细节，如果当前有memtable再写盘，这个memtable也可以check一下）
4.后台有个进程一直在压缩这些sst。
这里是不完美的，当系统crash的时候，memtable里面是没有写入到disk的，会丢数据，所以每次在写memtable的时候，都追加写一个log file，类似redo，WAL（后面说）。这个log里面的key不是有序的，主要目的是在recover的时候，从依靠这个log来恢复memtable。

性能再优化
当查询一个不存在的key的时候需要遍历所有的sst，这个是比较慢的，一般可以用bloom filter过滤掉绝大部分的请求，这个也是比较有名的方法。（我记得大概意思是多种方式hash，一个key就在多种hash的结果标记true，查询的时候，用多种hash看标记是不是都是true，如果是，就可能存在，如果有一个不是，就一定不是。这样的好处是省空间，坏处就是只能说可能存在，所以最坏情况还是遍历所有的sst，但是概率比较小。如果发生就会会产生p99之外的那些长尾query）

LevelDB和RocksDB的本质就是V4。类似的存储引擎也用在Cassandra和HBase里，这些都是基于GG的Bigtable。
这种index方法就叫做Log Structured Merge-Tree。使用这种机制的storage engine就叫做LSM storage engine。
Elasticasearch和Solr用Lucene做全文检索引擎，也是用了相似的方法来存term dictionary。

关于SST的merge和compact，有两种主流的方法，一个是size-tiered，另外是leveled的。leveldb和rocksdb是按照level的，Hbase是按照size的，Cassandra都支持。按size的就是新的小的sst都不断合并进老的和大的sst中，按照level的key range会分成很多小的sst，老数据被一道另外的level去。（以前看的leveldb都忘记了，这就是不记笔记的坏处啊！！得再看下）

基于log的db设计基本到这里结束，下一篇记着讲第三章的内容。