Redis 源码分析压缩列表(ziplist)

本文涉及的产品
云数据库 Tair(兼容Redis),内存型 2GB
Redis 开源版,标准版 2GB
推荐场景:
搭建游戏排行榜
简介: 压缩列表是由一系列特殊编码的连续内存块组成的顺序整数结构,一个压缩列表可以包含任意多个节点,每个节点可以保存一个字节数组或者一个整数。适合存储小对象和长度有限的数据。

压缩列表是由一系列特殊编码的连续内存块组成的顺序整数结构,一个压缩列表可以包含任意多个节点,每个节点可以保存一个字节数组或者一个整数。适合存储小对象和长度有限的数据。


压缩列表是列表键和哈希键的底层实现之一,当列表键只包含少量列表项,并且每个列表项要么是小整数值,要么是长度比较短的字符串,那么 Redis 就会使用压缩列表来做列表键的底层实现。


举个例子,当哈希表只包含少量键值对,并且每个键值对的键和值要么就是小整数值,要么就是长度比较短的字符串,那么 Redis 就会使用压缩列表来做哈希键 的底层实现。


image.png


数据结构



下面是  ziplistEntry 的定义:


/* Each entry in the ziplist is either a string or an integer. */
typedef struct {
    /* When string is used, it is provided with the length (slen). */
    unsigned char *sval;
    unsigned int slen;
    /* When integer is used, 'sval' is NULL, and lval holds the value. */
    long long lval;
} ziplistEntry;


下面是压缩列表的每个部分组成(逻辑结构)


image.png


  1. zlbytes 记录了整个压缩列表的字节数,在压缩列表进行内存重新分配或者计算 zlend 的时候使用


  1. ztail 记录了压缩列表表尾节点距离压缩列表的起始地址有多少个字节,通过该偏移量无需遍历真个压缩列表就可以确定表尾节点,在返乡遍历时使用


  1. zllen 记录压缩列表包含的节点数量,当该值小于 65535 时,记录的列表节点数量;否则该值恒等于 65535时, 要获取节点数量需要进行遍历。


  1. zlend 特殊值 0xFF (十进制 255),用来标记压缩列表的末端。


举个例子(如下图):


image.png


每个部分说明:


1)列表 zlbytes 属性的值为 0x50 (十进制 80),表示压缩列表的总长度为 80 个字节


2)列表 zltail 属性的值为 0x3c (十进制 60),这个表示如果我们有一个指向压缩列表

的启始指针 p, 那么我们就用指针加上偏移量 60, 就可以计算出尾节点的 entry3. 的地址。


3)列表 zllen 属性值为 0x3(十进制 3 )表示有 3个节点。


节点构成



/* We use this function to receive information about a ziplist entry.
 * Note that this is not how the data is actually encoded, is just what we
 * get filled by a function in order to operate more easily. */
typedef struct zlentry {
    unsigned int prevrawlensize; /* Bytes used to encode the previous entry len*/
    unsigned int prevrawlen;     /* Previous entry len. */
    unsigned int lensize;        /* Bytes used to encode this entry type/len.
                                    For example strings have a 1, 2 or 5 bytes
                                    header. Integers always use a single byte.*/
    unsigned int len;            /* Bytes used to represent the actual entry.
                                    For strings this is just the string length
                                    while for integers it is 1, 2, 3, 4, 8 or
                                    0 (for 4 bit immediate) depending on the
                                    number range. */
    unsigned int headersize;     /* prevrawlensize + lensize. */
    unsigned char encoding;      /* Set to ZIP_STR_* or ZIP_INT_* depending on
                                    the entry encoding. However for 4 bits
                                    immediate integers this can assume a range
                                    of values and must be range-checked. */
    unsigned char *p;            /* Pointer to the very start of the entry, that
                                    is, this points to prev-entry-len field. */
} zlentry;


对应关系如下:


image.png


转换函数如下:


static inline void zipEntry(unsigned char *p, zlentry *e) {
    ZIP_DECODE_PREVLEN(p, e->prevrawlensize, e->prevrawlen);
    ZIP_ENTRY_ENCODING(p + e->prevrawlensize, e->encoding);
    ZIP_DECODE_LENGTH(p + e->prevrawlensize, e->encoding, e->lensize, e->len);
    assert(e->lensize != 0); /* check that encoding was valid. */
    e->headersize = e->prevrawlensize + e->lensize;
    e->p = p;
}


image.png


prevlen: 记录的是当前节点的长度,以字节为单位。当一个节点长度小于 254时, prevlen 是需要一个字节即可;否则 prevlen 需要使用 5 个字节来进行存储,其中第一个字节固定位 0xfe (254), 而后面 4个字节蒂娜存储前一个节点的长度。作用是:更具该属性可以快速定位前一个节点的起始位置,支持 ziplist 反向遍历。


1、 数据为字符串


编码 字符串长度 content 属性保存值
00bbbbbb 1 字节 长度小于 63 字节数组
01bbbbbb xxxxxxxx 2 字节 长度小于等于 16 383 字节数组
10_ _ _ _ _ _ aaaaaaaa bbbbbbbb cccccccc dddddddd 5 字节 长度小于等于 4 294 967 295字节数组


2、数据为整数时


编码 字符串长度 content 属性保存值
11000000 1 字节 Int16_t 类型的整数
11010000 1 字节 Int32_t 类型的整数
11100000 1 字节 Int64_t 类型的整数
11110000 1 字节 24 位有符号整数
11111110 1 字节 8 位有符号整数
1111xxxx 1 字节 使用这个编码的节点没有对应的 content 属性,因为编码本身 xxxx 四个位已经保存了一个介于 0 和 12 之间的值, 1 = 11110001> 13 = 11111111> 避免和 8 位冲突所以是 [0, 12] 所以它无需 content 属性


