第一部分 数据结构与对象

[toc]

1. 简单动态字符串

​ Redis自己构建了一种名为简单动态字符串(SDS)的抽象类型,并将其作为Redis的默认字符串表示.在Redis中,包含字符串值的键值对在底层都是SDS实现的.C字符串只会作为字面量使用.

(1). SDS的定义

struct sdshdr{
    // 记录出发数组中已经使用了的字符数量
    // 也就是sds所保存的字符串的长度
    int len;
    
    // 记录空闲空间的数量
    int free;
    
    // 字节数组,存储字符数据
    char buf[];
}

​ SDS遵循C字符串以空字符('\0')结尾的惯例,目的是为了直接重用一部分C字符串库函数.但是这个空字符是不计入len属性中的.

(2). SDS和C字符串的区别

​ C字符串并不能满足Redis在安全性,效率以及功能方面的要求.

1). 获取字符串长度

​ SDS可以常数复杂度的获取字符串的长度,因为数据结构中已经存储了字符串的长度,不需要遍历数组去求累计和.

2). 杜绝缓冲区溢出

​ 在修改前会判断空间是否足够使用(free字段的值),而如果使用C字符串,需要先进行手动判断,保证空间足够.

​ SDS API对SDS进行修改时,API会检查SDS的空间是否满足修改所需的要求.如果不足,则会自动进行扩容.

3). 减少修改字符串时带来的内存充分配次数

​ C字符串的底层总是空间大小刚好合适(n+1).这样对字符串进行修改时,就经常会涉及到内存的重分配.SDS中保留了空闲空间,接触了字符串长度和底层数组长度的关联.

​ 通过未使用空间,SDS实现了==空间预分配==和==惰性空间释放==两种优化策略.

1>. 空间预分配

​ 每次都额外分配内存,减少内存重新分配.优化SDS的增长.

​ 额外分配的内存等于所使用的内存,但不超过1 MB.

​ 拓展SDS时会优先使用空闲空间,如果空闲空间不足,才会重新分配内存.

2>. 惰性空间释放

​ 长度缩短时,不会立刻回收内存.优化SDS缩短.

​ SDS提供了相应API,可以手动的真正释放SDS未使用的空间.从而不会造成内存浪费.

4). 二进制安全

​ 不需要考虑'/0'的意义,那么就可以存储二进制数据.

5). 兼容部分C字符串函数

2. 链表

Redis使用的C语言没有内置链表的实现,所以Redis构建了自己的实现方式.

当list内存储了较多的元素或者list中包含的元素都是较长的字符串时,Redis就会使用链表作为列表的底层实现.

链表的数据结构实现略过.

(1). 链表和链表节点的实现

// 链表节点的定义
typedef struct listNode{
    // 前继节点
    struct listNode *prev;
    // 后继节点
    struct listNode *prev;
    // 指向节点存储的数据
    void *value;
}listNode;

// 链表的数据结构定义
typedef struct list{
    // 头结点
    listNode *head;
    // 尾节点
    listNode *tail;
    // 链表长度
    unsigned long len;
    // 复制链表节点的函数
    void *(*dup)(void *ptr);
    // 释放链表节点的函数
    void (*free)(void *ptr);
    // 节点值对比函数
    int (*match)(void *ptr, void *key);
}list;

void * 的用法相当于Java中的Object,可以保存所有类型的指针.

​ list中存储了链表的长度,所以可以O(1)时间复杂度获取数据量.

3. 字典

字典在Redis中的应用非常广泛,Redis中的数据库就是使用字典作为底层实现的(从数据结构的key得到数据结构的对象).

字典还是哈希类型的底层实现之一,当一个哈希类型包含的键值对比较多,或者键值对中的元素都是比较成的字符串时,Redis就会使用字典作为哈希类型的底层实现.

(1). 字典的实现

1). 哈希表以及其节点的定义

​ Redis字典所使用的哈希表的定义:

