Redis 源码学习(一):常用数据结构

创作人 Leo


编辑时间 Mon Mar 15,2021 at 15:17


简介

本系列通过 redis 3.2.x 源代码分析 redis 程序
redis 通过 io 复用同时服务多个 client ;降低网络 io 等待时间
内部通过一个主循环顺序处理命令,实现单线程处理,避免了加锁带来的性能消耗以及降低程序维护的复杂度

本章主要介绍 redis 的基础数据结构:

  1. 对象 object
  2. 动态字符串 sds
  3. 哈希表 dict

Object

redis 所有的数据都被包装成了 object,然后保存到 db
db 实际上是在内存中维护的一个哈希表 dict
server.h 中定义了 redis 的 object 结构以及相关函数

/* The actual Redis Object */
#define LRU_BITS 24
#define LRU_CLOCK_MAX ((1<<LRU_BITS)-1) /* Max value of obj->lru */
#define LRU_CLOCK_RESOLUTION 1000 /* LRU clock resolution in ms */
typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS; /* lru time (relative to server.lruclock) */
    int refcount;
    void *ptr;
} robj;

/* Redis object implementation */
void decrRefCount(robj *o);
void decrRefCountVoid(void *o);
void incrRefCount(robj *o);
robj *resetRefCount(robj *obj);
void freeStringObject(robj *o);
void freeListObject(robj *o);
void freeSetObject(robj *o);
void freeZsetObject(robj *o);
void freeHashObject(robj *o);
robj *createObject(int type, void *ptr);
robj *createStringObject(const char *ptr, size_t len);
robj *createRawStringObject(const char *ptr, size_t len);
robj *createEmbeddedStringObject(const char *ptr, size_t len);
robj *dupStringObject(robj *o);
int isObjectRepresentableAsLongLong(robj *o, long long *llongval);
robj *tryObjectEncoding(robj *o);
robj *getDecodedObject(robj *o);
size_t stringObjectLen(robj *o);
robj *createStringObjectFromLongLong(long long value);
robj *createStringObjectFromLongDouble(long double value, int humanfriendly);
robj *createQuicklistObject(void);
robj *createZiplistObject(void);
robj *createSetObject(void);
robj *createIntsetObject(void);
robj *createHashObject(void);
robj *createZsetObject(void);
robj *createZsetZiplistObject(void);
int getLongFromObjectOrReply(client *c, robj *o, long *target, const char *msg);
int checkType(client *c, robj *o, int type);
int getLongLongFromObjectOrReply(client *c, robj *o, long long *target, const char *msg);
int getDoubleFromObjectOrReply(client *c, robj *o, double *target, const char *msg);
int getLongLongFromObject(robj *o, long long *target);
int getLongDoubleFromObject(robj *o, long double *target);
int getLongDoubleFromObjectOrReply(client *c, robj *o, long double *target, const char *msg);
char *strEncoding(int encoding);
int compareStringObjects(robj *a, robj *b);
int collateStringObjects(robj *a, robj *b);
int equalStringObjects(robj *a, robj *b);
unsigned long long estimateObjectIdleTime(robj *o);
#define sdsEncodedObject(objptr) (objptr->encoding == OBJ_ENCODING_RAW || objptr->encoding == OBJ_ENCODING_EMBSTR)

robj包括

  1. 数据类型
  2. 编码类型
  3. lru 信息
  4. 引用计数
  5. 数据指针
robj 中数据都是以 void * 的方式保存,获取之后转换成对应类型   
比如:    
int *integer_data = robj->ptr; 是获取一个整数指针  
char *str_data = robj->ptr; 获取一个字符串(字节数组)指针    
Person *struct_data = robj->ptr; 获取一个自定义数据结构指针  

robj 通过引用计数管理内存

void decrRefCount(robj *o);
void incrRefCount(robj *o);

当程序需要引用 object ,通过调用 incrRefCount 可以防止外部释放掉 object
在使用完之后调用 decrRefCount ;当引用计数递减到 1 decrRefCount 会触发 free 内存操作

SDS sample dynamic string

redis 中动态字符串数据结构
sds.c sds.h

sds 是非常常用的数据类型,包括每次从命令行接收的 args 也是通过 sds 包装后传给 command 回调函数的

void demoCmd(client *c)
{
    long long id;
    if (!string2ll(c->argv[1]->ptr, sdslen(c->argv[1]->ptr), &id)) {
        addReply(c, shared.err);
        return;
    }
    ...
}

sds 中包含了字符串常用的函数:

sds sdsnewlen(const void *init, size_t initlen);
sds sdsnew(const char *init);
sds sdsempty(void);
sds sdsdup(const sds s);
void sdsfree(sds s);
sds sdsgrowzero(sds s, size_t len);
sds sdscatlen(sds s, const void *t, size_t len);
sds sdscat(sds s, const char *t);
sds sdscatsds(sds s, const sds t);
sds sdscpylen(sds s, const char *t, size_t len);
sds sdscpy(sds s, const char *t);

sds sdscatfmt(sds s, char const *fmt, ...);
sds sdstrim(sds s, const char *cset);
void sdsrange(sds s, int start, int end);
void sdsupdatelen(sds s);
void sdsclear(sds s);
int sdscmp(const sds s1, const sds s2);
sds *sdssplitlen(const char *s, int len, const char *sep, int seplen, int *count);
void sdsfreesplitres(sds *tokens, int count);
void sdstolower(sds s);
void sdstoupper(sds s);
sds sdsfromlonglong(long long value);
sds sdscatrepr(sds s, const char *p, size_t len);
sds *sdssplitargs(const char *line, int *argc);
sds sdsmapchars(sds s, const char *from, const char *to, size_t setlen);
sds sdsjoin(char **argv, int argc, char *sep);
sds sdsjoinsds(sds *argv, int argc, const char *sep, size_t seplen);

