Innodb-B+樹-并發(fā)控制

內(nèi)存并發(fā)控制

為了維護(hù)內(nèi)存結(jié)構(gòu)的一致性,比如Dictionary cache灼芭、sync array有额、trx system等結(jié)構(gòu)。
InnoDB并沒有直接使用glibc提供的庫彼绷,而是自己封裝了兩類:

  1. 一類是mutex巍佑,實(shí)現(xiàn)內(nèi)存結(jié)構(gòu)的串行化訪問。
  2. 一類是rw lock寄悯,實(shí)現(xiàn)讀寫阻塞萤衰,讀讀并發(fā)的訪問的讀寫鎖。

B+樹并發(fā)控制

B+樹的并發(fā)控制主要分2個(gè)方面猜旬,一個(gè)是節(jié)點(diǎn)中內(nèi)容的并發(fā)控制脆栋、另一個(gè)是樹結(jié)構(gòu)的并發(fā)控制,比如樹高的變化洒擦、頁的分裂等等椿争。
為了實(shí)現(xiàn)上述兩方面的并發(fā)控制。

5.6版本

InnoDB為每一個(gè)index熟嫩,維護(hù)兩種rw lock:

  1. index級(jí)別的秦踪,用于保護(hù)B-Tree結(jié)構(gòu)不被破壞。
  2. block級(jí)別的邦危,用于保護(hù)block內(nèi)部結(jié)構(gòu)不被破壞,僅適用于葉子節(jié)點(diǎn)舍扰,非葉子節(jié)點(diǎn)不加鎖倦蚪。

rw lock分為S、X兩種模式边苹,如果設(shè)計(jì)到SMO陵且,需要對(duì)index級(jí)別的rw lock加X鎖,這樣的實(shí)現(xiàn)帶來的好處是代碼實(shí)現(xiàn)非常簡(jiǎn)單, 但是缺點(diǎn)也很明顯由于在SMO 操作的過程中, 讀取操作也是無法進(jìn)行的, 并且SMO 操作過程可能有IO 操作, 帶來的性能抖動(dòng)非常明顯
具體參考http://mysql.taobao.org/monthly/2020/06/02/

5.7版本

主要有這兩個(gè)改動(dòng)

  1. rw-lock引入了sx模式个束,優(yōu)化了阻塞讀的問題慕购。
  2. block級(jí)別的rw-lock,非葉子幾點(diǎn)也加鎖茬底。
    S沪悲、X、SX三個(gè)模式的兼容關(guān)系如下:
/*
 LOCK COMPATIBILITY MATRIX
    S SX  X
 S  +  +  -
 SX +  -  -
 X  -  -  -
 */

加鎖的具體流程:

  1. 如果是一個(gè)查詢請(qǐng)求
  • 那么首先把btree index->lock S LOCK
  • 然后沿著搜索btree 路徑, 遇到的non-leaf node page 都加 S LOCK
  • 然后直到找到 leaf node 以后, 對(duì)leaft node page 也是 S LOCK, 然后把index-> lock 放開
    image.png

    2.修改請(qǐng)求的流程也參見http://mysql.taobao.org/monthly/2020/06/02/
    這個(gè)page 的修改是否會(huì)引起 btree 的變化阱表?
  • 如果不會(huì), 那么很好, 對(duì)leaf node 執(zhí)行了X LOCK 以后, 修改完數(shù)據(jù)返回就可以
  • 如果會(huì), 那么需要執(zhí)行悲觀插入操作, 重新遍歷btree. 這時(shí)候給index->lock 是加 SX LOCK。
    因?yàn)橐呀?jīng)給btree 加上sx lock, 那么搜索路徑上的btree 的page 都不需要加 lock, 但是需要把搜索過程中的page 保存下來, 最后階段給搜索路徑上有可能發(fā)生結(jié)構(gòu)變化的page 加x lock较屿。
    這樣就保證了在搜索的過程中, 對(duì)于read 操作的影響降到最低翩概。
    只有在最后階段確定了本次修改btree 結(jié)構(gòu)的范圍, 對(duì)可能發(fā)生結(jié)構(gòu)變化的page 加X lock 以后, 才會(huì)有影響。

