單機存儲引擎的基礎方法

這是一篇關於單機存儲引擎基本思路的總結和分析。

看了 Facebook Haystack 的論文 [1] 後，對於其單機對象存儲引擎的設計感覺十分簡潔，進而對其他單機引擎的設計產生了一些興趣。

看了 [2] 之後，對單機存儲引擎有了一個非常粗略的了解。首先，需要處理的內容分為兩類：數據及其索引。此時有兩種方案：

1. 數據和索引放到一起（聚簇索引，Clustered Index），例如 Berkeley DB，InnoDB，LevelDB
2. 數據和索引分別存放，例如 MyISAM，Facebook Haystack

對於索引，只考慮精確索引，有以下分類：

• 平坦結構
• 哈希表，例如 Bitcask
• 樹結構
• B 樹族，例如 Berkeley DB，InnoDB，MyISAM
• LSM 樹，例如 LevelDB
• 分形樹，例如 PerconaFT
• R 樹，例如 PostGIS
• T 樹（純內存結構 )，例如 EXtremeDB

方案比較（個人看法）

數據和索引放在一起存儲的方案，其優點在於：

1. 索引到 Key 之後無需再進行一次 IO 操作即可直接取出 Value
2. 索引和數據的一致性高
3. 如果索引是有序的，則數據也是有序存放的，進行掃描時效率高

數據和索引不放在一起存儲的方案，其優點在於：

1. 數據和索引可以以不同的方式進行組織
2. 索引的大小顯著減少

如果索引能夠全放入內存，則不應該使用聚簇索引。寫請求較多的情況下，最好不要使用聚簇索引。需要支持掃描請求的話，並且數據存儲於 HDD 的情況下，應該考慮聚簇索引。如果在意啟動時間，應該使用聚簇索引。具體解釋見後面 Update 1。

對於索引方案，可以看到很少有使用哈希表做索引的存儲引擎。個人認為這是因為哈希表必須全部裝入內存，並且很難進行增量持久化。這對於傳統資料庫場景和文件系統場景都是不可接受的，因為佔用了太多內存。B 樹和 LSM 樹比較受歡迎也是因為索引可以部分裝入內存，這樣熱點索引載入內存，其他留在磁碟上，剩下的內存就可以做其他事情了，最差也可以做熱點數據的緩存用。

LSM 樹是近幾年新興的索引結構，其比較 B 樹的優點是讀寫性能更高。這是得益於其分裂、合併的操作可以在後台進行。LSM 樹的缺點是寫放大，這在論文 [3] 中有所改進。LSM 的另一個問題是在寫請求較多時，後台合併的速度不夠快以至於很難完成分裂、合併等操作，以至於整體性能的持續下降。

幾乎所有的存儲引擎沒有採用 Facebook Haystack 的方案，使用非同步寫入 Index File 的方式增量持久化內存索引信息。這是因為大部分存儲引擎是為了小 Value 設計的。對於 Facebook Haystack 的場景，平均個 Value 大約有 80KB 左右的大小，一個 100GB 的資料庫也只能存儲約 1.3 million 個對象，其索引大小應不會超過 10MB。常見的資料庫使用場景應該不是這樣的，但是我沒有統計數據。但是個人認為，對於純 Key-Value Store 的場景（無需在節點上進行 join 之類的計算），可以接受比較大的索引大小，比如說 10GB 的索引。在這樣的情況下，Facebook Haystack 的設計方案還是很有吸引力的，相當於一次同步的順序寫入操作即可完成寫請求。如果比較在意索引佔用內存的話，也可以使用 LSM 樹進行索引，但是將索引和數據分離仍然能夠受益，見論文 [4]。

References

[1] Beaver, D., Kumar, S., Li, H. C., Sobel, J., Vajgel, P., & Facebook, I. (2010). Finding a Needle in Haystack: Facebook』s Photo Storage. In Proc. USENIX Symp. Operating Systems Design and Implementations (OSDI』10) (pp. 1–14).

[2] Martin Kleppmann. 2016. Designing Data-Intensive Applications: The Big Ideas Behind Reliable, Scalable, and Maintainable Systems (1st ed.). O』Reilly Media, Inc.

[3] Pandian Raju, Rohan Kadekodi, Vijay Chidambaram, and Ittai Abraham. 2017. PebblesDB: Building Key-Value Stores using Fragmented Log-Structured Merge Trees. In Proceedings of the 26th Symposium on Operating Systems Principles - SOSP 』17, 497–514. DOI:https://doi.org/10.1145/3132747.3132765

[4] Thanumalayan Sankaranarayana Pillai Lanyue Lu and Remzi H. Arpaci-Dusseau Andrea C. Arpaci-Dusseau. 2016. WiscKey: Separating Keys from Values in SSD-Conscious Storage. Fast 』16 13, 1 (2016), 1–28. https://doi.org/10.1145/3033273

Update 1

個人非常同意評論區 @CatKang 的看法：選擇數據和索引分離還是在一起這個問題得考慮三個維度：索引特性，對象大小，請求特徵。

由於已經有兩位知友就我對於如何選擇聚簇索引的看法提出一些問題，我希望把這一段討論進一步展開一些，給出我提出這一建議的具體原因。

如果索引能夠全放入內存，則不應該使用聚簇索引。使用聚簇索引很可能就不能將索引全部載入內存中，在這種情況下有點得不償失。全內存索引性能高，索引結構上受到的限制極少。如有可能，應該盡量使用全內存索引。

寫請求較多的情況下，最好不要使用聚簇索引。並非不要使用聚簇索引，而是建議考慮非聚簇索引。不使用聚簇索引，可以更自由的組織寫入數據的存放方式，進而獲得更高的寫入性能，比如說像 Haystack 那樣順序寫單文件，又比如說並行寫 SSD 上不同 cell 的多個文件。使用聚簇索引可以避免使用非聚簇索引帶來的一些問題，例如掃描性能可能下降，刪除場景浪費空間，索引和數據的 Crash 一致性問題，等等。但是不可避免的，數據的寫入受限於索引的組織方式。使用 B 樹，隨機寫帶來性能下降。使用 LSM 樹進行索引，（個人看法）也不過是將隨機寫延遲到後台線程進行，隨機寫轉化為順序寫的代價就是寫放大，並且在持續高寫入場景下，還會有 compact 和寫入請求爭用寫入帶寬的問題。

需要支持掃描請求的話，並且數據存儲於 HDD 的情況下，應該考慮聚簇索引。掃描請求最好是數據有序排放，一次掃描正好訪問一個連續空間，性能高。此時如果索引本身是有序的，再採用聚簇索引，對掃描請求的支持效率是最高的。

如果在意啟動時間，應該使用聚簇索引。非聚簇索引的索引和數據有 Crash 一致性問題。在 Crash-Recover 的場景下，需要從數據恢復索引的最新狀態，帶來啟動時間的增加。