redis5.0.4_redis源码阅读

redis5.0.4_redis源码阅读redis中压缩列表ziplist相关的文件为:ziplist.h与ziplist.c 压缩列表是redis专门开发出来为了节约内存的内存编码数据结构。源码中关于压缩列表介绍的注释也写得比较详细。 一

redis 5.0.7 源码阅读——压缩列表ziplist

redis中压缩列表ziplist相关的文件为:ziplist.h与ziplist.c

压缩列表是redis专门开发出来为了节约内存的内存编码数据结构。源码中关于压缩列表介绍的注释也写得比较详细。

一、数据结构

压缩列表的整体结构如下(借用redis源码注释):

1 /*
2 <zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend>
3 */

代码100分

各个部分的含义:

类型 长度 用途
zlbytes uint32_t 4B ziplist总字节数,包括zlbytes
zltail uint32_t 4B 最后一个entry的偏移量
zllen uint16_t 2B entry数量
zlend uint8_t 1B ziplist固定结尾,值固定为0xFF
entry 不定 不定 ziplist的各节点,具体结构不定

关于entry,借用redis源码注释的结构改造一下:

代码100分1 /*
2 <prevlen> <encoding> [<entry-data>]
3 */

prevlen表示的是前一个entry的长度,用于反向遍历,即从最后一个元素遍历到第一个元素。因每个entry的长度是不确定的,所以要记录一下前一个entry的长度。prevlen本身的长度也是不定的,与前一entry的实际长度有关。若长度小于254,只需要1B就可以了。若实际长度大于等于254,则需要5B,第1B固定为254,后面4B存储实际长度。

encoding则与entry存储的data有关。

encoding前两位 encoding内容 encoding长度 entry-data类型 entry-data长度
00 |00pppppp| 1B string 6b能表示的数字,0~63,encoding中存储的长度为大端字节序
01 |01pppppp|qqqqqqqq| 2B string 14b能表示的数字,64~16383,encoding中存储的长度为大端字节序
10 |10000000|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt| 5B string int32能表示的数字,16384~2^32-1,encoding中存储的长度为大端字节序
11 |11000000| 1B int16 2B
11 |11010000| 1B int32 4B
11 |11100000| 1B int64 8B
11 |11110000| 1B int24 3B
11 |11111110| 1B int8 1B
11 |1111xxxx| 1B xxxx在[0001,1101]之间,表示0~12的数字,存储时进行+1操作
11 |11111111| 1B End of ziplist special entry(源码注释)

如一个具体的ziplist,有两个成员“2”与“5”:

/*
[0f 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [ff]
      |             |          |       |       |     |
   zlbytes        zltail     zllen    "2"     "5"   end
*/

zlbytes值为15,表示这个ziplist总长为15B

zltail的值为12,表示最后一个entry的偏移量为12

zllen的值为2,表示一共有两个entry

第一个entry的prevlen为0。因为第一个成员之前没有其它成员了,所以是0,占1B。值为“2”,可以用数字表示,且是介于[0,12]之间,故使用1111xxxx的encoding方式,无entry-data。2的二进制编码为0010,+1后为0011,实际为11110011,即0xF3。同理,5的encoding为0xF6。做为第二个entry,其前一个entry的总长为2,故其prevlen值为2。

zlend固定是0xFF。

二、基本操作

redis中使用了大量的宏定义与函数配合操作ziplist。

1、创建

代码100分 1 #define ZIPLIST_HEADER_SIZE     (sizeof(uint32_t)*2+sizeof(uint16_t))
 2 #define ZIPLIST_END_SIZE        (sizeof(uint8_t))
 3 #define ZIPLIST_BYTES(zl)       (*((uint32_t*)(zl)))
 4 #define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t))))
 5 #define ZIPLIST_LENGTH(zl)      (*((uint16_t*)((zl)+sizeof(uint32_t)*2)))
 6 #define ZIP_END 255 
 7 
 8 
 9 unsigned char *ziplistNew(void) {
10     unsigned int bytes = ZIPLIST_HEADER_SIZE+ZIPLIST_END_SIZE;
11     unsigned char *zl = zmalloc(bytes);
12     ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);
13     ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE);
14     ZIPLIST_LENGTH(zl) = 0;
15     zl[bytes-1] = ZIP_END;
16     return zl;
17 }

