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

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

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

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

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

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

延伸閱讀：

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

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

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

健壯性：

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

死鎖活鎖問題：

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