Chinaunix首页 | 论坛 | 博客
  • 博客访问: 159118
  • 博文数量: 55
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 622
  • 用 户 组: 普通用户
  • 注册时间: 2016-12-21 22:26
个人简介

90后空巢老码农

文章分类

全部博文(55)

文章存档

2019年(7)

2018年(47)

2017年(1)

我的朋友

分类: NOSQL

2019-02-01 19:52:09

说实话,当我看见这两个文件的时候,内心深处的想法是崩溃的(哦谢特麻惹法克),你说你一个redis搞那么多list干啥。。。但是当我看到它的注释的时候,心里稍微好受了一点

点击(此处)折叠或打开

  1. /* quicklist.c - A doubly linked list of ziplists
  2.  */

真香!!!貌似这东西是一个双向链表,而链表的每个元素就是之前介绍过的ziplist,这样梳理一下,貌似一个东西刚刚讲过,还热乎,另一个是常规双向链表,有搞头了,嘿嘿嘿~~~
目前来讲的话这边提供了五中数据结构quicklistNode, quicklistLZF, quicklist,quicklistIter, quicklistEntry,它们的具体定义以及说明如下:
quicklistNode

点击(此处)折叠或打开

  1. typedef struct quicklistNode {
  2.     struct quicklistNode *prev;
  3.     struct quicklistNode *next;
  4.     unsigned char *zl;
  5.     unsigned int sz; /* 未被压缩的情况下:ziplist size in bytes */
  6.     unsigned int count : 16; /* count of items in ziplist */
  7.     unsigned int encoding : 2; /* RAW==1 or LZF==2 */
  8.     unsigned int container : 2; /* NONE==1 or ZIPLIST==2 */
  9.     unsigned int recompress : 1; /* was this node previous compressed? */
  10.     unsigned int attempted_compress : 1; /* node can't compress; too small */
  11.     unsigned int extra : 10; /* more bits to steal for future usage */
  12. } quicklistNode;
struct quicklistNode共占用32字节,定义中可以明确地看到使用了bit fields这种东西,字段当中:
字段 描述
count:16 ziplist当中的items
encoding:2 这里需要注意的是quicklist会使用一种名叫LZF的压缩算法来对ziplist压缩,如果压缩,该字段值为2;如果不压缩,该字段值为1。算法的具体实现见lzf的3个文件(lzf.h,lzf_c.c, lzf_d.c)。
container 存放数据的容器:1位NONE;2位ziplist,现阶段应该都是这个。
recompress:1 表示该节点是否为临时解压,若是,稍后会被压缩回去
attempted_compress:1 节点太小,不能被压缩
extra:10 保留
当整个节点没有被LZF压缩的时候,quicklistNode当中的zl会指向一个ziplist,但是,当该节点压缩之后,quicklistNode当中的zl会指向一个quicklistLZF结构体,其中的sz保存压缩后的字节数:

点击(此处)折叠或打开

  1. typedef struct quicklistLZF {
  2.     unsigned int sz; /* LZF size in bytes*/
  3.     char compressed[];
  4. } quicklistLZF;
quicklist是一个40字节的结构体,其结构如下,其中各个字段的值如代码中所示

点击(此处)折叠或打开

  1. typedef struct quicklist {
  2.     quicklistNode *head;
  3.     quicklistNode *tail;
  4.     unsigned long count; /* total count of all entries in all ziplists */
  5.     unsigned long len; /* number of quicklistNodes */
  6.     int fill : 16; /* 每一个节点中最多包含的元素个数-5到0xFFFF */
  7.     unsigned int compress : 16; /* depth of end nodes not to compress;0=off */
  8. } quicklist;
  9. /* Optimization levels for size-based filling */
  10. static const size_t optimization_level[] = {4096, 8192, 16384, 32768, 65536};
其中需要多说一下的字段是fill和compress,链表会根据fill字段的值来决定每个节点当中存放的元素个数,会参照上面的optimization_level的数组
fill值 描述
整数m 每个节点上的ziplist最多包含m个数据项
n = [-5,-1] 根据(-n)-1的值来确定下标,取下标对应的optimization_level数组中的元素来当做最大的数据项,默认值为-2
而compress字段表示当前quicklist当中两端各有多少个节点不压缩,若取0,则表示整个链表不压缩;若取2,则两端各有2个节点不进行压缩。
剩下的就是quicklistIter和quicklistEntry了,代码如下:

点击(此处)折叠或打开

  1. typedef struct quicklistIter {
  2.     const quicklist *quicklist;
  3.     quicklistNode *current;
  4.     unsigned char *zi;
  5.     long offset; /* offset in current ziplist */
  6.     int direction;
  7. } quicklistIter;

  8. typedef struct quicklistEntry {
  9.     const quicklist *quicklist;
  10.     quicklistNode *node;
  11.     unsigned char *zi;
  12.     unsigned char *value;
  13.     long long longval;
  14.     unsigned int sz;
  15.     int offset;
  16. } quicklistEntry;
由于这个链表当中涉及到压缩,但是如果被压缩的数据量过小的话,产生的结果可能比被压缩之前的数据还要占用空间,所以redis是定义了一些宏来避免这种情况的发生

点击(此处)折叠或打开

  1. #define SIZE_SAFETY_LIMIT 8192
  2. #define MIN_COMPRESS_BYTES 48
  3. #define MIN_COMPRESS_IMPROVE 8
由于quicklist结构的特殊性(大链表套小链表,期间还存在压缩解压等操作),其操作的代码也就比较繁琐(不算测试部分1400+行),但是如果将各个字段的含义搞明白之后,看起来就有人犹豫了,都是些结合其自身元素特性的一些组合,这里也就不再赘述了。





碎碎念在节前:节前是真的心累,各种事情焦头烂额,现在感觉没人报问题反而心里没有底了,真是fo了,不管如何,自己还是要努力向前冲,提前祝大家
新春快乐,年年暴富~~~~~~~~~~
阅读(272) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册