在读取一个key的值时，leveldb会按照如下顺序查找这个key：
- 在memtable中查询
- 在level0中查询
- 在level1中查询
- 。。。(依次查询更高level的文件)
一旦在memtable或者某个level中查找到了这个key，就不在需要去更高level查询了。
在memtable中读取数据是内存操作，性能不需要担心。但是在level0到level6的文件中读取数据需要进行磁盘io，速度会比较慢。因此，leveldb使用了缓存。
使用缓存来提升性能是很常见的手段，这属于常规操作。这里主要关注两个问题：
- leveldb的缓存是怎么设计的。
- 高level的文件可能会非常大，比如几G或者十几G，leveldb的缓存是怎么处理这样的大文件的。
leveldb使用LRU策略来淘汰缓存。LRU策略比较简单，它的实现一般是由一个hashtable+一个链表组成，当访问某个key之后，需要在链表中提升整个key的位置，操作链表时需要加锁来防止竞争。相比这种简单的LRU模型，levedb实现的LRUcache有两个不同的地方：
- 使用了分片cache来降低锁的粒度。
- 在每个lru cache实例内部，使用了两个链表，避免了频繁的提升操作。
主要的几个类及它们的关系如图：
cache.png
这两个改进都在一定程度上提高了cache的访问性能。将cache分片，每个cache使用一把锁，而不是全部的cache使用同一把锁，可以降低对锁的争抢。当前分片数是16，也就是说，这个cache模型允许16并发的访问。
使用in_use_list来记录正在被访问的cache entry，并使用引用计数来统计有多少线程正在使用这个entry。当entry为1时，才进行一次提升操作，即把此条entry移动到lru_list的头部。当容量超过限制时，从lru_list的尾部开始删除数据。 在这个机制下，如果某些key被频繁的访问，它们会维持在in_use_list中，而不需要频繁的进行提升操作。
关于第二个问题，leveldb没有缓存整个文件的内容，而是缓存了文件的元信息，以及部分数据block。sst文件的格式如文档中描述，数据被组织成一个个block，每个block的大小在4k左右。level以block为单位缓存文件中的数据，并将所有的block放在一个单独的缓存池中。也就是说，leveldb使用了两个ShardedLRUCache实例来缓存sst文件：
- 一个用于缓存sst文件的元信息
- 一个用于缓存sst文件中的block数据
这个思路很直白：文件太大了没法缓存，就缓存文件的一部分数据。两个缓存的大小都是可以配置的，如果需要较高的读取性能，可以将block缓存的大小设置大一点，目前默认是8M。
总结
主要亮点在于LRU的分片以及in_use_list的使用。
网友评论