你知道LevelDB吗？

"

引用

了解 Redis 的同学都知道它是一个纯内存的数据库，凭借优秀的并发和易用性打下了互联网项的半壁江山。Redis 之所以高性能是因为它的纯内存访问特性，而这也成了它致命的弱点 —— 内存的成本太高。所以在绝大多数场合，它比较适合用来做缓存，长期不被访问的冷数据被淘汰掉，只有热的数据缓存在内存中，这样就不会浪费太多昂贵的内存空间。

但是 Redis 的诱惑太大了，用它来做持久存储使用起来太方便了。要是内存的价格低廉，真恨不得把所有的数据都堆到 Redis 中，但是技术的选择总是要考虑到现实世界的成本问题。那如何才能享受到 Redis 作为持久层易用性的同时还可以节省内存成本呢？

LevelDB 来了！

LevelDb 简介

LevelDB是Google传奇工程师Jeff Dean和Sanjay Ghemawat开源的KV存储引擎，无论从设计还是代码上都可以用精致优雅来形容，非常值得细细品味。LevelDB的数据是存储在磁盘上的，采用LSM-Tree的结构实现。LSM-Tree将磁盘的随机写转化为顺序写，从而大大提高了写速度。为了做到这一点LSM-Tree的思路是将索引树结构拆成一大一小两颗树，较小的一个常驻内存，较大的一个持久化到磁盘，他们共同维护一个有序的key空间。写入操作会首先操作内存中的树，随着内存中树的不断变大，会触发与磁盘中树的归并操作，而归并操作本身仅有顺序写。

随着数据的不断写入，磁盘中的树会不断膨胀，为了避免每次参与归并操作的数据量过大，以及优化读操作的考虑，LevelDB将磁盘中的数据又拆分成多层，每一层的数据达到一定容量后会触发向下一层的归并操作，每一层的数据量比其上一层成倍增长。这也就是LevelDB的名称来源。

LevelDB整体架构

具体到代码实现上，LevelDB有几个重要的角色，包括对应于上文提到的内存数据的Memtable，分层数据存储的SST文件，版本控制的Manifest、Current文件，以及写Memtable前的WAL。这里简单介绍各个组件的作用和在整个结构中的位置，更详细的介绍将在之后的博客中进行。

Memtable：内存数据结构，跳表实现，新的数据会首先写入这里；

Log文件：写Memtable前会先写Log文件，Log通过append的方式顺序写入。Log的存在使得机器宕机导致的内存数据丢失得以恢复；

Immutable Memtable：达到Memtable设置的容量上限后，Memtable会变为Immutable为之后向SST文件的归并做准备，顾名思义，Immutable Mumtable不再接受用户写入，同时会有新的Memtable生成；

SST文件：磁盘数据存储文件。分为Level 0到Level N多层，每一层包含多个SST文件；单层SST文件总量随层次增加成倍增长；文件内数据有序；其中Level0的SST文件由Immutable直接Dump产生，其他Level的SST文件由其上一层的文件和本层文件归并产生；SST文件在归并过程中顺序写生成，生成后仅可能在之后的归并中被删除，而不会有任何的修改操作。

Manifest文件： Manifest文件中记录SST文件在不同Level的分布，单个SST文件的最大最小key，以及其他一些LevelDB需要的元信息。

Current文件: 从上面的介绍可以看出，LevelDB启动时的首要任务就是找到当前的Manifest，而Manifest可能有多个。Current文件简单的记录了当前Manifest的文件名，从而让这个过程变得非常简单。

读写操作

作为KV数据存储引擎，基本的读写操作是必不可少的，通过对读写操作流程的了解，也能让我们更直观的窥探其内部实现。

1，写流程

LevelDB的写操作包括设置key-value和删除key两种。需要指出的是这两种情况在LevelDB的处理上是一致的，删除操作其实是向LevelDB插入一条标识为删除的数据。下面就一起看看LevelDB插入值的过程。

