Redis数据结构源码解析(四) 压缩列表

结合Java对比Redis的压缩列表

说到Java中的列表，我们可能会快想到 ArrayList和 LinkedList，他们俩的区别在于一个是数组实现一个是链表实现。对于数组和链表都有各自的优劣。

回到Redis的列表同样也可以使用数组和列表去实现，Redis中有实现 listNode 和 list 结构，使用了链表结果但是这只是用于服务端存放运行数据，不存放开发者存储的数据。

原因很简单：

链表在元素过多的时候确实可以提高插入的效率的优势，但是他对内存的管理不够优秀，会产生大量的内存碎片。内存碎片在大量执行内存操作的Redis中显然是不友好的。
链表的 Node 结构中前置节点和后置节点指针属性太多，造成内存的浪费！（真的是把勤俭持家发挥到了极致，从来没考虑过这个东西可能会浪费多少内存）

就如上两个问题在Redis中使用了数组作为压缩列表的底层实现。Redis自己定义了一个规范(或者叫格式?)，将数据整齐的安排好，有统一的插入与查询方法，保证即使列表被压缩在了数组中也能完整的读取。

抽象结构

先抽象的看一下，我前面所说的规范、格式大致是个什么样子

list

在数组中基本以如下格式进行存储

<zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend>

zlbytes :记录整个列表的占用字节数，也包括了自身的4个字节
zltail：记录从第一个节点到最后一个节点的偏移量，用于反向的遍历
zllen：节点个数，如果超过2^16 -1 时就无法记录节点个数了，此时统计需要O(N)遍历
entry：就是存储客户端数据的节点
zlend：一个标记位，类似于字符串中说到的 \0，仅仅是用于记录结束点

entity

<prevlen> <encoding> <entry-data>

prevlen：前驱节点的长度

encoding：当前节点的编码格式

entry-data：真正的数据

基本结构

zlentry

typedef struct zlentry {
    // 前置节点长度
    unsigned int prevrawlensize; /* Bytes used to encode the previous entry len*/
    // 前置
    unsigned int prevrawlen;     /* Previous entry len. */
    // encoding 长度
    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;

TODO

暂时先抽象了解，后续补上

优劣分析

ziplist 存储在一段连续的内存上，所以存储效率很高。但是，它不利于修改操作，插入和删除操作需要频繁的申请和释放内存。特别是当ziplist长度很长的时候，一次 realloc可能会导致大批量的数据拷贝。

总结

关于列表的底层实现，Java圈里貌似更多还是喜欢用链表，但是Redis使用了数组，原因是：链表会造成内存的碎片和过多的节点指针造成内存的浪费。