代码如下:


image.png


连锁更新



在 entry 中 prevlen 会保留前一个字节的长度:


  • 如果前一个字典长度小于 256 字节,那么 prevlen 属性需要一个字


  • 如果前一个字节的长度大于等于 256 字节,那么 prevlen 属性就需要用 5 个字节来保存这个长度


因此当插入或者删除操作,会打破 ziplist 具有特性,此时需要进行节点的更新。Redis 中只处理集诶单的扩张即 1 个字节变成 5 个重点,不进行收缩操作(为了防止反复出现缩小 -扩大)


最差的情况下:连续更新对 ziplist 执行 N 次空间分配操作,而每次重新分配最坏的复杂度为 O(N), 所以连锁更新最坏的情况是 O(N ^2)。


注意点



1、查找时间复杂度为 O(N)


2、列表的长度超过了 UINT16_MAX, 此时 zllen 不再表示节点的个数


3、连锁更新相关内容


相关实践学习
基于Redis实现在线游戏积分排行榜
本场景将介绍如何基于Redis数据库实现在线游戏中的游戏玩家积分排行榜功能。
云数据库 Redis 版使用教程
云数据库Redis版是兼容Redis协议标准的、提供持久化的内存数据库服务,基于高可靠双机热备架构及可无缝扩展的集群架构,满足高读写性能场景及容量需弹性变配的业务需求。 产品详情:https://www.aliyun.com/product/kvstore     ------------------------------------------------------------------------- 阿里云数据库体验:数据库上云实战 开发者云会免费提供一台带自建MySQL的源数据库 ECS 实例和一台目标数据库 RDS实例。跟着指引,您可以一步步实现将ECS自建数据库迁移到目标数据库RDS。 点击下方链接,领取免费ECS&RDS资源,30分钟完成数据库上云实战!https://developer.aliyun.com/adc/scenario/51eefbd1894e42f6bb9acacadd3f9121?spm=a2c6h.13788135.J_3257954370.9.4ba85f24utseFl
相关文章
|
10天前
|
NoSQL 关系型数据库 MySQL
Redis 列表(List)
10月更文挑战第16天
13 2
|
22天前
|
存储 分布式计算 NoSQL
大数据-40 Redis 类型集合 string list set sorted hash 指令列表 执行结果 附截图
大数据-40 Redis 类型集合 string list set sorted hash 指令列表 执行结果 附截图
23 3
|
2天前
|
存储 NoSQL Redis
Redis常见面试题:ZSet底层数据结构,SDS、压缩列表ZipList、跳表SkipList
String类型底层数据结构,List类型全面解析,ZSet底层数据结构;简单动态字符串SDS、压缩列表ZipList、哈希表、跳表SkipList、整数数组IntSet
|
25天前
|
缓存 NoSQL Redis
Redis命令:列表模糊删除详解
Redis命令:列表模糊删除详解
21 3
|
26天前
|
存储 缓存 NoSQL
数据的存储--Redis缓存存储(一)
数据的存储--Redis缓存存储(一)
60 1
|
26天前
|
存储 缓存 NoSQL
数据的存储--Redis缓存存储(二)
数据的存储--Redis缓存存储(二)
37 2
数据的存储--Redis缓存存储(二)
|
22天前
|
消息中间件 缓存 NoSQL
Redis 是一个高性能的键值对存储系统,常用于缓存、消息队列和会话管理等场景。
【10月更文挑战第4天】Redis 是一个高性能的键值对存储系统,常用于缓存、消息队列和会话管理等场景。随着数据增长,有时需要将 Redis 数据导出以进行分析、备份或迁移。本文详细介绍几种导出方法:1)使用 Redis 命令与重定向;2)利用 Redis 的 RDB 和 AOF 持久化功能;3)借助第三方工具如 `redis-dump`。每种方法均附有示例代码,帮助你轻松完成数据导出任务。无论数据量大小,总有一款适合你。
56 6
|
27天前
|
缓存 NoSQL 关系型数据库
redis和缓存及相关问题和解决办法 什么是缓存预热、缓存穿透、缓存雪崩、缓存击穿
本文深入探讨了Redis缓存的相关知识,包括缓存的概念、使用场景、可能出现的问题(缓存预热、缓存穿透、缓存雪崩、缓存击穿)及其解决方案。
127 0
redis和缓存及相关问题和解决办法 什么是缓存预热、缓存穿透、缓存雪崩、缓存击穿
|
2天前
|
存储 缓存 监控
利用 Redis 缓存特性避免缓存穿透的策略与方法
【10月更文挑战第23天】通过以上对利用 Redis 缓存特性避免缓存穿透的详细阐述,我们对这一策略有了更深入的理解。在实际应用中,我们需要根据具体情况灵活运用这些方法,并结合其他技术手段,共同保障系统的稳定和高效运行。同时,要不断关注 Redis 缓存特性的发展和变化,及时调整策略,以应对不断出现的新挑战。
21 10
|
2天前
|
缓存 监控 NoSQL
Redis 缓存穿透的检测方法与分析
【10月更文挑战第23天】通过以上对 Redis 缓存穿透检测方法的深入探讨,我们对如何及时发现和处理这一问题有了更全面的认识。在实际应用中,我们需要综合运用多种检测手段,并结合业务场景和实际情况进行分析,以确保能够准确、及时地检测到缓存穿透现象,并采取有效的措施加以解决。同时,要不断优化和改进检测方法,提高检测的准确性和效率,为系统的稳定运行提供有力保障。
20 5