怎么實(shí)現(xiàn)數(shù)據(jù)庫(kù)內(nèi)部存儲(chǔ)結(jié)構(gòu)探索

?我一直以來(lái)都在不斷的研究和探索數(shù)據(jù)庫(kù)的內(nèi)部存儲(chǔ)原理。我認(rèn)為這個(gè)話題是非常巨大且復(fù)雜的，我努力所學(xué)也只占其千萬(wàn)分之一。我將會(huì)講解一些數(shù)據(jù)庫(kù)存儲(chǔ)的內(nèi)部機(jī)制，數(shù)據(jù)庫(kù)是如何進(jìn)行優(yōu)化操作來(lái)提供驚人速度及其優(yōu)勢(shì)和缺點(diǎn)。

?當(dāng)我們談起數(shù)據(jù)庫(kù)內(nèi)部存儲(chǔ)結(jié)構(gòu)時(shí)，人們都會(huì)想到B樹(shù)或者B+樹(shù)，但是我們?cè)谶@里并不會(huì)談?wù)撨@些數(shù)據(jù)結(jié)構(gòu)的原理，我們會(huì)展示這些數(shù)據(jù)結(jié)構(gòu)為什么適合作為數(shù)據(jù)庫(kù)存儲(chǔ)的內(nèi)部結(jié)構(gòu)以及使用這些數(shù)據(jù)結(jié)構(gòu)的目的。

?傳統(tǒng)的關(guān)系型數(shù)據(jù)將數(shù)據(jù)以B樹(shù)的形式存儲(chǔ)在磁盤(pán)上，它們也會(huì)在RAM上使用B樹(shù)維護(hù)這些數(shù)據(jù)的索引，來(lái)保證更快的訪問(wèn)速度。插入的行存儲(chǔ)在B樹(shù)的葉子節(jié)點(diǎn)上，所有的中間節(jié)點(diǎn)用來(lái)存儲(chǔ)用于導(dǎo)航查詢語(yǔ)句的原數(shù)據(jù)。

    因此，當(dāng)有數(shù)以百萬(wàn)計(jì)的數(shù)據(jù)被插入到數(shù)據(jù)庫(kù)中時(shí)，索引和數(shù)據(jù)存儲(chǔ)會(huì)變得十分大。因此，為了快速的訪問(wèn)，需要從磁盤(pán)中加載所有數(shù)據(jù)到內(nèi)存，但是RAM一般沒(méi)有這么大的空間來(lái)存儲(chǔ)所有的數(shù)據(jù)。因此，數(shù)據(jù)庫(kù)必須從磁盤(pán)中讀取部分?jǐn)?shù)據(jù)。這種加載數(shù)據(jù)的場(chǎng)景如下圖所示：

 

?磁盤(pán)I/O花費(fèi)的時(shí)間很長(zhǎng)，是影響數(shù)據(jù)庫(kù)性能的主要原因之一。B樹(shù)是支持隨機(jī)讀寫(xiě)，in-place 替換,十分緊湊并且自平衡的數(shù)據(jù)結(jié)構(gòu)，但是受磁盤(pán)I/O速度的限制。隨機(jī)讀意味著當(dāng)訪問(wèn)磁盤(pán)數(shù)據(jù)時(shí)，磁頭必須移動(dòng)到柱面上的指定位置，因此會(huì)消耗大量時(shí)間。

?B樹(shù)被設(shè)計(jì)為使用block的形式存儲(chǔ)數(shù)據(jù)，因?yàn)椴僮飨到y(tǒng)讀取讀取一個(gè)block的數(shù)據(jù)要比讀取單獨(dú)字節(jié)數(shù)據(jù)要快的多。MySQL的InnoDB存儲(chǔ)引擎的block大小為16KB。這意味著每次你讀取或者寫(xiě)入數(shù)據(jù)時(shí)，大小為16KB的block數(shù)據(jù)會(huì)被從磁盤(pán)加載到RAM中，它會(huì)被寫(xiě)入新的數(shù)據(jù)，并且再次寫(xiě)回到磁盤(pán)上。假設(shè)數(shù)據(jù)庫(kù)表的每一行數(shù)據(jù)為128字節(jié)（實(shí)際大小會(huì)變化），一個(gè)block（葉子節(jié)點(diǎn)）為16KB，存儲(chǔ)了(16 * 1024) / 128 = 128行數(shù)據(jù)。

    B樹(shù)的高度一般小于10，但是每一層的節(jié)點(diǎn)數(shù)量卻很多，由此可以管理數(shù)以萬(wàn)計(jì)的數(shù)據(jù)?；谏鲜鎏匦?，B樹(shù)適合作為數(shù)據(jù)內(nèi)部存儲(chǔ)結(jié)構(gòu)。

