242
Bitcask存儲模型
----《大規模分布式存儲係統：原理解析與架構實戰》讀書筆記
最近一直在分析OceanBase的源碼，恰巧碰到了OceanBase的核心開發者的新作《大規模分布式存儲係統：原理解析與架構實戰》.看完樣章後決定入手，果然物有所值。對於準備學習分布式的同學，這是一本不錯的書籍，相對係統，全麵的介紹了分布式的相關技術和項目，基本都是幹貨。還有一半是在介紹OceanBase的內容，對我來說，正是踏破鐵鞋無覓處，接下來會有幾篇專門研究存儲引擎的讀書筆記喲。廢話不多說，轉入正題。
1.存儲的介質與讀寫
談存儲，那麼理解存儲的介質的特性顯然很重要，書中談了很多硬件結構，但最重要的結論，都濃縮在存儲介質對比這張表中了。
磁盤介質對比
| 類別 | 每秒讀寫(IOPS)次數 | 每GB價格(元) | 隨機讀取 | 隨機寫入 |
|---|---|---|---|---|
| 內存 | 千萬級 | 150 | 友好 | 友好 |
| SSD盤 | 35000 | 20 | 友好 | 寫入放大問題 |
| SAS磁盤 | 180 | 3 | 磁盤尋道 | 磁盤尋道 |
| SATA磁盤 | 90 | 0.5 | 磁盤尋道 | 磁盤尋道 |
從表中可以看出，內存的隨機讀寫能力最強，遠超SSD盤和磁盤。但是我們都知道，內存無法持久化。現在許多公司在性能要求高的地方都使用了SSD盤，相對SAS和SATA磁盤，隨機讀取速度有了很大的提升。但是對於隨機寫入，存在寫入放大問題。
寫入放大問題與SSD盤的特性有關，SSD盤不能隨機寫入，隻能整塊整塊的寫入。最簡單的例子，比如要寫入一個4KB的數據，最壞的情況就是，一個塊裏已經沒有幹淨空間了，但是有無效數據可以擦除，所以主控就把所有的數據讀出來，擦除塊，再加上這個4KB新數據寫回去，這個操作帶來的寫入放大就是: 實際寫4K的數據，造成了整個塊（512KB）的寫入操作，那就是128倍放大。此外，SSD盤的壽命也有寫入次數相關。
如果使用SSD來作為存儲引擎的存儲介質，最好從設計上減少或避免隨機寫入，使用順序寫入取而代之。
2.Bitcask存儲模型介紹
存儲係統的基本功能包括：增、刪、讀、改。其中讀取操作有分為順序讀取和隨機讀取。
總體來說，大部分應用使用讀的功能最多，解決讀的性能是存儲係統的重要命題。一般來說。快速查找的思想基本源自二分查找法和哈希查詢。例如關係數據庫中常用的B+存儲模型就是使用二分查找的思想，當然，實際實現比二分查找複雜很多。B+存儲模型支持順序掃描。另外一類則是基於哈希思想的鍵值模型，這類模型不支持順序掃描，僅支持隨機讀取。
今天要討論的Bitcask模型是一種日誌型鍵值模型。所謂日誌型，是指它不直接支持隨機寫入，而是像日誌一樣支持追加操作。Bitcask模型將隨機寫入轉化為順序寫入。有兩個好處：
- 提高隨機寫入的吞吐量，因為寫操作不需要查找，直接追加即可
- 如果使用SSD作為存儲介質，能夠更好的利用新硬件的特性
Bitcask中存在3種文件，包括數據文件,索引文件和線索文件(hint file,姑且就叫線索文件吧)。數據文件存儲於磁盤上，包含了原始的數據的鍵值信息；索引文件存在於內存，用於記錄記錄的位置信息，啟動Bitcask時，它會將所有數據的位置信息全部讀入一個內存中的哈希表，也就是索引文件；線索文件(hint file)並不是Bitcask的必需文件，它的存在是為了提供啟動時構建索引文件的速度。
2.1 日誌型的數據文件
Bitcask的數據文件組織如下圖：任意時刻，係統中隻有一個數據文件支持寫入，稱為active data file。其餘的數據文件都是隻讀文件，稱為older data file。
上麵數據項分別為：後麵幾項的crc校驗值,時間戳,key，value，key的大小，value的大小。
數據文件中就是連續一條條上麵格式的數據，如下圖：
2.2 索引哈希表
索引哈希表記錄了全部記錄的主鍵和位置信息，索引哈希表的值包含了：記錄文件的編號,value長度,value的在文件中的位置和時間戳。Bitcask的總體數據結構如下圖：
2.3 線索文件(hint file)
Bitcask啟動時要重建索引哈希表，如果數據量特別大，則會導致啟動很慢。而線索文件(hint file)則是用來加速啟動時重建哈希表的速度。線索文件(hint file)的記錄與數據文件的格式基本相同，唯一不同的是數據文件記錄數據的值，而線索文件(hint file)則是記錄數據的位置。
這樣在啟動的時候就可以不用讀數據文件，而是讀取線索文件(hint file)，一行行重建即可，大大加快了哈希表的重建速度。
3. Bitcask功能介紹
上節提到，存儲係統的基本功能包括：增、刪、讀、改。那麼Bitcask中如何實現的呢？
-
如何增加記錄？
用戶寫入的記錄直接追加到活動文件，因此活動文件會越來越大，當到達一定大小時，Bitcask會凍結活動文件，新建一個活動文件用於寫入，而之前的活動文件則變為了older data file。寫入記錄的同時還要在索引哈希表中添加索引記錄。 -
如何刪除記錄？
Bitcask不直接刪除記錄，而是新增一條相同key的記錄，把value值設置一個刪除的標記。原有記錄依然存在於數據文件中，然後更新索引哈希表。 -
如何修改記錄？
Bitcask不支持隨機寫入。因為對於存儲係統的基本功能中的增和改，實際上都是一樣的，都是直接寫入活動數據文件。同時修改索引哈希表中對應記錄的值。(這個時候，實際上數據文件中同一個key值對應了多條記錄，根據時間戳記錄來判斷，以最新的數據為準。) -
如何讀取記錄?
讀取時，首先從索引哈希表中定位到記錄在磁盤中位置，然後通過IO讀取出對應的記錄。 -
合並(Marge)操作
Bitcask這種隻增不減地不斷寫入，必然會是數據文件不斷的膨脹。而其中有許多是被標記刪除和修改後留下的無用記錄。合並操作就是為了剔除這部分數據，減小數據文件大小。
merge操作，通過定期將所有older data file中的數據掃描一遍並生成新的data file（沒有包括active data file 是因為它還在不停寫入）。如果同一個Key有多條記錄，則隻保留最新的一條。從而去掉數據文件中的冗餘數據。而且進行合並(Marge)操作時，還可以順帶生成線索文件(hint file)。合並(Marge)操作通常會在數據庫較閑的時候進行，比如淩晨一兩點等。
4.總結
Bitcask是一個精煉的鍵值存儲模型。采用日誌型的數據結構，隻追加不改寫就記錄，提高了隨機寫入的吞吐量，通過建立哈希表來加快查詢速度，定期合並數據文件，並生成線索文件(hint file)，提高啟動時重建哈希表的速度。
這是我參考了網上的一個python實現，並增加了部分功能後的代碼:https://github.com/Winnerhust/Code-of-Book/blob/master/Large-Scale-Distributed-Storage-System/bitcask.py
除了增刪讀寫外,主要還實現了：
- 數據文件合並，合並時可以選擇生成線索文件(hint file)
- 可以使用線索文件(hint file)啟動
最後更新：2017-04-03 05:39:19