开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 大数据 -> Redis进阶；底层数据结构实现 -> 正文阅读

[大数据]Redis进阶；底层数据结构实现

Redis进阶；底层数据结构实现

Redis K-V 底层设计原理

我们都知道redis单线程还这么快的原因是他是基于内存的；现如今内存的读取速度是极快的，ns级别的访问速度；仅次于cpu内部的多级缓存；

redis有哪些应用场景呢？

String底层数据结构

redis是使用C语言开发的，所以String底层肯定也是由C语言定义的；

c语言的string是一个char数组实现，但redis并没有直接采用这种实现方式，因为这种方式c在读取时是按照/0来截取数组的，因为在数组的最后c语言会加上/0来标记数组结束，但是redis面向的是各种语言的调用，所以它并不能直接使用这种结尾方式，

解决方式也不算难；那就是使用结构体存储，相当于Java中的对象之类的；无非就是解决字符截取的问题，那么直接定义一个长度表示元素在数组中的个数不就能解决了；所以

redis 3.2 以前
struct sdshdr {
    int len;//字符个数；
    int free;//剩余容量
    char buf[];//具体存放字符数据的数组，
};

但是这个做法又产生了新的问题，那就是结构体中的两个多余变量是int类型的啊，不也要占用空间；所以在3.2之后改成了如下：

redis 3.2 后

typedef char *sds;

struct __attribute__ ((__packed__)) sdshdr5 {//容量2的5次方；
    unsigned char flags; /*一个字节做标记位，其中3bit用来标记类型， 5bit标记字符串长度 */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used */已经使用的长度 
    uint8_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; /* used */
    uint16_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; /* used */
    uint32_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
...

根据不同长度字符串选择不同容量的结构体，非人性化

redis底层数据库设计

我们都知道redis底层有16个数据库；那么数据库是怎么定义的呢？其实也很容易想到，那就是和上面的string一样，是redis自己设计的一个结构体用来存储数据库中元素信息；也就是定义一个结构体，里面的属性指针指向不同的字典存放具体的数据

typedef struct redisDb {//db对象
    dict *dict;                //字典  
    dict *expires;          //过期时间管理
    dict *blocking_keys;          //阻塞队列
    dict *ready_keys;           
    dict *watched_keys;         
    int id;                      //数据库序号
    long long avg_ttl;           //查看过期时间
    unsigned long expires_cursor;  
    list *defrag_later;          
} redisDb;

解释一下 dict:其实就是存放键值对的一个结构体（对象）；在c++或Java中的体现是Map这种集合；

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; 
    unsigned long iterators;  
    } dict;

这里面主要看dictht这个结构体；它就是存放键值对的地方；至于具体是如何存放的；可以预想的是；redis既然这么快，存放数据当然是数组这种形式；redis采用的方式也很容易想到，就是数组+ 链表；采用hash算法获取索引；存放在数组中，发生hash冲突之后就采用头插法构成链表；这和Java中hashMap不谋而合；

typedef struct dictht {
    dictEntry **table;//指向具体的键值对table
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;


typedef struct dictEntry {
    void *key;   //键
    union {
        void *val; //值
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;//下一个
} dictEntry;

Redis的KEY：redis的可以都是string组成的，也就是开头说的sds结构体；

Redis的Value：Key统一都是string，但是redis有这么多中数据结构，他的值总当然也是由不同的数据结构构成！也就是val指针指向的是一个新的结构体；

typedef struct redisObject {
    unsigned type:4; //四个bit标记value类型 list set string hash
    unsigned encoding:4; //标记编码类型 raw int embstr 
    unsigned lru:LRU_BITS;  
    int refcount;
    void *ptr;
} robj;

List底层设计

List可以从两边添加元素，不难想到redis底层使用双端链表来实现的；

底层使用一种叫做ziplist来实现；

robj *createZiplistObject(void) {
    unsigned char *zl = ziplistNew();
    robj *o = createObject(OBJ_LIST,zl);
    o->encoding = OBJ_ENCODING_ZIPLIST;
    return o;
}

unsigned char *ziplistNew(void) {
    unsigned int bytes = ZIPLIST_HEADER_SIZE+ZIPLIST_END_SIZE;
    unsigned char *zl = zmalloc(bytes);
    ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);
    ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE);
    ZIPLIST_LENGTH(zl) = 0;
    zl[bytes-1] = ZIP_END;
    return zl;
}


