LSM-Tree - LevelDb之LRU缓存
引言
LRU缓存在各种开源组件中都有使用的场景，常常用于做冷热数据和淘汰策略，使用LRU主要有三点。
- 第一点是实现非常简单。
- 第二点是代码量本身也不错。
- 最后涉及数据结构非常经典。
LevelDB对于LRU缓存实现算是比较经典的案例，这一节来介绍它是如何使用LRU实现缓存的。
LeetCode 中有一道相应LRU缓存算法的题目，感兴趣可以做一做：
lru-cache
理论
根据wiki的LRU缓存结构介绍，可以了解到缓存的基本淘汰策略过程，比如下面这张图的节点淘汰过程：
读取的顺序为 A B C D E D F，缓存大小为 4，括号内的数字表示排序，数字越小越靠后，表示 Least recently.
根据箭头的读取顺序，读取到E的时候，发现缓存已经满了，这时会淘汰最早的一个A(0)。
接下来继续读取并且更新排序，倒数第二次中发现D是最大的，而B是最小的，当读取F加入缓存之后，发现缓存已经是满的，此时发现相对于A之后插入的数值B访问次数最小，于是进行淘汰并且替换。
根据最少实用原则LRU 的实现需要两个数据结构：
- HashTable（哈希表）: 用于实现O(1)的查找。
- List: 存储
Least recently排序，用于旧数据的淘汰。
LevelDB实现
这里直接看LevelDB是如何应用这个数据结构的。
LevelDB的LRUCache设计有4个数据结构，是依次递进的关系，分别是：
- LRUHandle（LRU节点，也就是LRUNode）
- HandleTable（哈希表）
- LRUCache（关键，缓存接口标准和实现）
- ShardedLRUCache（用于提高并发效率）