聊一聊跳錶數據結構

背景

在討論那些 “不著名” 的數據結構時，跳錶經常會出現。但實際上它們並沒有那麼默默無聞，事實上許多生產級軟件都在積極地使用它們。在這篇文章中，我將描述如何製作一個玩具式的實現，以及潛在的性能優化和它們在現實世界中的使用案例，通過這三方面來探討跳錶。那麼什麼是跳錶呢？跳錶是一種指向性的數據結構，它的靈感來自鏈表和二叉樹。它們是排列在不同層級上的排序鏈表的集合，其中層級在設計上允許跳過部分節點，以便在後面搜索鍵時獲得對數的複雜度。它們是二叉樹的替代品，甚至在某些情況下就是 B 樹，事實上，跳錶的最後一層看起來有點像 B+ 樹。對於需要有序存儲或快速查找的隨機負載，跳錶的執行性能非常好。跳錶不同層級的構建本質上是基於概率的，因此如果底層的隨機算法不夠均勻，這些層級上的列表便很容易變得不平衡。與 Hashmap 和 Tree 相比，跳錶通常更容易實現，這使它們成爲理想的替代選擇，特別是當只需要在內存中查找時。爲什麼要使用跳錶? 首先，查找、刪除和插入具有對數的時間複雜度。其次，這些操作是相對非常容易實現的，因爲不需要重新平衡樹 (如 RB 樹，AVL 樹，B+ 樹) 或調整容器大小(如 HashMaps)。最後，線程安全的實現也不太複雜，與其他有序集合相比，有鎖和無鎖的併發實現通常內存佔用也比較低。

讓我們用圖來介紹一下跳錶。

這個圖本質上代表了按鍵的順序組織的鏈表數據結構的集合。其中有不同的層級，它們有序的包含前一級別的元素子集。通常相同節點沒有多個副本，它只是一種在不同級別表示相同節點的方法，但這可能取決於具體實現。例如在圖中，存在於所有層級上的 Node 5 連接到了 Node 24、Node 15、Node 7。它可能看起來有多個副本，但它是同一個節點，只是具有不同級別的多個連接。

玩具實現

對於實現，我將使用帶有泛型的 Go ，因爲我已經想使用它們一段時間了，沒有一個比泛型類型安全的集合更好的用例了。使用泛型通常需要約束或特徵 (如 rustacans 所說)，我在標準庫中找不到約束來強制元素順序，所以我使用了 golang.org/x/exp/constraints 包，它提供了 Ordered 約束，這將爲我們提供一種比較方法，並在跳錶中保持它們的排序。

數據結構

讓我們定義一個結構體來存儲單個節點的鍵和值：

type Record[K constraints.Ordered, V any] struct {  
   Key   K  
   Value V  
}

然後是節點本身：

type SkipNode[K constraints.Ordered, V any] struct {  
   record  *Record[K, V]  
   forward []*SkipNode[K, V]  
}

注意 forward[i] 表示在 第 i 層級 的列表中的下一個成員。例如，在上圖中，Node 5 的 forward[0] 將指針指向 Node 7，forward[1] 指向 Node 15，foward[2] 指向 Node 24。

一旦我們有了這些結構體定義，我們就可以定義構造函數來幫助我們快速構建結構：

func NewRecord[K constraints.Ordered, V any](key K, value V) *Record[K, V] {  
   return &Record[K, V]{  
      Key:   key,  
      Value: value,  
   }  
}  

func NewSkipNode[K constraints.Ordered, V any](key K, value V, level int) *SkipNode[K, V] {  
   return &SkipNode[K, V]{  
      record:  NewRecord(key, value),  
      forward: make([]*SkipNode[K, V], level+1),  
   }  
}

最後如下所示，我們可以編寫跳錶結構體：

type SkipList[K constraints.Ordered, V any] struct {  
   head  *SkipNode[K, V]  
   level int  
   size  int  
}

