同样是1亿数据，为什么nutsdb扛不住，而badgerdb可以？
背景
? 之前在知乎上看到一個問題：作為一個KV數據庫，levelDB為什么使用LSM樹實現，而不是hash索引？當時就想作答一番。不過看到問題下方已經有大佬作答了，而我也說不出什么新東西來。于是選擇作罷。
? 但是最近有nutsdb用戶提了一個issue。大致描述的場景是，他們每天大概有1億的數據寫入，用badgerdb是可以cover住的，但是用nutsdb每次都會因為內存耗盡而提前終止。這個問題正好也涉及到LSM和Hash索引這兩種存儲架構。也讓我聯想起在那個知乎上的問題，覺得可以寫一篇文章分析這種情況。**為什么同樣是一億數據，nutsdb內存會不夠用，而badgerdb卻能cover得住呢？**順便我們也可以從內存的角度來看，在大規模數據的背景下這兩種架構的對應實現的表現如何。
? 我們知道，論文和實際落地有時候是有比較大的出入的，所以這篇文章主要會關注LSM和Bitcask（Hash索引的典型代表）的對應實現，也就是leveldb和nutsdb，為什么是leveldb呢，因為badgerdb是在leveldb的基礎上實現了kv分離以達到減少讀寫放大，這個feature并不會對這篇文章的討論結果有多少影響，所以為了降低文章的復雜度，本文決定選取leveldb作為觀察對象。分析現實世界中這兩者的異同。本人水平有限，分析過程中有不當之處還請批評指正。
前置知識
? 這篇文章不會深入到源碼級別，重點是理論分析。很多地方不會講述技術細節，而是一筆帶過。所以需要朋友們對一些前置的知識有一定的了解。我找了一些個人認為講的比較好的文章，讓大家對LSM，Bitcask，leveldb，nutsdb有整體的了解。大家如果對以上的知識沒有太多的了解的話，可以翻到文章最下方看延伸閱讀上的材料哦～
1. nutsdb
nutsdb寫入和讀取數據的流程相對比較簡單，寫入數據的時候會直接將數據encode成二進制數據，直接寫入到磁盤中。通過構建一個索引對象插入到內存索引數據結構（Bitcask中使用的是hashmap，而nutsdb實現是使用B+Tree）的方式記錄數據在磁盤的位置(文件名+數據在文件中的偏移)。
轉過來看，讀取數據的時候可以在內存的索引結構中得到數據的的位置，然后用一次系統調用將數據取出。
? 所以我們可以知道的是，nutsdb每新增一條數據，都要在內存中構建一個索引對象去標識數據的位置，以方便我們可以根據這個位置讀取出來。所以當數據量很大的時候，索引對象會持續增多，內存遲早是會扛不住的。當然我們可以使用一些壓縮算法，比如在論文《Optimistically Compressed Hash Tables & Strings in the USSR》中提到的對hash的壓縮，將內存中的索引數據進行一定程度的壓縮。不過這樣是治標不治本的，只能延緩內存爆滿的發生，隨著數據的增長內存該炸還是會炸的。
2. goleveldb
? 相比而言leveldb的情況就復雜很多。Leveldb存儲的數據分為兩部分，一是存儲在WAL和與之對應的MemTable的數據，另外是以SST形式組織起來數據，也就是經過Minor Compaction和Major Compaction之后形成的一層層數據文件。
? 所以歸結起來在leveldb中，內存里會有一下三樣東西。1. Memtable 2. LRU緩存（用來緩存在SST中讀取出來的block，其中有索引內容，也有數據內容） 3. SST的內存索引。
? Memtable和LRU緩存大小是配置可控的，所以在這一塊上，可謂窮有窮的玩法，富有富的玩法。也就說如果內存充足可以在Memtable和LRU放置更多更多，內存預算不是很多的話就可以分配少一點，memtable放的東西少會頻繁觸發minor compaction， LRU少會頻繁發生IO系統調用讀取磁盤數據，不過無論內存情況怎么樣，memTable和LRU緩存始終是能玩的。還有剩下的一個，SST的索引，是什么呢？
? 我們之前講到，程序是運行在內存中的，對于持久化存儲引擎而言，數據是會落到磁盤上保存的，但是磁盤不知道你存了什么進來，所以需要存儲引擎設計一些算法精準找到磁盤中的數據。Bitcask模型比較簡單，也就是一條數據對應一個索引。這樣直接可以讀取數據了。但是在leveldb中，他能夠以很小的內存管理一大片磁盤中的數據，讓我們看看他是怎么做到的。
? 我們可以在上圖中看到leveldb會有因為一次次compaction操作所形成的一層層的SST文件，當然我們要知道的是，這里所謂的一層層，是我們的邏輯概念，磁盤是不會幫你維護這個邏輯的。所以在內存中我們需要維護這個關系。那么他是怎么做的呢，下面我們看看goleveldb代碼實現。
var levels []tFiles// tFiles hold multiple tFile. type tFiles []*tFile// tFile holds basic information about a table. type tFile struct {fd storage.FileDescseekLeft int32size int64imin, imax internalKey }? 我們可以看到，levels代表所有層次SST文件的所有索引信息。而tFiles代表一層的SST文件的索引信息。tFile結構維護的是一個SST文件的索引信息，其中最重要的內容其實是imin和imax，標識了這個文件中存儲的數據Key的范圍。查詢數據的時候可以依次遍歷每一層，因為上層的數據總是比下層的新，如果在當層找到了就不需要往下找了，找不到就繼續往下層找，直到遍歷完最后一層。在同層中可以通過比對Key與tFile中的存儲的imin和imax看下key是否存在于這個文件中。如果存在的話就可以讀取這個文件來找到這條數據。得益于SST的優秀設計，找尋數據就像開啟一個又一個的盲盒，在即有的提示之下不斷的迫近數據所在，直到最后豁然開朗找到數據。而這一個個盲盒很大一部分又都在磁盤中。不會像nutsdb那樣所有數據都需要一個索引對象存在與內存中。如下圖所示的SST文件的組織結構。
? 讓我們看看要在SST中讀取一條數據需要打開幾個盲盒。首先我們會在內存中判斷這個要讀取的key是不是在imin和imax之間，如果是的話，就讀SST的Footer，Footer會提示我們找到SST數據模塊的索引信息（Index Block）以及索引信息的描述信息（Meta Index Block，布隆過濾器是可選的，所以這個實際上可能不一定有）。根據Index Block我們可以找到數據所在。當然這里不會展開SST中每個Block是怎么設計的，感興趣的朋友可以看延伸閱讀哦。
? 我們可以看到，通過高效的數據組織形式。只需要很小一部分內存，也就是levels這個對象里面包含的東西，存儲少量的索引對象在內存中，也可以管理很大量的磁盤數據，也就是大量的數據。這樣雖然會引入多次的系統調用才能最終找到數據，但是這些讀取過的block都可以被緩存起來，后面也不需要在重復發生系統調用了。
? 綜上所講述，leveldb在內存的使用上，無論數據量的多少可以達到一個比較健康的狀態。數據量多的時候，可能會出現零散讀取數據的情況，會頻繁的在緩存中進行換入換出，性能上會變慢，但是不至于不可用，換一個角度來說，數據量如果很大，系統變慢，從感官上來說，應該是屬于正常的。但是不可用，很難接受的。
? 說到這里你可能會問了，nutsdb也可以這樣組織數據嘛，這不就解決內存問題了？這個問題問的很好，但是理論上來說，是不太可能的。為什么呢？
3. nutsdb可以換一個數據組織方式嗎？
? 為什么說不太可能呢？問題的關鍵在于，nutsdb的數據是亂序存儲的，而leveldb是有序存儲的。正是這一字之差造成了這樣的情況。為什么這么說呢？
? 在我們之前的文章中，講過在nutsdb中一條數據在磁盤里是這樣存在的。數據是以下圖的形式一條條的追加寫入到磁盤之中。可以理解為，在磁盤中相鄰數據之間沒有任何關系，所以需要在內存中記錄每一條數據在什么位置。不然就不知道怎么找數據了。
? 那么leveldb呢？為什么數據有序就可以做到呢？得益于Memtable這樣的內存數據結構，在leveldb中他的實現是跳表。在跳表的最下面一層就是一條有序的鏈表，可以通過一次遍歷就寫入這些數據到SST的Data Block中。也就是說在SST中數據之間其實是有序排列的。這樣就可以通過不斷的縮小范圍找到數據啦。
總結
? 說到這， 其實并不是bitcask的設計不行，正所謂架構沒有最好和最壞，只有最合適的。bticask讀寫性能都比較穩定，點查場景中速度較快，但是缺點就是內存占用會隨著數據的增長而增長。leveldb讀會稍微差一點，因為需要多次io才能找到數據，并且有時候會跨越多個層級讀取SST。不過bitcask的設計會存在一個問題，就是隨著數據的不斷增長，內存也會水漲船高，如果您有比較大量的數據，不是很建議使用bitcask實現的存儲引擎去存儲哦。在這里我要由衷贊嘆的是，SST的設計確實精美絕倫。
延伸閱讀
總結
以上是生活随笔為你收集整理的同样是1亿数据，为什么nutsdb扛不住，而badgerdb可以？的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： KBU1010-ASEMI电源控制柜整流
- 下一篇： 中国凝血因子席市场趋势报告、技术动态创新