LevelDB源碼分析之十一：cache
ShardedLRUCache封裝了16個(gè)LRUCache緩存片，每次對(duì)緩存的讀取、插入、查找、刪除操作都是調(diào)用某個(gè)緩存片LRUCache中的相應(yīng)方法完成。
LRUCache為一個(gè)循環(huán)雙向鏈表，與標(biāo)準(zhǔn)實(shí)現(xiàn)一致。其“頭結(jié)點(diǎn)”lru_的prev始終指向最新結(jié)點(diǎn)，next始終指向最久未用節(jié)點(diǎn)，其對(duì)象容器為HashTable（哈希表），用于為L(zhǎng)RUCache提供快速的查找操作。
LRUHandle為結(jié)點(diǎn)類。其next_hash指針用于HashTable中的bucket單向鏈表 。next和prev指針用于LRUCache循環(huán)雙向鏈表的后繼和前驅(qū)。
他們之間的關(guān)系如下圖所示：
關(guān)于HashTable可以參考：哈希表（Hash Table）
關(guān)于LRUCache可以參考：LRU Cache原理和實(shí)現(xiàn)
一.Cache接口類
class Cache;
// 創(chuàng)建Cache的全局方法，capacity為容量大小
extern Cache* NewLRUCache(size_t capacity);
class Cache {
public:
Cache() { }
virtual ~Cache();
// 表示結(jié)點(diǎn)的結(jié)構(gòu)體
struct Handle { };
// 插入鍵值對(duì)，并指定占用的緩存大小（charge），返回被插入的結(jié)點(diǎn)。
// 如果插入的鍵值對(duì)用不到了，傳給deleter函數(shù)。
// 如果返回值用不到了，記得調(diào)用this->Release(handle)釋放。
virtual Handle* Insert(const Slice& key, void* value, size_t charge,
void (*deleter)(const Slice& key, void* value)) = 0;
// 如果沒(méi)找到結(jié)點(diǎn)，返回NULL。否則返回找到的結(jié)點(diǎn)。
// 如果返回值用不到了，記得調(diào)用this->Release(handle)釋放。
virtual Handle* Lookup(const Slice& key) = 0;
// 釋放結(jié)點(diǎn)，注意不要重復(fù)釋放。
virtual void Release(Handle* handle) = 0;
// 返回結(jié)點(diǎn)handle中的Value值，注意判斷handle的有效性。
virtual void* Value(Handle* handle) = 0;
// 刪除包含key的結(jié)點(diǎn)
virtual void Erase(const Slice& key) = 0;
// 返回?cái)?shù)字ID，用于處理多線程同時(shí)訪問(wèn)緩存時(shí)的同步
virtual uint64_t NewId() = 0;
private:
void LRU_Remove(Handle* e);
void LRU_Append(Handle* e);
void Unref(Handle* e);
struct Rep;
Rep* rep_;
// No copying allowed
Cache(const Cache&);
void operator=(const Cache&);
};
struct LRUHandle {
void* value;
void (*deleter)(const Slice&, void* value);//刪除器。當(dāng)refs == 0時(shí)，調(diào)用deleter完成value對(duì)象釋放。
LRUHandle* next_hash; // 作為HashTable中的節(jié)點(diǎn)，指向hash值相同的節(jié)點(diǎn)（解決hash沖突采用鏈地址法）
LRUHandle* next; // 作為L(zhǎng)RUCache中的節(jié)點(diǎn)，指向后繼
LRUHandle* prev; // 作為L(zhǎng)RUCache中的節(jié)點(diǎn)，指向前驅(qū)
size_t charge; // 用戶指定占用緩存的大小
size_t key_length; // key長(zhǎng)度
uint32_t refs; // 引用計(jì)數(shù)
uint32_t hash; // 哈希值
char key_data[1]; // key內(nèi)容的起始位置
Slice key() const {
// For cheaper lookups, we allow a temporary Handle object
// to store a pointer to a key in "value".
if (next == this) {
return *(reinterpret_cast(value));
} else {
return Slice(key_data, key_length);
}
}
}; 關(guān)于char key_data[1]，在LevelDB源碼分析之五：skiplist（1）這篇博客中又類似用法。key_data位于結(jié)構(gòu)體的最后面，可在申請(qǐng)內(nèi)存時(shí)，申請(qǐng)足夠多的空間。?
往下面看會(huì)看到這句：
LRUHandle* e = reinterpret_cast(
malloc(sizeof(LRUHandle)-1 + key.size())); 三.HashTable
LRUCache的實(shí)現(xiàn)并為用C++標(biāo)準(zhǔn)庫(kù)內(nèi)置的哈希表，用的是自己實(shí)現(xiàn)的哈希表。
class HandleTable {
public:
HandleTable() : length_(0), elems_(0), list_(NULL) { Resize(); }
~HandleTable() { delete[] list_; }
LRUHandle* Lookup(const Slice& key, uint32_t hash) {
return *FindPointer(key, hash);
}
LRUHandle* Insert(LRUHandle* h) {
LRUHandle** ptr = FindPointer(h->key(), h->hash);
LRUHandle* old = *ptr;
h->next_hash = (old == NULL ? NULL : old->next_hash);
// 不管找沒(méi)找到h結(jié)點(diǎn)，都是可以直接將h替換到*ptr的。
// 1.如果找到了，因?yàn)閗ey相同，直接替換相當(dāng)于替換結(jié)點(diǎn)中的value
// 2.如果沒(méi)找到，直接替換是理所當(dāng)然的了
*ptr = h;
//如果沒(méi)找到，相當(dāng)于要添加了一個(gè)新的結(jié)點(diǎn)，此時(shí)結(jié)點(diǎn)總數(shù)elems_加1
if (old == NULL) {
++elems_;
if (elems_ > length_) {
// Since each cache entry is fairly large, we aim for a small
// average linked list length (<= 1).
// 當(dāng)elems_ > length_時(shí)進(jìn)行擴(kuò)容，這樣可以保證在大部分情況下，所有以哈希地址為頭的
// 鏈表平均最多只有一個(gè)結(jié)點(diǎn)。因?yàn)榻Y(jié)點(diǎn)比較大，擴(kuò)容后能保證查找的時(shí)間復(fù)制度為O(1)。
Resize();
}
}
// 將old返回很重要，因?yàn)檫@個(gè)被摘到的handle需要在函數(shù)外面銷毀。
return old;
}
// 刪除結(jié)點(diǎn)，比較簡(jiǎn)單
LRUHandle* Remove(const Slice& key, uint32_t hash) {
LRUHandle** ptr = FindPointer(key, hash);
LRUHandle* result = *ptr;
if (result != NULL) {
*ptr = result->next_hash;
--elems_;
}
return result;
}
private:
// The table consists of an array of buckets where each bucket is
// a linked list of cache entries that hash into the bucket.
uint32_t length_; //哈希地址數(shù)組的長(zhǎng)度
uint32_t elems_; //哈希表中所有結(jié)點(diǎn)的總數(shù)
LRUHandle** list_; //哈希地址數(shù)組的二級(jí)指針
// Return a pointer to slot that points to a cache entry that
// matches key/hash. If there is no such cache entry, return a
// pointer to the trailing slot in the corresponding linked list.
// 如果找到了結(jié)點(diǎn)，返回該結(jié)點(diǎn)的二級(jí)指針。
// 如果沒(méi)找到結(jié)點(diǎn)，分兩種情況:
// 1.根據(jù)哈希值求出的哈希地址是空的，也就是說(shuō)以該哈希地址（哈希桶）為頭的單鏈表
// 還沒(méi)有結(jié)點(diǎn)。hash & (length_ - 1)的取值范圍是0—（length_-1）。此時(shí)返回
// 哈希地址的二級(jí)指針，*ptr=NULL 。
// 2.查找到了以某哈希地址為頭的單鏈表的尾部，也沒(méi)找到該結(jié)點(diǎn)。此時(shí)返回
// 尾部結(jié)點(diǎn)next_hash域的二級(jí)指針，*ptr=NULL 。
LRUHandle** FindPointer(const Slice& key, uint32_t hash) {
LRUHandle** ptr = &list_[hash & (length_ - 1)];
while (*ptr != NULL &&
((*ptr)->hash != hash || key != (*ptr)->key())) {
ptr = &(*ptr)->next_hash;
}
return ptr;
}
// 哈希表擴(kuò)容
// HandleTable內(nèi)部維護(hù)了一個(gè)LRUHandle*的數(shù)組，默認(rèn)大小為4。隨著插入數(shù)據(jù)的增多，
// 該數(shù)組會(huì)自動(dòng)增長(zhǎng)一倍，并將原數(shù)組中的數(shù)據(jù)重新分配到新的數(shù)組中。
void Resize() {
uint32_t new_length = 4;
while (new_length < elems_) {
new_length *= 2;
}
LRUHandle** new_list = new LRUHandle*[new_length];
memset(new_list, 0, sizeof(new_list[0]) * new_length);
uint32_t count = 0;
// 需要注意的是，從新分配結(jié)點(diǎn)的時(shí)候，結(jié)點(diǎn)都往每個(gè)鏈表的頭部插入的。
// 而正常的Insert操作，相同hash值的結(jié)點(diǎn)是插入到鏈表的尾部
for (uint32_t i = 0; i < length_; i++) {
LRUHandle* h = list_[i];
while (h != NULL) {
LRUHandle* next = h->next_hash;
Slice key = h->key();
uint32_t hash = h->hash;
LRUHandle** ptr = &new_list[hash & (new_length - 1)];
h->next_hash = *ptr;
*ptr = h;
h = next;
count++;
}
}
assert(elems_ == count);
delete[] list_;
list_ = new_list;
length_ = new_length;
}
};四.LRUCache
LRUCache::LRUCache()
: usage_(0),
last_id_(0) {
// Make empty circular linked list
// 創(chuàng)建空的循環(huán)鏈表
lru_.next = &lru_;
lru_.prev = &lru_;
}
LRUCache::~LRUCache() {
for (LRUHandle* e = lru_.next; e != &lru_; ) {
LRUHandle* next = e->next;
// 如果不為1，說(shuō)明LRUCache的使用者并未主動(dòng)調(diào)用Release或Erase方法。
// 因?yàn)槌跏嫉囊糜?jì)數(shù)為2，調(diào)用Release或Erase時(shí)，引用計(jì)數(shù)會(huì)減一。
assert(e->refs == 1);
Unref(e);
e = next;
}
}
// 引用計(jì)數(shù)減一。引用計(jì)數(shù)變?yōu)?時(shí)，調(diào)用刪除器deleter。
void LRUCache::Unref(LRUHandle* e) {
assert(e->refs > 0);
e->refs--;
if (e->refs <= 0) {
usage_ -= e->charge;
(*e->deleter)(e->key(), e->value);
free(e);
}
}
void LRUCache::LRU_Remove(LRUHandle* e) {
e->next->prev = e->prev;
e->prev->next = e->next;
}
void LRUCache::LRU_Append(LRUHandle* e) {
// Make "e" newest entry by inserting just before lru_
e->next = &lru_;
e->prev = lru_.prev;
e->prev->next = e;
e->next->prev = e;
}
// 根據(jù)LRUCache規(guī)則，被訪問(wèn)的結(jié)點(diǎn)要移動(dòng)到雙向鏈表的lru_結(jié)點(diǎn)之前
// 移動(dòng)只是改變了結(jié)點(diǎn)前驅(qū)指針和后繼指針的指向，結(jié)點(diǎn)的存儲(chǔ)位置并沒(méi)變化
// 返回被找到的結(jié)點(diǎn)，如果沒(méi)找到，返回NULL
Cache::Handle* LRUCache::Lookup(const Slice& key, uint32_t hash) {
? MutexLock l(&mutex_);
? LRUHandle* e = table_.Lookup(key, hash);
? if (e != NULL) {
? ? e->refs++;// 這里為何要加一，后面會(huì)說(shuō)到
? ? LRU_Remove(e);
? ? LRU_Append(e);
? }
? // 如果返回值不為NULL且用不到了，記得調(diào)用Relese或Erase釋放。
? return reinterpret_cast(e);
}
// 釋放結(jié)點(diǎn)
void LRUCache::Release(Cache::Handle* handle) {
MutexLock l(&mutex_);
Unref(reinterpret_cast(handle));
}
Cache::Handle* LRUCache::Insert(
const Slice& key, uint32_t hash, void* value, size_t charge,
void (*deleter)(const Slice& key, void* value)) {
MutexLock l(&mutex_);
LRUHandle* e = reinterpret_cast(
malloc(sizeof(LRUHandle)-1 + key.size()));
e->value = value;
e->deleter = deleter;
e->charge = charge;
e->key_length = key.size();
e->hash = hash;
// 初始設(shè)為2，一個(gè)是給LRUCache自身析構(gòu)時(shí)用，一個(gè)是給外部調(diào)用Release或Erase時(shí)用。
e->refs = 2;
memcpy(e->key_data, key.data(), key.size());
LRU_Append(e);
usage_ += charge;
// 當(dāng)哈希表中已存在hash值相同的結(jié)點(diǎn)時(shí)，將原有的結(jié)點(diǎn)從雙向鏈表中移除，
// 并釋放該結(jié)點(diǎn)。
// 這里不需要調(diào)用哈希表的Remove方法將該結(jié)點(diǎn)從哈希表中移除，因?yàn)镮nsert
// 的時(shí)候?qū)嶋H上已經(jīng)移除了。
// 這段代碼也可以看出為何哈希表的Insert方法要返回舊結(jié)點(diǎn)？因?yàn)椴环祷嘏f
// 結(jié)點(diǎn)，后續(xù)就無(wú)法對(duì)該結(jié)點(diǎn)進(jìn)行LRU_Remove操作了。
LRUHandle* old = table_.Insert(e);
if (old != NULL) {
LRU_Remove(old);
Unref(old);
}
// 如果已用容量超過(guò)了總?cè)萘壳翌^結(jié)點(diǎn)lru_還有后繼。
// 刪除lru_的后繼結(jié)點(diǎn)，根據(jù)LRUCache規(guī)則，這個(gè)結(jié)點(diǎn)最近用的最少。
// 該結(jié)點(diǎn)既要從哈希表中移除，也要從雙向鏈表中移除，然后再釋放。
while (usage_ > capacity_ && lru_.next != &lru_) {
LRUHandle* old = lru_.next;
LRU_Remove(old);
table_.Remove(old->key(), old->hash);
Unref(old);
}
// 返回新插入的結(jié)點(diǎn)，LRUCache的使用者需要主動(dòng)調(diào)用該結(jié)點(diǎn)的Relese或Erase方法來(lái)釋放結(jié)點(diǎn)。
return reinterpret_cast(e);
}
// 刪除結(jié)點(diǎn)，注意和Release方法的不同。刪除結(jié)點(diǎn)先將結(jié)點(diǎn)從哈希表和
// 雙向鏈表中移除，然后再釋放該結(jié)點(diǎn)。
void LRUCache::Erase(const Slice& key, uint32_t hash) {
MutexLock l(&mutex_);
LRUHandle* e = table_.Remove(key, hash);
if (e != NULL) {
LRU_Remove(e);
Unref(e);
}
} 在Insert時(shí)，引用計(jì)數(shù)初始化為2，一個(gè)是給LRUCache自身析構(gòu)時(shí)用，一個(gè)是給外部調(diào)用Release或Erase時(shí)用。Insert時(shí)，返回的是新插入的結(jié)點(diǎn)，插入完成后，需要調(diào)用該結(jié)點(diǎn)Release或Erase方法將引用計(jì)數(shù)減1，那么此時(shí)該結(jié)點(diǎn)的引用計(jì)數(shù)就是1了。在LRUCache析構(gòu)時(shí)，會(huì)先將結(jié)點(diǎn)的引用計(jì)數(shù)再減1，如果此時(shí)引用計(jì)數(shù)為0，則調(diào)用deleter，并將該結(jié)點(diǎn)徹底從內(nèi)存中free。
在Lookup時(shí)，如果查找接結(jié)點(diǎn)存在，此時(shí)引用計(jì)數(shù)會(huì)加1，也即是變成了3。此時(shí)，在用戶持有該結(jié)點(diǎn)的期間，該緩存可能被刪除（多種原因，如：超過(guò)緩存容量觸發(fā)回收、具有相同key的新緩存插入、整個(gè)緩存被析構(gòu)等），導(dǎo)致用戶訪問(wèn)到非法內(nèi)存，程序崩潰。因此，需要使用引用計(jì)數(shù)要加1來(lái)維護(hù)結(jié)點(diǎn)的生命周期。因?yàn)長(zhǎng)ookup返回的是找到的結(jié)點(diǎn)，用戶在查找完成后，要主動(dòng)調(diào)用該結(jié)點(diǎn)的Release或Erase來(lái)使引用計(jì)數(shù)從新變成2。
2.LRUHandle為什么會(huì)被同時(shí)置于哈希表和雙向鏈表之中？
注意看LookUp的實(shí)現(xiàn)，如果單純使用鏈表，則僅能提供O(n)的查詢效率，所以在查詢時(shí)，利用了哈希表實(shí)現(xiàn)O(1)的查詢。
那么，如果單純使用哈希表呢？雖然可以實(shí)現(xiàn)O(1)的查詢，但卻無(wú)法更新緩存節(jié)點(diǎn)的訪問(wèn)時(shí)間。這是因?yàn)殒湵砜梢园凑展潭ǖ捻樞虮槐闅v，而哈希表中的節(jié)點(diǎn)無(wú)法提供固定的遍歷順序（考慮Resize前后）。
那么，可不可以將訪問(wèn)時(shí)間記錄在Handle中，然后僅用哈希表，這樣既可以實(shí)現(xiàn)O(1)的查詢，又可以方便地更新緩存記錄的訪問(wèn)時(shí)間，豈不美哉？但是，如果沒(méi)有按訪問(wèn)時(shí)間排序的鏈表，當(dāng)觸發(fā)緩存回收時(shí)，我們?nèi)绾慰焖俣ㄎ坏侥男┚彺嬗涗浺换厥漳兀?br />
鏈表O(n)的查詢效率、哈希表不支持排序，兩種數(shù)據(jù)結(jié)構(gòu)單獨(dú)都無(wú)法滿足這里的需求。作者大神巧妙地將二者結(jié)合，取長(zhǎng)補(bǔ)短，利用哈希表實(shí)現(xiàn)O(1)的查詢，利用鏈表維持對(duì)緩存記錄按訪問(wèn)時(shí)間排序
注1：哈希表實(shí)現(xiàn)O(1)操作的前提是：平均每哈希桶元素?cái)?shù) <= 1
注2：為了保持平均哈希桶元素?cái)?shù)，必要時(shí)必須Resize，而Resize后，原有順序?qū)⒈淮蚱?br />
五.ShardedLRUCache
static const int kNumShardBits = 4;
static const int kNumShards = 1 << kNumShardBits;
class ShardedLRUCache : public Cache {
?private:
? // 16片LRUCache緩存
? LRUCache shard_[kNumShards];
? port::Mutex id_mutex_;
? uint64_t last_id_;
? // 使用哈希函數(shù)求出哈希值
? static inline uint32_t HashSlice(const Slice& s) {
? ? return Hash(s.data(), s.size(), 0);
? }
? // 取哈希值的高四位來(lái)定位使用那片LRUCache緩存
? static uint32_t Shard(uint32_t hash) {
? ? return hash >> (32 - kNumShardBits);
? }
?public:
? // capacity是Cache大小，其單位可以自行指定（如table cache，一個(gè)sstable文件的索引信息是一個(gè)單位，
? // 而block cache，一個(gè)byte是一個(gè)單位）
? explicit ShardedLRUCache(size_t capacity)
? ? ? : last_id_(0) {
? ? const size_t per_shard = (capacity + (kNumShards - 1)) / kNumShards;
? ? for (int s = 0; s < kNumShards; s++) {
? ? ? shard_[s].SetCapacity(per_shard);
? ? }
? }
? virtual ~ShardedLRUCache() { }
? virtual Handle* Insert(const Slice& key, void* value, size_t charge,
? ? ? ? ? ? ? ? ? ? ? ? ?void (*deleter)(const Slice& key, void* value)) {
? ? const uint32_t hash = HashSlice(key);
? ? return shard_[Shard(hash)].Insert(key, hash, value, charge, deleter);
? }
? virtual Handle* Lookup(const Slice& key) {
? ? const uint32_t hash = HashSlice(key);
? ? return shard_[Shard(hash)].Lookup(key, hash);
? }
? virtual void Release(Handle* handle) {
? ? LRUHandle* h = reinterpret_cast(handle);
? ? shard_[Shard(h->hash)].Release(handle);
? }
? virtual void Erase(const Slice& key) {
? ? const uint32_t hash = HashSlice(key);
? ? shard_[Shard(hash)].Erase(key, hash);
? }
? // 返回handle結(jié)點(diǎn)的value值
? virtual void* Value(Handle* handle) {
? ? return reinterpret_cast(handle)->value;
? }
? // 返回?cái)?shù)字ID，用于處理多線程同時(shí)訪問(wèn)緩存時(shí)的同步
? virtual uint64_t NewId() {
? ? MutexLock l(&id_mutex_);
? ? return ++(last_id_);
? }
}; SharedLRUCache到底是什么呢？我們?yōu)槭裁葱枰窟@是因?yàn)閘evelDB是多線程的，每個(gè)線程訪問(wèn)緩沖區(qū)的時(shí)候都會(huì)將緩沖區(qū)鎖住，為了多線程訪問(wèn)，盡可能快速，減少鎖開(kāi)銷，ShardedLRUCache內(nèi)部有16個(gè)LRUCache，查找Key時(shí)首先計(jì)算key屬于哪一個(gè)分片，分片的計(jì)算方法是取32位hash值的高4位，然后在相應(yīng)的LRUCache中進(jìn)行查找，這樣就大大減少了多線程的訪問(wèn)鎖的開(kāi)銷。這種設(shè)計(jì)思路，非常值得我輩學(xué)習(xí)，致敬大神。
六.cache的使用
為了加快查找速度，LevelDB在內(nèi)存中采用Cache的方式，在table中采用bloom filter的方式，盡最大可能加快隨機(jī)讀操作。LevelDB的Cache分為兩種，分別是table cache和block cache。
1.table cache
table cache緩存的是table的索引數(shù)據(jù)，類似于文件系統(tǒng)中對(duì)inode的緩存。table cache默認(rèn)大小是1000，注意此處緩存的是1000個(gè)table文件的索引信息，而不是1000個(gè)字節(jié)。table cache的大小由options.max_open_files確定，其最小值為20-10，最大值為50000－10。
2.block cache
block cache是緩存的block數(shù)據(jù)，block是table文件內(nèi)組織數(shù)據(jù)的單位，也是從持久化存儲(chǔ)中讀取和寫(xiě)入的單位。由于table是按照key有序分布的，因此一個(gè)block內(nèi)的數(shù)據(jù)也是按照key緊鄰排布的（有序依照使用者傳入的比較函數(shù)，默認(rèn)按照字典序），類似于Linux中的page cache。
block默認(rèn)大小為4k，由LevelDB調(diào)用open函數(shù)打開(kāi)數(shù)據(jù)庫(kù)時(shí)時(shí)傳入的options.block_size參數(shù)指定。LevelDB的代碼中限制的block最小大小為1k，最大大小為4M。對(duì)于頻繁做scan操作的應(yīng)用，可適當(dāng)調(diào)大此參數(shù)，對(duì)大量小value隨機(jī)讀取的應(yīng)用，也可嘗試調(diào)小該參數(shù)。
block cache默認(rèn)實(shí)現(xiàn)是一個(gè)8M大小的ShardedLRUCache，此參數(shù)由options.block_cache設(shè)定。當(dāng)然也可根據(jù)應(yīng)用需求，提供自定義的緩存策略。注意，此處的大小是未壓縮的block大小。
參考鏈接：https://www.jianshu.com/p/9e7773432772
參考鏈接：http://www.360doc.com/content/14/0325/16/15064667_363619144.shtml
下載文檔
