文章目錄

• • 前言
  • 引擎背景
  • 引擎原理
  • • 1. 磁盤(pán)數(shù)據(jù)結(jié)構(gòu)
    • 2. 內(nèi)存數(shù)據(jù)結(jié)構(gòu)
    • 3. 讀流程
    • 4. 數(shù)據(jù)合并
  • 總結(jié)

前言

最近工作中部分項(xiàng)目中，對(duì)存儲(chǔ)引擎的需求希望高性能的寫(xiě)、點(diǎn)查，并不需要Range。這里看到大家總會(huì)提到BitCask這個(gè)存儲(chǔ)引擎方案，并不是很了解，特此做一個(gè)總體的學(xué)習(xí)記錄。

引擎背景

BitCask 是分布式數(shù)據(jù)庫(kù)Riak有存儲(chǔ)引擎上的一些需求，但是當(dāng)時(shí)(2010年左右)業(yè)界并沒(méi)有一個(gè)能夠滿(mǎn)足需求的引擎，包括但不限于Berkeley DB, Tokyo Cabinet, Innostore等。所以BitCask便應(yīng)運(yùn)而生，主要為了解決以下一些需求：

• 讀/寫(xiě) 的低延時(shí)
• 隨機(jī)寫(xiě)場(chǎng)景下的高吞吐
• 支持?jǐn)?shù)據(jù)量遠(yuǎn)大于內(nèi)存的持久化存儲(chǔ)
• 異常恢復(fù)機(jī)制，能夠快速recovery且不丟數(shù)據(jù)
• 便捷得數(shù)據(jù)備份機(jī)制
• 支持易理解的數(shù)據(jù)結(jié)構(gòu)
• 大并發(fā)/大數(shù)據(jù)量下的引擎穩(wěn)定性保障
• 支持平滑遷移到Riak

除了最后一條定制化需求之外，對(duì)于今天我們的存儲(chǔ)引擎來(lái)說(shuō)其實(shí)都是一些最基本的需求，因?yàn)闆](méi)有強(qiáng)Range性能需求，所以這一些基本要求也是可以理解的，無(wú)非就是引擎的穩(wěn)定性和性能。然而，當(dāng)時(shí)業(yè)界并沒(méi)有這樣的一個(gè)存儲(chǔ)引擎，所以Riak的開(kāi)發(fā)者們也就只能擼起袖子自己搞了。google的bigtable中提出的LSM-tree對(duì)讀性能并不友好，所以也不滿(mǎn)足。

因?yàn)闆](méi)有Range,他們便從hash數(shù)據(jù)結(jié)構(gòu)入手來(lái)提供O(1)的點(diǎn)查，由借鑒了Log-Structure Merged 數(shù)據(jù)結(jié)構(gòu)中的log-merging思想，來(lái)提供強(qiáng)大的寫(xiě)入性能。

引擎原理

1. 磁盤(pán)數(shù)據(jù)結(jié)構(gòu)

BitCask磁盤(pán)數(shù)據(jù)結(jié)構(gòu)非常簡(jiǎn)單，一個(gè)BitCask實(shí)例就是一個(gè)文件系統(tǒng)目錄。需要保證同一時(shí)刻只有一個(gè)進(jìn)程會(huì)訪(fǎng)問(wèn)這個(gè)目錄，進(jìn)程寫(xiě)入的數(shù)據(jù)更新僅僅會(huì)落在一個(gè)Active data file中，當(dāng)這個(gè)文件達(dá)到了一個(gè)給定的閾值，會(huì)創(chuàng)建一個(gè)新的active data file，而之前的接受寫(xiě)入的文件會(huì)被標(biāo)記為只讀。

進(jìn)程寫(xiě)入key/value到active data file的過(guò)程時(shí)追加寫(xiě)方式，也就是類(lèi)似于一個(gè)文件writer，這個(gè)過(guò)程會(huì)轉(zhuǎn)化成磁盤(pán)上的順序?qū)?#xff0c;所以寫(xiě)入性能肯定會(huì)很高。

每一個(gè)磁盤(pán)上的entry數(shù)據(jù)格式如下：

• crc : 當(dāng)前entry的數(shù)據(jù)校驗(yàn)

• tstamp: 時(shí)間戳

• ksz: key size

• value_sz : value size

• key : key的內(nèi)容

• value : value的內(nèi)容

如果想要?jiǎng)h除數(shù)據(jù)，也是寫(xiě)入一個(gè)deletion的 tombstone標(biāo)記，后續(xù)的log-merging會(huì)清理。

所以，每一個(gè)磁盤(pán)上的datafile 中的entry最后都追加成這樣的形態(tài)：

2. 內(nèi)存數(shù)據(jù)結(jié)構(gòu)

之前說(shuō)了，bitcask保證低延時(shí)的情況下也是為了提升讀寫(xiě)吞吐的，他們?yōu)榱俗屪x性能遠(yuǎn)超LSM-tree的這樣的數(shù)據(jù)結(jié)構(gòu)，采用了hash表作為內(nèi)存索引數(shù)據(jù)結(jié)構(gòu)。

內(nèi)存數(shù)據(jù)結(jié)構(gòu)叫做keydir，形態(tài)如下：

這個(gè)hash表映射的key都是定長(zhǎng)的，這個(gè)key在hash表中的’value’ 存儲(chǔ)了幾個(gè)字段：

• file_id : 這個(gè)key所屬的datafile id
• value_sz : value size
• value_pos: value在 data file中的偏移地址
• tstamp: 時(shí)間戳

