Redis 的【数据类型】

  • 数据类型概念

Redis 数据库中每个数据都是由【key - value 键值对】形成的,而键值对是由一个个对象组成的;

Redis 数据库中的健 key,是为一个【字符串对象】

Redis 数据库中的值 value,则是为以下五种对象组成,或者说由以下五种数据类型组成:

  1. 字符串对象
  2. 列表对象
  3. 哈希对象
  4. 集合对象
  5. 有序集合对象
  • 数据类型操作方法

数据类型操作方法

String

  • 基本概念

String 是 redis 最基本的类型,在 redis 中,一个 key 对应一个 value。value 其实不仅是 String,也可以是数字

string 类型是二进制安全的。意思是 redis 的 string 可以包含任何数据。比如 jpg 图片或者序列化的对象

string 类型是 Redis 最基本的数据类型,string 类型的值【最大能存储 512MB】。

  • 使用场景
  1. 缓存: 经典使用场景,把常用信息,字符串,图片或者视频等信息放到 redis 中,redis 作为缓存层,mysql 做持久化层,降低 mysql 的读写压力。
  2. 计数器:redis 是单线程模型,一个命令执行完才会执行下一个,同时数据可以一步落地到其他的数据源。
  3. session:常见方案 spring session + redis 实现 session 共享,
  • 实现方式

String 在 redis 内部存储默认就是一个字符串,被 redisObject 所引用,当遇到 incr,decr 等操作时会转成数值型进行计算,此时 redisObject 的 encoding 字段为 int。

Hash

  • 基本概念

hash 是一个键值对集合,是一个 string 类型的 key 和 value 的映射表,key 还是 key,但是 value 是一个键值对(key-value)。

类比于 Java 里面的 Map<String,Map<String,Object>> 集合。

img

  • 使用场景

缓存: 能直观,相比 string 更节省空间,的维护缓存信息,如用户信息,视频信息等。

  • 实现方式

上面已经说到 Redis Hash 对应 Value 内部实际就是一个 HashMap,实际这里会有 2 种不同实现:

  1. 这个 Hash 的成员比较少时 Redis 为了节省内存会采用类似一维数组的方式来紧凑存储,而不会采用真正的 HashMap 结构,对应的 value redisObject 的 encoding 为ZipList,即底层存储此时为压缩列表 ZipList
  2. 当成员数量增大时会自动转成真正的 HashMap,此时 encoding 为HashTable

List

  • 基本概念

list 列表,它是简单的字符串列表,按照插入顺序排序,你可以添加一个元素到列表的头部(左边)或者尾部(右边),它的底层实际上是个链表(双向链表),通常用于消息队列中。

img

  • 使用场景

通过列表,我们可以实现以下几个数据结构:

  • lpush+lpop=Stack(栈)
  • lpush+rpop=Queue(队列)
  • lpush+ltrim=Capped Collection(有限集合)
  • lpush+brpop=Message Queue(消息队列)

时间轴,timeline:所谓时间轴系统就是典型的微博模式:用户在自己的主页可以看到其关注的博主发表的信息列表(按时间排序);而其它用户可以一个用户的个人主页看到这个人发布的信息列表(按时间排序)。

  • 实现方式

Redis list 的实现为一个双向链表,即可以支持反向查找和遍历,更方便操作,不过带来了部分额外的内存开销,Redis 内部的很多实现,包括发送缓冲队列等也都是用的这个数据结构。

Set

  • 基本概念

Redis 的 set 是 string 类型的无序集合。

相对于列表,集合也有两个特点:无序和不可重复

无序:表示集合中的元素是没有顺序的,不存在元素下标

不可重复:元素不能够重复

Redis set 对外提供的功能与 list 类似是一个列表的功能,特殊之处在于 set 是可以自动排重的,当你需要存储一个列表数据,又不希望出现重复数据时,set 是一个很好的选择,并且 set 提供了判断某个成员是否在一个 set 集合内的重要接口,这个也是 list 所不能提供的。

img

  • 使用场景

Sets 集合的概念就是一堆不重复值的组合。利用 Redis 提供的 Sets 数据结构,可以存储一些集合性的数据

