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