HashCache：低內存緩存存儲系統

一個典型的緩存存儲（或KV存儲）有3部分組成：

1、內存過濾器（in-memory filter）用於在磁碟查詢前判斷Key的存在性。典型的演算法有：布隆過濾器（Bloom Filter）。

2、內存索引（in-memory index）用於在內存中索引磁碟數據的位置。演算法有：哈希表（Hash Table）、Cuckoo Hashing等。

3、磁碟存儲（on-flash data layout）用於Key Value持久化。演算法有：WAL（Write-ahead logging）、SSTable、B樹等。

由於磁碟容量增長遠大於內存（RAM）容量的增長，同時價格更便宜，所以緩存系統多是針對1，2步驟的優化，從而佔據更少的內存空間。本項目適用於對內存敏感的發展中國家，提出多種設計策略減少內存使用，極端情況下不使用內存索引同時又保持高性能存儲和查詢。

下面分段講述，從不使用內存空間到逐步優化實現。

HashCache-Basic

本演算法完全移除1，2的實現，只使用磁碟存儲。由此帶來2個問題：要查詢的Key的存在性和定位目標數據。本演算法視磁碟為一維的哈希表。

如圖所示，將磁碟的部分劃分為N等分，固定大小的bin，每個bin存儲一個對象（包含原始的Key Value）。當存儲對象時，取hash(key) % N定位到相應

的bin，然後寫入即可。當Hash碰撞時，直接複寫。當查詢時，相同的定位辦法，然後取出對象，進行Key比較，相等則返回Value。

有時對象大小要大於劃定的固定大小，需要將剩餘部分存入環形Log（circular log）中，此時bin中還需要存儲log的位置（offset），對象的大小。

演算法劣勢：Hash高碰撞，相同的Hash值的Key只能存儲一個。

HashCache-Set

參照內存Hash碰撞的解決策略，可以擴充HC-Basic為N路set關聯表，即每個bin現在包含S個元素，每個元素仍然包含對象大小，Key，Value，log的位置。如圖所示：

因為這些元素位置是臨近的，每次讀取S個元素稍微比讀一個元素多耗費時間。

演算法劣勢：當要查詢的元素不存在時，仍然需要1次磁碟查找。當set實現LRU演算法時，需要增加一次磁碟寫（更新最近使用）。

HC-SetMem

HC-Set緩存未命中（cache miss）問題，可以通過提供in-memory filter來實現。演算法如下：

1、提供一個二維數組，每一行對應HC-Set中的一個bin，N列對應N路關聯，每一個元素表示數據實體的H位Hash值。同時為了使用LRU緩存清理策略，需要每一個內存元素持有forward和reverse指針（設一個指針32位），故每一個內存對象需要佔據（H + 2 * 32）位。

2、由於每一個bin中的S個元素的餘數（%N）相等，即這些元素的Hash低（log(N)）位是相同的，因此可以移出。如此內存Hash對象需要（H+ 64 - log(N)）位。

3、LRU緩存清理需要在S位元素清理，即需要排名到S-1，只要log(S)位標記LRU演算法。如此內存對象需要（H+ log(S) - log(N)）位。

4、可以只為部分set關聯表保留in-memory filter。

演算法劣勢：每次緩存寫時，因為對象位置是由其Hash值決定，因此需要隨機定址（seek），當高頻率寫時，仍然是一個性能問題。

HC-Log

為了解決緩存寫隨機定址，可以是由傳統的緩存Log策略，即每次寫只是追加元素，這需要報每個對象的位置（offset）寫入內存對象中。同時保留HC-SetMem提供的內存對象策略，這樣可以保留緩存未命中磁碟讀解決問題。

參考文檔

1、HashCache: Cache Storage for the Next Billion。https://www.usenix.org/event/nsdi09/tech/full_papers/badam/badam.pdf

2、SILT: A Memory-Efficient, High-Performance Key-Value Store。

https://www.cs.cmu.edu/~hl/papers/silt-sosp2011.pdf

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！