`
xpenxpen
  • 浏览: 731667 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

redis源码阅读笔记(6)——ziplist

阅读更多
1.高层视角解读

压缩列表(ziplist)是为了尽可能地节约内存而设计的特殊编码双端链表,是列表键和哈希键的底层实现之一。
当一个列表键或者哈希键只包含少量项, 并且每个项要么就是小整数值, 要么就是长度比较短的字符串, 那么 Redis 就会使用压缩列表来做底层实现。

请先看这篇文章
http://www.redisbook.com/en/latest/toc.html 里的第7章——压缩列表

2.底层代码
请看ziplist.h , ziplist.c, 2000多行代码。

3.(题外话)代码调试
和前面5篇文章提到的源代码相比,ziplist是到目前为止最复杂的一个数据结构了。首先这个数据结构没有一个.h文件来定义它的结构,所以一开始我看的云里雾里的。
如果看代码看不清楚的话,我们不妨写一个测试程序,再加上断点一步一步调试。
本人采用了cygwin(安装gcc,gdb)加上eclipse cdt来调试。
另外由于原版的redis代码我不知道怎么在eclipse里编译通过,所以重新改了一下,把和ziplist相关的代码抽取了出来,可以编译通过。可下载附件。
eclipse里面有个memory view,相当好,可以看某个内存地址里的值。我们可以通过观察内存地址里的值,从而理解ziplist的数据结构。

4.测试代码以及跟踪结果
测试代码在附件压缩包里的ziplist.c
int main(void)
{
	unsigned char *zl = ziplistNew();
	char * str1 = "abcde";
	char * str2 = "ABC";
	char * str3 = "10";
	zl = ziplistPush(zl, (unsigned char*)str1, strlen(str1), ZIPLIST_TAIL);
	zl = ziplistPush(zl, (unsigned char*)str2, strlen(str2), ZIPLIST_TAIL);
	zl = ziplistPush(zl, (unsigned char*)str3, strlen(str3), ZIPLIST_HEAD);
	return 0;
}


ziplist代码理解的难点就是,h文件中是没有这个数据结构的定义的(不像别的sds,adlist啊是看得到定义的)。另外zlentry只是一个中间临时存储变量,最后写到ziplist里就完全成了直接写连续的一块内存。

ZIPLIST_ENTRY_HEAD和ZIPLIST_ENTRY_TAIL分别指向第一个节点和最后一个节点,这个和java里的LinkedList还有redis里的adlist如出一辙,方便正向遍历和反向遍历。

ziplistNew以后如图所示,这个时候还一个元素都没有。


加入了第1个节点"abcde"以后


加入了第2个节点"ABC"以后(加在最后)
加入了第3个节点"10"以后(加在最前面)


5. 新增元素带来的扩容以及元素移动
每次加入节点时需要扩容,调用的是realloc函数,可以理解成这个函数会保留原来数组的内容,只是把数组容量扩大。当然,如果找不到足够的连续空间供扩容的话,就会另辟一块新的内存地址,并将原来数组的内容复制过去。
元素的加入有2种情况。
第一种是元素加到列表的末尾,这样前面的元素无需移动,将新元素放入新扩容的地址就行了。
第二种情况就是加到列表的开头或中间,这样后面的元素都要往后移动。我们可以想象是往ArrayList中间插入了一个元素,然后后面的元素一个一个往后挪动。这样有没有性能问题?

答案是没有性能问题的。注意最后一张图里的蓝线,代表着内存的移动,调用了一次memmove函数,用memmove的话只是内存拷贝,速度还是很快的。之所以不用memcpy是因为memcpy复制的两块内存不能有交叉。而memmove允许两块内存有重合的地方。

6.内存拷贝性能测试
测试代码可以见附件压缩包里的memmovetest.c
#include <stdio.h>
#include <string.h>
#include <time.h>

#define ROUND 100000000

int main(void)
{
	int N = 100;
	char src[N];
	char dest[N];
	memset(src, 'A', N);

	char * pSrc = src;
	char * pDest = dest;

	int i, j;

	//1. loop
	double timeStart = (double)clock();
	for (j = 0; j < ROUND; j++)
	{
		for (i = 0; i < N; i++)
		{
			*pDest++ = *pSrc++;
		}

		pSrc = src;
		pDest = dest;
	}
	double timeFinish = (double)clock();
	printf("operate time(loop): %.2fms\n", (timeFinish-timeStart));

	memset(dest, 0, N);



	//2. memcpy
	timeStart = (double)clock();
	for (j = 0; j < ROUND; j++)
	{
		memcpy(dest, src, N);
	}
	timeFinish = (double)clock();
	printf("operate time(memcpy): %.2fms\n", (timeFinish-timeStart));

	memset(dest, 0, N);

	//3. memmove
	timeStart = (double)clock();
	for (j = 0; j < ROUND; j++)
	{
		memmove(dest, src, N);
	}
	timeFinish = (double)clock();
	printf("operate time(memmove): %.2fms\n", (timeFinish-timeStart));

	return 0;
}


3种方法测试下来,普通的循环复制最慢,需要20多秒,而另外两种memcpy和memmove都只要2秒左右就完成了复制。
这是我在一台Win7 64位系统上测试的结果
operate time(loop): 23836.00ms
operate time(memcpy): 1701.00ms
operate time(memmove): 1279.00ms

这是我在另一台Win7 32位系统上测试的结果
operate time(loop): 26707.00ms
operate time(memcpy): 2762.00ms
operate time(memmove): 2886.00ms

其中memcpy和memmove的差别不明显,我测得的结果是32位系统上memcpy更快,而64位系统上memmove更快。原因不明?但都是一个数量级的。

至于原因么,因为memcpy和memmove的复制都是以word pointer为单位的,而自己写的那个是以byte pointer为单位的。另外,SIMD指令的运用也使得memcpy和memmove的执行得到了加速。

7.为何不用双向链表
通过图我们可以发现,双向链表(adlist)每个节点需要一个previous指针和一个next指针,这样2个指针就需要8个字节,而压缩列表(ziplist)一般情况下只需要2个字节,记录前一个元素的长度就可以了。

8.编码方式
如果可以转为数字,则转为数字。
会首先调用util.c里面的string2ll函数,尝试将string转为long long型,并以数字型存储。如"123"可以转成123,如果不能转,则以字符串形式存储。
比如前面的测试代码前面两个节点"abcde", "ABC"以字符串形式存储,而最后加入的第3个节点"10"可以转为整数10,这样只需要1个字节就能存10这个整数了,如果用字符串形式存储的话要2个字节(2个char)。(将内存榨干到极限啊!)(最后真正存入的是241+10=251)
解释:
当整数是介于 0 和 12 之间的值时,采用如下编码
1111xxxx 1 字节
11110000(2)=240(10)

9.#define的应用
通过阅读ziplist.c,可以看到有许多预处理器指令#define

9.1 类函数宏(function-like macro),
#define ZIPLIST_BYTES(zl)       (*((uint32_t*)(zl)))

解释一下这个语法,c语言里面#define是允许写成函数的样子,且带有参数的,这种写法称之为类函数宏(function-like macro),宏的参数则用括号括起来。
以上语法类似于定义了一个函数ZIPLIST_BYTES,参数是zl,然后后面则是函数的实现。

9.2 一行写不下可以在一行的结尾加"\"表示下一行是连着的。
#define ZIPLIST_INCR_LENGTH(zl,incr) { \
    if (ZIPLIST_LENGTH(zl) < UINT16_MAX) \
        ZIPLIST_LENGTH(zl) = intrev16ifbe(intrev16ifbe(ZIPLIST_LENGTH(zl))+incr); \
}


9.3 为何使用类函数宏
用意就是用空间换时间,因为函数调用是有额外开销的,还是为了提速啊。另外宏有一个取巧的地方,就是不用检查参数类型,不管你是啥类型,都接受。
比如
#define MAX (X, Y) ((X) > (Y) ? (X): (Y))

甭管你X,Y是int还是double型,都接受。
  • 大小: 3.2 KB
  • 大小: 3.2 KB
  • 大小: 10.8 KB
分享到:
评论

相关推荐

    redis源码阅读笔记(10)——事件

    在Redis源码阅读笔记(10)——事件中,我们将探讨Redis如何利用事件模型来实现非阻塞I/O,以及相关的编程模型如Reactor模式和NIO。 Redis使用了一个基于epoll的事件处理器,epoll是Linux系统提供的一种高效I/O多路...

    redis源码阅读笔记(7)——对象

    这篇源码阅读笔记主要关注Redis中的对象系统,它是Redis实现高效数据操作的关键。 在Redis中,每个数据都有一个特定的对象类型,比如`OBJ_STRING`、`OBJ_HASH`等,这些类型定义了数据的存储方式和操作行为。对象...

    redis源码阅读笔记(1)——sds

    本篇笔记将聚焦于Redis源码中的“sds”(Simple Dynamic Strings,简单动态字符串)部分,这是Redis中处理字符串的基础数据结构。 首先,我们要明白sds是什么。在C语言中,字符串是以字符数组的形式存在的,而sds是...

    ziplist--redis源码研究笔记-压缩列表ziplist1

    - Redis提供了多个宏定义来方便地访问和操作`ziplist`的各个部分,例如`ZIPLIST_BYTES()`用于获取`ziplist`的总大小,`ZIPLIST_TAIL_OFFSET()`获取最后一个元素的偏移量,`ZIPLIST_LENGTH()`获取元素个数,以及`...

    redis源码阅读中文分析注释

    redis源码阅读中文分析注释

    Redis 源码阅读.zip

    Redis 源码阅读Redis 源码阅读对Redis源码的注释工作已经转移到annotated_redis_source项目,欢迎意见、star和fork。黄子2013.3.5项目说明学习 Redis 的源码,并加上相关的注释。由于Redis的版本升级比较快,对源码...

    redis/phpredis源码及文档

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

    redis安装遇到的问题——linux centos7.5

    Redis 安装遇到的问题——Linux Centos7.5 Redis 是一个开源的、基于内存的数据结构存储系统,常用于数据库、缓存、消息队列等场景。但是,在 Linux Centos7.5 环境中安装 Redis 时可能会遇到一些问题,这篇文章将...

    Redis全套学习笔记 (带章节目录) 完整版pdf

    Redis,即远程字典服务,是一个开源的使用ANSI C语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value数据库,并提供多种语言的API。...本文适合Redis初学者和进阶者阅读,是一份全面而实用的学习笔记。

    redis源码资源下载

    Redis(Remote Dictionary Server),即远程字典服务,是一个开源的、高性能的、基于内存的Key-Value数据库,它使用ANSI C语言编写,支持网络,并提供了多种语言的API。Redis以其丰富的数据结构、高性能、持久化特性...

    scala连接redis哨兵模式 demo 使用scala的redis库(csdn)————程序.pdf

    6. 异步执行与等待结果:代码示例展示了如何使用Await等待异步操作完成,这在处理可能需要时间的Redis操作时非常有用。 7. 关闭ActorSystem:最后,使用Akka框架的ActorSystem对象需要被终止,以确保所有后台线程...

    狂神redis源码笔记.rar

    通过阅读“狂神redis源码笔记”和解压的“redis-study”文件,你将能够深入理解Redis的内部运作,掌握Java客户端的使用技巧,提升在实际项目中运用Redis的能力。这包括但不限于了解Redis的设计模式、源码实现细节、...

    redis的可视化工具——redisdesktopmanager

    6. **搜索功能**:提供搜索功能,帮助用户快速定位到目标键,对于大型Redis实例尤其有用。 7. **实时监控**:可以实时监控Redis服务器的性能指标,如内存使用、CPU占用率和命令执行速率等。 8. **版本更新**:例如...

    Redis全套学习笔记 完整版pdf.rar

    Redis全套学习笔记 完整版pdf.rar set:添加键值对 get:获取值 apend:追价值 strlen:获取值的长度 setnx:key不存在时,设置key的值 incr:原子递增1 decr:原子递减1 incrby/decrby:递增或者递减指定的数字 ...

    Redis全套学习笔记-带章节目录-114页.pdf

    Redis全套学习笔记 Redis是一种基于内存的NoSQL数据库,具有高性能、可扩展性和灵活性等特点。以下是Redis的详细知识点: 安装和启动 * 安装Redis可以通过下载软件包或使用yum、apt-get等安装工具进行安装。 * ...

    Redis Windows源码

    在Windows环境下,Redis的源码分析和部署对于开发者来说具有重要意义,尤其是在Windows服务端开发中。以下是对"Redis Windows源码"的详细解析: 1. Redis核心架构: Redis基于单线程模型,通过事件驱动机制处理...

    redis源码安装以及配置

    **一、Redis源码安装** 1. **下载源码** 首先,我们需要从Redis官方网站或者GitHub仓库下载源码。在这个例子中,我们使用的是`redis-2.8.9.tar.gz`。你可以通过命令行工具如`wget`或`curl`来下载,或者直接在网页...

Global site tag (gtag.js) - Google Analytics