LevelDB对外暴露的写接口包括Put，Delete和Write，其中Write需要WriteBatch作为参数，而Put和Delete首先就是将当前的操作封装到一个WriteBatch对象，并调用Write接口。这里的WriteBatch是一批写操作的集合，其存在的意义在于提高写入效率，并提供Batch内所有写入的原子性。

在Write函数中会首先用当前的WriteBatch封装一个Writer，代表一个完整的写入请求。LevelDB加锁保证同一时刻只能有一个Writer工作。其他Writer挂起等待，直到前一个Writer执行完毕后唤醒。单个Writer执行过程如下：

• 在MakeRoomForWrite中为当前的写入准备Memtable空间：Level0层有过多的文件时，会延缓或挂起当前写操作；Memtable已经写满则尝试切换到Immutable Memtable，生成新的Memtable供写入，并触发后台的Immutable Memtable向Level0 SST文件的Dump。Immutable Memtable Dump不及时也会挂起当前写操作。
• BuildBatchGroup中会尝试将当前等待的所有其他Writer中的写入合并到当前的WriteBatch中，以提高写入效率。
• 之后将WriteBatch中内容写入Binlog并循环写入Memtable。
• 关注上述代码的最后一行，在所有的值写入完成后才将Sequence真正更新，而LevelDB的读请求又是基于Sequence的。这样就保证了在WriteBatch写入过程中，不会被读请求部分看到，从而提供了原子性。

2，读流程

• 首先，生成内部查询所用的Key，该Key是由用户请求的UserKey拼接上Sequence生成的。其中Sequence可以用户提供或使用当前最新的Sequence，LevelDB可以保证仅查询在这个Sequence之前的写入。
• 用生成的Key，依次尝试从 Memtable，Immtable以及SST文件中读取，直到找到。
• 从SST文件中查找需要依次尝试在每一层中读取，得益于Manifest中记录的每个文件的key区间，我们可以很方便的知道某个key是否在文件中。Level0的文件由于直接由Immutable Dump 产生，不可避免的会相互重叠，所以需要对每个文件依次查找。对于其他层次，由于归并过程保证了其互相不重叠且有序，二分查找的方式提供了更好的查询效率。
• 可以看出同一个Key出现在上层的操作会屏蔽下层的。也因此删除Key时只需要在Memtable压入一条标记为删除的条目即可。被其屏蔽的所有条目会在之后的归并过程中清除。

3,SSTable文件

SST文件并不是平坦的结构，而是分层组织的，这也是LevelDB名称的来源。

SST文件的一些实现细节：

1、每个SST文件大小上限为2MB，所以，LevelDB通常存储了大量的SST文件；

2、SST文件由若干个4K大小的blocks组成，block也是读/写操作的最小单元；

3、SST文件的最后一个block是一个index，指向每个data block的起始位置，以及每个block第一个entry的key值（block内的key有序存储）；

4、使用Bloom filter加速查找，只要扫描index，就可以快速找出所有可能包含指定entry的block。

5、同一个block内的key可以共享前缀（只存储一次），这样每个key只要存储自己唯一的后缀就行了。如果block中只有部分key需要共享前缀，在这部分key与其它key之间插入\"reset\"标识。

由log直接读取的entry会写到Level 0的SST中（最多4个文件）；

当Level 0的4个文件都存储满了，会选择其中一个文件Compact到Level 1的SST中；

注意：Level 0的SSTable文件和其它Level的文件相比有特殊性：这个层级内的.sst文件，两个文件可能存在key重叠，比如有两个level 0的sst文件，文件A和文件B，文件A的key范围是：{bar, car}，文件B的Key范围是{blue,samecity}，那么很可能两个文件都存在key=”blood”的记录。对于其它Level的SSTable文件来说，则不会出现同一层级内.sst文件的key重叠现象，就是说Level L中任意两个.sst文件，那么可以保证它们的key值是不会重叠的。

