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 pointer
LRUHandle** ptr = &list_[hash & (length_ - 1)];
//遍历链表，寻找查询的key-value
while (*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 *list
e->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 NDEBUG
assert(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等于是又做了一次分桶，用来提升并发写。
原文地址：https://blog.csdn.net/zhangsj1007/article/details/144317723
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！