redis底层数据类型

前言

redisObject

实际上,不论redis存储的值是五种数据类型的哪一种,都是通过RedisObject来存储的，redis（Romote Dictonary server）远程字典服务

1. redisObject中的type字段指明了要存的值的类型,即String/List/Zset/Hash中的一个
2. RedisObject中encoding表示底层使用的编码格式,为了提供存储和执行效率,每种数据结构的底层结构不止一种
3. RedisObject中的ptr字段指向对象所在的地址.可以看出字符串对象虽然经过了RedisObject的包装,但仍然需要SDS存储

所以每个类型都是通过设定RedisObject中的这三个属性来实现的

SDS

SDS的结构定义在sds.h文件中，SDS的定义在redis3.2版本之后有一些改变，由一种数据结构变成了5种数据结构，会根据SDS的长度来选择不同的结构，达到节省内存你的效果

// 3.0
struct sdshdr {
    // 记录buf数组中已使用字节的数量，即SDS所保存字符串的长度
    unsigned int len;
    // 记录buf数据中未使用的字节数量
    unsigned int free;
    // 字节数组，用于保存字符串
    char buf[];
};

// 3.2
/* Note: sdshdr5 is never used, we just access the flags byte directly.
 * However is here to document the layout of type 5 SDS strings. */
struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used */
    uint8_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; /* used */
    uint16_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; /* used */
    uint32_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* used */
    uint64_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
3.2版本之后，会根据字符串的长度来选择对应的数据结构

static inline char sdsReqType(size_t string_size) {
    if (string_size < 1<<5)  // 32
        return SDS_TYPE_5;
    if (string_size < 1<<8)  // 256
        return SDS_TYPE_8;
    if (string_size < 1<<16)   // 65536 64k
        return SDS_TYPE_16;
    if (string_size < 1ll<<32)  // 4294967296 4G
        return SDS_TYPE_32;
    return SDS_TYPE_64;
}

• 获取字符串长度

C语言使用长度为N+1的字符数组来表示长度为N的字符串，字符数组的最后一个元素为空字符0,但是这种简单的字符串表示方式不能满足Redis对于字符串在安全性,效率以及功能方面的要求,那么使用SDS有哪些好处呢

C字符串不记录字符串的长度,获取长度必须遍历整个字符串

• 缓存区溢出

C字符串不记录自身的长度，每次增长或缩短一个字符串，都要对底层的字符数组进行一次内存重分配操作。如果是拼接append操作之前没有通过内存重分配来扩展底层数据的空间大小，就会产生缓存区溢出；如果是截断trim操作之后没有通过内存重分配来释放不再使用的空间，就会产生内存泄漏

而SDS通过未使用空间解除了字符串长度和底层数据长度的关联，3.0版本是用free属性记录未使用空间，3.2版本则是alloc属性记录总的分配字节数量。通过未使用空间，SDS实现了空间预分配和惰性空间释放两种优化的空间分配策略，解决了字符串拼接和截取的空间问题

C字符串中的字符串必须符合某种编码,除了字符串的末尾里面是不能包含空字符的,否则会被认为是字符串的结尾,这些限制了C字符串只能保存文本数据,而不能保存图片这样的二进制数据

• 二进制安全

而SDS的API都会以处理二进制的方式来处理存放在buf数组里面的数据,不会对里面的数据做任何的限制,SDSshiyonglen属性来判断字符串是否结束,而不是空字符

• 兼容部分C字符串函数

虽然SDS的API是二进制安全的，但还是像C字符串一样以空字符结尾，目的是为了让保存文本数据的SDS可以重用一部分C字符串的函数

redis包含五中常用数据结构

String,List,Hash,Set,Zset

String

字符串的存储过程分为俩步1.选择合适的SDS类型,2.选择合适的Encoding编码

选择合适的SDS类型

根据value的长度选择对于的SDS类型

redis底层的数据结构有