robj *createObject(int type, void *ptr) {
    robj *o = zmalloc(sizeof(*o));
    o->type = type;
    o->encoding = OBJ_ENCODING_RAW;
    o->ptr = ptr;
    o->refcount = 1;
    if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
        o->lru = (LFUGetTimeInMinutes()<<8) | LFU_INIT_VAL;  
    } else {
        o->lru = LRU_CLOCK();   // 获取 24bit 当前时间秒数
    }
    return o;
}

这种结构在产生连锁更新时会出问题所以升级为quickList

详细地址

Hash底层设计

Hash其实也是字典来实现的，不过在数据量少的时候其实是使用ziplist来实现的；因为ziplist是一串连续空间，也就是数组，获取元素很快；当元素变大是就会改为hashtable;

hashtable也就是字典dict；不再赘述；

Set底层设计

set是一个集合，并且并不重复，那么可以思考一下redis会如何选择数据结构呢？集合存放用一个数组便可以完成，但是去重该如何实现呢？

其实set底层使用了一个value恒为null的hashtable ,这样便可以达到去重的效果；

但是其中还有一个小细节：如果set存储的全是整形时会采用intset这个数据结构；

intset优点：占用空间少，查询可以用二分，速度也很快；数据量大可以升级，直到64位也表示不了就会使用hashtable;

Zset底层设计

zset与set的区别就是zset有序并且有两个元素，设置分数；键为元素值为分数；根据分数排序；

既然要排序的话肯定是要用得链表；但是数据量大的时候元素的查找会变得很慢了；为了解决这种问题，redis采用了跳表这种数据结构；

具体设计图：

可以看到，一条跳表由一个个节点构成，每一个节点都有对应的层级属性构成，另外还有指向前结点和后节点的指针，方便元素的查找；

渐进式rehash及扩容机制

上面我们介绍了redis数据库中都是键值对存储元素数据的，键统一都是string，而value则指向一个对象redisObject,而redisobject又指向不同的数据结构：ziplist hash set之类的；另外还有一个指针指向数据存放的内存地址（sds）；

再看一下redis字典dict的定义：

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; 
    unsigned long iterators;  
    } dict;

其中指向的dictht是一个数组，长度为二，那么这个是干嘛的？

redis底层采用数组+ 链表+hash散列来存储元素，那就会出现一个问题；链表过长怎么办，元素过多怎么办？

所以中间需要有一个扩容机制，也就设计到了数据的转移，所以才会出现两个dictht，就是用来转移数据用得，第一次加入数据会加入ht[0],扩容后rehash到ht[1];

可是问题又出现了，redis是单线程的；转移那麽多数据肯定耗时耗力；难道在此期间就不管用户请求了嘛？当然不是的，为了处理这个问题，redis采用了一种渐进式rehash的做法，也就是说rehash并不是一次性完成的，二是分批次完成；隔一段时间就rehash;

那再扩容期间有数据插入或查询怎么办？
- 插入：之间插入到扩容的新数组，
- 查询：两个数组都会查一遍；
如何扩容以及扩容判断条件

源码如下

/*
     * 如果哈希表ht[0]中保存的key个数与哈希表大小的比例已经达到1:1，即保存的节点数已经大于哈希表大小
     * 且redis服务当前允许执行rehash，或者保存的节点数与哈希表大小的比例超过了安全阈值（默认值为5）
     * 则将哈希表大小扩容为原来的两倍
     */
    if (d->ht[0].used >= d->ht[0].size &&
        (dict_can_resize ||
         d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))
    {
        return dictExpand(d, d->ht[0].used*2);
    }