Redis学习笔记：基础篇数据结构与对象_embstr 是哪两个单词

环境

window10+

前言

开始研究Redis了；

Redis的数据都是键值对，对象类型应该指的是值对象类型；

SDS 简单动态字符串

simple dynamic string

简单动态字符串：简称SDS

Redis底层是用C语言写的，并且字符串Redis自己实现了一套。

为什么要自己实现一套呢？有以下几个原因：

① C语言的字符串是没办法立马知道字符串长度的，需要利用遍历整个字符串来进行计算；
② C语言的库方法在执行字符串拼接时，是需要手动分配足够的内存才行，否则就会产生缓冲区溢出。即修改了内存中其他地址的值。
③ C语言的字符串保存的二进制数据是不安全的；
④ 每次都进行内存的重分配非常耗性能，Redis利用free属性来减少内存重分配次数；

内存重分配是个双向的概念：一、增加内存，对于操作 字符串拼接；二、减少内存，对于操作字符串减少。

什么是二进制安全：
以C语言来说，strlen函数就不算是binary safe的，因为它依赖于特殊的字符’\0’来判断字符串是否结束，所以对于字符串str = "1234\0123"来说，strlen(str)=4；
而在php中，strlen函数是binary safe的，因为它不会对任何字符（包括'\0'）进行特殊解释，所以在php中，strlen(str)=8
知乎上网友总结的一句话：只关心二进制化的字符串,不关心具体格式.只会严格的按照二进制的数据存取。不会妄图已某种特殊格式解析数据

二进制安全(binary safe)是什么意思？ - 夏大雨的回答 - 知乎
https://www.zhihu.com/question/28705562/answer/41806793

以下是Redis自己定义的用来保存字符串的C语言的结构体：

struct sdshdr {
	// 记录buf数组中已使用的字节数的数量
	// 等于SDS所保存字符串的长度
	int len;
	
	// 记录buf数组中未使用字节的数量
	int free;

	// 字节数组，用于保存字符串
	char buf[];
}
1
2
3
4
5
6
7
8
9
10
11

Redis之所以能做到二进制安全，因为SDS使用len属性的值而不是空字符来判断字符串是否结束。

redis的 所有的SDS API都是二进制安全的。

链表

因为C语言没有内置链表的数据结构，所以Redis自己实现了一个；

Redis的链表，是单向的，不是环状的，所以对链表的访问是以null结束的。

字典

和Java中hashmap有异曲同工之妙，并且在扩容方面有些差异，具体可以参考：
Redis学习笔记：字典rehash底层实现与Java区别

其数据结构如下图：

key：是一个指针
value：支持：指针，无符号整数和有符号整数；

字典结构：

typedef struct dict {
	// 类型特定函数
	dictType *type;
	// 私有数据
	void * privdata;

	// 哈希表
	dictht ht[2];
	// rehash索引
	// 当rehash不在进行时，值为-1
	int trehashidx;
} dict;
1
2
3
4
5
6
7
8
9
10
11
12

哈希表结构：

typedef struct dict ｛
	// 哈希表数组
	dictEntry **table;
	// 哈希表大小
	unsigend long size;
	// 哈希表大小掩码
	unsigend long sizemask;
	// 该哈希表已有节点的数量
	unsigned long used;
｝dictht;
1
2
3
4
5
6
7
8
9
10

哈希表节点结构：

typedef struct dictEntry ｛
	void * key;
	union{
		void *val;
		uint64_t u64;
		int64_t s64;
	} v;
	struct dictEntry *next;
｝dictEntry;
1
2
3
4
5
6
7
8
9

跳跃表

跳跃表在Redis（版本3）中使用场景很少，只在有序集合和集群节点内部才使用；

这里我不由得思考一个问题：为什么Redis有序集合要使用跳跃表？；

个人认为：
① 代码实现上，红黑树、平衡二叉树实现起来很复杂
② 区间访问的查找，跳跃表效率更高，因为其可以跨越过个节点建立索引，而平衡二叉树只能相隔两个节点来建立索引
③ 插入操作时，跳跃表只需要修改前后指针，而平衡树得左旋或右旋来来实现平衡。

跳跃表由两部分组成：zskiplist 和 zskiplistNode；
跳跃表结构：

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

跳跃表节点结构：

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

zskiplist : 记录跳跃的信息；
如：表头指针，表尾指针、节点数量、最大层数节点的层数。

zskiplistNode: 记录节点信息；也就是具体的数据信息；
如：层（包括：前进指针、跨度）、后退指针、对象、分值；

成员对象：就是我们要保存的具体数据；
分值：可以理解为对象的权重；作用就是用来排序的；

层的跨度：两个节点之间的距离；跨度是用来计算排位的，即目标节点在跳跃表中的排位；

后退指针：前进指针可以跳跃多个节点，而后退指针，只能一层一层的后退；

整数集合

叫：intset

这是一个只储存数字的小集合；

Q：当集合变得很大时，会转成什么？

该集合底层支持3种int类型格式；
① int16 ②int32 ③int64

数据结构如下：

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

上面的结构中，虽然contents被int8_t 声明，但是其并不保存任何int8的数据，真正的数据是上面写的当个类型。具体哪个类型，由encoding，来决定的；

之所以有三种int类型，目的也是为了节约内存；当要保存的值超过了当前类型的范围时，Redis会自动升级类型；但是只升级不缩减；
举个例子：假设intset 一开始保存的是 99 100 122 这三个数字，int16类型就足够了，
但是现在插入一个65536 这个数字，超过了int16表示的范围，这个时候Redis会先升级contents数组的类型，然后再移动原有的数字到相应的位（bit)上，接着再插入新数字65536；

