原文地址：http://hedengcheng.com/?p=525
問(wèn)題背景
今天，看到Twitter的DBA團(tuán)隊(duì)發(fā)布了其最新的MySQL分支：Changes in Twitter MySQL 5.5.28.t9衔憨，此分支最重要的一個(gè)改進(jìn)叶圃，就是修復(fù)了MySQL 的Bug #67718：InnoDB drastically under-fills pages in certain conditions。關(guān)于此Bug的詳細(xì)描述践图，以及如何重現(xiàn)此問(wèn)題掺冠，可以閱讀以上的Bug鏈接，以下簡(jiǎn)單描述下此Bug對(duì)應(yīng)的問(wèn)題：
InnoDB的索引分裂策略码党，在特定的情況下德崭，索引頁(yè)面的分裂存在問(wèn)題，導(dǎo)致每個(gè)分裂出來(lái)的頁(yè)面闽瓢，僅僅存儲(chǔ)一條記錄接癌，頁(yè)面的空間利用率極低心赶。
此Bug引起了我的興趣扣讼，因此準(zhǔn)備跟大家簡(jiǎn)單聊聊B+樹(shù)索引的結(jié)構(gòu)、B+樹(shù)的分裂缨叫、B+樹(shù)分裂操作的優(yōu)化椭符、Bug #67718的成因，以及個(gè)人對(duì)如何修復(fù)此Bug的一些建議等耻姥。
B+樹(shù)索引結(jié)構(gòu)
傳統(tǒng)關(guān)系型數(shù)據(jù)庫(kù)(Oracle/MySQL/PostgreSQL…)销钝，其主要的索引結(jié)構(gòu)，使用的都是B+樹(shù)琐簇。更有甚者蒸健，InnoDB引擎的表數(shù)據(jù)，整個(gè)都是以B+樹(shù)的組織形式存放的婉商。下圖似忧，是一個(gè)經(jīng)典的B+樹(shù)組織結(jié)構(gòu)圖(2層B+樹(shù)，每個(gè)頁(yè)面的扇出為4)：
注意：
此B+樹(shù)丈秩，以InnoDB實(shí)現(xiàn)的B+樹(shù)結(jié)構(gòu)為準(zhǔn)盯捌；
此B+樹(shù)，有5條用戶記錄蘑秽，分別是1饺著，2箫攀，3，4幼衰，5靴跛；
B+樹(shù)上層頁(yè)面中的記錄，存儲(chǔ)的是下層頁(yè)面中的最小值(Low Key)渡嚣；
B+樹(shù)的所有數(shù)據(jù)汤求，均存儲(chǔ)在B+樹(shù)的葉節(jié)點(diǎn)；
B+樹(shù)葉節(jié)點(diǎn)的所有頁(yè)面严拒，通過(guò)雙向鏈表鏈接起來(lái)扬绪；
B+樹(shù)的分裂
在上圖B+樹(shù)的基礎(chǔ)上，繼續(xù)插入記錄6裤唠，7挤牛，B+樹(shù)結(jié)構(gòu)會(huì)產(chǎn)生以下的一系列變化：
插入記錄6，新的B+樹(shù)結(jié)構(gòu)如下：
插入記錄7种蘸，由于葉頁(yè)面中只能存放4條記錄墓赴，插入記錄7，導(dǎo)致葉頁(yè)面分裂航瞭，產(chǎn)生一個(gè)新的葉頁(yè)面诫硕。
傳統(tǒng)B+樹(shù)頁(yè)面分裂操作分析：
按照原頁(yè)面中50%的數(shù)據(jù)量進(jìn)行分裂，針對(duì)當(dāng)前這個(gè)分裂操作刊侯，3章办，4記錄保留在原有頁(yè)面，5滨彻，6記錄藕届，移動(dòng)到新的頁(yè)面。最后將新紀(jì)錄7插入到新的頁(yè)面中亭饵；
-
50%分裂策略的優(yōu)勢(shì)：
- 分裂之后休偶，兩個(gè)頁(yè)面的空間利用率是一樣的；如果新的插入是隨機(jī)在兩個(gè)頁(yè)面中挑選進(jìn)行辜羊，那么下一次分裂的操作就會(huì)更晚觸發(fā)踏兜；
-
50%分裂策略的劣勢(shì)：
空間利用率不高：按照傳統(tǒng)50%的頁(yè)面分裂策略，索引頁(yè)面的空間利用率在50%左右八秃；
分裂頻率較大：針對(duì)如上所示的遞增插入(遞減插入)碱妆，每新插入兩條記錄，就會(huì)導(dǎo)致最右的葉頁(yè)面再次發(fā)生分裂喜德；
疑問(wèn)：
傳統(tǒng)50%分裂的策略山橄，有不足之處，如何優(yōu)化？接著往下看航棱。
B+樹(shù)分裂操作的優(yōu)化
由于傳統(tǒng)50%分裂的策略睡雇，有不足之處，因此饮醇，目前所有的關(guān)系型數(shù)據(jù)庫(kù)它抱，包括Oracle/InnoDB/PostgreSQL，以及本人以前參與研發(fā)的Oscar數(shù)據(jù)庫(kù)朴艰，目前正在研發(fā)的NTSE观蓄、TNT存儲(chǔ)引擎，都針對(duì)B+樹(shù)索引的遞增/遞減插入進(jìn)行了優(yōu)化祠墅。經(jīng)過(guò)優(yōu)化侮穿，以上的B+樹(shù)索引，在記錄6插入完畢毁嗦，記錄7插入引起分裂之后亲茅，新的B+樹(shù)結(jié)構(gòu)如下圖所示：
對(duì)比上下兩個(gè)插入記錄7之后，B+樹(shù)索引的結(jié)構(gòu)圖狗准，可以發(fā)現(xiàn)二者有很多的不同之處：
新的分裂策略克锣，在插入7時(shí)，不移動(dòng)原有頁(yè)面的任何記錄腔长，只是將新插入的記錄7寫(xiě)到新頁(yè)面之中袭祟；
原有頁(yè)面的利用率，仍舊是100%捞附；
-
優(yōu)化分裂策略的優(yōu)勢(shì)：
索引分裂的代價(jià)薪砣椤：不需要移動(dòng)記錄；
索引分裂的概率降低：如果接下來(lái)的插入故俐，仍舊是遞增插入想鹰，那么需要插入4條記錄紊婉，才能再次引起頁(yè)面的分裂药版。相對(duì)于50%分裂策略，分裂的概率降低了一半喻犁；
索引頁(yè)面的空間利用率提高：新的分裂策略槽片，能夠保證分裂前的頁(yè)面，仍舊保持100%的利用率肢础，提高了索引的空間利用率还栓；
-
優(yōu)化分裂策略的劣勢(shì)：
- 如果新的插入，不再滿足遞增插入的條件传轰，而是插入到原有頁(yè)面剩盒，那么就會(huì)導(dǎo)致原有頁(yè)面再次分裂，增加了分裂的概率慨蛙。
因此辽聊，此優(yōu)化分裂策略纪挎，僅僅是針對(duì)遞增遞減插入有效，針對(duì)隨機(jī)插入跟匆，就失去了優(yōu)化的意義异袄，反而帶來(lái)了更高的分裂概率。
在InnoDB的實(shí)現(xiàn)中玛臂，為每個(gè)索引頁(yè)面維護(hù)了一個(gè)上次插入的位置烤蜕，以及上次的插入是遞增/遞減的標(biāo)識(shí)。根據(jù)這些信息迹冤，InnoDB能夠判斷出新插入到頁(yè)面中的記錄讽营，是否仍舊滿足遞增/遞減的約束，若滿足約束泡徙，則采用優(yōu)化后的分裂策略斑匪；若不滿足約束，則退回到50%的分裂策略锋勺。
但是蚀瘸，InnoDB的實(shí)現(xiàn)，有不足之處庶橱，會(huì)導(dǎo)致下面提到的一個(gè)Bug贮勃。
Bug#67718的成因
在Bug#67718中提到，在特定的插入情況下苏章，InnoDB的索引頁(yè)面利用率極低寂嘉，這是由于InnoDB不正確的使用優(yōu)化分裂策略導(dǎo)致的。
考慮以下的一個(gè)B+樹(shù)枫绅，已有的用戶數(shù)據(jù)是1泉孩，2，3并淋，4寓搬，5，6县耽，100句喷，并且在插入記錄100之后，引起索引頁(yè)面分裂兔毙，記錄100在分裂后被插入到新的頁(yè)面：
由于插入100能夠滿足遞增的判斷條件唾琼，因此采用了優(yōu)化分裂策略，分裂不移動(dòng)數(shù)據(jù)澎剥，新紀(jì)錄100插入到新頁(yè)面之中锡溯，原有頁(yè)面的最后插入位置仍舊是6號(hào)記錄不變，原有頁(yè)面仍舊保持遞增的插入標(biāo)識(shí)不變。
此時(shí)祭饭，考慮連續(xù)插入9涌乳，8，7這幾條記錄甜癞，會(huì)得到什么樣的B+樹(shù)夕晓？此時(shí)，全局遞增插入變?yōu)槿诌f減插入悠咱。
插入記錄9后的B+樹(shù)結(jié)構(gòu)：
由于InnoDB的B+樹(shù)蒸辆，上層節(jié)點(diǎn)保存的是下層頁(yè)面中的最小值(Low Key)，因此記錄9仍舊會(huì)插入到【3析既，4躬贡，5，6】頁(yè)面眼坏，此時(shí)頁(yè)面已滿拂玻，需要分裂。而且判斷出記錄9仍舊滿足頁(yè)面中的遞增判斷條件(Last_Insert_Pos = 6宰译，9插入到6之后檐蚜，并且原來(lái)是遞增插入的)。因此沿侈，采用優(yōu)化的分裂策略闯第，產(chǎn)生新的頁(yè)面插入記錄9，原有頁(yè)面記錄保持不變缀拭。
插入記錄8后的B+樹(shù)結(jié)構(gòu)：
插入記錄7咳短，也一樣。采用優(yōu)化的分裂策略蛛淋，記錄7獨(dú)占一個(gè)頁(yè)面咙好。
分析：
-
Bug#67718的主要副作用
- 是頁(yè)面的利用率極低，每個(gè)索引葉頁(yè)面褐荷，只能存放一條記錄勾效；
-
Bug#67718的主要原因
- InnoDB錯(cuò)誤的采用了優(yōu)化的索引分裂策略。InnoDB判斷是否滿足遞增/遞減的插入模式诚卸，采用的是頁(yè)面級(jí)的判斷葵第，哪怕全局的模式發(fā)生了變化，只要頁(yè)面內(nèi)記錄的模式未變合溺，仍舊會(huì)選擇優(yōu)化后的索引分裂策略；
修復(fù)Bug#67718的建議
在本人做Oscar數(shù)據(jù)庫(kù)的索引分裂優(yōu)化時(shí)缀台，當(dāng)時(shí)也同樣碰到了此問(wèn)題棠赛。當(dāng)時(shí)的解決方案是：每次分裂，若插入的記錄是頁(yè)面中的最后一條記錄，則至少將此記錄前一條記錄分裂到新頁(yè)面之中睛约。采用此策略鼎俘，針對(duì)100，9辩涝，8這一個(gè)系列的插入贸伐，會(huì)產(chǎn)生以下的系列B+樹(shù)：
插入100，9怔揩，8后的B+樹(shù)：
插入100時(shí)捉邢，移動(dòng)原有頁(yè)面最后一條記錄到新的頁(yè)面(將6移動(dòng)到新頁(yè)面)，此時(shí)新頁(yè)面中的記錄為【6商膊，100】伏伐。接下來(lái)插入9，8晕拆，都會(huì)插入到新的頁(yè)面之中藐翎，不會(huì)產(chǎn)生分裂操作，空間利用率提高实幕，減少了索引頁(yè)面分裂吝镣，解決了Bug#67718的問(wèn)題。
當(dāng)然昆庇，肯定還有更優(yōu)的策略赤惊，歡迎感興趣的朋友們一起討論！