新创建的ziplist,没有entry,只有zlbytes、zltail、zllen与zlend:

1 /*
2 [0b 00 00 00] [0a 00 00 00] [00 00] [ff]
3       |             |          |     |
4    zlbytes        zltail     zllen  end
5 */

2、插入

假设有以下ziplist:

1 /*
2 [0f 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [ff]
3       |             |          |       |       |     |
4    zlbytes        zltail     zllen    "2"     "5"   end
5 */

要在”2″与”5″之间插入节点“3”,则:

a.获取所要插入位置当前节点“5”的prevlen=2,prevlen_size=1

若要插入的位置是end处,则取出zltail进行偏移,取到“5”节点,直接进行计算。而如果当前是个空ziplist,直接就是0了。

b.获取节点“3”的实际长度,若其为纯数字,则可以使用数字存储,节约内存。否则直接使用外部传入的,string的长度。

这里有一点:

 1 int zipTryEncoding(unsigned char *entry, unsigned int entrylen, long long *v, unsigned char *encoding) {
 2     long long value;
 3 
 4     if (entrylen >= 32 || entrylen == 0) return 0;
 5     if (string2ll((char*)entry,entrylen,&value)) {
 6         /* Great, the string can be encoded. Check what"s the smallest
 7          * of our encoding types that can hold this value. */
 8         if (value >= 0 && value <= 12) {
 9             *encoding = ZIP_INT_IMM_MIN+value;
10         } else if (value >= INT8_MIN && value <= INT8_MAX) {
11             *encoding = ZIP_INT_8B;
12         } else if (value >= INT16_MIN && value <= INT16_MAX) {
13             *encoding = ZIP_INT_16B;
14         } else if (value >= INT24_MIN && value <= INT24_MAX) {
15             *encoding = ZIP_INT_24B;
16         } else if (value >= INT32_MIN && value <= INT32_MAX) {
17             *encoding = ZIP_INT_32B;
18         } else {
19             *encoding = ZIP_INT_64B;
20         }
21         *v = value;
22         return 1;
23     }
24     return 0;
25 }

在尝试使用数字编码的时候,如果len >= 32,则直接不尝试,并不清楚这个32是怎么来的。

本例中,“3”可以直接使用数字编码,且在[0,12]之间,故没有entry-data

c.获得本entry的总长度,即prevlen、encoding、entry-data长度和。本处为1+1=2

d.判断一下插入后,后一个entry的prevlen是否足够存储新entry的长度。新长度为2,原entry的prevlen只有1B,足够。

此处需要注意,如果原本是5B的prevlen,当前1B就足够存储,则不做任何处理,强制使用5B来存储1B能存储的数字。而如果原来是1B,当前要5B,则还需要4B空间。

e.重新分配ziplist空间。新增加的字节数,为c、d两步之和。此处只需要额外2B的空间。

分配空间后:

1 /*
2 [11 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [ff] [00 ff]
3       |             |          |       |       |     |
4    zlbytes        zltail     zllen    "2"     "5"   end
5 */

重新分配空间会自动设置zlend与zlbytes

f.将“5”及之后的节点(不包括zlend)往后移:

1 /*
2 [11 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [02 f6] [ff]
3       |             |          |       |       |       |
4    zlbytes        zltail     zllen    "2"     "5"     "5"  
5 */

g.修正当前“5”所在位置的prevlen=2:

1 /*
2 [11 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [02 f6] [ff]
3       |             |          |       |       |       |
4    zlbytes        zltail     zllen    "2"     "5"     "5"  
5 */

h.修改zltail:

1 /*
2 [11 00 00 00] [0e 00 00 00] [02 00] [00 f3] [02 f6] [02 f6] [ff]
3       |             |          |       |       |       |
4    zlbytes        zltail     zllen    "2"     "5"     "5"  
5 */

i.填写新entry:

1 /*
2 [11 00 00 00] [0e 00 00 00] [02 00] [00 f3] [02 f4] [02 f6] [ff]
3       |             |          |       |       |       |
4    zlbytes        zltail     zllen    "2"     "3"     "5"  
5 */

j.更新zllen:

