LevelDB---必知的基础知识小春留学论坛
简介
是⼀个功能上类Redis的key/value存储引擎。Redis是⼀个基于纯内存的存储系统，⽽LevelDB是基于内存 + SSD的架构，内存存储最新的修改和热数据（可理解为缓存），SSD作为全量数据的持久化存储，所以LevelDB具备⽐redis更⾼的存储量，且具备良好的写⼊性能，读性能就略差了，主要原因是由于冷数据需要进⾏磁盘IO。Facebook在levelDB的基础上优化了 RocksDB。
LevelDB⼀般采⽤ proxy + 多机主备 的形式搭建集群，常见的兼容Redis协议，可通过Redis客户端访问。
架构
LevelDB 有点类似于建筑，分为地基和地⾯两部分，也就是磁盘和内存，⽽地基⼜好⽐地壳结构分了很多层级，不同层级的数据还会定期从上往下移动 —— 沉积作⽤。如果磁盘底层的冷数据被修改了，它⼜会再次进⼊内存，⼀段时间后⼜会被持久化刷回到磁盘⽂件的浅层，然后再慢慢往下移动到底层。bra是什么
内存结构
LevelDB 的内存中维护了 2 个跳跃列表，⼀个是只读的 rtable，⼀个是可修改的 wtable。简单理解，跳跃列表就是⼀个 Key 有序的 Set 集合，key通过分层连接的⽅式，提⾼链表的查找速率。跳跃列表的查找和更新操作时间复杂度都是 Log(n)。
跳跃列表是由多个层次的链表构成，其中最底层的链表存储了所有的 Key，它们是有序的。普通链表并不⽀持快速⼆分查找，但是跳跃链表的特殊结构可以让最底层的链表以近似⼆分查找算法的效率定位到指定节点。简单理解就是跳跃列表同时具备了有序数组的快速定位能⼒和链表的⾼效增删能⼒。但是它会付出⼀定的代价，在实现上有⼀定的复杂度。
rtable和wtable的数据结构
其中 quence 为全局⾃增序列号，LevelDB 遇到⼀个修改操作，全局序列号⾃动加⼀。LevelDB 中的 Key 存储了多个版本的 Value。LevelDB 使⽤序列号来标记键值对的版本，序列号越⼤，对应的键值对越新。
type 为数据类型，标记是 Put 还是 Delete 操作，只有两个取值，0 表⽰ Delete，1 表⽰ Put。
如果是删除操作，后⾯的 value_size 字段值 为 0，value 字段值是空的。我们要将 Delete 操作等价看成 Put 操作。同时为了节省存储空间，internal_key_size 和 value_size 都要采⽤ varint 整数编码。
如果跳跃列表中同⼀个 key 存在多个修改操作，也就是说有多个「复合 Key」，那么这⼏个「复合 Key」 肯定会挨在⼀起按照 quence 值排序的。当 Get 操作到来时，它会在跳跃列表中定位到 key 所在的位置，选择这⼏个同样的 key 中 q 最⼤的「复合 Key」，提取出其中的 value 值返回。
三大作风
权利游戏待 Put 和 Delete 操作⽇志写到⽇志⽂件后，其键值对合并成「复合 Key」插⼊到 wtable 的指定位置中。
待 wtable 的⼤⼩达到⼀个阈值，LevelDB 将它凝固成只读的 rtable，同时⽣成⼀个新的 wtable 继续接受写操作。rtable 将会被异步线程刷到磁盘中。Get 操作会优先查询 wtable，如果找不到就去 rtable 中去找，rtable 如果还找不到，再去磁盘⽂件⾥去找。
澳洲留学
因为 wtable 要⽀持多线程读写，所以访问它是需要加锁控制。⽽ rtable 是只读的，它就不需要，但是
它的存在时间很短，rtable ⼀旦⽣成，很快就会被异步线程序列化到磁盘上，然后就会被置空。但是异步线程序列化也需要耗费⼀定的时间，如果 wtable 增长过快，很快就被写满了，这时候 rtable 还没有完成序列化，⽽wtable 急需变⾝怎么办？这时写线程就会阻塞等待异步线程序列化完成，这是 LevelDB 的卡顿点之⼀，也是未来 RocksDB 的优化点。
图中还有个⽇志⽂件，记录了近期的写操作⽇志。如果 LevelDB 遇到突发停机事故，没有持久化的 wtable 和 rtable 数据就会丢失。这时就必须通过重放⽇志⽂件中的指令数据来恢复丢失的数据。注意到⽇志⽂件也是有两份的，它和内存的跳跃列表正好对应起来。当 wtable 要变⾝时，⽇志⽂件也会跟着变⾝。待 rtable 落盘成功之后，只读⽇志⽂件就可以被删除了。
磁盘结构
LevelDB 在磁盘上存储了很多 sst ⽂件，sst 表⽰ Sorted String Table，⽂件⾥所有的 Key 都会有序的。每个⽂件都会对应⼀个层级，每个层级都会有多个⽂件。底层的⽂件内容来源于上⼀层，最终它们都会来源于 0 层⽂件，⽽ 0 层的⽂件⼜来源于内存⾥的 rtable 序列化。⼀个 rtable 会被序列化为⼀个完整的 0 层⽂件。这就是我们前⾯所说的「下沉作⽤」。
从内存的 rtable 序列化成 0 层 sst ⽂件称之为「Minor Compaction」，从 n 层 sst ⽂件下沉到 n+1 层 sst ⽂件称之为「Major Compaction」。之所以这样区分是因为 Minor 速度很快耗费资源少，将 rtable 完整地序列化为⼀个 sst ⽂件就完事了。⽽ Major 会涉及到多个⽂件之间的合并操作，耗费资源多，速度慢。层级越深的⽂件总容量越⼤，在 LevelDB 源码⾥有⼀个层级容量公式，容量和层级呈指数级关系。⽽通常每个 sst ⽂件的⼤⼩都差不多，区别就成了每⼀层的⽂件数量不⼀样。
capacity=level>0&&10^(level+1)M
每个⽂件⾥⾯的 Key 都是有序的，也就是说它内部的 Key 取值会有⼀个确定的范围。0 层⽂件和其它层⽂件有⼀个明显的区别那就是其它层内部的⽂件之间范围不会重叠，它们按照 Key 的顺序严格做了切分。⽽ 0 层⽂件的内容是直接从内存 dump 下来的，所以 0 层的多个⽂件的 Key 取值范围会有重叠。
当内存出现读 miss 要去磁盘搜寻时，会⾸先从 0 层搜寻，如果搜不到再去更深层次搜寻。
better off如果是其它层级，搜寻速度会很快，因为可以根据 Key 的范围快速确定它可能会位于哪个⽂件中。但是对于 0 层，因为⽂件 Key 范围会重叠，所以它可能存在于多个⽂件中，那就需要对这多个⽂件进⾏搜寻。正因如此，LevelDB 限制了 0 层⽂件的数量，如果数量超出了默认的 4 个，就需要「下沉」到 1 层，这个「下沉」操作就是 Major Compaction。
出超所有⽂件的 Key 取值范围、层级和其它元信息会存储在数据库⽬录⾥⾯的 MANIFEST ⽂件中。数据库打开时，读取⼀下这个⽂件就知道了所有⽂件的层级和 Key 取值范围。
MANIFEST ⽂件也有版本号，它的版本号体现在⽂件名上如 MANIFEST-000361。每⼀次重新打开数据库，都会⽣成⼀个新的MANIFEST ⽂件，具有不同的版本号，然后还需要将⽼的 MANIFEST ⽂件删除。
数据库⽬录中还有另外⼀个⽂件 CURRENT，它⾥⾯的内容很简单，就是当前 MANIFEST 的⽂件名。LevelDB ⾸先读取 CURRENT ⽂件才知道哪个 MANIFEST ⽂件是有效⽂件。在遇到断电时，会存在⼀个⼩概率中间状态，新旧 MANIFEST ⽂件共存于数据库⽬录中。
我们知道 LevelDB 的数据库⽬录不允许多进程同时访问，那它是如何防⽌其它进程意外对这个⽬录⽂件进⾏读写操作呢？仔细观察数据库⽬录，你还会发现⼀个名称为 LOCK 的⽂件，它就是控制多进程访问数据库的关键。当⼀个进程打开了数据库时，会在这个⽂件上加上互斥⽂件锁，进程结束时，锁就会⾃动释放。
还有最后⼀个不那么重要的操作⽇志⽂件 LOG，它记录了数据库的⼀系列关键性操作⽇志，例如每⼀次 Minor 和 Major Compaction 的相关信息。
世界贸易组织的英文缩写
多路归并
Compaction 是⽐较耗费资源的操作，为了不影响线上的读写操作，LevelDB 将 Compaction ⼯作交给⼀个单⼀的异步线程来完成。如果⼯作量巨⼤，这个单⼀的异步线程也会有点吃不消。当异步线程
吃不消的时候，线上内存的读写操作也会收到影响。因为只有 rtable 沉到磁盘⾥了，wtable 才可以变⾝。只有 wtable 变⾝了，才会有新的 wtable 被创建来容纳后续更多的键值对。总之就是⼀环套⼀环，环环相扣。
下⾯我们来研究⼀下 Compaction 。Minor Compaction 很好理解，就是内容空间有限，所以需要将 rtable 中的数据 dump 到磁盘 0 层⽂件。那为什么需要从 0 层⽂件 Compact 下沉到 1 层⽂件呢？因为 0 层⽂件如果过多，就会影响查找效率。前⾯我们提到 0 层⽂件之间的 Key 范围会有重叠，所以单个 Key 可能存在于多个⽂件中，IO 读次数将会被⽂件的数量放⼤。通过 Major Compaction 可以减少 0层⽂件的数量，提升读效率。那是不是只需要下沉到 1 层⽂件就可以了呢？那 LevelDB 究竟是什么原因需要这么多层级呢？
beingdone
假设 LevelDB 只有 2 层（ 0 层和 1 层），那么时间⼀长，1 层肯定会累计⼤量的⽂件。当 0 层的⽂件需要下沉时，也就是 Major Compaction 要来了，假设只下沉⼀个 0 层⽂件，它不是简简单单地将⽂件元信息的层数从 0 改成 1 就可以了。它需要继续保持 1 层⽂件的有序性，每个⽂件中的 Key 取值范围要保持没有重叠。它不能直接将 0 层⽂件中的键值对分散插⼊或者追加到 1 层的所有⽂件中，因为 sst ⽂件是紧凑存储的，插⼊操作肯定涉及到磁盘块的移动。再说还有删除操作，它需要⼲掉 1 层⽂件中的某些已删除的键值对，避免它们持续占⽤空间。
那 LevelDB 究竟是怎么做的呢？它采⽤多路归并算法，将相关的 0 层⽂件和 1 层 sst ⽂件作为输⼊，进⾏多路归并，⽣成多个新的 1 层sst ⽂件，再将⽼的 sst ⽂件⼲掉，同时还会⽣成新的 MANIFEST ⽂件。对于每个 0 层⽂件，它会根据 Key 的取值范围搜寻 1 层⽂件中和它的范围有重叠部分的 sst ⽂件。如果 1 层⽂件数量过多，每次多路归并涉及到的⽂件数量太多，归并算法就会⾮常耗费资源。所以LevelDB 同样也需要控制 1 层⽂件的数量，当 1 层容量满时，就会继续下沉到 2 层、3 层、4 层等。
⾮ 0 层的多路归并资源消耗要少⼀些，因为单个⽂件的 Key 取值范围有限，能覆盖到下⼀层的⽂件数量有限，参与多路归并的输⼊⽂件就少了很多。但是这个逻辑有个漏洞，那就是上下层的⽂件数量有 10 倍的差距，按照平均范围间隔来算，意味着上层平均⼀个⽂件的取值范围会覆盖到下⼀层的 10 个⽂件。所以说⾮ 0 层的多路归并资源消耗其实也不低，Major Compaction 就是⼀个⽐较消耗资源的操
cosmic
作。
