同样是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电源控制柜整流
- 下一篇: 中国凝血因子席市场趋势报告、技术动态创新