redis 数据结构

String

数据结构

 struct sdshdr {
   int len;//记录buf数组中已使用字节的数量等于SDS所保存字符串的长度
   int alloc;//记录对象分配的内存空间
   char flag;//记录字符串类型。
   char buf[];//字节数组，用于保存字符串
}

示例

string示例.png

这里就可以存储"Redis C",而C只能读取Redis字符串

对C字符串和SDS之间的区别进行总结

C字符串	SDS
获取字符串长度的复杂度为O(N)	获取字符串长度的复杂度为O(1)
API是不安全的，可能会造成缓存区溢出	API是安全的，不会造成缓存区溢出
修改字符串长度N次必然需要执行N次内存重分配	修改字符串长度N次最多需要执行N次内存重分配
只能保存文本数据	可以保存文件或则二进制数据
可以使用所有<string.h>库中的函数	可以使用一部分<string.h>库中的函数

链表

数据结构

typedef struct listNode {
    struct listNode *prev; //前置节点
    struct listNode *next; //后置节点
    void *value; //节点的值
} listNode;

typedef struct listIter {
    listNode *next;
    int direction;
} listIter;

typedef struct list {
    listNode *head; //表头节点
    listNode *tail; //表尾节点
    void *(*dup)(void *ptr); //节点值复制函数
    void (*free)(void *ptr); //节点值释放函数
    int (*match)(void *ptr, void *key); //节点值对比函数
    unsigned long len;
} list;

示例

image.png

链表的特点

• 链表呗广泛用于实现Redis的个钟功能，比如列表键，发布与订阅、慢查询、监视器等。
• Redis的链表是双向无环链表。
• listIter的结构是为了遍历list使用的。与java Iterator类似
• list定义的三个函数是为了抽象node的value使用。value的类型不同，三个函数的内容也不同，类似于JAVA的抽象方法。

MAP

数据结构

typedef struct dictEntry {
    void *key;  //键
    union {  //值
        void *val;  //字符串或别的值
        uint64_t u64;  //无符号数字
        int64_t s64;  //有符号数字
        double d; //浮点
    } v;
    struct dictEntry *next;  //指向下个哈希表节点,形成链表
} dictEntry;
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索引,当rehash不在进行时,值为-1
    unsigned long iterators;  //当前iterators遍历的数量
} dict;

结构示例

image.png

map特色

• rehash

1. 为字典的ht[1]哈希表分配空间,,这个哈希表的空间大小取决于要执行的操作,以及ht[0]当前包含的键值对数量(也即使ht[0].used属性的值):

*  如果执行的是扩展操作,那么ht[1]的大小为第一个大于等于ht[0].used*2的2的n次方幂;
*  如果执行的是收缩操作,那么ht[1]的大小为第一个大于等于ht[0].used的2的n次幂.

2. 将保存在ht[0]中的所有键值对rehash到ht[1]上面;
   3.当ht[0]包含的所有键值对都迁移到ht[1]之后(ht[0]变为空表),释放ht[0],将ht[1]设置为ht[0],并在ht[1]新创建一个空白哈希表,为下一次rehash做准备.

• rehash的扩展与收缩条件

1. 服务器当前没有执行BGSAVE命令或者BGREWRITEAOF命令,并且哈希表的负载因子大于等于1.
2. 服务器目前正在执行BGSAVE命令或者BGREWRITEAOF命令,并且哈希表负载因子大于等于5.
3. 哈希表的负载因子小于0.1时,程序自动开始对哈希表执行收缩操作.
   负载因子公式: load_factor = ht[0].used / ht[0].size;
   java-hashMap负载因子为0.75 转换为redis的负载因子为 0.75;

• 渐进式rehash
  如果 ht[0] 里只保存着四个键值对， 那么服务器可以在瞬间就将这些键值对全部 rehash 到 ht[1] ； 但是， 如果哈希表里保存的键值对数量不是四个， 而是四百万、四千万甚至四亿个键值对， 那么要一次性将这些键值对全部 rehash 到 ht[1] 的话， 庞大的计算量可能会导致服务器在一段时间内停止服务。
  因此， 为了避免 rehash 对服务器性能造成影响， 服务器不是一次性将 ht[0] 里面的所有键值对全部 rehash 到 ht[1] ， 而是分多次、渐进式地将 ht[0] 里面的键值对慢慢地 rehash 到 ht[1] 。
  以下是哈希表渐进式 rehash 的详细步骤：

1. 为 ht[1] 分配空间， 让字典同时持有 ht[0] 和 ht[1] 两个哈希表。
   在字典中维持一个索引计数器变量 rehashidx ， 并将它的值设置为 0 ， 表示 rehash 工作正式开始。
2. 在 rehash 进行期间，ht[0]只会执行删除'查找,对字典执行添加只会作用于ht[1] ， 当 rehash 工作完成之后， 程序将 rehashidx 属性的值增一。
3. 随着字典操作的不断执行， 最终在某个时间点上， ht[0] 的所有键值对都会被 rehash 至 ht[1] ， 这时程序将 rehashidx 属性的值设为 -1， 表示 rehash 操作已完成。

代码示例

