案例

Redis6

案例

Hash 类型键的字段个数小于 hash-max-ziplist-entries 并且每个字段名和小于字段值的长度 hash-max-ziplist-value 时，Redis 才会使用 OBJ_ENCODING_ZIPLIST 来存储该键，签署条件任意一个不满足则会转换为 OBJ_ENCODING_HT 的编码方式。

127.0.0.1:6379> config get hash*
1) "hash-max-ziplist-entries"
2) "512"
3) "hash-max-ziplist-value"
4) "64"
127.0.0.1:6379> config set hash-max-ziplist-entries 3
OK
127.0.0.1:6379> config set hash-max-ziplist-value 8
OK
127.0.0.1:6379> config get hash*
1) "hash-max-ziplist-entries"
2) "3"
3) "hash-max-ziplist-value"
4) "8"
127.0.0.1:6379> hset user01 name z3
(integer) 1
127.0.0.1:6379> object encoding user01
"ziplist"
# 字符值长度大于 8 时，编码格式会由 ZIPLIST 方式切换为 Hashtable 方式
127.0.0.1:6379> hset user01 name z3aaaaaaa
(integer) 0
127.0.0.1:6379> object encoding user01
"hashtable"
 
127.0.0.1:6379> hmset user01 name li4 age 28 score 98
OK
127.0.0.1:6379> object encoding user01
"ziplist"
127.0.0.1:6379> hmset user01 name li4 age 28 score 98 birth 19981111
"hashtable"
127.0.0.1:6379>

结构

• hash-max-ziplist-entries：使用压缩列表保存时哈希集合中的最大元素个数。
• hash-max-ziplist-value：使用压缩列表保存时哈希集合中单个元素的最大长度。

结论

• 哈希对象保存的键值对数量小于 512 个；

• 所有的键值对的键和值的字符串长度都小于等 64 byte（一个英文字母一个字节）时用 ziplist，反之用 hashtable。

• ziplist 升级到 hashtable 可以，反过来降级不可以

  一旦从压缩列表转为了哈希表，Hash 类型就会一直用哈希表进行保存而不会再转回压缩列表了。

  在节省内存空间方面哈希表就没有压缩列表高效了。

流程

源码分析