?因此，在B樹(shù)上進(jìn)行讀操作是相對(duì)來(lái)說(shuō)比較快速的，因?yàn)樵摬僮髦恍枰闅v一些節(jié)點(diǎn)并且進(jìn)行較少次數(shù)的磁盤(pán)I/O請(qǐng)求。而且，范圍查詢因?yàn)榭梢詫?shù)據(jù)以block的形式進(jìn)行獲取和操作而速度更快。你可以進(jìn)行下列操作來(lái)讓基于B-Tree的數(shù)據(jù)庫(kù)性能更好：

    減少索引節(jié)點(diǎn)數(shù)量：這是提升關(guān)系型數(shù)據(jù)庫(kù)性能的常用策略。索引越多，插入和更新操作需要管理的索引數(shù)量也越多。當(dāng)數(shù)據(jù)庫(kù)數(shù)據(jù)運(yùn)行時(shí)間越來(lái)越久時(shí)，就需要?jiǎng)h除一些老舊或者無(wú)用的索引，并且謹(jǐn)慎地添加新的索引。但是你也要注意，索引越少意味著查詢性能越差，你需要在查詢性能和插入更新性能之間進(jìn)行取舍(譯者注：可以考慮數(shù)據(jù)庫(kù)的讀寫(xiě)比率)。

    順序插入：如果你能以主鍵大小為基礎(chǔ)進(jìn)行大量數(shù)據(jù)的順序插入，那么插入數(shù)據(jù)的速度會(huì)十分的快。因?yàn)樵诓迦脒^(guò)程中，插入行所屬的block已經(jīng)在內(nèi)存中，所以數(shù)據(jù)庫(kù)可以直接將行插入到內(nèi)存的數(shù)據(jù)結(jié)構(gòu)中，然后通過(guò)一次磁盤(pán)I/O提交到數(shù)磁盤(pán)中。當(dāng)然，這些都取決于數(shù)據(jù)庫(kù)的具體實(shí)現(xiàn)，但是我認(rèn)為現(xiàn)代的數(shù)據(jù)庫(kù)一般都會(huì)進(jìn)行類似的優(yōu)化。

?但是B樹(shù)并不是適合所有情景的最優(yōu)存儲(chǔ)結(jié)構(gòu)。對(duì)B樹(shù)結(jié)構(gòu)的寫(xiě)操作性能很差，比隨機(jī)讀還要差，因?yàn)閿?shù)據(jù)庫(kù)必須從磁盤(pán)中加載數(shù)據(jù)對(duì)應(yīng)的頁(yè)，然后修改它并沖洗新寫(xiě)入到磁盤(pán)中。隨機(jī)寫(xiě)入時(shí)平均有100字節(jié)每秒寫(xiě)入速度，這個(gè)限制是由于磁盤(pán)的基本工作原理。

    事實(shí)上，簡(jiǎn)單依賴于緩存的使用，索引搜索和更多的內(nèi)存可以處理更多的讀操作，但是應(yīng)付更多的寫(xiě)操作就比較麻煩。當(dāng)你需要寫(xiě)入或更新大量的數(shù)據(jù)時(shí)，B樹(shù)結(jié)構(gòu)并不是最正確的選擇。長(zhǎng)久以來(lái)，傳統(tǒng)數(shù)據(jù)庫(kù)進(jìn)行了大量的優(yōu)化，比如說(shuō)InnoDB嘗試使用緩沖來(lái)減少磁盤(pán)I/O操作。具體操作如下所示：

 

?數(shù)據(jù)庫(kù)寫(xiě)操作可以通過(guò)提升磁盤(pán)的帶寬來(lái)提升速度，但是目前關(guān)系型數(shù)據(jù)庫(kù)都沒(méi)有這樣做。而且關(guān)系型數(shù)據(jù)庫(kù)管理系統(tǒng)一般都是十分復(fù)雜的，因?yàn)樗麄兪褂面i，并發(fā)，ACID事務(wù)等操作，這使得寫(xiě)入操作更加復(fù)雜。

?當(dāng)今信息時(shí)代，在比如消息、聊天、實(shí)時(shí)通訊和物聯(lián)網(wǎng)等客戶為中心的服務(wù)和大量無(wú)結(jié)構(gòu)化數(shù)據(jù)的分布式系統(tǒng)中，每小時(shí)都會(huì)進(jìn)行數(shù)百萬(wàn)計(jì)的寫(xiě)入操作。因此，這些系統(tǒng)是以寫(xiě)為主的系統(tǒng)，為了迎合這些系統(tǒng)的需要，數(shù)據(jù)庫(kù)需要能夠擁有快速插入數(shù)據(jù)的能力。典型的數(shù)據(jù)庫(kù)并不能很好的滿足類似的場(chǎng)景，因?yàn)樗鼈儫o(wú)法應(yīng)付高可用性，盡可能的最終一致性，無(wú)格式數(shù)據(jù)的靈活性和低延遲等要求。

