`

redis之压缩列表源码剖析

阅读更多

形象化设计模式实战             HELLO!架构                     redis命令源码解析

 

用过Redis的应该对其哈希命令不陌生,在探索其实现之前,先得了解Redis的一个内部映射数据结构——压缩列表。

 

1、zipList的结构

找到ziplist.c文件,在代码注释中:

 * The general layout of the ziplist is as follows:
 * <zlbytes><zltail><zllen><entry><entry><zlend>

 

 

//注意这三个定义,新建时会使用。
#define ZIPLIST_BYTES(zl)       (*((uint32_t*)(zl))) //32位unsigned int,4个字节
#define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t))))
#define ZIPLIST_LENGTH(zl)      (*((uint16_t*)((zl)+sizeof(uint32_t)*2))) //16位unsigned int,2个字节
/* Create a new empty ziplist. 
 *
 * 创建并返回一个新的 ziplist 
 *
 * T = O(1)
 */
unsigned char *ziplistNew(void) {

    // ZIPLIST_HEADER_SIZE 是 ziplist 表头的大小
    // 1 字节是表末端 ZIP_END 的大小
    unsigned int bytes = ZIPLIST_HEADER_SIZE+1;

    // 为表头和表末端分配空间
    unsigned char *zl = zmalloc(bytes);

    // 初始化<zlbytes>,整个ziplist 占用的内存字节数,对ziplist 进行内存重分配,或者计算末端时使用。
    ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);
    // 初始化<zltail>,到达ziplist 表尾节点的偏移量。通过这个偏移量,可以在不遍历整个ziplist 的前提下,弹出表尾节点。
    ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE);
    // 新的list还没有entry,所以为0
    ZIPLIST_LENGTH(zl) = 0;
    // 初始化<zlend>,用于标记ziplist的末端
    zl[bytes-1] = ZIP_END;

    return zl;
}

 

成功后,ziplist结构如图所示:

 

2、节点(entry)的结构

 

+-----------------------+---------------+-----------+-------------+

 

| pre_entry_length | encoding | length | content |

 

+-----------------------+----------------+-----------+-------------+

pre_entry_length:记录了前一个节点的长度,通过这个值,可以进行指针计算,从而跳转到上一个节点,占用1或5字节。
encoding            :content的数据类型,值为00,01,10,11,占用两bit。
length                 :content的长度,占用1-5字节(和encoding一起)。
content               :真正要保存的数据。
 
这里知道个大概就好,后面会详解。
 
 

3、几个重要的宏

 
这里先看两个宏,因为插入节点时会用到。
/* Decode the number of bytes required to store the length of the previous
 * element, from the perspective of the entry pointed to by 'ptr'. 
 *
 * 解码 ptr 指针,
 * 取出编码前置节点长度所需的字节数,并将它保存到 prevlensize 变量中。
 *
 * T = O(1)
 */
#define ZIP_DECODE_PREVLENSIZE(ptr, prevlensize) do {                          \
    if ((ptr)[0] < ZIP_BIGLEN) {                                               \
        (prevlensize) = 1;                                                     \
    } else {                                                                   \
        (prevlensize) = 5;                                                     \
    }                                                                          \
} while(0);
ZIP_BIGLEN为254。
根据编码方式的不同,pre_entry_length 域可能占用1 字节或者5 字节:
• 1 字节:如果前一节点的长度小于254 字节,那么只使用一个字节保存它的值。
• 5 字节:如果前一节点的长度大于等于254 字节,那么将第1 个字节的值设为254 ,然后用接下来的4 个字节保存实际长度。
 
/* Extract the encoding from the byte pointed by 'ptr' and set it into
 * 'encoding'. 
 *
 * 从 ptr 中取出节点值的编码类型,并将它保存到 encoding 变量中。
 *
 * T = O(1)
 */
#define ZIP_ENTRY_ENCODING(ptr, encoding) do {  \
    (encoding) = (ptr[0]); \
    if ((encoding) < ZIP_STR_MASK) (encoding) &= ZIP_STR_MASK; \
} while(0)
ZIP_STR_MASK为0xc0,二进制就是11000000,与11000000取&,只能四种结果:11000000,1000000,01000000,00000000,这就是之前说encoding类型的由来。

 
/* Decode the length encoded in 'ptr'. The 'encoding' variable will hold the
 * entries encoding, the 'lensize' variable will hold the number of bytes
 * required to encode the entries length, and the 'len' variable will hold the
 * entries length. 
 *
 * 解码 ptr 指针,取出列表节点的相关信息,并将它们保存在以下变量中:
 *
 * - encoding 保存节点值的编码类型。
 *
 * - lensize 保存编码节点长度所需的字节数。
 *
 * - len 保存节点的长度。
 *
 * T = O(1)
 */
#define ZIP_DECODE_LENGTH(ptr, encoding, lensize, len) do {                    \
                                                                               \
    /* 取出值的编码类型 */                                                     \
    ZIP_ENTRY_ENCODING((ptr), (encoding));                                     \
                                                                               \
    /* 字符串编码 */                                                           \
    if ((encoding) < ZIP_STR_MASK) {                                           \
        if ((encoding) == ZIP_STR_06B) {                                       \
            (lensize) = 1;                                                     \
            (len) = (ptr)[0] & 0x3f;                                           \
        } else if ((encoding) == ZIP_STR_14B) {                                \
            (lensize) = 2;                                                     \
            (len) = (((ptr)[0] & 0x3f) << 8) | (ptr)[1];                       \
        } else if (encoding == ZIP_STR_32B) {                                  \
            (lensize) = 5;                                                     \
            (len) = ((ptr)[1] << 24) |                                         \
                    ((ptr)[2] << 16) |                                         \
                    ((ptr)[3] <<  8) |                                         \
                    ((ptr)[4]);                                                \
        } else {                                                               \
            assert(NULL);                                                      \
        }                                                                      \
                                                                               \
    /* 整数编码 */                                                             \
    } else {                                                                   \
        (lensize) = 1;                                                         \
        (len) = zipIntSize(encoding);                                          \
    }                                                                          \
} while(0);
</pre><pre name="code" class="cpp">/*
 * 字符串编码类型
 */
#define ZIP_STR_06B (0 << 6)
#define ZIP_STR_14B (1 << 6)
#define ZIP_STR_32B (2 << 6)
ZIP_STR_06B就是00000000,ZIP_STR_14B就是01000000,ZIP_STR_32B就是10000000,
 
00开头:1 byte ,长度小于等于63 字节的字符数组。
01开头:2 byte, 长度小于等于16383 字节的字符数组。
10开头:5 byte ,长度小于等于4294967295 的字符数组。
11开头:表示content 部分保存着整数。
 
结构略显复杂,感觉好省内存啊,哈哈。
 

4、插入节点

 
由于代码量太大,所以代码不贴出。
大致步骤:
1. 记录到达ziplist 末端所需的偏移量(因为之后的内存重分配可能会改变ziplist 的地址,因此记录偏移量而不是保存指针)
2. 根据新节点要保存的值,计算出编码这个值所需的空间大小,以及编码它前一个节点的长度所需的空间大小,然后对ziplist 进行内存重分配(如果不是末端,还需要计算出节点的相对偏移量:nextdiff,如果nextdiff不等于0,需要对list进行联动更新)。
3. 设置新节点的各项属性:pre_entry_length 、encoding 、length 和content 。
4. 更新ziplist 的各项属性,比如记录空间占用的zlbytes ,到达表尾节点的偏移量zltail,以及记录节点数量的zllen
 
大致图解:

 
这里解释一下__ziplistCascadeUpdate:就是在nextdiff不等于0时触发,新节点后面节点的pre_entry_length是1字节,但新节点的长度需要5字节,这样就需要更改新节点后面的节点的pre_entry_length,然而,因为新节点后面节点的空间长度改变了,所以程序又必须检查它的后继节点,看它的pre_entry_length 能否编码新长度,如果不能的话,程序又需要继续对下一个节点进行扩容,这就是__ziplistCascadeUpdate要做的。这种检查的时间复杂度是O(N2),但是这种概率比较小。
值得注意的是在抖动过程中,只扩展,不收缩,因为可能会出现重复的扩展——收缩——再扩展——再收缩的抖动(flapping)效果,这样只会降低Redis的性能。
 
内存映射数据结构可以节省大量的内存,不过,因为内存映射数据结构的编码和操作方式要比内部数据结构要复杂得多,所以内存映射数据结构所占用的CPU 时间会比作用类似的内部数据结构要多。
压缩列表解析到这了,查找(遍历列表查找),删除(移除后和insert一样进行__ziplistCascadeUpdate)没什么难点,有兴趣可以自己看下源码。

 

3
3
分享到:
评论

相关推荐

    redis压缩列表原理与应用

    Redis压缩列表是一种特殊的内存数据结构,它旨在通过特定的编码规则优化内存使用。在详细阐述压缩列表的原理和应用之前,首先需要理解它并非对数据进行传统意义上的压缩,而是通过编码方式将数据紧凑地存储在连续的...

    【作者面对面问答】包邮送《Redis 5设计与源码分析》5本

    墨墨导读:本文节选自《Redis 5设计与源码分析》,主要为读者分析Redis高性能内幕,重点从源码层次讲解了Redis事件模型,网络IO事件重在使用IO复用模型,时间事件重在限制最大执行CPU时间。最后简单介绍了Redis的...

    redis/phpredis源码及文档

    Redis是一个开源的使用ANSI C语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value数据库,并提供多种语言的API。 附件里面包括redis源码,phpredis源码,redis指令及文档

    Redis解压缩直接使用

    Redis是一种高性能的键值数据存储系统,由Salvatore Sanfilippo开发,最初设计为一个内存中的数据结构存储系统,但现在的版本支持持久化到磁盘,并提供了丰富的数据类型,如字符串、哈希表、列表、集合和有序集合。...

    windows上的redis解压缩版

    Redis基于内存存储,数据读写速度非常快,支持多种数据结构,如字符串、哈希、列表、集合和有序集合。它通过网络通信协议提供服务,可以与各种编程语言的客户端进行交互。 在Windows上安装Redis,通常步骤如下: 1....

    Redis操作各种类型源码,多种实现方式(含jar包)

    标题中的“Redis操作各种类型源码,多种实现方式”指的是通过编程语言与Redis进行交互,理解并实现其不同数据类型的存取操作。例如,你可以通过Java的Jedis库来操作Redis,实现如下功能: 1. 字符串(String):Redis...

    redis源码资源下载

    数据结构丰富:Redis支持多种数据结构,包括字符串(string)、哈希(hash)、列表(list)、集合(set)、有序集合(sorted set)等。这些数据结构都支持丰富的操作,如push/pop、add/remove以及取交集、并集和差集...

    Redis Windows源码

    例如,链表、跳跃表(用于有序集合的快速查找)和压缩表(用于节省内存)等都是Redis内部的重要组件。 3. 源码编译与配置: 要在Windows上编译Redis源码,首先需要安装GCC编译器(如MinGW)和make工具。然后,使用...

    redis-5.0.14.源码

    这些数据结构的实现通常采用内存优化的方式,如 SDS(Simple Dynamic String)代替 C 语言的标准字符串,压缩列表(Ziplist)和字典(Dictionary)用于存储不同数据类型。 2. **持久化**:Redis 提供了两种持久化...

    基于C#的NewLife.Redis高性能Redis协议封装设计源码

    本项目是基于C#的NewLife.Redis高性能Redis协议封装设计源码,包含119个文件,其中包括95个C#源文件、6个csproj文件、3个YAML文件、2个PNG图片文件、2个pubxml文件、1个Editorconfig文件、1个gitignore文件、1个eddx...

    redis源码日志(源码分析)

    "redis源码日志(源码分析)"是针对Redis源码进行深入剖析的学习资料,旨在帮助开发者理解如何通过源码实现Redis的高并发处理能力和海量数据存储功能。 在Redis中,高并发主要依赖于以下几点: 1. **单线程模型**...

    Redis实战中文版及源码下载

    在这个“Redis实战中文版及源码下载”的资源中,你将能够获取到关于Redis的实战经验和源码分析,这对于深入理解Redis的工作原理以及在实际项目中的应用非常有帮助。 Redis的主要特点包括: 1. **高速缓存**:Redis...

    redis字节码存压缩对象

    Redis 是一个高性能的键值数据库,它在存储数据时,为了优化内存使用和提升效率,会采用各种策略来处理数据,其中包括对数据进行压缩。在 Redis 中,字节码(Bytecode)是一种表示数据的方式,它可以是序列化的对象...

    Redis_redis_源码

    1. **Redis的数据结构**:Redis支持多种数据结构,如字符串(Strings)、哈希表(Hashes)、列表(Lists)、集合(Sets)和有序集合(Sorted Sets)。这些数据结构的设计使得Redis在处理复杂数据操作时非常高效。 2...

    redis压缩版windows64

    "redis压缩版windows64"标题表明这是一个专为64位Windows系统设计的Redis压缩包,简化了安装流程,用户只需解压即可开始使用。 在描述中提到的“解压即用”,意味着这个版本的Redis已经包含了所有运行所需文件,不...

    Redis协议客户端易语言模块源码

    资源介绍:。JimStone(谢栋) - Redis协议客户端模块。Redis协议客户端模块:STRedisClient for E。实现了对 Redis 客户端协议的封装。资源作者:。JimStone(谢栋)。资源界面:。资源下载:。

    redis实战(压缩版)

    在“redis实战(压缩版)”中,你将深入学习到如何利用Redis来提升应用的性能和可扩展性。 首先,Redis支持多种数据结构,包括字符串(Strings)、哈希(Hashes)、列表(Lists)、集合(Sets)和有序集合(Sorted Sets),这些...

    C# Redis秒杀活动系统源码

    **C# Redis 秒杀活动系统源码详解** 在当今的电商环境中,秒杀活动是一种常见的促销手段,能够迅速吸引用户关注并刺激消费。本文将深入解析基于C#开发、利用Redis作为缓存数据库的秒杀活动系统源码。Redis因其高效...

Global site tag (gtag.js) - Google Analytics