Redis 数据结构与对象

原 作者 刘生玺 | 发表于 | 分类于 2016级

文章目录

前提：跳表

先给出大体结构图：

在这里插入图片描述
在这里插入图片描述
时间复杂度：O(log(n)) 　如果是3个节点提取就是O(log3(n))，以此类推

如何分析：(n) －＞(n/2)－＞（n/4）－＞（n/8）－…（n/2^k）

假设有ｈ级，最高层是2个节点！则n/(2^h) == 2，则 h = log2(n)-1，每一层ｍ个节点．则时间复杂度为O(m*log(n))

跳表是不是很浪费内存？？

在这里插入图片描述
总和为 O(n)
如何降低：

  • 可以三个或者五个节点抽取上级一索引

实际上，在软件开发中，我们不必太在意索引占用的额外空间。在讲数据结构和算法时，我们习惯性地把要处理的数据看成整数，但是在实际的软件开发中，原始链表中存储的有可能是很大的对象，而索引结点只需要存储关键值和几个指针，并不需要存储对象，所以当对象比索引结点大很多时，那索引占用的额外空间就可以忽略了。

删除时，要注意该节点是不是在索引中也出现了，如果出现的话，还要记得把他从索引中也要删除掉！！！

索引的动态更新

在这里插入图片描述
红黑树，AVL：左右旋
跳表：随机函数

当我们往跳表中插入数据的时候，我们可以选择同时将这个数据插入到部分索引层中。如何选择加入哪些索引层呢？

我们通过一个随机函数，来决定将这个结点插入到哪几级索引中，比如随机函数生成了值 K，那我们就将这个结点添加到第一级到第 K 级这 K 级索引中。

在这里插入图片描述

Redis中底层数据结构

SDS 简单动态字符串

Redis 只在表示字符串字面量的时候，也即不需要对字符串的值进行修改的地方，使用C字符串表示。比如打印日志之类的。其他时候都是使用自己封装的 SDS结构来表示字符串值。比如：缓冲区 等。

sds 的定义：

struct sdshdr {
    int len; //已使用的字节长度，也即buf的长度
    int free; //记录未使用的字节的数量
    char buf[];//字节数组，redis会自动加上‘\0’
};
SDS与C字符串相比有什么优点？
O(1)获取字符串长度（STRLEN命令）
杜绝缓冲区溢出。会先检查空间是否足够，不满足就会自动拓展。
内存重分配策略。类似于 vector .

  • 空间欲分配策略。

    如果修改之后的 SDS.len < 1MB。分配与len 相同的未使用内存。此时自然是 len == free
    如果修改之后的 SDS.len >=1MB。直接分配 1MB 大小内存。

  • 惰性空间释放策略

就是先将不使用的空间用free来保存一下。然后也提供API支持真正释放未使用的内存空间。

二进制安全

C字符串中的字符必须符合某种编码( 比如ASCII),并且除了字符串的末尾之外，字符串里面不能包含空字符，否则最先被程序读人的空字符将被误认为是字符串结尾(现在想想http，万一文本信息就含有 \r\n 呐？所以就是有了二进制分帧！)，这些限制使得C字符串只能保存文本数据，而不能保存像图片、音频、视频、压缩文件这样的二进制数据。

举个例子，如果有一种使用空字符来分割多个单词的特殊数据格式，如图所示，那么这种格式就不能使用C字符串来保存，因为C字符串所用的函数只会识别出其中的"Redis",而忽略之后的"Cluster"。

在这里插入图片描述
虽然数据库- . 般用于保存文本数据，但使用数据库来保存二进制数据的场景也不少见，因此，为了确保Redis可以适用于各种不同的使用场景,SDS的API都是二进制安全的(binary-safe),所有SDSAPI都会以处理二进制的方式来处理SDS存放在buf数组里的数据,程序不会对其中的数据做任何限制、过滤、或者假设，数据在写人时是什么样的，它被读取时就是什么样。

这也是我们将SDS的buf属性称为字节数组的原因一Redis不是用这个数组来保存字符，而是用它来保存一系列二进制数据。

例如，使用SDS来保存之前提到的特殊数据格式就没有任何问题，因为SDS使用len属性的值而不是空字符来判断字符串是否结束

会兼容部分的C字符串函数

如果SDS中保存的是文本数据的话，就可以使用一部分的C库函数。

在这里插入图片描述

缓冲区溢出是什么以及有什么后果？

  • 缓冲区溢出

  • 带来的后果

参考：https://www.cnblogs.com/clover-toeic/p/3737011.html

链表（使用到的地方：发布与订阅，慢查询，监视器，服务器的client链表）list

/*
 * 双端链表节点
 */
typedef struct listNode {
    // 前置节点
    struct listNode *prev;
    // 后置节点
    struct listNode *next;
    // 节点的值
    void *value;
} listNode;
/*
 * 双端链表迭代器
 */
typedef struct listIter {
    // 当前迭代到的节点
    listNode *next;
    // 迭代的方向
    int direction;
} listIter;
/*
 * 双端链表总控结构（有类似于文件系统操作表的函数指针保存）
 */
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;