我們需要頭部節點，它本質上是用一個 虛擬節點 來幫助我們保持與跳錶剩餘部分的連接，size 是跳錶中的元素數量，levels 是當前跳錶中的層級數量，這將在稍後用於 插入 和 查找 操作。最後，爲了構造跳錶，我們可以編寫這樣的函數：

func NewSkipList[K constraints.Ordered, V any]() *SkipList[K, V] {  
   return &SkipList[K, V]{  
      head:  NewSkipNode[K, V](new(K), new(V), 0),  
      level: -1,  
      size:  0,  
   }  
}

查找操作

查找操作是跳錶中幾乎所有操作的核心算法。這很像二分搜索，但在每層的鏈表中，當我們在搜索中遇到 障礙 時，我們開始尋找下面的層級，並利用跳錶的有序和分層結構，得以跳過許多節點。算法可以總結如下

從跳錶的頂層開始查找 key。
只要當前 key 比要找的 key 小，就在同一個層級繼續向前查找。
如果碰巧找到了 key，則返回它的值。
如果下一個 key 比目標 key 大，那麼就開始查找下面的層級

func (s *SkipList[K, V]) Find(key K) (V, bool) {  
   x := s.head  
  
   for i := s.level; i >= 0; i-- {  
  
      for {  
         if x.forward[i] == nil || x.forward[i].record.Key > key {  
            break  
         } else if x.forward[i].record.Key == key {  
            return x.forward[i].record.Value, true  
         } else {  
            x = x.forward[i]  
         }  
      }  
   }  
  
   return *new(V), false    
}

我們可以想象在尋找 key 時發生的事情

插入操作

爲了執行對跳錶的插入，我們需要幾個 helper 方法。首先是確定新節點的層級。在我們的實現中，我們使用了樸素的概率方法，即使用隨機函數來選擇層級，層級的概率是 2^(-L-1)。這在大多數情況下是可行的，並且非常容易實現，但它的效率取決於隨機函數的好壞。它可能總是選擇層級 0。理想情況下，我們希望從跳錶得到的是節點數比它下面級別少一半，以便充分利用二分搜索的優勢。

func (s *SkipList[K, V]) getRandomLevel() int {  
   level := 0  
   for rand.Int31()%2 == 0 {  
      level += 1  
   }  
   return level  
}

第二個是 adjustLevel，這個方法負責增加跳錶頭部的前向指針數組大小，以便能夠保存新層級的指針，以防新節點的層級大於跳錶當前所包含的層級。我們並不關心在頭節點記錄中存儲的鍵值，這就是爲什麼我用 *new(K)， *new(V) 來存儲空值的原因。我也可以存儲 nil 指針，但這樣也行。

func (s *SkipList[K, V]) adjustLevel(level int) {  
   temp := s.head.forward  
   
   s.head = NewSkipNode(*new(K), *new(V), level)
   s.level = level  
   
   copy(s.head.forward, temp)  
}

插入建立在我們前面描述的 helper 方法和 Find 操作的基礎上。它可以總結爲以下步驟

爲新節點指定一個層級
調整跳錶頭部的大小，以便能夠存儲指定層級的指針
通過比較 key 開始在每一層尋找新節點的適當位置，同時開始爲新節點構建 next 指針數組。當繼續往下走的時候就這樣做。
更新指針以將新節點插入到正確的位置。

func (s *SkipList[K, V]) Insert(key K, value V) {   
   newLevel := s.getRandomLevel()  
  
   if newLevel > s.level {  
      s.adjustLevel(newLevel)  
   }  
  
   newNode := NewSkipNode[K, V](key, value, newLevel)  
   updates := make([]*SkipNode[K, V], newLevel+1)  
   x := s.head  
  
   for i := s.level; i >= 0; i-- {  
      for x.forward[i] != nil && x.forward[i].record.Key < key {  
         x = x.forward[i]  
      }  
      updates[i] = x  
   }  
  
   for i := 0; i <= newLevel; i++ {  
      newNode.forward[i] = updates[i].forward[i]  
      updates[i].forward[i] = newNode  
   }
   
   s.size += 1
}

