阅读 73

redis总结--数据结构

一、redis中数据对象

redis有五大数据类型, 通过统一对象redisObject存储, redisObject的结构主要包含以下部分:

  • type属性存储对象的类型, 也就是string, list, hash, set, zset中的一种。可以通过type命令查看。
  • encoding属性记录对象的所使用的编码,即底层数据结构。
  • ptr 指向底层数据结构的指针。
1 typedef struct redisObject {
2     // 类型
3     unsigned type:4;
4     // 编码
5     unsigned encoding:4;
6     // 指向底层实现数据结构的指针
7     void *ptr;
8     // ...
9 } robj;
复制代码

redis为每种数据类型,提供了两种以上的底层数据结构实现,可以通过type和object encoding这两个命令查看数据对象的类型和数据结构。

127.0.0.1:6379> set key1 100
OK
127.0.0.1:6379> type key1
string
127.0.0.1:6379> object encoding key1
"int"
127.0.0.1:6379> set key2 'abc'
OK
127.0.0.1:6379> type key2
string
127.0.0.1:6379> object encoding key2
"embstr"
复制代码

二、不同数据类型对应的底层数据结构

1. 字符串
  • int:8个字节的长整型。
  • embstr:小于等于39个字节的字符串。
  • raw:大于39个字节的字符串。 Redis会根据当前值的类型和长度决定使用哪种内部编码实现。
2. 哈希
  • ziplist(压缩列表):当哈希类型元素个数小于hash-max-ziplist-entries 配置(默认512个)、同时所有值都小于hash-max-ziplist-value配置(默认64 字节)时,Redis会 使用ziplist作为哈希的内部实现,ziplist使用更加紧凑的 结构实现多个元素的连续存储,所以在节省内存方面比hashtable更加优秀。
  • hashtable(哈希表):当哈希类型无法满足ziplist的条件时,Redis会使 用hashtable作为哈希的内部实现,因为此时ziplist的读写效率会下降, 而 hashtable的读写时间复杂度为O(1)。
3. 列表
  • ziplist(压缩列表):当列表的元素个数小于list-max-ziplist-entries配置 (默认512个),同时列表中每个元素的值都小于list-max-ziplist-value配置时 (默认64字节), Redis会选用ziplist来作为列表的内部实现来减少内存的使 用。
  • linkedlist(链表):当列表类型无法满足ziplist的条件时,Redis会使用 linkedlist作为列表的内部实现。
  • quicklist ziplist和linkedlist的结合, 以ziplist为节点的链表(linkedlist)
4. 集合
  • intset(整数集合):当集合中的元素都是整数且元素个数小于set-max- intset-entries配置(默认512个)时,Redis会选用intset来作为集合的内部实 现,从而减少内存的使用。
  • hashtable(哈希表):当集合类型无法满足intset的条件时,Redis会使 用hashtable作为集合的内部实现。
5. 有序集合
  • ziplist(压缩列表):当有序集合的元素个数小于zset-max-ziplist- entries配置(默认128个),同时每个元素的值都小于zset-max-ziplist-value配 置(默认64字节)时, Redis会用ziplist来作为有序集合的内部实现,ziplist 可以有效减少内存的使用。
  • skiplist(跳跃表):当ziplist条件不满足时,有序集合会使用skiplist作 为内部实现,因为此时ziplist的读写效率会下降。

三、数据结构实现

1. int

int保存的是long类型的整数,8个字节长整型,直接保存在redisObject对象的ptr属性中。

2. embstr

embstr保存小于等于39个字节的字符串,使用动态字符串(SDS)实现。直接保存在redisObject对象的ptr属性中,只需要分配一次内存, 即创建redisObject对象。

3. raw

raw保存大于39个字节的字符串,使用动态字符串(SDS)实现,需要单独分配内存给sdshdr(SDS)结构。

注意: 在redis 3.2之后,embstr和raw改为以44字节为分界线

SDS redis没有采用c的字符串结构,而是构建了动态字符串的数据结构,先来看看结构源码:

