redis简介 （六）整数集合、压缩列表

1. 整数集合

1.1 基本用法

[[email protected] redis]# redis-cli 
127.0.0.1:6379> sadd numbers 10000 10086 10010
(integer) 3
127.0.0.1:6379> OBJECT encoding numbers
"intset"
127.0.0.1:6379> 
           

如果我们创建一个纯数字的集合，那么它的内部编码方式将是intset，整数集合。

1.2 数据结构

typedef struct intset {
    uint32_t encoding;
    uint32_t length;
    int8_t contents[];
} intset;
           

encoding 表示编码方式（注意这个encoding和object的encoding不同）

/* Note that these encodings are ordered, so:
 * INTSET_ENC_INT16 < INTSET_ENC_INT32 < INTSET_ENC_INT64. */
#define INTSET_ENC_INT16 (sizeof(int16_t))
#define INTSET_ENC_INT32 (sizeof(int32_t))
#define INTSET_ENC_INT64 (sizeof(int64_t))
           

length表示集合中元素的数量

contents是元素数组，数组中不含重复元素，且从小到大排列。看似contents是一个int8_t的数组，实际它取决于encoding的类型，如果是INTSET_ENC_INT16 则是int16_t数组，int32_t,int64_t亦然。

1.3 升级

一个整数集合的encoding为int8，那么插入一个int16、int32或者int64时，原先的编码容不下这么大的数据，那么集合将会发生升级。升级会重新分配内存，调整大小。redis这样做，可以达到节约内存的目的。

2 压缩列表

2.1 简介

压缩列表是哈希表的实现之一，当保存的对象是短字符串，redis会使用压缩列表来实现哈希键。

127.0.0.1:6379>  HMSET xiaoming age 25 sex male
OK
127.0.0.1:6379> hgetall xiaoming
1) "age"
2) "25"
3) "sex"
4) "male"
127.0.0.1:6379> OBJECT ENCODING xiaoming
"ziplist"
           

2.2 数据结构

ziplist和其他数据结构不同，它不是一个正常的结构体，而是一块连续的内存，程序通过宏来进行管理。原因在于它要让存放节点的entry尽量紧凑.

• zlbytes：4个字节，压缩列表总大小
• zltail_offset：4个字节，记录压缩列表最后一个节点entry到压缩列表的起始地址的偏移大小（字节）
• zllength：2个字节，压缩列表节点数量
• entry[1-N]：长度不定，保存节点数据
• zlend：1个字节结束标志(0xFF)

/* Utility macros.*/

/* Return total bytes a ziplist is composed of. */
#define ZIPLIST_BYTES(zl)       (*((uint32_t*)(zl)))

/* Return the offset of the last item inside the ziplist. */
#define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t))))

/* Return the length of a ziplist, or UINT16_MAX if the length cannot be
 * determined without scanning the whole ziplist. */
#define ZIPLIST_LENGTH(zl)      (*((uint16_t*)((zl)+sizeof(uint32_t)*2)))

/* The size of a ziplist header: two 32 bit integers for the total
 * bytes count and last item offset. One 16 bit integer for the number
 * of items field. */
#define ZIPLIST_HEADER_SIZE     (sizeof(uint32_t)*2+sizeof(uint16_t))

/* Size of the "end of ziplist" entry. Just one byte. */
#define ZIPLIST_END_SIZE        (sizeof(uint8_t))

/* Return the pointer to the first entry of a ziplist. */
#define ZIPLIST_ENTRY_HEAD(zl)  ((zl)+ZIPLIST_HEADER_SIZE)

/* Return the pointer to the last entry of a ziplist, using the
 * last entry offset inside the ziplist header. */
#define ZIPLIST_ENTRY_TAIL(zl)  ((zl)+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl)))

/* Return the pointer to the last byte of a ziplist, which is, the
 * end of ziplist FF entry. */
#define ZIPLIST_ENTRY_END(zl)   ((zl)+intrev32ifbe(ZIPLIST_BYTES(zl))-1)
           

entry的结构，为了支持双向遍历，存放了前一个entry的长度信息，当前entry的长度信息。剩下两个元素是编码和数据信息指针。

当前entry指针为p，那么上一个entry的地址就是p-p.prevrawlen.

prevrawlen是前一个节点的长度

prevrawlensize是指prevrawlen的大小，1字节或者5字节

typedef struct zlentry {
    unsigned int prevrawlensize; /* Bytes used to encode the previous entry len*/
    unsigned int prevrawlen;     /* Previous entry len. */
    unsigned int lensize;        /* Bytes used to encode this entry type/len.
                                    For example strings have a 1, 2 or 5 bytes
                                    header. Integers always use a single byte.*/
    unsigned int len;            /* Bytes used to represent the actual entry.
                                    For strings this is just the string length
                                    while for integers it is 1, 2, 3, 4, 8 or
                                    0 (for 4 bit immediate) depending on the
                                    number range. */
    unsigned int headersize;     /* prevrawlensize + lensize. */
    unsigned char encoding;      /* Set to ZIP_STR_* or ZIP_INT_* depending on
                                    the entry encoding. However for 4 bits
                                    immediate integers this can assume a range
                                    of values and must be range-checked. */
    unsigned char *p;            /* Pointer to the very start of the entry, that
                                    is, this points to prev-entry-len field. */
} zlentry;
           

添加或者删除节点时，可能会引发连锁更新的操作，连锁更新的最坏复杂度为O(N^2)。

假设在一个压缩列表中，包含e1、e2、e3、e4….. ，e1节点的小于或等于253字节，则e2.prevrawlen的大小为1字节。

在e2与e1之间插入了一个新节点e_new，e_new整体长度大于253字节，e2.prevrawlen会扩充为5字节；

接着e3会e2变化而变化，e4以后都会变化。删除节点时，也是这个道理。连锁更新引起空间再分配。ziplist的存储效率高，数据都一段连续的内存上。但是修改的时候，需要频繁申请释放内存，优缺点明显。所以Redis3.2之后，在部分场景下，采用quicklist替换了ziplist。如下链表中就采用了quicklist。

127.0.0.1:6379> rpush lst 1 2 3 100 125 150 190r
(integer) 7
127.0.0.1:6379> OBJECT ENCODING lst
"quicklist"
           

参考

redis设计与实现

https://blog.csdn.net/men_wen/article/details/70176753