代碼實(shí)現(xiàn)

B樹的搜索入口函數(shù)為btr_cur_search_to_nth_level门岔,其參數(shù)latch_mode分為兩部分,低字節(jié)為如下的基本操作模式:

/** Latching modes for btr_cur_search_to_nth_level(). */
enum btr_latch_mode {
    /** Search a record on a leaf page and S-latch it. */
    BTR_SEARCH_LEAF = RW_S_LATCH,
    /** (Prepare to) modify a record on a leaf page and X-latch it. */
    BTR_MODIFY_LEAF = RW_X_LATCH,
    /** Obtain no latches. */
    BTR_NO_LATCHES = RW_NO_LATCH,
    /** Start modifying the entire B-tree. */
    BTR_MODIFY_TREE = 33,
    /** Continue modifying the entire B-tree. */
    BTR_CONT_MODIFY_TREE = 34,
    /** Search the previous record. */
    BTR_SEARCH_PREV = 35,
    /** Modify the previous record. */
    BTR_MODIFY_PREV = 36,
    /** Start searching the entire B-tree. */
    BTR_SEARCH_TREE = 37,
    /** Continue searching the entire B-tree. */
    BTR_CONT_SEARCH_TREE = 38
};

每種模式的加鎖流程可以參考:https://zhuanlan.zhihu.com/p/164705538

悲觀寫入

悲觀寫入因?yàn)闀?huì)涉及SMO,所以需要重新遍歷B Tree加鎖

row_ins_clust_index_entry
//這里是BTR_MODIFY_LEAF
----row_ins_clust_index_entry_low(flags, BTR_MODIFY_LEAF, index, n_uniq, entry, n_ext, thr, dup_chk_only)
--------btr_pcur_open //調(diào)用btr_cur_search_to_nth_level 查詢索引樹烤送,將cursor移動(dòng)到待插入記錄相應(yīng)的位置
------------btr_cur_optimistic_insert //樂觀插入
//如果插入失敗需要遍歷B樹寒随,此時(shí)是BTR_MODIFY_TREE
----row_ins_clust_index_entry_low(flags, BTR_MODIFY_TREE, index, n_uniq, entry, n_ext, thr, dup_chk_only)
--------btr_pcur_open //調(diào)用btr_cur_search_to_nth_level 查詢索引樹,將cursor移動(dòng)到待插入記錄相應(yīng)的位置
-----------btr_cur_optimistic_insert //樂觀插入
-----------btr_cur_pessimistic_insert //悲觀插入

