0.简介
Remote Dictionary Server(Redis) 是一个 由C语言编写的key-value存储系统。
Redis特点:
- Redis将其数据库完全保存在内存中,仅使用磁盘进行持久化。【持久,即把数据(如内存中的对象)保存到可永久保存的存储设备中(如磁盘)。持久化的主要应用是将内存中的对象存储在数据库中,或者存储在磁盘文件中、XML数据文件中等等。】
- 与其它键值数据存储相比,Redis有一组相对丰富的数据类型。【其他数据库不行吗?】
- Redis可以将数据复制到任意数量的从机中。【其他数据库不行吗?】
Redis的数据都是缓存在内存中。周期性的把更新的数据写入磁盘或者把修改操作写入追加的记录文件,并且在此基础上实现了master-slave(主从)同步。
1.数据结构与对象
1.1.Redis简单动态字符串
redis创建了一个简单动态字符串(simple dynamic string,SDS)来保存字符串,而没有直接采用C 语言传统的字符串表示(以空字符结尾的字符数组,以下简称 C 字符串)。SDS数据结构如下:
struct sdshdr{
//buf已使用的字节数
int len;
//buf未使用的字节数
int free;
//字节数组,用于保存字符串
char buf[];
}
SDS数据结构中记录着数组buf中已使用的字节和未使用的字节。
len和free是根据输入的字符串自动生成的。
SDS 与 C 字符串的区别:
1.常数复杂度获取字符串长度。SDS获取一个 SDS 长度的复杂度仅为 O(1)。对于C字符串,由于C字符串不会记录自身长度,因此只能遍历,直到遇到结尾的空字符为止,时间复杂度为O(N)
2.SDS杜绝缓冲区溢出。由于C字符串未记录自身长度,容易导致缓冲区溢出。在执行字符串拼接时,如果没有足够的空间,并且相邻内存地址被其他字符串占用时,字符串的数据将溢出,且容易意外修改相邻的字符串内容。相比而言,SDS会将这种情况扼杀在摇篮之中,SDS API先判断空间是否满足,如果不满足则将空间扩展至执行修改所需的大小。
3.减少修改字符串时带来的内存重分配次数
空间预分配(优化字串增长):程序不仅会为 SDS 分配修改所必须要的空间, 还会为 SDS 分配额外的未使用空间。在扩展 SDS 空间之前,SDS API 会先检查未使用空间是否足够, 如果足够的话, API 就会直接使用未使用空间, 而无须执行内存重分配。具体为:
- 增加字串长度以后,字串的长度L小于1MB时,则分配2L+1个字节,(额外的一字节用于保存空字符);
- 字串的长度L大于等于1MB时,则分配L+1MB+1B的空间(额外的一字节用于保存空字符)
惰性空间释放(优化字串缩短):当 SDS 的 API 需要缩短 SDS 保存的字符串时, 程序并不立即使用内存重分配来回收缩短后多出来的字节, 而是使用 free 属性将这些字节的数量记录起来, 并等待将来使用。
4.SDS API都是二进制安全的。
C字符串的字符必须符合某种编码,并且中间不能有空字符,否则读取时会被误以为是字符串结尾。种种局限使得C字符串只能存文本,不能存图片,音频,视频,压缩文件等二进制数据。 为确保Redis对不同使用场景的支持,SDS API都是二进制安全的,也就是所有SDS API都会以二进制的方式存取buf中的数据,数据的写入和读出都是一个样的。由于SDS读取时并不是依靠空字符来判断结束的,而是len属性,所以是二进制安全的。
5.兼容部分C字符串函数。
SDS虽然都是二进制安全的,但也遵循以空字符结尾的习惯。SDS API总会在buf数组分配空间时多分配一个字节用于容纳空字符,这是为了保存文本的SDS重用一部分<string.h>库函数,避免代码重复。
SDS API中介绍操作SDS的函数
1.2.Redis 链表和链表节点的实现
当一个列表键包含了数量比较多的元素,或者列表中包含的元素都是比较长的字符串时,Redis就会使用链表作为列表键的底层实现。
每个链表节点使用一个 adlist.h/listNode 结构来表示:
typedef struct listNode {
// 前置节点
struct listNode *prev;
// 后置节点
struct listNode *next;
// 节点的值
void *value;
} listNode;
adlist.h/list链表的数据结构:
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;