隨機(jī)IO幾乎是令所有DBA談虎色變的一個(gè)問(wèn)題，這個(gè)問(wèn)題，往往在數(shù)據(jù)量小的時(shí)候不出現(xiàn)，在數(shù)據(jù)量超過(guò)內(nèi)存大小時(shí)，才陡然出現(xiàn)，令沒(méi)有經(jīng)驗(yàn)的DBA促不及防，也令有經(jīng)驗(yàn)的DBA寢食難安。

傳統(tǒng)的數(shù)據(jù)庫(kù)架構(gòu)對(duì)隨機(jī)IO幾乎沒(méi)有還手之力。傳統(tǒng)數(shù)據(jù)庫(kù)的核心通常是頁(yè)級(jí)緩存、B+樹(shù)、堆或索引組織表，這些機(jī)制，對(duì)隨機(jī)IO的抵抗能力，都無(wú)一例外的可 悲的差。頁(yè)級(jí)緩存有很強(qiáng)的“連坐”效應(yīng)，就是為了要緩存一條有價(jià)值的記錄，順帶可能要同時(shí)緩存百條無(wú)價(jià)值的記錄。傳統(tǒng)上這一點(diǎn)自豪的稱之為 locality，是用來(lái)減少I(mǎi)O的，但往往會(huì)導(dǎo)致內(nèi)存緩存的利用率很差。在記錄的級(jí)別，應(yīng)用的訪問(wèn)模式通常符合Zipf分布，其中10%的記錄所占的訪 問(wèn)概率超過(guò)90%。如果我們用記錄級(jí)的緩存，用相當(dāng)于數(shù)據(jù)量10%的內(nèi)存，就可以消除90%的IO，但用頁(yè)級(jí)緩存，這10%的熱點(diǎn)記錄，很可能就分布在 70%的頁(yè)面上，這樣同樣10%的內(nèi)存，很可能只能消除可悲的30%的IO。B+樹(shù)的情況也好不了，如果索引大于內(nèi)存量，每次隨機(jī)的索引搜索、插入和刪 除，幾乎都將帶來(lái)一次隨機(jī)IO(假設(shè)索引的非葉節(jié)點(diǎn)都在內(nèi)存中)。

新的SSD硬件可以緩解隨機(jī)讀問(wèn)題，但對(duì)隨機(jī)寫(xiě)依然是無(wú)能為力。SSD的技術(shù)比較成熟了，期望它哪一天能魔術(shù)般的也搞定隨機(jī)寫(xiě)，是不現(xiàn)實(shí)的。但我們可以從數(shù)據(jù)庫(kù)架構(gòu)上來(lái)想辦法，謝天謝地，其實(shí)有很多辦法，雖然未必能馬上就用上。

先說(shuō)記錄的隨機(jī)IO。之前已經(jīng)說(shuō)過(guò)，用記錄級(jí)的緩存是很好的，我們NTSE的測(cè)試 表 明這一招很有效。但似乎不太有公開(kāi)的數(shù)據(jù)庫(kù)支持類似的功能。煺而求其次，大家可以用Memcached，但兩者有重大區(qū)別。用Memcached時(shí)，很難 保證Memcached與數(shù)據(jù)庫(kù)的一致性，除非用數(shù)據(jù)庫(kù)事務(wù)來(lái)保證，但這樣會(huì)導(dǎo)致在兩個(gè)系統(tǒng)之間進(jìn)行每個(gè)事務(wù)毫秒級(jí)的鎖定。雖然數(shù)據(jù)庫(kù)內(nèi)置的記錄級(jí)緩存也 需要用某種加鎖機(jī)制來(lái)保證一致性，但這個(gè)鎖定時(shí)間是微秒級(jí)的，并發(fā)度不可同日而語(yǔ)。但最重要的一點(diǎn)是，Memcached通常只能消除隨機(jī)讀IO，對(duì)隨機(jī) 寫(xiě)無(wú)能為力。而數(shù)據(jù)庫(kù)內(nèi)置的記錄級(jí)緩存，則可以很好的解決這個(gè)問(wèn)題。數(shù)據(jù)庫(kù)內(nèi)置記錄緩存的設(shè)計(jì)，常用的有幾招：