http://static.kancloud.cn/taobaomysql/monthly/67063
http://mysql.taobao.org/monthly/2020/06/02/
https://zhuanlan.zhihu.com/p/164705538
http://liuyangming.tech/07-2019/InnoDB-Lock.html#insert%E7%9A%84rwlock
http://mysql.taobao.org/monthly/2017/10/03/
http://mysql.taobao.org/monthly/2018/09/01/

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末帮坚,一起剝皮案震驚了整個(gè)濱河市妻往,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌叶沛,老刑警劉巖蒲讯,帶你破解...
    沈念sama閱讀 212,383評(píng)論 6 493
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場(chǎng)離奇詭異灰署,居然都是意外死亡判帮,警方通過查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,522評(píng)論 3 385
  • 文/潘曉璐 我一進(jìn)店門溉箕,熙熙樓的掌柜王于貴愁眉苦臉地迎上來晦墙,“玉大人,你說我怎么就攤上這事肴茄∩纬” “怎么了?”我有些...
    開封第一講書人閱讀 157,852評(píng)論 0 348
  • 文/不壞的土叔 我叫張陵寡痰,是天一觀的道長(zhǎng)抗楔。 經(jīng)常有香客問我,道長(zhǎng)拦坠,這世上最難降的妖魔是什么连躏? 我笑而不...
    開封第一講書人閱讀 56,621評(píng)論 1 284
  • 正文 為了忘掉前任,我火速辦了婚禮贞滨,結(jié)果婚禮上入热,老公的妹妹穿的比我還像新娘。我一直安慰自己晓铆,他們只是感情好勺良,可當(dāng)我...
    茶點(diǎn)故事閱讀 65,741評(píng)論 6 386
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著骄噪,像睡著了一般尚困。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上链蕊,一...
    開封第一講書人閱讀 49,929評(píng)論 1 290
  • 那天尾组,我揣著相機(jī)與錄音忙芒,去河邊找鬼。 笑死讳侨,一個(gè)胖子當(dāng)著我的面吹牛呵萨,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播跨跨,決...
    沈念sama閱讀 39,076評(píng)論 3 410
  • 文/蒼蘭香墨 我猛地睜開眼潮峦,長(zhǎng)吁一口氣:“原來是場(chǎng)噩夢(mèng)啊……” “哼!你這毒婦竟也來了勇婴?” 一聲冷哼從身側(cè)響起忱嘹,我...
    開封第一講書人閱讀 37,803評(píng)論 0 268
  • 序言:老撾萬榮一對(duì)情侶失蹤,失蹤者是張志新(化名)和其女友劉穎耕渴,沒想到半個(gè)月后拘悦,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 44,265評(píng)論 1 303
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡橱脸,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 36,582評(píng)論 2 327
  • 正文 我和宋清朗相戀三年础米,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片添诉。...
    茶點(diǎn)故事閱讀 38,716評(píng)論 1 341
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡屁桑,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出栏赴,到底是詐尸還是另有隱情,我是刑警寧澤须眷,帶...
    沈念sama閱讀 34,395評(píng)論 4 333
  • 正文 年R本政府宣布竖瘾,位于F島的核電站花颗,受9級(jí)特大地震影響,放射性物質(zhì)發(fā)生泄漏捎稚。R本人自食惡果不足惜乐横,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 40,039評(píng)論 3 316
  • 文/蒙蒙 一今野、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧罐农,春花似錦、人聲如沸涵亏。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,798評(píng)論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽拆内。三九已至,卻和暖如春麸恍,著一層夾襖步出監(jiān)牢的瞬間灵巧,已是汗流浹背抹沪。 一陣腳步聲響...
    開封第一講書人閱讀 32,027評(píng)論 1 266
  • 我被黑心中介騙來泰國(guó)打工, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留融欧,地道東北人敏弃。 一個(gè)月前我還...
    沈念sama閱讀 46,488評(píng)論 2 361
  • 正文 我出身青樓,卻偏偏與公主長(zhǎng)得像噪馏,于是被迫代替她去往敵國(guó)和親麦到。 傳聞我的和親對(duì)象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 43,612評(píng)論 2 350

推薦閱讀更多精彩內(nèi)容

  • MySQL : 基于InnoDB的物理復(fù)制實(shí)現(xiàn) 最近有幸前去美國(guó)參加Percona Live 2016會(huì)議并分享了...
    meng_philip123閱讀 1,561評(píng)論 1 2
  • ?一致性非鎖定讀(consistent nonlocking read)是指InnoDB存儲(chǔ)引擎通過多版本控制(M...
    程序員歷小冰閱讀 1,621評(píng)論 0 3
  • 久違的晴天逝薪,家長(zhǎng)會(huì)隅要。 家長(zhǎng)大會(huì)開好到教室時(shí),離放學(xué)已經(jīng)沒多少時(shí)間了董济。班主任說已經(jīng)安排了三個(gè)家長(zhǎng)分享經(jīng)驗(yàn)步清。 放學(xué)鈴聲...
    飄雪兒5閱讀 7,515評(píng)論 16 22
  • 今天感恩節(jié)哎,感謝一直在我身邊的親朋好友虏肾。感恩相遇廓啊!感恩不離不棄。 中午開了第一次的黨會(huì)封豪,身份的轉(zhuǎn)變要...
    迷月閃星情閱讀 10,559評(píng)論 0 11
  • 可愛進(jìn)取谴轮,孤獨(dú)成精。努力飛翔吹埠,天堂翱翔第步。戰(zhàn)爭(zhēng)美好,孤獨(dú)進(jìn)取缘琅。膽大飛翔粘都,成就輝煌。努力進(jìn)取刷袍,遙望翩隧,和諧家園∩胛疲可愛游走...
    趙原野閱讀 2,723評(píng)論 1 1