第5集Redis工作原理之底层数据结构

struct sdshdr {
    int len;        // 字符串长度
    int free;       // 剩余空间
    char buf[];     // 字符数组
};

// 当SDS需要扩展时
if (newlen < SDS_MAX_PREALLOC)
    newlen *= 2;  // 预分配一倍空间
else
    newlen += SDS_MAX_PREALLOC;  // 预分配1MB

// 删除字符时，不立即释放内存
void sdstrim(sds s, const char *cset) {
    // 只是修改len和free字段，不释放内存
    // 下次append时可以复用这些空间
}

typedef struct zskiplistNode {
    robj *obj;                    // 成员对象
    double score;                 // 分值
    struct zskiplistNode *backward; // 后退指针
    struct zskiplistLevel {
        struct zskiplistNode *forward;  // 前进指针
        unsigned int span;               // 跨度
    } level[];
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;    // 节点数量
    int level;              // 层数
} zskiplist;

typedef struct zlentry {
    unsigned int prevrawlensize;  // 前一个节点长度字段的大小
    unsigned int prevrawlen;      // 前一个节点的长度
    unsigned int lensize;         // 当前节点长度字段的大小
    unsigned int len;             // 当前节点的长度
    unsigned int headersize;      // 头部大小
    unsigned char encoding;       // 编码方式
    unsigned char *p;             // 指向节点内容的指针
} zlentry;

typedef struct intset {
    uint32_t encoding;  // 编码方式
    uint32_t length;    // 集合包含的元素数量
    int8_t contents[];  // 保存元素的数组
} intset;

// 升级过程
intset *intsetUpgradeAndAdd(intset *is, int64_t value) {
    uint8_t curenc = intsetValueEncoding(is->encoding);
    uint8_t newenc = intsetValueEncoding(value);
    int length = intsetLen(is);
    
    // 设置新编码
    is->encoding = newenc;
    is = intsetResize(is, length + 1);
    
    // 从后往前重新插入元素
    for (int i = length - 1; i >= 0; i--) {
        intsetSet(is, i, intsetGetEncoded(is, i, curenc));
    }
    
    // 插入新元素
    intsetSet(is, length, value);
    return is;
}

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;         // rehash索引
    unsigned long iterators; // 迭代器数量
} dict;

int dictRehash(dict *d, int n) {
    int empty_visits = n * 10; // 最多访问n*10个空桶
    
    while (n-- && d->ht[0].used != 0) {
        dictEntry *de, *nextde;
        
        // 找到非空桶
        while (d->ht[0].table[d->rehashidx] == NULL) {
            d->rehashidx++;
            if (--empty_visits == 0) return 1;
        }
        
        // 迁移这个桶中的所有节点
        de = d->ht[0].table[d->rehashidx];
        while (de) {
            nextde = de->next;
            // 计算新哈希值
            h = dictHashKey(d, de->key) & d->ht[1].sizemask;
            de->next = d->ht[1].table[h];
            d->ht[1].table[h] = de;
            d->ht[0].used--;
            d->ht[1].used++;
            de = nextde;
        }
        d->ht[0].table[d->rehashidx] = NULL;
        d->rehashidx++;
    }
    
    // 检查是否完成rehash
    if (d->ht[0].used == 0) {
        zfree(d->ht[0].table);
        d->ht[0] = d->ht[1];
        _dictReset(&d->ht[1]);
        d->rehashidx = -1;
        return 0;
    }
    
    return 1;
}

// Redis对象的内存布局
typedef struct redisObject {
    unsigned type:4;        // 对象类型
    unsigned encoding:4;    // 编码方式
    unsigned lru:LRU_BITS;  // LRU时间戳
    int refcount;           // 引用计数
    void *ptr;              // 指向实际数据的指针
} robj;