• t_hash.c

  • 在 Redis 中，hashtable 被称为字典（dictionary），它是一个数组 + 链表的结构

  • OBJ_ENCODING_HT 编码分析，每个键值对都会有一个 dictEntry

    OBJ_ENCODING_HT 这种编码方式内部才是真正的哈希表结构，或称为字典结构，其可以实现 O(1) 复杂度的读写操作，因此效率很高。在 Redis 内部，从 OBJ_ENCODING_HT 类型到底真正的散列表数据结构是一层层嵌套下去的，组织关系见面图：

    

    /* dict.h */
    typedef struct dictEntry {
        void *key;
        union {
            void *val;
            uint64_t u64;
            int64_t s64;
            double d;
        } v;
        struct dictEntry *next;
    } dictEntry;
     
    typedef struct dictType {
        uint64_t (*hashFunction)(const void *key);
        void *(*keyDup)(void *privdata, const void *key);
        void *(*valDup)(void *privdata, const void *obj);
        int (*keyCompare)(void *privdata, const void *key1, const void *key2);
        void (*keyDestructor)(void *privdata, void *key);
        void (*valDestructor)(void *privdata, void *obj);
    } dictType;
     
    /* This is our hash table structure. Every dictionary has two of this as we
     * implement incremental rehashing, for the old to the new table. */
    typedef struct dictht {
        dictEntry **table;
        unsigned long size;
        unsigned long sizemask;
        unsigned long used;
    } dictht;
     
    typedef struct dict {
        dictType *type;
        void *privdata;
        dictht ht[2];
        long rehashidx; /* rehashing not in progress if rehashidx == -1 */
        unsigned long iterators; /* number of iterators currently running */
    } dict;

    /* t_hash.c */
    /* Check the length of a number of objects to see if we need to convert a
     * ziplist to a real hash. Note that we only check string encoded objects
     * as their string length can be queried in constant time. */
    void hashTypeTryConversion(robj *o, robj **argv, int start, int end) {
        int i;
        size_t sum = 0;
     
        if (o->encoding != OBJ_ENCODING_ZIPLIST) return;
     
        for (i = start; i <= end; i++) {
            if (!sdsEncodedObject(argv[i]))
                continue;
            size_t len = sdslen(argv[i]->ptr);
            if (len > server.hash_max_ziplist_value) { // ⭐️
                hashTypeConvert(o, OBJ_ENCODING_HT); // ⭐️
                return;
            }
            sum += len;
        }
        if (!ziplistSafeToAdd(o->ptr, sum))
            hashTypeConvert(o, OBJ_ENCODING_HT); // ⭐️
    }

  • hset 命令解读

    /* t_hash.c */
    void hsetCommand(client *c) {
        int i, created = 0;
        robj *o;
     
        if ((c->argc % 2) == 1) {
            addReplyErrorFormat(c,"wrong number of arguments for '%s' command",c->cmd->name);
            return;
        }
     
        if ((o = hashTypeLookupWriteOrCreate(c,c->argv[1])) == NULL) return;
        hashTypeTryConversion(o,c->argv,2,c->argc-1); // ⭐️
     
        for (i = 2; i < c->argc; i += 2)
            created += !hashTypeSet(o,c->argv[i]->ptr,c->argv[i+1]->ptr,HASH_SET_COPY);
     
        /* HMSET (deprecated) and HSET return value is different. */
        char *cmdname = c->argv[0]->ptr;
        if (cmdname[1] == 's' || cmdname[1] == 'S') {
            /* HSET */
            addReplyLongLong(c, created);
        } else {
            /* HMSET */
            addReply(c, shared.ok);
        }
        signalModifiedKey(c,c->db,c->argv[1]);
        notifyKeyspaceEvent(NOTIFY_HASH,"hset",c->argv[1],c->db->id);
        server.dirty++;
    }

    /* t_hash.c */
    // 类型
    /* Check the length of a number of objects to see if we need to convert a
     * ziplist to a real hash. Note that we only check string encoded objects
     * as their string length can be queried in constant time. */
    void hashTypeTryConversion(robj *o, robj **argv, int start, int end) {
        int i;
        size_t sum = 0;
     
        if (o->encoding != OBJ_ENCODING_ZIPLIST) return;
     
        for (i = start; i <= end; i++) {
            if (!sdsEncodedObject(argv[i]))
                continue;
            size_t len = sdslen(argv[i]->ptr);
            if (len > server.hash_max_ziplist_value) {
                hashTypeConvert(o, OBJ_ENCODING_HT);
                return;
            }
            sum += len;
        }
        if (!ziplistSafeToAdd(o->ptr, sum))
            hashTypeConvert(o, OBJ_ENCODING_HT);
    }

