Skip to main content

​
Chapter 3: Data Structures

Redis isn’t just a key-value store - it’s a data structure server. In this chapter, we’ll implement Lists, Sets, Hashes, and Sorted Sets, learning powerful data structures along the way.
Prerequisites: Chapter 2: TCP Server
Further Reading: DSA Patterns
Time: 4-5 hours
Outcome: Full support for Redis data types

​
Redis Data Structures Overview

┌─────────────────────────────────────────────────────────────────────────────┐
│                         REDIS DATA STRUCTURES                                │
├─────────────────────────────────────────────────────────────────────────────┤
│                                                                              │
│   STRING              LIST                SET                 HASH           │
│   ──────              ────                ───                 ────           │
│   "hello"             ┌───┐               ┌────────────┐      ┌──────────┐  │
│                       │ A │               │    Set     │      │ field1:  │  │
│   Simple              │ B │               │  {A,B,C}   │      │   val1   │  │
│   key-value           │ C │               │            │      │ field2:  │  │
│                       │ D │               │ Unique     │      │   val2   │  │
│                       └───┘               │ members    │      └──────────┘  │
│                       Doubly linked       └────────────┘      Hash table    │
│                                                                              │
│   SORTED SET (ZSET)                                                         │
│   ─────────────────                                                         │
│   ┌─────────────────────────────────────────────────────────┐              │
│   │  Score │ Member    ← Sorted by score                    │              │
│   │  ───── │ ──────                                         │              │
│   │   1.0  │  "alice"  ← Skip list for O(log n) operations │              │
│   │   2.5  │  "bob"                                         │              │
│   │   3.0  │  "carol"                                       │              │
│   └─────────────────────────────────────────────────────────┘              │
│                                                                              │
└─────────────────────────────────────────────────────────────────────────────┘

​
Part 1: Lists

Redis lists are implemented as doubly-linked lists for O(1) push/pop at both ends.

​
List Structure

internal/store/list.go
package store

import (
    "sync"
)

// ListNode represents a node in a doubly-linked list
type ListNode struct {
    Value []byte
    Prev  *ListNode
    Next  *ListNode
}

// List is a doubly-linked list with O(1) access to both ends
type List struct {
    head   *ListNode
    tail   *ListNode
    length int
    mu     sync.RWMutex
}

// NewList creates a new empty list
func NewList() *List {
    return &List{}
}

// Len returns the number of elements
func (l *List) Len() int {
    l.mu.RLock()
    defer l.mu.RUnlock()
    return l.length
}

// LPush adds elements to the head (left)
func (l *List) LPush(values ...[]byte) int {
    l.mu.Lock()
    defer l.mu.Unlock()
    
    for _, value := range values {
        node := &ListNode{Value: value}
        
        if l.head == nil {
            l.head = node
            l.tail = node
        } else {
            node.Next = l.head
            l.head.Prev = node
            l.head = node
        }
        l.length++
    }
    
    return l.length
}

// RPush adds elements to the tail (right)
func (l *List) RPush(values ...[]byte) int {
    l.mu.Lock()
    defer l.mu.Unlock()
    
    for _, value := range values {
        node := &ListNode{Value: value}
        
        if l.tail == nil {
            l.head = node
            l.tail = node
        } else {
            node.Prev = l.tail
            l.tail.Next = node
            l.tail = node
        }
        l.length++
    }
    
    return l.length
}

// LPop removes and returns the first element
func (l *List) LPop() ([]byte, bool) {
    l.mu.Lock()
    defer l.mu.Unlock()
    
    if l.head == nil {
        return nil, false
    }
    
    value := l.head.Value
    l.head = l.head.Next
    
    if l.head == nil {
        l.tail = nil
    } else {
        l.head.Prev = nil
    }
    
    l.length--
    return value, true
}

// RPop removes and returns the last element
func (l *List) RPop() ([]byte, bool) {
    l.mu.Lock()
    defer l.mu.Unlock()
    
    if l.tail == nil {
        return nil, false
    }
    
    value := l.tail.Value
    l.tail = l.tail.Prev
    
    if l.tail == nil {
        l.head = nil
    } else {
        l.tail.Next = nil
    }
    
    l.length--
    return value, true
}