//新增替换的时候调用该方法
  dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing)
{
    long index;
    dictEntry *entry;
    dictht *ht;
    //如果当前正在rehash,则调用一步rehash,转移一个table数组
    if (dictIsRehashing(d)) _dictRehashStep(d);

    /* Get the index of the new element, or -1 if
     * the element already exists. (查找key,如果存在返回-1)*/
    if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1)
        return NULL;

    /* Allocate the memory and store the new entry.
     * Insert the element in top, with the assumption that in a database
     * system it is more likely that recently added entries are accessed
     * more frequently. (分配内存,rehash时插入到ht[1]上面)*/
    ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
    entry = zmalloc(sizeof(*entry));
    entry->next = ht->table[index];
    ht->table[index] = entry;
    ht->used++;

    /* Set the hash entry fields. (设置key值)*/
    dictSetKey(d, entry, key);
    return entry;
}

跳跃表

数据结构

typedef struct zskiplistNode {
    sds ele;  //对象
    double score;  //分值
    struct zskiplistNode *backward;  //后退指针
    struct zskiplistLevel {  //层
        struct zskiplistNode *forward;  //前进指针
        unsigned long span;  //跨度
    } level[];
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;//头尾节点
    unsigned long length; //list长度
    int level; //表中层数最大的节点层数
} zskiplist;

示例

跳表结构示例
如果不懂跳表的数据结构可以阅读一下:http://zhangtielei.com/posts/blog-redis-skiplist.html

跳表特色

1. 跳跃表示有序集合的底层实现之一
2. Redis的跳跃表实现由zskiplist和zskiplistNode两个结构组成,其中zskiplist用于保存跳跃表信息,而zskiplistNode则用于标示跳跃表节点.
   3.每个跳跃表节点的层高都是1至64之间的随机数.
   4.在同一个跳跃表中,多个节点可以包含相同的分值,但每个节点的成员对象可以相同(<<redis设计与实现>>说对象唯一,是因为跳跃表永远都是和dict一起使用,所以已经过滤掉了重复对象)
   代码:

//插入代码
zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {
    zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
    unsigned int rank[ZSKIPLIST_MAXLEVEL];
    int i, level;
    //校验数据
    serverAssert(!isnan(score));
    x = zsl->header;
    for (i = zsl->level-1; i >= 0; i--) {
        /* store rank that is crossed to reach the insert position(查询插入位置) */
        rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];
        while (x->level[i].forward &&
                (x->level[i].forward->score < score ||
                    (x->level[i].forward->score == score &&
                    sdscmp(x->level[i].forward->ele,ele) < 0)))//因为level[0]是前指针,所以在遍历i=0时是往前遍历,找到插入的前一个指针
        {
            rank[i] += x->level[i].span;
            x = x->level[i].forward;
        }
        update[i] = x;
    }
 
    level = zslRandomLevel();//获取随机level
    ...省略算法代码

    x->backward = (update[0] == zsl->header) ? NULL : update[0];
    if (x->level[0].forward)  //level[0]就是backward一样
        x->level[0].forward->backward = x;
    else
        zsl->tail = x;
    zsl->length++;
    return x;
}

5. 跳跃表中的节点按照分值大小进行排序,当分值相同时,节点按照成员对象大小进行排序.

整数集合

数据结构

typedef struct intset {
    uint32_t encoding;  //编码方式INT16,INT32,INT64
    uint32_t length;  //数量
    int8_t contents[];  //保存元素的数组
} intset;

示例

image.png
image.png

整数列表特色

1. 整数集合是集合键的底层实现之一
2. 不同的编码是为了节约内存,数字小的时候会用INT16的方式
3. 整数集合只支持升级操作,不支持降级操作
4. 数组以有序,无重复的方式保存集合
   代码示例:

//插入代码
intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {
    uint8_t valenc = _intsetValueEncoding(value);
    uint32_t pos;
    if (success) *success = 1;


    if (valenc > intrev32ifbe(is->encoding)) {
        //升级编码长度
        return intsetUpgradeAndAdd(is,value);
    } else {
        //查询value是否存在返回1,不存在返回0 pos返回前一个位置
        if (intsetSearch(is,value,&pos)) {
            if (success) *success = 0;
            return is;
        }

        is = intsetResize(is,intrev32ifbe(is->length)+1);//扩容,删除也会清空内存
        if (pos < intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+1);//不是最后一个移动位置
    }

    _intsetSet(is,pos,value);//设置值
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    return is;
}

压缩列表

数据结构

压缩列表没有数据结构,只有一个大的内存快,通过内存地址计算各个属性
组成部分视图:

代码实现:

#define ZIPLIST_HEADER_SIZE     (sizeof(uint32_t)*2+sizeof(uint16_t))//定义ziplist头部分
#define ZIPLIST_BYTES(zl)       (*((uint32_t*)(zl))) //记录zip的大小
#define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t)))) //记录zip尾节点距离压缩列表起始地址有多少字节,定位尾节点地址
#define ZIPLIST_LENGTH(zl)      (*((uint16_t*)((zl)+sizeof(uint32_t)*2)))//节点的长度

entry的数据结构:

typedef struct zlentry {
    unsigned int prevrawlensize; //记录了前一个节点的长度，通过这个值，可以进行指针计算，从而跳转到上一个节点。
    unsigned int prevrawlen;     // 前一个entry长度
    unsigned int lensize;        // entry的字节大小
    unsigned int len;           
    unsigned int headersize;     /* prevrawlensize + lensize. */
    unsigned char encoding;      //节点类型可能是整数或者字符串
    unsigned char *p;            /* Pointer to the very start of the entry, that
                                    is, this points to prev-entry-len field. */
} zlentry;