• ziplist.c

  ziplist 压缩列表是一种紧凑编码格式，总体思想是多花时间来换取节约空间，即以部分读写性能为代价，来换取极高的内存空间利用率，因此只会用于字段个数少，且字段值也较小的场景。压缩列表内存利用率极高的原因与其连续内存的特性是分不开的。

  /* The ziplist is a specially encoded dually linked list that is designed
   * to be very memory efficient. It stores both strings and integer values,
   * where integers are encoded as actual integers instead of a series of
   * characters. It allows push and pop operations on either side of the list
   * in O(1) time. However, because every operation requires a reallocation of
   * the memory used by the ziplist, the actual complexity is related to the
   * amount of memory used by the ziplist.
   */

  想想我们的学过的一种GC垃圾回收机制：标记--压缩算法。当一个 hash 对象 只包含少量键值对且每个键值对的键和值要么就是小整数要么就是长度比较短的字符串，那么它用 ziplist 作为底层实现。

  • ziplist 概述

    为了节约内存而开发的，它是由连续内存块组成的顺序型数据结构，有点类似于数组。

    ziplist 是一个经过特殊编码的双向链表，它不存储指向前一个链表节点 prev 和指向下一个链表节点的指针 next 而是存储上一个节点长度和当前节点长度，通过牺牲部分读写性能，来换取高效的内存空间利用率，节约内存，是一种时间换空间的思想。只用在字段个数少，字段值小的场景里面。

     /*
     * ZIPLIST OVERALL LAYOUT
     * ======================
     *
     * The general layout of the ziplist is as follows:
     *
     * <zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend>
     *
     * NOTE: all fields are stored in little endian, if not specified otherwise.
     */

    

    ziplist 各个组成单元含义

    属性	类型	长度	用途
    zlbytes	uint32_t	4 字节	记录整个压缩列表占用的内存字节数：在对压缩列表进行内存重新分配，或者计算 zlend 的位置时使用
    zltail	uint32_t	4 字节	记录压缩列表表尾节点距离压缩列表的起始地址有多少字节：通过这个偏移量，程序无需遍历整个压缩列表就可以确定表尾节点的地址
    zllen	uint16_t	2 字节	记录了压缩列表包含的节点数量：当这个属性的值小于 UINT16_MAX（65535）时，整个属性的值就是压缩列表包含节点的数量；当整个值等于 UINT16_MAX 时，节点的真实数量需要遍历整个压缩列表才能计算得出
    entryX	列表节点	不定	压缩列表包含的各个节点，节点的长度由节点保存的内容决定
    zlend	uint8_t	1 字节	特殊值 0xFF（十进制 255），用于标记压缩列表的末端

  • zlentry 压缩列表节点的构成

    /* ziplist.c */
    /* We use this function to receive information about a ziplist entry.
     * Note that this is not how the data is actually encoded, is just what we
     * get filled by a function in order to operate more easily. */
    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;

  • ziplist 存取情况

    

    变量名	含义
    prevlen	记录了前一个节点的长度
    encoding	记录了当前节点实际数据的类型以及长度
    data	记录了当前节点的实际数据

    • zlentry 解析

      压缩列表 zlentry 节点结构：每个 zlentry 由前一个节点的长度、encoding 和 entry-data 三部分组成

      typedef struct zlentry {
          unsigned int prevrawlensize; /* 上一个节点的长度所占的字节数 */
          unsigned int prevrawlen;     /* 上一个节点的长度 */
          unsigned int lensize;        /* 编码当前节点长度len所需要的字节数 */
          unsigned int len;            /* 当前节点长度 */
          unsigned int headersize;     /* 当前节点的header大小，headersize = lensize + prevrawlensize */
          unsigned char encoding;      /* 当前节点的编码格式 */
          unsigned char *p;            /* 当前节点指针 */
      } zlentry;

      • 前节点：（前节点占用的内存字节数）表示前 1 个 zlentry 的长度，privious_entry_length 有两种取值情况：1 字节或 5 字节。取值 1 字节时，表示上一个 entry 的长度小于 254 字节。虽然 1 字节的值能表示的数值范围是 0 到 255，但是压缩列表中 zlend 的取值默认是 255，因此，就默认用 255 表示整个压缩列表的结束，其他表示长度的地方就不能再用 255 这个值了。所以，当上一个 entry 长度小于 254 字节时，prev_len 取值为 1 字节，否则，就取值为 5 字节。记录长度的好处：占用内存小，1 或者 5 个字节。

      • enncoding：记录节点的 content 保存数据的类型和长度。

      • content：保存实际数据内容

      

    • 为什么 zlentry 这么设计？数组和链表数据结构对比

      privious_entry_length，encoding 长度都可以根据编码方式推算，真正变化的是 content，而 content 长度记录在 encoding 里 ，因此 entry 的长度就知道了。entry 总长度 = privious_entry_length 字节数 + encoding 字节数 + content字节数

      

      为什么 entry 这么设计？记录前一个节点的长度？

      链表在内存中，一般是不连续的，遍历相对比较慢，而 ziplist 可以很好的解决这个问题。如果知道了当前的起始地址，因为 entry 是连续的，entry 后一定是另一个 entry，想知道下一个 entry 的地址，只要将当前的起始地址加上当前 entry 总长度。如果还想遍历下一个 entry，只要继续同样的操作。

  • 明明有链表了，为什么出来一个压缩链表？

    • 普通的双向链表会有两个指针，在存储数据很小的情况下，我们存储的实际数据的大小可能还没有指针占用的内存大，得不偿失。ziplist 是一个特殊的双向链表没有维护双向指针：previous next；而是存储上一个 entry 的长度和当前 entry 的长度，通过长度推算下一个元素在什么地方。牺牲读取的性能，获得高效的存储空间，因为（简短字符串的情况）存储指针比存储 entry 长度更费内存。这是典型的”时间换空间“。

    • 链表在内存中一般是不连续的，遍历相对比较慢而 ziplist 可以很好的解决这个问题，普通数组的遍历是根据数组里存储的数据类型找到下一个元素的（例如 int 类型的数组访问下一个元素时每次只需要移动一个 sizeof(int) 就行），但是 ziplist 的每个节点的长度是可以不一样的，而我们面对不同长度的节点又不可能直接 sizeof(entry)，所以 ziplist 只好将一些必要的偏移量信息记录在了每一个节点里，使之能跳到上一个节点或下一个节点。

      备注：sizeof 实际上是获取了数据在内存中所占用的存储空间，以字节为单位来技术。

    • 头节点里有头节点里同时还有一个参数 len，和 string 类型提到的 SDS 类似，这里是用来记录链表长度的。因此获取链表长度时不用再遍历整个链表，直接拿到 len 值就可以了，这个时间复杂度是 O(1)。

  • ziplist 总结

    • ziplist 为了节省内存，采用了紧凑的连续存储。
    • ziplist 是一个双向链表，可以在时间复杂度为 O(1) 下从头部、尾部进行 pop 或 push。
    • 新增或更新元素可能会出现连锁更新现象（致命缺点导致被 listpack 替换）。
    • 不能保存过多的元素，否则查询效率就会降低，数量小和内容小的情况下可以使用。

