Optimistic Lock Coupling: A Scalable and Efficient General-Purpose Synchcronization Method

（下文中的鎖Lock指的都是Latch）

傳統(tǒng)的細(xì)粒度鎖在現(xiàn)在的CPU上擴(kuò)展性很差，已經(jīng)不適用了；而Latch-Free設(shè)計(jì)和實(shí)現(xiàn)上都非常復(fù)雜，開(kāi)銷(xiāo)很大(詳細(xì)看前文)。而這里樂(lè)觀(guān)鎖耦合作為替代方案，同時(shí)具有擴(kuò)展性強(qiáng)和易于實(shí)現(xiàn)的優(yōu)點(diǎn)，而且尤其適用于樹(shù)形結(jié)構(gòu)。

傳統(tǒng)上數(shù)據(jù)庫(kù)使用的是細(xì)粒度鎖來(lái)同步內(nèi)部數(shù)據(jù)結(jié)構(gòu)，但是雖然細(xì)粒度鎖避免了鎖的爭(zhēng)用，但是仍會(huì)導(dǎo)致不好的可擴(kuò)展性，主要在于鎖的獲取與釋放都要寫(xiě)入共享內(nèi)存，而由于現(xiàn)代多核CPU實(shí)現(xiàn)緩存一致性的方式，這種寫(xiě)入方式會(huì)導(dǎo)致額外的Cache miss，并且包含內(nèi)部數(shù)據(jù)的緩存線(xiàn)會(huì)成為物理爭(zhēng)用點(diǎn)。因此任何頻繁訪(fǎng)問(wèn)的鎖如樹(shù)的根節(jié)點(diǎn)都嚴(yán)重限制了可擴(kuò)展性。

而無(wú)鎖結(jié)構(gòu)，通常比基于鎖的方法(尤其是以讀取為主的工作負(fù)載)擴(kuò)展性要好很多。但它有兩個(gè)缺點(diǎn)：實(shí)現(xiàn)困難，復(fù)雜且容易出錯(cuò)的代碼；硬件提供的原子原語(yǔ)功能有限(如原子的CaS只能是8byte)，復(fù)雜的操作需要在數(shù)據(jù)結(jié)構(gòu)中進(jìn)行額外的間接尋址——如Bw樹(shù)中，需要一個(gè)間接表來(lái)獲取下一個(gè)節(jié)點(diǎn)的地址，會(huì)導(dǎo)致額外的Cache miss增加開(kāi)銷(xiāo)。

樂(lè)觀(guān)鎖耦合OLC是集合基于鎖的和無(wú)鎖同步的同步方法。OLC有兩種模式：第一種類(lèi)似于傳統(tǒng)的互斥鎖，通過(guò)物理方式獲取底層鎖來(lái)排除其他線(xiàn)程；第二種，通過(guò)驗(yàn)證版本計(jì)數(shù)器version counter，讀可以樂(lè)觀(guān)進(jìn)行。第一種用于寫(xiě)，第二種用于讀。

OLC有以下幾種樂(lè)觀(guān)的特性

• 減少對(duì)共享內(nèi)存的寫(xiě)入次數(shù)，減少cache miss，適用于大多數(shù)負(fù)載。(主要體現(xiàn)在樂(lè)觀(guān)鎖上，不用寫(xiě)只用驗(yàn)證)
• 與不同步代碼相比，只需要增加很少的額外CPU指令
• OLC適用于BSL, tries, trie/B-tree混合和B-tree，這樣的樹(shù)形結(jié)構(gòu)
• 與無(wú)鎖模式相比，OLC也是單線(xiàn)程數(shù)據(jù)結(jié)構(gòu)，易于使用，只需要少量的修改

相關(guān)工作

鎖耦合是1977年提出的在B樹(shù)上并發(fā)操作的方法。樹(shù)遍歷期間最多持有兩個(gè)鎖，讀/寫(xiě)鎖。

1981年B-link樹(shù)。一次持有一個(gè)鎖，在釋放父鎖和獲取子鎖之間，有節(jié)點(diǎn)拆分的中間狀態(tài)，當(dāng)發(fā)生拆分時(shí)，正在搜索的鍵可能在該節(jié)點(diǎn)的右兄弟節(jié)點(diǎn)。B-link樹(shù)和鎖耦合有相同的可擴(kuò)展性問(wèn)題(獲得的鎖數(shù)量相同)。

2001年樂(lè)觀(guān)無(wú)鎖索引遍歷OLFIT，引入了版本計(jì)數(shù)器的概念，稱(chēng)之為樂(lè)觀(guān)鎖。OLFIT十分復(fù)雜

