底层使用到的数据结构
1 SDS(简单动态字符串)
如上图,对于简单的字符串,SDS可以比喻成java里面的StringBuffer,其中free记录了buff中的可以用的字符的长度,len记录了buff中已用的字符的长度,buff具体的集体了字符串的内容,与C语言类似,结束符使用'\0'
扩容策略
1 如果在对sds进行append操作的时候,如果free字段不足以存储append的字符串,如果sds扩容后的长度小于1M,那么free扩容成与len一样的长度。(也就是预分配一倍的空间)
2 如果在对sds进行扩容后的len大于1M,那么free的值也变成1M,等于说对大于1M的sds进行预分配1M的空间
缩容策略
直接使用free字段记录buff里面的可用空间,这样能避免下次扩容的时候再次的申请内存空间,当然sds也提供的api真正的释放buff里面的free资源。
由于sds使用len来存储buff里面的有效字符串,所以在输出的时候,直接从buff的头截取len长度的资源来返回,所以使用sds是安全的。
2 链表
链表可以类比成java里面的LinkedList
如上图,list里面保存了head 和 tail节点,分别指向链表的第一个节点和最后一个节点,
且第一个节点的pre指针为null,最后一个节点的next指针也为null,这样整个list是没有环的,通过next或是pre的指针是否为null,我们可以判定是否到了链表的尾部和头部。其list里面的len属性保存了节点的个数,能很方便的知道链表的长度。
3字典
如上所示,dict解决key冲突的做法是开地址法,所有hash值相同的key都放在dictTable相同的slot里面,并使用链表连接。
可以看到dict里面有两个ht,用于dict扩容,为把备份的ht申请内存空间,并先采用分批迁移的方式将entry迁移到新的ht,使用渐进式的方式进行迁移,防止entry过多,堵塞主线程。
4跳跃表
跳跃表一般用于有序链表的快速查找
对于有序的数组,我们可以使用二分查找进行logN时间复杂度的查找,但是对于链表,由于没有下标信息,我们无法使用二分查找,而跳跃表就是在链表的基础上,多层次的存储关键节点信息,可以跳跃性的往后查找。
radis中的跳跃表一般用于实现有序集合。(关于跳跃表网上的介绍很多,这里不重复的介绍)
5整数集合(intSet)
当一个集合只包含整数 成员,且数量不多的时候, redis会使用整数集合来实现集合
如上,intset的encoding保存了contents里面的编码方式,由于数字的变大,编码方式可能进行升级,但是不会进行降级,length保存了数组的大小。
整数集合是集合的底层实现之一
整数集合已无序的方式存储数据 ,且数组里面的编码方式只支持升级操作不支持降级操作。
6ziplist (压缩列表)
压缩列表是列表和哈希表的底层实现之一。
其中每个压缩列表节点的组成如下
所以我们可以对压缩列表进行反向的正向的遍历操作
压缩列表是一种为实现节约内存而开发的顺序型数据结构
压缩列表是用作列表和哈希的底层实现之一
7 对象
虽然redis在底层实现了如上的6中数据结构,但是redis没有直接的使用,而是统一的使用RedisObject进行了封装,这样做的好处是,根据数据的变化,可以动态的变更RedisObject的底层的实现,而上层做到无感知(果然没有什么是添加一个代理做不到的事情),对象的数据结构如下
其中type就是redis支持的五种数据结构,
字符串 REDIS_STRING
列表 REDIS_LIST
哈希 REDIS_HASH
集合 REDIS_SET
有序集合 REDIS_ZSET
对于不同的type,可以有不同的encoding的实现,主要编码常亮如下
REDIS_ENCODING_INT long类型的整数
REDIS_ENCODING_EMBSTR embstr编码的简单动态字符串
REDIS_ENCODING_RAW 简单动态字符串
REDIS_ENCODING_HT 字典
REDIS_ENCODING_LINKEDLIST 双端链表
REDIS_ENCODING_ZIPLIST 压缩列表
REDIS_ENCODING_INTSET 整数集合
REDIS_ENCODING_SKIPLIST 跳跃表和字典
对于每一种type至少有两种encoding可以来实现
一般来说 字符串对象的编码可以是 int raw 和embstr
列表对象的编码可以是ziplist 和linkedlist
哈希对象的编码可以是 ziplist和hashtable
集合对象可以是intset和hashtable
有序集合的编码可以是ziplist和skiplist
内存回收的机制使用引用计数法来实现,redis会共享0-9999的字符串的对象
8 数据库
redis服务器,默认会创建16个数据库,我们默认使用0号数据库
redisdb里面的expires字典单独的保存了数据库中所有的键的过期时间
过期键的删除策略如下
1 惰性删除(访问key的时候,检查key在expires字典是否过期,如果过期,删除)
2 定期删除 轮训每个redisdb,随机删除20个。设置的时间到就停止
可以使用save(堵塞主线程)和bgsave(fork子线程,执行完了通知主线程)命令保存rdb文件,redis启动的时候会载入rdb文件,可以对redis的服务端进行rdb的存储的策略的设置
也可以使用aof文件,aof的重写能力可以减少aof文件的大小
数据库通知的能力,可以实现对某个键或者action进行监控。
rdb + aof
命令请求会先写在aof缓存里面,然后在同步到aof文件
事件
redis服务器是一个事件驱动程序,服务器要处理两种事件
1 文件事件,redis通过socket与客户端进行连接,而文件事件就是对socket操作的抽象,redis服务器与客户端的通信会产生相应的文件事件,服务器通过监听这些文件事件来完成网络操作
2 时间事件 redis里面的一些操作如要在给定的时间点执行,而时间事件就是对这类定时操作的抽象
文件事件
redis使用reactor模式实现了自己的网络事件处理器(文件事件处理器)
文件事件处理器使用多路io复用技术来监听多个socket,并根据当前的任务关联不同的事件处理器
当被监听的socket准备好 accept read write close时,文件处理器就调用socket之前关联好的事件处理器来进行处理,文件时间处理器是单线程运行的,但是使用reactor实现了 高性能的网络通信模型,又可以很好的与redis中其他的同样以单线程运行的模块进行对接,这样保证了redis的简洁性。
io多路复用程序监听多个socket,并向文件事件分派器通过队列的方式有序的同步socket,只有先前队列里面的套接字产生的事件处理完成之后,后面的socket产生的事件才会由文件事件分派器进行分配。如下
io多路复用技术使用 select epoll kqueue等技术来实现(可以进行更加细致的研究)
时间事件
时间事件是放在redis的单线程的主loop里面通过轮询来实现的,所以时间事件的实际处理时间会比设定的时间晚一些
文件事件和时间事件是合作关系,服务器会轮流的处理这两种事件,并且处理事件的过程中不会进行抢占。
客户端
redis的服务端通过链表的方式保存了所有与之相连的客户端的信息,如下
记录的客户端的主要属性有
套接字描述符
名字
标志
输入缓冲区(每个客户端的输入信息都缓存在这里等待执行)
命令与命令参数
命令的实现函数
输出缓冲区
身份验证
时间信息
服务器
复制
哨兵模式
哨兵模式是redis集群的高可用方案 ,哨兵本身如何的实现高可用呢???
如上图,哨兵是一个特殊的redis的集群,可与实现对redis集群的监控,且在master主机下线之后,会根据相关的策略选取一台slave机器升级为master。如下
每台哨兵有主观下线配置和客观下线配置
比如s1通过主观下线配置检测到了某台master挂了,那么会与其他的哨兵进行沟通,达成客观下线的共同约定之后,才会将这台master真的下线.
而此时的哨兵集群会通过raft协议选举主的sentinel,然后由主sentinel来执行故障转移的操作。
集群
可以通过给每个master指定slot(默认的redis集群一共有16384个slot)的方式,搭建redis集群,这个是redis高性能,且可扩展的一个体现(但是需要手动的分配slot这一点不是很人性化),而且如果请求的redis的key不在请求的机器上,会通过MOVED返回让client重定向到新的redis服务器上面去。整个集群的请求模式如下
如上题,比较符合老外的去中心化的架构模式,但是确定是分布式逻辑和存储模块耦合,所以如果我们可与单独的将分布式逻辑拆出来,那么架构就更加的清晰了,于是我们可与使用codis的架构,如下
通过封装一层codis-proxy代理(codis-proxy完全的实现了redis的协议,对于客户端来说,他就是一个伪装的redis),具体如下
route负责将请求转发到redis
而model和zk交互保证proxy集群的数据(slot配置,分组配置等,其实就是使用zk当了数据库和高可用的工具),
整个codis的具体架构参考如下
@link https://blog.csdn.net/shmiluwei/article/details/51958359
发布与订阅
在redis的服务端会保存 所有频道的订阅关系
如上图所示,服务端明确的知道哪些客户端订阅了哪些频道。
那么某个redis将消息发送到指定的频道的时候,服务端会轮询的比对和发送(典型的监听者模式\订阅者模式)
事务
redis通过multi exec watch命令来实现事务(其实就是将命令批量入队列,然后在一个一个的执行)
redis的事务没有原子性,由于不支持事务回滚,所以不支持原子性
由于没有原子性,所以没有一致性
隔离性 由于redis是单线程的,所以天然的支持隔离性
永久性 使用rdb和aof来实现
lua脚本
redis执行lua脚本的引用和执行,可以通过lua脚本来实现复杂的语义
排序
redis的sort命令可以对列表 集合和和有序集合进行排序
支持 by asc desc limit
store可以保存排序结果,方便下次使用