/* Low level functions exposed to the user API */
sds sdsMakeRoomFor(sds s, size_t addlen);
void sdsIncrLen(sds s, int incr);
sds sdsRemoveFreeSpace(sds s);
size_t sdsAllocSize(sds s);
void *sdsAllocPtr(sds s);

/* Export the allocator used by SDS to the program using SDS.
 * Sometimes the program SDS is linked to, may use a different set of
 * allocators, but may want to allocate or free things that SDS will
 * respectively free or allocate. */
void *sds_malloc(size_t size);
void *sds_realloc(void *ptr, size_t size);
void sds_free(void *ptr);

sds 的信息存储在串开头的前面,根据不同的初始化长度,创建不同的sds头

sds sdsnewlen(const void *init, size_t initlen) {
    void *sh;
    sds s;
    // 通过初始长度获取 type 定义
    char type = sdsReqType(initlen); 
    /* Empty strings are usually created in order to append. Use type 8
     * since type 5 is not good at this. */
    if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
    int hdrlen = sdsHdrSize(type); // 通过 type 获取头结构体的大小
    unsigned char *fp; /* flags pointer. */

    // 初始化的内存:sds头+初始长度+1
    sh = s_malloc(hdrlen+initlen+1); 
    if (!init)
        memset(sh, 0, hdrlen+initlen+1);
    if (sh == NULL) return NULL;
    // s 是要返回的首地址,这个首地址是去掉头部的,所以我们在外部可以直接将 sds 当做 const char* 使用
    s = (char*)sh+hdrlen;  
    fp = ((unsigned char*)s)-1;
    // 根据不同的 sds type 编辑头部信息
    switch(type) {
        case SDS_TYPE_5: {
            *fp = type | (initlen << SDS_TYPE_BITS);
            break;
        }
        case SDS_TYPE_8: {
            SDS_HDR_VAR(8,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
        case SDS_TYPE_16: {
            SDS_HDR_VAR(16,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
        case SDS_TYPE_32: {
            SDS_HDR_VAR(32,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
        case SDS_TYPE_64: {
            SDS_HDR_VAR(64,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
    }
    if (initlen && init)
        memcpy(s, init, initlen);
    s[initlen] = '\0';
    return s;
}

释放 sds 内存需要使用 sdsfree 函数;注意,不是 sds_free 函数

/* Free an sds string. No operation is performed if 's' is NULL. */
void sdsfree(sds s) {
    if (s == NULL) return;
    // 释放的内存空间从 s 初始地址向前找到他的头部地址,再开始释放
    s_free((char*)s-sdsHdrSize(s[-1]));
}

util 中包含了 string2ll、string2l、ll2string、d2string 字符串和整数转换的函数

int ll2string(char *s, size_t len, long long value);
int string2ll(const char *s, size_t slen, long long *value);
int string2l(const char *s, size_t slen, long *value);
int d2string(char *buf, size_t len, double value);

哈希表

redis 中的直接查找都是使用这个哈希表,包括指令查找
源文件:dict.c dict.h

哈希存储流程:

  1. 通过hash 函数将数据分到 k 桶
  2. hash 值冲突的情况,将数据在 k 桶内按照链表存储
  3. 字符串哈希算法:MurmurHash2;大小写敏感字符串哈希算法:djb hash;32位整数哈希算法:Thomas Wang’s 32 bit Mix Function
  4. 长整数建议使用 dictGenHashFunction ,也就是 MurmurHash2 算法;将大整数转成字符串再进行哈希

hash 接口定义

typedef struct dictType {
    unsigned int (*hashFunction)(const void *key);
    void *(*keyDup)(void *privdata, const void *key);
    void *(*valDup)(void *privdata, const void *obj);
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);
    void (*keyDestructor)(void *privdata, void *key);
    void (*valDestructor)(void *privdata, void *obj);
} dictType;

hashFunction 哈希函数,决定k进入哪一个哈希桶
keyDup key 复制;NULL 为不复制,直接使用传入的key内存地址
valDup value 复制;NULL 为不复制,直接使用传入的 value 内存地址
keyCompare 哈希冲突下,查找数据的 key 比较函数
keyDestructor 当成员被从哈希表删除,在这里进行 key 内存销毁
valDestructor 当成员被从哈希表删除,在这里进行 value 内存销毁

哈希查找流程:

  1. 首先通过 hashFunction 计算出哈希 k 桶
  2. 通过 keyCompare 对 k 桶数据一次进行精确比较,并返回符合的值

阅读:125
搜索
  • Linux 高性能网络编程库 Libevent 简介和示例 2033
  • Mac系统编译PHP7【20190929更新】 1962
  • Windows 安装Swoole 1626
  • Hadoop 高可用集群搭建 (Hadoop HA) 1583
  • Hadoop 高可用YARN 配置 1516
  • 小白鼠问题 1435
  • Hadoop Map Reduce 案例:好友推荐 1364
  • 自动化测试工具 Selenium 1221
  • GIT 分支管理 1161
  • Php 迅搜中文分词 2 1070
简介
不定期分享软件开发经验,生活经验