? ? ? ? 上一篇文章中我們詳細講述了跳表的增添、查找和修改的操作，這篇文章我們來講解一下跳表在多線程并發時的安全問題。在Redis中，除了網絡IO部分和大文件的后臺復制涉及到多線程外，其余任務執行時全部都是單線程，這也就意味著在Redis中不存在跳表的多線程并發問題。但在Java程序開發中，我們可能也會使用到跳表，這時候就不得不考慮如何設計一個并發安全的調表結構。

? ? ? ? JDK中提供了一種支持并發安全的跳表結構ConcerrentSkipListMap可以直接使用。不過這篇文章我們來自己思考一下在設計并發安全的跳表時我們需要考慮哪些內容。

全局讀寫鎖

? ? ? ? 首先對于跳表的操作可以分為讀操作和寫操作兩種。那么最簡單粗暴的方法就是對整個跳表加讀寫鎖。所有的寫操作需要持有寫鎖才可以進行，所有的讀操作可以同時持有多把讀鎖，來實現并發讀取。不過這時候我們來考慮這樣一個問題，對跳表加了全局讀寫鎖，如果一個線程拿到了寫鎖，并且對跳表的操作時間很長，那么后邊所有的寫操作和讀操作都會被阻塞，如果對跳表的大小、存儲數據的大小和每次寫操作的時間進行嚴格限制，全局加讀寫鎖在寫少讀多的場景下還是有一定的可用性的。

? ? ? ? 上面全局加讀寫鎖雖然實現簡單，但是有很大可能會造成線程間的阻塞等待，實用性并不高，而造成阻塞問題的根源是鎖的顆粒度太大了，有沒有一種方法可以將鎖的顆粒度進行細化，這樣就可以同時允許多個線程拿到不同的鎖進行操作，降低線程阻塞的概率。

節點讀寫鎖

? ? ? ? 我們來思考這樣一個問題，當我們對單向鏈表并發操作時，對于寫操作（增加、刪除），其實只需要執行一步操作，就是找到被操作節點的前一個節點，并將其next修改為被操作節點的后一個節點。這就意味著，如果我們在并發環境下對被操作節點的前一個節點進行加鎖操作，就可以保證同一時間只有一個線程對被加鎖節點后的節點進行操作。

? ? ? ? 在對跳表的節點進行加鎖時，我們還需要多考慮一點，由于新加入的節點的高度是隨機的，可能會比當前跳表的高度要高，這個時候我們需要對跳表的頭結點進行加鎖，并修改跳表的最大高度。

? ? ? ? 總的來說，其實我們在細化跳表中鎖的顆粒度到節點上時，需要考慮兩部分。第一是如果新加入的節點高度小于跳表原最大高度，這時就從上至下逐層取到操作節點的左邊界節點的鎖即可；第二是如果新加入的節點高度大于跳表原有最大高度，這時就需要持有跳表的頭結點鎖，然后再進行第一部分的操作。

查詢操作

? ? ? ? 查詢操作的步驟就是從跳表的最高層head節點開始，從上往下逐層遍歷，直到找到key值小于target并且最接近于target的左邊界節點，然后進行層數下降。具體的流程如下圖所示：

增添操作

? ? ? ? 增加操作執行時，如果增加的節點已經存在了，則會更新為新值，如果不存在，則要將其插入跳表中。可以將增加操作分為以下四個步驟：

? ? ? ? ①首先檢查要添加的節點是否存在。

? ? ? ? ②如果存在，則將舊值更新為新值。

? ? ? ? ③如果不存在，則將新節點插入跳表中。

? ? ? ? ④如果要插入節點，并且節點高度比原有跳表要高，則對跳表的高度進行擴容。

? ? ? ? 上述步驟中的①、②、③在并發情況下需要是原子性的，來保證單一線程對跳表更改的有效性。具體的流程如下圖所示：

刪除操作

? ? ? ? 刪除操作的步驟就是查詢到要刪除的節點，將其每一層的前一個節點的指針進行變更，指向當前層被操作節點的后一個節點就可以了。具體的流程如下所示：

? ? ? ? 不過刪除操作存在一個問題，就是左邊界這種策略對于刪除和增添并發執行的時候會失效，可能會造成新增添的節點被誤刪。所以造執行刪除操作時，還是采用全局鎖的方式來對其和增添操作進行隔離。

? ? ? ? 本文主要梳理了一下自己實現并發安全的跳表的一些思路，算是學完Redis底層數據結構和并發編程之后筆者的一些思考，如果有什么問題或者勘誤，歡迎評論區留言。

????????