// LRange returns elements from start to stop (inclusive)
func (l *List) LRange(start, stop int) [][]byte {
    l.mu.RLock()
    defer l.mu.RUnlock()
    
    // Handle negative indices
    if start < 0 {
        start = l.length + start
    }
    if stop < 0 {
        stop = l.length + stop
    }
    
    // Bounds checking
    if start < 0 {
        start = 0
    }
    if stop >= l.length {
        stop = l.length - 1
    }
    if start > stop || start >= l.length {
        return [][]byte{}
    }
    
    // Walk to start position
    current := l.head
    for i := 0; i < start; i++ {
        current = current.Next
    }
    
    // Collect elements
    result := make([][]byte, 0, stop-start+1)
    for i := start; i <= stop && current != nil; i++ {
        result = append(result, current.Value)
        current = current.Next
    }
    
    return result
}

// LIndex returns the element at index
func (l *List) LIndex(index int) ([]byte, bool) {
    l.mu.RLock()
    defer l.mu.RUnlock()
    
    // Handle negative indices
    if index < 0 {
        index = l.length + index
    }
    
    if index < 0 || index >= l.length {
        return nil, false
    }
    
    current := l.head
    for i := 0; i < index; i++ {
        current = current.Next
    }
    
    return current.Value, true
}

​
Part 2: Sets

Sets use a hash map for O(1) membership tests and operations.
internal/store/set.go
package store

import (
    "sync"
)

// Set is an unordered collection of unique strings
type Set struct {
    members map[string]struct{}
    mu      sync.RWMutex
}

// NewSet creates a new empty set
func NewSet() *Set {
    return &Set{
        members: make(map[string]struct{}),
    }
}

// Add adds members to the set, returns count of new members added
func (s *Set) Add(members ...string) int {
    s.mu.Lock()
    defer s.mu.Unlock()
    
    added := 0
    for _, member := range members {
        if _, exists := s.members[member]; !exists {
            s.members[member] = struct{}{}
            added++
        }
    }
    return added
}

// Remove removes members from the set
func (s *Set) Remove(members ...string) int {
    s.mu.Lock()
    defer s.mu.Unlock()
    
    removed := 0
    for _, member := range members {
        if _, exists := s.members[member]; exists {
            delete(s.members, member)
            removed++
        }
    }
    return removed
}

// IsMember checks if a member exists
func (s *Set) IsMember(member string) bool {
    s.mu.RLock()
    defer s.mu.RUnlock()
    
    _, exists := s.members[member]
    return exists
}

// Members returns all members
func (s *Set) Members() []string {
    s.mu.RLock()
    defer s.mu.RUnlock()
    
    result := make([]string, 0, len(s.members))
    for member := range s.members {
        result = append(result, member)
    }
    return result
}

// Card returns the cardinality (size)
func (s *Set) Card() int {
    s.mu.RLock()
    defer s.mu.RUnlock()
    return len(s.members)
}

// Intersect returns the intersection with another set
func (s *Set) Intersect(other *Set) *Set {
    s.mu.RLock()
    other.mu.RLock()
    defer s.mu.RUnlock()
    defer other.mu.RUnlock()
    
    result := NewSet()
    
    // Iterate over smaller set for efficiency
    smaller, larger := s.members, other.members
    if len(s.members) > len(other.members) {
        smaller, larger = larger, smaller
    }
    
    for member := range smaller {
        if _, exists := larger[member]; exists {
            result.members[member] = struct{}{}
        }
    }
    
    return result
}

// Union returns the union with another set
func (s *Set) Union(other *Set) *Set {
    s.mu.RLock()
    other.mu.RLock()
    defer s.mu.RUnlock()
    defer other.mu.RUnlock()
    
    result := NewSet()
    
    for member := range s.members {
        result.members[member] = struct{}{}
    }
    for member := range other.members {
        result.members[member] = struct{}{}
    }
    
    return result
}

// Diff returns members in s but not in other
func (s *Set) Diff(other *Set) *Set {
    s.mu.RLock()
    other.mu.RLock()
    defer s.mu.RUnlock()
    defer other.mu.RUnlock()
    
    result := NewSet()
    
    for member := range s.members {
        if _, exists := other.members[member]; !exists {
            result.members[member] = struct{}{}
        }
    }
    
    return result
}

​
Part 3: Hashes

Hashes are maps of field-value pairs within a key.
internal/store/hash.go
package store

import (
    "sync"
)

// Hash is a map of field-value pairs
type Hash struct {
    fields map[string][]byte
    mu     sync.RWMutex
}

// NewHash creates a new empty hash
func NewHash() *Hash {
    return &Hash{
        fields: make(map[string][]byte),
    }
}

