levelDB中的LRU

https://www.jianshu.com/p/9e7773432772

在諸多的Cache政策中，LRUCache（Least Recently Used，最近最少被使用）因為完美地契合了局部性原理，故而成為最常見的Cache政策。而Cache算法的設計與實作，也是面試中經常會遇到的問題。

下面，讓我們來看一下LevelDB中的LRUCache實作。

單條緩存記錄：LRUHandle

（LRUHandle是Hash表中存儲的一個元素，存儲了prev、next等資訊，維護了一個雙向連結清單，next_hash是當Hash沖突時哈希桶中的多個元素用連結清單維護）

23 // An entry is a variable length heap-allocated structure.  Entries
 24 // are kept in a circular doubly linked list ordered by access time.
 25 struct LRUHandle {
 26   void* value;
 27   void (*deleter)(const Slice&, void* value);
 28   LRUHandle* next_hash;
 29   LRUHandle* next;
 30   LRUHandle* prev;
 31   size_t charge;      // TODO(opt): Only allow uint32_t?
 32   size_t key_length;
 33   uint32_t refs;
 34   uint32_t hash;      // Hash of key(); used for fast sharding and comparisons
 35   char key_data[1];   // Beginning of key
...
 46 };

LevelDB是一個Key/Value存儲庫，所緩存的資料自然是Key/Value對，26/32/35行用以存儲kv對。*這裡有一點困惑，key_data 為什麼是 char[1]，而不直接使用 char*? *

當回收一條緩存記錄時，27行中的deleter将被調用，以callback的形式通知緩存使用者，一條資料被移出緩存。這裡Slice是key類型，姑且認為是string，不影響接下來的了解。

31行的charge用來儲存每條緩存記錄的容量，當所有緩存記錄的容量和超過緩存總容量時，最近最少被使用的緩存記錄将被回收。

32行用以維護引用計數。

重點看下28/29/30/34行，28/34行暗示出緩存記錄将被置于哈希表中，29/30行暗示出緩存記錄将被置于雙向連結清單中。

存疑一：LRUHandle為什麼會被同時置于哈希表和雙向連結清單之中呢？（問題驅動，這種學習方法很好）

哈希表：HandleTable