// 哈希表节点的定义
typedef struct dictEntry{
    // 键
    void *key;
    // 值(枚举类型,分别存储结构体类型,无符号数和有符号数)
    union{
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    // 指向下一个节点
    struct dictEntry *next;
}dictEntry;

// 哈希表整体数据结构的定义
typedef struct dictht{
    // 节点数组(第一个星号表示数组,第二个表示数组中存储的是指向字节节点的指针)
    dictEntry **table;
    // 哈希表的大小
    unsigned long size;
    // 哈希表大小减一,用于方便计算索引值(散列)
    unsigned long sizemask;
    // 已占用的空间数
    unsigned long used;
}

​ 从以上定义可以看出,Redis中哈希表的底层和Java中HashMap的底层数据结构定义是一样的,都是使用数组+链表存储数据,使用链地址法(拉链法)解决哈希冲突.

2). 字典

​ Redis中的字典的数据结构定义:

// 这个结构体中定义了一些操纵特定类型键值对的函数,Redis会为不同用途的字典设置不用的函数
// 是为了创建多态字典使用的
typedef struct dictType{
    // 计算哈希值的函数
    unsigned int (*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 *privadata, void *key);
    // 销毁值
    void (*valDestructor)(void *privadata, void *obj);
}
// 这个是字典的结构体定义
typedef struct dict{
    // 这个字典使用的方法
    dictType *type;
    // 私有数据
    void *privdata;
    // 每一个字典都会使用两个哈希表,ht[1]的哈希表只会在ht[0]的哈希表rehash时才会使用
    dictht ht[2];
    // rehash索引,当rehash不再进行时,为-1(相当于状态量,根据这个状态量判断从ht[0]或者ht[1]中取出数据)
    int rehashidx;
}

(2). 哈希算法

​ 当要插入键值对时,先要根据插入的键计算出哈希值,然后根据这个哈希值散列到哈希表节点的数组中.

// 每一个字典使用的哈希方法可能是不一样的
hash = dict->type->hashFunction(key);
// 得到哈希值之后,对哈希值和数组长度减一按位与得到数组中的下标
index = hash & dict->ht[x].sizemask;

(3). 解决键冲突

​ Redis中的哈希表使用链地址法解决哈希冲突.

​ 因为dictEntry中的链表是单向链表,所以新节点会使用头插法进入链表.

(4). rehash

Redis中哈希表的rehash机制:

​ 二倍对ht[1]扩容(这里保证了容量为2^n,在hash的时候使用了按位与)

​ rehash时全部重新hash到另外一张表中

​ 释放原表,然后将新表设置为ht[0],并在ht[1]处创建空白表(这里的空白是指没有初始化数组,但是有其他部分数据)

哈希表的扩容和收缩:

当满足以下条件时,程序自动进行哈希表的扩容:

1. 服务器没有在执行BGSAVE或者BGREWRITEAOF命令(后台线程持久化数据),并且哈希表的负载因子大于1(负载因子: 元素数 / 桶数量)
2. 服务器正在进行后台线程持久化数据,并且负载因子大于5

另一方面,当负载因子小于0.1时,程序自动进行哈希表的收缩操作.caozuo

(5). 渐进式rehash

​ rehash动作并不是一次性执行完的,而是分多次,渐进式地完成的.(防止Redis短时间内被rehash占用cpu而停止服务)

​ 这个过程是从哈希数组的0号位置向后进行的,rehashidx(rehash索引)表示当前进行到的位置,当rehashidx累加到数组长度时,渐进式rehash结束,设置为-1.

渐进式rehash期间对哈希表的操作:

​ 在渐进式rehash进行时,字典会同时使用两个哈希表,例如:如果要找一个键,会现在ht[0]上面寻找,如果没能找到,再在ht[1]上寻找.

​ 所有的新值一律会保存到ht[1]中,也就是新表中,保证ht[0]中的数据只减不增.,并且锁着rehash的进行被全部复制到新表中,最后被清空.

