數(shù)據(jù)庫如何抵抗隨機(jī)IO的問題、方法與現(xiàn)實
隨機(jī)IO幾乎是令所有DBA談虎色變的一個問題，這個問題，往往在數(shù)據(jù)量小的時候不出現(xiàn)，在數(shù)據(jù)量超過內(nèi)存大小時，才陡然出現(xiàn)，令沒有經(jīng)驗的DBA促不及防，也令有經(jīng)驗的DBA寢食難安。
傳統(tǒng)的數(shù)據(jù)庫架構(gòu)對隨機(jī)IO幾乎沒有還手之力。傳統(tǒng)數(shù)據(jù)庫的核心通常是頁級緩存、B+樹、堆或索引組織表，這些機(jī)制，對隨機(jī)IO的抵抗能力，都無一例外的可 悲的差。頁級緩存有很強(qiáng)的“連坐”效應(yīng)，就是為了要緩存一條有價值的記錄，順帶可能要同時緩存百條無價值的記錄。傳統(tǒng)上這一點(diǎn)自豪的稱之為 locality，是用來減少IO的，但往往會導(dǎo)致內(nèi)存緩存的利用率很差。在記錄的級別，應(yīng)用的訪問模式通常符合Zipf分布，其中10%的記錄所占的訪 問概率超過90%。如果我們用記錄級的緩存，用相當(dāng)于數(shù)據(jù)量10%的內(nèi)存，就可以消除90%的IO，但用頁級緩存，這10%的熱點(diǎn)記錄，很可能就分布在 70%的頁面上，這樣同樣10%的內(nèi)存，很可能只能消除可悲的30%的IO。B+樹的情況也好不了，如果索引大于內(nèi)存量，每次隨機(jī)的索引搜索、插入和刪 除，幾乎都將帶來一次隨機(jī)IO(假設(shè)索引的非葉節(jié)點(diǎn)都在內(nèi)存中)。
新的SSD硬件可以緩解隨機(jī)讀問題，但對隨機(jī)寫依然是無能為力。SSD的技術(shù)比較成熟了，期望它哪一天能魔術(shù)般的也搞定隨機(jī)寫，是不現(xiàn)實的。但我們可以從數(shù)據(jù)庫架構(gòu)上來想辦法，謝天謝地，其實有很多辦法，雖然未必能馬上就用上。
先說記錄的隨機(jī)IO。之前已經(jīng)說過，用記錄級的緩存是很好的，我們NTSE的測試 表 明這一招很有效。但似乎不太有公開的數(shù)據(jù)庫支持類似的功能。煺而求其次，大家可以用Memcached，但兩者有重大區(qū)別。用Memcached時，很難 保證Memcached與數(shù)據(jù)庫的一致性，除非用數(shù)據(jù)庫事務(wù)來保證，但這樣會導(dǎo)致在兩個系統(tǒng)之間進(jìn)行每個事務(wù)毫秒級的鎖定。雖然數(shù)據(jù)庫內(nèi)置的記錄級緩存也 需要用某種加鎖機(jī)制來保證一致性，但這個鎖定時間是微秒級的，并發(fā)度不可同日而語。但最重要的一點(diǎn)是，Memcached通常只能消除隨機(jī)讀IO，對隨機(jī) 寫無能為力。而數(shù)據(jù)庫內(nèi)置的記錄級緩存，則可以很好的解決這個問題。數(shù)據(jù)庫內(nèi)置記錄緩存的設(shè)計，常用的有幾招：
1、最基本的一招是，如果要訪問的 記錄在記錄緩存中，就不去讀底層的堆文件。當(dāng)然這是廢話，如果不這樣，那還叫記錄級緩存嗎?但如果僅僅是這樣，記錄緩存跟Memcached是一樣的，還 不如用Memcached，更靈活。但接下來數(shù)據(jù)庫內(nèi)置記錄級緩存的招數(shù)，基本上都是Memcached搞不定的。
2、如果僅僅如果更新命中了記錄緩存中的記錄，則只更新記錄緩存，不更新底層的堆等存儲。具體細(xì)化下來有UPDATE和DELETE兩種，NTSE暫時只能搞定UPDATE;
3、 記錄緩存里的東西，總是要有周期的持久化的，否則恢復(fù)時間不能保證。這個第叁招，就是持久化也就是把記錄緩存中的臟記錄dump出去的時候，不要去更新對 應(yīng)的堆中的記錄，否則短時間就會爆發(fā)大規(guī)模的隨機(jī)讀寫，做法應(yīng)該是像內(nèi)存數(shù)據(jù)庫那樣，把臟記錄用順序?qū)慖O dump出來。NTSE就是這么做的，刷記錄緩存臟記錄時，我們先看看對應(yīng)的頁面在頁面緩存中在不在，在，則更新堆，否則順序dump到log中。
4、在更新時，可以只把UPDATE后的后像插入到記錄緩存中，根本不去讀塬來的記錄，當(dāng)然這個要看具體情況，如果后像是依賴于前像的那這招就不靈，但很多時候是可以用的，比如根據(jù)主鍵找到一條記錄，不管3721把其中一些屬性改掉。NTSE暫時還搞不定這招，有待改進(jìn)。
記錄緩存的這4招，消除數(shù)據(jù)庫中記錄操作帶來的隨機(jī)IO是很有效的。遺憾的是這不是必殺技，如果記錄的訪問確實的純隨機(jī)的就會失效，幸運(yùn)的是這樣的情況不常出現(xiàn)。
索 引的隨機(jī)IO問題要更復(fù)雜一點(diǎn)。我們簡單點(diǎn)，只說涉及到單個索引項的操作。傳統(tǒng)的B+樹，無論是搜索、插入還是刪除(更新相當(dāng)于插入+刪除，就不額外討論 了)，理論上都是O(log(B)(N))次IO(其中B是頁面包含的鍵值數(shù)，N是總鍵值數(shù))，但實際情況下可以假設(shè)非葉節(jié)點(diǎn)都在內(nèi)存中，因此是1次 IO。磁盤一般只能有每秒幾百次隨機(jī)IO，因此對大的索引，每秒只能有幾百次操作，這個性能真是低的可憐。B+樹是70年代的老怪物，但直到今天，大多數(shù) 數(shù)據(jù)庫里仍然用得是它，但實際上，有比傳統(tǒng)B+樹更能對付隨機(jī)IO的東西。
1996年，P O'Neil等提出的 LSM-Tree 是一個重大 突 破。LSM-Tree主要有兩種變形，最簡單的LSM-Tree，是一個內(nèi)存中的小索引加上外存中的大索引，更新先緩存在小索引中，再批量更新到大索引， 這樣就有望合并對屬性同一頁面的多次更新的IO。復(fù)雜的LSM-Tree，是劃分為多個level的很多的小索引，每個level的大小，近似的是前一個 level大小的r倍，如果一個level有r個小索引，則合并形成一個下一level的較大的索引，這樣隨機(jī)插入或刪除的平均IO開銷可以降低到 log(N)/B次，是一個很大的提升。但帶來的問題是，搜索的時候，就要搜索這么多個小索引，而這樣的索引會有O(log(N/B))個，那是可能有幾 十個，搜索的性能就可能下降幾十倍，這往往也帶來問題。LSM-Tree已經(jīng)有不少的現(xiàn)實應(yīng)用，BigTable、Cassandra、Lucene等這 些用的是復(fù)雜的那種LSM-Tree，InnoDB的change buffer可以說是那種一大一小的簡單LSM-Tree。NTSE想在做多版本事務(wù)的時候順便實現(xiàn)change buffer。
2000年，MA Bender等提出的Cache Oblivious B-Tree 是第二個重大突破。這個跟LSM-Tree有些類似，也是索引從小到大分成相鄰大小翻倍的多個索引，因此隨機(jī)插入或刪除的平均IO開銷也是log(N)/B次，但它用了Fractional Cascading 的技術(shù)，使得搜索的性能較傳統(tǒng)B+樹相關(guān)不多。雖然論文發(fā)表了10年了，這種索引似乎現(xiàn)在只有TokuDB 一家實現(xiàn)，它是稱之為Fractal Tree。我們拿來試了試，效果果然出奇的好。
有沒有可能將來搞出一個比Fractal Tree更好的東西呢，遺憾的是如果硬件不發(fā)生根本改變，已經(jīng)證明Fractal Tree已經(jīng)是最理想的了。
但LSM-Tree或Fractal Tree，其實只是消除索引的隨機(jī)插入和刪除帶來的隨機(jī)IO，對隨機(jī)搜索沒什么幫助。這個剩下的索引的隨機(jī)搜索問題比較復(fù)雜，要分解來看。一種是真正的來自于應(yīng)用需求的搜索，另一種是檢查唯一性帶來的搜索。這兩種處理方法是不同的。
對于真正的來自于應(yīng)用需求的搜索，處理還得借助于記錄級緩存類似的技術(shù)，但這時變成索引項的緩存了。InnoDB中的Adaptive Hash Index就是這個東西。但對檢查唯一性帶來的搜索，Bloomfilter是個好方法，經(jīng)常可以消除98%以上不必要的檢查。所以BigTable里就 用。但對傳統(tǒng)B+樹由于索引是實時更新的，Bloomfilter不好用，對Fractal Tree，索引是在merge的時候再批量更新的，可以用Bloomfilter。我們試了TokuDB，根據(jù)性能表明看，它對索引性索引的隨機(jī)插入，也 能輕松對付，估計也是用了Bloomfilter類似的技術(shù)。
因此，我們可以看到，隨機(jī)IO這個老大難的問題，其實還是有不少的技術(shù)可以 解決的。然而，現(xiàn)實是悲摧的，我們經(jīng)常在用的主流數(shù)據(jù)庫，無論是商業(yè)的Oracle、DB2、SQL Server，還是開源的MySQL、PostgreSQL，都基本上還在用最老土的技術(shù)，InnoDB里搞了一點(diǎn)change buffer，就能讓人津津樂道半天。NoSQL系統(tǒng)走在前面，用上了LSM-Tree，但也并不是***進(jìn)的，搜索的性能經(jīng)常令人擔(dān)憂。在索引這方 面，TokuDB走在前面，但還沒為大眾接受。記錄方面，不清楚為什么大家不作記錄級緩存，這不是很難的事，莫非認(rèn)為用Memcached就可以了，“因 為善小而不為”?
相信未來，總有改善的一天。
【編輯推薦】
