Implement Redis data structures - Lists, Sets, Hashes, and Sorted Sets with skip lists
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.This distinction is what makes Redis special. A plain key-value store is like a filing cabinet where every drawer holds a single sheet of paper. Redis is a filing cabinet where drawers can hold sorted binders, index cards, or entire sub-cabinets. By pushing data structure logic into the server, Redis eliminates the “read-modify-write” round trip that plagues naive caching patterns. Instead of fetching a list, appending to it in your application, and writing it back (three network calls, plus a race condition), you send a single RPUSH command and the server handles it atomically.
┌─────────────────────────────────────────────────────────────────────────────┐│ 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. Why not an array? Because arrays have O(n) insertion at the head (every element must shift). For a message queue or activity feed where you constantly push to one end and pop from the other, a doubly-linked list is the right tool. The trade-off is that random access by index (LINDEX) becomes O(n) — you have to walk from the head or tail. Real Redis optimizes this further with a “quicklist” (a linked list of small arrays), but the pure linked list is the right starting point for understanding the design.
List Structure
internal/store/list.go
package storeimport ( "sync")// ListNode represents a node in a doubly-linked listtype ListNode struct { Value []byte Prev *ListNode Next *ListNode}// List is a doubly-linked list with O(1) access to both endstype List struct { head *ListNode tail *ListNode length int mu sync.RWMutex}// NewList creates a new empty listfunc NewList() *List { return &List{}}// Len returns the number of elementsfunc (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 elementfunc (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 elementfunc (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 indexfunc (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 storeimport ( "sync")// Set is an unordered collection of unique stringstype Set struct { members map[string]struct{} mu sync.RWMutex}// NewSet creates a new empty setfunc NewSet() *Set { return &Set{ members: make(map[string]struct{}), }}// Add adds members to the set, returns count of new members addedfunc (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 setfunc (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 existsfunc (s *Set) IsMember(member string) bool { s.mu.RLock() defer s.mu.RUnlock() _, exists := s.members[member] return exists}// Members returns all membersfunc (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 setfunc (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 setfunc (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 otherfunc (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 storeimport ( "sync")// Hash is a map of field-value pairstype Hash struct { fields map[string][]byte mu sync.RWMutex}// NewHash creates a new empty hashfunc NewHash() *Hash { return &Hash{ fields: make(map[string][]byte), }}// Set sets field to value, returns 1 if new field, 0 if updatedfunc (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 fieldfunc (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 fieldsfunc (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 fieldsfunc (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 fieldsfunc (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 existsfunc (h *Hash) Exists(field string) bool { h.mu.RLock() defer h.mu.RUnlock() _, exists := h.fields[field] return exists}// Len returns the number of fieldsfunc (h *Hash) Len() int { h.mu.RLock() defer h.mu.RUnlock() return len(h.fields)}// Keys returns all field namesfunc (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 valuesfunc (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 valuesfunc (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 storeimport ( "math/rand" "sync")const ( maxLevel = 32 // Maximum levels probability = 0.25 // P = 1/4)// SkipListNode represents a node in the skip listtype 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 datatype SkipList struct { head *SkipListNode tail *SkipListNode length int level int mu sync.RWMutex}// NewSkipList creates a new skip listfunc NewSkipList() *SkipList { return &SkipList{ head: &SkipListNode{forward: make([]*SkipListNode, maxLevel)}, level: 1, }}// randomLevel generates a random level for a new nodefunc randomLevel() int { level := 1 for rand.Float64() < probability && level < maxLevel { level++ } return level}// Insert adds a member with score, returns true if newfunc (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 memberfunc (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 memberfunc (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 elementsfunc (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 lookupstype ZSet struct { skiplist *SkipList dict map[string]float64 // member -> score for O(1) lookup}// NewZSet creates a new sorted setfunc NewZSet() *ZSet { return &ZSet{ skiplist: NewSkipList(), dict: make(map[string]float64), }}// Add adds members with scoresfunc (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 memberfunc (z *ZSet) Score(member string) (float64, bool) { score, exists := z.dict[member] return score, exists}// Remove removes membersfunc (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 rankfunc (z *ZSet) Range(start, stop int, withScores bool) []struct{ Member string; Score float64 } { return z.skiplist.RangeByRank(start, stop)}// RangeByScore returns members in score rangefunc (z *ZSet) RangeByScore(min, max float64) []struct{ Member string; Score float64 } { return z.skiplist.RangeByScore(min, max)}// Card returns the cardinalityfunc (z *ZSet) Card() int { return z.skiplist.Len()}
Exercises
Exercise 1: Implement LINSERT
Add insertion before/after a pivot:
// LINSERT key BEFORE|AFTER pivot value// Find the pivot and insert before/after it