在这里插入图片描述

  • 多态：节点使用 void *来保存节点值，并且可以通过 dup,free,match 三个属性来为节点值设置特定函数，所以链表可以用以保存不同类型的值。

字典(dict)

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

每个dictEntry结构保存一个键值对
sizemask和哈希值一起决定一个键应该被放到table数组的那个索引上面。

在这里插入图片描述

哈希表的节点（dictEntry结构保存一个键值对）
typedef struct dictEntry {
    // 键
    void *key;
    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    // 指向下个哈希表节点，形成链表
    struct dictEntry *next; //链式解决冲突
} dictEntry;

在这里插入图片描述

Redis 字典的实现
typedef struct dict {
    // 类型特定函数
    dictType *type;
    // 私有数据
    void *privdata;
    // 哈希表
    dictht ht[2];
    // rehash 索引
    // 当 rehash 不在进行时，值为 -1
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */
    // 目前正在运行的安全迭代器的数量
    int iterators; /* number of iterators currently running */
} dict;

type，privdata 为了实现多态字典。不详抒。

Redis中使用的哈希算法(MurmurHash算法 高运算性能，低碰撞率，hadoop、memcached 等使用)

当要将一个新的键值对添加到字典里面时，程序需要先根据键值对的键计算出哈希值和索引值，然后再根据索引值，将包含新键值对的哈希表节点放到哈希表数组的指定索引上面。
Redis计算哈希值和索引值的方法如下:

#使用字典设置的哈希函数，计算键key的哈希值
hash = dict->type->hashFunction (key) ;

#使用哈希表的sizemask属性和哈希值，计算出索引值#根据情况不同，ht[x]可以是ht[0]或者ht[1]
index = hash & dict->ht[x] .si zemask;

渐进式 reHash 的过程

关于负载因子等见：哈希表的负载因子

  1. 为字典的ht[1]哈希表分配空间，这个哈希表的空间大小取决于要执行的操作，以及ht[0]当前包含的键值对数量(也即是ht[0].used属性的值):

  2. 将保存在ht[0]中的所有键值对rehash到ht[1]. 上面: rehash指的是重新计算键的哈希值和索引值，然后将键值对放置到ht[1]哈希表的指定位置上。

    • 在字典中维持-一个索引计数器变量rehashidx,并将它的值设置为0，表示rehash工作正式开始。
    • 在rehash进行期间，每次对字典执行添加、删除、查找或者更新操作时,程序除了执行指定的操作以外，还会顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1]，当rehash工作完成之后，程序将rehashidx属性的值增一。
    • 随着字典操作的不断执行，最终在某个时间点上，ht[0]的所有键值对都会被rehash至ht[1],这时程序将rehashidx属性的值设为-1，表示rehash操作已完成。

  3. 当ht[0]包含的所有键值对都迁移到了ht[1]之后(ht[0]变为空表)，释放ht[0]，将ht[1]设置为ht[0]，并在ht[1]新创建-一个空白哈希表，为下一次rehash做准备。

跳表（O(logN)，zskiplist）

整数集合（intset）

用于保存整数，元素不会重复，从小到大排列。content中的类型根据编码方式而决定。在有需要时会进行自动转换。

typedef struct intset {
     // 编码方式
    uint32_t encoding;
    // 集合包含的元素数量
    uint32_t length;
    // 保存元素的数组
    int8_t contents[]; 
} intset;

在这里插入图片描述

压缩列表（ziplist）

由一系列特殊编码的连续内存块组成的顺序型的数据结构，可以包含任意多个节点，每个节点可以保存一个字节数组或一个整数值。

在这里插入图片描述
一个节点的结构是这样子的：
在这里插入图片描述
其实就是一种变异化的数组，也满足数组的一些特性。比如：不太能够支持随机添加和删除等。

对象的分类与底层支持的数据结构

Redis并没有直接使用这些数据结构来实现键值对数据库，而是基于这些数据结构创建了一个对象系统，这个系统包含字符串对象、列表对象、哈希对象、集合对象和有序集合对象这五种类型的对象，每种对象都用到了至少- -种我们前面所介绍的数据结构。

通过这五种不同类型的对象，Redis可以在执行命令之前，根据对象的类型来判断-一个对象是否可以执行给定的命令。使用对象的另-个好处是，我们可以针对不同的使用场景，为对象设置多种不同的数据结构实现，从而优化对象在不同场景下的使用效率。

除此之外，Redis 的对象系统还实现了基于引用计数技术的内存回收机制，当程序不再使用某个对象的时候，这个对象所占用的内存就会被自动释放;另外，Redis 还通过引用计数技术实现了对象共享机制，这一机制可以在适当的条件下，通过让多个数据库键共享同一个对象来节约内存。

最后，Redis的对象带有访问时间记录信息，该信息可以用于计算数据库键的空转时长，在服务器启用了mmaxmemory功能的情况下，空转时长较大的那些键可能会优先被服务器删除。

对象类型与编码

Redis 采用了面向对象的程序设计思路，将值和键都当作对象来对待。对于每一个对象，redis都用一个redisObject来表示。

