美文网首页
redis数据结构总结

redis数据结构总结

作者: 知止9528 | 来源:发表于2019-01-16 00:24 被阅读3次
    redis数据结构.png

    string

    redis的字符串是动态字符串,内部结构实现类似于java的arraylist

    其次,redis采用了预分配冗余空间的方式来减少内存的频繁分配,比如我实际需要8k,它会给我分配20k

    当字符串长度小于1M时,扩容都是加倍现有的空间,超过1M时,扩容时一次只会多扩1M.

    字符串的最大长度是512M

    string的数据结构(Simple Dynamic String)

    struct SDS<T> {
      T capacity; // 数组容量
      T len; // 数组长度
      byte flags; // 特殊标识位,不理睬它
      byte[] content; // 数组内容
    }
    

    它的结构是一个带长度信息的字节数组。

    image.png

    这样设计的原理

    content 里面存储了真正的字符串内容,capacity 表示所分配数组的长度,len 表示字符串的实际长度。字符串是可以修改的字符串,它要支持 append 操作。如果数组没有冗余空间,那么追加操作必然涉及到分配新数组,然后将旧内容复制过来,再 append 新内容。如果字符串的长度非常长,这样的内存分配和复制开销就会非常大。

    SDS的数据结构使用了范型 T,为什么不直接用 int 呢,这是因为当字符串比较短时,len 和 capacity 可以使用 byte 和 short 来表示,Redis 为了对内存做极致的优化,不同长度的字符串使用不同的结构体来表示。

    接下来就是string的两种存储方式

    embstr vs raw

    Redis 的字符串有两种存储方式,在长度特别短时,使用 emb 形式存储 (embeded),当长度超过 44 时,使用 raw 形式存储。

    关于为什么是44

    首先来了解一下 Redis 对象头结构体,所有的 Redis 对象都有下面的这个结构头:

    struct RedisObject {
        int4 type; // 4bits
        int4 encoding; // 4bits
        int24 lru; // 24bits
        int32 refcount; // 4bytes
        void *ptr; // 8bytes,64-bit system
    } robj;
    

    不同的对象具有不同的类型 type(4bit),同一个类型的 type 会有不同的存储形式 encoding(4bit),为了记录对象的 LRU 信息,使用了 24 个 bit 来记录 LRU 信息。每个对象都有个引用计数,当引用计数为零时,对象就会被销毁,内存被回收。ptr 指针将指向对象内容 (body) 的具体存储位置。这样一个 RedisObject 对象头需要占据 16 字节的存储空间。

    其次再看

    SDS 结构体的大小,在字符串比较小时,SDS 对象头的大小是capacity+3,至少是 3。意味着分配一个字符串的最小空间占用为 19 字节 (16+3)。

    struct SDS {
        int8 capacity; // 1byte
        int8 len; // 1byte
        int8 flags; // 1byte
        byte[] content; // 内联数组,长度为 capacity
    }
    
    image.png

    embstr 存储形式是这样一种存储形式,它将 RedisObject 对象头和 SDS 对象连续存在一起,使用 malloc 方法一次分配。而 raw 存储形式不一样,它需要两次 malloc,两个对象头在内存地址上一般是不连续的。

    而内存分配器 jemalloc/tcmalloc 等分配内存大小的单位都是 2、4、8、16、32、64 等等,为了能容纳一个完整的 embstr 对象,jemalloc 最少会分配 32 字节的空间,如果字符串再稍微长一点,那就是 64 字节的空间。如果总体超出了 64 字节,Redis 认为它是一个大字符串,不再使用 emdstr 形式存储,而该用 raw 形式。
    SDS 结构体中的 content 中的字符串是以字节\0结尾的字符串,之所以多出这样一个字节,是为了便于直接使用 glibc 的字符串处理函数,以及为了便于字符串的调试打印输出。

    image.png

    看上面这张图可以算出,留给 content 的长度最多只有 45(64-19) 字节了。字符串又是以\0结尾,所以 embstr 最大能容纳的字符串长度就是 44。

    hash

    相当于java中HashMap,是无序字典.也是 数组+链表的二维结构

    需要注意的是,redis的字典的值只能是字符串,同时扩容时采用的是渐进式rehash策略(因为redis是单线程的,当HashMap字典很大时,一次性全部rehash是个比较耗时的操作)

    在rehash的同时,保留新旧两个hash结构,查询时同时查询两个hash结构,然后通过定时任务以及hash操作指令中,循序渐进地将旧hash的内容一点点迁移到新的hash结构中。迁移完后,使用新的代替旧的

    hash的数据结构

    image.png

    dict 结构内部包含两个 hashtable,通常情况下只有一个 hashtable 是有值的。但是在 dict 扩容缩容时,需要分配新的 hashtable,然后进行渐进式搬迁,这时候两个 hashtable 存储的分别是旧的 hashtable 和新的 hashtable。待搬迁结束后,旧的 hashtable 被删除,新的 hashtable 取而代之。

    扩容时机

    正常情况下,当 hash 表中元素的个数等于第一维数组的长度时,就会开始扩容,扩容的新数组是原数组大小的 2 倍。不过如果 Redis 正在做 bgsave,为了减少内存页的过多分离 (Copy On Write),Redis 尽量不去扩容 (dict_can_resize),但是如果 hash 表已经非常满了,元素的个数已经达到了第一维数组长度的 5 倍 (dict_force_resize_ratio),说明 hash 表已经过于拥挤了,这个时候就会强制扩容。

    缩容时机

    当 hash 表因为元素的逐渐删除变得越来越稀疏时,Redis 会对 hash 表进行缩容来减少 hash 表的第一维数组空间占用。缩容的条件是元素个数低于数组长度的 10%。缩容不会考虑 Redis 是否正在做 bgsave。

    list

    内部采用了quicllist,类似于linkedlist,但除了左右指针,还维护了上下指针,有点类似于小组长的机制,不断往下找。

    在列表元素较少的情况下回使用一块连续的内存存储,这个结构是ziplist,它将所有的元素紧挨着一起存储,分配一块连续的内存。当数据量较多时才会使用quicklist,这是因为普通的链表需要附加指针,会比较浪费内存.

    set集合

    相当于java中的HashSet,内部的键值对是无序的唯一的。

    zset有序集合

    类似于java中的Sorted和HashMap的结合体,一方面它是一个set,保证了内部value的唯一性,另一方面可以给每个value赋予一个score,代表这个value的权重.

    此外

    redis还为我们提供了一些其它的数据结构,比如位图,HyperLogLog等

    相关文章

      网友评论

          本文标题:redis数据结构总结

          本文链接:https://www.haomeiwen.com/subject/jfbudqtx.html