Log：最大4MB (可配置), 会写入Level 0；

Level 0：最多4个SST文件,；

Level 1：总大小不超过10MB；

Level 2：总大小不超过100MB；

Level 3+：总大小不超过上一个Level ×10的大小。

比如：0 ↠ 4 SST, 1 ↠ 10M, 2 ↠ 100M, 3 ↠ 1G, 4 ↠ 10G, 5 ↠ 100G, 6 ↠ 1T, 7 ↠ 10T

在读操作中，要查找一条entry，先查找log，如果没有找到，然后在Level 0中查找，如果还是没有找到，再依次往更底层的Level顺序查找；如果查找了一条不存在的entry，则要遍历一遍所有的Level才能返回\"Not Found\"的结果。

在写操作中，新数据总是先插入开头的几个Level中，开头的这几个Level存储量也比较小，因此，对某条entry的修改或删除操作带来的性能影响就比较可控。

可见，SST采取分层结构是为了最大限度减小插入新entry时的开销；

Compaction操作

对于LevelDb来说，写入记录操作很简单，删除记录仅仅写入一个删除标记就算完事，但是读取记录比较复杂，需要在内存以及各个层级文件中依照新鲜程度依次查找，代价很高。为了加快读取速度，levelDb采取了compaction的方式来对已有的记录进行整理压缩，通过这种方式，来删除掉一些不再有效的KV数据，减小数据规模，减少文件数量等。

LevelDb的compaction机制和过程与Bigtable所讲述的是基本一致的，Bigtable中讲到三种类型的compaction: minor ，major和full：

• minor Compaction，就是把memtable中的数据导出到SSTable文件中；
• major compaction就是合并不同层级的SSTable文件；
• full compaction就是将所有SSTable进行合并；

LevelDb包含其中两种，minor和major。

Minor compaction 的目的是当内存中的memtable大小到了一定值时，将内容保存到磁盘文件中，如下图：

immutable memtable其实是一个SkipList，其中的记录是根据key有序排列的，遍历key并依次写入一个level 0 的新建SSTable文件中，写完后建立文件的index 数据，这样就完成了一次minor compaction。从图中也可以看出，对于被删除的记录，在minor compaction过程中并不真正删除这个记录，原因也很简单，这里只知道要删掉key记录，但是这个KV数据在哪里？那需要复杂的查找，所以在minor compaction的时候并不做删除，只是将这个key作为一个记录写入文件中，至于真正的删除操作，在以后更高层级的compaction中会去做。

当某个level下的SSTable文件数目超过一定设置值后，levelDb会从这个level的SSTable中选择一个文件（level>0），将其和高一层级的level+1的SSTable文件合并，这就是major compaction。

我们知道在大于0的层级中，每个SSTable文件内的Key都是由小到大有序存储的，而且不同文件之间的key范围（文件内最小key和最大key之间）不会有任何重叠。Level 0的SSTable文件有些特殊，尽管每个文件也是根据Key由小到大排列，但是因为level 0的文件是通过minor compaction直接生成的，所以任意两个level 0下的两个sstable文件可能再key范围上有重叠。所以在做major compaction的时候，对于大于level 0的层级，选择其中一个文件就行，但是对于level 0来说，指定某个文件后，本level中很可能有其他SSTable文件的key范围和这个文件有重叠，这种情况下，要找出所有有重叠的文件和level 1的文件进行合并，即level 0在进行文件选择的时候，可能会有多个文件参与major compaction。

LevelDb在选定某个level进行compaction后，还要选择是具体哪个文件要进行compaction，比如这次是文件A进行compaction，那么下次就是在key range上紧挨着文件A的文件B进行compaction，这样每个文件都会有机会轮流和高层的level 文件进行合并。

