您好,欢迎访问代理记账网站
移动应用 微信公众号 联系我们

咨询热线 -

电话 15988168888

联系客服
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

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.2typedef 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);
    }

既然有扩容当然也有缩容:

条件: 当哈希表保存的key数量与哈希表的大小的比例小于10%时需要缩容。最小容量为4


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进