接下來(lái)20年，內(nèi)存容量的增長(zhǎng)導(dǎo)致對(duì)其他數(shù)據(jù)結(jié)構(gòu)的大量研究。2010年的A practical concurrent binary search tree是第一個(gè)提出跨節(jié)點(diǎn)交叉驗(yàn)證的論文，而不是像OLFIT分別驗(yàn)證每個(gè)節(jié)點(diǎn)——"hand-over-hand, optimistic validation"。后來(lái)的MassTree基于相同的思想，用于復(fù)雜協(xié)議的部分使用。

關(guān)于A(yíng)RT提出了兩個(gè)實(shí)用性強(qiáng)的并發(fā)控制協(xié)議ROWEX和OLC。而ROWEX需要修改底層的數(shù)據(jù)結(jié)構(gòu)(在原始ART中節(jié)點(diǎn)內(nèi)有序，為適應(yīng)ROWEX改為了無(wú)序)。OLC無(wú)需對(duì)數(shù)據(jù)結(jié)構(gòu)進(jìn)行其他修改。

Bw-tree的研究也證明了OLC的優(yōu)秀性能。而前文也表明了對(duì)于寫(xiě)密集的工作負(fù)載，有鎖通常比無(wú)鎖的同步性能更好。這仿佛在暗示OLC可以作為同步的通用標(biāo)準(zhǔn)，同步的范式。

樂(lè)觀(guān)鎖耦合

在傳統(tǒng)鎖耦合上，用的還是讀寫(xiě)鎖，獲取釋放鎖都要寫(xiě)入共享內(nèi)存導(dǎo)致cache miss。這樣就算是只讀的工作負(fù)載，根節(jié)點(diǎn)的鎖仍然會(huì)成為爭(zhēng)用的焦點(diǎn)。

悲觀(guān)鎖對(duì)于B樹(shù)很不友好，因?yàn)楦?jié)點(diǎn)的修改非常罕見(jiàn)，但是遍歷樹(shù)的過(guò)程中都要鎖定根節(jié)點(diǎn)。更樂(lè)觀(guān)的方法，即不需要鎖定內(nèi)部節(jié)點(diǎn)，更有利于B 樹(shù)。

樂(lè)觀(guān)鎖的工作
讀操作：
1.讀取鎖的版本(如果鎖未釋放，restart)
2.訪(fǎng)問(wèn)節(jié)點(diǎn)
3.再次讀版本驗(yàn)證訪(fǎng)問(wèn)期間沒(méi)有修改
如果最后一步驗(yàn)證失敗，restart。

寫(xiě)操作和傳統(tǒng)的排它鎖一樣
1.獲取鎖(必要時(shí)等待)
2.訪(fǎng)問(wèn)/寫(xiě)節(jié)點(diǎn)
3.版本號(hào)++，解鎖節(jié)點(diǎn)

傳統(tǒng)lock coupling和opitmistic lock couping的對(duì)比

OLC代碼

實(shí)現(xiàn)樂(lè)觀(guān)鎖，可以把鎖和版本計(jì)數(shù)器合成一個(gè)64bit的word。典型的讀操作原子地讀版本計(jì)數(shù)器，在C++11中可以用std::atomic實(shí)現(xiàn)。
在x86中，由于x86強(qiáng)內(nèi)存順序保證，原子讀是很便宜的。順序一致的加載不需要memory fences。因此加載時(shí)std::atomic的唯一作用就是防止指令重排。這使得版本訪(fǎng)問(wèn)和驗(yàn)證很便宜。以排他模式獲取和釋放樂(lè)觀(guān)鎖與傳統(tǒng)鎖的代價(jià)相當(dāng)。

OLC代碼需要能夠處理重新啟動(dòng)，因?yàn)轵?yàn)證或鎖升級(jí)可能會(huì)導(dǎo)致并發(fā)失敗。放在循環(huán)中的容易實(shí)現(xiàn)restart，這樣的循環(huán)還可以限制樂(lè)觀(guān)restart的次數(shù)，并在競(jìng)爭(zhēng)嚴(yán)重的時(shí)候恢復(fù)到悲觀(guān)鎖模式。會(huì)退到傳統(tǒng)鎖能力是OLC健壯性的一個(gè)主要優(yōu)勢(shì)。

OLC在刪除和重用節(jié)點(diǎn)時(shí)需要小心，因?yàn)閯h除線(xiàn)程不能確定某個(gè)節(jié)點(diǎn)可以被回收，因?yàn)槠渌€(xiàn)程仍然可能樂(lè)觀(guān)地從該節(jié)點(diǎn)讀取數(shù)據(jù)。因?yàn)樾枰褂萌鏴poch-based回收, hazard pointers或optimized hazard pointers。

評(píng)估

對(duì)于查找，OLC直到20個(gè)線(xiàn)程時(shí)可擴(kuò)展性仍可達(dá)到線(xiàn)性。