Redis设计与实现读书笔记

底层使用到的数据结构

1 SDS(简单动态字符串)

image.png

如上图,对于简单的字符串,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


image.png

如上图,list里面保存了head 和 tail节点,分别指向链表的第一个节点和最后一个节点,
且第一个节点的pre指针为null,最后一个节点的next指针也为null,这样整个list是没有环的,通过next或是pre的指针是否为null,我们可以判定是否到了链表的尾部和头部。其list里面的len属性保存了节点的个数,能很方便的知道链表的长度。

3字典

image.png

如上所示,dict解决key冲突的做法是开地址法,所有hash值相同的key都放在dictTable相同的slot里面,并使用链表连接。
可以看到dict里面有两个ht,用于dict扩容,为把备份的ht申请内存空间,并先采用分批迁移的方式将entry迁移到新的ht,使用渐进式的方式进行迁移,防止entry过多,堵塞主线程。

4跳跃表

跳跃表一般用于有序链表的快速查找
对于有序的数组,我们可以使用二分查找进行logN时间复杂度的查找,但是对于链表,由于没有下标信息,我们无法使用二分查找,而跳跃表就是在链表的基础上,多层次的存储关键节点信息,可以跳跃性的往后查找。
radis中的跳跃表一般用于实现有序集合。(关于跳跃表网上的介绍很多,这里不重复的介绍)

5整数集合(intSet)

当一个集合只包含整数 成员,且数量不多的时候, redis会使用整数集合来实现集合

image.png

如上,intset的encoding保存了contents里面的编码方式,由于数字的变大,编码方式可能进行升级,但是不会进行降级,length保存了数组的大小。
整数集合是集合的底层实现之一
整数集合已无序的方式存储数据 ,且数组里面的编码方式只支持升级操作不支持降级操作。

6ziplist (压缩列表)

压缩列表是列表和哈希表的底层实现之一。


image.png

其中每个压缩列表节点的组成如下


image.png

所以我们可以对压缩列表进行反向的正向的遍历操作
压缩列表是一种为实现节约内存而开发的顺序型数据结构

压缩列表是用作列表和哈希的底层实现之一

7 对象

虽然redis在底层实现了如上的6中数据结构,但是redis没有直接的使用,而是统一的使用RedisObject进行了封装,这样做的好处是,根据数据的变化,可以动态的变更RedisObject的底层的实现,而上层做到无感知(果然没有什么是添加一个代理做不到的事情),对象的数据结构如下


image.png

其中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的简洁性。


image.png

io多路复用程序监听多个socket,并向文件事件分派器通过队列的方式有序的同步socket,只有先前队列里面的套接字产生的事件处理完成之后,后面的socket产生的事件才会由文件事件分派器进行分配。如下


image.png

io多路复用技术使用 select epoll kqueue等技术来实现(可以进行更加细致的研究)

时间事件


image.png

时间事件是放在redis的单线程的主loop里面通过轮询来实现的,所以时间事件的实际处理时间会比设定的时间晚一些
文件事件和时间事件是合作关系,服务器会轮流的处理这两种事件,并且处理事件的过程中不会进行抢占。

客户端

redis的服务端通过链表的方式保存了所有与之相连的客户端的信息,如下


image.png

记录的客户端的主要属性有
套接字描述符
名字
标志
输入缓冲区(每个客户端的输入信息都缓存在这里等待执行)
命令与命令参数
命令的实现函数
输出缓冲区
身份验证
时间信息

服务器

复制

哨兵模式

哨兵模式是redis集群的高可用方案 ,哨兵本身如何的实现高可用呢???


image.png

如上图,哨兵是一个特殊的redis的集群,可与实现对redis集群的监控,且在master主机下线之后,会根据相关的策略选取一台slave机器升级为master。如下


image.png

每台哨兵有主观下线配置和客观下线配置
比如s1通过主观下线配置检测到了某台master挂了,那么会与其他的哨兵进行沟通,达成客观下线的共同约定之后,才会将这台master真的下线.
而此时的哨兵集群会通过raft协议选举主的sentinel,然后由主sentinel来执行故障转移的操作。

集群

可以通过给每个master指定slot(默认的redis集群一共有16384个slot)的方式,搭建redis集群,这个是redis高性能,且可扩展的一个体现(但是需要手动的分配slot这一点不是很人性化),而且如果请求的redis的key不在请求的机器上,会通过MOVED返回让client重定向到新的redis服务器上面去。整个集群的请求模式如下


image.png

如上题,比较符合老外的去中心化的架构模式,但是确定是分布式逻辑和存储模块耦合,所以如果我们可与单独的将分布式逻辑拆出来,那么架构就更加的清晰了,于是我们可与使用codis的架构,如下


image.png

通过封装一层codis-proxy代理(codis-proxy完全的实现了redis的协议,对于客户端来说,他就是一个伪装的redis),具体如下


image.png

route负责将请求转发到redis
而model和zk交互保证proxy集群的数据(slot配置,分组配置等,其实就是使用zk当了数据库和高可用的工具),
整个codis的具体架构参考如下


image.png

@link https://blog.csdn.net/shmiluwei/article/details/51958359

发布与订阅

在redis的服务端会保存 所有频道的订阅关系

image.png

image.png

如上图所示,服务端明确的知道哪些客户端订阅了哪些频道。
那么某个redis将消息发送到指定的频道的时候,服务端会轮询的比对和发送(典型的监听者模式\订阅者模式)

事务

redis通过multi exec watch命令来实现事务(其实就是将命令批量入队列,然后在一个一个的执行)
redis的事务没有原子性,由于不支持事务回滚,所以不支持原子性
由于没有原子性,所以没有一致性
隔离性 由于redis是单线程的,所以天然的支持隔离性
永久性 使用rdb和aof来实现

lua脚本

redis执行lua脚本的引用和执行,可以通过lua脚本来实现复杂的语义

排序

redis的sort命令可以对列表 集合和和有序集合进行排序
支持 by asc desc limit
store可以保存排序结果,方便下次使用

记录慢查询日志(就不应该有这样的慢查询)

监视器 客户端可以将自己变为监视器,所有的命令都会echo到监视器

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 213,864评论 6 494
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 91,175评论 3 387
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 159,401评论 0 349
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 57,170评论 1 286
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 66,276评论 6 385
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,364评论 1 292
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,401评论 3 412
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,179评论 0 269
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,604评论 1 306
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,902评论 2 328
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,070评论 1 341
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,751评论 4 337
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,380评论 3 319
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,077评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,312评论 1 267
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 46,924评论 2 365
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 43,957评论 2 351

推荐阅读更多精彩内容