概述
字符串
SDC(Simple Dynamic String,简略动静字符串)作为字符串示意
每个sds.h/sdshdr构造示意一个SDS值
struct sdshdr{
...
}
len
free
buff
劣势
- 常数复杂度获取字符串长度
数据结构中有len属性用于保留字符串的长度 - 杜绝缓冲区溢出
在字符串进行扩大前,会先检查一下buff的长度是否足够,如果不够的话就会进行扩大,而后再执行增加字符的操作 - 缩小内存调配次数
SDS通过两种策略来实现
3.1 空间预调配
如果对SDS进行批改之后,len属性小于1MB,那么程序调配和len同样大小的未应用空间,即len和free属性值雷同;如果大于1MB,那么将调配1MB未应用空间
3.2 惰性空间开释
当SDS的API须要缩短保留的字符串时,内存重调配不会立刻开释未应用的空间,而是将其作为free的数量 - 二进制平安
首先须要理解C,C的字符串必须合乎某种编码,例如如果一开始读入空格将被辨认为结尾
SDS以二进制模式存储,文本存进去是什么内容,拿进去就还是什么内容 -
兼容局部C字符串函数
SDS遵循C字符串以空字符结尾,这样就能重用/<string.h>的stracasecmp函数strcasecpm(sds->buff,"hello world!")
链表
数据结构
双向链表
typedef struct list{
…
}list
listNode * head;
温习一下结点的数据结构
typedef struct listNode{
struct ListNode * prev;
struct ListNode * next;
void * value;
}
listNode * tail;
unsigned long len;
//节点复制函数
void (dup)(void *ptr)个性
双端、无环、带表头和表尾指针、带链表长度计数器和多态
对于多态这里解释一下,以复制函数为例,应用的void*指针来保留节点值,所以能够保留各种不同类型的值用处
-
列表键、公布与订阅、慢查问、监视器等
列表键临时不知
公布与订阅容易音讯失落,实用于要求不高的场景,能够从确保音讯不失落的问题从延长
慢查问临时不知
监视器临时不知字典
哈希表节点与哈希表数据结构
键值节点构造
哈希表构造
字典构造
从下面的图里能够看到,字典中有哈希表构造,而哈希表中有key-value键值节点
哈希算法
通过键来计算出哈希值和索引值(通过哈希值和哈希掩码计算出来),将蕴含新键值对的哈希表节点放在置顶索引下面
解决键抵触(哈希抵触)
链表法
rehash(从新散列)
说人话就是为了在字典外面的数据减少或者缩小的时候将哈希表的长度管制在肯定范畴内,防止不够用或者过于节约
当哈希表减少或者缩减到肯定水平时就会触发rehash操作 - 如果是减少,那么ht[1]的大小等于ht[0].used*2的2^n^
如果是缩小,那么ht[1]的大小等于ht[0].used的2^n^ - 将ht[0]的所有键值都放到ht[1]中,这个过程会从新计算hash值和索引值
-
开释ht[0],而后将ht[1]设置为ht[0],并且在ht[1]新创建一个空白哈希表,为下一次的rehash做筹备
渐进式rehash
先定义一个rehashindex变量,初始值为0,在执行新增、删除、查问时都会将对应ht[0]的redisindex索引处的key-value从新散列到ht[1],并且在渐进式rehash期间,新增的结点不会进入到ht[0]中,就保障了ht[0]最终会成为空表
跳跃表
几个重要的概念
- 后退指针
每个跳跃表结点都有指向下一个结点的指针 - 层
每个跳跃表结点都会有很多层,至于具体是干什么的当初还不太分明 - 后退指针
最初一个跳跃表结点指向前一个结点 - 跨度
就是从头结点开始到指标结点经验的门路,有点想图的权 -
分值和成员
分值是一个double类型的浮点数,跳跃表中的所有的结点的分值依照从小大来排序对象是一个指针,它指向一个字符串对象,而字符串对象中则保留一个SDS值
不太分明一个跳跃表结点是不是只能寄存一个对象,然而我猜想是这样的总结
- Redis的跳跃表实现是由zkiplist和zkiplistNode两个构造组成,其中zkiplist用于保留跳跃表信息(比方表头节点、表尾节点、长度),而zskiplistNode则用于跳跃表节点
-
多个跳跃表节点的分值能够雷同,然而对象必须惟一
整数汇合
整数汇合是汇合键的底层实现之一,当一个汇合只蕴含整数值元素,并且这个汇合的元素数量不多时,Redis
sadd numbers 1 3 5 7 9
下面的命令用的是sadd,阐明用的汇合set的根本类型(Redis对外提供的)降级
先来看数据结构
typedef strunct intset{ unit32_t encoding; }
下面的encoding属性决定以后数组的元素是用什么形式编码,如果以后是inset_enc_int16,此时再增加进一个64位编码的元素那么就会执行降级操作
整数汇合只反对降级而不反对降级压缩列表
压缩列表ziplist是列表键(List???)和哈希键(Hash???)的底层实现之一。当一个列表键只蕴含大量列表项,并且每个列表项要么是小整数值,要么是长度比拟短的字符串,那么Redis就会应用压缩列表来做列表键的底层实现
在3.2和5之后引入了quicklist和listpack,所以废除了对象
5种根本类型
就是入门篇里提到的5种类型对象
注:因为Redis外面都是键对象和值对象,所以这一章的角度都是从这两个对象登程
EVAL “for i=1, 128 do redis.call(‘ZADD’, KEYS[1], i, i) end” 1 numbers
下面这段代码是往一个zset外面插入128个元素,从1开始
在开始内容之前须要先看一个数据结构typedef struct redisObject{ //类型 unsigned type:4; //编码 unsigned encoding:4; //指向底层实现数据结构的设计 void *ptr; //对象的空转时长 unsigned lru:22; //援用计数 int refcount; }
不同类型的编码方式
尽管Redis有5种根本数据类型,然而每种数据类型还是的底层还是有至多两种以上的编码方式(这里说的编码方式和底层用的数据结构不是一个概念)
这里就不得不提一下多态了,真的是随处可见,比如说所有的类型都可能应用命令DEL
有些命令是数据类型独有的,例如RPUSH、ZADD,这些命令在执行时,不同底层编码方式也都会执行这些指令。类型查看
服务器在执行某些命令前,会先查看给定键的类型可能执行指定的命令,其实就是查看值对象的类型
内存回收机制
对象上有个字段refcount,代表以后对象被援用次数,如果为0,则会从内存中删除掉
内存共享
0-9999整数值会事后存好,就像Java的字符串常量池一样
空转工夫
越近拜访的值空转工夫会越少
单机数据库的实现
抉择数据库
select 0(index)
客户端程序中有个数据结构,其中有个属性保留了以后客户端应用的数据库数据库键空间
数据库键空间是这一章的重点
对于键值变动时的操作过程
- 新增键
- 删除键
- 更新键
-
读写键的保护操作
服务器中键有命中和不命中次数属性,是一个统计指标
键有ideltime,用来批示键的闲置工夫
键有过期时长,不晓得和这个闲置工夫的属性有什么关系
键有个属性代表是否被批改,书上说的是键是不是为dirty(脏键),每次批改这个值都会被加1,如果客户端应用WATCH命令对其进行了监听,那么客户端程序在执行事务程序时就会留神到。设置生存或者过期工夫
RDB长久化
SAVE和BGSAVE
Mac下应用Homebrew装置的Redis的RDB文件地位
- 首先还是得找到redis.conf的地位
应用brew info redis命令能够查看到
/opt/homebrew/etc/redis.conf -
在redis.conf找到dbfilename和dir属性的值来确定文件名称和门路
db.dump和/opt/homebrew/var/db/redisAOF长久化
AOF缓冲区
重写
AOF重写缓冲区
事件
首先来温习一下多路复用,没方法用的多有什么辙
几个要害的记忆点,bind()函数和accept()函数,socket
客户端connect()
已连贯队列
多过程模型
多线程模型
IO多路复用模型select()和poll()
IO多路复用模型epoll()
事件机制,回调函数Redis中的IO多路复用
客户端
次要内容是服务器外部保留的redis-client构造,对其中的的属性进行解说
服务端