1 存储的本质
每每讲到存储的本质，我都很喜欢拿图书馆来类比，如果单独讲存储，无非就是把东西存下去，我们当然可以把图书一股脑的塞到图书馆里，而不去考虑各类图书的排布关系。但是存的目的却并不只是存，试想一下，如果存下去的东西，需要花费大量的时间才能取出来，这样的存储系统有什么意义呢？非常认同《数据密集型应用系统设计》中的一句话，中文是“建立秩序，省却搜索”，存储系统的意义就在于要建立秩序，这样的秩序能够帮助我们快速地找到存下去的东西，这也就是存储的本质。
2 levelDB存储系统
2.1 LSM-Tree
LSM-Tree，稍微了解levelDB的人应该对此不陌生，levelDB使用了LSM-Tree作为其大方向的存储结构，网上对LSM-Tree的介绍比比皆是，此处笔者就不再赘述了。需要注意的是，LSM-Tree有如下特点
- 由于将整块的block顺序写（或者说levelDB不支持随机写），所以levelDB的写性能会比较高，利好磁盘。但是需要注意的是，由于其后台compaction的存在，在大量文件情况下，会对磁盘造成压力，侵占磁盘的写带宽，从而对当前写造成影响。
- 由于分级存储的存在，所以LSM-Tree对新数据的读取比较友好，但是对旧数据则比较糟糕，尤其是那些“深入腹地”的数据。这是一种权衡，与B+树那样的类平衡结构相比，LSM-Tree选择更倾向于新数据，B+树则在平衡中也平衡了新旧数据的读取效率。
2.2 SSTable文件结构
本小节内容参考levelDB-hook
本小节，不探讨具体的文件结构，而是通过一系列问题进行巩固，
- SSTable中除了data block之外，还有各种其他block，在写data block时，如何保证其他block不会因为data block的写入而向后移动呢？
- SSTable存储数据时，每条record（除了restart起始点之外）都是用shared key（与前一个record相比）+unshared key来存储，对于一组restart内（默认16个record），如果想要获取该组内靠后的record，岂不是要从头开始逐步处理，才能获取其完整的key？
- 如何获取完整的index block起始地址？data block的起始地址被记录在index block中，但是index block却没有地方记录（footer中储存了最开始的index block的起始地址和大小）？
- 如何逐次获取index block中的数据？
- 读取某个key的record的具体流程是什么？（不考虑filter block的情况下）
- SSTable中的block一定是4KB组织吗？（默认）
- filter block中存储的是什么数据？其存储的是完整的key吗？filter block可以用于定位某个record吗？filter block是如何起作用的？filter block与data block、index block一样具有restart points的设计吗？
- levelDB中有多少种block是按照restart points那样的格式进行组织的？
回答
- 为了保证数据不后移，levelDB严格按照先写data block，在整个SSTable file完成之前filter block、meta index block、、index block等数据都在内存中维护，直到需要持久整个文件时，才持久化其他block。levelDB中的4KB持久线仅对data block起效果。
- 确实如此，但是整个过程在内存中完整，且restart size为16，所以整个过程还是比较高效的。
- 整个SSTable file文件中只有一个filter block、meta index block、index block，所以对于index block而言，只需要在footer中记录其offset和size即可。
- index block数据格式与data block中相同，当获取到某个entry的start offset之后，首先读出前12个字节的header数据（shared length、unshared length、value length），然后解析header，再读出具体的数据即可。
- 流程如下：
5.1 首先需要读SSTable文件的footer，这部分数据量是固定的，在尾部占据48字节的数据量，前32个字节分别是meta index block handle以及index block handle
5.2 根据index block handle定位到index block，读出index block的数据，由于index block中的物理结构与data block相同，所以可以在block内部利用restart points使用二分查找方法找到具体的data block（offset和size）
5.3 根据5.2步得到的offset和size，读出data block数据，之后再次根据restart points进行二分查找，找到该record - 不是，由于压缩的存在，所以想要将block的大小严格控制在4KB是比较难的，但是其实更难的是，如果严格控制block在4KB，那么当某一条record过长，从而出现跨block的情况时，数据的组织、读取都会变得非常困难，所以levelDB并不严格控制block为4KB。4KB对levelDB来说仅代表该data block需要被flush到磁盘中。
- 几个小问题如下：
7.1 存储的是连续的完整的key + 各个key的start offset，并且filter block尾部也记录了start offset的length，用于定位。
7.2 filter block中的数据决定了其不能用于定位某个record，只能用于判断某个record是否存在。
7.3 filter block中存储的是完整的key，所以其不需要先在index block和data block中利用restart points进行二分查找来确定record的位置，所以其可以更快地进行判定。
7.4 没有，filter block核心是通过两个vector，分别记录原始key以及原始key的start offset，等到SSTable file要进行持久化时，再一次性写入文件中。 - data block、index block、meta index block
