Redis 底层数据结构原理：SDS、跳表、哈希表、压缩列表与 intset

摘要Redis 之所以快且省内存关键在于它在 C 语言之上自造了一套「编码encoding」抽象同一个对外类型string / hash / set / zset会按数据规模自动选用最省或最快的底层结构。本文从 C 原生字符串与哈希表的痛点切入逐层拆解 SDS、哈希表 dict、压缩列表 listpack、intset 与跳表 skiplist 的设计动机并给出OBJECT ENCODING真实观测与 Python 最小实现两条可运行示例帮你从「会用 Redis」升级到「懂 Redis 底层数据结构」。导语很多同学能熟练敲出SET、HSET、ZADD但被面试追问一句「Redis 的字符串为什么不是 C 的原生char*」「zset 为什么用跳表而不是红黑树」就卡壳。问题不在命令用得不熟而在于我们只看到了 Redis 的「对外类型」没看到它背后真正干活的「底层编码」。这篇文章就把这层窗户纸捅破。如果你还想从「网络模型 数据结构」整体视角再串一遍可以配合阅读这篇拆解Redis 为什么快从网络模型到数据结构层层拆解。引言为什么「会用 Redis」不等于「懂 Redis」C 语言的原生字符串是「以\0结尾的char*」它有两个硬伤取长度必须从头扫到尾时间复杂度O(N)且遇到中间的\0会被截断无法安全存储图片、序列化对象等二进制数据。C 的原生哈希表在「大量小对象」场景下也不划算每个键值对都要额外分配指针和元数据内存碎片多、缓存命中差。Redis 的解法是在 C 之上自造一套「编码抽象」——对外只暴露 5 种类型对内则按数据规模自动挑选最省内存或最快的底层结构。这也是为什么同一个hash元素少时占用极小、元素一多就「悄悄变胖」。C 原生字符串 Redis 自造 SDS strlen O(N) ──▶ len 字段 O(1) 二进制不安全 ──▶ 以 len 判定边界二进制安全 扩容易溢出 ──▶ 预分配 惰性释放杜绝溢出本文有两条贯穿全程的可运行主线一条用redis-cli实地观测编码变化一条用 Python 手撕最小实现来印证原理。一切的起点robj 与编码encoding机制Redis 里每个值都是一个redisObject常称robj。它最重要的两个字段是type和encodingtype是「对外类型」string / list / hash / set / zsetencoding是「底层编码」两者完全解耦。这就解释了为什么「同一个类型有多种实现」string可以是int/embstr/rawhash可以是listpack/hashtablezset可以是listpack/skiplist。# 直接查看某个 key 当前使用的底层编码——这是全文观测的主工具 OBJECT ENCODING user:1 # 可能输出listpack / hashtable / ziplist老版本等encoding的切换遵循一条铁律为省内存的特殊编码一旦被「撑破阈值」就会升级为通用结构且通常不可逆。比如一个embstr字符串被APPEND后必然变成raw即使后续内容缩短也不会退回embstr。常见编码输出速查int、embstr、raw字符串、listpack/ziplist小规模 hash/zset/list、hashtable、skiplist、intset、quicklist。SDSRedis 为什么不用 C 原生字符串SDSSimple Dynamic String简单动态字符串是 Redis 自己实现的字符串结构。它的头部记录了len已用长度、alloc总分配量和buf[]实际字节因此STRLEN这类操作直接读len就是O(1)。struct sdshdr { uint8_t len; // 已用长度O(1) 取长度 uint8_t alloc; // 已分配容量不含头与结尾 \0 char buf[]; // 实际字节二进制安全 };SDS 的「二进制安全」体现在它以len判定边界而不是遇到\0就停所以可以存任意字节。同时 API 在修改前会先检查剩余空间不够才扩容从根本上杜绝缓冲区溢出。为减少内存重分配SDS 用了两个技巧空间预分配append 后按需多分配甚至翻倍和惰性空间释放缩短时不立即归还留作free备用。字符串的三种编码是这样分工的SET n 10086 OBJECT ENCODING n # → int可解析为 long 的整数最省 SET s hello OBJECT ENCODING s # → embstr≤44 字节与 robj 同块一次 malloc SET big $(python3 -c print(x*100)) OBJECT ENCODING big # → raw44 字节独立分配那「44 字节」从哪来这是OBJ_ENCODING_EMBSTR_SIZE_LIMIT 44当字符串很短时Redis 把robj头和sds头在同一块内存里一次性分配省一次malloc超过这个上限就拆成两块变成raw。结构头本身还用uint8/uint16/uint32/uint64等变长类型进一步省内存。哈希表 dictRedis 的「地基」dict是 Redis 的通用地基整个 keyspace、hash/set 的hashtable编码、zset 里member → score的查找底层都依赖它。理解了 dict才理解为什么HGET/HSET平均是O(1)。dict 用链式哈希解决冲突并维护两张表ht[0]和ht[1]来支持渐进式 rehash扩容不是一次性搬迁几十 GB 数据那会卡死服务而是用rehashidx指针逐步迁移期间读写会同时查两张表。dict ├─ ht[0] (正在使用的哈希表) └─ ht[1] (扩容/缩容时的过渡表) rehashidx: 已迁移到第几个桶逐步推进当负载因子used / size超过阈值时触发扩容迁移过程中每个命令顺手搬运一小批后台定时任务也会兜底。代价是一个 big hash 一旦触发 rehash会有持续的内存与 CPU 开销这正是 bigkey 要警惕的原因。压缩列表 ziplist 与 listpack小块数据的极致省内存ziplist压缩列表是一段连续内存开头是zlbytes/zltail/zllen后面是一串紧凑的entry。每个 entry 由prevlen前一项长度、encoding数据类型/长度和entry-data组成完全没有指针开销。[zlbytes][zltail][zllen][entry][entry]...[entry][zlend] entry [prevlen][encoding][entry-data]省内存的代价是在中间插入/修改时若前一项长度从 1 字节变成 5 字节会引发向后连锁更新cascade update最坏O(N)。listpackRedis ≥7.2 起逐步取代 ziplist去掉了对「前一项长度」的向前依赖从根本上消除了连锁更新。两者触发升级的阈值一致以下为 Redis 7.4 的默认值类型阈值参数默认超限后编码hashhash-max-listpack-entries / value512 / 64hashtablezsetzset-max-listpack-entries / value128 / 64skiplistsetset-max-intset-entries512hashtable注意这些默认值随版本略有差异生产环境请以你所用版本的redis.conf为准。intset纯整数集合的极致压缩intset整数集合用于「元素全是整数且数量较小」的set。它把整数按int16/int32/int64紧凑升序存进一个数组查找用二分O(logN)且没有任何指针开销。intset [encoding][length][contents...] (紧凑升序整数数组)当插入一个更大范围的整数时整个集合会升级编码如 16 位升到 32 位所有元素一次性按新宽度重排。升级是单向的——一旦升上去就不会降级。SADD nums 1 2 3 OBJECT ENCODING nums # → intset全整数且小 SADD nums hello # 加入非整数 OBJECT ENCODING nums # → hashtable整体升级一旦元素不再是「全整数」或超出set-max-intset-entries默认 512整个 set 就升级为hashtable。跳表 skiplist有序集合的另一半zset底层是双结构dict负责member → score的O(1)查找跳表负责按score有序、支持O(logN)的范围与排名查询。两者共享同一份member/score数据不重复存储。跳表本质是一个「多层有序链表」最底层是完整数据越往上索引越稀疏插入节点时按概率幂次P0.5决定层数查找时从最高层往下「跳」平均复杂度O(logN)。L3: head ───────────────▶ node(95) L2: head ─────▶ node(85) ──▶ node(95) L1: head ─▶ node(78) ─▶ node(85) ─▶ node(95) (底层全量有序范围查询顺着它一路向右)为什么不用红黑树跳表的范围遍历更简单找到起点顺着底层走即可对应ZRANGEBYSCORE实现更短、缓存更友好平均性能足够。当 zset 元素少且值小时用listpack超限则用dict skiplist。编码何时转换一张速查表把五大类型的编码与触发条件汇总成一张表方便对照上文的OBJECT ENCODING实测对外类型小数据编码升级条件大数据编码stringint整数 / embstr≤44B超长或 appendrawhashlistpack / ziplist元素数或值超阈值hashtablelistlistpackquicklist 节点元素变多quicklistsetintset全整数且小含非整数或超阈值hashtablezsetlistpack / ziplist元素数或值超阈值skiplist(dict)关键提醒这些转换几乎都是单向升级。升级后即使把数据再缩回小体量编码也不会退化回去——这是排查「内存降不下来」时容易踩的坑。实战观测①redis-cli OBJECT ENCODING 可运行示例下面这段脚本可以直接复制进redis-cli执行观察编码随数据规模的变化# 字符串三态 SET n 10086 OBJECT ENCODING n # → int SET s hello OBJECT ENCODING s # → embstr SET big $(python3 -c print(x*100)) OBJECT ENCODING big # → raw APPEND s world, redis! OBJECT ENCODING s # → rawembstr 不可变append 后升级 # hash小数据 listpack超限升级 hashtable HSET user:1 name tom age 18 OBJECT ENCODING user:1 # → listpackRedis ≥7老版本为 ziplist # zset小数据 listpack超限升级 skiplist ZADD rank 100 a 200 b 300 c OBJECT ENCODING rank # → listpack等价的 redis-py 脚本适合写进测试或巡检脚本import redis r redis.Redis(host127.0.0.1, port6379, db0, decode_responsesTrue) def show(label, key): print(f{label:12s} encoding{r.object(encoding, key)}) r.set(n, 10086) show(string-int, n) # int r.set(s, hello) show(string-emb, s) # embstr r.set(big, x * 100) show(string-raw, big) # raw r.hset(user:1, mapping{name: tom, age: 18}) show(hash-small, user:1) # listpack / ziplist r.zadd(rank, {a: 100, b: 200, c: 300}) show(zset-small, rank) # listpack / ziplist跑完你会看到同样的SET、HSET、ZADD因为数据特征不同底层编码天差地别——这正是「编码抽象」存在的意义。手撕实现②Python 最小 SDS 与跳表下面两个 Python 实现是教学简化版只为印证设计动机并非与 Redis 源码逐字节一致请勿用于生产。最小 SDS模拟len/free头部、O(1) 取长度、append 预分配、惰性释放class SDS: 最小 SDS 模拟header 记录长度与空闲buf 存字节。 def __init__(self, s): self.buf bytearray(s.encode(utf-8)) if isinstance(s, str) else bytearray(s) self.len len(self.buf) self.free 0 # 当前空闲字节 def length(self): O(1) 取长度对应 SDS 的 len 字段而非 C 的 strlen O(N)。 return self.len def append(self, s): add bytearray(s.encode(utf-8)) if isinstance(s, str) else bytearray(s) need self.len len(add) if self.free len(add): self.buf[self.len:self.len len(add)] add else: # 空间不足按需扩容并做 2 倍预分配示意 new_cap max(need, (self.len self.free) * 2) new_buf bytearray(new_cap) new_buf[:self.len] self.buf[:self.len] new_buf[self.len:need] add self.buf new_buf self.free new_cap - need self.len need return self def __str__(self): return self.buf[:self.len].decode(utf-8, replace) s SDS(hi) print(s.length(), s) # 2 hi s.append( redis) # 触发预分配 print(s.length(), s) # 8 hi redis最小跳表实现随机层数、insert、search、按 score 区间查询直观展示「多层索引」如何把范围查询降到O(logN)import random class SkipListNode: def __init__(self, score, member, level): self.score score self.member member self.forward [None] * level class SkipList: MAX_LEVEL 16 P 0.5 def __init__(self): self.level 1 self.head SkipListNode(None, None, self.MAX_LEVEL) self.length 0 def _random_level(self): lvl 1 while random.random() self.P and lvl self.MAX_LEVEL: lvl 1 return lvl def insert(self, score, member): update [None] * self.MAX_LEVEL x self.head for i in range(self.level - 1, -1, -1): while x.forward[i] and (x.forward[i].score score or (x.forward[i].score score and x.forward[i].member member)): x x.forward[i] update[i] x x x.forward[0] if x and x.score score and x.member member: return # member 唯一已存在则跳过 lvl self._random_level() if lvl self.level: for i in range(self.level, lvl): update[i] self.head self.level lvl node SkipListNode(score, member, lvl) for i in range(lvl): node.forward[i] update[i].forward[i] update[i].forward[i] node self.length 1 def search(self, member): x self.head.forward[0] while x: if x.member member: return x.score x x.forward[0] return None def zrange_by_score(self, lo, hi): 对应 ZRANGEBYSCORE 的范围查询。 out, x [], self.head.forward[0] while x: if lo x.score hi: out.append((x.member, x.score)) elif x.score hi: break x x.forward[0] return out if __name__ __main__: sl SkipList() for score, member in [(85, alice), (92, bob), (78, carol), (95, dave)]: sl.insert(score, member) print(bobs score:, sl.search(bob)) # 92 print(range 80-95:, sl.zrange_by_score(80, 95)) # [(alice,85),(bob,92),(dave,95)]把它和前文对照insert里的_random_level就是跳表层数的概率来源zrange_by_score从底层链表顺序遍历正是 Redis 做范围查询的思路。总结从编码视角看 Redis 为什么快、省内存快来自三处 O(1)/O(logN) 的设计SDS 用len字段让长度获取变 O(1)dict 让键查找平均 O(1)跳表用多层索引把有序集合的范围查询压到 O(logN)。省内存来自「按规模自适应」小数据走listpack/ziplist/intset这类紧凑编码几乎零指针开销、缓存局部性好一旦数据变大就自动升级为hashtable/skiplist保性能。这种「小用紧凑、大用通用」的切换是 Redis 内存优化的统一动机。实践上有两点值得记住第一合理控制 hash / zset 的元素规模别让单个 key 变成 bigkey否则编码升级与 rehash 会带来明显的内存与延迟代价第二排查内存异常时先OBJECT ENCODING看一眼底层编码往往能直接定位问题。想深入源码建议按这条路径读sds.c字符串、dict.c哈希表、t_zset.c跳表、t_hash.c压缩列表/哈希表切换。参考资料Redis 官方文档SDS 内部实现 https://redis.io/docs/latest/operate/oss_and_stack/reference/internals/internals-sds/Redis 官方文档内存优化 https://redis.io/docs/management/optimization/memory-optimization/© 2026 | 转载请注明出处结论PASS