Redis
数据结构与对象(基于Redis2.8)
动态字符串
1.SDS结构体
组成 SDS结构体含有属性len表示已使用字节数量 free表示未使用字节数量 char[]表示字节数组
优点 O(1)时间获得数组使用长度 拼接字符串时将先检查free是否够用若不够用则扩展空间后再拼接避免缓存区的逸出 扩展空间策略根据字符串长度若<1MB则长度和未使用空间分配相等否则固定分配1MB未使用空间 字符串缩短时不立即释放多余空间而采用增长free长度 使用len属性判断字符串是否结束
链表
1.链表节点结构体
组成 前指针prev 后指针next 值指针value
2.链表结构体
组成 表头节点head 表尾节点tail 节点数量len 节点复制函数dup 节点释放函数free 节点对比函数match
特点 head的前指针以及tail的后指针均为null因此为无环结构 常用于列表
字典
1.哈希表结构体
组成 哈希表数组table 哈希表大小size 哈希表大小掩码sizemark 哈希表已有节点数量used
2.哈希表节点结构体
组成 键key 值v 下个节点指针next
3.字典结构体
组成 特定类型函数指针type 私有数据privdata 哈希表ht rehash状态trehashidx默认-1
4.rehash过程
扩展操作则ht[1]的大小为>=ht[0].used*2的第一个2^n 收缩操作则ht[1]的大小为>=ht[0].used的第一个2^n
在ht[0]中的键值对在查找等操作时分批次转移 同时新增操作在ht[1]进行
当ht[0]中的所有键值对转移后释放ht[0]并设置ht[1]为ht[0]同时创建新空白哈希表给ht[1]
当负载因子(哈希表已保存节点数/哈希表大小)<0.1时 执行收缩操作
跳表
跳表结构
整数集合
1.intset结构体
组成 编码方式encoding 集合元素数量length 元素数组contents
特点 每个元素在数组中按照从小到大的顺序排序且不包含重复项 元素占用字节数按照编码方式确定为16或32或64位
升级 当放入元素范围超出原本可表示范围 则数组扩展后从尾到头将元素转移后新元素再放入数组
压缩列表
1.列表
组成 压缩列表占用内存字节数zlbytes 压缩列表尾节点距离压缩列表起始地址字节数zltail 节点数量zllen zllen个数量节点entryX 末端标记zlend
2.节点
组成 前一节点的字节长度previous_entry_length 记录content属性保存的数据类型和长度encoding 节点值content
特点 列表项仅为整数或较短的字符串
连锁更新 当多个节点的长度刚好为250字节到253字节之间时(当前一节点长度<254时 previous_entry_length采用1字节 否则采用5字节) 在其前者插入长度超过253字节的节点会导致后续的节点刚好均需要发生扩容 时间复杂度为O(n^2)
快表(Redis3.x版本出现)
1.概述
由于链表的前后指针占用空间原因用于代替链表
2.结构
多个链表形成一段采用压缩表存储 每段之间通过前后指针链接
对象
1.redisObject结构体
组成 类型type 编码encoding 数据结构指针prt
2.字符串对象
当值为整数型且可被long表示时 编码类型为int
当为字符串类型且长度>32字节 编码类型为raw
当为字符串类型且长度<=32字节 编码类型为embstr
embstr可将raw内存分配次数从2次降为1次同时销毁次数也从2次降为1次
3.列表对象
字符串元素长度<64字节&&元素个数<512 编码类型为ziplist 否则编码类型为linkedlist
4.哈希对象
字符串元素长度<64字节&&元素个数<512 编码类型为ziplist 否则编码类型为hashtable
5.集合对象
元素为整数&&元素个数<512 编码类型为intset 否则编码类型为hashtable
6.有序集合对象
元素字节长度<64&&元素个数<128 编码类型为ziplist 否则编码类型为skiplist
同时使用哈希表和跳表的原因在于 哈希表支持单个查询值时间为O(1) 跳表支持范围查询O(logN)
7.内存回收
引用计数技术实现内存回收
8.空转时长
redisObject的lru属性记录对象最后一次被访问时间 当服务器占用内存数超过maxmemory时优先释放空转时长较高的对象
单机数据库
数据库
1.服务器中的数据库
服务器默认数据库数量为16
2.过期键删除策略
定时删除策略 使用于CPU不忙而内存紧张环境
惰性删除策略 取出键时对键进行检查若过期则删除 使用于内存不紧张环境
定期删除策略 每固定时间内用固定时间去随机获得部分设置过期键后判断若过期则删除
3.内存淘汰策略
LRU随机抽取若干后选择最少使用数据淘汰 TTL随机抽取若干后选择即将过期的数据淘汰 RANDOM
4.AOF、RDB和复制功能对过期键的处理
生成RDB文件时过期键不会加入文件 载入RDB文件时若为主服务器则过期键不载入否则从服务器载入所有键由于主从同步时数据情况因此不会有影响
写入AOF文件时仅在键被主动或被动删除时才将删除命令写入AOF文件 AOF重写时过期键被忽略
复制模式下从服务器收到读数据后即使过期依然返回数据直到收到主服务器发来的删除命令
5.数据库通知
关注某个键执行什么命令的通知称为键空间通知
关注某个命令被什么键执行的通知称为键事件通知
RDB持久化
1.RDB文件的创建与载入
SAVE命令阻塞Redis服务器进程直到RDB文件创建完毕 BGSAVE调用fork函数派生子进程创建RDB文件后向父进程发送信号而父进程继续处理命令请求
2.自动间隔性保存
多个条件构成条件数组 默认为900 1,300 10,60 10000
dirty计数器记录上次保存后服务器对数据库做的修改次数 每成功执行一次数据库修改命令 程序对dirty计数器进行更新
lastsave保存上一次执行保存的时间
Redis服务器每隔100毫秒调用serverCron对所有条件根据dirty计数器和lastsave时间进行判断 若符合则执行保存操作
3.RDB文件结构
AOF持久化
1.AOF持久化的实现
命令追加到AOF缓冲区中后转入文件
appendfsync的always在每个事件循环将缓冲区中的所有内容写入AOF文件 所以慢但是如果丢失仅一次事件循环内容
appendfsync的everysec每隔一秒将缓冲区内容写入AOF文件 丢失一秒数据
appendfsync的no由操作系统决定当缓冲区快满时写入AOF文件
2.AOF重写
服务器进程派生子进程根据数据库内容重写AOF文件 同时服务器进程负责处理请求并写入AOF缓冲区 待子进程进入完毕后发送信号至主进程 主进程再将AOF缓冲区内容写入AOF文件
事件
1.文件事件
基于Reactor模式 参考Netty模型
2.时间事件
时间事件组成无序链表 时间事件执行器遍历链表查找已到达的时间事件并调用对应的事件处理器 如果是定时事件则删除否则按照时间返回值更新when属性
3.事件的调度与执行
获取最近的时间事件－计算还要多久时间事件到达－阻塞时间－处理产生的文件事件－处理时间事件
运行流程
客户端
1.套接字属性
伪客户端套接字fd属性为-1 普通客户端fd属性为>-1的整数
2.名字
3.标志
包括主服务器 从服务器等
4.输入缓冲区
保存客户端发送的命令请求
5.命令与命令参数
argv[0]表示命令 argv[1]及以后表示参数 argc表示argv长度
6.命令的实现函数
根据argv[0]查找命令表对应命令实现函数
7.输出缓冲区
命令回复保存在输出缓冲区中 固定大小缓冲区默认长度为16*1024即16KB 可变缓冲区
8.身份验证
authenticated 0表示拒绝命令 1表示接受命令 若不启动身份验证则均接受命令
9.时间
服务器
1.命令请求的执行过程
发送命令请求->读取命令请求到输入缓冲区->命令执行器查找命令实现->命令执行器执行预备操作->命令执行器调用命令的实现函数->命令执行器执行后续工作->将命令回复给客户端->客户端接收并打印命令回复
2.初始化服务器
初始化redisServer结构体->载入配置选项->初始化服务器数据结构->还原数据库状态->执行事件循环
多机数据库的实现
复制
1.完整重同步
主服务器通过BGSAVE命令创建RDB文件后发送给从服务器同步后再将缓冲区中的写命令发送给从服务器同步
2.部分重同步
从服务器发送本机的复制偏移量及服务器运行ID到主服务器 主服务器判断ID是否相同 不相同则进行完整重同步操作 相同则从积压缓冲区(固定长度队列)查找偏移量是否存在缓冲区 存在则进行部分重同步操作 不存在则进行完整重同步操作
3.心跳检测
每秒从服务器向主服务器发送REPLCONF命令你给 用于检测主从服务器状态 辅助实现min-slaves配置选项 检测命令丢失
Sentinel
1.作用
本质为特殊模式的Redis服务器 由一个或多个Sentinel实例组成的Sentinel系统监视多个主服务器及其从服务器 当主服务器下线时自动将某个从服务器升级为主服务器
2.过程
初始化服务器 代码替换为Sentinel专用代码 初始化Sentinel状态 初始化Sentinel监视主服务器列表 创建与主服务器的网络连接
3.概述
每个Sentinel实例会与主服务器 从服务器 其他Sentinel实例均进行连接 对于主从服务器既通过命令连接发送消息到通道_sentinel_:hello同时通过订阅连接从频道中接收信息 每秒向所有连接发送Ping命令若在指定时间内连续获得无效回复则认为主观下线 同时询问其他Sentinel实例若超过数量的Sentinel实例均认为主观下线则认为客观下线 客观下线后Sentinel选举领头Sentinel 由领头Sentinel执行故障转移操作
集群
1.槽指派
clusterNode结构体属性slots中每位若1表示节点负责处理该槽否则不处理该槽 clusterState结构体属性slots中每个项若为null表示该槽未指派任何节点否则指向某节点 两种数据结构使得操作时间复杂度为O(1)
2.过程
对key经过CRC16运算再与16383^运算确定槽位置 若该位置不是当前节点负责处理则返回MOVED错误指引客户端转向处理对应的节点 若是则处理命令
3.重新分片
对目标节点及源节点发送命令准备 对源节点发送命令获得属于槽的最多count个键值对的键名 对源节点发送命令将被选中的键从源节点迁移到目标节点 重复以上步骤直到对应槽所有键值对被转移 向任一节点发送命令将槽转移到目标节点该消息将发送到集群最终集群所有节点都将明确
4.ASK错误
当槽在被转移时 若命令的键在该槽中 源节点在先检查该键是否在目前槽中 若存在则返回不存在则返回ASK错误 客户端将先发送ASKING命令到目标节点后再重新发送命令 否则该命令将被目标节点返回MOVE错误因为该key所在槽目前仍指派给源节点
5.ASK错误和MOVE错误比较
ASK错误和MOVED错误均导致客户端请求转向 ASK错误客户端仅访问一次指向位置而在以后的访问中继续访问原位置 MOVED错误客户端将一直访问新位置
独立功能的实现
发布与订阅
1.概述
SUBSCRIBE和PSBUSCRIBE命令建立通道和客户端的链表方式 当一个消息发布时查找对应的链表头从而遍历链表将消息发送给所有订阅给通道的客户端 SUBCRIBE用于订阅准确的通道 PSUBSCRIBE用于订阅模式匹配的通道
事务
1.特点
在事务执行期间不执行其他客户端命令
2.WATCH命令
乐观锁 监视多个键 当事务提交时若在事务过程中被监视的键被其他客户端更改则提交失败
3.ACID
原子性 事务中即使发生运行错误 事务中其余的所有操作依然执行 没有回滚
一致性 事务发生入队错误时事务的所有操作不执行 执行错误时依然运行其他操作 单进程处理事务意味着事务提交时处理串行化而不是MULTI命令开启事务后即拒绝其他事务执行
隔离性 各个事务互不影响 结果与串行执行相同
持久性 特定条件即AOF模式下每条命令后的SAVE下支持持久性
