- 浏览: 725002 次
- 性别:
- 来自: 上海
文章分类
- 全部博客 (168)
- 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)
- 机器学习 (1)
最新评论
-
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 2306本文转载自http://skynetdoc.com/?p=11 ... -
redis源码阅读笔记(13)——事务
2014-07-22 15:40 11771. 高层视角解读 redis的 ... -
redis源码阅读笔记(12)——发布与订阅
2014-07-21 16:33 16301. 发布/订阅 发布/订阅(Publish/subscrib ... -
redis源码阅读笔记(11)——服务器与客户端
2014-07-21 16:14 21581.高层视角 可首先阅读《Redis设计与实现》中的服务器与 ... -
redis源码阅读笔记(10)——事件
2014-07-20 14:40 15461. Reactor模式 Reactor模式(反应器模式)是一 ... -
redis源码阅读笔记(9)——RDB,AOF持久化
2014-07-18 16:12 24971. 持久化 Redis提供了两种持久化数据到硬盘的方式。 R ... -
redis源码阅读笔记(8)——数据库
2014-07-18 11:27 12901. 高层视角解读 Redis设计与实现中的数据库章节 Re ... -
redis源码阅读笔记(7)——对象
2014-07-12 23:19 7114本篇我们研究redis里的对象。 1. 概述 redis有5 ... -
redis源码阅读笔记(5)——intset
2014-07-08 16:23 8781.高层视角解读 整数集合(intset)是集合键的底层实现 ... -
redis源码阅读笔记(4)——skiplist
2014-07-08 15:08 9830.跳表基础知识 跳表(s ... -
redis源码阅读笔记(3)——dict
2014-07-08 13:26 14201.高层视角解读 字典, ... -
redis源码阅读笔记(2)——adlist
2014-07-07 15:54 1822adlist(A doubly linked list)是Re ... -
redis源码阅读笔记(1)——sds
2014-07-06 01:03 1434最近突然一时兴起,开 ... -
用spring-data-redis实现类似twitter的网站
2014-06-20 14:09 73771. spring-data-redis简介 封装了一下red ... -
jedis/nosql-unit初步
2014-06-17 16:36 11961. redis的客户端概述 redis的客户端实在太多了,比 ... -
redis初步
2014-06-16 23:19 16440. 介绍 redis是一个高性 ...
相关推荐
在Redis源码阅读笔记(10)——事件中,我们将探讨Redis如何利用事件模型来实现非阻塞I/O,以及相关的编程模型如Reactor模式和NIO。 Redis使用了一个基于epoll的事件处理器,epoll是Linux系统提供的一种高效I/O多路...
这篇源码阅读笔记主要关注Redis中的对象系统,它是Redis实现高效数据操作的关键。 在Redis中,每个数据都有一个特定的对象类型,比如`OBJ_STRING`、`OBJ_HASH`等,这些类型定义了数据的存储方式和操作行为。对象...
本篇笔记将聚焦于Redis源码中的“sds”(Simple Dynamic Strings,简单动态字符串)部分,这是Redis中处理字符串的基础数据结构。 首先,我们要明白sds是什么。在C语言中,字符串是以字符数组的形式存在的,而sds是...
- Redis提供了多个宏定义来方便地访问和操作`ziplist`的各个部分,例如`ZIPLIST_BYTES()`用于获取`ziplist`的总大小,`ZIPLIST_TAIL_OFFSET()`获取最后一个元素的偏移量,`ZIPLIST_LENGTH()`获取元素个数,以及`...
redis源码阅读中文分析注释
Redis是一个开源的使用ANSI C语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value数据库,并提供多种语言的API。 附件里面包括redis源码,phpredis源码,redis指令及文档
Redis 安装遇到的问题——Linux Centos7.5 Redis 是一个开源的、基于内存的数据结构存储系统,常用于数据库、缓存、消息队列等场景。但是,在 Linux Centos7.5 环境中安装 Redis 时可能会遇到一些问题,这篇文章将...
Redis,即远程字典服务,是一个开源的使用ANSI C语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value数据库,并提供多种语言的API。...本文适合Redis初学者和进阶者阅读,是一份全面而实用的学习笔记。
6. 异步执行与等待结果:代码示例展示了如何使用Await等待异步操作完成,这在处理可能需要时间的Redis操作时非常有用。 7. 关闭ActorSystem:最后,使用Akka框架的ActorSystem对象需要被终止,以确保所有后台线程...
通过阅读“狂神redis源码笔记”和解压的“redis-study”文件,你将能够深入理解Redis的内部运作,掌握Java客户端的使用技巧,提升在实际项目中运用Redis的能力。这包括但不限于了解Redis的设计模式、源码实现细节、...
6. **搜索功能**:提供搜索功能,帮助用户快速定位到目标键,对于大型Redis实例尤其有用。 7. **实时监控**:可以实时监控Redis服务器的性能指标,如内存使用、CPU占用率和命令执行速率等。 8. **版本更新**:例如...
Redis(Remote Dictionary Server),即远程字典服务,是一个开源的、高性能的、基于内存的Key-Value数据库,它使用ANSI C语言编写,支持网络,并提供了多种语言的API。Redis以其丰富的数据结构、高性能、持久化特性...
Redis全套学习笔记 完整版pdf.rar set:添加键值对 get:获取值 apend:追价值 strlen:获取值的长度 setnx:key不存在时,设置key的值 incr:原子递增1 decr:原子递减1 incrby/decrby:递增或者递减指定的数字 ...
Redis全套学习笔记 Redis是一种基于内存的NoSQL数据库,具有高性能、可扩展性和灵活性等特点。以下是Redis的详细知识点: 安装和启动 * 安装Redis可以通过下载软件包或使用yum、apt-get等安装工具进行安装。 * ...
在Windows环境下,Redis的源码分析和部署对于开发者来说具有重要意义,尤其是在Windows服务端开发中。以下是对"Redis Windows源码"的详细解析: 1. Redis核心架构: Redis基于单线程模型,通过事件驱动机制处理...
**一、Redis源码安装** 1. **下载源码** 首先,我们需要从Redis官方网站或者GitHub仓库下载源码。在这个例子中,我们使用的是`redis-2.8.9.tar.gz`。你可以通过命令行工具如`wget`或`curl`来下载,或者直接在网页...
Redis 安装简单,可以通过源码编译或使用包管理器安装。启动Redis有前台和后台两种方式,后台启动更常见。Redis 可通过`redis-cli`命令行工具进行交互,提供一系列命令用于操作数据库。 2. Redis 数据类型: - **...