升级后新插入的数字，就两种情况，要么比所有的元素大，要么比所有元素小（负数的情况）；
前者是插入到数组最后面，后者是插入到索引为0的位置；

压缩列表

ziplist

encoding：
① 字节数组编码
② 整数编码

当保存值中有数字又有字符串时，那么肯定使用的是字节数组编码；
当保存的值都是数字时，使用的整数编码；

在Redis高版本中，又加入了一个新的列表，quicklist；

对象

Redis保存的任何数据都是键值对的形式，那么这也就意味着其会创建两个对象：
① 键 对象
② 值 对象

那么对象结构是什么样的呢？

typedef struct redisObject {
	// 类型
	unsigned type:4;
	// 编码
	unsigned encoding:4;
	// 指向底层实现数据结构的指针
	void *ptr;
	... ...
}
1
2
3
4
5
6
7
8
9

和保存数据相关只有上面三个字段，所以其他字段没有列举出来；

type 类型只有五种，也就是Redis那5种类型：
① 字符串对象 ② 列表对象 ③哈希对象 ④ 集合对象 ⑤有序集合对象

encoding: 这个属性决定了 ptr指针指向对象的底层实现是哪个数据结构；

根据上面的总结，Redis支持的数据结构有：SDS、双端链表、字典、跳跃表、压缩列表、整数集合；
外加上C语言自带的，long类型整数；

字符串对象

字符串对象encoding属性可以是：int、raw和embstr，这三种编码；

int ： 保存的值是一个long整数

embstr：保存的值是一个字符串并且字节小于等于39字节；

raw：保存的值是字符串，并且字节大于39字节；

Q：embstr和raw区别？
A：embstr是专门用来保存短字符串的一种优化编码方式。
raw编码会调用两次内存分配函数来分别创建redisObject结构和sdshdr结构，
而embstr编码则通过调用一次内存分配函数来分配一块连续的内存空间，
空间依次包含redisObject和sdshdr两个结构。

注意的场景：

① 当保存的是浮点数时，Redis会将其作为字符串进行保存。
② 当对保存的浮点数进行数学运行（比如加一）时，Redis会先将其转为浮点数，
相加后，再以字符串进行保存；

int、embstr 在某些场景下会转为raw编码

比如当对int的值，执行append这种字符串操作时，那么字符串对象的编码将从int变为raw；

当对embstr编码格式的字符串进行任何修改操作时，其字符串对象编码也将变为raw；

这是因为Redis并没有对embstr编码的字符串对象编写任何相应的修改程序，换句话说，embstr编码的字符串对象实际上是只读的；

列表对象

按照书本执行的命令可以看出，新版的Redis已经不再使用ziplist了；

哈希对象

底层使用的是ziplist或hashtable数据结构；

下图是ziplist结构图

上图插入了两个键值对：
① 键：name 值：tom
② 键：age 值：25

如果采用的是hashtable的底层实现，那么其存储结构如下：

说明：

dictEntry数组中，key,value，都是在dictEntry类里的，其中key和value的数据都是字符串对象。
（key是指向“age"字符串对象的指针，value也是指向一个保存了值为25的字符串对象）

• 哈希对象保存的所有键值对的键和值的字符串长度都小于64字节；
• 哈希对象保存的键值对数量小于512个；

不能满足这两个条件的哈希对象需要使用hashtable编码；
上面两个条件的上限值，可以通过配置文件进行修改；

集合对象

编码支持：intset和hashtable；

hashtable的结构：

从上图可以看出，字典的每个键都是一个字符串对象，每个字符串对象包含了一个集合元素，而字典的值则全部设置为null；

intset结构很简单，就不贴图了；

① 集合对象保存的所有元素都是整数值；
② 集合对象保存的元素数量不超过512个。

以上两个条件同时成立时，底层使用intset数据结构；否则就是要hashtable或者说时字典结构；

有序集合对象

有序集合一定有两样东西：实际存储的数据（成员对象）、分值（用于排序）；

编码支持：ziplist 和 skiplist (dict)

ziplist： 存储数据的结构，和哈希对象使用ziplist编码格式一样的，成员对象和分值是紧挨在一起的；

skiplist: 有序集合在使用跳跃表结构时，还是使用了字典(dict)。

Q : 为什么有序集合在使用跳跃表时，需要同时使用字典结构？
A：为了查询的效率；跳跃表适合范围查询，比如ZRANK，ZRANGE这种命令查询时，能高效执行；但是在进行精准查询时，效率就不行，比如根据成员查询分值。这时跳跃表的时间复杂度为O(logN)，但是字典的话，这种查询只需要O(1)。所以有序集合将两者进行结合来实现高效查询；

① 有序集合保存的元素数量小于128个；
② 有序集合保存的所有元素成员的长度都小于64个字节；

同时满足上面两个条件，则使用ziplist，否则使用zskiplist;

---

数据结构基本看完了，书本中结尾处，介绍了类型判断。
Redis的命令大体上分为两类：
① 通用的命令：type key，任何键都可以执行
② 只能对特定键执行的命令；append 只能对字符串键执行；

正是因为有上面的区别，所以当执行命令时，Redis得进行类型检查；即通过redisObject结构中type属性来做判断；

redisObject {
	type  // 类型
	encoding // 编码
	ptr   // 指向数据的指针
	refcount //引用计数器
	lru    // 记录对象最后一次被命令程序范围的时间；对象空转时长
}
1
2
3
4
5
6
7

refcount 用于内存释放，当为0时，可以被回收
lru: 被命令object idletime 执行时，不会修改lru的值。
当服务器占用内存超过maxmemory选项，且内存回收算法为volatile-lru或者allkeys-lru时，会优先回收lru较高的键进行内存释放；