《redis 设计与实现》--总结
Redis设计与实现,以及关于Redis使用的总结
1.数据结构与对象
1.简单动态字符串
Redis自己构建了简单动态字符串(Simple Dynamic String,SDS)来作为默认的字符串表示。
SDS的构造如下:
优势是:
- 能够在常数时间内获取字符串的长度-通过len属性
- 能够杜绝缓冲区溢出:记录了缓冲区的大小,在长度不够时,能够自动扩展空间
- 减少修改字符串时带来的内存重新分配次数:采用空间预分配和惰性空间释放
2.链表
Redis自己实现了链表。拥有以下特性:双端无环、带表头指针和表尾指针、带链表长度计数器、多态(使用void* 保存节点值)
3.字典
Redis字典底层采用哈希表实现。采用MurmurHash2算法,解决键冲突的方式是:链地址法。
哈希表的扩展与收缩:以下条件满足时:
- 服务器没有执行BGSAVE或BGREWRITEAOF命令,哈希表负载因子>1
- 服务器在执行BGSAVE或BGREWRITEAOF命令,哈希表负载因子>5
4.跳跃表
Redis采用跳跃表作为有序集合键的底层数据结构,另:在集群节点中用作内部数据结构
跳跃表:一种有序数据结构,通过在一个节点维持多个指向其他节点的指针,从而达到快速访问节点的目的。支持平均O(logN),最差O(N)复杂度的查找。
Redis中跳跃表的实现:
5.整数集合
Redis中集合键的底层实现之一,当一个集合只包含整数值元素,并且这个集合中元素的数量不多时,就会使用整数集合作为集合键的底层实现。
整数集合的升级策略:能够提高整数集合的灵活性,并且能够尽可能的节约内存。升级后不支持降级
6.压缩列表
Redis中列表键和哈希键的底层实现之一。
7.对象
Redis使用上述的数据结构创建了一个对象系统。包括:字符串对象、列表对象、哈希对象、集合对象和有序集合对象。其实这就是一直说的Redis五种数据结构:字符串、列表、字典、集合、有序集合。
2.单机数据库的实现
数据库
Redis服务器讲所有数据库保存在一个db数组中,默认创建16个数据库。
切换数据库:select 0 #选择0号数据库
数据库键空间
键空间的键也是数据库的键。每个键都是一个字符串对象。
键空间的值也是数据库的值,每个值可以是字符串对象、列表对象、哈希对象、集合对象,有序集合对象中的任意一个Redis对象。
一个键空间的例子:
设置键的生存时间或过期时间
原理是:过期时间是一个UNIX时间戳,当键的过期时间来临是,服务器就会自动从数据库中删除一个键。
命令:
expire <key> <ttl> #key的生存时间为ttl秒
pexpire <key> <ttl> #key的生存时间为ttl毫秒
expireat <key> <timestamp> #key的生存时间直到timestamp指定的时间戳s
pexpireat <key> <timestamp> #key的生存时间直到timestamp指定的时间戳ms
persist <key> #移除key的过期时间
ttl <key> #计算key的剩余生存时间
setex命令可以设置一个字符串键的同时为键设置过期时间。 一个带有过期字典的数据库例子:(实际中,键空间的键和过期字典中的键都指向同一个键对象)
过期键删除策略
- 定时删除: 内存最友好,CPU时间最不友好
- 惰性删除:CPU时间友好,内存不友好
- 定期删除:折中 Redis实际使用:惰性删除和定期删除配合使用。
过期键的处理
- RDB文件: 生成RDB文件:已过期的键不会保存到新创建的RDB文件中,因此对生成新的RDB文件没有影响。 载入RDB文件:主服务器模式时,过期键不会被载入。从服务器模式时,都会被载入,但同步后,从服务器数据会被清空,所以也没有影响。
- AOF文件:
AOF写入:如果某个键已经过期,但没有被删除,AOF文件不会因为这个过期键产生任何影响。如果已经删除,AOF文件会追加一条DEL命令显式记录该键已被删除。
AOF重写:已过期的键不会被保存到重写的AOF文件。 - 复制:
主服务器删除一个过期键,会显示向所有的从服务器发送DEL命令,告知删除。
从服务器遇到过期的键也不会删除。只有接收到DEL命令后才会删除过期键。
RDB持久化
通过保存数据库中的键值对来记录数据库状态不同。
功能:将Redis在内存中的数据库状态保存到磁盘中,避免数据意外丢失。RDB文件是一个经过压缩的二进制文件,保存在硬盘中,因此Redis进程退出,只要RDB文件仍在,就可以用来还原数据库的状态。
RDB文件的创建和载入
服务器在载入RDB文件期间,会一直阻塞。
SAVE命令由服务器进程执行保存工作,因此会阻塞服务器。BGSAVE命令由子进程执行保存工作。
自动间隔性保存
设置服务器配置的save选项,让服务器每隔一段时间自动执行一次BGSAVE命令。
save 900 1 # 900s内发生了至少一次修改
save 300 10
save 60 10000
满足上述一个条件,BASAVE就会执行。
RDB文件结构
头部 | 数据库版本 | 数据 | 正文结束符 | 校验和 |
---|---|---|---|---|
REDIS | db_version | databases | EOF | check_sum |
AOF持久化(Append Only File)
通过保存Redis服务器所执行的写命令来记录数据库状态。
AOF持久化的实现过程
命令追加:将内容追加到aof_buf缓冲区的末尾。
写入与同步:服务器每次结束一个时间循环之前,都会调用flushAppendOnlyFile函数,考虑是否将aof_buf缓冲区中的内容写入和保存到AOF文件中。选项值为:alwals,everysec,no
载入与数据还原:还原过程:创建一个不带网络连接的伪客户端;从AOF文件中分析并读取一条写命令;使用伪客户端执行被读出的写命令;循环处理。
AOF重写
目的:解决AOF文件体积膨胀。
实现原理:从数据库中读取键现在的值,然后用一条命令去记录键值对,代替之前记录这个键值对的多条命令。
后台重写:子进程AOF重写期间,服务器进程可以继续处理命令请求。
后台重写问题:子进程重写期间,服务器还需要处理命令请求,可能导致服务器当前数据库状态和重写后的AOF文件所保存的数据库状态不一致。解决办法:AOF重写缓冲区。
事件
文件事件
文件事件处理器。基于Reactor模式,使用IO多路复用程序同时监听多个套接字。
3.多机数据库的实现
4.独立功能的实现
常见问题
AOF和RDB比较
- 两者区别:RDB持久化是指在指定的时间间隔内将内存中的数据集快照写入磁盘,实际操作过程是fork一个子进程,先将数据集写入临时文件,写入成功后,再替换之前的文件,用二进制压缩存储。AOF持久化以日志的形式记录服务器所处理的每一个写、删除操作,查询操作不会记录,以文本的方式记录,可以打开文件看到详细的操作记录。
- 优缺点:RDB:灵活设置备份频率和周期。方便灾难恢复,可以轻松的将一个单独的文件压缩再转移到其他存储介质上。性能最大化。数据集很大时,启动效率相对AOF较高。缺点:很难保证高可用,可能数据在写入磁盘之前会丢失。数据集较大时,可能导致服务器停止服务。
AOF:数据持久性。对日志的写入操作采用的是append模式,写入过程即使出现宕机,也不会破坏日志文件中已经存在的内容。如果日志过大,Redis可以自动启用rewrite机制。包含一个格式清晰、易于理解的日志文件用于记录所有的修改操作。缺点:RDB 在恢复大数据集时的速度比 AOF 的恢复速度要快。根据同步策略的不同,AOF在运行效率上往往会慢于RDB。
Redis分布式锁
使用setnx来争抢锁,抢到之后,再用expire给锁加一个过期时间防止锁忘记了释放。
如果在setnx之后执行expire之前进程意外crash或者要重启维护了,那会怎么样?
同时把setnx和expire合成一条指令来用
寻找key
假如Redis里面有1亿个key,其中有10w个key是以某个固定的已知的前缀开头的,如果将它们全部找出来?
用keys指令可以扫出指定模式的key列表。
redis的单线程的。keys指令会导致线程阻塞一段时间,线上服务会停顿,直到指令执行完毕,服务才能恢复。这个时候可以使用scan指令,scan指令可以无阻塞的提取出指定模式的key列表,但是会有一定的重复概率,在客户端做一次去重就可以了,但是整体所花费的时间会比直接用keys指令长。
Redis同步机制
Redis可以使用主从同步,从从同步。第一次同步时,主节点做一次bgsave,并同时将后续修改操作记录到内存buffer,待完成后将rdb文件全量同步到复制节点,复制节点接受完成后将rdb镜像加载到内存。加载完成后,再通知主节点将期间修改的操作记录同步到复制节点进行重放就完成了同步过程。
redis相比memcached有哪些优势
- 丰富的数据类型
- 速度快
- 可以持久化
区别: - 存储方式:Memecache把数据全部存在内存之中,断电后会挂掉,数据不能超过内存大小。Redis有部份存在硬盘上,这样能保证数据的持久性。
- 数据类型:Memcache对数据类型支持相对简单。Redis有复杂的数据类型,Redis不仅仅支持简单的k/v类型的数据,同时还提供list,set,zset,hash等数据结构的存储。
- 底层模型:它们之间底层实现方式以及与客户端之间通信的应用协议不一样。Redis直接自己构建了VM 机制,因为一般的系统调用系统函数的话,会浪费一定的时间去移动和请求。
- value大小:redis最大可以达到1GB,而memcache只有1MB。
- Redis支持数据的备份,即master-slave模式的数据备份。
Redis的LRU算法
最近最久未用算法。当内存达到限制时,Redis 具体的回收策略是通过 maxmemory-policy 配置项配置的。
no-eviction:不清除数据,只是返回错误,这样会导致浪费掉更多的内存,对大多数写命令(DEL 命令和其他的少数命令例外)
allkeys-lru:从所有的数据集(server.db[i].dict)中挑选最近最少使用的数据淘汰,以供新数据使用
volatile-lru:从已设置过期时间的数据集(server.db[i].expires)中挑选最近最少使用的数据淘汰,以供新数据使用
allkeys-random:从所有数据集(server.db[i].dict)中任意选择数据淘汰,以供新数据使用
volatile-random:从已设置过期时间的数据集(server.db[i].expires)中任意选择数据淘汰,以供新数据使用
volatile-ttl:从已设置过期时间的数据集(server.db[i].expires)中挑选将要过期的数据淘汰,以供新数据使用
Redis常见的性能问题及解决
- Master最好不要做任何持久化工作,如RDB内存快照和AOF日志文件. 特别是不要启用内存快照做持久化,如果数据比较关键,某个Slave开启AOF备份数据,策略为每秒同步一次。
- 尽量避免在压力很大的主库上增加从库。
- Master调用BGREWRITEAOF重写AOF文件,AOF在重写的时候会占大量的CPU和内存资源,导致服务load过高,出现短暂服务暂停现象。
- Redis主从复制的性能问题,为了主从复制的速度和连接的稳定性,Slave和Master最好在同一个局域网内
适合Redis的场景
- 会话缓存 全页缓存 队列 排行榜/计数器 发布/订阅 会话 购物车
Nosql和Key-Value数据库
NoSQL,泛指非关系型的数据库,全称Not Only SQL,意即“不仅仅是SQL”。
NoSQL数据库的四大家族:
- 键值(Key-Value)数据库:Redis、Memcached
- 面向文档(Document-Oriented)数据库:MongoDB 适用:日志、分析
- 列存储(Wide Column Store/Column-Family)数据库 HBase 适用:日志、博客平台
- 图(Graph-Oriented)数据库 适用:关系性强,推荐引擎
Redis最大连接数
默认10000
redis的瓶颈
Redis 主从复制
Redis 复制功能
Redis的定时机制怎么实现的,有哪些弊端,你将如何改进这个弊端
Redis是单线程的,为什么这么高效。我用了对比的方式说,举例Apache和Nginx,一个多线程,一个IO多路复用
Redis的数据类型有哪些,底层怎么实现,跳跃表,哈希表,整数集合等等
Redis的rehash怎么做的,为什么要渐进rehash,渐进rehash怎么实现的
Redis和memcached的区别,Redis为什么可以组集群
Reference:
https://www.bookstack.cn/read/note-of-interview/framework-redis.md
http://www.techug.com/post/nosql.html