如果选好了level L的文件A和level L+1层的文件进行合并，那么问题又来了，应该选择level L+1哪些文件进行合并？levelDb选择L+1层中和文件A在key range上有重叠的所有文件来和文件A进行合并。也就是说，选定了level L的文件A，之后在level L+1中找到了所有需要合并的文件B,C,D…..等等。剩下的问题就是具体是如何进行major 合并的？就是说给定了一系列文件，每个文件内部是key有序的，如何对这些文件进行合并，使得新生成的文件仍然Key有序，同时抛掉哪些不再有价值的KV 数据。

Major compaction的过程如下：对多个文件采用多路归并排序的方式，依次找出其中最小的Key记录，也就是对多个文件中的所有记录重新进行排序。之后采取一定的标准判断这个Key是否还需要保存，如果判断没有保存价值，那么直接抛掉，如果觉得还需要继续保存，那么就将其写入level L+1层中新生成的一个SSTable文件中。就这样对KV数据一一处理，形成了一系列新的L+1层数据文件，之前的L层文件和L+1层参与compaction 的文件数据此时已经没有意义了，所以全部删除。这样就完成了L层和L+1层文件记录的合并过程。

那么在major compaction过程中，判断一个KV记录是否抛弃的标准是什么呢？其中一个标准是：对于某个key来说，如果在小于L层中存在这个Key，那么这个KV在major compaction过程中可以抛掉。因为我们前面分析过，对于层级低于L的文件中如果存在同一Key的记录，那么说明对于Key来说，有更新鲜的Value存在，那么过去的Value就等于没有意义了，所以可以删除。

Redis 缓存有什么问题？

当我们将 Redis 拿来做缓存用时，背后肯定还有一个持久层数据库记录了全量的冷热数据。Redis 和持久层数据库之间的数据一致性是由应用程序自己来控制的。应用程序会优先去缓存中获取数据，当缓存中没有数据时，应用程序需要从持久层加载数据，然后再放进缓存中。当数据更新发生时，需要将缓存置为失效。

function getUser(String userId) User {

User user = redis.get(userId);

if user == null {

user = db.get(userId);

if user != null {

redis.set(userId, user);

}

}

return user;

}

function updateUser(String userId, User user) {

db.update(userId, user);

redis.expire(userId);}

有过这方面开发经验的朋友们就知道写这样的代码还是挺繁琐的，所有的涉及到缓存的业务代码都需要加上这一部分逻辑。

严格来说我们还需要仔细考虑缓存一致性问题，比如在 updateUser 方法中，数据库正确执行了更新，但是缓存 redis 因为网络抖动等原因置为失效没有成功，那么缓存中的数据就成了过期数据。如果你将设置缓存和更新持久存的先后顺序反过来，也还是会有其它问题，这个读者可以自行思考一下。

在多进程高并发场合也会导致缓存不一致，比如一个进程对某个 userId 调用 getUser() 方法，因为缓存里没有，它需要从数据库里加载。结果刚刚加载出来，正准备要设置缓存，这时候发生了内存 fullgc 代码暂停了一会，而正在此时另一个进程调用了 updateUser 方法更新了数据库，将缓存置为失效（其实缓存里本来就没有数据）。然后前面那个进程终于 fullgc 结束要开始设置缓存了，这时候进缓存的就是过期的数据。

LevelDB是如何解决的？

LevelDB 将 Redis 缓存和持久层合二为一，一次性帮你搞定缓存和持久层。有了 LevelDB，你的代码可以简化成下面这样

function getUser(String userId) User {

return leveldb.get(userId);}function updateUser(String userId, User user) {

leveldb.set(userId, user);}

而且你再也不用当心缓存一致性问题了，LevelDB 的数据更新要么成功要么不成功，不存在中间薛定谔状态。LevelDB 的内部已经内置了内存缓存和持久层的磁盘文件，用户完全不用操心内部是数据如何保持一致的。

关注小编,小编会每天为你分享有趣的技术文章哦。偷偷告诉你私信小编“学习”会有意想不到的惊喜哟~~!

"

文章来源: https://www.toutiao.com/group/6720024032067977740/