// Set sets field to value, returns 1 if new field, 0 if updated
func (h *Hash) Set(field string, value []byte) int {
    h.mu.Lock()
    defer h.mu.Unlock()
    
    isNew := 0
    if _, exists := h.fields[field]; !exists {
        isNew = 1
    }
    h.fields[field] = value
    return isNew
}

// Get returns the value of a field
func (h *Hash) Get(field string) ([]byte, bool) {
    h.mu.RLock()
    defer h.mu.RUnlock()
    
    value, exists := h.fields[field]
    return value, exists
}

// MSet sets multiple fields
func (h *Hash) MSet(pairs map[string][]byte) {
    h.mu.Lock()
    defer h.mu.Unlock()
    
    for field, value := range pairs {
        h.fields[field] = value
    }
}

// MGet returns values for multiple fields
func (h *Hash) MGet(fields ...string) [][]byte {
    h.mu.RLock()
    defer h.mu.RUnlock()
    
    result := make([][]byte, len(fields))
    for i, field := range fields {
        result[i] = h.fields[field] // nil if not exists
    }
    return result
}

// Del deletes fields
func (h *Hash) Del(fields ...string) int {
    h.mu.Lock()
    defer h.mu.Unlock()
    
    deleted := 0
    for _, field := range fields {
        if _, exists := h.fields[field]; exists {
            delete(h.fields, field)
            deleted++
        }
    }
    return deleted
}

// Exists checks if a field exists
func (h *Hash) Exists(field string) bool {
    h.mu.RLock()
    defer h.mu.RUnlock()
    
    _, exists := h.fields[field]
    return exists
}

// Len returns the number of fields
func (h *Hash) Len() int {
    h.mu.RLock()
    defer h.mu.RUnlock()
    return len(h.fields)
}

// Keys returns all field names
func (h *Hash) Keys() []string {
    h.mu.RLock()
    defer h.mu.RUnlock()
    
    keys := make([]string, 0, len(h.fields))
    for k := range h.fields {
        keys = append(keys, k)
    }
    return keys
}

// Values returns all values
func (h *Hash) Values() [][]byte {
    h.mu.RLock()
    defer h.mu.RUnlock()
    
    values := make([][]byte, 0, len(h.fields))
    for _, v := range h.fields {
        values = append(values, v)
    }
    return values
}

// GetAll returns all fields and values
func (h *Hash) GetAll() map[string][]byte {
    h.mu.RLock()
    defer h.mu.RUnlock()
    
    result := make(map[string][]byte, len(h.fields))
    for k, v := range h.fields {
        result[k] = v
    }
    return result
}

​
Part 4: Sorted Sets with Skip Lists

Sorted Sets are the most complex data structure - they maintain elements sorted by score while allowing O(log n) operations.

​
What is a Skip List?

┌─────────────────────────────────────────────────────────────────────────────┐
│                            SKIP LIST STRUCTURE                               │
├─────────────────────────────────────────────────────────────────────────────┤
│                                                                              │
│   Level 3: HEAD ─────────────────────────────────────────────────► NIL      │
│                                                                              │
│   Level 2: HEAD ──────────────────► 15 ──────────────────────────► NIL      │
│                                                                              │
│   Level 1: HEAD ────────► 7 ──────► 15 ──────► 22 ────────────────► NIL     │
│                                                                              │
│   Level 0: HEAD ► 3 ► 7 ► 11 ► 15 ► 18 ► 22 ► 26 ► 30 ► NIL                │
│                                                                              │
│   SEARCH for 18:                                                            │
│   1. Start at HEAD, Level 3                                                 │
│   2. Level 3: Go right → hit NIL, go down                                   │
│   3. Level 2: Go right → 15 < 18, go right → NIL, go down                  │
│   4. Level 1: At 15, go right → 22 > 18, go down                           │
│   5. Level 0: At 15, go right → 18 = target, FOUND!                        │
│                                                                              │
│   Average O(log n) because each level skips ~half the elements             │
│                                                                              │
└─────────────────────────────────────────────────────────────────────────────┘

​
Skip List Implementation

internal/store/skiplist.go
package store

import (
    "math/rand"
    "sync"
)

const (
    maxLevel    = 32   // Maximum levels
    probability = 0.25 // P = 1/4
)

