- 浏览: 702851 次
- 性别:
- 来自: 上海
文章分类
- 全部博客 (167)
- CSS (1)
- Eclipse (4)
- English (1)
- ExtJS (1)
- Git (3)
- Grails (3)
- Groovy (2)
- Hadoop (7)
- HTML5 (2)
- JavaScript (3)
- Maven (2)
- MQ (5)
- MyBatis (3)
- NodeJS (6)
- NoSQL (4)
- Oracle (6)
- PDF (3)
- Python (9)
- Redis (17)
- Tomcat (2)
- Unix (8)
- Web Service (6)
- 安全 (1)
- 电子书 (6)
- 工具 (1)
- 其他 (21)
- 人工智能 (2)
- 视觉 (2)
- 算法 (6)
- 图表 (1)
- 网络 (13)
- 性能 (5)
- 游戏 (9)
- 字节码 (3)
- 机器学习 (0)
最新评论
-
lijunwyf:
cevin15 写道可以看下这个开源软件,https://gi ...
用markdown2html把md转换成html -
cevin15:
可以看下这个开源软件,https://github.com/c ...
用markdown2html把md转换成html -
Raina:
运行不了呢……提示错误无法加载主类Baiduwallpaper ...
用Java更换Windows桌面壁纸 -
苏城细雨沐秋风:
我把解码的jar添加到类路径后,mp3可以播放,但是flac和 ...
java播放mp3/ogg/ape/flac音乐 -
peishuai1987:
请问楼主现在怎么样了,读了很多源码吗,比如mybatis、sp ...
mybatis源码阅读心得
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
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
3种方法测试下来,普通的循环复制最慢,需要20多秒,而另外两种memcpy和memmove都只要2秒左右就完成了复制。
这是我在一台Win7 64位系统上测试的结果
这是我在另一台Win7 32位系统上测试的结果
其中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),
解释一下这个语法,c语言里面#define是允许写成函数的样子,且带有参数的,这种写法称之为类函数宏(function-like macro),宏的参数则用括号括起来。
以上语法类似于定义了一个函数ZIPLIST_BYTES,参数是zl,然后后面则是函数的实现。
9.2 一行写不下可以在一行的结尾加"\"表示下一行是连着的。
9.3 为何使用类函数宏
用意就是用空间换时间,因为函数调用是有额外开销的,还是为了提速啊。另外宏有一个取巧的地方,就是不用检查参数类型,不管你是啥类型,都接受。
比如
甭管你X,Y是int还是double型,都接受。
压缩列表(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型,都接受。
发表评论
-
redis官方文档中文版_Partitioning : 怎么样将你的数据分布在多个redis instance上?
2014-07-30 17:26 2213本文转载自http://skynetdoc.com/?p=11 ... -
redis源码阅读笔记(13)——事务
2014-07-22 15:40 10851. 高层视角解读 redis的 ... -
redis源码阅读笔记(12)——发布与订阅
2014-07-21 16:33 15391. 发布/订阅 发布/订阅(Publish/subscrib ... -
redis源码阅读笔记(11)——服务器与客户端
2014-07-21 16:14 20581.高层视角 可首先阅读《Redis设计与实现》中的服务器与 ... -
redis源码阅读笔记(10)——事件
2014-07-20 14:40 14521. Reactor模式 Reactor模式(反应器模式)是一 ... -
redis源码阅读笔记(9)——RDB,AOF持久化
2014-07-18 16:12 23981. 持久化 Redis提供了两种持久化数据到硬盘的方式。 R ... -
redis源码阅读笔记(8)——数据库
2014-07-18 11:27 11891. 高层视角解读 Redis设计与实现中的数据库章节 Re ... -
redis源码阅读笔记(7)——对象
2014-07-12 23:19 7019本篇我们研究redis里的对象。 1. 概述 redis有5 ... -
redis源码阅读笔记(5)——intset
2014-07-08 16:23 7881.高层视角解读 整数集合(intset)是集合键的底层实现 ... -
redis源码阅读笔记(4)——skiplist
2014-07-08 15:08 8900.跳表基础知识 跳表(s ... -
redis源码阅读笔记(3)——dict
2014-07-08 13:26 13351.高层视角解读 字典, ... -
redis源码阅读笔记(2)——adlist
2014-07-07 15:54 1734adlist(A doubly linked list)是Re ... -
redis源码阅读笔记(1)——sds
2014-07-06 01:03 1339最近突然一时兴起,开 ... -
用spring-data-redis实现类似twitter的网站
2014-06-20 14:09 72571. spring-data-redis简介 封装了一下red ... -
jedis/nosql-unit初步
2014-06-17 16:36 11031. redis的客户端概述 redis的客户端实在太多了,比 ... -
redis初步
2014-06-16 23:19 15200. 介绍 redis是一个高性 ...
相关推荐
redis源码阅读中文分析注释
NULL 博文链接:https://xpenxpen.iteye.com/blog/2093786
NULL 博文链接:https://xpenxpen.iteye.com/blog/2088678
NULL 博文链接:https://xpenxpen.iteye.com/blog/2091126
scala连接redis哨兵模式 demo 使用scala的redis库(csdn)————程序
1. Ziplist 能存储strings和integer值,整型值被存储为实际的整型值而不是字符数组 2. Ziplist 是为了尽可能节约内存而设计相当特殊
redis安装遇到的问题——linux centos7.5,包括未安装gcc,make不能编译等所有问题
Redis是一个开源的使用ANSI C语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value数据库,并提供多种语言的API。 附件里面包括redis源码,phpredis源码,redis指令及文档
Redis,即远程字典服务,是一个开源的使用ANSI C语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value数据库,并提供多种语言的API。...本文适合Redis初学者和进阶者阅读,是一份全面而实用的学习笔记。
redis源码级别的分析。需要具备c语言基础的开发学习,十分详细,带你全程深入了解redis。
redis的可视化工具,方便进行测试
Redis全套学习笔记 完整版pdf.rar set:添加键值对 get:获取值 apend:追价值 strlen:获取值的长度 setnx:key不存在时,设置key的值 incr:原子递增1 decr:原子递减1 incrby/decrby:递增或者递减指定的数字 ...
Redis全套学习笔记-带章节目录
springBoot集成Redis源码,springBoot集成Redis源码,springBoot集成Redis源码
redis的学习笔记
Redis源码阅读参考资料1
Redis学习笔记.pdf 含目录 #资源达人分享计划#
学习狂神说-Redis视频笔记,笔记完整并且加入了个人的理解和认知,笔记工整清晰,而且适合记忆学习。
Redis的Windows版本源码