redis内部实现

sdshdr 这个结构体在redis内部使用的非常频繁。由于C标准的字符串,没有记录字符串长度,如果要计算字符串长度,期时间复杂度是O(N),
redis通过sdshdr 结构表示字符串,并且通过len记录字符串当前的长度,和free来记录,当前可用的长度。

typedef char *sds;  // 兼容C标准字符串。

struct sdshdr {
    unsigned int len;
    unsigned int free;
    char buf[];     // 实际的字符串右 buf 这个指针指向
};

// 返回字符串长度。
static inline size_t sdslen(const sds s) {
    struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr))); // 这个通过公式可得到实际结构的指针地址,进而得到字符串长度。
    return sh->len;
}

// 返回剩余可用 这里使用了inline 来提升性能。
static inline size_t sdsavail(const sds s) {
    struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));
    return sh->free;
}

来看下sdshdr是如何初始化的:

/* Create a new sds string with the content specified by the 'init' pointer
 * and 'initlen'.
 * If NULL is used for 'init' the string is initialized with zero bytes.
 *
 * The string is always null-termined (all the sds strings are, always) so
 * even if you create an sds string with:
 *
 * mystring = sdsnewlen("abc",3);
 *
 * You can print the string with printf() as there is an implicit \0 at the
 * end of the string. However the string is binary safe and can contain
 * \0 characters in the middle, as the length is stored in the sds header. */
sds sdsnewlen(const void *init, size_t initlen) {   // 初始化长度
    struct sdshdr *sh;

    if (init) {
        sh = zmalloc(sizeof(struct sdshdr)+initlen+1);   // +1 是为了字符串末尾的 '\0' 
    } else {
        sh = zcalloc(sizeof(struct sdshdr)+initlen+1);  // 如果没有初始化字符串,就先初始化为0值
    }
    if (sh == NULL) return NULL;    // 内存分配失败
    sh->len = initlen;
    sh->free = 0;
    if (initlen && init)    // 如果需要初始化,就将字符串拷贝到新的字符串
        memcpy(sh->buf, init, initlen);
    sh->buf[initlen] = '\0';    // 标准字符串总是在末尾 加 0 或 '\0'
    return (char*)sh->buf;  // 返回的是C字符串指针。
}

// 注意,长度计算公式是:zmalloc(sizeof(struct sdshdr)+initlen+1)

分析 redis.dict 的实现

  • redis的哈希表实现使用的是拉链法.

哈希表单个键值对的结构实现如下:

typedef struct dictEntry {

    // 键
    void *key;

    // 值 (这里使用的union类型)
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;

    // 指向下个哈希表节点,形成链表
    struct dictEntry *next;

} dictEntry;

dictht结构体分析

  • dictht 表示 dict.hash-table
  • 大致的结构就是一个固定数组保存底层数据,然后每个数组元素都是一个链表 - 存储 dictEntry 链表
  • ...

Leave a Comment

Your email address will not be published. Required fields are marked *

PHP 8.1.1 - 29.265 ms, 0 Q