• redis_encoding_int (long类型的整数)
• redis_encoding_embstr (embstr编码的简单动态字符串)
• redis_encoding_raw (简单动态字符串)
• redis_encoding_ht (字典）
• redis_encoding_linkedlist （双端链表）
• redis_encoding_ziplist（压缩列表）
• redis_encoding_intset（整数集合）
• redis_encoding_skiplist（跳跃表和字典）

字符串的底层encoding编码结构是int,row或者embstr

embstr和raw比较

• int:当一个value是整型时,
• embstr:小于等于44个字符串
• raw大于等于44个字节字符串

embstr好处:使用只分配一次内存空间(因此RedisObject和sds是连续的),而raw需要分配俩次内存空间(分别为RedisObject和sds分配空间)因此与raw相比,embstr好处在于创建时少分配一次空间,删除时也少释放一片空间,以及对象的所有数据连在一起,寻找方便.

坏处:而embstr的坏处也非常明显,如果字符串长度增加需要重新分配时,整个redisObject和SDS都需要重新分配空间,因此redis的embstr实现为只读

总结如果一个字符串内容可以转换为long,那么该字符串会被转化为long类型,对象ptr指向该long,并且对象类型也用int表示.普通的字符串有两种 embstr 和 raw。如果字符串对象的长度小于 44字节，就用 embstr，否则用 raw。

为什么是44

实际redis中存储数据的最小SDS结构是SDS_TYPE_8结构

可以看出一个最小的SDS,至少占用3字节,再加上RedisObject16个字节,也就是说一个最小的字符串是19个字节(int8就是8位)

再了解下redis的内存分配器：jemalloc、tcmalloc。

这些内存分配器可以分配的大小2/4/8/16/32/64字节,最多可以分配64字节,即64k的连续内存

64字节，减去RedisObject的16字节和SDS的3字节头信息，剩下45字节，再去除0结尾，这样得出embstr可存储最大长度为64-16-3-1=44字节的字符串。

hash

也叫字典

哈希对象的编码有俩种 ziplist，hashtable

当哈希表保存的键值对量小于512，所有键值对的长度都小于64字节时，使用ziplist（压缩列表）存储。否则使用hashtable存储存储

redis的hashtable和java的hashmap有些类似，都是通过数组+链表的实现方式解决部分的哈希冲突

压缩列表是列表（List）和散列（Hash）的底层实现之一，一个列表只包含少量列表项，并且每个列表项是小整数值或比较短的字符串，会使用压缩列表作为底层实现（在3.2版本之后是使用quicklist实现）

dict.h/dictht

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

哈希表是由数组table组成，table中每个元素都是指向dict.h/dictEntry结构的指针，哈希表节点的定义如下

typedef struct dictEntry {
    // 键
    void *key;
    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    // 指向下一个哈希表节点，形成链表
    struct dictEntry *next;
} dictEntry;

其中key是我们的键；v是键值，可以是一个指针，也可以是整数或浮点数；next属性是指向下一个哈希表节点的指针，可以让多个哈希值相同的键值对形成链表，解决键冲突问题

最后就是我们的字典结构，dict.h/dict

typedef struct dict {
    // 和类型相关的处理函数
    dictType *type;
    // 私有数据
    void *privdata;
    // 哈希表
    dictht ht[2];
    // rehash 索引，当rehash不再进行时，值为-1
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    // 迭代器数量
    unsigned long iterators; /* number of iterators currently running */
} dict;

type属性和privdata属性是针对不同类型的键值对，用于创建多类型的字典，type是指向dictType结构的指针，privdata则保存需要传给类型特定函数的可选参数，关于dictType结构和类型特定函数可以看下面代码

typedef struct dictType {
    // 计算哈希值的行数
    uint64_t (*hashFunction)(const void *key);
    // 复制键的函数
    void *(*keyDup)(void *privdata, const void *key);
    // 复制值的函数
    void *(*valDup)(void *privdata, const void *obj);
    // 对比键的函数
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);
    // 销毁键的函数
    void (*keyDestructor)(void *privdata, void *key);
    // 销毁值的函数
    void (*valDestructor)(void *privdata, void *obj);
} dictType;

list

列表对象的编码有两种，分别是：ziplist、linkedlist。当列表的长度小于 512，并且所有元素的长度都小于 64 字节时，使用ziplist存储；否则使用 linkedlist 存储。

代码如下

adlist.h

typedef struct listNode {
    // 前置节点
    struct listNode *prev;
    // 后置节点
    struct listNode *next;
    // 节点值
    void *value;
} listNode;

list.h

typedef struct list {
    // 链表头节点
    listNode *head;
    // 链表尾节点
    listNode *tail;
    // 节点值复制函数
    void *(*dup)(void *ptr);
    // 节点值释放函数
    void (*free)(void *ptr);
    // 节点值对比函数
    int (*match)(void *ptr, void *key);
    // 链表所包含的节点数量
    unsigned long len;
} list;

每个节点listNode可以通过prev和next指针分布指向前一个节点和后一个节点组成双端链表，同时每个链表还会有一个list结构为链表提供表头指针head、表尾指针tail、以及链表长度计数器len，还有三个用于实现多态链表的类型特定函数

此外，Redis的发布与订阅、慢查询、监视器等功能也用到了链表

• dup：用于复制链表节点所保存的值
• free：用于释放链表节点所保存的值
• match：用于对比链表节点所保存的值和另一个输入值是否相等

