signed

QiShunwang

“诚信为本、客户至上”

redis源码

2021/6/3 15:19:34   来源:
字符串
  • redis的字符串结构是SDS,是一个自带长度信息的字节数组

    struct SDS<T> {
        T capacity;     //数组容量	1byte
        T len;			//数组长度	1byte
        byte flags;		//特殊标志位	1byte
        byte[] content; //数组内容
    }
    
  • SDS使用的泛型T,是为了根据属性的大小来判断使用什么类型,redis对内存做了极致的优化。

  • 字符串长度不得超过512M

embstr与raw
  • redis的字符串有两种存储方式,当长度特别短时是embstr,当长度超过44字节是使用的是raw

  • redis的对象头结构占据16个字节,分别是4bit的type,4bit的存储形式,24bit的LRU信息,4bytes的引用计数,8bytes的指针,指向具体的存储位置。

    struct RedisObject {
        int4 type;			//4bits
        int4 encoding;		//4bits
        int24 lru;			//24bits
        int32 refcount;		//4bytes
        void *ptr			//8bytes
    }
    
  • redis的SDS对象头结构是至少3字节,再加上SDS的content是以NULL结尾的字符串,所以一共20个字节。

  • 当字符串的长度超过44字节时,总长度就会超过64字节,而内存分配器jemalloc的最大分配单位是64字节,当大于64字节,就会使用raw进行存储。

字典
字典内部结构
  • 字典结构内部包含两个hashtable,通常只有一个hashtable有值,当进行字典扩容或者缩容时,需要分配新的hashtable,然后进行渐进式搬迁,这时候两个分别存着旧的hashtable与新的hashtable。
  • hashtable的结构与HashMap一样,都是使用分桶的方式解决hash冲突,第一维是数组,第二维是链表。
渐进式rehash
  • 大字典的扩容是很耗时间的,这是一个O(n)的操作,redis很难承受这样的消耗,所以进行渐进式小步搬迁。·搬迁操作埋伏在当前的操作指令中,还有定时的任务进行触发主动搬迁。
查找过程
  • 将key值通过hash函数映射成一个整数,然后在hash表中查找该key的值。
hash函数
  • redis的hash函数是siphash,对即使很小的key也可以产生随机性很好的输出。
扩容条件
  • 正常情况下,当hash表中的元素个数等于第一维数组的大小时就会开始扩容,扩容的数组大小是之前的2倍,如果redis正在进行bgsave(快照),会暂时避免进行扩容。但如果元素个数特别多(5倍),会强制扩容。
缩容条件
  • 当hash表因为删除变得稀疏时,会进行缩容,条件是10%。
set
  • set的的底层实现也是字典,不过他的value都是null。
压缩列表
  • redis为了节约内存空间,在set与hash容器对象元素个数较少时,会使用压缩列表,压缩列表是一块连续的存储空间,非常紧凑,没有冗余空隙。
struct ziplist<T> {
    int32 zlbytes;			//整个压缩列表占用字节数
    int32 zltail_offset;	//最后一个元素距离起始位置的偏移量,用于快速定位最后一个节点
    int16 zllength;			//元素个数
    T[] entries;			//元素内容
    int8 zlend;				//标志压缩列表的结束,值恒定为0xFF
}
  • 压缩列表支持双向遍历,所以才会有zltail_offset。
  • entry也会根据存储内容的不同,又不一样的结构。
struct entry {
    int<var> prevlen;
    int<var> encoding;
    optional byte[] content;
}
  • prevlen表示前一个entry的长度,他是一个变长的整数,当字符串长度小于254时,使用一个字段来表示,当大于254时,使用5个字段来表示。
  • encoding字段存储了元素内容的编码类型信息,是很复杂,详见P191.
增加元素
  • ziplist是紧凑存储,所以当增加元素时,需要调用realloc扩展内存,取决于当前的分配器算法与ziplist内存大小,
  • ziplist不适合存储大型字符串,存储元素不宜过多。
级联更新
  • 如果ziplist每个元素都存储了253个字节,然后修改第一个元素,就会导致后面的所有元素都进行级联更新。
intset整数集合

当set容纳的元素是整数而且个数比较少时,redis会使用ineset进行存储,intset是紧凑的整数数组结构,同时支持16位、32位、64位的整数。

struct intset<T> {
    int32 encoding;
    int32 length;
    int<T> contents;
}
快速列表
  • quicklist是ziplist与linkedlist的结合体,将linkedlist按段切分,每一段使用ziplist,ziplist之前使用双向指针串联起来。
  • redis还会对ziplist进行压缩存储,LZF算法,可以选择压缩深度,默认是0,也就是不压缩,设置为1之后,quicklist首尾两个ziplist不压缩。
  • quicklist默认每个ziplist长度为8KB,超过这个字节数就新起一个ziplist。
跳跃列表

zset的内部实现就是一个hash字典加一个跳跃列表。

跳跃列表内部结构

kv之间用双向指针连起来,,有序排列,从小到大,同一层的kv使用指针串起来。

查找过程

从最高层查找最后一个比我小的节点,然后下一层继续寻找最后一个比我小的节点,一直到最底层找到对应元素,这个路径叫做搜索路径,算法复杂度是O(lg(n)).

随机层数

新插入一个元素时,调用随机算法分配一个合理的层数。插入成功后重排下前后指针。

更新过程

redis是采用先删除在插入的操作来完成更新操作的。