struct sdshdr{
     //记录buf数组中已使用字节的数量
     //等于 SDS 保存字符串的长度
     int len;
     //记录 buf 数组中未使用字节的数量
     int free;
     //字节数组,用于保存字符串,最后一个位置存储的是空字符'\0', 不计入len
     char buf[];
}
复制代码

SDS的优化:

  • 空间预分配,不用担心字符串变更造成的内存溢出。
    • 如果空间够用,则不会额外分配空间, 通过free属性。
    • 如果修改后的 SDS 长度 len 小于 1MB,那么程序分配和 len 属性相等的未使用空间,此时 free 和 len 的值相同。所以此时数组的实际长度为 free + len + 1byte(额外的空字符 1 个字节)。
    • 如果修改后的 SDS 长度大于 1MB,那么程序分配 1MB 的未使用空间。实际长度为 len + 1MB + 1byte。
  • 惰性空间释放,字符串缩短,并不是立即重新分配内存,释放空间。
  • 常数时间复杂度读取字符串长度, 通过len属性
  • 二进制安全, c语言中空字符意味着字符串结束,SDS则不需要考虑,通过len判断是否结束。

分界线39或44的来源

  • Redis中内存分配使用的是 jemalloc,jemalloc 分配内存的时候是按照 8、16、32、64 作为 chunk 的单位进行分配的。
  • 为了保证采用embstr编码方式的字符串能被 jemalloc 分配在同一个 chunk 中,整个redisObject不超过64
  • 因此OBJ_ENCODING_EMBSTR_SIZE_LIMIT = 64 - 16(redisObject) - 4(sdshdr的len属性) - 4(sdshdr的free属性) - 1(sdshdr的buf最后一位'\0') = 39。
  • len和size之前使用unsign int,占4个字节,调整为调整为unit8_t, 占1个字节。并追加了一个char flag 1个字节。
4. ziplist

压缩列表是 Redis 为了节约内存而实现的,是一系列特殊编码的连续内存块组成的顺序型数据结构。 结构如下图:

  • zlbytes 4字节,记录整个压缩列表占用的内存字节数。
  • zltail 4字节,记录压缩列表表尾节点的位置。
  • zllen 2字节,记录压缩列表节点个数。超过需要65535遍历。
  • entry 列表节点,长度不定,由内容决定。
  • zlend 1字节,0xFF 标记压缩的结束。 压缩列表的节点结构如下图:
  • privious_entry_length占四个字节,取决于前一个节点的长度,小于254字节,就是占1个字节,否则就是5个字节。
  • enncoding 记录节点的content保存数据的类型和长度。

压缩列表的遍历: 通过指向表尾节点的位置指针p1, 减去节点的previous_entry_length,得到前一个节点起始地址的指针。如此循环,从表尾遍历到表头节点。

5. linkedlist

双向链表结构,表头节点的前置节点和表尾节点的后置节点都是NULL,是无环链表。链表结构源码如下:

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

一个由ziplist组成的双向链表(ziplist和linklist结合),即链表的每个节点都是ziplist;redis3.2新增的数据结构,用于列表的实现。quicklist结构源码:

typedef struct quicklist {
    // 指向头部quicklist节点的指针
    quicklistNode *head;
    //  指向尾部quicklist节点的指针
    quicklistNode *tail;
    // quicklist中所有ziplist中的entry节点数量。
    unsigned long count;
    // quicklist的链表节点数量
    unsigned int len; 
    // 保存ziplist的大小,配置文件设定,占16bits
    int fill : 16;        
    // 保存压缩程度值,配置文件设定,占16bits,0表示不压缩
    unsigned int compress : 16; 
} quicklist;
复制代码
7. intset

当一个集合中只有整数元素,就会使用intset结构。结构源码:

typedef struct intset {
    // 编码方式
    uint32_t encoding;
    // 集合包含的元素数量
    uint32_t length;
    // 保存元素的数组
    int8_t contents[];
} intset;
复制代码
  • encoding有三种属性值:INTSET_ENC_INT16,INTSET_ENC_INT32, INTSET_ENC_INT64, 分别表示用int16_t, int32_t, int64_tL类型的数组,进行数据存储。 当元素大小超过时,会进行升级。(不支持降级)
8. hashtable