比如在微博应用中,可以将一个用户所有的关注人存在一个集合中,将其所有粉丝存在一个集合。Redis 还为集合提供了求交集、并集、差集等操作,可以非常方便的实现如共同关注、共同喜好、二度好友等功能,对上面的所有集合操作,你还可以使用不同的命令选择将结果返回给客户端还是存集到一个新的集合中。

通常用于:

标签(tag),给用户添加标签,或者用户给消息添加标签,这样有同一标签或者类似标签的可以给推荐关注的事或者关注的人。

点赞,或点踩,收藏等,可以放到 set 中实现

  • 实现方式

Set 的内部实现依靠 HashMap(key 为对象名,value 为 null) + IntSet(整形数组)实现;

转换关系:结合对象保存的所有元素都是整数值,集合对象保存的元素数量不超过 512 个(满足这 2 个条件为 IntSet,否则为 HashMap)

由于元素不多的时候为 IntSet(有序数组),查找数据的时候用的是二分查找,因此效率很高。

Zset(Sorted Set)

  • 基本概念

zset(sorted set 有序集合),和上面的 set 数据类型一样,也是 string 类型元素的集合,但在其基础之上,加了一个score(double 类型),之前 set 是k1 v1 v2 v3,现在 zset 是 k1 score1 v1 score2 v2

通过这个 score,redis 将 Set 中的成员从小到大进行排序(这也是为什么说 Zset 是有序的原因啦)

特点:zset 的成员是唯一的,但分数(score)却可以重复。

img

  • 使用场景

Redis sorted set 的使用场景与 set 类似,区别是 set 不是自动有序的,而 sorted set 可以通过用户额外提供一个优先级(score)的参数来为成员排序,并且是插入有序的,即自动排序。当你需要一个有序的并且不重复的集合列表,那么可以选择 sorted set 数据结构,

另外还可以用 Sorted Sets 来做带权重的队列,比如普通消息的 score 为 1,重要消息的 score 为 2,然后工作线程可以选择按 score 的倒序来获取工作任务。让重要的任务优先执行。

通常用于:

排行榜:有序集合经典使用场景。例如小说视频等网站需要对用户上传的小说视频做排行榜,榜单可以按照用户关注数,更新时间,字数等打分,做排行。

twitter 的 public timeline可以以发表时间作为 score 来存储,这样获取时就是自动按时间排好序的。

  • 实现方式

Redis sorted set 的内部使用 HashMap 和跳跃表(SkipList)来保证数据的存储和有序,HashMap 里放的是成员到 score 的映射,而跳跃表里存放的是所有的成员,排序依据是 HashMap 里存的 score,使用跳跃表的结构可以获得比较高的查找效率,并且在实现上比较简单。

Redis 的【数据结构】

  • 数据结构与数据类型关系

    上面学习的五种数据类型,底层依靠这 6 种数据结构去实现;

简单动态字符串 - SDS

  • 基本概念

传统 C 语言的字符串以空字符结尾,而 Redis 自己重新构建了一种新的字符串结构,命名为简单动态字符串(Simple Dynamic String, SDS),将这种新型的字符串结构作为 Redis 的默认字符串表示

在 Redis 中,C 字符串只会用在一些无须修改的地方,比如打印常量:

1
redisLog(REDIS_WARNING,"Redis is now ready to exit, bye bye...");

如果是需要修改的地方,会使用 SDS 来表示:

1
2
redis> RPUSH fruits "apple" "banana" "cherry"
(integer) 3

Redis 将在数据库中创建一个新的键值对,其中:

  • key 是一个字符串对象,底层保存了一个字符串 fruits 的 SDS。
  • value 是一个列表对象列表包含了三个字符串对象,由 SDS 实现。
  • SDS 底层

SDS 是一个结构体,定义在sds.h/sdshdr

1
2
3
4
5
6
7
8
9
struct sdshdr {
// 记录 buf 数组中已使用字节的数量
// 等于 SDS 所保存字符串的长度
int len;
// 记录 buf 数组中未使用字节的数量
int free;
// 字节数组,用于保存字符串
char buf[];
};

