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

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

要減少核間通訊，就要減少寫競(jìng)爭(zhēng)，要減少寫競(jìng)爭(zhēng)，最直接的途徑就是細(xì)化鎖粒度，這不是一件容易的事，無鎖數(shù)據(jù)結(jié)構(gòu)也不是一件容易的事，好的無鎖數(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í)際上仍然有鎖，只是把它移到了用戶代碼，理想條件下，競(jìng)爭(zhēng)應(yīng)該非常罕見，鎖的作用就是在這種非常罕見的情況下，保證并發(fā)程序正確地按照預(yù)期順序執(zhí)行。如果競(jìng)爭(zhēng)率很高，那不管是有鎖還是無鎖，性能損失都是非常大的。

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

延伸閱讀：

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

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

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

健壯性：

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

死鎖活鎖問題：

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