typedef struct redisObject {
    // 类型
    unsigned type:4; 
    //就是上面提到的那五种对象类型，所以检查能不能够执行某一个命令时，就是根据这个去检查的
    // 编码
    unsigned encoding:4; //底层实现的数据结构的类型嘛 Object encoding 
    // 对象最后一次被访问的时间
    unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */
    // 引用计数
    int refcount;
    // 指向实际值的指针
    void *ptr;
} robj;

字符串对象（编码类型有 int,raw,embstr）

int 类型

如果一个字符串对象保存的是整数值，并且这个整数值可以用long类型来表示，那么字符串对象会将整数值保存在字符串对象结构的ptr属性里面(将void*转换成long),并将字符串对象的编码设置为int。

raw类型

如果是字符串，且长度 >39 B
在这里插入图片描述

embstr类型

如果是字符串，且长度 <= 39 。好像已经变成以44分界了，详见：https://blog.csdn.net/XiyouLinux_Kangyijie/article/details/78045385

embstr 编码是专门用于保存短字符串的一种优化编码方式，这种编码和raw编码一样，都使用redisObject结构和sdshdr结构来表示字符串对象，但raw编码会调用两次内存分配函数来分别创建redisObject结构和sdshdr结构，而embstr编码则通过调用- .次内存分配函数来分配一块连续的空间，空间中依次包含redisobject和sdshdr两个结构，
在这里插入图片描述
embstr 编码创建的内存块结构象执行命令时产生的效果是相同的，但使用embstr编码的字符串对象来保存短字符串值有以下好处:

  • embstr编码将创建字符串对象所需的内存分配次数从raw编码的两次降低为一-次。
  • 释放embstr编码的字符串对象只需要调用-一次内存释放函数，而释放raw编码的字符串对象需要调用两次内存释放函数。
  • 因为embstr编码的字符串对象的所有数据都保存在一块连续的内存里面，所以这种编码的字符串对象比起raw编码的字符串对象能够更好地利用缓存带来的优势

long,double 等也都是按照字符串保存的，在有需要时进行转换。

列表对象

由 压缩列表和链表实现。ziplist,linklist

(1): 压缩列表（数据量小,小整数或短字符串）

当列表中存储的数据量比较小的时候，列表就会以压缩列表的方式实现．具体还需要满足下面两个条件：

  • 列表中保存的单个数据小于64字节
  • 列表中数据个数小于512个

压缩列表有点儿类似于数组，但是他允许存储的数据大小不同．结构是下面这样：
在这里插入图片描述
如果单纯的使用数组来实现，就会以最长的元素来实现，这是对内存的浪费．

(2): 链表（数据量大时）

哈希对象

由压缩列表和哈希表实现。（ziplist和hashtable）

(1)压缩列表（数据量小,小整数或短字符串）

具体还要满足两个条件：

  • 字典中保存的健和值的大小都必须小于　64　字节
  • 字典中的键值对的个数要小于　512　个
    在这里插入图片描述
(2)散列表（数据量大）

使用的随机函数：MurmurHash2。运行速度快、随机性好

支持动态的扩容，缩容

  • 装载因子＞1，扩容原来2倍
  • 装载因子＜0.1，缩容一半大小
    在这里插入图片描述

集合对象

由整数集合和哈希表实现（ intset 和 hashtable ）

(1) 整数集合

需要满足的条件：

  • 储存的数据是整数
  • 数据元素不超过　512　个

其余都是散列表实现
在这里插入图片描述

(2) 哈希表

哈希的value 全是 NULL
在这里插入图片描述

有序集合对象

由压缩列表和跳表实现（ziplist，skiplist）

(1)压缩列表（数据量小）

每个集合元素使用两个紧挨在一起的压缩列表节点来保存。 前一个节点保存数据，后一个节点保存元素的分值

在这里插入图片描述
在这里插入图片描述

(2) 跳表（数据量大）

底层实现时，使用了一个zset的结构来实现。

typedef struct zset {
    // 字典，键为成员，值为分值
    // 用于支持 O(1) 复杂度的按成员取分值操作
    dict *dict; 
    // 跳跃表，按分值排序成员
    // 用于支持平均复杂度为 O(log N) 的按分值定位成员操作
    // 以及范围操作
    zskiplist *zsl;
} zset;

dict //成员到分值的映射。O(1)查找对应元素的分值。类似于使用链表和哈希表实现 LRU 。具体存储的对象又是和跳表共享的，所有不用担心dict会额外消耗内存。

这里需要生成一个简单的思想就是：散列表经常会和链表一起使用

在这里插入图片描述

对象共享与对象的空转时长

对象共享

在这里插入图片描述
redis 会在服务器初始化时，创建0～9999个字符串对象，如果用到就共享即可。

对象的空转时长

即上面提到的 redisObject中的lru选项。表示的是对象最后一次被访问的时间

OBJECT IDLETIME 命令就是服务器的LRU时间减去对象的LRU选项得出的结果
即为对象的空转时长。

如果服务器打开了maxmemory选项的化，就会优先被服务器释放空间。