48 // We provide our own simple hash table since it removes a whole bunch
 49 // of porting hacks and is also faster than some of the built-in hash
 50 // table implementations in some of the compiler/runtime combinations
 51 // we have tested.  E.g., readrandom speeds up by ~5% over the g++
 52 // 4.4.3's builtin hashtable.
 53 class HandleTable {
 54  public:
 55   HandleTable() : length_(0), elems_(0), list_(NULL) { Resize(); }
 56   ~HandleTable() { delete[] list_; }
 57 
 58   LRUHandle* Lookup(const Slice& key, uint32_t hash) {
 59     return *FindPointer(key, hash);
 60   }
 61 
 62   LRUHandle* Insert(LRUHandle* h) {
 63     LRUHandle** ptr = FindPointer(h->key(), h->hash);
 64     LRUHandle* old = *ptr;
 65     h->next_hash = (old == NULL ? NULL : old->next_hash);
 66     *ptr = h;
 67     if (old == NULL) {
 68       ++elems_;
 69       if (elems_ > length_) {
 70         // Since each cache entry is fairly large, we aim for a small
 71         // average linked list length (<= 1).
 72         Resize();
 73       }
 74     }
 75     return old;
 76   }
 77  
 78   LRUHandle* Remove(const Slice& key, uint32_t hash) {
 79     LRUHandle** ptr = FindPointer(key, hash);
 80     LRUHandle* result = *ptr;
 81     if (result != NULL) {
 82       *ptr = result->next_hash;
 83       --elems_;
 84     }
 85     return result;
 86   }
 87 
 88  private:
 89   // The table consists of an array of buckets where each bucket is
 90   // a linked list of cache entries that hash into the bucket.
 91   uint32_t length_;
 92   uint32_t elems_;
 93   LRUHandle** list_;

LookUp用以查找給定記錄是否存在，Remove用以删除一條記錄，Insert用以插入/更新一條記錄，如果是更新操作，還會傳回舊記錄。

**為什麼不區分插入和更新操作? **

因為對于緩存寫者而言，TA不知道也不關心資料是否在緩存中，TA隻是盡可能地将TA認為近期會被通路到的資料寫入緩存。這裡Insert命名不好，幂等操作用Put更好。（若key不存在，直接插入一個kv對，如果key存在，修改相應的kv對）

存疑二：Insert操作為什麼傳回舊緩存記錄？（75 行 return old）

95   // Return a pointer to slot that points to a cache entry that
 96   // matches key/hash.  If there is no such cache entry, return a
 97   // pointer to the trailing slot in the corresponding linked list.
 98   LRUHandle** FindPointer(const Slice& key, uint32_t hash) {
 99     LRUHandle** ptr = &list_[hash & (length_ - 1)];
100     while (*ptr != NULL &&
101            ((*ptr)->hash != hash || key != (*ptr)->key())) {
102       ptr = &(*ptr)->next_hash;
103     }
104     return ptr;
105   }

哈希表的實作中，FindPointer傳回一個指向next_hash的指針ptr，而該next_hash指向所找到的緩存記錄，有了ptr，就可以直接修改next_hash的指向，達到添加/删除連結清單節點的目的。而我都是通過儲存目前節點與前置節點兩個一級指針來完成上述操作的，遠沒有作者對指針的了解深刻。

107   void Resize() {
108     uint32_t new_length = 4;
109     while (new_length < elems_) {
110       new_length *= 2;
111     }
112     LRUHandle** new_list = new LRUHandle*[new_length];
113     memset(new_list, 0, sizeof(new_list[0]) * new_length);
114     uint32_t count = 0;
115     for (uint32_t i = 0; i < length_; i++) {
116       LRUHandle* h = list_[i];
117       while (h != NULL) {
118         LRUHandle* next = h->next_hash;
119         uint32_t hash = h->hash;
120         LRUHandle** ptr = &new_list[hash & (new_length - 1)];
121         h->next_hash = *ptr;
122         *ptr = h;
123         h = next;
124         count++;
125       }
126     }
127     assert(elems_ == count);
128     delete[] list_;
129     list_ = new_list;
130     length_ = new_length;
131   }

Resize()操作實作記憶體自動增長，用以保證哈希桶中的單連結清單的平均長度 <= 1，進而保證添删查操作O(1)的時間複雜度。

LRUCache

134 // A single shard of sharded cache.
135 class LRUCache {
136  public:
137   LRUCache();
138   ~LRUCache();
139 
140   // Separate from constructor so caller can easily make an array of LRUCache
141   void SetCapacity(size_t capacity) { capacity_ = capacity; }
142 
143   // Like Cache methods, but with an extra "hash" parameter.
144   Cache::Handle* Insert(const Slice& key, uint32_t hash,
145                         void* value, size_t charge,
146                         void (*deleter)(const Slice& key, void* value));
147   Cache::Handle* Lookup(const Slice& key, uint32_t hash);
148   void Release(Cache::Handle* handle);
149   void Erase(const Slice& key, uint32_t hash);
150   void Prune();
151   size_t TotalCharge() const {
152     MutexLock l(&mutex_);
153     return usage_;
154   }
155 
156  private:
157   void LRU_Remove(LRUHandle* e);
158   void LRU_Append(LRUHandle* e);
159   void Unref(LRUHandle* e);
160 
161   // Initialized before use.
162   size_t capacity_;
163 
164   // mutex_ protects the following state.
165   mutable port::Mutex mutex_;
166   size_t usage_;
167 
168   // Dummy head of LRU list.
169   // lru.prev is newest entry, lru.next is oldest entry.
170   LRUHandle lru_;
171 
172   HandleTable table_;
173 };

SetCapacity用以設定緩存容量，當容量溢出時，觸發回收邏輯。

LRUCache同時維護了一個雙向連結清單（LRUList）和一個哈希表（HandleTable），LRUList中按通路時間排序緩存記錄，prev從最近到最久，next反之。

另外，注意一下Insert和LookUp的傳回值， Cache::Handle的定義如下：

40   // Opaque handle to an entry stored in the cache.
 41   struct Handle { };

我曾多次在API文檔中見過opaque handle的字樣，但一直不解其意。直到現在才明白，所謂的opaque handle其角色類似于基類指針，隐藏實作細節，每個實作者需要提供自己的實作，如Handle之于LRUHandle。

175 LRUCache::LRUCache()
176     : usage_(0) {
177   // Make empty circular linked list
178   lru_.next = &lru_;
179   lru_.prev = &lru_;
180 }
181 
182 LRUCache::~LRUCache() {
183   for (LRUHandle* e = lru_.next; e != &lru_; ) {
184     LRUHandle* next = e->next;
185     assert(e->refs == 1);  // Error if caller has an unreleased handle
186     Unref(e);
187     e = next;
188   }
189 }
190 
191 void LRUCache::Unref(LRUHandle* e) {
192   assert(e->refs > 0);
193   e->refs--;
194   if (e->refs <= 0) {
195     usage_ -= e->charge;
196     (*e->deleter)(e->key(), e->value);
197     free(e);
198   }
199 }

為什麼維護引用計數？

讀取資料時，使用者首先從緩存中查找欲讀的資料是否存在，如果存在，使用者将獲得命中緩存的Handle。在使用者持有該Handle的期間，該緩存可能被删除（多種原因，如：超過緩存容量觸發回收、具有相同key的新緩存插入、整個緩存被析構等），導緻使用者通路到非法記憶體，程式崩潰。是以，需要使用引用計數來維護Handle的生命周期。

201 void LRUCache::LRU_Remove(LRUHandle* e) {
202   e->next->prev = e->prev;
203   e->prev->next = e->next;
204 }
205 
206 void LRUCache::LRU_Append(LRUHandle* e) {
207   // Make "e" newest entry by inserting just before lru_
208   e->next = &lru_;
209   e->prev = lru_.prev;
210   e->prev->next = e;
211   e->next->prev = e;
212 }
213 
214 Cache::Handle* LRUCache::Lookup(const Slice& key, uint32_t hash) {
215   MutexLock l(&mutex_);
216   LRUHandle* e = table_.Lookup(key, hash);
217   if (e != NULL) {
218     e->refs++;
219     LRU_Remove(e);
220     LRU_Append(e);
221   }
222   return reinterpret_cast<Cache::Handle*>(e);
223 }

注意看LookUp的實作，如果單純使用連結清單，則僅能提供O(n)的查詢效率，是以在查詢時，利用了哈希表實作O(1)的查詢。

那麼，如果單純使用哈希表呢？雖然可以實作O(1)的查詢，但卻無法更新緩存節點的通路時間（218-220行）。這是因為連結清單可以按照固定的順序被周遊，而哈希表中的節點無法提供固定的周遊順序（考慮Resize前後）。

有的讀者可能會想，可不可以将通路時間記錄在Handle中，然後僅用哈希表，這樣既可以實作O(1)的查詢，又可以友善地更新緩存記錄的通路時間，豈不美哉？但是，如果沒有按通路時間排序的連結清單，當觸發緩存回收時，我們如何快速定位到哪些緩存記錄要被回收呢？（僅在Handle中存時間的話，每次LRU淘汰需要排序）

回答疑問一：LRUHandle為什麼會被同時置于哈希表和雙向連結清單之中呢？

查詢	插入	删除	有序
連結清單	O(n)	O(1)	O(1)	支援
哈希表	O(1)	O(1)	O(1)	不支援

注1：哈希表實作O(1)操作的前提是：平均每哈希桶元素數 <= 1

注2：為了保持平均哈希桶元素數，必要時必須Resize，而Resize後，原有順序将被打破

連結清單O(n)的查詢效率、哈希表不支援排序，兩種資料結構單獨都無法滿足這裡的需求。作者巧妙地将二者結合，取長補短，利用哈希表實作O(1)的查詢，利用連結清單維持對緩存記錄按通路時間排序。

230 Cache::Handle* LRUCache::Insert(
231     const Slice& key, uint32_t hash, void* value, size_t charge,
232     void (*deleter)(const Slice& key, void* value)) {
233   MutexLock l(&mutex_);
234 
235   LRUHandle* e = reinterpret_cast<LRUHandle*>(
236       malloc(sizeof(LRUHandle)-1 + key.size()));
237   e->value = value;
238   e->deleter = deleter;
239   e->charge = charge;
240   e->key_length = key.size();
241   e->hash = hash;
242   e->refs = 2;  // One from LRUCache, one for the returned handle
243   memcpy(e->key_data, key.data(), key.size());
244   LRU_Append(e);
245   usage_ += charge;
246 
247   LRUHandle* old = table_.Insert(e);
248   if (old != NULL) {
249     LRU_Remove(old);
250     Unref(old);
251   }
252 
253   while (usage_ > capacity_ && lru_.next != &lru_) {
254     LRUHandle* old = lru_.next;
255     LRU_Remove(old);
256     table_.Remove(old->key(), old->hash);
257     Unref(old);
258   }
259 
260   return reinterpret_cast<Cache::Handle*>(e);
261 }

Insert操作是整個LRUCache實作的核心。

235-243行：申請記憶體，存儲使用者資料
244行：将該緩存記錄插入到雙向連結清單中的最新端
245行：計算已使用容量
247-251行：如果是更新操作，回收舊記錄，回答了疑問二：Insert操作為什麼傳回舊緩存記錄？（HandleTable ::Insert是單純地插入到hash表中，如果是更新，需要從連結清單中删除掉舊的KV，是以傳回old kv用于在連結清單中删除）
253-258行：已用容量超過總量，回收最近最少被使用的緩存記錄。

總結

一個小小的LRUCache實作，不僅使用了引用計數技術來管理記憶體，還巧妙地結合了哈希表和雙向連結清單兩種資料結構的優勢，達到性能與功能的完美結合。

levelDB中的LRU

單條緩存記錄：LRUHandle

哈希表：HandleTable

LRUCache

總結

繼續閱讀

Codeforces 1417 D. Make Them Equal(思維+構造)

查找算法之二分查找查找算法之二分查找

查找算法學習之二分查找（Python版本）——BinarySearch

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

Command Network(POJ 3164)---定根最小樹形圖模闆題題目描述輸入格式輸出格式輸入樣例輸出樣例分析源程式

開源低帶寬語音編解碼器

241 Different Ways to Add Parentheses（C代碼版）

【趨高機器視覺】機器視覺技術原了解析及解決方案

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制規程及特點4． CSMA/CD協定5． CSMA/CD的優點6．結束語

極大似然法(ML)與最大期望法(EM)

C++ 第十五周報告1--《冒泡法排序》

筆試面試題目：滑動視窗(二)

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

hdu7108哈希