下面给出了一个示例,free 为 0 代表所有空间都被使用,len 长度为 5,表示 SDS 保存的字符串长度为 5,buf 就是字符串实体。

在这里插入图片描述

保存空字符的 1 字节空间不计算在 len 属性内。遵循空字符结尾这一惯例的好处是, SDS 可以直接重用一部分 C 字符串函数库里面的函数。

比如我们不需要对 SDS 专门设置打印函数。

1
printf("%s",s->buf);
  • SDS 与 C 字符串区别
  1. C 字符串获取长度的能力有限

    • 因为 C 字符串并不记录自身的长度信息,所以为了获取一个 C 字符串的长度,程序必须遍历整个字符串,对遇到的每个字符串进行计数,直到遇到代表字符串结尾的空字符串为止,这个操作的时间复杂度为:$O(N)$
    • 而 SDS 本身记录了 len,所以时间复杂度$O (1)$,常数时间
  2. 杜绝缓冲区溢出

    由于 C 字符串不记录长度,当我们拼接两个字符串的时候,容器可能因为空间不足发生溢出。redis 中的sdscat将在执行拼接操作前检查长度是否充足,若不足则先拓展空间,再拼接。

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

    C 字符串类似于数组,每次修改大小都会重新分配以此内存。

    • 如果程序执行的是增长字符串的操作,程序需要先通过内存重分配来扩展底层数组组的空间大小,如果忘了这一步就会产生缓冲区溢出
    • 如果程序执行的是缩短字符串的操作,程序需要通过内存重分配来释放字符串不再使用的那部分空间,如果忘了这一步就会产生内存泄露

    Redis 的分配原理类似于std::vector,通过空间预分配的办法优化字符串增加(不仅分配修改所必须的空间,还分配额外的使用空间),分配规则如下:

    • 若 len 比较小(小于 1MB),则 free 是 len 一样大。如果修改后 len 为 13 字节,则 free 也为 13 字节,buf 实际长度为 13+13+1=27 字节。
    • 若 len 比较大(大于 1MB),则每次 free 只会有 1MB,比如修改后 len 为 30MB,则 free 为 1MB,总长度为 30MB+1MB+1byte。

    此外,使用惰性空间释放优化字符串缩短。当缩短时,将释放的空间放入 free 中保存起来,等待使用。

  4. 二进制安全

    C 字符串以空字符\0结尾,使得 C 字符串只能保存文本数据, 而不能保存像图片、音频、视频、压缩文件这样的二进制数据。我们希望有一种使用空字符来分割多个单词的特殊数据格式。换句话说,数据写入时什么样,读取时就是什么样

    SDS 利用 len 来判断是否结束,而不是空字符\0

    img

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

链表 - List

  • 基本概念

链表提供了高效的节点重排能力,以及顺序性的节点访问方式,并且可以通过增删节点来灵活地调整链表的长度

链表键的底层实现之一就是链表。当一个列表键包含了数量比较多的元素,又或者列表中包含的元素都是比较长的字符串时,Redis 就会使用链表作为列表键的底层实现

此外,发布与订阅、慢查询、监视器等功能也用到了链表,Redis 服务器本身还使用链表来保存多个客户端的状态信息,以及使用链表来构建客户端输出缓冲区

  • 底层实现

链表节点定义在adlist.h/listNode,如下:

1
2
3
4
5
6
7
8
typedef struct listNode {
// 前置节点
struct listNode *prev;
// 后置节点
struct listNode *next;
// 节点的值
void *value;
} listNode;

虽然可以多个 Node 组成链表,但是为了方便,Redis 设计了adlist.h/list 来持有链表:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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;

在这里插入图片描述

  • Redis 链表特点