4. 跳跃表

跳跃表是一种数据结构,通过在每个节点中维持多个指向其他节点的指针从而达到快速访问节点的目的.

Redis采用跳跃表作为有序集和(zset)的底层实现之一,当zset包含的元素数量较多又或者zset中存储的都是较长的字符串时,Redis就会使用跳跃表作为zset的底层实现.

同链表,字典等数据结构被广泛的应用在Redis中不同,Redis内部只在zset和集群节点中使用到了跳跃表.

跳表──没听过但很犀利的数据结构

跳表内算法:跳跃表原理

(1). 跳跃表的定义

​ 跳跃表是链表的进化版解决了链表查找元素时间复杂度常量阶的缺点.常常用来代替平衡树(实现更简单,效率也不低).

​ 跳表相当于在链表的节点中存储了多个next指针,根据跳跃的维度不同加以区分,在内存表示中将步长(这里的步长并不是确定的,只能大致认为上层的步长比下层的要大)越大的指针放在上面,步长小的放在下面,如此就有了层的概念,如图所示:

[图片上传失败...(image-c171f1-1590395023188)]

​ 查找时,先根据高层级指针向后寻找,如果找到的元素大于要寻找的元素,向回退一步,使用低一层的指针向后访问.当步长为1并且还没有找到时,就意味着整个表中都没有这个元素.

(2). 跳跃表节点

​ 跳跃表节点的数据结构定义:

typedef struct zskiplistNode {
    // 后退指针
    // 用于从后向前遍历元素(从前向后只需要挨个访问层级为0的前进指针即可)
    struct zskiplistNode *backward;
    // 该节点的分值,跳跃表中元素排列的依据,可以理解为跳跃表也是一个按照分值有序的链表
    // 当分值相等时,将存储对象的大小作为排序的依据
    // 这应该是Redis中跳表实现独有的
    double score;
    // 节点内存储的对象
    robj *obj;
    // 节点处于各个层的层对象
    struct zskiplistLevel {
        // 前进指针
        struct zskiplistNode *forward;
        // 本次前进的跨度
        unsigned int span;
    } level[];
} zskiplistNode;

1). 层

​ 每一个节点的层数是使用数组存储的,就可以做到扩容.

​ 每创建一个新链表节点时,程序都根据==幂次定律(越大的数,生成的概论越小)生成一个1~32的值作为level数组的大小==,这个大小就是这个节点最大的层的高度,也就是可以为访问到的最高的层.

2). 前进指针

​ 这个指针是每一个有独立的,向后访问时,先使用高层级的前进指针访问,如果没找到,再使用低一级的前进指针访问.直到层级为0.

3). 跨度

​ 跨度表示这个前进指针前进的步数,用于在访问节点时计算节点在跳跃表中的排位.

​ 指向null的前进指针对应的跨度为0,表示不连接任何节点.

(3). 跳跃表

​ 数据结构定义如下:

typedef struct zskiplist {
    // 头节点，尾节点
    struct zskiplistNode *header, *tail;
    // 节点数量
    unsigned long length;
    // 目前表内节点的最大层数
    int level;
} zskiplist;

​ 表头结点是不存储数据的,并且表内节点的最大层数也不考虑表头结点.

​ 最大层数用于选择一开始使用那一层的前进指针进行遍历.

(4). 跳表的插入(Java实现)

public void insert(int value) {
    int level = randomLevel(); // 幂次定律
    Node newNode = new Node();
    newNode.data = value;
    newNode.maxLevel = level;
    Node update[] = new Node[level];
    // 将0 ~ leval-1下标处的元素更新为head(跳表头节点)
    for (int i = 0; i < level; ++i) {
        update[i] = head;
    }

    // 从最高层向下寻找,类似跳表中的查找
    Node p = head;
    for (int i = level - 1; i >= 0; --i) {
        while (p.forwards[i] != null && p.forwards[i].data < value) {
            // 向后寻找
            p = p.forwards[i];
        }
        update[i] = p;// 更新每一个update,也就是说update记录的是在每一层中node节点的前继节点
    }

    // 更新每一层,通过update数组
    for (int i = 0; i < level; ++i) {
        newNode.forwards[i] = update[i].forwards[I];
        update[i].forwards[i] = newNode;
    }

    // 更新层数
    if (levelCount < level) levelCount = level;
}