redis的hash表,采用链地址法解决冲突。 哈希表结构:

typedef struct dict {
    // 类型特定函数
    dictType *type;
    // 私有数据
    void *privdata;
    // 哈希表
    dictht ht[2];
    // rehash 索引
    // 当 rehash 不在进行时,值为 -1
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */
} dict;
复制代码

其中dictht ht[0]为正常情况下使用,ht[1]为rehash过程使用。

typedef struct dictht {
    // 哈希表数组
    dictEntry **table;
    // 哈希表大小
    unsigned long size;
    // 哈希表大小掩码,用于计算索引值, 总是等于 size - 1
    unsigned long sizemask;
    // 该哈希表已有节点的数量
    unsigned long used;
} dictht;
复制代码

hash节点结构:

typedef struct dictEntry {
    // 键
    void *key;
    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    // 指向下个哈希表节点,形成链表
    struct dictEntry *next;  // 单链表结构
} dictEntry;
复制代码
  • redis的hash节点采用单链表结构,哈希表没有使用红黑树,对哈希节点进行优化。 ps: 在hash冲突严重时,大量hashcode落到同一个hash节点上,此时hash表退化成单链表。 在JDK1.8中采用HashTable对进行优化,当链表数量超过8时,使用红黑树替代链表。

  • rehash 由负载因子决定什么时候进行rehash。过程如下:

  1. 为ht[1]分配空间,大小为比当前ht[0]已使用值的两倍大的第一个2的整数幂。如,已使用空间7,则分配比7*2大的最近的2的整数幂,即16。
  2. 将ht[0]中所有键值对,rehash到ht[1]上。
  3. 完成迁移后,释放ht[0], 将ht[1]设置为ht[0], 在ht[1]处新建空白哈希表,为下一次rehash做准备。
  • 渐进式rehash 当键值对数量巨大,一次性全部rehash将造成阻塞,服务暂停。所以拆分成多次,慢慢的将ht[0]中的数据rehash到ht[1]中。过程如下:
  1. 为ht[1]分配空间,同时持有两个哈希表(一个空表、一个有数据)。
  2. 维持计数器rehashidx,初始值为0,表示rehash开始。
  3. 每次增删改查,都顺带将ht[0]中的数据迁移到ht[1], rehashidx++.
  4. 直到rehash完成,rehashidx设置为-1。 渐进式hash中,更新、删除、查找都会在两个hash表上进行。新增操作只在ht[1]上进行,保证ht[0]只减不增,直到成为空表。 (假如ht[0]有冷门数据一直不被操作,ht[0]一直没有清空,ht[1]触发新的rehash阈值怎么办?)
9. skiplist跳跃表

跳跃表的结构如下:

typedef struct zskiplist {
    // 表头节点和表尾节点
    struct zskiplistNode *header, *tail;
    // 跳表节点的数量
    unsigned long length;
    // 跳表层数
    int level;
} zskiplist;
复制代码

节点结构如下:

typedef struct zskiplistNode {
    // 后退指针
    struct zskiplistNode *backward;
    // 分数值
    double score;
    // 成员对象
    robj *obj;
    // 层
    struct zskiplistLevel {
        // 前进指针
        struct zskiplistNode *forward;
        // 跨度,记录两个节点间的距离
        unsigned int span;
    } level[];
} zskiplistNode;
复制代码
  • skiplist是一种以空间换取时间的结构。由于链表,无法进行二分查找,因此借鉴数据库索引的思想,提取出链表中关键节点(索引),先在关键节点上查找,再进入下层链表查找。提取多层关键节点,就形成了跳跃表。
  • 跳跃表在es的lucene索引也有有应用。

为什么用跳跃表不用平衡树

  1. skiplist算法实现简单得多。
  2. 跳跃表和平衡树的插入删除时间复杂度都是O(logn),不过平衡树的插入和删除操作引发树结构的调整,操作复杂。skiplist只需要修改相邻节点的指针,操作简单。
  3. 查询单个key,跳跃表和平衡树的时间复杂度都是O(logn),大体相当。
  4. 范围查找,平衡树要复杂,skiplist适合zset各种操作。
关注下面的标签,发现更多相似文章
评论