一、C無(wú)鎖(lockfree)數(shù)據(jù)結(jié)構(gòu)與有鎖數(shù)據(jù)結(jié)構(gòu)相比
在現(xiàn)代多核 CPU 中,提升性能的重點(diǎn)的不在于有鎖還是無(wú)鎖,而是盡可能減少核間通訊。
要減少核間通訊,就要減少寫競(jìng)爭(zhēng),要減少寫競(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í)際上仍然有鎖,只是把它移到了用戶代碼,理想條件下,競(jìng)爭(zhēng)應(yīng)該非常罕見(jiàn),鎖的作用就是在這種非常罕見(jiàn)的情況下,保證并發(fā)程序正確地按照預(yù)期順序執(zhí)行。如果競(jìng)爭(zhēng)率很高,那不管是有鎖還是無(wú)鎖,性能損失都是非常大的。
例如在 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 讓出來(lái),起到很好的效果,避免了 CPU 的浪費(fèi)。
延伸閱讀:
二、無(wú)鎖數(shù)據(jù)結(jié)構(gòu)的好處
主要原因: 將并發(fā)最大化。
使用基于鎖的容器, 會(huì)讓線程阻塞或等待; 互斥鎖削弱了結(jié)構(gòu)的并發(fā)性。 在無(wú)鎖數(shù)據(jù)結(jié)構(gòu)中, 某些線程可以逐步執(zhí)行。 在無(wú)等待數(shù)據(jù)結(jié)構(gòu)中, 無(wú)論其他線程當(dāng)時(shí)在做什么, 每一個(gè)線程都可以轉(zhuǎn)發(fā)進(jìn)度。
健壯性:
如果線程在持有鎖的同時(shí)死亡,那么該數(shù)據(jù)結(jié)構(gòu)將永遠(yuǎn)被破壞。但是,如果線程在對(duì)無(wú)鎖數(shù)據(jù)結(jié)構(gòu)的操作中途中途死亡,則除了該線程的數(shù)據(jù)外,什么都不會(huì)丟失。其他線程可以正常進(jìn)行。
死鎖活鎖問(wèn)題:
死鎖問(wèn)題不會(huì)困擾無(wú)鎖數(shù)據(jù)結(jié)構(gòu); 無(wú)等待的代碼不會(huì)被活鎖所困擾,因其操作執(zhí)行步驟是有上限的。