How to Build a Redis‑Style Sorted Set with Skiplist in Go

Building EasyRedis Sorted Set

The author creates a Redis‑like service called EasyRedis in Go across a series of articles, and this seventh part focuses on implementing the ordered set (sorted set) using a skiplist.

Requirement analysis

Each member must be unique (deduplication).

The collection must support forward and reverse ordered traversal.

Deduplication is achieved with a map[string]*Pair, while ordering is provided by a skiplist. The core structures are defined as:

type SortedSet struct {
    dict map[string]*Pair // map for member uniqueness
    skl  *skiplist       // skiplist for ordering
}

type Pair struct {
    Member string
    Score  float64
}

Linear‑list insertion and its limitation

In a plain linked list, inserting a new node (e.g., value 9) requires scanning from the head to find the predecessor – the largest node smaller than the new value. The article shows a diagram and pseudocode for this linear search.

type node struct {
    val int64
}
var curNode *node = &node{val:9}
if pre.next != nil && pre.next.val < curNode.val {
    pre = pre.next
}
pre.next = curNode

As the list grows, this linear scan becomes increasingly inefficient, prompting the need for a faster predecessor‑search method.

Introducing the skiplist

A skiplist is essentially a multi‑level linked list. The article presents diagrams and explains that each node may have several forward pointers (levels), allowing the algorithm to “skip” over large portions of the list.

Skiplist search algorithm

The search starts from the highest level and moves forward while the forward node’s value is less than the target, then drops one level. The relevant structs and loop are:

type Level struct {
    forward *node // pointer at this level
    span    int64 // distance covered at this level
}

type node struct {
    val   int64
    level []*Level // slice of levels for the node
}

var maxlevel = 5
var curNode *node = &node{val:9}
var dummy *node = &node{val:0}
var pre *node = dummy
for i := maxlevel-1; i >= 0; i-- {
    for pre.level[i].forward != nil && pre.level[i].forward.val < curNode.val {
        pre = pre.level[i].forward
    }
}

By traversing from the top level down, the algorithm locates the predecessor (e.g., node 5) with far fewer steps than a single‑level list.

Command implementation (ZADD)

The entry point for adding elements is the cmdZAdd function in engine/sortedset.go. It obtains or creates a SortedSet object, iterates over the supplied pair s, and calls sortedSet.Add(pair.Member, pair.Score):

func cmdZAdd(db *DB, args [][]byte) protocol.Reply {
    // ... omitted ...
    sortedSet, _, reply := db.getOrInitSortedSetObject(key)
    if reply != nil { return reply }
    i := int64(0)
    for _, pair := range pairs {
        if sortedSet.Add(pair.Member, pair.Score) {
            i++ // count of newly added members
        }
    }
    // ... omitted ...
}

SortedSet.Add logic

The method first checks the map for an existing member. If found and the score differs, the old entry is removed from the skiplist and the new one is inserted; if the score is unchanged, nothing is done. For a brand‑new member, the pair is stored in the map and inserted into the skiplist. The function returns true for a new insertion and false for an update.

func (s *SortedSet) Add(member string, score float64) bool {
    pair, ok := s.dict[member]
    s.dict[member] = &Pair{Member: member, Score: score}
    if ok {
        if score != pair.Score {
            s.skl.remove(pair.Member, pair.Score)
            s.skl.insert(member, score)
        }
        return false
    }
    s.skl.insert(member, score)
    return true
}

Insertion details – recording predecessors

Because a skiplist has multiple levels, inserting a node requires remembering the predecessor at each level (stored in beforeNode). The article shows a diagram of the predecessor chain for inserting node 3 and lists the predecessor for each level:

Level 4 predecessor: dummy

Level 3 predecessor: 1

Level 2 predecessor: 2

Level 1 predecessor: 2

Level 0 predecessor: 2

Full skiplist insertion code

func (s *skiplist) insert(member string, score float64) *node {
    beforeNode := make([]*node, defaultMaxLevel)      // predecessors per level
    beforeNodeOrder := make([]int64, defaultMaxLevel) // order numbers per level

    node := s.header
    for i := s.maxLevel - 1; i >= 0; i-- {
        if i == s.maxLevel-1 {
            beforeNodeOrder[i] = 0
        } else {
            beforeNodeOrder[i] = beforeNodeOrder[i+1]
        }
        for node.levels[i].forward != nil &&
            (node.levels[i].forward.Score < score ||
                (node.levels[i].forward.Score == score && node.levels[i].forward.Member < member)) {
            beforeNodeOrder[i] += int64(node.levels[i].span)
            node = node.levels[i].forward
        }
        beforeNode[i] = node
    }

    newLevel := randomLevel()
    if newLevel > s.maxLevel {
        for i := s.maxLevel; i < newLevel; i++ {
            beforeNode[i] = s.header
            beforeNodeOrder[i] = 0
            beforeNode[i].levels[i].forward = nil
            beforeNode[i].levels[i].span = s.length
        }
        s.maxLevel = newLevel
    }

    node = newNode(newLevel, member, score)
    for i := int16(0); i < newLevel; i++ {
        node.levels[i].forward = beforeNode[i].levels[i].forward
        beforeNode[i].levels[i].forward = node
        node.levels[i].span = beforeNode[i].levels[i].span - (beforeNodeOrder[0] - beforeNodeOrder[i])
        beforeNode[i].levels[i].span = beforeNodeOrder[0] - beforeNodeOrder[i] + 1
    }
    for i := newLevel; i < s.maxLevel; i++ {
        beforeNode[i].levels[i].span++
    }
    if beforeNode[0] == s.header {
        node.backward = nil
    } else {
        node.backward = beforeNode[0]
    }
    if beforeNode[0].levels[0].forward != nil {
        beforeNode[0].levels[0].forward.backward = node
    } else {
        s.tailer = node
    }
    s.length++
    return node
}

Edge‑case handling

If the new node’s height exceeds the current maximum, missing predecessor slots are filled with the header node and their spans are set to the current list length. If the new node is much shorter than the highest level, the span of the higher levels is incremented by one.

Effect demonstration

The article concludes with an image showing the resulting ordered set after a series of insertions.