丨mvcc如何實(shí)現(xiàn)多并發(fā)控制

MVCC機(jī)制的思想是保存一個(gè)key-value數(shù)據(jù)的多個(gè)歷史版本，etcd基于它不僅實(shí)現(xiàn)了可靠的Watch機(jī)制，避免了 頻繁發(fā)起ListPod等expensiverequest操作，保障etcd集群穩(wěn)定性。而且MVCC還能以較低的并發(fā)控制開銷，實(shí)現(xiàn)各類級(jí)別的事希望通過本節(jié)課，幫助你搞懂MVCC含義和MVCC機(jī)制下key-value數(shù)據(jù)的更新、查詢、刪除原理，了解treeIndex索引模塊、bob模塊是如何相互協(xié)作，實(shí)現(xiàn)保存一個(gè)key-value數(shù)據(jù)多個(gè)歷史版本。什么是首先和你聊聊什么是MVCC，從名字上理解，它是一個(gè)基于多版本技術(shù)實(shí)現(xiàn)的一種并發(fā)控制機(jī)制。那常見的并發(fā)機(jī)制有哪些？MVCC的優(yōu)點(diǎn)在哪里呢？提到并發(fā)控制機(jī)制你可能就沒那么陌生了，比如數(shù)據(jù)庫中的悲觀鎖，也就是通過鎖機(jī)制確保同一時(shí)刻只能有一個(gè)事務(wù)對(duì)數(shù)據(jù)進(jìn)行修改操作，常見的實(shí)現(xiàn)方案有讀寫鎖、互斥鎖、兩階段鎖等。悲觀鎖是一種事先預(yù)防機(jī)制，它悲觀地認(rèn)為多個(gè)并發(fā)事務(wù)可能會(huì)發(fā)生，因此它要求事務(wù)必須先獲得鎖，才能進(jìn)行修改數(shù)據(jù)操作。但是悲觀鎖粒度過大、高并發(fā)場(chǎng)景下大量事務(wù)會(huì)阻塞等，會(huì)導(dǎo)致服務(wù)性能較差。MVCC機(jī)制正是基于多版本技術(shù)實(shí)現(xiàn)的一種樂觀鎖機(jī)制，它樂觀地認(rèn)為數(shù)據(jù)不會(huì)發(fā)生沖在MVCC數(shù)據(jù)庫中，你更新一個(gè)ey-value數(shù)據(jù)的時(shí)候，它并不會(huì)直接覆蓋原數(shù)據(jù)，而是新增一個(gè)版本來新的數(shù)據(jù)，每個(gè)數(shù)據(jù)都有一個(gè)版本號(hào)。版本號(hào)它是一個(gè)邏輯時(shí)間，為了方便你深入理解版本號(hào)意義，在下面我給你畫了一個(gè)ecdMCC版本號(hào)時(shí)間序列圖。從圖中你可以看到，隨著時(shí)間增長(zhǎng)，你每次修改操作，版本號(hào)都會(huì)遞增。每修改一次，生成一條新的數(shù)據(jù)記錄。當(dāng)你指定版本號(hào)數(shù)據(jù)時(shí)，它實(shí)際問的是版本號(hào)生成那個(gè)時(shí)間點(diǎn)的快照數(shù)據(jù)。當(dāng)你刪除數(shù)據(jù)的時(shí)候，它實(shí)際也是新增一條帶刪除標(biāo)識(shí)的數(shù)據(jù)記錄。了解完什么是MVCC，我先通過幾個(gè)簡(jiǎn)單命令，帶你初體驗(yàn)下MVCC性，看看它是如何幫助你查詢歷史修改記錄，以及找回不刪除的key的。啟動(dòng)一個(gè)空集群，更新兩次 o后，如何獲取 o的上一個(gè)版本值呢？刪 o后，還能讀到歷史版本如下面令所示，第一次key o更新完后，我們通過get命令獲取下它的key-value詳細(xì)信息。正如你所看到的，除了key、value信息，還有各類版本號(hào)，我后面會(huì)詳細(xì)和你介紹它們的含義。這里我們重點(diǎn)關(guān)注mod_revision，它表示key最后一次修改時(shí)的etcd版本號(hào)。當(dāng)我們?cè)俅胃耴eyo為world2后，然后通過查詢時(shí)指定key第一次更新后的版本號(hào)，你會(huì)發(fā)現(xiàn)我們查詢到了第一次更新的值，甚至我們執(zhí)行刪除keyo后，依然可以獲得到這個(gè)值。那么etcd是如何實(shí)現(xiàn)的呢?123456789#更新$etcdctlo#通過指定輸出模式為json,查看$etcdctl{{o-}}#再次修改$etcdctl#確認(rèn)修改成功$etcdctlgetoo#指定查詢版本號(hào),$etcdctlget#刪除$etcdctl1o--oo#刪除后指定查詢版本號(hào)3,獲得 $etcdctlget o--rev=3在詳細(xì)和你介紹etcd如何實(shí)現(xiàn)MVCC特性前，我先和你從整體上介紹下MVCC模塊。下圖是MVCC塊的一個(gè)整體架構(gòu)圖，整個(gè)MVCC性由treeIndex、Backend/bob當(dāng)你執(zhí)行MVCC性初體驗(yàn)中的put后，請(qǐng)求經(jīng)過gRPCKVServer、Raft流轉(zhuǎn)，對(duì)應(yīng)的日志條目被提交后，Apply模塊開始執(zhí)行此日志內(nèi)容。Aply模塊通過MCC模塊來執(zhí)行put請(qǐng)求，持久化ey-ale數(shù)據(jù)。MCC模塊將請(qǐng)求請(qǐng)劃分成兩個(gè)類別，分別是讀事務(wù)（ReaTxn）和寫事務(wù)（WrieTxn）。讀事務(wù)負(fù)責(zé)處理rane請(qǐng)求，寫事務(wù)負(fù)責(zé)ut/elee操作。讀寫事務(wù)基于reeInex、Backend/bob提供的能力，實(shí)現(xiàn)對(duì)key-value的增刪改查功能treeIndex模塊基于內(nèi)存版B-tree實(shí)現(xiàn)了key索引管理，它保存了用戶key與版本（revision）的映射關(guān)系等信Backend模塊負(fù)責(zé)etcd的key-value持久化，主要由ReadTx、BatchTx、Buffer組成，ReadTx定義了抽象的讀事務(wù)接口，BatchTx在ReadTx之上定義了抽象的寫事務(wù)接口，Buffer是數(shù)據(jù)緩存區(qū)。etcd計(jì)上支持多種Backend現(xiàn)，目前實(shí)現(xiàn)的Backendbob。bob一個(gè)基于B+tree實(shí)現(xiàn)的、支持事務(wù)的key-value嵌入式數(shù)據(jù)庫。treeIndex與bo b關(guān)系你可參考下圖。當(dāng)你發(fā)起一個(gè)get o命令時(shí)，從treeIndex中獲取key的版本號(hào)，然后再通過這個(gè)版本號(hào)，從bo b獲取value信息。bo b的value是包含用戶key-value、各種版本號(hào)、lease信息的結(jié)構(gòu)體。接下來我和你重點(diǎn)聊聊treeIndex模塊的原理與數(shù)據(jù)結(jié)構(gòu)為什么需要treeIndex模塊呢對(duì)于etcdv2來說，當(dāng)你通過etcdctl發(fā)起一個(gè)put o操作時(shí)，etcdv2直接更新內(nèi)存樹，這就導(dǎo)致歷史版本直接被覆蓋，無法支持保存key的歷史版本。在etcdv3中引入treeIndex模塊正是為了解決這個(gè)問題，支持保存key的歷史版本，提供穩(wěn)定的Watch機(jī)那etcdv3又是如何基于treeIndex模塊，實(shí)現(xiàn)保存key的歷史版本的在02節(jié)課里，我們提到過etcd在每次修改key時(shí)會(huì)生成一個(gè)全局遞增的版（revision），然后通過數(shù)據(jù)結(jié)構(gòu)B-tree保存用戶key與版本號(hào)之間的關(guān)系，再以版本號(hào)作為bo bkey，以用戶的key-value等信息作為bo bvalue，保存到bo 下面我就為你介紹下，etcd存用戶key版本號(hào)映射關(guān)系的數(shù)據(jù)結(jié)構(gòu)B-tree，為什么etcd使用它而不使用哈希表、平衡二叉樹？etcd功能特性上分析etcd持范圍查詢，因此保存索引的數(shù)據(jù)結(jié)構(gòu)也必須支持范圍查詢才行。所以哈希表不適合，而B-tree支持范圍查詢。從性能上分析，平橫二叉樹每個(gè)節(jié)點(diǎn)只能容納一個(gè)數(shù)據(jù)、導(dǎo)致樹的高度較高，而B-tree增、刪、改、查性能的開源項(xiàng)目btree，使用Go言實(shí)現(xiàn)了一個(gè)內(nèi)存版的B-tree，對(duì)外提供了簡(jiǎn)單易用的接口。etcd正是基于btree庫實(shí)現(xiàn)了一個(gè)名為treeIndex的索引模塊，通過它來查詢、保存用戶key與版本號(hào)之間的關(guān)系。下圖是個(gè)最大度（degree>1，簡(jiǎn)稱d）為5的B-tree，度是B-tree中的一個(gè)參個(gè)度為d的B-tree中，節(jié)點(diǎn)保存的最大key數(shù)為2d-1，否則需要進(jìn)行平衡、操作。這里你要注意的是在etcdtreeIndex塊中，創(chuàng)建的是最大度32B-tree，也就是一個(gè)葉子節(jié)點(diǎn)最多可以保存63個(gè)key。從圖中你可以看到，你通過put/txn命令寫入的一系列key，treeIndex模塊基于B-tree將其組織起來，節(jié)點(diǎn)之間基于用戶key比較大小。當(dāng)你查找一個(gè)keyk95時(shí)，通過B-tree的特性，你僅需通過圖中流程1和2兩次快速比較，就可快速找到k95所在的節(jié)點(diǎn)。treeIndex，每個(gè)節(jié)點(diǎn)的key一個(gè)keyIndex構(gòu)，etcd是通過它保存了用key與版本號(hào)的映射關(guān)系那么keyIndex結(jié)構(gòu)包含哪些信息呢？下面是字段說明，你可以參考一代代12345typekeyIndexstruct[]byte//用戶的key名稱，比如我們案例中的 revision//最后一次修改key時(shí)的etcd版本號(hào),比如我們案例中的剛generations[]generation//generation保存了一個(gè)key若干代版本號(hào)信息，每代中包含對(duì)}keyIndex中包含用戶的key、最后一次修改key時(shí)的etcd版本號(hào)、key的若干（generation）版本號(hào)信息，每代中包含對(duì)key的多次修改的版本號(hào)列表。那我們要如何理解generations？為什么它是個(gè)數(shù)組呢?generations表示一個(gè)key從創(chuàng)建到刪除的過程，每代對(duì)應(yīng)key的一個(gè)生命周期的開始與結(jié)束。當(dāng)你第一次創(chuàng)建一個(gè)key時(shí)，會(huì)生成第0代，后續(xù)的修改操作都是在往第0代中追加修本號(hào)。當(dāng)你把key刪除后，它就會(huì)生成新的第1代，一個(gè)key不斷經(jīng)歷創(chuàng)建、刪generation結(jié)構(gòu)詳細(xì)信息如2 3revision//表示generation結(jié)構(gòu)創(chuàng)建時(shí)的版本45[]revision//每次修改key時(shí)的revision追加到此數(shù)generation結(jié)構(gòu)中包含此key的修改次數(shù)、generation創(chuàng)建時(shí)的版本號(hào)、對(duì)此key的修你需要注意的是版本號(hào)（revision）并不是一個(gè)簡(jiǎn)單的整數(shù)，而是一個(gè)結(jié)構(gòu)體。revision結(jié)代代12typerevisionstructmain//一個(gè)全局遞增的主版本號(hào)，隨put/txn/delete事務(wù)遞增，一個(gè)事務(wù)內(nèi)的334sub//一個(gè)事務(wù)內(nèi)的子版本號(hào)，從0開始隨事務(wù)內(nèi)put/delete}revision包含main和sub兩個(gè)字段，main是全局遞增的版本號(hào)，它是個(gè)etcd邏輯時(shí)鐘，隨著put/txn/delete等事務(wù)遞增。sub是一個(gè)事務(wù)內(nèi)的子版本號(hào)，從0開始隨事務(wù)內(nèi)的put/delete操作遞增。比如啟動(dòng)一個(gè)空集群，全局版本號(hào)默認(rèn)為1，執(zhí)行下面的txn事務(wù)，它包含兩次put、一次get操作，那么按照我們上面介紹的原理，全局版本號(hào)隨讀寫事務(wù)自增，因此是main為2，sub隨事務(wù)內(nèi)的put/delete操作遞增，因此key o的revison為{2,0}，keyworld的revision為{2,1}。代代12345678$etcdctltxn-successrequestsooputworld介紹完treeIndex基本原理、數(shù)據(jù)結(jié)構(gòu)后，我們?cè)倏纯丛贛VCC特性初體驗(yàn)中的更新、查詢、刪除key案例里，treeIndex與bob是如何協(xié)作，完成以上key-value操M(fèi)VCC更新key當(dāng)你通過etcdctl發(fā)起一個(gè)puto操作時(shí)，如下面的put事務(wù)流程圖流程一所示，在put寫事務(wù)中，首先它需要從treeIndex模塊中查詢key的keyIndex索引信息，keyIndex中了key的創(chuàng)建版本號(hào)、修改的次數(shù)等信息，這些信息在事務(wù)中發(fā)揮著重要作用，因此會(huì)在bo b的value中。在我們的案例中，因?yàn)槭堑谝淮蝿?chuàng) okey，此時(shí)keyIndex索引為空其次etcd會(huì)根據(jù)當(dāng)前的全局版本號(hào)（空集群?jiǎn)?dòng)時(shí)默認(rèn)為1）自增，生成put o操作對(duì)應(yīng)的版本號(hào)revision{2,0}，這就是bo b的key。 b的value是mv b.KeyValue結(jié)構(gòu)體，它是由用戶key、value、create_revision、mod_revision、version、lease組成。它們的含義分別如下：create_revision表示此key創(chuàng)建時(shí)的版本號(hào)。在我們的案例中，key o是第一次創(chuàng)建，那么值就是2。當(dāng)你再次修改keyo的時(shí)候，寫事務(wù)會(huì)從treeIndex模塊查詢o第一次創(chuàng)建的版本號(hào)，也就是keyIndex.generations[i].created字段，賦值給create_revision字段mod_revision示key后一次修改時(shí)的版本號(hào)，即put作發(fā)生時(shí)的全局版本號(hào)version示此key修改次數(shù)。每次修改的時(shí)候，寫事務(wù)會(huì)從treeIndex塊查o經(jīng)歷過的修改次數(shù)，也就是keyIndex.generations[i].ver段，將ver段值加1后，賦值給version字段。填充好bob的KeyValue結(jié)構(gòu)體后，這時(shí)就可以通過Backend的寫事務(wù)batchTx接口將key{2,0},value為mvb.KeyValue保存到bob的緩存中，并同步更新buffer，此時(shí)到 b中的key、value數(shù)據(jù)如下然后put務(wù)需將本次修改的版本號(hào)與用戶key映射關(guān)系保存到treeIndex也因?yàn)閗ey o是首次創(chuàng)建，treeIndex模塊它會(huì)生成key o對(duì)應(yīng)的keyIndex對(duì)象，keyIndex填充后的結(jié)果如下所代代12345"modified:<2,0>[{ver:1,created:<2,0>,revisions:[<2,0>]}我們來簡(jiǎn)易分析一下上面的結(jié)key為 o，modified為最后一次修本號(hào)<2,0>，key o是首次創(chuàng)建的，因此新增一個(gè)generation代它的生命周期、修改記錄；generationver示修改次數(shù)，首次創(chuàng)建1，后續(xù)隨著修改操作遞增；generation.created表示創(chuàng)建generation時(shí)的版本號(hào)為<2,0>；revision數(shù)組保存對(duì)此key修改的版本號(hào)列表，每次修改都會(huì)將將相應(yīng)的版本號(hào)追加revisions數(shù)組中通過以上流程，一個(gè)put操作終于完但是此時(shí)數(shù)據(jù)還并未持久化，為了提升etcd的寫吞吐量、性能，一般情況下（默認(rèn)堆積的寫事務(wù)數(shù)大于1萬才在寫事務(wù)結(jié)束時(shí)同步持久化），數(shù)據(jù)持久化由Backend的異步goroutine完成，它通過事務(wù)批量提交，定時(shí)將bo b頁緩存中的臟數(shù)據(jù)提交到持久化存MVCC查詢key完成put o為world1操作后，這時(shí)你通過etcdctl發(fā)起一個(gè)get o操作，MVCC模塊首先會(huì)創(chuàng)建一個(gè)讀事務(wù)對(duì)象（TxnRead），在etcd3.4中Backend實(shí)現(xiàn)了ConcurrentReadTx，也就是并發(fā)讀特性。并發(fā)讀特性的原理是創(chuàng)建讀事務(wù)對(duì)象時(shí)，它會(huì)全量拷貝當(dāng)前寫事務(wù)未提交的buffer數(shù)據(jù)，并發(fā)的讀寫事務(wù)不再阻塞在一個(gè)buffer資源鎖上，實(shí)現(xiàn)了全并發(fā)讀。如上圖所示，在讀事務(wù)中，它首先需要根據(jù)key從treeIndex模塊獲取版本號(hào)，因我們未帶版本號(hào)讀，默認(rèn)是的數(shù)據(jù)。treeIndex模塊從B-tree中，根據(jù)key查找到keyIndex對(duì)象后，匹配有效的generation，返回generation的revisions數(shù)組中最后一讀事務(wù)對(duì)象根據(jù)此版本號(hào)為key，通過Backend的并發(fā)讀事務(wù)（ConcurrentReadTx）接口，優(yōu)先從buffer中查詢，命中則直接返回，否則從bob中查詢此key的value信那指定版本號(hào)歷史記錄又是怎么實(shí)現(xiàn)的呢當(dāng)你再次發(fā)起一個(gè)puto為world2修改操作時(shí)，keyo對(duì)應(yīng)的keyIndex的結(jié)果如下面所示，keyIndex.modified字段更新為<3,0>，generation的revision數(shù)組追加的版本號(hào)<3,0>，ver修改為2。代代12345"modified:<3,0>[{ver:2,created:<2,0>,revisions: b插入一個(gè)新的keyrevision{3,0}，此時(shí)到 b中的key-value數(shù)據(jù)如下這時(shí)你再發(fā)起一個(gè)指定歷史版本號(hào)為2的讀請(qǐng)求時(shí)，實(shí)際是讀版本號(hào)為2的時(shí)間點(diǎn)的快照數(shù)據(jù)。treeIndex模塊會(huì)遍歷generation內(nèi)的歷史版本號(hào)，返回小于等于2的最大歷史版本號(hào)，在我們這個(gè)案例中，也就是revision{2,0}，以它作為bob的key，從bob中查詢出value即可。MVCC刪除key介紹完MVCC更新、查詢key的原理后，我們接著往下看。當(dāng)你執(zhí)行etcdctldel 命令時(shí)，etcd會(huì)立刻從treeIndex和bo b中刪除此數(shù)據(jù)嗎？還是增加一個(gè)標(biāo)記實(shí)現(xiàn)延遲刪除（lazydelete）呢？答案為etcd實(shí)現(xiàn)的是延期刪除模式，原理與key更新類似與更新key不一樣之處在于，一方面，生成的bobkey版本號(hào){4,0,t}追加了刪除標(biāo)（tombstone,簡(jiǎn)寫t），bobvalue變成只含用戶key的KeyValue結(jié)構(gòu)體。另一方面treeIndex模塊也會(huì)給此keyo對(duì)應(yīng)的keyIndex對(duì)象，追加一個(gè)空的generation對(duì)象，表示此索引對(duì)應(yīng)的key被刪除了。當(dāng)你再次查詢o的時(shí)候，treeIndex模塊根據(jù)keyo查找到keyindex對(duì)象后，若發(fā)現(xiàn)其存在空的generation對(duì)象，并且查詢的版本號(hào)大于等于被刪除時(shí)的版本號(hào)，則會(huì)返 o操作后的keyIndex的結(jié)果如下面所112345678代"modified:<4,0>[{ver:3,created:<2,0>,revisions:] b此時(shí)會(huì)插入一個(gè)新的keyrevision{4,0,t}，此時(shí)到bo b中的key-value數(shù)那么key打上刪除標(biāo)記后有哪些用途呢？什么時(shí)候會(huì)真正刪除它一方面刪除key會(huì)生成events，Watch塊根據(jù)key刪除標(biāo)識(shí)，會(huì)生成對(duì)應(yīng)Delete另一方面，當(dāng)你重啟etcd，遍歷bo b中的key構(gòu)建treeIndex內(nèi)存樹時(shí)，你需要知道哪些key是已經(jīng)被刪除的，并為對(duì)應(yīng)的key索引生成tombstone標(biāo)識(shí)。而真正刪除treeIndex中的索引對(duì)象、bo b中的key是通過壓縮(compactor)組件異步完成。正因?yàn)閑tcd刪除key作是基于以上延期刪除原理實(shí)現(xiàn)的，因此只要壓縮組件未回收歷史版本，我們就能從etcd中找回誤刪的數(shù)據(jù)。最后我們來小結(jié)下今天的內(nèi)容，我通過MVCC特性初體驗(yàn)中的更新、查詢、刪除key案例，為你分析了MVCC整體架構(gòu)、模塊，它由treeIndex、bo b組成。treeIndex模塊基于開源的btree庫實(shí)現(xiàn)，它的數(shù)據(jù)結(jié)構(gòu)keyIndex，保存了用戶key與版本號(hào)關(guān)系。每次修改key都會(huì)生成新的版本號(hào)，生成新的bo bkey- b的key為版本號(hào)，value包含用戶key-value、各種版本號(hào)、lease的 b.KeyValue結(jié)構(gòu)體當(dāng)你未帶版本號(hào)查詢key時(shí)，etcd返回的是key版本數(shù)據(jù)。當(dāng)你指定版本號(hào)數(shù)據(jù)時(shí)，etcd實(shí)際上返回的是版本號(hào)生成那個(gè)時(shí)間點(diǎn)的快照數(shù)據(jù)。刪除一個(gè)數(shù)據(jù)時(shí)，etcd并未真正刪除它，而是基于lazydelete實(shí)現(xiàn)的異步刪除。刪除原理本質(zhì)上與更新操作類似，只不過bobkey打上刪除標(biāo)記，keyIndex索引中追加空的generation。真正刪除key是通過etcd的壓縮組件去異步實(shí)現(xiàn)的，在后面的課程里基于以上原理特性的實(shí)現(xiàn)，etcd現(xiàn)了保存