特点 描述
双端 链表节点带有 prev 和 next 指针,获取某个节点的前置节点和后置节点的复杂度都是 O(1)
无环 表头节点的 prev 指针和表尾节点的 next 指针都指向 NULL,对链表的访问以 NULL 为终点
自带头尾指针 通过 list 结构的 head 指针和 tail 指针,程序获取链表的表头节点和表尾节点的复杂度为 O(1)
带链表长度计数器 程序使用 list 结构的 len 属性来对 list 持有的链表节点进行计数,程序获取链表中节点数量的复杂度为 O(1)
多态 链表节点使用 void*指针来保存节点值,并且可以通过 list 结构的 dup、free、match 三个属性为节点值设置类型特定函数,所以链表可以用于保存各种不同类型的值(泛型编程)

字典 - Hash

  • 基本概念

字典(映射)是一种用于【保存键值对】的抽象数据结构

在字典中,一个键可以和一个值进行关联,这些关联的键和值就称为键值对,字典中的每个键都是独一无二的

Redis 的数据库就是使用字典来作为底层实现的,对数据库的 CRUD 操作也是构建在对字典的操作之上的

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

  • 哈希表底层实现

Redis 字典所使用的哈希表dict.h/dictht 结构定义:

1
2
3
4
5
6
7
8
9
10
11
typedef struct dictht {
// 哈希表数组
dictEntry **table;
// 哈希表大小
unsigned long size;
// 哈希表大小掩码,用于计算索引值
// 总是等于 size - 1
unsigned long sizemask
// 该哈希表已有节点的数量
unsigned long used;
} dictht;

table 是一个数组, 数组中的每个元素都是一个指向 dict.h/dictEntry 结构的指针。

dictht图示

  • 哈希表节点底层实现

字典中含有数组,数组包含着一个个的元素,每个元素都是一个指向 dict.h/dictEntry 结构的指针。

这里提及的dictEntry,翻译过来叫字典健,即哈希表节点,每个dictEntry保存着一个键值对:

1
2
3
4
5
6
7
8
9
10
11
12
typedef struct dictEntry {
// 键
void *key;
// 值
union {
void *val;
uint64_t u64;
int64_t s64;
} v;
// 指向下个哈希表节点,形成链表
struct dictEntry *next;
} dictEntry;

v 属性则保存着键值对中的值, 值可以是一个指针, 或者是一个 uint64_t 整数, 又或者是一个 int64_t 整数。

next 属性是指向另一个哈希表节点的指针, 这个指针可以将多个哈希值相同的键值对连接在一次, 以此来解决键冲突(collision)的问题

EG:下图中键的索引值都是 2,通过链表的形式完成了冲突的规避。

img

  • 字典底层实现

Redis 中的字典由 dict.h/dict 结构表示:

1
2
3
4
5
6
7
8
9
10
11
typedef struct dict {
// 类型特定函数
dictType *type;
// 私有数据
void *privdata;
// 哈希表
dictht ht[2];
// rehash 索引
// 当 rehash 不在进行时,值为 -1
int rehashidx; /* rehashing not in progress if rehashidx == -1 */
} dict;

其中type 属性和 privdata 属性是针对不同类型的键值对, 为创建多态字典而设置的

type 属性是一个指向 dictType 结构的指针, 每个 dictType 结构保存了一簇用于操作特定类型键值对的函数。

privdata 属性则保存了需要传给那些类型特定函数的可选参数。

dictTyoe属性保存了类型特定的函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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 *privdata, void *key);
// 销毁值的函数
void (*valDestructor)(void *privdata, void *obj);
} dictType;

ht属性是一个包含了两个项的数组,数组中的每个项都是一个 dictht 哈希表,一般情况下, 字典只使用 ht[0] 哈希表, ht[1] 哈希表只会在对 ht[0] 哈希表进行 rehash 时使用。

rehashidx属性记录了 rehash 目前的进度,如果目前没有在进行 rehash,那么它的值为-1

下图展示了一个普通状态下(没有 rehash)的字典

img

  • Hash 算法

程序需要先根据键值对的键计算出哈希值和索引值, 然后再根据索引值, 将包含新键值对的哈希表节点放到哈希表数组的指定索引上面。

键 key → Hash 值;键 key → Index 值

Redis 计算 Hash 值和 Index 值方法如下:

1
2
3
4
5
6
// 使用字典设置的哈希函数,计算键 key 的哈希值
hash = dict->type->hashFunction(key);

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