Redis7

案例

Hash 类型键的字段个数小于 hash-max-listpack-entries 且每个字段名和字段值的长度小于 hash-max-listpack-value 时，Redis 才会使用 OBJ_ENCODING_LISTPACK 来存储该键，前述条件任意一个不满足则会转换为 OBJ_ENCODING_HT 的编码方式。

127.0.0.1:6379> config get hash*
1) "hash-max-ziplist-value"
2) "64"
3) "hash-max-listpack-entries"
4) "512"
5) "hash-max-ziplist-entries"
6) "512"
7) "hash-max-listpack-value"
8) "64"
127.0.0.1:6379> config set hash-max-listpack-entries 3
OK
127.0.0.1:6379> config set hash-max-listpack-value 5
OK
127.0.0.1:6379> config get hash*
1) "hash-max-ziplist-value"
2) "5"
3) "hash-max-listpack-entries"
4) "3"
5) "hash-max-ziplist-entries"
6) "3"
7) "hash-max-listpack-value"
8) "5"
127.0.0.1:6379> config set hash-max-ziplist-value 7
OK
127.0.0.1:6379> config set hash-max-ziplist-entries 7
OK
127.0.0.1:6379> config get hash*
1) "hash-max-ziplist-value"
2) "7"
3) "hash-max-listpack-entries"
4) "7"
5) "hash-max-ziplist-entries"
6) "7"
7) "hash-max-listpack-value"
8) "7"
127.0.0.1:6379> config set hash-max-listpack-entries 2
OK
127.0.0.1:6379> config set hash-max-listpack-value 4
OK
127.0.0.1:6379> hset user01 id 1 name z3
(integer) 2
127.0.0.1:6379> object encoding user01
"listpack"
127.0.0.1:6379> hset user01 id 1 name z3 age 22
(integer) 1
127.0.0.1:6379> object encoding user01
"hashtable"
127.0.0.1:6379> 

结构

• hash-max-listpack-entries：使用压缩列表保存时哈希集合中的最大元素个数。
• hash-max-listpack-value：使用压缩列表保存时哈希集合中单个元素的最大长度。

结论

• 哈希对象保存的键值对数量小于 512 个；
• 所有的键值对的键和值的字符串长度都小于等 64 byte（一个英文字母一个字节）时用 listpack，反之用 hashtable。
• listpack升级到 hashtable 可以，反过来降级不可以

流程

同前，只不过 ziplist 修改为 listpack

源码分析