1 /*
2 [11 00 00 00] [0e 00 00 00] [03 00] [00 f3] [02 f4] [02 f6] [ff]
3       |             |          |       |       |       |
4    zlbytes        zltail     zllen    "2"     "3"     "5"  
5 */

 

若在此基础上,在“3”前,插入的是一个长度为256的string X,则:

a.获取“3”的prevlen与prevlen_size

prevlen=2,prevlen_size=1

b.长度大于32,使用string进行存储,实际长度data_len=256

c.获取entry总长度

此处prevlen长度为1B,encoding长度为2B ,entry-data长度为256B,共1+2+256=259

d.判断一下插入后,后一个entry的prevlen是否足够存储新entry的长度。新长度为259,超过了254,需要5B,而原本只有1B,还差了4B。即,nextdiff=4

e.分配空间。新增加字节数为259+4=263,共280B,即0x118

分配空间后:

1 /*
2 [0x118] [0xe] [03 00] [00 f3] [02 f4] [02 f6] [...] [ff]
3    |      |      |       |       |       |      |   
4 zlbytes zltail zllen    "2"     "3"     "5"    263B
5    4B     4B
6 */

f.memmove操作

ziplist中的memmove操作:

1 memmove(p+reqlen,p-nextdiff,curlen-offset-1+nextdiff);

操作完之后:

1 /*
2 [...] [00 f3] [02 f4] [02 f6] [...] [03 00] [00 f3] [02 f4] [02 f6] [ff]
3   |      |       |       |      |              |       |       |
4 header  "2"     "3"     "5"    255B           "2"     "3"     "5"  
5  10B 
6 */

其中header为zlbytes、zltail与tllen

其实与以下写法相同效果:

1 memmove(p+reqlen+nextdiff,p,curlen-offset-1+nextdiff);

这种写法操作完之后:

1 /*
2 [0x118] [0xe] [03 00] [00 f3] [02 f4] [02 f6] [...] [02 f4] [02 f6] [ff]
3    |      |      |       |       |       |      |      |       |
4 zlbytes zltail zllen    "2"     "3"     "5"    259B   "3"     "5"  
5    4B     4B
6 */

目的是一样的,把原来的节点移至正确的位置上。

g.修正当前“3”所在位置的prevlen=259,即0X103:

1 /*
2 [0x118] [0xe] [03 00] [00 f3] [...] [FE 03 01 00 00 f4] [02 f6] [ff]
3    |      |      |       |      |            |             |
4 zlbytes zltail zllen    "2"    259B         "3"           "5"  
5    4B     4B
6 */

h.此时节点”3″的长度发生变化,需要更新其后一个节点”5″的prevlen:

1 /*
2 [0x118] [0xe] [03 00] [00 f3] [...] [FE 03 01 00 00 f4] [06 f6] [ff]
3    |      |      |       |      |            |             |
4 zlbytes zltail zllen    "2"    259B         "3"           "5"  
5    4B     4B
6 */

i.修改zltail:

1 /*
2 [0x118] [0x115] [03 00] [00 f3] [...] [FE 00 00 01 03 f4] [06 f6] [ff]
3    |       |       |       |      |            |             |
4 zlbytes  zltail  zllen    "2"    259B         "3"           "5"  
5    4B      4B
6 */

j.填写新entry:

encoding值为:01000001 00000000 即0x4100,大端字节序

填写后:

1 /*
2 [0x118] [0x115] [03 00] [00 f3] [02 41 00 ...] [FE 00 00 01 03 f4] [06 f6] [ff]
3    |       |       |       |          |                 |             |
4 zlbytes  zltail  zllen    "2"         X                "3"           "5"  
5    4B      4B                        259B
6 */

k.更新zllen:

1 /*
2 [0x118] [0x115] [04 00] [00 f3] [02 41 00 ...] [FE 00 00 01 03 f4] [06 f6] [ff]
3    |       |       |       |          |                 |             |
4 zlbytes  zltail  zllen    "2"         X                "3"           "5"  
5    4B      4B                        259B
6 */

 

若有连续几个entry的长度在[250,253]B之间,在插入新节点后可能存在连锁更新的情况。

如以下ziplist(只保留部分entry,其余节点省略):