举个例子,假如想要将键值对k0v0 添加到下面的字典中。

假设计算出的 hash 值是 8,则 index 为

1
index = hash & dict->ht[0].sizemask = 8 & 3 = 0;

至于 Redis 的哈希值计算方法,使用的是 MurmurHash2这种算法的优点在于, 即使输入的键是有规律的, 算法仍能给出一个很好的随机分布性, 并且算法的计算速度也非常快。

  • 解决 Key 冲突

当有两个或以上数量的键被分配到了哈希表数组的同一个索引上面时,我们称这些键发生了冲突

Redis 的哈希表使用链地址法来解决键冲突,每个哈希表节点都有一个 next 指针,多个哈希表节点可以用 next 指针构成一个单向链表,被分配到同一个索引上的多个节点可以用这个单向链表连接起来,这就解决了键冲突的问题

因为 dictEntry 节点组成的链表没有指向链表表尾的指针,所以为了速度考虑,程序总是将新节点添加到链表的表头位置(复杂度为 O(1)),排在其他已有节点的前面

使用链表解决 k2 和 k1 的冲突:

还未插入k2

插入了k2

  • Rehash

Rehash 的意义:随着操作的不断执行, 哈希表保存的键值对会逐渐地增多或者减少, 为了让哈希表的负载因子(load factor)维持在一个合理的范围之内, 当哈希表保存的键值对数量太多或者太少时, 程序需要对哈希表的大小进行相应的扩展或者收缩。

再哈希的关键在于重新分配哈希表的大小,分配的原则如下:

  • 如果执行拓展操作ht[1] 的大小为第一个大于等于 ht[0].used * 2 的 $2^n$,比如原表大小为 4,则 ht[0].used * 2结果为 8,而 8 刚好是$2^3$,所以新的大小是 8。
  • 如果执行的是收缩操作, 那么 ht[1] 的大小为第一个大于等于 ht[0].used 的$2^ n$

完成分配后,将保存在 ht[0] 中的所有键值对 rehashht[1] 上面,然后 将 ht[1] 设置为 ht[0] , 并在 ht[1] 新创建一个空白哈希表, 为下一次 rehash 做准备。

决定是否再 Hash 的要素来自于负载因子,计算方法如下:

1
2
//负载因子 = 哈希表已保存节点数量 / 哈希表大小
load_factor = ht[0].used / ht[0].size
  • 渐进式 Rehash

如果键值对很多,则将ht[0]重新 hash 到ht[1]上,则会导致服务器在一段时间内停止服务。为了避免这种问题,需要分多次渐进式的慢慢映射。

关键点在于维持一个索引计数器变量 rehashidx , 并将它的值设置为 0 , 表示 rehash 工作正式开始。

在 rehash 进行期间, 每次对字典执行增删改查, 程序除了执行指定的操作以外, 还会顺带将 ht[0] 哈希表在 rehashidx 索引上的所有键值对 rehash 到 ht[1] , 当 rehash 工作完成之后, 程序将 rehashidx 属性的值增一

完成后程序将 rehashidx 属性的值设为 -1 , 表示 rehash 操作已完成。

渐进式 rehash 的好处在于它采取分而治之的方式, 将 rehash 键值对所需的计算工作均滩到对字典的每个增删改查上, 从而避免了集中式 rehash 而带来的庞大计算量。

跳跃表 - SkipList

  • 引入与基本概念

跳跃表的引入

我们知道链表随机读写的能力很差,当增删改查的时候,如果要找到目标元素就需要遍历链表。假设某个数据结构是有序的,我们就会想到用二分法来快速查找,但链表是没有索引的,所以我们需要添加。

而提取索引的方法也非常简单,每个一个节点就提取出来一个元素到上一层,那么这一层就称为索引,索引中含有down指针,用于指向原始链表

可以继续向上拓展层数:

img

但是我们的链表不是静态的,增加和删除会破坏二分结构,所以我们就不强制要求 1:2 了,一个节点要不要被索引,建几层的索引,都在节点插入时由随机决定具体细节是:通过随机函数生成一个随机数 K,然后将要插入的数据同时插入到 k 级以下的每级索引中。