?LSM樹(shù)(Log Structured Merge Tree)應(yīng)運(yùn)而生。LSM并不是一種類似于B樹(shù)的數(shù)據(jù)結(jié)構(gòu)，而是一個(gè)系統(tǒng)。在LSM系統(tǒng)中，并沒(méi)有對(duì)數(shù)據(jù)的in-place替換；一旦數(shù)據(jù)被寫(xiě)入磁盤(pán)，它就再也不會(huì)被修改。顯然，它是一種只能在末尾添加(append only)的寫(xiě)入系統(tǒng)。一些日志結(jié)構(gòu)的文件系統(tǒng)比如ext3/4也使用類似的原理。

    因此，該系統(tǒng)就如同順序的記錄數(shù)據(jù)日志一般?；旧?，LSM系統(tǒng)利用了順序?qū)懙膬?yōu)勢(shì)。傳統(tǒng)的磁盤(pán)驅(qū)動(dòng)的寫(xiě)操作最高可以達(dá)到100MB/s，現(xiàn)代的固態(tài)硬盤(pán)在順序?qū)憰r(shí)的速度則更快。事實(shí)上，固態(tài)硬盤(pán)驅(qū)動(dòng)有一些內(nèi)置的并行機(jī)制來(lái)讓它可以同時(shí)寫(xiě)入16到32MB的數(shù)據(jù)。LSM樹(shù)和固態(tài)硬盤(pán)的特性十分匹配。順序?qū)懸入S機(jī)寫(xiě)快很多。

?為了正確地理解上述場(chǎng)景，讓我們簡(jiǎn)單的看一下Facebook的Cassandra數(shù)據(jù)庫(kù)是如何使用LSM原則的。

 

?Cassandra或者任何LSM系統(tǒng)都會(huì)維護(hù)一個(gè)或者多個(gè)用來(lái)在寫(xiě)入磁盤(pán)前存儲(chǔ)數(shù)據(jù)的內(nèi)存數(shù)據(jù)結(jié)構(gòu)(如上圖中的memtable)，比如說(shuō)子平衡樹(shù)(AVL)、紅黑樹(shù)、B樹(shù)或者跳表。該內(nèi)存數(shù)據(jù)結(jié)構(gòu)維護(hù)一個(gè)排序的數(shù)據(jù)集。

    不同的LSM實(shí)現(xiàn)互使用不同的數(shù)據(jù)結(jié)構(gòu)來(lái)適應(yīng)不同的需求，并不存在標(biāo)準(zhǔn)的LSM實(shí)現(xiàn)。當(dāng)內(nèi)存中存儲(chǔ)的數(shù)據(jù)超過(guò)配置的閾值時(shí)，內(nèi)存中存儲(chǔ)的數(shù)據(jù)就會(huì)被放置在將會(huì)被寫(xiě)入磁盤(pán)的隊(duì)列中。為了flush數(shù)據(jù)，Cassandra順序地寫(xiě)入排序的數(shù)據(jù)到磁盤(pán)中。

    磁盤(pán)維護(hù)一個(gè)叫做“SSTable”(Sorted Strings Table)的數(shù)據(jù)結(jié)構(gòu)，該數(shù)據(jù)就是寫(xiě)入文件數(shù)據(jù)的有序的快照，SSTable是不可變的。LSM系統(tǒng)可以管理磁盤(pán)上的多個(gè)文件。

