開(kāi)始正式的研究key-value形式的持久化存儲(chǔ)方案了，第一個(gè)閱讀的項(xiàng)目是tokyo cabinet，版本號(hào)是1.4.19.
tokyo cabinet支持幾種數(shù)據(jù)庫(kù)形式，包括hash數(shù)據(jù)庫(kù)，B+樹(shù)數(shù)據(jù)庫(kù)，fix-length數(shù)據(jù)庫(kù)，table數(shù)據(jù)庫(kù)。目前我僅看了第一種hash數(shù)據(jù)庫(kù)的實(shí)現(xiàn)。之所以選擇這個(gè)，是因?yàn)榈谝贿@種類(lèi)型的數(shù)據(jù)庫(kù)似乎是TC中使用的最多的一種，其次它的算法比之B+樹(shù)又更簡(jiǎn)單一些而效率上的表現(xiàn)也絲毫不差。
看看TC中代碼的組織。關(guān)于上面幾個(gè)分類(lèi)的數(shù)據(jù)庫(kù)實(shí)現(xiàn)，實(shí)際上在TC項(xiàng)目的代碼組織中各自以單個(gè)文件的形式出現(xiàn)，比如hash數(shù)據(jù)庫(kù)的代碼全都集中在 tchdb.c/h中，也只不過(guò)4000多行罷了。除去這幾種數(shù)據(jù)庫(kù)的實(shí)現(xiàn)文件，其余的代碼文件功能可以大體上分為兩類(lèi)，一類(lèi)是輔助性質(zhì)的代碼，給項(xiàng)目中各個(gè)部分使用上的，另一部分就是單獨(dú)的管理數(shù)據(jù)庫(kù)的CLI程序的代碼，比如tchmgr.c/h就是用于管理HASH數(shù)據(jù)庫(kù)的CLI程序的代碼。之所以要交代一下項(xiàng)目中代碼的組織，無(wú)非是為了說(shuō)明，其實(shí)如果將問(wèn)題集中在HASH數(shù)據(jù)庫(kù)或者其他形式的數(shù)據(jù)庫(kù)實(shí)現(xiàn)上，起碼在TC中，所要關(guān)注的代碼是不多的。
首先來(lái)看數(shù)據(jù)庫(kù)文件是如何組織的。
從圖中可以看到，hash數(shù)據(jù)庫(kù)文件大致分為四個(gè)部分：數(shù)據(jù)庫(kù)文件頭，bucket 數(shù)組，free pool數(shù)組，最后的是真正存放record的部分。下面對(duì)這幾部分做一個(gè)說(shuō)明。
1）數(shù)據(jù)庫(kù)文件頭
數(shù)據(jù)庫(kù)文件頭部分存放的是關(guān)于該數(shù)據(jù)庫(kù)的一些總體信息，包括這些內(nèi)容：
| name |
offset |
length |
feature |
| magic number |
0 |
32 |
identification of the database. Begins with "ToKyO CaBiNeT" |
| database type |
32 |
1 |
hash (0x01) / B+ tree (0x02) / fixed-length (0x03) / table (0x04) |
| additional flags |
33 |
1 |
logical union of open (1<<0) and fatal (1<<1) |
| alignment power |
34 |
1 |
the alignment size, by power of 2 |
| free block pool power |
35 |
1 |
the number of elements in the free block pool, by power of 2 |
| options |
36 |
1 |
logical union of large (1<<0), Deflate (1<<1), BZIP2 (1<<2), TCBS (1<<3), extra codec (1<<4) |
| bucket number |
40 |
8 |
the number of elements of the bucket array |
| record number |
48 |
8 |
the number of records in the database |
| file size |
56 |
8 |
the file size of the database |
| first record |
64 |
8 |
the offset of the first record |
| opaque region |
128 |
128 |
users can use this region arbitrarily |
需要說(shuō)明的是，上面這個(gè)表格來(lái)自tokyocabinet的官方文檔說(shuō)明，在
這里。同時(shí)，數(shù)據(jù)庫(kù)文件中需要存放數(shù)據(jù)的地方，使用的都是小端方式存放的，以下就不再就這點(diǎn)做說(shuō)明了。從上面的表格可以看出，數(shù)據(jù)庫(kù)文件頭的尺寸為256 bytes。
在操作hash數(shù)據(jù)庫(kù)的所有API中，都會(huì)用到一個(gè)對(duì)象類(lèi)型為T(mén)CHDB的指針，該結(jié)構(gòu)體中存放的信息就包括了所有數(shù)據(jù)庫(kù)文件頭的內(nèi)容，所以每次在打開(kāi)或者創(chuàng)建一個(gè)hash數(shù)據(jù)庫(kù)的時(shí)候，都會(huì)將數(shù)據(jù)庫(kù)文件頭信息讀入到這個(gè)指針中（函數(shù)tchdbloadmeta）。
2）bucket 數(shù)組
bucket array中的每個(gè)元素都是一個(gè)整數(shù)，按照使用的是32位還是64位系統(tǒng)，存放的也就是32位或者64位的整數(shù)。這個(gè)數(shù)組存放的這個(gè)整數(shù)值，就是每次對(duì) key 進(jìn)行hash之后得到的hash值所對(duì)應(yīng)的第一個(gè)元素在數(shù)據(jù)庫(kù)文件中的偏移量。
3）free pool數(shù)組
free pool數(shù)組中的每個(gè)元素定義結(jié)構(gòu)體如下：
typedef struct { // type of structure for a free block
uint64_t off; // offset of the block
uint32_t rsiz; // size of the block
} HDBFB;
很明顯，僅有兩個(gè)成員，一個(gè)存放的是在數(shù)據(jù)庫(kù)文件中的偏移量，一個(gè)則是該free block的尺寸。free pool數(shù)組用于保存那些被刪除的記錄信息，以便于回收利用這些數(shù)據(jù)區(qū)，后續(xù)會(huì)針對(duì)free pool相關(guān)的操作，API做一個(gè)詳細(xì)的分析。
4）record數(shù)據(jù)區(qū)
每個(gè)record數(shù)據(jù)區(qū)的結(jié)構(gòu)如下表：
| name |
offset |
length |
feature |
| magic number |
0 |
1 |
identification of record block. always 0xC8 |
| hash value |
1 |
1 |
the hash value to decide the path of the hash chain |
| left chain |
2 |
4 |
the alignment quotient of the destination of the left chain |
| right chain |
6 |
4 |
the alignment quotient of the destination of the right chain |
| padding size |
10 |
2 |
the size of the padding |
| key size |
12 |
vary |
the size of the key |
| value size |
vary |
vary |
the size of the value |
| key |
vary |
vary |
the data of the key |
| value |
vary |
vary |
the data of the value |
| padding |
vary |
vary |
useless data |
當(dāng)然，上面這個(gè)結(jié)構(gòu)只是該record被使用時(shí)的結(jié)構(gòu)圖，當(dāng)某一項(xiàng)record被刪除時(shí)，它的結(jié)構(gòu)就變?yōu)椋?br>
| name |
offset |
length |
feature |
| magic number |
0 |
1 |
identification of record block. always 0xB0 |
| block size |
1 |
4 |
size of the block |
對(duì)比兩種情況，首先是最開(kāi)始的magic number是不同的，當(dāng)magic number是0XB0也就是該record是已經(jīng)被刪除的free record時(shí)，那么緊跟著的4個(gè)字節(jié)存放的就是這個(gè)free record的尺寸，而record后面的部分可以忽略不計(jì)了。
分析完了hash數(shù)據(jù)庫(kù)文件的幾個(gè)組成部分，從最開(kāi)始的數(shù)據(jù)庫(kù)文件示意圖中還看到，從文件頭到bucket array這一部分將通過(guò)mmap映射到系統(tǒng)的共享內(nèi)存中，當(dāng)然，可以映射的內(nèi)容可能不止到這里，但是，數(shù)據(jù)庫(kù)文件頭+bucket array這兩部分是一定要映射到共享內(nèi)存中的，也就是說(shuō)，hash數(shù)據(jù)庫(kù)中映射到共享內(nèi)存中的內(nèi)容上限沒(méi)有限制，但是下限是文件頭+bucket array部分。
同時(shí)，free pool也會(huì)通過(guò)malloc分配一個(gè)堆上的內(nèi)存，存放到TCHDB的fbpool指針中。
這幾部分（除了record zone），通過(guò)不同的方式都分別的讀取到內(nèi)存中，目的就是為了加快查找的速度，后面會(huì)詳細(xì)的進(jìn)行說(shuō)明。