簡單的Key - Value存儲系統原型 HashDB

HashDB是一個簡單的KeyValue存儲系統原型，提供基本的 二元組的數據存儲與讀取功能，亦即當前被廣為推崇的NoSQL存儲系統。最初想到設計這個小系統，完全是出于偶然。本人維護著一個輕量級的開源重復數據刪除小工具deduputil， 它基于塊級對文件目錄進行數據去重并進行打包，支持定長和變長數據分塊算法，并支持數據塊壓縮。deduputil使用hash數據指紋來區分和識別重復 數據塊，數據塊指紋采用hashtable進行存儲和查找，并完全置于內存中。假設，數據塊平均大小為4KB，數據塊對象屬性描述約需40字節，則存儲 8TB數據的指紋大約需要80GB內存，如此龐大的內存需求使得deduputil很難工作于普通的PC或服務器。因此決定對deduputil進行重 構，支持在內存有限的環境下進行大數據量的去重和打包，思想是讓指紋數據在內存與磁盤之間進行交換。最初想直接采用類似Tokyo Cabinet的NoSQL系統，后來發現這些系統遠遠比deduputil復雜，使用它們真是大材小用，而且使得deduputil對第三方軟件產生了 依賴。于是產生了設計一個簡單的KeyValue存儲系統的念頭，經過幾個晚上的奮戰，HashDB原型系統完成并成功應用于deduputil上，代碼 量不到1000行，非常非常輕量級。HashDB以較小的內存消耗達到支持超大hashtable，數據持久化存儲于文件中，并在內存與文件之間進行交 換。HashDB主要采用了hashtable, bloom filter, set-assocaite cache, file layout, btree等數據結構與算法，初步性能測試結果表明HashDB的性能基本還算不錯，已經比較接近Tokyo Cabinet的性能。HashDB源碼包含在deduputil中，可以從 http://sourceforge.net/projects/deduputil/獲得。 

2、基本原理

HashDB采用哈稀表 數據結構組織數據，以文件形式對數據進行持久化存儲，文件數據布局如下圖所示，由header, bloom filter, bucket array, hash entries四個部分組成。Header記錄HashDB的一些全局信息，比如總的記錄數、hash桶數、緩存記錄數以及它們在文件中的偏移 位置。Header持久化存儲在HashDB文件頭部，加載時需要首先讀取它，然后據此加載其他組成部分數據。Bloom filter是一個空間效率很高的數據結構，它由一個位數組和一組hash映射函數組成。Bloom filter可以用于檢索一個元素是否在一個集合中，它的優點是空間效率和查詢時間都遠遠超過一般的算法，缺點是有一定的誤識別率和刪除困難。這里主要利 用bloom filter來快速判斷給定Key是否存在于HashDB中，如果不存在則直接返回，存在則再進行文件I/O讀寫和Key精確查找，從而節省大量的I/O 和檢索開銷。bloom filter長度由最大支持記錄數決定，在創建HashDB時指定并保存在header中，一旦創建不可修改，下次啟動時從header中讀取并加載。

HashDB 以hashtable方式組織數據，桶數組長度在創建時指定，同樣以后不可修改。bucket array會遠遠小于記錄總數，一般平均桶長在10以上。通常情況下，桶中以鏈表方式組織產生沖突的記錄，查找時遍歷鏈表，當桶較長時順序查找效率較低。 HashDB桶中的記錄采用btree結合二次hash方法來組織，這點參考了Tokyo Cabinet。Btree實現簡單，查找時間復雜度為log(h)，但可能會發生二叉樹極度為平衡的情況，而平衡樹（如RB, B*, B-, B+樹）實現則較為復雜。二次hash方法，先比較hash值再比較關鍵字key，從而獲得較為平衡的btree。實踐表明，btree結合二次hash 的方法非常有效，可以大大提高檢索效率。Bucket array中記錄中對應桶的btree根結點偏移，以它為Root可以遍歷搜索整個hash桶。

Hash entries區域部分存儲了所有的KeyValue記錄，出于簡化設計實現考慮，每個記錄的大小固定，Key和Value都有最大長度限制，記錄以 Append方式增加，支持修改Key對應的Value值，目前沒有支持刪除操作。同一個桶中的記錄以btree方式組織，入口地址保存在bucket array中對應桶節點中。HashDB設計了Cache系統來提升性能，緩存的記錄數量通常約為總記錄數的10%，這也是采納了熱點數據的常見比率。 Cache管理算法采用類似計算機高速Cache的組相聯（Set-associative）算法，以hash為基礎進行記錄的換入和換出，即同一個桶中 的記錄會被cache到相同的cache項中。

HashDB 中，header, bloom filter, bucket array, hash entries四個部分持久化存儲于文件中，運行時header, bloom filter, bucket array完全緩存在內存中，cache則僅在運行時存在，這部分內存空間消耗是可以估算的。假設，總記錄數tnum=1000萬，hash桶數 bnum=100萬，緩存記錄數量cnum=100萬，每條記錄固定大小為1KB，則內存消耗=1000萬/8 + 100萬*8 + 100萬*1KB = 1.25MB + 8MB + 1GB。HashDB加載時，header, bloom filter, bucket array將從文件中讀取并載入內存，并讀取每個hash桶的第一個記錄對cache進行預熱。HashDB關閉時，內存中的所有臟數據將被寫回文件，記 錄數龐大時，這個過程會比較耗時。

HashDB目前還是一個很簡單的原型系統，沒有提供鎖機制，只能應用于單進程/線程模式。HashDB也沒有提供常駐系統服務（Daemon），僅提供如下幾個API進行訪問。詳細信息請參考hashdb.h & hashdb.c，簡單描述如下：
HASHDB *hashdb_new(uint64_t tnum, uint32_t bnum, uint32_t cnum, hashfunc_t hash_func1, hashfunc_t hash_func2);
創建一個新的HashDB對象，參數分別為總記錄數、hash桶數、緩存記錄數、兩個hash函數。

int hashdb_open(HASHDB *db, const char *path);
使 用HashDB對象打開文件，路徑由path指定。如果HashDB文件已經存在，則將header, bloom filter, bucket array載入內存，然后預讀記錄進行cache預熱；如果是新建HashDB，則根據hashdb_new輸入參數計算header結構各項參數值，然 后在文件中為header, bloom filter, bucket array預分配空間。 

int hashdb_close(HASHDB *db, int flash);
關閉HashDB，將緩存數據中的所有臟數據與加文件，并釋放內存空間。

int hashdb_set(HASHDB *db, char *key, void *value, int vsize);
設 置（寫入或更新）KeyValue記錄，參數分別為關鍵字、值以及value長度。pos = hash_func1(key) % cnum，計算出key對應的cache位置，如果該位置已經緩存記錄但不是當前記錄，則將該記錄換出內存（緩存狀態設置為未緩存）；如果沒有緩存并 bloom filter判斷記錄存在，則查找記錄并換入內存。然后，設置緩存記錄結構各項數據，對于新記錄需要設置bloom filter位狀態和緩存狀態。

int hashdb_get(HASHDB *db, char *key, void *value, int *vsize);
讀 取KeyValue記錄，參數分別為關鍵字、值緩沖區和值長度。pos = hash_func1(key) % cnum，計算出key對應的cache位置，如果bloom filter判斷該記錄不存在，則直接返回。如果該位置緩存記錄但不是當前記錄，則將該記錄換出內存；如果沒有緩存，則查找記錄并換入內存，然后復制 key對應的記錄值和值長度。

項目主頁：http://www.baiduhome.net/lib/view/home/1322745726671