这里只会记录在学习 Redis 源码时觉得比较好玩的地方，不会一五一十的讲细节。

内存分配

zmalloc 在实际 malloc 到的内存前面加一个 size 。

void *zmalloc(size_t size) {
    void *ptr = malloc(size+PREFIX_SIZE);
    *((size_t*)ptr) = size;
    update_zmalloc_stat_alloc(size+PREFIX_SIZE);
    return (char*)ptr+PREFIX_SIZE;
}

动态字符串 sds

sds 在基础的 char* 前面加一段 header 来记录信息（类似于 Go 实现）。

// 除了 sdshdr64，还有 sdshdr32、sdshdr16... 区分不同的长度上限
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* used */
    uint64_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

sds sdsnewlen(const void *init, size_t initlen) {
    ...
    sh = s_malloc(hdrlen+initlen+1);
    s = (char*)sh+hdrlen;   // 实际字符串
    memcpy(s, init, initlen);
    return s;
}

字典 dict

• 基本数据结构

  • dictEntry：键值对。（冲突处理：开链）
  • dictht：哈希表。记录使用情况用来 rehash
  • dict

    typedef struct dict {
        dictType *type; // 不同type有不同的hash算法
        void *privdata;
        dictht ht[2];   // 两个 ht 来实现渐进式的 rehash
        long rehashidx; /* rehashing not in progress if rehashidx == -1 */
        unsigned long iterators; /* number of iterators currently running */
    } dict;
    

• 哈希算法

• rehash：冲突元素太多时扩容。通过两个哈希表进行

  • 渐进式策略：
    • 每次执行操作时转移一个
    • 定时每次转移100个

• 数据操作

  • 每次操作前尽可能进行一次 rehash。
  • rehash 时，要依次在两个表里查询；其他操作类似。

跳跃表 zset

• 数据结构
  • span

整数集合 intset

• 数据结构
  • encoding 记录元素大小，对于小的数字，使用 int16_t 来节省内存。
• resize
  • 先分配足够内存，再调用 memmove 函数进行搬移
  • 单向升级，只有在插入元素的时候，如果 encoding 过小时会进行

鸣谢

• Redis源码剖析