?因此，如果數(shù)據(jù)在內(nèi)存中沒(méi)有被發(fā)現(xiàn)，Cassandra需要掃描所有磁盤(pán)上的SSTables來(lái)搜索該數(shù)據(jù)。因此，Cassandra的讀操作相對(duì)來(lái)說(shuō)要比寫(xiě)操作慢，但是這里有一些可以處理的方法。Cassandra或者其他LSM系統(tǒng)會(huì)在后臺(tái)運(yùn)行壓縮程序來(lái)減少SSTable的數(shù)量。壓縮程序?qū)STable進(jìn)行歸并排序，在新的SSTable找那個(gè)插入新的排序數(shù)據(jù)并且刪除老的SSTables。但是使用壓縮程序有時(shí)候無(wú)法應(yīng)付數(shù)據(jù)庫(kù)中數(shù)以百萬(wàn)計(jì)的更新操作。

    因此，一些概率數(shù)據(jù)結(jié)構(gòu)(probabilistic data structures)比如Bloom filters被應(yīng)用來(lái)快速判斷是否一些數(shù)據(jù)存在于SSTable。Bloom filters十分適合對(duì)內(nèi)存中的數(shù)據(jù)進(jìn)行判斷，因?yàn)樗枰M(jìn)行大量的隨機(jī)查詢來(lái)進(jìn)行數(shù)據(jù)是否存在的概率性判斷。Bloom filters算法可以極大地減少遍歷查詢SSTables的花費(fèi)。因此，LSM系統(tǒng)解決了在大數(shù)據(jù)中寫(xiě)操作需要花費(fèi)大量時(shí)間的問(wèn)題。

    LSM系統(tǒng)也有Read amplification的問(wèn)題-會(huì)讀取出比它實(shí)際需要更多的數(shù)據(jù)。因此，還有介于B Tree和LSM Tree之間的解決方法來(lái)給出我們最優(yōu)（不一定準(zhǔn)確）的讀寫(xiě)效率嗎？

?Fractal Tree Index是基于B-Tree的數(shù)據(jù)結(jié)構(gòu)。依據(jù)開(kāi)發(fā)人員給出的benchmark，該數(shù)據(jù)結(jié)構(gòu)有比B-Tree更優(yōu)良的性能。Fractal tree支持在非葉節(jié)點(diǎn)上的信息緩存。MySQL的高性能存儲(chǔ)引擎Tokudb就使用了Fractal tree。

 

?如上圖所示，在Fractal Tree中，你進(jìn)行的添加列，刪除列，插入，更新等任何操作都會(huì)被當(dāng)做操作消息存儲(chǔ)在非葉節(jié)點(diǎn)上。由于操作只是被簡(jiǎn)單地存儲(chǔ)在緩存或者任何次級(jí)索引緩存(secondary index buffer)中，所以，所有的操作都會(huì)被迅速執(zhí)行結(jié)束。

    當(dāng)某一個(gè)節(jié)點(diǎn)的緩存滿了之后，這些操作消息會(huì)依次從根節(jié)點(diǎn)，經(jīng)過(guò)非葉節(jié)點(diǎn)，向葉節(jié)點(diǎn)進(jìn)行傳遞。葉節(jié)點(diǎn)仍然存儲(chǔ)著真實(shí)數(shù)據(jù)。當(dāng)進(jìn)行讀時(shí)，讀操作會(huì)考慮查詢路徑節(jié)點(diǎn)上的所有操作消息來(lái)獲取真實(shí)的數(shù)據(jù)狀態(tài)。但是由于tokudb會(huì)盡力將所有非葉節(jié)點(diǎn)緩存在內(nèi)存中，所以這一過(guò)程也很快。

?tokubd中的block最大可以達(dá)到4MB，而不是InnoDB中的16KB。這樣的大小可以允許一次I/O操作時(shí)加載或?qū)懟馗嗟臄?shù)據(jù)，這也有助于一次壓縮更多數(shù)據(jù)來(lái)減少磁盤(pán)上數(shù)據(jù)的存儲(chǔ)大小。

    因此，tokudb強(qiáng)調(diào)借助更大的block大小能夠?qū)崿F(xiàn)更好的數(shù)據(jù)壓縮和更少的磁盤(pán)I/O。tokudb宣稱它們的存儲(chǔ)引擎比InnoDB更快,提供比InnoDB更快的讀寫(xiě)吞吐,并且tokudb也宣稱自己有更少的碎片(fragmentation)問(wèn)題，它也支持多集群索引等。下圖是benchmark的相關(guān)統(tǒng)計(jì)圖：

 

?只有你系統(tǒng)中的benchmark可以幫助你判斷正確的數(shù)據(jù)點(diǎn)和需求解決方案。但是MySQL的存儲(chǔ)引擎會(huì)持續(xù)地不斷改進(jìn)和支持新出現(xiàn)的需求。LSM樹(shù)是為了高寫(xiě)入場(chǎng)景的系統(tǒng)，然而B(niǎo)樹(shù)是為了傳統(tǒng)的場(chǎng)景應(yīng)用。Fractal樹(shù)的索引改進(jìn)了B樹(shù)索引存在的一些缺陷。因此，未來(lái)會(huì)不斷地出現(xiàn)技術(shù)上的革新，包括數(shù)據(jù)庫(kù)存儲(chǔ)技術(shù)，硬件，磁盤(pán)驅(qū)動(dòng)和操作系統(tǒng)，讓我們拭目以待。