• 源码说明

  /* object.c */
  robj *createHashObject(void) {
      unsigned char *zl = lpNew(0);
      robj *o = createObject(OBJ_HASH, zl);
      o->encoding = OBJ_ENCODING_LISTPACK;
      return o;
  }

  /* listpack.c */
  #define LP_HDR_SIZE 6       /* 32 bit total len + 16 bit number of elements. */
   
  /* Create a new, empty listpack.
   * On success the new listpack is returned, otherwise an error is returned.
   * Pre-allocate at least `capacity` bytes of memory,
   * over-allocated memory can be shrunk by `lpShrinkToFit`.
   * */
  unsigned char *lpNew(size_t capacity) {
      unsigned char *lp = lp_malloc(capacity > LP_HDR_SIZE+1 ? capacity : LP_HDR_SIZE+1);
      if (lp == NULL) return NULL;
      lpSetTotalBytes(lp,LP_HDR_SIZE+1);
      lpSetNumElements(lp,0);
      lp[LP_HDR_SIZE] = LP_EOF;
      return lp;
  }

  lpNew 函数创建了一个空的 listpack，一开始分配的大小是 LP_HDR_SIZE 再加 1 个字节。LP_HDR_SIZE 宏定义是在 listpack.c 中，它默认是 6 个字节，其中 4 个字节是记录 listpack 的总字节数，2 个字节是记录 listpack 的元素数量。此外，listpack 的最后一个字节是用来标识 listpack 的结束，其默认值是宏定义 LP_EOF。和 ziplist 列表项的结束标记一样，LP_EOF 的值也是 255。

  /* object.c */
  robj *createHashObject(void) {
      unsigned char *zl = lpNew(0);
      robj *o = createObject(OBJ_HASH, zl);
      o->encoding = OBJ_ENCODING_LISTPACK;
      return o;
  }
   
   
  /* ===================== Creation and parsing of objects ==================== */
   
  robj *createObject(int type, void *ptr) {
      robj *o = zmalloc(sizeof(*o));
      o->type = type;
      o->encoding = OBJ_ENCODING_RAW;
      o->ptr = ptr;
      o->refcount = 1;
   
      /* Set the LRU to the current lruclock (minutes resolution), or
       * alternatively the LFU counter. */
      if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
          o->lru = (LFUGetTimeInMinutes()<<8) | LFU_INIT_VAL;
      } else {
          o->lru = LRU_CLOCK();
      }
      return o;
  }
• 明明有 ziplist 了，为什么出来一个 listpack 紧凑列表？

  • 复习

    

    压缩列表里的每个节点中的 prevlen 属性都记录了【前一个节点的长度】，而且 prevlen 属性的空间大小跟前一节点长度值相关，比如：

    • 如果前一个节点的长度小于 254 字节，那么 prevlen 属性需要用 1 字节的空间来保存这个长度值；
    • 如果前一个节点的长度大于等于 254 字节，那么 prevlen 属性需要用 5 字节的空间来保存这个长度值。

  • ziplist 的连锁更新问题

    压缩列表新增某个元素或修改某个元素时，如果空间不不够，压缩列表占用的内存空间就需要重新分配。而当新插入的元素较大时，可能会导致后续元素的 prevlen 占用空间都发生变化，从而引起「连锁更新」问题，导致每个元素的空间都要重新分配，造成访问压缩列表性能的下降。

    案例说明：压缩列表每个节点正因为需要保存前一个节点的长度字段，就会有连锁更新的隐患

    第一步：现在假设一个压缩列表中有多个连续的、长度在 250～253 之间的节点，如下图：

    

    因为这些节点长度值小于 254 字节，所以 prevlen 属性需要用 1 字节的空间来保存这个长度值。

    第二步：这时，如果将一个长度大于等于 254 字节的新节点加入到压缩列表的表头节点，即新节点将成为entry1的前置节点，如下图：

    

    因为 entry1 节点的 prevlen 属性只有 1 个字节大小，无法保存新节点的长度，此时就需要对压缩列表的空间重分配操作并将 entry1 节点的 prevlen 属性从原来的 1 字节大小扩展为 5 字节大小。

    第三步：连续更新问题出现

    

    entry1 节点原本的长度在 250～253 之间，因为刚才的扩展空间，此时 entry1 节点的长度就大于等于 254，因此原本 entry2 节点保存 entry1 节点的 prevlen 属性也必须从 1 字节扩展至 5 字节大小。entry1 节点影响 entry2 节点，entry2 节点影响 entry3 节点......一直持续到结尾。这种在特殊情况下产生的连续多次空间扩展操作就叫做「连锁更新」

  • 结论

    listpack 是 Redis 设计用来取代掉 ziplist 的数据结构，它通过每个节点记录自己的长度且放在节点的尾部，来彻底解决掉了 ziplist 存在的连锁更新的问题

