Level DB --- Cache

class Cache是Level DB中的重要的数据结构，它是一个LRU（Least Recently Used） Cache的实现。这里面的判断条件主要是内存大小（而不是存储entry的个数）。当内存达到上界，会释放不被使用的entry（存储到lru_中的entry）。

HandleTable 

说到class Cache先说class Handle Table，它是Level DB作者实现的一个hash map，对于相同哈希值碰撞，Handle Table使用了链地址法---即相同的hash值组成了一个链表，它要比C++ STL中的hash map快5%，同时，Handle Table不是一个通用的hash map，它是定制化LRUHandle（Cache中使用的结构体）使用的hash map，这也是它效率高的一个原因。

                                                                   图1. Handle Table

核心函数

LRUHandle** FindPointer(const Slice& key, uint32_t hash) {//hash & (length_ - 1)，计算slot，ptr是hash值相同链表的head pointerLRUHandle** ptr = &list_[hash & (length_ - 1)];//遍历链表，寻找查询的key-valuewhile (*ptr != nullptr && ((*ptr)->hash != hash || key != (*ptr)->key())) {ptr = &(*ptr)->next_hash;}return ptr;
}

//检索 key & hash 的 pointer
LRUHandle* Lookup(const Slice& key, uint32_t hash)//插入新的entry
LRUHandle* Insert(LRUHandle* h)//删除key & value 的 pointer
LRUHandle* Remove(const Slice& key, uint32_t hash) //当插入的key的数量达到一定的值，为了保证效率，会重新扩大slots（list_）的数量，
//slots数量增加，重新hash，每个slot的链表也会变小，加快链表遍历检索的效率
//这里为了进一步加快效率，我们也可以定义自己的Resize触发条件
void Resize()

Cache

Handle

Handle是Cache计算的entry句柄，它既存在于hash table中，也存在于双向链表（Least Recently Used由双向链表实现）中，它的嵌入方式如图2所示。

                                                             图2. LRU Handle

Handle在hash table中的组织形式如图1所示，在双向链表中的组织形式如图3所示。

                                                                图3. 双向链表

添加与删除

对于从双向链表中做删除操作很简单，只需要将重置handle的pre和next指针，如图4所示。

                                                                 图4. 双向链表删除handle

void LRUCache::LRU_Remove(LRUHandle* e) {e->next->prev = e->prev;e->prev->next = e->next;
}

对于从双向链表中插入，需要插入到双向链表的head，如图5所示

                                                           图5. 双向链表插入handle

void LRUCache::LRU_Append(LRUHandle* list, LRUHandle* e) {// Make "e" newest entry by inserting just before *liste->next = list;e->prev = list->prev;e->prev->next = e;e->next->prev = e;
}

当内存达到上限的时候，将会循环从lru_中list next开始删除，如图6所示

                            图6. 当内存导到上限，逐个删除lru_中的least recently used handle

while (usage_ > capacity_ && lru_.next != &lru_) {LRUHandle* old = lru_.next;assert(old->refs == 1);bool erased = FinishErase(table_.Remove(old->key(), old->hash));if (!erased) {  // to avoid unused variable when compiled NDEBUGassert(erased);}
}

lru_ 和 in_use_

在设计上，Cache 用了2个双向链表lru_和in_use_，这么设计主要是从计算效率上考虑。当一个新的handle会存储到in_use_中，当这个handle被删除，它会转移到lru_中。而当这个handle需要再次被只用，就可以从lru_重新插入到in_use_，而不需要重新申请资源。

当需要释放资源的时候，直接从lru_中删除。

GUARDED_BY 

#define GUARDED_BY(x) THREAD_ANNOTATION_ATTRIBUTE__(guarded_by(x))
#define THREAD_ANNOTATION_ATTRIBUTE_(x) __attribute__((x))

所以

#define GUARDED_BY(x) __attribute__((x))(guarded_by(x))

编译器会确保在访问特定变量之前必须先锁定相应的互斥量（mutex），从而防止多个线程同时访问该变量，导致数据竞争和不一致的问题‌。等于在编译的时候就做了临界区域的保护提醒。

代码中的EXCLUSIVE_LOCKS_REQUIRED也同理。

ShardedLRUCache

ShardedLRUCache，是用来进一步提升Cache的性能，因为Cache里面有临界区域影响了并发写，ShardedLRUCache等于是又做了一次分桶，用来提升并发写。