5. 整数集合

整数集合是集合(set)的底层实现之一,当一个集合中只包含整型元素时,并且数量不多,Redis就会使用整数集合作为集合的底层实现.

以数组为底层实现的set

(1). 整数集合的实现

​ 整数集合是Redis用于保存整数值的集合抽象数据结构,可以保存int16_t,int32_t或者int64_t.

​ 结构体定义如下:

typedef struct intset{
    // 编码方式
    uint32_t encoding;
    // 集合包含的元素数量
    uint32_t length;
    // 保存元素的数组(这里的类型为最基本的类型,后面根据不同的encoding,使用多个格子表示一个元素)
    int8_t contents[];
} intset;

• encoding:决定了contents数组中值的类型
• length:记录整个整数集合包含的元素数量
• contents:虽然定义为int8_t,但是实际的类型还是决定于encoding.并且数组中的元素在数组中按照大小升序排列.不包含重复项

​ 对整数集合的各种操作类似ArrayList.

​ 对元素的查找是二分的,插入操作也会先找这个元素,也是先二分,在移动后面的元素.

(2). 升级

​ 当要添加一个元素,但是这个元素超出了现有的编码方式的取值范围时,就需要执行升级来对数组的元素进行扩充.然后才可以将这个元素插入到整数集合中.

​ 大致步骤如下:

1. 根据新元素的类型,扩展整数集合底层数组的空间大小,并且分配新元素的空间(在原有空间基础上进行扩容,而不是重新分配整个新的数组)
2. 将原先就存在的数据转换为新的类型,并且放置到正确的位置上,要保证有序性(对旧元素来说,是从后向前遍历的).在空间的使用上面,起始位置变为原来的二倍,结束位置变为二倍加一
3. 将新元素添加到底层数组中

因为能引起升级的元素是超出原有的元素取值范围的,所以要么比所有元素大,要么比所有元素小,所以最后这个元素会被放在索引处为0或者length-1的位置上.

升级操作是单向的,不存在降级的行为.

(3). 升级的好处

1. 提升灵活性:避免类型错误
2. 节约内存:为了实现上面的做法,也可以直接使用int64_t作为底层实现,不过太过耗费内存.

6. 压缩链表

压缩链表是list和hash的底层实现之一.

当一个list中只包含少量元素并且每一个元素都是小的整数值或者长度较短的字符串时,Redis就会使用压缩链表作为list的底层实现.

当一个hash中只包含少量的键值对并且每个键值对都是小整数值或者长度较短的字符串时,Redis就会使用压缩表来作为hash的底层实现.

(1). 压缩列表的构成

​ 压缩列表是Redis为了节约内存而开发的,是由一些列特殊编码的连续内存块组成的顺序型数据结构.一个压缩列表可以包含任意多个节点,一个节点可以存储一个字节数组或者一个整数值.

​ 压缩列表的组成:

(2). 压缩列表节点的构成

​ 每一个压缩列表节点可以保存一个字节数组(0-2⁶-1, 0-2¹⁴-1, 0-2³²-1)或者一个整数值(4位无符号,1字节有符号,3字节有符号,int16_t类型,int32_t类型,int64_t类型),每一个节点的构成如下:

1). previous_entry_length

​ 前一个节点的长度(以字节为单位).

​ 如果前一个节点大小小于254字节,那么这个属性只占一个字节,如果超出254,那么这个属性占5字节.