1、最基本的一招是，如果要訪問(wèn)的 記錄在記錄緩存中，就不去讀底層的堆文件。當(dāng)然這是廢話，如果不這樣，那還叫記錄級(jí)緩存嗎?但如果僅僅是這樣，記錄緩存跟Memcached是一樣的，還 不如用Memcached，更靈活。但接下來(lái)數(shù)據(jù)庫(kù)內(nèi)置記錄級(jí)緩存的招數(shù)，基本上都是Memcached搞不定的。

2、如果僅僅如果更新命中了記錄緩存中的記錄，則只更新記錄緩存，不更新底層的堆等存儲(chǔ)。具體細(xì)化下來(lái)有UPDATE和DELETE兩種，NTSE暫時(shí)只能搞定UPDATE;

3、 記錄緩存里的東西，總是要有周期的持久化的，否則恢復(fù)時(shí)間不能保證。這個(gè)第叁招，就是持久化也就是把記錄緩存中的臟記錄dump出去的時(shí)候，不要去更新對(duì) 應(yīng)的堆中的記錄，否則短時(shí)間就會(huì)爆發(fā)大規(guī)模的隨機(jī)讀寫(xiě)，做法應(yīng)該是像內(nèi)存數(shù)據(jù)庫(kù)那樣，把臟記錄用順序?qū)慖O dump出來(lái)。NTSE就是這么做的，刷記錄緩存臟記錄時(shí)，我們先看看對(duì)應(yīng)的頁(yè)面在頁(yè)面緩存中在不在，在，則更新堆，否則順序dump到log中。

4、在更新時(shí)，可以只把UPDATE后的后像插入到記錄緩存中，根本不去讀塬來(lái)的記錄，當(dāng)然這個(gè)要看具體情況，如果后像是依賴于前像的那這招就不靈，但很多時(shí)候是可以用的，比如根據(jù)主鍵找到一條記錄，不管3721把其中一些屬性改掉。NTSE暫時(shí)還搞不定這招，有待改進(jìn)。

記錄緩存的這4招，消除數(shù)據(jù)庫(kù)中記錄操作帶來(lái)的隨機(jī)IO是很有效的。遺憾的是這不是必殺技，如果記錄的訪問(wèn)確實(shí)的純隨機(jī)的就會(huì)失效，幸運(yùn)的是這樣的情況不常出現(xiàn)。

索 引的隨機(jī)IO問(wèn)題要更復(fù)雜一點(diǎn)。我們簡(jiǎn)單點(diǎn)，只說(shuō)涉及到單個(gè)索引項(xiàng)的操作。傳統(tǒng)的B+樹(shù)，無(wú)論是搜索、插入還是刪除(更新相當(dāng)于插入+刪除，就不額外討論 了)，理論上都是O(log(B)(N))次IO(其中B是頁(yè)面包含的鍵值數(shù)，N是總鍵值數(shù))，但實(shí)際情況下可以假設(shè)非葉節(jié)點(diǎn)都在內(nèi)存中，因此是1次 IO。磁盤(pán)一般只能有每秒幾百次隨機(jī)IO，因此對(duì)大的索引，每秒只能有幾百次操作，這個(gè)性能真是低的可憐。B+樹(shù)是70年代的老怪物，但直到今天，大多數(shù) 數(shù)據(jù)庫(kù)里仍然用得是它，但實(shí)際上，有比傳統(tǒng)B+樹(shù)更能對(duì)付隨機(jī)IO的東西。

1996年，P O'Neil等提出的 LSM-Tree 是一個(gè)重大 突 破。LSM-Tree主要有兩種變形，最簡(jiǎn)單的LSM-Tree，是一個(gè)內(nèi)存中的小索引加上外存中的大索引，更新先緩存在小索引中，再批量更新到大索引， 這樣就有望合并對(duì)屬性同一頁(yè)面的多次更新的IO。復(fù)雜的LSM-Tree，是劃分為多個(gè)level的很多的小索引，每個(gè)level的大小，近似的是前一個(gè) level大小的r倍，如果一個(gè)level有r個(gè)小索引，則合并形成一個(gè)下一level的較大的索引，這樣隨機(jī)插入或刪除的平均IO開(kāi)銷可以降低到 log(N)/B次，是一個(gè)很大的提升。但帶來(lái)的問(wèn)題是，搜索的時(shí)候，就要搜索這么多個(gè)小索引，而這樣的索引會(huì)有O(log(N/B))個(gè)，那是可能有幾 十個(gè)，搜索的性能就可能下降幾十倍，這往往也帶來(lái)問(wèn)題。LSM-Tree已經(jīng)有不少的現(xiàn)實(shí)應(yīng)用，BigTable、Cassandra、Lucene等這 些用的是復(fù)雜的那種LSM-Tree，InnoDB的change buffer可以說(shuō)是那種一大一小的簡(jiǎn)單LSM-Tree。NTSE想在做多版本事務(wù)的時(shí)候順便實(shí)現(xiàn)change buffer。