我們可以想象在尋找 key 時發生的事情

Delete Operation

刪除操作

刪除操作與查找操作非常相似，只需在查找不同層級的鍵時不斷刪除引用。

func (s *SkipList[K, V]) Delete(key K) {  
  
   x := s.head  
  
   for i := s.level; i >= 0; i-- {  
      for {  
         if x.forward[i] == nil || x.forward[i].record.Key > key {  
            break  
         } else if x.forward[i].record.Key == key {  
            x.forward[i] = x.forward[i].forward[i]  
         } else {  
            x = x.forward[i]  
         }  
      }  
   }  
}

如下所示，我們可以想象刪除操作過程。

性能優化

內存訪問

與鏈表或二叉樹一樣，跳錶不是緩存友好型的。大多數現代 CPU 都試圖預測未來會使用哪些內存。最常見的算法是，它假設程序將請求大塊連續的數據 (如數組)，所以它試圖按預期將連續的內存塊加載到緩存行，但鏈表節點不一定連續，這將導致在 CPU 緩存無用數據)，因爲只有幾個塊是相關的，其餘的空間將被浪費，下一個節點可能位於完全不同的內存塊中。數組最適合在 L1 中緩存，但是對於鏈表，不能保證下一個節點能在緩存中匹配，甚至不能保證 L2 或 L3 緩存中能匹配到，這取決於內存分配器的表現。

如果我們看一下下圖中的訪存延遲時間，就可以清楚地看到如果緩存失效太頻繁，性能會有多糟糕。這意味着訪問列表中的不同節點可能比訪問數組中的下一個元素要慢 100-200 倍。

使用共享內存分配器

通常情況下，跳錶或鏈表的問題根源在於緩存不友好的內存訪問模式。讓我們看看高效分配內存是如何幫助我們提高性能的。

從在上圖中可以看到, 內存分配可以採取三種形式：

(1) 是分配器分配隨機分佈的內存塊。(2) 是分配器分配連續但沒有按列表指針的正確順序的內存塊。(3) 是指分配器分配連續且符合列表訪問模式的內存塊。

爲簡單實現分配的內存很有可能看起來像 (1) 這樣，基本上表示分佈在各處的內存塊。對鏈表下一個節點的任何訪問都將是緩存不友好的。如果我們使用內存池或共享分配器，我們可以使用類似 (2) 的語句。節點的所有內存都可以從一個專用的內存塊中分配。這樣可以提高數據緩存命中率和 TLB 緩存命中率。(3)是我們在理想情況下想要的，但實現可能會非常複雜，特別是刪除操作。

一些編程語言可以很容易地替換內存分配器，如 C++ 和 Rust，然而這對於 Go 來說是棘手的。但可以通過手動內存管理和使用自定義內存池來完成。

使用鬆散跳錶

鬆散跳錶在每個節點中存儲多個元素。鬆散目的是提供更好的緩存性能，但這取決於所訪問對象的大小。這些變量可能會浪費額外的空間，因爲每個節點會爲數組分配內存，而數組可能不會一直被佔用。刪除操作可能很棘手，因爲它會在節點數組中創建間隙。搜索與常規跳錶非常相似，當找到一個候選數組時，對數組進行線性搜索。要插入時需要 push 到數組。如果沒有多餘的可用空間，則通過添加新的跳錶節點進行插入。

跟蹤每一層的元素

我在描述其中一個 helper 方法時簡要地討論了這一點。在我的實現中，決定層級位置是基於概率而非確定性的，但問題在於，如果存在一個糟糕的隨機函數，我們便有可能創造出不平衡的跳錶。不平衡的意思是，某個層級的節點數量超過理想數量。所以爲了讓搜索性能儘可能快，一個高效的實現應該確保一個層級只有前一個層級一半的元素。它允許在查找 key 時最高效地 跳過 部分節點。當然，主動平衡會降低插入和刪除性能，所以需要適當的權衡。

業界跳錶使用

