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

本文涉及的产品
Redis 开源版,标准版 2GB
推荐场景:
搭建游戏排行榜
云数据库 Tair(兼容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
相关文章
|
29天前
|
NoSQL 关系型数据库 MySQL
Redis 列表(List)
10月更文挑战第16天
17 2
|
13天前
|
存储 NoSQL Java
Redis命令:列表模糊删除详解
通过本文的介绍,我们详细探讨了如何在Redis中实现列表的模糊删除。虽然Redis没有直接提供模糊删除命令,但可以通过组合使用 `LRANGE`和 `LREM`命令,并在客户端代码中进行模糊匹配,来实现这一功能。希望本文能帮助你在实际应用中更有效地操作Redis列表。
26 0
|
1月前
|
存储 分布式计算 NoSQL
大数据-40 Redis 类型集合 string list set sorted hash 指令列表 执行结果 附截图
大数据-40 Redis 类型集合 string list set sorted hash 指令列表 执行结果 附截图
27 3
|
21天前
|
存储 NoSQL Redis
Redis常见面试题:ZSet底层数据结构,SDS、压缩列表ZipList、跳表SkipList
String类型底层数据结构,List类型全面解析,ZSet底层数据结构;简单动态字符串SDS、压缩列表ZipList、哈希表、跳表SkipList、整数数组IntSet
|
NoSQL 关系型数据库 Redis
Redis命令——列表(List)
Redis列表是简单的字符串列表,按照插入顺序排序。你可以添加一个元素到列表的头部(左边)或者尾部(右边) 一个列表最多可以包含 232 - 1 个元素 (4294967295, 每个列表超过40亿个元素)。
858 0
|
1月前
|
存储 缓存 NoSQL
数据的存储--Redis缓存存储(一)
数据的存储--Redis缓存存储(一)
|
NoSQL Redis 索引
redis必杀命令:列表(List)
题记: Redis列表是简单的字符串列表,按照插入顺序排序。你可以添加一个元素导列表的头部(左边)或者尾部(右边) 一个列表最多可以包含 232 - 1 个元素 (4294967295, 每个列表超过40亿个元素)。
831 0
|
1月前
|
消息中间件 缓存 NoSQL
Redis 是一个高性能的键值对存储系统,常用于缓存、消息队列和会话管理等场景。
【10月更文挑战第4天】Redis 是一个高性能的键值对存储系统,常用于缓存、消息队列和会话管理等场景。随着数据增长,有时需要将 Redis 数据导出以进行分析、备份或迁移。本文详细介绍几种导出方法:1)使用 Redis 命令与重定向;2)利用 Redis 的 RDB 和 AOF 持久化功能;3)借助第三方工具如 `redis-dump`。每种方法均附有示例代码,帮助你轻松完成数据导出任务。无论数据量大小,总有一款适合你。
74 6
|
8天前
|
缓存 NoSQL 关系型数据库
大厂面试高频:如何解决Redis缓存雪崩、缓存穿透、缓存并发等5大难题
本文详解缓存雪崩、缓存穿透、缓存并发及缓存预热等问题,提供高可用解决方案,帮助你在大厂面试和实际工作中应对这些常见并发场景。关注【mikechen的互联网架构】,10年+BAT架构经验倾囊相授。
大厂面试高频:如何解决Redis缓存雪崩、缓存穿透、缓存并发等5大难题
|
10天前
|
存储 缓存 NoSQL
【赵渝强老师】基于Redis的旁路缓存架构
本文介绍了引入缓存后的系统架构,通过缓存可以提升访问性能、降低网络拥堵、减轻服务负载和增强可扩展性。文中提供了相关图片和视频讲解,并讨论了数据库读写分离、分库分表等方法来减轻数据库压力。同时,文章也指出了缓存可能带来的复杂度增加、成本提高和数据一致性问题。
【赵渝强老师】基于Redis的旁路缓存架构