LRU

除了利用哈希表来存储数据以外，leveldb还利用LRU来管理数据。

Leveldb中，LRU利用一个双向循环链表来实现。每一个链表项称之为LRUNode。

type lruNode struct {
    n   *Node // customized node
    h   *Handle
    ban bool
 
    next, prev *lruNode
}

一个LRUNode除了维护一些链表中前后节点信息以外，还存储了一个哈希表中数据项的指针，通过该指针，当某个节点由于LRU策略被驱逐时，从哈希表中“安全的”删除数据内容。

LRU提供了以下几个接口：

• Promote

若一个hash表中的节点是第一次被创建，则为该节点创建一个LRUNode，并将LRUNode至于链表的头部，表示为最新的数据；

若一个hash表中的节点之前就有相关的LRUNode存在与链表中，将该LRUNode移至链表头部；

若因为新增加一个LRU数据，导致超出了容量上限，就需要根据策略清除部分节点。

• Ban

将hash表节点对应的LRUNode从链表中删除，并“尝试”从哈希表中删除数据。

由于该哈希表节点的数据可能被其他线程正在使用，因此需要查看该数据的引用计数，只有当引用计数为0时，才可以真正地从哈希表中进行删除。