redis数据结构总结

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等