HashCrack程序數(shù)據(jù)及索引設(shè)計(jì)2
上個(gè)月寫了《HashCrack程序數(shù)據(jù)及索引設(shè)計(jì)》里面已經(jīng)提到早期設(shè)計(jì)的幾種存儲(chǔ)方法，最后達(dá)到了每條記錄15個(gè)字節(jié)左右的水平，但這個(gè)存儲(chǔ)效果還是很差的，而且是單體文件，受制于內(nèi)存限制，后來又設(shè)計(jì)了幾種復(fù)合索引格式，支持1萬億記錄一個(gè)復(fù)合索引，下面簡(jiǎn)單講講之后的研究成果。
6、將內(nèi)容區(qū)和索引區(qū)合并，索引位置不再提供指向內(nèi)容區(qū)的size_t，內(nèi)容區(qū)不再需要，直接在索引區(qū)，這樣索引區(qū)indexnode
Struct indexnode
{
Size_t nextoffset;
Char str[0];
};
經(jīng)過此修改之后稍微不好的地方就是如果一個(gè)文件里面要管理不同長(zhǎng)度的字符串那么只能取最長(zhǎng)的字符串長(zhǎng)度，以便indexnode保持相同大小容易索引。
這種方法雖然效果不錯(cuò)，但平均下來一個(gè)字符串還是要占用11個(gè)左右的字節(jié)，而且不同長(zhǎng)度的字符串有一些浪費(fèi)的地方。
7、以上的存儲(chǔ)方法雖然已經(jīng)比較緊湊，但還不是最緊湊的方法，如果不保存字符串只是保存字符串在序列中的位置，那么不同字符串也沒有長(zhǎng)度不同，也可以用同樣的大小去保存，如果一個(gè)db保存42億以下的字符串，那么只要4個(gè)字節(jié)就可以了，如果一個(gè)db保存1萬億以下的數(shù)據(jù)，那么只要5個(gè)字節(jié)就可以，這真是個(gè)非常有創(chuàng)意的想法，其實(shí)我當(dāng)初想到這個(gè)想法的時(shí)候很擔(dān)心計(jì)算效率，遲遲沒有動(dòng)手代碼，但思考了幾天之后打消了我對(duì)效率的擔(dān)心，相反，只保存一個(gè)position比復(fù)制N個(gè)字符串可能還要快一點(diǎn)，這樣我們就只要9個(gè)字節(jié)描述indexnode了，看定義：
Struct indexnode
{
Size_t lpos;
Byte hpos;
Size_t nextoffset;
};
精確到9個(gè)字節(jié)表示一條記錄，很不錯(cuò)，也沒有更多的限制。事實(shí)上9字節(jié)版本的速度比方法6的確是要快一點(diǎn)，還沒優(yōu)化的時(shí)候就比6方法要快一些了，當(dāng)然查詢的時(shí)候由于要多計(jì)算一些信息，理論上是要慢一點(diǎn)的，但由于都是內(nèi)存計(jì)算，其實(shí)影響不是很大。
8、上述9個(gè)字節(jié)的方法雖然已經(jīng)很緊湊，但如果給nextoffset做一點(diǎn)限制，讓一個(gè)區(qū)段的數(shù)據(jù)為1667w以下，那么描述nextoffset 只需要3個(gè)字節(jié)即可，這樣indexnode總的長(zhǎng)度就只需要8個(gè)字節(jié)，這真是很好的想法，我為這個(gè)想法驕傲，看下indexnode的8字節(jié)版本
Struct indexnode
{
Size_t lpos;
Size_t hpos:8;
Size_t nextoffset:24;
};
精確的8字節(jié)indexnode，如此我們最終實(shí)現(xiàn)了最緊湊的md5數(shù)據(jù)庫，每條記錄8個(gè)字節(jié)，幾乎無法再減少了，期待哪天突然靈光閃現(xiàn)再創(chuàng)造出更緊湊的存儲(chǔ)方法吧，呵呵，這個(gè)實(shí)現(xiàn)其實(shí)已經(jīng)超越了我最初的估計(jì)了，我以為能減少到12個(gè)字節(jié)已經(jīng)到頂了，沒想到還能減少到8個(gè)字節(jié)。
8字節(jié)的版本最初寫出來的時(shí)候效率下降得很厲害，因?yàn)橐郧?/span>nextoffset當(dāng)指針用，現(xiàn)在3個(gè)字節(jié)無法當(dāng)指針，只能轉(zhuǎn)換，多一個(gè)轉(zhuǎn)換函數(shù)效率下降了一些，其他地方剛寫的時(shí)候也是非優(yōu)化算法，所以第一個(gè)8字節(jié)版本效率比9字節(jié)降低了一半以上，但花了一個(gè)早上優(yōu)化之后效率又上去了，現(xiàn)在制造復(fù)合索引只需要82秒就可完成1億條記錄，速度比方法6快不少，方法6需要120秒左右。
或許我講得比較簡(jiǎn)單，如果不是深入研究這一塊的人或許看不明白，但精華我基本上講出來了，實(shí)現(xiàn)上其實(shí)有很多技巧，如果要做到象我一樣的速度其實(shí)是需要很深功力的，我測(cè)試用的機(jī)器是朋友的入門級(jí)服務(wù)器E5504 2.0cpu，4G內(nèi)存，普通7200轉(zhuǎn)硬盤。