2000年，MA Bender等提出的Cache Oblivious B-Tree 是第二個(gè)重大突破。這個(gè)跟LSM-Tree有些類似，也是索引從小到大分成相鄰大小翻倍的多個(gè)索引，因此隨機(jī)插入或刪除的平均IO開(kāi)銷也是log(N)/B次，但它用了Fractional Cascading 的技術(shù)，使得搜索的性能較傳統(tǒng)B+樹(shù)相關(guān)不多。雖然論文發(fā)表了10年了，這種索引似乎現(xiàn)在只有TokuDB 一家實(shí)現(xiàn)，它是稱之為Fractal Tree。我們拿來(lái)試了試，效果果然出奇的好。

有沒(méi)有可能將來(lái)搞出一個(gè)比Fractal Tree更好的東西呢，遺憾的是如果硬件不發(fā)生根本改變，已經(jīng)證明Fractal Tree已經(jīng)是最理想的了。

但LSM-Tree或Fractal Tree，其實(shí)只是消除索引的隨機(jī)插入和刪除帶來(lái)的隨機(jī)IO，對(duì)隨機(jī)搜索沒(méi)什么幫助。這個(gè)剩下的索引的隨機(jī)搜索問(wèn)題比較復(fù)雜，要分解來(lái)看。一種是真正的來(lái)自于應(yīng)用需求的搜索，另一種是檢查唯一性帶來(lái)的搜索。這兩種處理方法是不同的。

對(duì)于真正的來(lái)自于應(yīng)用需求的搜索，處理還得借助于記錄級(jí)緩存類似的技術(shù)，但這時(shí)變成索引項(xiàng)的緩存了。InnoDB中的Adaptive Hash Index就是這個(gè)東西。但對(duì)檢查唯一性帶來(lái)的搜索，Bloomfilter是個(gè)好方法，經(jīng)?？梢韵?8%以上不必要的檢查。所以BigTable里就 用。但對(duì)傳統(tǒng)B+樹(shù)由于索引是實(shí)時(shí)更新的，Bloomfilter不好用，對(duì)Fractal Tree，索引是在merge的時(shí)候再批量更新的，可以用Bloomfilter。我們?cè)嚵薚okuDB，根據(jù)性能表明看，它對(duì)索引性索引的隨機(jī)插入，也 能輕松對(duì)付，估計(jì)也是用了Bloomfilter類似的技術(shù)。

因此，我們可以看到，隨機(jī)IO這個(gè)老大難的問(wèn)題，其實(shí)還是有不少的技術(shù)可以 解決的。然而，現(xiàn)實(shí)是悲摧的，我們經(jīng)常在用的主流數(shù)據(jù)庫(kù)，無(wú)論是商業(yè)的Oracle、DB2、SQL Server，還是開(kāi)源的MySQL、PostgreSQL，都基本上還在用最老土的技術(shù)，InnoDB里搞了一點(diǎn)change buffer，就能讓人津津樂(lè)道半天。NoSQL系統(tǒng)走在前面，用上了LSM-Tree，但也并不是***進(jìn)的，搜索的性能經(jīng)常令人擔(dān)憂。在索引這方 面，TokuDB走在前面，但還沒(méi)為大眾接受。記錄方面，不清楚為什么大家不作記錄級(jí)緩存，這不是很難的事，莫非認(rèn)為用Memcached就可以了，“因 為善小而不為”?

相信未來(lái)，總有改善的一天。

【編輯推薦】

1. 簡(jiǎn)單說(shuō)說(shuō)Oracle分區(qū)
2. PostgreSQL的PDF.NET驅(qū)動(dòng)程序構(gòu)建過(guò)程
3. 一步一步設(shè)計(jì)你的數(shù)據(jù)庫(kù)之不可輕視的需求分析