​ 记录这个值的目的在于可以直接计算得出前一个节点的起始地址.压缩列表从表尾向表头遍历就是通过这个原理实现的.只要拥有了一个指向某节点其实地址的指针,就可以一直向前寻找,知道到达头节点.

2). encoding

​ 这个属性记录了节点的content属性锁保存的数据的类型以及长度

​ 如果存储的是字节数组,那么encoding长度为1(00xxxxxx),2(01开头)或者5字节(10开头),去掉开头的两位之后表示字节数组的长度.

​ 如果存储的是数字,encoding起始的两位为11.

3). content

​ 节点的content属性负责保存节点的值,节点的值可以使字节数组或者整数,由encoding决定.

(3). 连锁更新

​ 之前的节点构成中我们知道previous_entry_length属性可以是1字节(0~254)也可以是5(255~...)字节.那么如果有若干长度为220~223字节长度的节点连续排列,此时将第一个节点进行扩容,扩容至224节点以上,这个节点的长度是记录在下一节点上的,那么下一节点的previous_entry_length就会由1字节变为5字节,会进行空间的重分配,然后继续向后发生连锁反应.

​ 这里需要知道的是,==普通的插入操作(不产生连锁更新现象)是将插入元素的所有后继节点整体向后移动,并不需要挨个的进行扩容==,效率并不低.而连锁更新现象只有节点长度为220~223字节的节点连续排列时才会发生,概率非常低,并且对三五个节点的连锁更新并不会影响性能.

7. 对象

​ 之前的6个小结介绍了Redis中使用到的6种底层数据结构,但Redis并没有直接使用这些数据结构来实现NoSQL数据库,而是创建了对象系统,这个系统包含字符串对象(string),列表对象(list),哈希对象(hash),集合对象(set)和有序集和对象(zset).每一种对象都至少用到了一种底层数据结构.

​ 针对不同的使用场景,为一个对象设置多种不同的数据结构实现,从而优化使用效率.

​ Redis还为对象系统实现了基于引用计数的内存回收机制.

​ Redis的对象带有访问时间的记录信息.空转时间较长的元素是可能被优先删除的.

(1). 对象的类型与编码

​ Redis使用对象来表示数据库中的键和值,也就是说,我们在Redis数据库中新建一个键值对,Redis至少会创建两个对象,一个对象充当键,一个对象充当值.

​ 每一个对象都由一个redisObject表示.

typedef struct redisObject{
    // Redis对象类型,就是Redis中5种数据结构,分别对应五个不同的常量
    unsigned type : 4;
    // 编码,也就是底层数据结构的类型对应的符号
    unsigned encoding : 4;
    // 指向实际底层数据结构(实际内存)的指针
    void *ptr;
} robj;

(2). Redis对象类型和底层数据结构的对应

​ 跳表和字典可以使用同一种编码,也就是说,在Redis对象中,跳表和字典是搭配使用的.但字典可以单独存在.

(2). string对象

​ 字符串对象的编码可以是int,raw或者embstr.

​ 如果是int类型,那么ptr指针指向一个long类型的变量.

​ 如果是row类型,那么ptr指向一个sds结构体.两次内存分配.

​ 如所示embstr类型,那么在==redisObject的后面紧接着就是sds结构体的内存==.只进行一次内存分配.

​ 需要知道的是,浮点型的数值是使用后两种类型当做字符串存储的.

编码转换:

​ int编码的字符串经过一系列操作(如追加式的拼接)后,不再是整数值,就会变成raw编码的字符串.

​ ==embstr编码的字符串对象没有任何修改程序,所以是只读的.所以对embstr编码的字符串进行修改时,就会转换成raw编码的字符串==

(3). list对象

​ 列表对象的编码可以是ziplist(压缩列表)或者linkedlist(双端列表).

​ 如果使用ziplist作为编码,ptr指针指向的是一个压缩列表,压缩列表的每一项就是list中的每一个元素.