1 /*
2 ... [FD 40 FA ...] [FD 40 FA ...] ...
3           |              |
4        E1 253B        E2 253B
5 */

E1的prevlen为FD,即长度为253。此时在E1之前插入一个长度为256的节点,E1需要增加prevlen的长度,从而导致E1整体长度增加。

E2的prevlen为FD,即E1的长度为253。增加4个节点之后为257,E2也需要增加prevlen的长度。

之后还可能会有E3,E4等entry需要处理,产生了连锁反应,直到到了以下情况才会停止:

i.到了zlend

ii.不需要继续扩展

iii.需要减少prevlen字节数时

连锁更新时需要多次重新分配空间,最坏情况下有n个节点的ziplist,需要分配n次空间,而每次分配的最坏情况时间复杂度为O(n),故连锁更新的最坏情况时间复杂度为O(n^2)。

 

3、查找

ziplist的查找过程其实是一次遍历,依次解析出prevlen、encoding与entry-data,然后根据encoding类型,决定是要用strcmp,还是直接使用数字的比较。在首次进行数字比较的时候,会把传入要查找的串,尝试一次转换成数字的操作。如果无法转换,就会跳过数字比较操作。

查找操作支持每隔几个entry才做一次比较操作。如,查找每5个entry中,值为“1”的entry。

 

4、删除

如有以下ziplist:

1 /*
2 [0x118] [0x115] [04 00] [00 f3] [02 41 00 ...] [FE 00 00 01 03 f4] [06 f6] [ff]
3    |       |       |       |          |                 |             |
4 zlbytes  zltail  zllen    "2"         X                "3"           "5"  
5    4B      4B                        259B
6 */

删除的是节点“5”,因是最后一个节点,则只要先修改zltail:

1 /*
2 [0x118] [0x10F] [04 00] [00 f3] [02 41 00 ...] [FE 00 00 01 03 f4] [06 f6] [ff]
3    |       |       |       |          |                 |             |
4 zlbytes  zltail  zllen    "2"         X                "3"           "5"  
5    4B      4B                        259B
6 */

然后resize:

1 /*
2 [0x116] [0x10F] [04 00] [00 f3] [02 41 00 ...] [FE 00 00 01 03 f4] [ff]
3    |       |       |       |          |                 |         
4 zlbytes  zltail  zllen    "2"         X                "3"        
5    4B      4B                        259B
6 */

最后修改zllen即可:

1 /*
2 [0x116] [0x10F] [03 00] [00 f3] [02 41 00 ...] [FE 00 00 01 03 f4] [ff]
3    |       |       |       |          |                 |         
4 zlbytes  zltail  zllen    "2"         X                "3"        
5    4B      4B                        259B
6 */

 

如果是这个ziplist:

1 /*
2 [0x118] [0x115] [04 00] [00 41 00 ...] [FE 00 00 01 03 f4] [06 f3] [02 f6] [ff]
3    |       |       |          |                 |             |       |
4 zlbytes  zltail  zllen        X                "3"           "2"     "5"  
5    4B      4B                259B
6 */

如果删除是的节点”3″,则先要计算删除后,”3″节点后的”2″节点的prevlen长度是否足够,然后直接写入。此时长度不够,并不会直接重新分配空间,而是直接使用之前”3″节的最后4B空间:

1 /*
2 [0x118] [0x115] [04 00] [00 41 00 ...] [FE 00] [FE 00 00 01 03 f3] [02 f6] [ff]
3    |       |       |          |           |             |             |
4 zlbytes  zltail  zllen        X           2B           "2"           "5"  
5    4B      4B                259B
6 */

然后修改zltail:

1 /*
2 [0x118] [0x113] [04 00] [00 41 00 ...] [FE 00] [FE 00 00 01 03 f3] [02 f6] [ff]
3    |       |       |          |           |             |             |
4 zlbytes  zltail  zllen        X           2B           "2"           "5"  
5    4B      4B                259B
6 */

接着进行memmove操作:

1 /*
2 [0x118] [0x113] [04 00] [00 41 00 ...] [FE 00 00 01 03 f3] [02 f6] [02 f6] [ff]
3    |       |       |          |                 |             |       | 
4 zlbytes  zltail  zllen        X                "2"           "5"     "5"
5    4B      4B                259B
6 */

