Redis-源码理解

Posted on | Edited on | In

RedisObject

所有的Redis对象都有如下的头信息

1
2
3
4
5
6
7
struct ReidsObject{
    int4 type; //类型 4bit
    int4 encoding; //编码方式 4bit
    int24 lru; //lru时间戳 24bit
    int32 refcount; //引用计数如果为0回收 4byte
    void *ptr; //指针 8byte
}robj

每一中RedisObject的数据类型对应一个type,但是根据情况可能对应多个encoding

字符串的原理

Redis的字符串叫SDS格式如下

1
2
3
4
5
6
7

struct SDS<T>{
    T capacity; //容量 1byte
    T len; //实际长度 1byte
    byte flags; //特殊标志位 1byte
    byte[] content; //数组长度
}

redis的字符串支持修改，为了减少修改的成本会预先申请capacity个长度的byte数组，当数组写入字符串的时候根据len定位。好处如下：

  • 当发生追加等操作时候不需要申请新的数组，copy原数组
  • 获取字符串长度时候只需要访问len变量即可，不需要遍历数组

  • len和capacity使用泛型T可以针对长度将变量设置为byte short。对对象用到了极致

    redis的字符串在小于44字节的时候encoding是embstr,大于44字节的encoding是raw。如果字符串是embstr，分配内存往往RedisObject和SDS是紧挨着的；如果是raw内存是不连续的；为什么是44个字节，原理如下：

  • 为什么是44个字节
    • SDS除content最少占用ReidsObject占16byte+SDS的3byte(假设这时候content为空)=19byte
    • 由于redis的内存管理工具分配方式是8/16/32/64，由于头文件占据了19空间，所以至少分配32字节。当content+redisObj需要分配64字节,那么content最多存储45字节，减去最后的空字符NULL，剩余44字节。
  • 超过这个阈值Redis会认为对象是个大字符串适合用raw去存

dict

Redis的hash结构，所有的key-value是一个全局的dict，以及设置了expire的key-value，另外zset的value–score的对应关系也是通过字典结构。

1
2
3
4
5
6
7
8
9
struct RedisDb{
dict* dict;
dict* expires;
}

struct zset{
    dict *dict   // value=>score
    zskiplist *zsl
}

dict采用的rehash策略是渐进式的rehash,防止hash过大rehash影响主流程。采用的hash算法是siphash

扩容：当元素等于dict数组长度时候会扩容，扩容为原来的2倍，如果遇到bgsave尽量不会去扩容，但是如果当元素打到dict数组的5倍会进行强制扩容
缩容：当元素低于dict数组长度10%会缩容。缩容不会考虑bgsave。

ziplist

1
2
3
4
5
6
7
8
9
10
11
12
13
struct ziplist<T>{
int32  zlbytes; //压缩表占用自己数
int32  zltail_offset; //最后一位偏移量用于到这遍历
int16 length; //长度
T[] entries; //元素列表
int8 zlend;  //压缩列表的结束标记，值：0xFF
}

srtuct entry{
    int<var> prevlen; //前一个长度
    int<var> encoding; //元素类型编码 小于254时候一个字节，大于254时候5个字节第一个自己是254（0xFE）
    optional byte[] contennt
}

intset

当集合set是整数且个数较小时候会考虑使用intset

1
2
3
4
5
struct intset<T>{
    int32 encoding;
    int32 length;
    int<T> content;
}

quicklist

list采用这种数据结构是ziplist和linkedlist的整合，将linkedlist按照ziplist分段，时内存更紧凑，每一段在用链表链接起来。

skiplist

zset采用这种方式，优点：快速定位.它的层数是2的64次方。
zset的rank的排名是通过zslforward的span对象计算出来的每次插入的时候都会维护这个值，表示当前层到这个节点跳过了多少节点