為什么 MongoDB 使用 B 樹(shù)？
為什么這么設(shè)計(jì)(Why's THE Design)是一系列關(guān)于計(jì)算機(jī)領(lǐng)域中程序設(shè)計(jì)決策的文章，我們?cè)谶@個(gè)系列的每一篇文章中都會(huì)提出一個(gè)具體的問(wèn)題并從不同的角度討論這種設(shè)計(jì)的優(yōu)缺點(diǎn)、對(duì)具體實(shí)現(xiàn)造成的影響。
概述
MongoDB 是一個(gè)通用的、面向文檔的分布式數(shù)據(jù)庫(kù)[^1]，這是官方對(duì) MongoDB 介紹。區(qū)別于傳統(tǒng)的關(guān)系型數(shù)據(jù)庫(kù) MySQL、Oracle 和 SQL Server，MongoDB 最重要的一個(gè)特點(diǎn)就是『面向文檔』，由于數(shù)據(jù)存儲(chǔ)方式的不同，對(duì)外提供的接口不再是被大家熟知的 SQL，所以被劃分成了 NoSQL，NoSQL 是相對(duì) SQL 而言的，很多我們耳熟能詳?shù)拇鎯?chǔ)系統(tǒng)都被劃分成了 NoSQL，例如：Redis、DynamoDB[^2] 和 Elasticsearch 等。
sql-and-nosq
NoSQL 經(jīng)常被理解成沒(méi)有 SQL(Non-SQL)或者非關(guān)系型(Non-Relational)[^3]，不過(guò)也有人將其理解成不只是 SQL(Not Only SQL)[^4]，深挖這個(gè)詞的含義和起源可能沒(méi)有太多意義，這種二次解讀很多時(shí)候都是為營(yíng)銷服務(wù)的，我們只需要知道 MongoDB 對(duì)數(shù)據(jù)的存儲(chǔ)方式與傳統(tǒng)的關(guān)系型數(shù)據(jù)庫(kù)完全不同。
MongoDB 的架構(gòu)與 MySQL 非常類似，它們底層都使用了可插拔的存儲(chǔ)引擎以滿足用戶的不同需求，用戶可以根據(jù)數(shù)據(jù)特征選擇不同的存儲(chǔ)引擎，最新版本的 MongoDB 使用了 WiredTiger 作為默認(rèn)的存儲(chǔ)引擎[^5]。
mongodb-architecture
作為 MongoDB 默認(rèn)的存儲(chǔ)引擎，WiredTiger 使用 B 樹(shù)作為索引底層的數(shù)據(jù)結(jié)構(gòu)，但是除了 B 樹(shù)之外，它還支持 LSM 樹(shù)作為可選的底層存儲(chǔ)結(jié)構(gòu)，LSM 樹(shù)的全稱是 Log-structured merge-tree，你可以在 MongoDB 中使用如下所示的命令創(chuàng)建一個(gè)基于 LSM 樹(shù)的集合(Collection)[^6]:
- db.createCollection(
- "posts",
- { storageEngine: { wiredTiger: {configString: "type=lsm"}}}
- )
我們?cè)谶@篇文章中不僅會(huì)介紹 MongoDB 的默認(rèn)存儲(chǔ)引擎 WiredTiger 為什么選擇使用 B 樹(shù)而不是 B+ 樹(shù)，還會(huì)對(duì) B 樹(shù)和 LSM 樹(shù)之間的性能和應(yīng)用場(chǎng)景進(jìn)行比較，幫助各位讀者更全面地理解今天的問(wèn)題。
設(shè)計(jì)
既然要比較兩個(gè)不同數(shù)據(jù)結(jié)構(gòu)與 B 樹(shù)的差別，那么在這里我們將分兩個(gè)小節(jié)分別介紹 B+ 樹(shù)和 LSM 樹(shù)為什么沒(méi)有成為 WiredTiger 默認(rèn)的數(shù)據(jù)結(jié)構(gòu)：
- 作為非關(guān)系型的數(shù)據(jù)庫(kù)，MongoDB 對(duì)于遍歷數(shù)據(jù)的需求沒(méi)有關(guān)系型數(shù)據(jù)庫(kù)那么強(qiáng)，它追求的是讀寫單個(gè)記錄的性能;
- 大多數(shù) OLTP 的數(shù)據(jù)庫(kù)面對(duì)的都是讀多寫少的場(chǎng)景，B 樹(shù)與 LSM 樹(shù)在該場(chǎng)景下有更大的優(yōu)勢(shì);
上述的兩個(gè)場(chǎng)景都是 MongoDB 需要面對(duì)和解決的，所以我們會(huì)在這兩個(gè)常見(jiàn)場(chǎng)景下對(duì)不同的數(shù)據(jù)結(jié)構(gòu)進(jìn)行比較。
非關(guān)系型
我們?cè)谏厦嫫鋵?shí)已經(jīng)多次提到了 MongoDB 是非關(guān)系型的文檔數(shù)據(jù)庫(kù)，它完全拋棄了關(guān)系型數(shù)據(jù)庫(kù)那一套體系之后，在設(shè)計(jì)和實(shí)現(xiàn)上就非常自由，它不再需要遵循 SQL 和關(guān)系型數(shù)據(jù)庫(kù)的體系，可以更自由對(duì)特定場(chǎng)景進(jìn)行優(yōu)化，而在 MongoDB 假設(shè)的場(chǎng)景中遍歷數(shù)據(jù)并不是常見(jiàn)的需求。
mysql-innodb-b-plus-tree
MySQL 中使用 B+ 樹(shù)是因?yàn)?B+ 樹(shù)只有葉節(jié)點(diǎn)會(huì)存儲(chǔ)數(shù)據(jù)，將樹(shù)中的每一個(gè)葉節(jié)點(diǎn)通過(guò)指針連接起來(lái)就能實(shí)現(xiàn)順序遍歷，而遍歷數(shù)據(jù)在關(guān)系型數(shù)據(jù)庫(kù)中非常常見(jiàn)，所以這么選擇是完全沒(méi)有問(wèn)題的[^7]。
MongoDB 和 MySQL 在多個(gè)不同數(shù)據(jù)結(jié)構(gòu)之間選擇的最終目的就是減少查詢需要的隨機(jī) IO 次數(shù)，MySQL 認(rèn)為遍歷數(shù)據(jù)的查詢是常見(jiàn)的，所以它選擇 B+ 樹(shù)作為底層數(shù)據(jù)結(jié)構(gòu)，而舍棄了通過(guò)非葉節(jié)點(diǎn)存儲(chǔ)數(shù)據(jù)這一特性，但是 MongoDB 面對(duì)的問(wèn)題就不太一樣了：
mongodb-wiredtiger-b-tree
雖然遍歷數(shù)據(jù)的查詢是相對(duì)常見(jiàn)的，但是 MongoDB 認(rèn)為查詢單個(gè)數(shù)據(jù)記錄遠(yuǎn)比遍歷數(shù)據(jù)更加常見(jiàn)，由于 B 樹(shù)的非葉結(jié)點(diǎn)也可以存儲(chǔ)數(shù)據(jù)，所以查詢一條數(shù)據(jù)所需要的平均隨機(jī) IO 次數(shù)會(huì)比 B+ 樹(shù)少，使用 B 樹(shù)的 MongoDB 在類似場(chǎng)景中的查詢速度就會(huì)比 MySQL 快。這里并不是說(shuō) MongoDB 并不能對(duì)數(shù)據(jù)進(jìn)行遍歷，我們?cè)?MongoDB 中也可以使用范圍來(lái)查詢一批滿足對(duì)應(yīng)條件的記錄，只是需要的時(shí)間會(huì)比 MySQL 長(zhǎng)一些。
- SELECT * FROM comments WHERE created_at > '2019-01-01'
很多人看到遍歷數(shù)據(jù)的查詢想到的可能都是如上所示的范圍查詢，然而在關(guān)系型數(shù)據(jù)庫(kù)中更常見(jiàn)的其實(shí)是如下所示的 SQL —— 查詢外鍵或者某字段等于某一個(gè)值的全部記錄：
- SELECT * FROM comments WHERE post_id = 1
上述查詢其實(shí)并不是范圍查詢，它沒(méi)有使用 >、< 等表達(dá)式，但是它卻會(huì)在 comments 表中查詢一系列的記錄，如果 comments 表上有索引 post_id，那么這個(gè)查詢可能就會(huì)在索引中遍歷相應(yīng)索引，找到滿足條件的 comment，這種查詢也會(huì)受益于 MySQL B+ 樹(shù)相互連接的葉節(jié)點(diǎn)，因?yàn)樗軠p少磁盤的隨機(jī) IO 次數(shù)。
MongoDB 作為非關(guān)系型的數(shù)據(jù)庫(kù)，它從集合的設(shè)計(jì)上就使用了完全不同的方法，如果我們?nèi)匀皇褂脗鹘y(tǒng)的關(guān)系型數(shù)據(jù)庫(kù)的表設(shè)計(jì)思路來(lái)思考 MongoDB 中集合的設(shè)計(jì)，寫出類似如上所示的查詢會(huì)帶來(lái)相對(duì)比較差的性能：
- db.comments.find( { post_id: 1 } )
因?yàn)?B 樹(shù)的所有節(jié)點(diǎn)都能存儲(chǔ)數(shù)據(jù)，各個(gè)連續(xù)的節(jié)點(diǎn)之間沒(méi)有很好的辦法通過(guò)指針相連，所以上述查詢?cè)?B 樹(shù)中性能會(huì)比 B+ 樹(shù)差很多，但是這并不是一個(gè) MongoDB 中推薦的設(shè)計(jì)方法，更合適的做法其實(shí)是使用嵌入文檔，將 post 和屬于它的所有 comments 都存儲(chǔ)到一起：
- {
- "_id": "...",
- "title": "為什么 MongoDB 使用 B 樹(shù)",
- "author": "draven",
- "comments": [
- {
- "_id": "...",
- "content": "你這寫的不行"
- },
- {
- "_id": "...",
- "content": "一樓說(shuō)的對(duì)"
- }
- ]
- }
使用上述方式對(duì)數(shù)據(jù)進(jìn)行存儲(chǔ)時(shí)就不會(huì)遇到 db.comments.find( { post_id: 1 } ) 這樣的查詢了，我們只需要將 post 取出來(lái)就會(huì)獲得相關(guān)的全部評(píng)論，這種區(qū)別于傳統(tǒng)關(guān)系型數(shù)據(jù)庫(kù)的設(shè)計(jì)方式是需要所有使用 MongoDB 的開(kāi)發(fā)者重新思考的，這也是很多人使用 MongoDB 后卻發(fā)現(xiàn)性能不如 MySQL 的最大原因 —— 使用的姿勢(shì)不對(duì)。
有些讀者到這里可能會(huì)有疑問(wèn)了，既然 MongoDB 認(rèn)為查詢單個(gè)數(shù)據(jù)記錄遠(yuǎn)比遍歷數(shù)據(jù)的查詢更加常見(jiàn)，那為什么不使用哈希作為底層的數(shù)據(jù)結(jié)構(gòu)呢?
datastructures-and-query
如果我們使用哈希，那么對(duì)于所有單條記錄查詢的復(fù)雜度都會(huì)是 O(1)，但是遍歷數(shù)據(jù)的復(fù)雜度就是 O(n);如果使用 B+ 樹(shù)，那么單條記錄查詢的復(fù)雜度是 O(log n)，遍歷數(shù)據(jù)的復(fù)雜度就是 O(log n) + X，這兩種不同的數(shù)據(jù)結(jié)構(gòu)一種提供了最好的單記錄查詢性能，一種提供了最好的遍歷數(shù)據(jù)的性能，但是這都不能滿足 MongoDB 面對(duì)的場(chǎng)景 —— 單記錄查詢非常常見(jiàn)，但是對(duì)于遍歷數(shù)據(jù)也需要有相對(duì)較好的性能支持，哈希這種性能表現(xiàn)較為極端的數(shù)據(jù)結(jié)構(gòu)往往只能在簡(jiǎn)單、極端的場(chǎng)景下使用。
讀多寫少
LSM 樹(shù)是一個(gè)基于磁盤的數(shù)據(jù)結(jié)構(gòu)，它設(shè)計(jì)的主要目的是為長(zhǎng)期需要高頻率寫入操作的文件提供低成本的索引機(jī)制[^8]。無(wú)論是 B 樹(shù)還是 B+ 樹(shù)，向這些數(shù)據(jù)結(jié)構(gòu)組成的索引文件中寫入記錄都需要執(zhí)行的磁盤隨機(jī)寫，LSM 樹(shù)的優(yōu)化邏輯就是犧牲部分的讀性能，將隨機(jī)寫轉(zhuǎn)換成順序?qū)懸詢?yōu)化數(shù)據(jù)的寫入。
我們?cè)谶@篇文章不會(huì)詳細(xì)介紹為什么 LSM 樹(shù)有著較好的寫入性能，我們只是來(lái)分析為什么 WiredTiger 使用 B 樹(shù)作為默認(rèn)的數(shù)據(jù)結(jié)構(gòu)。WiredTiger 對(duì) LSM 樹(shù)和 B 樹(shù)的性能進(jìn)行了讀寫吞吐量的基準(zhǔn)測(cè)試[^9]，通過(guò)基準(zhǔn)測(cè)試得到了如下圖所示的結(jié)果，從圖中的結(jié)果我們能發(fā)現(xiàn)：
LSM_btree_Throughput
在不限制寫入的情況下;
- LSM 樹(shù)的寫入性能是 B 樹(shù)的 1.5 ~ 2 倍;
- LSM 樹(shù)的讀取性能是 B 樹(shù)的 1/6 ~ 1/3;
在限制寫入的情況下;
- LSM 樹(shù)的寫入性能與 B 樹(shù)的性能基本持平;
- LSM 樹(shù)的讀取性能是 B 樹(shù)的 1/4 ~ 1/2;
在限制寫入的情況下，每秒會(huì)寫入 30,000 條數(shù)據(jù)，從這里的分析結(jié)果來(lái)看，無(wú)論那種情況下 B 樹(shù)的讀取性能是遠(yuǎn)好于 LSM 樹(shù)的。對(duì)于大多數(shù)的 OLTP 系統(tǒng)來(lái)說(shuō)，系統(tǒng)的查詢會(huì)是寫的很多倍，所以 LSM 樹(shù)在寫入方面的優(yōu)異表現(xiàn)也沒(méi)有辦法讓它成為 MongoDB 默認(rèn)的數(shù)據(jù)格式。
總結(jié)
應(yīng)用場(chǎng)景永遠(yuǎn)都是系統(tǒng)設(shè)計(jì)時(shí)首先需要考慮的問(wèn)題，作為 NoSQL 的 MongoDB，其目標(biāo)場(chǎng)景就與更早的數(shù)據(jù)庫(kù)就有著比較大的差異，我們來(lái)簡(jiǎn)單總結(jié)一下 MongoDB 最終選擇使用 B 樹(shù)的兩個(gè)原因：
MySQL 使用 B+ 樹(shù)是因?yàn)閿?shù)據(jù)的遍歷在關(guān)系型數(shù)據(jù)庫(kù)中非常常見(jiàn)，它經(jīng)常需要處理各個(gè)表之間的關(guān)系并通過(guò)范圍查詢一些數(shù)據(jù);但是 MongoDB 作為面向文檔的數(shù)據(jù)庫(kù)，與數(shù)據(jù)之間的關(guān)系相比，它更看重以文檔為中心的組織方式，所以選擇了查詢單個(gè)文檔性能較好的 B 樹(shù)，這個(gè)選擇對(duì)遍歷數(shù)據(jù)的查詢也可以保證可以接受的時(shí)延;
LSM 樹(shù)是一種專門用來(lái)優(yōu)化寫入的數(shù)據(jù)結(jié)構(gòu)，它將隨機(jī)寫變成了順序?qū)戯@著地提高了寫入性能，但是卻犧牲了讀的效率，這與大多數(shù)場(chǎng)景需要的特點(diǎn)是不匹配的，所以 MongoDB 最終還是選擇讀取性能更好的 B 樹(shù)作為默認(rèn)的數(shù)據(jù)結(jié)構(gòu);
到最后，我們還是來(lái)看一些比較開(kāi)放的相關(guān)問(wèn)題，有興趣的讀者可以仔細(xì)思考一下下面的問(wèn)題：
BigTable、LevelDB 和 HBase 的應(yīng)用場(chǎng)景都是什么?它們的讀寫比例有多少?為什么使用 LSM 樹(shù)作為底層的數(shù)據(jù)結(jié)構(gòu)?
在設(shè)計(jì)表結(jié)構(gòu)時(shí)，MongoDB 與傳統(tǒng)的關(guān)系型數(shù)據(jù)庫(kù)有哪些區(qū)別?
如果對(duì)文章中的內(nèi)容有疑問(wèn)或者想要了解更多軟件工程上一些設(shè)計(jì)決策背后的原因，可以在博客下面留言，作者會(huì)及時(shí)回復(fù)本文相關(guān)的疑問(wèn)并選擇其中合適的主題作為后續(xù)的內(nèi)容。
[^1]: MongoDB 官方網(wǎng)站 The database for modern applications https://www.mongodb.com/
[^2]: 分布式鍵值存儲(chǔ) Dynamo 的實(shí)現(xiàn)原理 https://draveness.me/dynamo
[^3]: NoSQL 維基百科 https://en.wikipedia.org/wiki/NoSQL
[^4]: NoSQL (Not Only SQL database) https://searchdatamanagement.techtarget.com/definition/NoSQL-Not-Only-SQL
[^5]: 『淺入淺出』MongoDB 和 WiredTiger https://draveness.me/mongodb-wiredtiger
[^6]: MongoDB 中的集合(Collection)與 MySQL 中的表(Table)是差不多的概念
[^7]: 為什么 MySQL 使用 B+ 樹(shù) · Why's THE Design? https://draveness.me/whys-the-design-mysql-b-plus-tree
[^8]: The Log-Structured Merge-Tree (LSM-Tree), Patrick O'Neil, Edward Cheng, Dieter Gawlick, Elizabeth O'Neil https://www.cs.umb.edu/~poneil/lsmtree.pdf
[^9]: Btree vs LSM https://github.com/wiredtiger/wiredtiger/wiki/Btree-vs-LSM