链表特性

• 双端链表：带有指向前置节点和后置节点的指针，获取这两个节点的复杂度为O(1)
• 无环：表头节点的prev和表尾节点的next都指向NULL，对链表的访问以NULL结束
• 链表长度计数器：带有len属性，获取链表长度的复杂度为O(1)
• 多态：链表节点使用 void*指针保存节点值，可以保存不同类型的值

set

set类型的特点很简单,无序,不重复,跟java的hashSet类似.它的编码有俩种,分别是intset和hashtable.如果value可以转换成整数值,而且长度不超过512的话就是用intset存储,否则采用hashtable

hashtable在前面讲hash类型时讲过,这里的set集合采用的hashtable几乎一样,只是哈希表的value都是null.这个不难理解,java中也是用hashmap实现的hashset,只不过我们只用的是key

zset

zset是Redis中比较有特色的数据类型，它和set一样是不可重复的，区别在于多了score值，用来代表排序的权重。也就是当你需要一个有序的，不可重复的集合列表时，就可以考虑使用这种数据类型。

zset的编码有两种，分别是：ziplist、skiplist。当zset的长度小于 128，并且所有元素的长度都小于 64 字节时，使用ziplist存储；否则使用 skiplist 存储。

• hash用来存储value到score的映射,这样就可以在o(1)时间内找到value对应的分数
• skip按照从小到大的顺序存储分数
• skiplist每个元素都是[score,value]对

redis为什么使用跳表作为索引，不使用B+树

　　因为B+树的原理是叶子节点存储数据，非叶子节点存储索引，B+树的每个节点可以存储多个关键字，它将节点大小设置为磁盘页的大小，充分利用了磁盘预读的功能。每次读取磁盘页时就会读取一整个节点，每个叶子节点还有指向前后节点的指针，为的是最大限度的降低磁盘的IO;

　　而Redis是内存中读取数据，不涉及IO，因为数据在内存中读取耗费的时间是从磁盘的IO读取的百万分之一，因此使用了跳表，利用空间换时间的方式，实现简单，且能提高查询效率。

redis为什么使用跳表作为索引，不使用红黑树

　　选择跳跃表而非红黑树作为有序集合实现方式的原因，并非是基于并发上的考虑，redis是单线程，仅仅是因为跳跃表的实现相较于红黑树更加简洁，内存占用更有优势。

Redis 中的有序集合（Zset）支持的核心操作主要有以下几个：

• 插入一个数据
• 删除一个数据
• 查找一个数据
• 按照区间查找数据
• 迭代输出有序序列

其中，插入、删除、查找以及迭代输出有序序列这几个操作，红黑树也可以完成，时间复杂度和跳表是一样的。

按照区间查找数据这个操作，红黑树的效率没有跳表高。跳表查看实现原理可以在 O(logn) 时间复杂度定位区间的起点，然后在原始链表中顺序向后查询就可以了，这样非常高效【空间换时间，增加多级索引，从上往下开始查找】。此外，相比于红黑树，跳表还具有代码更容易实现、可读性好、*内存占用更有优势、*不容易出错、更加灵活等优点，因此 Redis 用跳表来实现。

zset不允许重复成员,是有序的,score可以重复

zset也叫作sortedSet

为什么不用其他数据结构,红黑树,b树

为什么不用红黑树

插入,删除,查找,以及迭代输出有序这几个操作红黑树也可以完成,且时间复杂度跟跳表一样.但按照区间来查找数据这个操作红黑树的效率没有跳表高.

跳表可以做到O(longn)的时间复杂度定位区间的起点,再在原始链表中顺序往后遍历,非常高效.

其他原因还有跳表更容易代码实现,更加灵活,可以通过改变引构策略,有效率平衡执行效率和内存消耗

Tips： 跳表不能完全替代红黑树，红黑树比跳表的出现要早一些，很多编程语言中的 Map 类型都是通过红黑树来实现，做业务开发时可以直接拿来用，不用费劲自己去实现，但跳表没有现成的实现，所以在开发中如果想使用跳表必须要自己实现。

为什么不用B+树

B+树的原理是叶子节点存储数据，非叶子节点存储索引，B+树的每个节点可以存储多个关键字，它将节点大小设置为磁盘页的大小，充分利用了磁盘预读的功能。每次读取磁盘页时就会读取一整个节点,每个叶子节点还有指向前后节点的指针，为的是最大限度的降低磁盘的IO;因为数据在内存中读取耗费的时间是从磁盘的IO读取的百万分之一。而Redis是内存中读取数据，不涉及IO，因此使用了跳表；