• listpack 结构

  General structure

  A listpack is encoded into a single linear chunk of memory. It has a fixed length header of six bytes (instead of ten bytes of ziplist, since we no longer need a pointer to the start of the last element). The header is followed by the listpack elements. In theory the data structure does not need any terminator, however for certain concerns, a special entry marking the end of the listpack is provided, in the form of a single byte with value FF (255). The main advantages of the terminator are the ability to scan the listpack without holding (and comparing at each iteration) the address of the end of the listpack, and to recognize easily if a listpack is well formed or truncated. These advantages are, in the idea of the writer, worth the additional byte needed in the representation.

  <tot-bytes> <num-elements> <element-1> ... <element-N> <listpack-end-byte>

  The six byte header, composed of the tot-bytes and num-elements fields is encoded in the following way:

  • tot-bytes: 32 bit unsigned integer holding the total amount of bytes representing the listpack. Including the header itself and the terminator. This basically is the total size of the allocation needed to hold the listpack and allows to jump at the end in order to scan the listpack in reverse order, from the last to the first element, when needed.
  • num-elements: 16 bit unsigned integer holding the total number of elements the listpack holds. However if this field is set to 65535, which is the greatest unsigned integer representable in 16 bit, it means that the number of listpack elements is not known, so a LIST-LENGTH operation will require to fully scan the listpack. This happens when, at some point, the listpack has a number of elements equal or greater than 65535. The num-elements field will be set again to a lower number the first time a LIST-LENGTH operation detects the elements count returned in the representable range.

  All integers in the listpack are stored in little endian format, if not otherwise specified (certain special encodings are in big endian because it is more natural to represent them in this way for the way the specification maps to C code).

  • 官网

    https://github.com/antirez/listpack/blob/master/listpack.md (opens in a new tab)

  • listpack 由 4 部分组成：total Bytes、Num Elem、Entry 以及 End

    <tot-bytes> <num-elements> <element-1> ... <element-N> <listpack-end-byte>
    |------ LP_HDR_SIZE ------|                            |----- 末尾标志 ----|

    组成	含义
    tot-bytes	为整个listpack 的空间大小，占用 4 个字节，每个 listpack 最多占用 4294967295Bytes
    num-elements	为 listpack 中的元素个数，即 Entry 的个数占用 2 个字节
    element-1 ~ element-N	为每个具体的元素
    listpack-end-byte	为 listpack 结束标志，占用 1 个字节，内容为 0xFF。

    

  • entry 结构

    Elements representation

    Each element in a listpack has the following structure:

    <encoding-type><element-data><element-tot-len>
    |                                            |
    +--------------------------------------------+
             (This is an element)

    The element type and element total length are always present. The element data itself sometimes is missing, since certain small elements are directly represented inside the spare bits of the encoding type.

    The encoding type is basically useful to understand what kind of data follows since strings can be encoded as little endian integers, and strings can have multiple string length fields bits in order to reduce space usage. The element data is the data itself, like an integer or an array of bytes representing a string. Finally the element total length, is used in order to traverse the list backward from the end of the listpack to its head, and is needed since otherwise there is no unique way to parse the entry from right to left, so we need to be able to jump to the left of the specified amount of bytes.

    Each element can always be parsed left-to-right. The first two bits of the first byte select the encoding. There are a total of 3 possibilities. The first two encodings represents small strings. The third encoding instead is used in order to specify other sub-encodings.

    • 当前元素的编码类型（entry-encoding）

    • 元素数据（entry-data）

    • 以及编码类型和元素数据这两部分的长度（entry-len）

    • listpackEntry 结构定义：

      /* redis/src/listpack.h */
      /* Each entry in the listpack is either a string or an integer. */
      typedef struct {
          /* When string is used, it is provided with the length (slen). */
          unsigned char *sval;
          uint32_t slen;
          /* When integer is used, 'sval' is NULL, and lval holds the value. */
          long long lval;
      } listpackEntry;
• ziplist 内存布局 VS listpack 内存布局

  

  和 ziplist 列表项类似，listpack 列表项也包含了元数据信息和数据本身。不过，为了避免 ziplist 引起的连锁更新问题，listpack 中的每个列表项不再像 ziplist 列表项那样保存其前一个列表项的长度。

  

Hash 的两种编码格式

• Redis6
  • ziplist
  • hashtable
• Redis7
  • listpack
  • hashtable