與平衡樹或哈希表相比，跳錶並不常見，但偶爾你也會遇到它們。就我個人而言，我只在以下地方見過它們，但我很確定這並不是特例，如果你仔細看，你會發現它在更常見的地方。

RocksDB

RocksDB 是一個用於快速存儲的可嵌入持久化鍵值存儲。RocksDB 還可以作爲 client-server 模式數據庫的基礎，目前最流行的使用它的數據庫之一是 CockroachDB。RocksDB 建立在 LevelDB 上，可擴展運行在多核 CPU 的服務器上，有效地使用快速存儲，支持 IO-bound、內存讀寫和一致性寫的工作負載。在內部，RocksDB 使用 LSM 樹進行存儲，並且在將已排序的鍵以 SST 文件的形式刷新到磁盤之前，需要一個 memtable 將其存儲在內存中。memtable 在 RocksDB 中的一種實現是由 RocksDB 中的跳錶做到的。新的寫操作總是將數據插入到 memtable 中，而讀操作在從 SST 文件讀取之前必須查詢 memtable，因爲 memtable 中的數據總是更新。

基於跳錶的 memtable 在讀寫、隨機訪問和順序 scan 方面都提供了良好的性能。此外，它還提供了一些其他 memtable 實現目前不支持的有用特性，比如併發插入和基於代價插入。

Redis SortedSet

Redis Sorted Sets 類似於 Sets，它的功能是用用戶定義的值存儲成員。引用 Antirez 的話，選擇它而不是平衡的樹是因爲

它們不是很佔用內存。但這基本上取決於你的使用。對於具有給定數量的層級，改變節點出現的概率參數將使內存佔用小於 b 樹。

一個 sorted set 通常是許多 ZRANGE 或 ZREVRANGE 操作的目標，也就是說，遍歷跳錶如同遍歷鏈表。通過這種操作，跳錶的緩存本地性至少與其他類型的平衡樹一樣好。

它們更容易實現、調試等等。例如，由於跳錶的簡單性，我收到了一個補丁 (已經合併在 Redis master)，以 O(log(N)) 複雜度增強跳錶實現 ZRANK 。它只需要對代碼做一些小小的修改。

MuQSS Linux 調度器

Con Kolivas 維護了一系列調度器補丁集，多年來他爲自己的使用進行了大量的調優，主要集中在減少延遲以獲得更好的桌面體驗。2016 年 10 月初， Kolivas 發佈了他廣受歡迎的桌面調度器補丁集的設計，並將其重命名爲 MuQSS。MuQSS 是具有多個運行隊列的 CPU 調度器，每個 CPU 一個運行隊列。隊列被實現爲跳錶，而不是鏈表。Kolivas 的實現是一個爲他的調度器自定義的跳錶。

參考資料

https://johnysswlab.com/the-quest-for-the-fastest-linked-list/
https://dgraph.io/blog/post/manual-memory-management-golang-jemalloc/
https://github.com/facebook/rocksdb/wiki/MemTable#concurrent-insert
https://www.igvita.com/2012/02/06/sstable-and-log-structured-storage-leveldb/
https://www.cockroachlabs.com/docs/stable/architecture/storage-layer.html
https://vldb.org/pvldb/vol9/p1389-srinivasan.pdf
https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.170.719&rep=rep1&type=pdf
https://15721.courses.cs.cmu.edu/spring2018/papers/08-oltpindexes1/skiplists-done-right2016.pdf
https://15721.courses.cs.cmu.edu/spring2018/papers/08-oltpindexes1/pugh-skiplists-cacm1990.pdf
https://github.com/dai-shi/excalidraw-claymate
https://lwn.net/Articles/720227/

原文地址：

https://ketansingh.me/posts/lets-talk-skiplist/

原文作者：

ketansingh

本文永久鏈接：

https://github.com/gocn/translator/blob/master/2022/w34_Let’s_talk_skiplist.md

譯者：haoheipi

校對：watermelo

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/rFEMpJiOZJ02Aii0PxNXAQ

背景