​ 如果使用linkedlist作为编码,创建的将会是一个链表,ptr指针指向链表对象(而非头节点),每一个节点都是字符串对象(字符串对象是Redis对象中唯一可以被嵌套的).

(4). hash对象

​ 哈希对象的编码可以是ziplist或者hashtable(字典).

​ 使用ziplist作为编码时,当有新的键值对进入hash对象时,程序先将保存了键的压缩列表节点推入列表尾,再添加值.也就是说,键和值一一对应,==先是键再是值==,只靠这个约定限制.先添加的键值对在空间上处于后添加的键值对之前.

​ 使用hashtable作为编码的哈希对象,那么底层就跟Java中的HashMap差不多,键和值都必须是字符串对象

(5). set对象

​ 集合对象的编码可以使intset(整数集合)或者hashtable(字典).

​ 使用intset作为编码,那么ptr指针指向一个整数集合结构体,内部实现类似于元素不重复的ArrayList(并且有整数集合的特性:内部动态类型和升级).

​ 使用hashtable作为编码,那么ptr指针指向一个字典结构体,其中字典只有键,所有的值都为NULL,这种实现很想Java中的HashSet.

(6). zset对象

​ 有序集和的编码可以是ziplist或者zkiplist(搭配hashtable).

​ ziplist编码的有序集和对象使用压缩列表作为底层实现,每两个连续的压缩列表节点表示一个zset节点,前一个保存元素成员,后一个保存分值.内部按分值升序排列.

​ skiplist编码的有序集和内部同事包含一个字典和一个跳表.其中的跳表按分值从小到大保存了所有集合元素.跳表节点的object属性保存了元素的成员,score属性保存了元素的分值.字典存储了所有成员到分值的映射.

​ ==值得一提的是,虽然使用了两种结构共同表示zset,但是底层的数据都是使用string表示的,在这两种结构中,通过共享指针做到了极小的内存开销.==

==为什么要使用跳表和字典同时实现有序集和:==

​ ==理论上这两种数据结构都可以单独完成zset的实现,但是单一使用字典,会导致无法按照有序的方式排列元素,导致每次执行范围型操作时,都需要遍历并排序所有元素;单一使用跳表,根据成员查找分值的时间复杂度会大大上升.==

(7). 类型检查和命令多态

​ Redis中用于操作数据的命令分为两类:一类是对任何键都可以使用的命令,如DEL,TYPE等.另一类只能对特定的键执行,例如:SET,GET,APPEND,STRLEN只能对字符串的键执行(使用错误会报错).

1). 类型检查的实现

​ Redis根据redisObject的type属性实现类型的检查.

​ 在执行一个类型特定命令之前,服务器会检查输入的键的值对象是否为执行命令所需的类型,如果是曹会执行命令,否则会返回一个类型错误.

2). 多态命令的实现

​ Redis还会根据redisObject的不同编码方式,选择执行不同的代码来执行命令.也就是说,在内部通过简单的类型判断来完成硬编码的方法选择,从而实现多态.

(8). 内存回收

​ Redis在字节的对象系统中构建了一个引用计数技术实现的内存回收机制.

​ 在redisObject中有一个字段为refcount,保存了这个对象被使用的数量,初始化为1.

​ 计数器的增加可以认为是两种现象:新的键指向这个值,在一个Redis程序中被持有.

(9). 对象共享

​ Redis中如果有两个100的string,那么不会在内存中存在两个一样的100,而是指向同一片内存,然后这个100的redisObject中的计数器加一.

​ 目前来说,Redis服务器在初始化时会创建0~9999一万个字符串对象,后面使用时直接共享即可,而不是创建新的对象.

(10). 对象的空转时长

​ redisObject结构包含的队后一个属性,:ru属性.记录了对象最后一次被命令程序访问的时间.将当前时间减去这个lru时间就可以计算出空转时间.

​ 这个时间可以被用在服务器上的内存回收算法LRU(最近最少使用算法).