一、C無鎖(lockfree)數據結構與有鎖數據結構相比
在現代多核 CPU 中,提升性能的重點的不在于有鎖還是無鎖,而是盡可能減少核間通訊。
要減少核間通訊,就要減少寫競爭,要減少寫競爭,最直接的途徑就是細化鎖粒度,這不是一件容易的事,無鎖數據結構也不是一件容易的事,好的無鎖數據結構實現一般會同時細化鎖粒度。比如并發隊列需要幾個鎖?再細分一下 spsc, spmc, mpsc, mpmc,又各自需要哪些鎖?
實際上,很多所謂的 LockFree 數據結構的實現,只是使用 user spin lock + yield 代替 mutex,這種鎖實際上不 scale,并且不 fair,要極力避免干這種事。
LockFree 實際上仍然有鎖,只是把它移到了用戶代碼,理想條件下,競爭應該非常罕見,鎖的作用就是在這種非常罕見的情況下,保證并發程序正確地按照預期順序執行。如果競爭率很高,那不管是有鎖還是無鎖,性能損失都是非常大的。
例如在 RocksDB 中,并發寫 MemTable 時就使用了非常激進的 spin,導致并發寫較高時大量 CPU 都浪費在 spin 上了,ToplingDB 反其道而行,把這一塊改成了發生競爭時優先 wait(使用 futex),把 cpu 讓出來,起到很好的效果,避免了 CPU 的浪費。
延伸閱讀:
二、無鎖數據結構的好處
主要原因: 將并發最大化。
使用基于鎖的容器, 會讓線程阻塞或等待; 互斥鎖削弱了結構的并發性。 在無鎖數據結構中, 某些線程可以逐步執行。 在無等待數據結構中, 無論其他線程當時在做什么, 每一個線程都可以轉發進度。
健壯性:
如果線程在持有鎖的同時死亡,那么該數據結構將永遠被破壞。但是,如果線程在對無鎖數據結構的操作中途中途死亡,則除了該線程的數據外,什么都不會丟失。其他線程可以正常進行。
死鎖活鎖問題:
死鎖問題不會困擾無鎖數據結構; 無等待的代碼不會被活鎖所困擾,因其操作執行步驟是有上限的。