這個(gè)內(nèi)存數(shù)據(jù)結(jié)構(gòu)僅僅保存最新的key-value數(shù)據(jù)信息，同一個(gè)key的舊數(shù)據(jù)還會(huì)存儲(chǔ)在舊的data file中，在后續(xù)的log-merging過(guò)中會(huì)被清理。

3. 讀流程

如下圖：

總共分為四步：

1. 從內(nèi)存的hash表中找到之前寫(xiě)入的key，取出這個(gè)key數(shù)據(jù)所在的file_id
2. 拿著file-id找到對(duì)應(yīng)的data file
3. 根據(jù)value_pos 找到datafile上的指定entry
4. 從entry的末尾向前讀取value_sz 的數(shù)據(jù)，即為key的value數(shù)據(jù)

現(xiàn)在，從Get的流程中我們很明顯的能夠看到bitcask 設(shè)計(jì)上存在的一些問(wèn)題：

1. 內(nèi)存索引 中hash表中存放的是所有寫(xiě)入的key，也就是一個(gè)機(jī)器能夠存放的總數(shù)據(jù)量是有限的
2. 因?yàn)闆](méi)有持久化索引，所以機(jī)器異常恢復(fù)的時(shí)候需要遍歷磁盤(pán)上所有的data file，來(lái)構(gòu)建內(nèi)存hash索引
3. 沒(méi)有讀緩存，即讀的過(guò)程中value都需要從磁盤(pán)加載，這里bitcask的開(kāi)發(fā)者說(shuō)是考慮到成本太高，也就沒(méi)有做了。。。那個(gè)時(shí)候的內(nèi)存應(yīng)該還挺貴的，記得10年的能買(mǎi)得起的筆記本電腦內(nèi)存應(yīng)該還處于2G以下，那個(gè)時(shí)候筆記本架構(gòu)普遍在大幾千:)

但是這個(gè)并不影響bitcask在當(dāng)時(shí)的性能優(yōu)勢(shì)，第一個(gè)數(shù)據(jù)量問(wèn)題其實(shí)能夠達(dá)到超過(guò)內(nèi)存10倍的持久化存儲(chǔ)能力就滿(mǎn)足 Riak的需求了這里他們也沒(méi)有再多說(shuō)。第二個(gè)問(wèn)題則就是時(shí)間上的問(wèn)題，或者可以多線(xiàn)程recovery來(lái)重放，他們也能接受。。。

4. 數(shù)據(jù)合并

之前說(shuō)了，為了提升寫(xiě)吞吐，bitcask采用了追加寫(xiě)方式，包括刪除操作也是一個(gè)追加的過(guò)程。因?yàn)槭亲芳訉?xiě)，也就有了GC來(lái)清理過(guò)期數(shù)據(jù)。

數(shù)據(jù)合并的過(guò)程大體如下，也很簡(jiǎn)單：

就是根據(jù)內(nèi)存中的lastest hash表中的key數(shù)據(jù)，遍歷所有older data files，只保留最新版本的key數(shù)據(jù)，將entry寫(xiě)入到一個(gè)新的merged data file中。因?yàn)檫@個(gè)文件可能會(huì)很大，所以會(huì)生成一個(gè)hint file來(lái)索引這個(gè)merged data file的內(nèi)容。當(dāng)然，hint file中的每一個(gè)entry也是對(duì)應(yīng)merged data file中的每一個(gè)entry，只是并沒(méi)有存儲(chǔ)value，而是存儲(chǔ)了value的偏移地址來(lái)加速讀取。

這個(gè)merged data file和hint file 除了能夠清理過(guò)期數(shù)據(jù)，釋放空間之外還能夠在機(jī)器異常恢復(fù)之后加速內(nèi)存中hash 索引的重建（畢竟都是lastest version，也就不需要再重新遍歷所有的數(shù)據(jù)了）

總結(jié)

總的來(lái)說(shuō)，bitcask就是一個(gè)簡(jiǎn)單的持久化hash引擎。隨著硬件的飛速發(fā)展，DRAM的價(jià)格越來(lái)越便宜，磁盤(pán)的性能不斷飆升，且價(jià)格也在不斷降低。到現(xiàn)在，甚至操作系統(tǒng)的I/O棧和網(wǎng)絡(luò)協(xié)議棧都因?yàn)橛布臉O致性能而成為瓶頸，而bitcask在那個(gè)時(shí)候構(gòu)建在文件系統(tǒng)之上的持久化層相比于現(xiàn)在已經(jīng)遠(yuǎn)遠(yuǎn)達(dá)不到性能要求了。

現(xiàn)在來(lái)看，內(nèi)存數(shù)據(jù)結(jié)構(gòu)不會(huì)有太大的變化，還是hash表。但底層只能基于新硬件來(lái)構(gòu)建引擎，并且引擎層跳過(guò)操作系統(tǒng)I/O棧自己來(lái)管理硬件，在此基礎(chǔ)上的hash引擎在當(dāng)代才能夠被稱(chēng)為高性能的hash引擎。

當(dāng)然，還需要有類(lèi)似rocksdb開(kāi)發(fā)者們的卓越編碼能力以及對(duì)操作系統(tǒng)細(xì)節(jié)的深刻理解和應(yīng)用才能讓引擎的性能在當(dāng)下的硬件上發(fā)揮到極致。

總結(jié)

以上是生活随笔為你收集整理的BitCask 持久化hash存储引擎 原理介绍的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。