使用CAS實作無鎖的SkipList

感謝同僚【付哲】釋出此文。

并發環境下最常用的同步手段是互斥鎖和讀寫鎖，例如pthread_mutex和pthread_readwrite_lock，常用的範式為：

這種方法的優點是：

程式設計模型簡單，如果小心控制上鎖順序，一般來說不會有死鎖的問題；

可以通過調節鎖的粒度來調節性能。

缺點是：

所有基于鎖的算法都有死鎖的可能；

上鎖和解鎖時程序要從使用者态切換到核心态，并可能伴随有線程的排程、上下文切換等，開銷比較重；

對共享資料的讀與寫之間會有互斥。

無鎖程式設計（嚴格來講是非阻塞程式設計）可以分為lock free和wait-free兩種，下面是對它們的簡單描述：

lock free：鎖無關，一個鎖無關的程式能夠確定它所有線程中至少有一個能夠繼續往下執行。這意味着有些線程可能會被任意的延遲，然而在每一個步驟中至少有一個線程能夠執行下去。是以這個系統作為一個整體總是在前進的，盡管有些線程的進度可能沒有其它線程走的快。

wait free：等待無關，一個等待無關的程式可以在有限步之内結束，而不管其它線程的相對執行速度如何。

lock based：基于鎖，基于鎖的程式無法提供上面的任何保證，任一線程持有了某互斥體并處于等待狀态，那麼其它想要擷取同意互斥體的線程隻有等待，所有基于鎖的算法無法擺脫死鎖的陰影。

本文提到的無鎖單指lock free。

常見的lock free程式設計一般是基于cas(compare and swap)操作：

即檢視記憶體位址ptr處的值，如果為oldvalue則将其改為newvalue，并傳回true，否則傳回false。x86平台上的cas操作一般是通過cpu的cmpxchg指令來完成的。cpu在執行此指令時會首先鎖住cpu總線，禁止其它核心對記憶體的通路，然後再檢視或修改*ptr的值。簡單的說cas利用了cpu的硬體鎖來實作對共享資源的串行使用。它的優點是：

開銷較小：不需要進入核心，不需要切換線程；

沒有死鎖：總線鎖最長持續為一次read+write的時間；

隻有寫操作需要使用cas，讀操作與串行代碼完全相同，可實作讀寫不互斥。

程式設計非常複雜，兩行代碼之間可能發生任何事，很多常識性的假設都不成立。

cas模型覆寫的情況非常少，無法用cas實作原子的複數操作。

而在性能層面上，cas與mutex/readwrite lock各有千秋，簡述如下：

單線程下cas的開銷大約為10次加法操作，mutex的上鎖+解鎖大約為20次加法操作，而readwrite lock的開銷則更大一些。

cas的性能為固定值，而mutex則可以通過改變臨界區的大小來調節性能；

如果臨界區中真正的修改操作隻占一小部分，那麼用cas可以獲得更大的并發度。

多核cpu中線程排程成本較高，此時更适合用cas。

單向連結清單實作的核心就是insert函數，這裡我們用兩個版本的insert函數來進行簡單的示範，使用的cas操作為gcc提供的__sync_compare_and_swap函數。

首先是無序的insert操作，即将新結點插入到指定結點的後面。

代碼分析：

首先修改node->next，此時node還沒有完成插入，隻能被本線程看到，是以這個修改可以直接進行。

在if中嘗試修改prev->next，如果失敗，則表明prev->next剛剛被其它線程修改了，則重複這一過程。

然後是有序的insert操作，即保證prev<= node <= next。

這段代碼相比上一版本多了一個next變量。如果去掉next變量，那麼代碼就是下面的樣子。

上面的代碼有着很嚴重的安全隐患：prev是共享資源，是以每個prev->next的值不一定是相等的！解決辦法就是用一個局部變量來儲存某個時刻prev的值，進而保證我們在不同地方進行比較的結點是一緻的。

目前常用的key-value資料結構有三種：hash表、紅黑樹、skiplist，它們各自有着不同的優缺點（不考慮删除操作）：

hash表：插入、查找最快，為o(1)；如使用連結清單實作則可實作無鎖；資料有序化需要顯式的排序操作。

紅黑樹：插入、查找為o(logn)，但常數項較小；無鎖實作的複雜性很高，一般需要加鎖；資料天然有序。

skiplist：插入、查找為o(logn)，但常數項比紅黑樹要大；底層結構為連結清單，可無鎖實作；資料天然有序。

如果要實作一個key-value結構，需求的功能有插入、查找、疊代、修改，那麼首先hash表就不是很适合了，因為疊代的時間複雜度比較高；而紅黑樹的插入很可能會涉及多個結點的旋轉、變色操作，是以需要在外層加鎖，這無形中降低了它可能的并發度。而skiplist底層是用連結清單實作的，可以實作為lock free，同時它還有着不錯的性能（單線程下隻比紅黑樹略慢），非常适合用來實作我們需求的那種key-value結構。leveldb、reddis的底層存儲結構就是用的skiplist。