// SkipListNode represents a node in the skip list
type SkipListNode struct {
    Member  string
    Score   float64
    forward []*SkipListNode // Forward pointers for each level
    span    []int           // Span for each level (used for rank)
}

// SkipList is a probabilistic data structure for sorted data
type SkipList struct {
    head   *SkipListNode
    tail   *SkipListNode
    length int
    level  int
    mu     sync.RWMutex
}

// NewSkipList creates a new skip list
func NewSkipList() *SkipList {
    return &SkipList{
        head:  &SkipListNode{forward: make([]*SkipListNode, maxLevel)},
        level: 1,
    }
}

// randomLevel generates a random level for a new node
func randomLevel() int {
    level := 1
    for rand.Float64() < probability && level < maxLevel {
        level++
    }
    return level
}

// Insert adds a member with score, returns true if new
func (sl *SkipList) Insert(member string, score float64) bool {
    sl.mu.Lock()
    defer sl.mu.Unlock()
    
    // Track update points and rank at each level
    update := make([]*SkipListNode, maxLevel)
    rank := make([]int, maxLevel)
    
    x := sl.head
    for i := sl.level - 1; i >= 0; i-- {
        if i < sl.level-1 {
            rank[i] = rank[i+1]
        }
        
        for x.forward[i] != nil &&
            (x.forward[i].Score < score ||
                (x.forward[i].Score == score && x.forward[i].Member < member)) {
            rank[i] += x.span[i]
            x = x.forward[i]
        }
        update[i] = x
    }
    
    // Check if member already exists
    if x.forward[0] != nil && x.forward[0].Member == member {
        // Update score
        x.forward[0].Score = score
        return false
    }
    
    // Create new node
    level := randomLevel()
    if level > sl.level {
        for i := sl.level; i < level; i++ {
            rank[i] = 0
            update[i] = sl.head
            update[i].span = append(update[i].span, sl.length)
        }
        sl.level = level
    }
    
    newNode := &SkipListNode{
        Member:  member,
        Score:   score,
        forward: make([]*SkipListNode, level),
        span:    make([]int, level),
    }
    
    for i := 0; i < level; i++ {
        newNode.forward[i] = update[i].forward[i]
        update[i].forward[i] = newNode
        
        // Update spans
        newNode.span[i] = update[i].span[i] - (rank[0] - rank[i])
        update[i].span[i] = (rank[0] - rank[i]) + 1
    }
    
    // Update spans for levels not affected
    for i := level; i < sl.level; i++ {
        update[i].span[i]++
    }
    
    // Update tail
    if newNode.forward[0] == nil {
        sl.tail = newNode
    }
    
    sl.length++
    return true
}

// Delete removes a member
func (sl *SkipList) Delete(member string) bool {
    sl.mu.Lock()
    defer sl.mu.Unlock()
    
    update := make([]*SkipListNode, maxLevel)
    x := sl.head
    
    for i := sl.level - 1; i >= 0; i-- {
        for x.forward[i] != nil && x.forward[i].Member < member {
            x = x.forward[i]
        }
        update[i] = x
    }
    
    x = x.forward[0]
    if x == nil || x.Member != member {
        return false
    }
    
    for i := 0; i < sl.level; i++ {
        if update[i].forward[i] == x {
            update[i].span[i] += x.span[i] - 1
            update[i].forward[i] = x.forward[i]
        } else {
            update[i].span[i]--
        }
    }
    
    if x == sl.tail {
        if x.forward[0] != nil {
            sl.tail = x.forward[0]
        } else {
            sl.tail = nil
        }
    }
    
    // Reduce level if needed
    for sl.level > 1 && sl.head.forward[sl.level-1] == nil {
        sl.level--
    }
    
    sl.length--
    return true
}

// GetScore returns the score of a member
func (sl *SkipList) GetScore(member string) (float64, bool) {
    sl.mu.RLock()
    defer sl.mu.RUnlock()
    
    x := sl.head
    for i := sl.level - 1; i >= 0; i-- {
        for x.forward[i] != nil && x.forward[i].Member < member {
            x = x.forward[i]
        }
    }
    
    x = x.forward[0]
    if x != nil && x.Member == member {
        return x.Score, true
    }
    return 0, false
}

