网站设计尺寸规范,无锡网站建设818gx,上海网站备案在哪里,个人网站上线流程class Cache是Level DB中的重要的数据结构#xff0c;它是一个LRU#xff08;Least Recently Used#xff09; Cache的实现。这里面的判断条件主要是内存大小#xff08;而不是存储entry的个数#xff09;。当内存达到上界#xff0c;会释放不被使用的entry#xff08;存…class Cache是Level DB中的重要的数据结构它是一个LRULeast 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它是定制化LRUHandleCache中使用的结构体使用的hash map这也是它效率高的一个原因。 图1. Handle Table
核心函数
LRUHandle** FindPointer(const Slice key, uint32_t hash) {//hash (length_ - 1)计算slotptr是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的数量达到一定的值为了保证效率会重新扩大slotslist_的数量
//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等于是又做了一次分桶用来提升并发写。