那麼，skiplist是什麼呢？它由多層有序連結清單組成，每層連結清單的結點數量都是上一層的x倍，而它的插入和查找操作都從頂層開始進行。

（圖檔取自wiki）

從上圖可以很容易看出查找的方式：

從頂層的頭結點出發；

若下一結點為目标值，則傳回結果；

若下一結點小于目标值，則前進；

若下一結點大于目标值或為null，則：

若目前處于最底層，則傳回null；

下降一層，重複2-4步。

在skiplist中，結點層數非常關鍵，如果各個結點的層數均勻分布，那麼插入與查找的效率就會比較高。為了實作這一目的，skiplist中每個結點的層數是在插入前随機算出來的，其基本原理就是令結點在i層的機率是i+1層的x倍，代碼如下：

插入新結點的過程與查找很類似，這裡我們假設連結清單中的各結點不允許重複：

計算出新結點的層數lv；

從lv層的頭結點出發，開始查找過程；

如果找到目标值，傳回null；

如果目前處于最底層，則建立新結點，并依次将新結點插入到1-lv層；

可以看出，插入操作的1-3步是單純的讀操作，隻有第4步才是對共享資源的寫操作。而第4步的插入實質上就是有序連結清單的插入操作，我們在前面已經簡述了如何用cas實作它。是以，隻要保證插入順序是從底層向上依次插入，那麼就可以将skiplist實作為lock free。插入順序從底向上進行的原因如下。

n個插入操作肯定需要至少n次cas，而任意一個cas成功後就意味着新結點已經成為了skiplist的一部分，變成了共享資源，則新結點就需要遵循其它結點的原則：每個結點都同時存在于1-lv層。容易看出，隻有從底層向上插入才能滿足這一條件。

多個cas操作本身沒有原子性，即在n次插入沒有完成前，新結點會表現出一定的不一緻性，具體來說就是多個線程先後通路新結點時，看到的它的層數并不相同。這種不一緻性會比較輕微的影響skiplist的性能，而不會影響它的正确性。

skiplist的插入代碼如下：

其中listinsert就是對前面有序連結清單插入的一個簡單改寫。整個插入過程遞歸實作，進而滿足了插入順序要從底向上的要求。

在設計無鎖skiplist時，不光需要我們将顯式的鎖用cas替換掉，還需要盡量避免一些隐式的鎖，以及一些非線程安全的函數。

randlevel中的rand()是非線程安全的函數，需要替換為線程安全的版本（如非标準庫的rand_r()），或是由各線程自己來儲存rand使用的seed。

在建立skiplist的時候需要指定一個max_level，即頭結點的層數，這個值在此skiplist生命期中固定不變。一般來說12-20層都是可以接受的。

全局new内部會加鎖，如果這裡有瓶頸的話需要換用自定義的記憶體池。

如果使用了記憶體池，那麼必須確定記憶體池本身是無鎖且支援并發寫的。否則就隻能将skiplist改寫為單寫多讀版本。

在計算新結點的層數時，需要傳入一個maxlevel，這裡有兩種常見做法：可以傳入skiplist的最大層數max_level，也可以傳入目前最大層數toplevel + 1。兩種做法的優缺點為：

傳入max_level可能在skiplist中結點數量較少時就達到很高的層數，降低了此時插入與查找的性能；但如果有序插入多個新結點，能保證各結點的層數均勻分布。

傳入toplevel + 1可以保證在結點數較少時不太可能出現很高的層數，但在有序插入多個新結點時，可能導緻前面插入結點的層數整體要低于後面插入的結點。

skiplist的修改操作也需要是lock free的，是以需要将node中的item改為指針，在修改某結點值的時候用cas來替換掉舊指針，并在完成後删除。

skiplist也可以在最底層加入反向指針prev，這樣就能直接o(1)的反向疊代。帶來的問題是更大的不一緻性——在插入未完成時兩個線程分别正向和反向疊代，看到的skiplist是不一緻的。但可以保證skiplist在插入完成後的最終狀态是一緻的。

本文隻是對無鎖skiplist設計的一個簡單回顧，不包括詳細的實作代碼。因為還不确定自己設計的有沒有纰漏，還需要認真學習一下leveldb和reddis中的skiplist代碼。

<a href="http://en.wikipedia.org/wiki/skip_list">http://en.wikipedia.org/wiki/skip_list</a>

<a href="http://www.myexception.cn/ai/972131.html">http://www.myexception.cn/ai/972131.html</a>

<a href="http://www.seflerzhou.net/post-6.html">http://www.seflerzhou.net/post-6.html</a>

<a href="http://coolshell.cn/articles/8239.html">http://coolshell.cn/articles/8239.html</a>

<a href="http://blog.csdn.net/sunmenggmail/article/details/12648465">http://blog.csdn.net/sunmenggmail/article/details/12648465</a>