這一節關注TC中的hash數據庫如何根據一個key查找到該key所在的record,因為后續的刪除,插入記錄都是以查找為基礎的,所以首先描述這部分內容.
從上一節的
概述中,可以看到record結構體中有兩個成員left,right:
typedef struct { // type of structure for a record
uint64_t off; // offset of the record
uint32_t rsiz; // size of the whole record
uint8_t magic; // magic number
uint8_t hash; // second hash value
uint64_t left; // offset of the left child record
uint64_t right; // offset of the right child record
uint32_t ksiz; // size of the key
uint32_t vsiz; // size of the value
uint16_t psiz; // size of the padding
const char *kbuf; // pointer to the key
const char *vbuf; // pointer to the value
uint64_t boff; // offset of the body
char *bbuf; // buffer of the body
} TCHREC;
說明,每個record是存放在一個類二叉樹的結構中的.
實際上,TC會首先根據一個record的key去算出該key所在的bucket index以及hash index,代碼如下:
/* Get the bucket index of a record.
`hdb' specifies the hash database object.
`kbuf' specifies the pointer to the region of the key.
`ksiz' specifies the size of the region of the key.
`hp' specifies the pointer to the variable into which the second hash value is assigned.
The return value is the bucket index. */
static uint64_t tchdbbidx(TCHDB *hdb, const char *kbuf, int ksiz, uint8_t *hp){
assert(hdb && kbuf && ksiz >= 0 && hp);
uint64_t idx = 19780211;
uint32_t hash = 751;
const char *rp = kbuf + ksiz;
while(ksiz--){
idx = idx * 37 + *(uint8_t *)kbuf++;
hash = (hash * 31) ^ *(uint8_t *)--rp;
}
*hp = hash;
return idx % hdb->bnum;
}
需要特別提醒的一點是,上面的算法中,根據key算出所在的bucket index,是經過模TCHDB->bnum之后的結果,也就是說,這個值是有限制的---最大不能超過TCHDB初始化時得到的bucket最大數量;而算出的二級hash值,我是沒有看出來有數值上的限制的,為什么?看了后面的內容就明白了.
因此,所有根據記錄的key算出bucket index相同的記錄全都以二叉樹的形式組織起來,而每個bucket array元素存放的整型值就是該bucket樹根所在記錄的offset.
到此,相關的結構體聯系都清楚了,下面的流程圖給出了查找一個key的記錄是否存在的流程:
簡單的解釋一下,這個查找的流程就是首先根據查找的key算出所在的bucket,然后在這個bucket的二叉樹中按照條件遍歷的過程.
前面提到過,bucket array是整個被mmap映射到共享內存中去的.我們來做一個估計,假設存放bucket array的內存使用了1G,而真正存放record的文件長度有16G,也就是,bucket array的元素與記錄大概是1:16的關系,假設所選的hash算法足夠的好,以至于每個記錄的key可以較為平均的分布在不同的bucket index上,也就是每個bucket array的元素組成的二叉樹上平均有16個元素,那么也就最多需要O(4)次讀取文件I/O(每次去讀取記錄的數據都是一次讀磁盤操作) + O(1)次內存讀操作(因為需要在bucket array中得到樹根元素的offset).
但是等等,上面還有一些細節沒有交待清楚.
首先,上面的二叉樹不是類似AVL,紅黑樹這樣的平衡二叉查找樹,也就是說,很可能在極端的情況下演變成一個鏈表---樹的一邊沒有元素,另一邊有全部的元素.
其次,上面的流程圖中還有一點就是每次比較首先比較的是hash值,這個值的奧秘就在于解決上面提到的那個問題.既然只是一個普通的二叉樹,無法保證平衡,那么就通過算出這個二級的hash值來保證平衡---當然,前提依然是所選擇的hash算法足夠的好,可以保證key平均的分布.
前面提到過,非平衡的二叉樹只會在極端的情況下才會演變為一個極端不平衡的二叉樹--鏈表,而諸如AVL,紅黑樹之類的平衡二叉樹,算法編碼都相對復雜,調試起來也麻煩,出錯了要跟進更麻煩,另外還別忘了,這些平衡二叉樹之所以能保持平衡,在刪除/增加元素時做的讓樹重新平衡的操作,比如旋轉等,都是要涉及到讀寫樹結點的,而這些,目前都是存放在磁盤上的---也就是這是相對較費時的操作,所以問題在于:是不是值得為這一個極端的情況去優化?另外,引入二級hash就是為了部分解決這個極端不平衡問題,它的思路簡單也容易實現,但是引入的另外一個問題就是每次查找時根據key去算bucket index的時候,還要耗費時間去算hash index了.
平衡點,還是平衡點.時間還是空間,這是一個問題.
所以,經過對TC的hash數據庫查找key流程的分析,最大的感受是:它沒有使用復雜的算法與數據結構,而是通過一些巧妙的優化如二級hash的引入,達到了系統效率和編碼調試復雜度之間一個較好的平衡.學會"平衡"各種因素,是做項目做事情,都要掌握的一個技能,而這個,只有多經歷多想才能慢慢積累了.
好了,簡單的回顧整個查找key的關鍵點:
1) 所有的record是以二叉樹的形式組織在同一個bucket上面的.
2) 這個二叉樹不是平衡的二叉樹
3) 為了解決問題二造成的極端不平衡問題,TC引入了二級hash,以保證這個二叉樹盡可能的平衡.
以上,就是TC對記錄,bucket的組織情況,以及整個查找算法的流程.可以看到,算法,結構體定義等等都不復雜,但是由于巧妙的構思,既可以使用盡可能簡單的算法/數據結構,又能規避可能出現的一些隱患,同時還能保證查找的高效率.
查找是key-value形式存儲的核心流程,能夠將這個流程優化,對整個系統的性能也有很大的影響.