// Range returns members with scores in [min, max]
func (sl *SkipList) RangeByScore(min, max float64) []struct{ Member string; Score float64 } {
    sl.mu.RLock()
    defer sl.mu.RUnlock()
    
    var result []struct{ Member string; Score float64 }
    
    // Find first node >= min
    x := sl.head
    for i := sl.level - 1; i >= 0; i-- {
        for x.forward[i] != nil && x.forward[i].Score < min {
            x = x.forward[i]
        }
    }
    
    // Traverse and collect
    x = x.forward[0]
    for x != nil && x.Score <= max {
        result = append(result, struct{ Member string; Score float64 }{x.Member, x.Score})
        x = x.forward[0]
    }
    
    return result
}

// RangeByRank returns members by rank (0-indexed)
func (sl *SkipList) RangeByRank(start, stop int) []struct{ Member string; Score float64 } {
    sl.mu.RLock()
    defer sl.mu.RUnlock()
    
    // Handle negative indices
    if start < 0 {
        start = sl.length + start
    }
    if stop < 0 {
        stop = sl.length + stop
    }
    if start < 0 {
        start = 0
    }
    if stop >= sl.length {
        stop = sl.length - 1
    }
    
    if start > stop {
        return nil
    }
    
    var result []struct{ Member string; Score float64 }
    
    // Find node at rank 'start'
    x := sl.head
    rank := -1
    
    for i := sl.level - 1; i >= 0; i-- {
        for x.forward[i] != nil && rank+x.span[i] < start {
            rank += x.span[i]
            x = x.forward[i]
        }
    }
    
    x = x.forward[0]
    rank++
    
    // Collect elements
    for x != nil && rank <= stop {
        result = append(result, struct{ Member string; Score float64 }{x.Member, x.Score})
        x = x.forward[0]
        rank++
    }
    
    return result
}

// Len returns the number of elements
func (sl *SkipList) Len() int {
    sl.mu.RLock()
    defer sl.mu.RUnlock()
    return sl.length
}

​
Sorted Set Wrapper

internal/store/zset.go
package store

// ZSet combines a skip list with a hash map for O(1) score lookups
type ZSet struct {
    skiplist *SkipList
    dict     map[string]float64 // member -> score for O(1) lookup
}

// NewZSet creates a new sorted set
func NewZSet() *ZSet {
    return &ZSet{
        skiplist: NewSkipList(),
        dict:     make(map[string]float64),
    }
}

// Add adds members with scores
func (z *ZSet) Add(members ...struct{ Member string; Score float64 }) int {
    added := 0
    for _, m := range members {
        if _, exists := z.dict[m.Member]; !exists {
            added++
        }
        z.dict[m.Member] = m.Score
        z.skiplist.Insert(m.Member, m.Score)
    }
    return added
}

// Score returns the score of a member
func (z *ZSet) Score(member string) (float64, bool) {
    score, exists := z.dict[member]
    return score, exists
}

// Remove removes members
func (z *ZSet) Remove(members ...string) int {
    removed := 0
    for _, member := range members {
        if _, exists := z.dict[member]; exists {
            delete(z.dict, member)
            z.skiplist.Delete(member)
            removed++
        }
    }
    return removed
}

// Range returns members by rank
func (z *ZSet) Range(start, stop int, withScores bool) []struct{ Member string; Score float64 } {
    return z.skiplist.RangeByRank(start, stop)
}

// RangeByScore returns members in score range
func (z *ZSet) RangeByScore(min, max float64) []struct{ Member string; Score float64 } {
    return z.skiplist.RangeByScore(min, max)
}

// Card returns the cardinality
func (z *ZSet) Card() int {
    return z.skiplist.Len()
}

​
Exercises

Add insertion before/after a pivot:
// LINSERT key BEFORE|AFTER pivot value
// Find the pivot and insert before/after it
Implement set operations as commands:
// SUNION key [key ...]
// SINTER key [key ...]
// SDIFF key [key ...]
Get the rank of a member in a sorted set:
// ZRANK key member
// Return 0-based rank (position) of member
// Hint: Track rank while traversing skip list

​
Key Takeaways

Linked Lists

O(1) push/pop at ends, O(n) access by index

Hash Sets

O(1) membership test using hash maps

Skip Lists

Probabilistic O(log n) sorted structure

Composite Structures

ZSet combines skip list + hash map for best of both

​
Further Reading

Hash Maps

Deep dive into hash table implementations

Linked Lists

Understanding linked list patterns

​
What’s Next?

In Chapter 4: Persistence, we’ll implement:
  • RDB snapshots (point-in-time backups)
  • AOF logging (append-only file)
  • Crash recovery

Next: Persistence

Learn how Redis survives restarts