resize操作:

1 /*
2 [0x116] [0x113] [04 00] [00 41 00 ...] [FE 00 00 01 03 f3] [02 f6] [ff]
3    |       |       |          |                 |             |   
4 zlbytes  zltail  zllen        X                "2"           "5"  
5    4B      4B                259B
6 */

最后要更新节点”2″及其之后entry的prevlen:

1 /*
2 [0x116] [0x113] [04 00] [00 41 00 ...] [FE 00 00 01 03 f3] [06 f6] [ff]
3    |       |       |          |                 |             |   
4 zlbytes  zltail  zllen        X                "2"           "5"  
5    4B      4B                259B
6 */

注意此时更新也是有可能产生连锁反应。

删除操作支持删除从指定位置开始,连续n个entry,操作类似。

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
转载请注明出处: https://daima100.com/10040.html

(0)
上一篇 2023-01-26
下一篇 2023-01-27

相关推荐

  • 我眼中的大数据(一)[通俗易懂]

    我眼中的大数据(一)[通俗易懂]前言 在正式落地谈技术之前,先花一些篇幅说说大数据技术的发展史。我们常说的大数据技术,其实起源于Google在2004年前后发表的三篇论文,分别是分布式文件系统GFS、大数据分布式计算框架MapRed

    2023-06-07
    155
  • 技术分享 | 使用备份恢复实例时存在的坑「终于解决」

    技术分享 | 使用备份恢复实例时存在的坑「终于解决」作者:林靖华 爱可生服务团队成员,负责处理客户在MySQL日常运维中遇到的问题;擅长处理备份相关的问题,对数据库相关技术有浓厚的兴趣,喜欢钻研各种问题。 本文来源:原创投稿 *爱可生开源社区出品,原…

    2023-02-06
    143
  • Oracle学习(六) — PL/SQL(一) 赋值、类型、异常、if、循环[通俗易懂]

    Oracle学习(六) — PL/SQL(一) 赋值、类型、异常、if、循环[通俗易懂]概述: PL/SQL(Procedural Language/SQL)是一种 Oracle数据库特有的、支持应用开发的语言,是Oracle在标准SQL语言上进行过程性扩展后形成的程序设计语言。 PL…

    2023-03-07
    147
  • 使用Tablib进行数据处理

    使用Tablib进行数据处理数据处理在计算机科学和工程中是一个重要的领域,常见的应用包括数据挖掘、机器学习、统计分析等等。在Python中,有许多第三方的库可以帮助我们进行数据处理。本文将介绍一种名为Tablib的库,它能够帮助我们轻松地进行数据导入、导出和转换。

    2024-04-24
    64
  • 电脑系统重装后没有声音怎么办[亲测有效]

    电脑系统重装后没有声音怎么办[亲测有效]电脑系统重装后没有声音怎么办,下面与大家分享下系统重装后没有声音怎么解决的教程。 1第一步鼠标右键单击此电脑,选择管理进入页面,单击设备管理器,展开声音、视频和游戏控制器,查看设备是否有问号,如果有…

    2023-04-10
    161
  • navicat调节字体大小_页面字体大小怎么调

    navicat调节字体大小_页面字体大小怎么调Navicat是一套快速、可靠和全面的数据库管理工具,专门用于简化数据库管理和降低管理成本。Navicat图形界面直观,提供简便的管理方法,设计和操作MySQL、MariaDB、SQL Server、

    2023-06-10
    145
  • MongoDB(八):索引[通俗易懂]

    MongoDB(八):索引[通俗易懂]1. 索引 索引支持查询的有效地提高效率。没有索引,MongoDB必须扫描集合的每个文档,以选择与查询语句匹配的文档。这种扫描效率很低,需要MongoDB处理大量的数据。 索引是特殊的数据结构,以易于

    2022-12-28
    145
  • win7怎么远程连接服务器_win7局域网远程桌面连接

    win7怎么远程连接服务器_win7局域网远程桌面连接windows7远程桌面连接 服务器群控远程桌面是微软公司为了便于网络管理员管理维护服务器推出的一项服务。从windows 2000 server版本开始引入,网络管理员时候远程桌面连接器连接到网络…

    2023-02-24
    139

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注