Concepts of SkipList: Implementation, Concurrency and Lock-free

Posted on

Concept

  • Ordered Data Structure
  • Combining Multi-layer linked list together, the node number of every layer will exponential decline with a factor K and K = 1 / r which r is a critical threshold for skiplist.
  • Each node has N pointer to its next nodes, the N is known as the degree of this node.
  • Support: O(log n) CRUD (Create/Read/Update/Delete)

  • Find Operation

    1
    2
    3
    4
    5
    6
    7
    8
    9
    Find (K):
      ptr = head->next_list[max_level - 1]
      for i in max_level to 0:
        find the last node (last_node) whose key is large than K
        ptr = pre_node->next_list[i]
        // updates[i] = pre_node
      if ptr->key == K
        return ptr
      return nullptr // return updata array if you need a insert

  • Insert Operation

    1
    2
    3
    4
    5
    6
    7
    8
    Insert (K, V):
      ptr, updates = Find(K)
      if ptr == nullptr:
        new_node = NewSkipListNode()
        new_degree = skiplist_rand()
        for i in 0 to max_level:
          new_node->next_node[i] = updates->next_list[i]
          updates->next_list[i] = new_node

Skiplist

  • A fine blog will describe more details.

Vary Implementations

  • My Implementation is here
  • Google nbds is here

Research Areas

  • NVM based data structure
    • How to design skiplist with less write overhead
    • How to persist skiplist in NVM
    • How to recover skiplist in NVM
  • Distributed SkipList
    • Partition/Across-Layers?
    • How to gain a higher concurrency
  • Write Optimization
    • Write-Optimize Skip List PODS’ 17
      • Cache higher level of the data structures (closest to root)
      • TO DO ….

Issues when concurrent accessing

  • Write-Write Conflict
  • Dirty Read
  • Fine-grained lock for every node
  • COW (copy on write) will cause O (n) copying overhead

Lock-Free