redis 底层
简单动态字符串 ( simple dynamic string,SDS)
SDS的应用
在redis里,c字符串只会用作字面量,用在不会更改的地方,例如打印日志。
需要修改的字符串,用SDS表示
set msg "hello world"
redis将创建一个键值对,键是一个字符串对象,对象的底层实现是保存着字符串"msg"的SDS
值也是字符串对象,对象的底层实现是保存着字符串"hello world"的SDS
rpush fruits "apple" "banana" "cherry"
键是一个字符串对象,对象的底层实现是保存着字符串"fruits"的SDS
值是一个列表对象,列表对象包含三个字符串对象,字符串对象的底层是三个SDS
AOF缓冲区和客户端的输入缓冲区,也是由SDS实现的
SDS的实现与优点
struct sdshdr{
int len; //buf数组中已使用字节的数量,即字符串长度,不包括 ‘\0‘
int free; //buf数组中未使用字节的数量,也不考虑 ‘\0‘,len=free=5,buf实际长度为11
char buf[]; //字节数组,c风格字符串,末尾是‘\0‘,好处是复用c的字符串函数
};
获取字符串长度O(1)
不会发生缓冲区溢出,例如拼接字符串的时候
二进制安全
可复用部分C字符串函数
减少内存重分配的次数,c字符串的长度增加或减少时都要对内存进行重分配
SDS空间预分配:长度增加时,如果len<1MB,则free=len;如果len>=1MB,则free=1MB。
这样可以减少连续执行字符串长度增加操作所需的内存重分配次数
SDS惰性空间释放:长度减少时,不进行内存重分配,而是记录到free里,
同时也提供了API来真正释放内存,不必担心内存浪费
链表
list元素较多时,或者list元素都是长字符串时,redis就用链表作为list的底层实现,
发布与订阅、慢查询、监视器、保存客户端状态信息、客户端输出缓冲区等都用到了链表
typedef struct listNode{ //双向无环链表节点
struct listNode *prev; //第一个节点的 prev==null
struct listNode *next; //最后一个节点的 next==null
void *value; //void* 可保存各种类型的值
}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;
字典 (又称 符号表symbol table、关联数组associative array、映射map)
redis数据库的底层实现就是字典,
当Hash的元素较多时,或者键或值是长字符串时,redis就用字典作为hash的底层实现
实现:
typedef struct dictht{
dictEntry **table; //哈希表数组
unsigned long size; //哈希表大小
unsigned long sizemask; //掩码,sizemask=size-1
unsigned long used; //已有节点数量
} dictht;
typedef struct dictEntry{
void *key; //键
union{
void *val;
uint64_tu64;
int64_ts64;
} v; //值
struct dictEntry *next; //下个哈希表节点
}
typedef struct dict{
dictType *type; //类型特定函数
void *privdata; //私有数据
dictht ht[2]; //哈希表 平时使用ht[0] rehash时使用ht[1]
in trehashidx; //rehash的进度 不在rehash时值为-1
}
hash算法
当字典用作redis数据库的底层实现,或者Hash键的底层实现时,redis使用MurmurHash2来计算哈希值,这种算法的优点在于即使输入的键是有规律的,算法仍能给出一个很好的随机性,且速度很快。
解决冲突
解决哈希冲突的两种方法:开散列法(又称拉链法,链地址法) 和 闭散列法(开地址法),redis里用的是开散列法。新节点总是添加到链表的表头位置O(1)。
rehash
为ht[1]分配空间,将ht[0]的所有键值对rehash到ht[1]上,然后销毁ht[0],将ht[1]作为新的ht[0],并创建一个新的空白ht[1]
哈希因子 = used / size
当不在执行bgSave或bgRewriteAof命令且哈希因子>=1,或者正在执行bgSave或bgRewriteAof命令且哈希因子>=5时,执行扩展操作
当哈希因子<=0.1时,执行收缩操作
执行bgSave或bgRewriteAof命令时,会创建子进程,操作系统采用写时复制技术,所以此时尽量不要rehash
渐进式rehash
rehash不是一次性集中完成的,rehashidx指向ht[0]已完成rehash的位置,查找时先查ht[0]再查ht[1],添加时只往ht[1]里添加
跳表
平均O(lgn),最坏O(n),
当有序集合的元素数量较多时,或者元素都是长字符串时,redis就用跳表作为有序集合的底层实现
集群节点中也用到跳表
左侧zskiplist结构,包含以下属性:
header指向表头节点
tail指向表尾节点,程序定位表头和表尾的复杂度为O(1)
level记录目前跳表内,层数最大的节点的层数(不包括表头节点)
length记录跳表长度(不包括表头节点),计算跳表长度的复杂度为O(1)
右侧zskiplistNode节点,包含以下属性:
层:L1表示第一层,L2表示第二层...每个层包含前进指针和跨度,图中的数字即为跨度,
跨度记录了前进指针指向的节点和当前节点的距离
每次创建一个新节点时,会根据幂次定律(越大的数出现的概率越小),
随机生成一个介于1到32之间的值作为level数组的大小,即层高。
跨度的作用是计算节点的排位
后退指针:BW表示后退指针,指向相邻的前一个节点,用于从后向前遍历
分值(double型):1.0 2.0 3.0表示分值,从小到大排列
成员对象:o1 o2 o3表示节点保存的成员对象。成员对象是一个指针,指向一个字符串对象,
字符串对象保存一个SDS值。成员对象必须是唯一的,
分值可以相同,相同分值的节点按成员对象的字典序排列
表头节点也有后退指针、分值、成员对象,但不会被用到,所以图中未画出。
整数集合
当集合只包含整数,且元素数量不多时,redis就用整数集合作为集合键的底层实现。
typedef struct intset{
uint32_t encoding; //编码方式
uint32_t length; //元素数量
int8_t contents[]; //保存元素的数组,从小到大排列,不会重复
} intset;
压缩列表
当list或hash的元素数量较少,且每个list项或者每个hash的键和值都是小整数值或者短字符串,redis就用压缩列表作为list或hash的底层实现
对象
typedef struct redisObject {
unsigned type:4; //类型
unsigned encoding:4; //编码
void *ptr; //指向底层实现数据结构的指针
int refcount; //引用计数
unsigned lru:22; //最后被访问的时间
} robj;
type 记录了对象的类型,键总是字符串类型,值可以是五种类型之一:
当称呼一个数据库键为“列表键”时,指的是这个键对应的值为列表对象
对键执行TYPE命令,返回的是对应的值对象的类型
特定类型的命令在执行前会检查值对象的type属性,如果不匹配就拒绝执行并返回错误
encoding 记录了对象所使用的底层数据结构:
每种类型的对象都至少有两种编码:
使用object encoding命令,可以查看键对应的值对象的编码
redis可以根据不同情况,使用不同的底层对象,极大提高了灵活性
多态命令:redis根据encoding,选择命令的正确实现代码
ptr 指向底层的数据结构
refcount 引用计数,可以用于内存回收和对象共享,例如redis会在启动时,创建一万个字符串对象,包含了0~9999的整数值,当要用到值为0~9999的字符串时,就可以使用这些共享对象
lru 用于统计键的空转时长,object idletime命令可打印lru,且该命令不会刷新lru的值