现在假设节点 17 是最后插入的,在插入之前,我们需要搜索得到插入的位置:

img

跳跃表的概述

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

跳跃表支持平均$O(logN) O(logN)O(logN)$、最坏$O(N)$复杂度的节点查找,还可以通过顺序性操作来批量处理节点

Redis 使用跳跃表作为有序集合键的底层实现之一,如果一个有序集合包含的元素数量比较多,又或者有序集合中元素的成员是比较长的字符串时,Redis 就会使用跳跃表来作为有序集合键的底层实现

Redis 只在两个地方用到了跳跃表,一个是实现有序集合键,另一个是在集群节点中用作内部数据结构

  • 底层实现

Redis 的跳跃表由 redis.h/zskiplistNoderedis.h/zskiplist 两个结构定义

img

其中 zskiplistNode 结构用于表示跳跃表节点, 而 zskiplist结构则用于保存跳跃表节点的相关信息, 比如*节点的数量 length(表头不算), 指向表头节点和表尾节点的指针 headerr 和 tail 以及 level 属性,记录着目前跳跃表内最大的层数(表头不算) *(类比上面的字典,其中一个数据结构 dicEntry 保存节点信息,dic 用于保存字典信息)

结构如下:

1
2
3
4
5
6
7
8
typedef struct zskiplist {
// 表头节点和表尾节点
struct zskiplistNode *header, *tail;
// 表中节点的数量
unsigned long length;
// 表中层数最大的节点的层数
int level;
} zskiplist;

zskiplistNode则包含以下的属性:

  1. 层:每层包含两个属性

    • 前进指针:用于访问位于表尾方向的其他节点(next 指针)
    • 跨度:记录前进指针所指向节点与当前结点的【距离】
  2. 后退指针(BW):指向位于当前节点的【前一个节点】,该指针用于程序从表尾 → 表头遍历使用 (pre 指针)

  3. 分值 score:各个节点中的 1.02.03.0 是节点所保存的分值。用于从小到大排列。如果分值相同,则成员对象小的排在前面。

  4. 成员对象(obj):各个节点中的 o1o2o3 是节点所保存的成员对象。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
typedef struct zskiplistNode {
// 后退指针
struct zskiplistNode *backward;
// 分值
double score;
// 成员对象
robj *obj;
// 层
struct zskiplistLevel {
// 前进指针
struct zskiplistNode *forward;
// 跨度
unsigned int span;
} level[];
} zskiplistNode;

(1)层

