当前位置：首页 > news >正文

Go语言Redis源码分析：数据结构实现

news 2026/5/28 11:19:25

Go语言Redis源码分析：数据结构实现

一、引言：Redis高性能的基石

Redis之所以能成为全球最流行的键值存储系统之一，其核心优势在于极致优化的数据结构设计。作为Go语言开发者，深入理解Redis的数据结构实现，不仅能帮助我们更好地使用Redis，更能学到很多高性能编程的精髓。

本文将从源码层面深入剖析Redis中几种核心数据结构的实现原理，包括跳表、字典、链表等，并探讨它们如何支撑Redis的高性能特性。

二、跳表（Skip List）：有序集合的核心

2.1 跳表数据结构定义

跳表是一种随机化的数据结构，通过在链表基础上增加多层索引，实现O(log n)复杂度的查找、插入和删除操作。在Redis中，跳表是有序集合（Sorted Set）的底层实现之一。

// 跳表节点结构体 type skiplistNode struct { level []*skiplistLevel // 节点在各层的指针 backward *skiplistNode // 后退指针，用于反向遍历 score float64 // 分值 obj *robj // 成员对象 } type skiplistLevel struct { forward *skiplistNode // 前进指针 span uint32 // 跨越的节点数，用于排名计算 } type skiplist struct { header *skiplistNode // 头节点 tail *skiplistNode // 尾节点 level int // 最大层数 length uint64 // 节点总数 }

2.2 跳表的插入过程

跳表的插入是其核心操作，关键在于随机层数的生成：

// 随机生成节点层数 func randomLevel() int { level := 1 // 0xFFFF = 65535，约1/4概率增加一层 for rand()&0xFFFF < PROBABILITY*0xFFFF { level++ } if level > MAX_LEVEL { level = MAX_LEVEL } return level } // 插入节点的核心逻辑 func zslInsert(zsl *skiplist, score float64, obj *robj) *skiplistNode { update := make([]*skiplistNode, MAX_LEVEL) rank := make([]uint64, MAX_LEVEL) // 从最高层开始查找插入位置 x := zsl.header for i := zsl.level - 1; i >= 0; i-- { if i == zsl.level-1 { rank[i] = 0 } else { rank[i] = rank[i+1] } // 在当前层向前遍历 for x.level[i].forward != nil && (x.level[i].forward.score < score || (x.level[i].forward.score == score && compareStringObjects(x.level[i].forward.obj, obj) < 0)) { rank[i] += x.level[i].span x = x.level[i].forward } update[i] = x } // 随机生成新节点层数 level := randomLevel() // 如果新节点层数超过当前跳表最大层数，更新跳表 if level > zsl.level { for i := zsl.level; i < level; i++ { rank[i] = 0 update[i] = zsl.header update[i].level[i].span = zsl.length } zsl.level = level } // 创建新节点 x = createSkiplistNode(level, score, obj) // 插入节点到各层 for i := 0; i < level; i++ { x.level[i].forward = update[i].level[i].forward update[i].level[i].forward = x // 更新span值 x.level[i].span = update[i].level[i].span - (rank[0] - rank[i]) update[i].level[i].span = (rank[0] - rank[i]) + 1 } // 更新未使用层的span for i := level; i < zsl.level; i++ { update[i].level[i].span++ } // 设置后退指针 if update[0] == zsl.header { x.backward = nil } else { x.backward = update[0] } if x.level[0].forward != nil { x.level[0].forward.backward = x } else { zsl.tail = x } zsl.length++ return x }

2.3 跳表的查找过程

// 查找指定分值和成员的节点 func zslSearch(zsl *skiplist, score float64, obj *robj) *skiplistNode { x := zsl.header for i := zsl.level - 1; i >= 0; i-- { // 在当前层向前遍历，找到小于目标score的最大节点 for x.level[i].forward != nil && (x.level[i].forward.score < score || (x.level[i].forward.score == score && compareStringObjects(x.level[i].forward.obj, obj) < 0)) { x = x.level[i].forward } // 如果找到完全匹配的节点，返回 if x.level[0].forward != nil && x.level[0].forward.score == score && compareStringObjects(x.level[0].forward.obj, obj) == 0 { return x.level[0].forward } } return nil }

三、字典（Dictionary）：哈希表实现

3.1 字典的数据结构

Redis的字典采用链式哈希表实现，解决哈希冲突问题：

// 哈希表节点 type dictEntry struct { key *robj // 键 val *robj // 值 next *dictEntry // 下一个节点，处理哈希冲突 } // 哈希表 type dictht struct { table []*dictEntry // 哈希表数组 size uint64 // 哈希表大小 sizemask uint64 // 掩码，用于计算索引 used uint64 // 已使用节点数 } // 字典 type dict struct { type *dictType // 类型特定函数 privdata interface{} // 私有数据 ht [2]dictht // 两张哈希表，用于渐进式rehash rehashidx int64 // rehash进度 iterators uint64 // 当前迭代器数量 }

3.2 渐进式Rehash机制

这是Redis的一大创新，避免了大规模数据迁移导致的性能抖动：

// 单步rehash func dictRehash(d *dict, n int) int { if !dictIsRehashing(d) { return 0 } for n > 0 && d.ht[0].used > 0 { var de, nextde *dictEntry // 找到一个非空槽位 for d.rehashidx < int64(d.ht[0].size) && d.ht[0].table[d.rehashidx] == nil { d.rehashidx++ } if d.rehashidx >= int64(d.ht[0].size) { // rehash完成 d.ht[0] = d.ht[1] _dictReset(&d.ht[1]) d.rehashidx = -1 return 0 } de = d.ht[0].table[d.rehashidx] // 将该槽位的所有节点迁移到ht[1] for de != nil { nextde = de.next // 计算新哈希值 h := dictHashKey(d, de.key) & d.ht[1].sizemask de.next = d.ht[1].table[h] d.ht[1].table[h] = de d.ht[0].used-- d.ht[1].used++ de = nextde n-- } d.ht[0].table[d.rehashidx] = nil d.rehashidx++ } return 1 }

四、链表（List）：双端链表实现

4.1 链表数据结构

// 链表节点 type listNode struct { prev *listNode // 前驱节点 next *listNode // 后继节点 value *robj // 节点值 } // 链表迭代器 type listIter struct { next *listNode // 下一个节点 direction int // 迭代方向：AL_START_HEAD或AL_START_TAIL } // 链表结构 type list struct { head *listNode // 头节点 tail *listNode // 尾节点 len uint64 // 节点数量 dup func(*robj) *robj // 复制函数 free func(*robj) // 释放函数 match func(*robj, *robj) int // 匹配函数 }

4.2 链表操作

// 创建新链表 func listCreate() *list { return &list{ head: nil, tail: nil, len: 0, dup: nil, free: nil, match: nil, } } // 在链表尾部添加节点 func listAddNodeTail(l *list, value *robj) *listNode { node := &listNode{ prev: nil, next: nil, value: value, } if l.len == 0 { l.head = node l.tail = node } else { node.prev = l.tail l.tail.next = node l.tail = node } l.len++ return node } // 删除节点 func listDelNode(l *list, node *listNode) { if node.prev != nil { node.prev.next = node.next } else { l.head = node.next } if node.next != nil { node.next.prev = node.prev } else { l.tail = node.prev } if l.free != nil && node.value != nil { l.free(node.value) } l.len-- }