起因

notion 是个方便高效的工具，用起来很顺手，但是最近频繁的 Notion Incident 邮件报警看得我着实心烦，很担心哪天要用的时候服务挂了干着急。所以决定寻找 notion 的替代。

有段时间没有更新了。最近因为一些原因，换了工作。

之前的工作内容偏dmp，离线处理，业务相关的东西一直关注的比较少。现在转向线上广告引擎，与业务结合比较紧密，有点不习惯，需要改变一下思考的方式了。

quicklist是由ziplist构成的双向链表。ziplist需要可能对内存进行复制，在长度较长的时候，性能不佳。quicklist存储多个小ziplist，对除head和tail外的节点还进行了压缩，保证了push和pop性能的同时，又减少了内存的占用。

ziplist

结构

ziplist是一个压缩的双向链表，由一个特殊编码的连续内存块构成。如果没有特殊指定，所有字段都是以小端序来存储的。

1
2
3
4
5

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

entry：
<prevlen> <encoding> <entry-data>

ziplist：

结构

intset存储了有序的整数集合。

1
2
3
4
5

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

encoding决定如何解析contents，取值为，

1
2
3

#define INTSET_ENC_INT16 (sizeof(int16_t))
#define INTSET_ENC_INT32 (sizeof(int32_t))
#define INTSET_ENC_INT64 (sizeof(int64_t))

字节序

不同于其他结构，intset在存储的时候考虑了字节序的问题，redis会使用小端序来存储intset的所有字段。目的是intset能够兼容不同字节序的cpu。

skiplist

结构

skiplist提供了平均$O(log n)$的查找、插入和删除。zskiplistNode中使用柔性数组设计，每个节点存储了sds，level数组存储了各层指向其他节点的指针，最大层数为ZSKIPLIST_MAXLEVEL = 64。