每次创建一个新跳跃表节点的时候, 程序都根据幂次定律 (power law越大的数出现的概率越小随机生成一个介于 132 之间的值作为 level 数组的大小, 这个大小就是层的“高度”。

下图展示了三个高度为 1 层、 3 层和 5 层的节点

层

(2)前进指针

前进指针分属于不同的层,level[i].forward,用于从表头向表尾方向访问节点。

下图中用虚线表示出了程序从表头向表尾方向,遍历跳跃表中所有节点的路径

前进指针

(3)跨度

跨度也分属不同的层,指向 NULL 的所有前进指针的跨度都为 0, 因为它们没有连向任何节点。

跨度实际上是用来计算位次(rank)的: 将沿途访问过的所有层的跨度累计起来, 得到的结果就是目标节点在跳跃表中的排位。

下图的例子中,查找分值为 3.0 的节点,由于只经过了一个层,跨度为 3,所以跳跃表中的排位为 3。

跨度

(4)后退指针

节点的后退指针用于从表尾向表头方向访问节点:跟可以一次跳过多个节点的前进指针不同,因为每个节点只有一个后退指针,所以每次只能后退至前一个节点

后退指针

(5)分值和成员

节点的分值是一个 double 类型的浮点数,跳跃表中的所有节点都按分值从小到大来排序

节点的成员对象是一个指针,它指向一个字符串对象,而字符串对象则保存着一个 SDS 值

在同一个跳跃表中,各个节点保存的成员对象必须是唯一的,但是多个节点保存的分值却可以是相同的:分值相同的节点将按照成员对象在字典序中的大小来进行排序,成员对象较小的节点会排在前面(靠近表头的方向),而成员对象较大的节点则会排在后面(靠近表尾的方向)

整数集合 - IntSet

  • 基本概念

当一个集合中只包含整数,并且元素的个数不是很多的话,redis 会用整数集合作为底层存储,它可以节省很多内存。

1
2
3
4
127.0.0.1:6379> SADD numbers 1 3 5 7 9
(integer) 5
127.0.0.1:6379> OBJECT ENCODING numbers
"intset"
  • 底层实现

整数集合(intset)是 Redis 用于保存整数值的集合抽象数据结构, 它可以保存类型为 int16_tint32_t 或者 int64_t 的整数值, 并且保证集合中不会出现重复元素。

每个 intset.h/intset 结构表示一个整数集合:

1
2
3
4
5
6
7
8
typedef struct intset {
// 编码方式
uint32_t encoding;
// 集合包含的元素数量
uint32_t length;
// 保存元素的数组
int8_t contents[];
} intset;

contents 数组是整数集合的底层实现: 整数集合的每个元素都是 contents 数组的一个数组项(item), 从小到大有序地排列,不包含任何重复项。

length 属性记录了整数集合包含的元素数量,也即是 contents 数组的长度

虽然 intset 结构将 contents 属性声明为 int8_t 类型的数组, 但实际上 contents 数组并不保存任何 int8_t 类型的值 —— contents 数组的真正类型取决于 encoding 属性的值

  • encodingINTSET_ENC_INT16int16_t 类型的数组,范围$[-2^{16},2^{16}-1]$
  • encoding INTSET_ENC_INT32 , 是一个 int32_t 类型的数组。
  • encodingINTSET_ENC_INT64 , 是一个 int64_t 类型的数组

下图展示了一个示例:

  • 升级

每当我们要将一个新元素添加到整数集合里面, 并且新元素的类型比整数集合元素的类型长时, 整数集合需要先进行升级(upgrade), 然后才能将新元素添加到整数集合里面。

过程如下:

  1. 根据新类型,扩展整数集合底层数组的空间大小, 并为新元素分配空间
  2. 将底层数组现有的所有元素都转换成与新元素相同的类型, 并将类型转换后的元素有序放置。
  3. 将新元素添加到底层数组里面。

举个例子来说的话:

一个包含三个 int16_t 类型的元素的整数集合:

sample

contents 数组的各个元素,以及它们所在的位:

(一开始的元素每个占 16 位)

元素初始位置

进行空间重分配之后的数组:

空间重分配

然后从 int16_t 类型转换为 int32_t 类型:

(每个元素从之前占 16 位,升级成占 32 位)

元素迁移 、 合并

转换

最后添加新元素到数组中:

添加元素

整数集合的升级策略有两个好处,一个是提升整数集合的灵活性,另一个是尽可能地节约内存

  • 降级

整数集合不支持降级操作, 一旦对数组进行了升级, 编码就会一直保持升级后的状态。

即使我们将集合里唯一一个真正需要使用 int64_t 类型来保存的元素 4294967295 删除了, 整数集合的编码仍然会维持 INTSET_ENC_INT64

压缩列表 - ZipList

【bonus】Linux 服务器中 Redis 的安装

使用的是 Xshell 远程连接阿里云服务器,配合 Xftp 搭配使用学习

创建 Redis 文件夹

  1. cd /user (注意 cd 后有个空格)
  2. mkdir redis (创建 redis 文件夹)

image-20210816172853637

下载 Redis 安装包、环境并解压

  1. cd /usr/redis //切换到 redis 目录下

  2. wget https://download.redis.io/releases/redis-5.0.8.tar.gz //下载安装包

  3. tar xzf redis-5.0.8.tar.gz //解压 redis 安装包

    image-20210816173120202

  4. yum install gcc-c++ //安装基本的 gcc 环境

  5. .gcc -v //查看自己 gcc 环境安装的版本

    image-20210816173251575

  6. cd redis-5.0.8 //切换到 redis 文件中

  7. make //编译

    image-20210816173426687

  8. make install //查看编译是否成功

    image-20210816173510827

  9. cd /usr/local/bin //切换到 bin 目录下

  10. mkdir rconfig //创建 redis 配置文件目录

    ![image-20210816173821112](

    https://er11.oss-cn-shenzhen.aliyuncs.com/img/image-20210816173821112.png)

  11. cp /usr/redis/redis-5.0.8/redis.conf rconfig //将 redis.conf 配置文件放到 bin 目录下,我们之后就是用这个文件启动 redis

  12. ls 启动

  13. cd rconfig // 进入配置文件

  14. ls 启动

    ![image-20210816174121193](

    https://er11.oss-cn-shenzhen.aliyuncs.com/img/image-20210816174121193.png)

修改配置文件【rconfig】

修改 redis 配置文件将 redis 修改为后台启动进程,确保不会终止它.

  1. cd /usr/local/bin/rconfig //切换到 redis 的配置文件下
  2. vim redis.conf //编辑 redis 配置文件

在这里由于我有 xftp 软件,我就不那么麻烦使用指令了,直接打开配置文件修改就好咯

image-20210816174434541

在这个文件中,找到GENERAL中的 守护进程daemonize,将no 改成 yes,这样子该进程就可以一直在后台跑了

image-20210816174538329

同时,我们需要注释掉本地连接:

befor:

image-20210818155831846

after:

image-20210818155850671

如果不想通过密码登录,需要取消保护模式:

image-20210818232312397

启动 redis 服务

  1. cd /usr/local/bin //切换到 bin 目录下
  2. redis-server rconfig/redis.conf //通过 redis 的配置文件来启动 redis

image-20210816180303309

使用 redis-cli 进行连接测试

  1. cd /usr/local/bin //切换到 bin 目录下
  2. redis-cli -p 6379 //通过端口号进行连接
  3. ping //显示连接

image-20210816180455106

设置 redis 开机自动登录

前面我们的 redis 是没有配置自动登录的,意味着每次都需要手动去开启登录,那么有什么办法可以解决这一问题呢?

答案是使用脚本,自动登录

  • 修改文件

首先进入以下目录 找到【redis_init_scipt.tpl】

对照修改:

1
2
3
4
5
6
7
8
9
10
redis_init_script文件修改以下内容:
1.在脚本的第二行增加:# chkconfig 2345 90 10
该行代码的意思是:redis服务必须在运行级2,3,4,5下被启动或关闭,启动的优先级是90,关闭的优先级是10。
2.设置redis服务端口:REDISPORT=6379
3.修改Redis执行路径,如果默认安装在/usr/local/bin/目录下则不需要修改,我是默认安装在/usr/local/bin/目录下的,因此,就直接复制以下即可:
EXEC=/usr/local/bin/redis-server
CLIEXEC=/usr/local/bin/redis-cli
4.Redis配置端口与文件:
PIDFILE=/var/run/redis_${REDISPORT}.pid
CONF="/etc/redis/${REDISPORT}.conf"

image-20210822161436606

  • 新增文件

进入到 Redis 解压目录下,创建目录 etc/redis

image-20210822162013823

接着输入指令: cp redis.conf /etc/redis/6379.conf

把 redis.conf 复制到目录 tec/redis 的 6379.conf 中 结果如下:

image-20210822162213093

将其中的 conf 文件进行修改:

image-20210822162522832

image-20210822162542795

  • 复制脚本到启动目录

(需要在 Redis 的解压目录下执行)

cp ./utils/redis_init_script /etc/init.d/redisd

image-20210822162708267

  • 向防火墙添加 Redis 端口,刷新防火墙规则,查询防火墙开放端口

$ firewall-cmd –zone=public –add-port=6379/tcp –permanent

$ firewall-cmd –reload

$ firewall-cmd –zone=public –list-port

image-20210822162856191

  • 设置开机自启动
1
chkconfig redisd on
  • 开启 Redis 服务

image-20210822163035809

  • 检验是否自启动成功

我们把阿里云服务器重启了一遍,不输入启动 Redis 的命令,直接去检测 Redis 端口:

image-20210822163359670

发现 Redis 是自己启动了的

参考