文章目錄
- 前言
- 引擎背景
- 引擎原理
- 1. 磁盤資料結構
- 2. 記憶體資料結構
- 3. 讀流程
- 4. 資料合并
- 總結
前言
最近工作中部分項目中，對存儲引擎的需求希望高性能的寫、點查，并不需要Range。這裡看到大家總會提到
BitCask
這個存儲引擎方案，并不是很了解，特此做一個總體的學習記錄。
引擎背景
BitCask
是分布式資料庫
Riak
有存儲引擎上的一些需求，但是當時(2010年左右)業界并沒有一個能夠滿足需求的引擎，包括但不限于
Berkeley DB
,
Tokyo Cabinet
,
Innostore
等。是以
BitCask
便應運而生，主要為了解決以下一些需求：
- 讀/寫 的低延時
- 随機寫場景下的高吞吐
- 支援資料量遠大于記憶體的持久化存儲
- 異常恢複機制，能夠快速recovery且不丢資料
- 便捷得資料備份機制
- 支援易了解的資料結構
- 大并發/大資料量下的引擎穩定性保障
- 支援平滑遷移到
Riak
除了最後一條定制化需求之外，對于今天我們的存儲引擎來說其實都是一些最基本的需求，因為沒有強Range性能需求，是以這一些基本要求也是可以了解的，無非就是引擎的穩定性和性能。然而，當時業界并沒有這樣的一個存儲引擎，是以
Riak
的開發者們也就隻能撸起袖子自己搞了。google的bigtable中提出的LSM-tree對讀性能并不友好，是以也不滿足。
因為沒有Range,他們便從hash資料結構入手來提供O(1)的點查，由借鑒了Log-Structure Merged 資料結構中的log-merging思想，來提供強大的寫入性能。
引擎原理
1. 磁盤資料結構
BitCask磁盤資料結構非常簡單，一個BitCask執行個體就是一個檔案系統目錄。需要保證同一時刻隻有一個程序會通路這個目錄，程序寫入的資料更新僅僅會落在一個Active data file中，當這個檔案達到了一個給定的門檻值，會建立一個新的active data file，而之前的接受寫入的檔案會被标記為隻讀。
程序寫入key/value到active data file的過程時追加寫方式，也就是類似于一個檔案writer，這個過程會轉化成磁盤上的順序寫，是以寫入性能肯定會很高。
每一個磁盤上的entry資料格式如下：
- crc : 目前entry的資料校驗
- tstamp: 時間戳
- ksz: key size
- value_sz : value size
- key : key的内容
- value : value的内容
如果想要删除資料，也是寫入一個deletion的 tombstone标記，後續的log-merging會清理。
是以，每一個磁盤上的datafile 中的entry最後都追加成這樣的形态：
2. 記憶體資料結構
之前說了，bitcask保證低延時的情況下也是為了提升讀寫吞吐的，他們為了讓讀性能遠超LSM-tree的這樣的資料結構，采用了hash表作為記憶體索引資料結構。
記憶體資料結構叫做
keydir
，形态如下：
這個hash表映射的key都是定長的，這個key在hash表中的’value’ 存儲了幾個字段：
- file_id : 這個key所屬的datafile id
- value_sz : value size
- value_pos: value在 data file中的偏移位址
- tstamp: 時間戳
這個記憶體資料結構僅僅儲存最新的key-value資料資訊，同一個key的舊資料還會存儲在舊的data file中，在後續的log-merging過中會被清理。
3. 讀流程
如下圖：
總共分為四步：
- 從記憶體的hash表中找到之前寫入的key，取出這個key資料所在的file_id
- 拿着file-id找到對應的data file
- 根據value_pos 找到datafile上的指定entry
- 從entry的末尾向前讀取value_sz 的資料，即為key的value資料
現在，從Get的流程中我們很明顯的能夠看到bitcask 設計上存在的一些問題：
- 記憶體索引 中hash表中存放的是所有寫入的key，也就是一個機器能夠存放的總資料量是有限的
- 因為沒有持久化索引，是以機器異常恢複的時候需要周遊磁盤上所有的data file，來建構記憶體hash索引
- 沒有讀緩存，即讀的過程中value都需要從磁盤加載，這裡bitcask的開發者說是考慮到成本太高，也就沒有做了。。。那個時候的記憶體應該還挺貴的，記得10年的能買得起的筆記本電腦記憶體應該還處于2G以下，那個時候筆記本架構普遍在大幾千:)
但是這個并不影響bitcask在當時的性能優勢，第一個資料量問題其實能夠達到超過記憶體10倍的持久化存儲能力就滿足
Riak
的需求了這裡他們也沒有再多說。第二個問題則就是時間上的問題，或者可以多線程recovery來重放，他們也能接受。。。
4. 資料合并
之前說了，為了提升寫吞吐，bitcask采用了追加寫方式，包括删除操作也是一個追加的過程。因為是追加寫，也就有了GC來清理過期資料。
資料合并的過程大體如下，也很簡單：
就是根據記憶體中的lastest hash表中的key資料，周遊所有older data files，隻保留最新版本的key資料，将entry寫入到一個新的merged data file中。因為這個檔案可能會很大，是以會生成一個hint file來索引這個merged data file的内容。當然，hint file中的每一個entry也是對應merged data file中的每一個entry，隻是并沒有存儲value，而是存儲了value的偏移位址來加速讀取。
這個merged data file和hint file 除了能夠清理過期資料，釋放空間之外還能夠在機器異常恢複之後加速記憶體中hash 索引的重建（畢竟都是lastest version，也就不需要再重新周遊所有的資料了）
總結
總的來說，bitcask就是一個簡單的持久化hash引擎。随着硬體的飛速發展，DRAM的價格越來越便宜，磁盤的性能不斷飙升，且價格也在不斷降低。到現在，甚至作業系統的I/O棧和網絡協定棧都因為硬體的極緻性能而成為瓶頸，而bitcask在那個時候建構在檔案系統之上的持久化層相比于現在已經遠遠達不到性能要求了。