一、C無(wú)鎖(lockfree)數(shù)據(jù)結(jié)構(gòu)與有鎖數(shù)據(jù)結(jié)構(gòu)相比

在現(xiàn)代多核 CPU 中，提升性能的重點(diǎn)的不在于有鎖還是無(wú)鎖，而是盡可能減少核間通訊。

要減少核間通訊，就要減少寫(xiě)競(jìng)爭(zhēng)，要減少寫(xiě)競(jìng)爭(zhēng)，最直接的途徑就是細(xì)化鎖粒度，這不是一件容易的事，無(wú)鎖數(shù)據(jù)結(jié)構(gòu)也不是一件容易的事，好的無(wú)鎖數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)一般會(huì)同時(shí)細(xì)化鎖粒度。比如并發(fā)隊(duì)列需要幾個(gè)鎖？再細(xì)分一下 spsc, spmc, mpsc, mpmc，又各自需要哪些鎖？

實(shí)際上，很多所謂的 LockFree 數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)，只是使用 user spin lock + yield 代替 mutex，這種鎖實(shí)際上不 scale，并且不 fair，要極力避免干這種事。

LockFree 實(shí)際上仍然有鎖，只是把它移到了用戶(hù)代碼，理想條件下，競(jìng)爭(zhēng)應(yīng)該非常罕見(jiàn)，鎖的作用就是在這種非常罕見(jiàn)的情況下，保證并發(fā)程序正確地按照預(yù)期順序執(zhí)行。如果競(jìng)爭(zhēng)率很高，那不管是有鎖還是無(wú)鎖，性能損失都是非常大的。

例如在 RocksDB 中，并發(fā)寫(xiě) MemTable 時(shí)就使用了非常激進(jìn)的 spin，導(dǎo)致并發(fā)寫(xiě)較高時(shí)大量 CPU 都浪費(fèi)在 spin 上了，ToplingDB 反其道而行，把這一塊改成了發(fā)生競(jìng)爭(zhēng)時(shí)優(yōu)先 wait(使用 futex)，把 cpu 讓出來(lái)，起到很好的效果，避免了 CPU 的浪費(fèi)。

延伸閱讀：

二、無(wú)鎖數(shù)據(jù)結(jié)構(gòu)的好處

主要原因： 將并發(fā)最大化。

使用基于鎖的容器， 會(huì)讓線(xiàn)程阻塞或等待； 互斥鎖削弱了結(jié)構(gòu)的并發(fā)性。 在無(wú)鎖數(shù)據(jù)結(jié)構(gòu)中， 某些線(xiàn)程可以逐步執(zhí)行。 在無(wú)等待數(shù)據(jù)結(jié)構(gòu)中， 無(wú)論其他線(xiàn)程當(dāng)時(shí)在做什么， 每一個(gè)線(xiàn)程都可以轉(zhuǎn)發(fā)進(jìn)度。

健壯性：

如果線(xiàn)程在持有鎖的同時(shí)死亡，那么該數(shù)據(jù)結(jié)構(gòu)將永遠(yuǎn)被破壞。但是，如果線(xiàn)程在對(duì)無(wú)鎖數(shù)據(jù)結(jié)構(gòu)的操作中途中途死亡，則除了該線(xiàn)程的數(shù)據(jù)外，什么都不會(huì)丟失。其他線(xiàn)程可以正常進(jìn)行。

死鎖活鎖問(wèn)題：

死鎖問(wèn)題不會(huì)困擾無(wú)鎖數(shù)據(jù)結(jié)構(gòu); 無(wú)等待的代碼不會(huì)被活鎖所困擾,因其操作執(zhí)行步驟是有上限的。