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