Redis 中的数据结构和高可用

结构

  1. Redis 中的数据结构
  2. Redis 持久化
  3. Redis 的单线程多路 IO 复用
  4. 分布式高可用架构

数据结构

string

string 内部的实现是一个可变的字节数组,当字符串长度小于 1M 时,每次扩容都是翻倍,如果超过 1M,扩容时一次只会多增加 1M 的空间,是字符串最大长度为 512M。

list

内部实现为双端链表或者压缩链表,查找性能比较慢,从表头和表尾追加和移除元素很快。通过 rpush/rpop/lpush/lpop 四条指令,可以将链表作为队列或堆栈使用。可用于实现 timeline 和消息队列。

只有同时满足两个条件时,才会使用压缩列表:列表中元素数量小于 512 个。列表中所有字符串对象都不到 64 字节。并且只可能由压缩列表转化为双端链表,不能反过来。

压缩列表

压缩列表是一种数据结构,通过将一系列数据与其编码信息存储在一块连续的内存区域,这块内存物理上是连续的,逻辑上被分为多个组成部分,从而达到节省内存的效果。压缩列表中每一个节点由三部分构成:

  1. previous length 用于存储上一个节点的长度,因此压缩列表可以从尾部向头部遍历,即当前节点位置减去上一个节点的长度即得到上一个节点的起始位置。previous length 的长度可能是1个字节或者是5个字节,如果上一个节点的长度小于 254,则该节点只需要一个字节就可以表示前一个节点的长度了,如果前一个节点的长度大于等于 254,则 previous length 的第一个字节为 254,后面用四个字节表示当前节点前一个节点的长度。
  2. 节点的 encoding 保存的是节点的 content 的内容类型以及长度。
  3. content 用于保存节点的内容。

img

压缩列表的新增、删除的操作平均时间复杂度为O(N),随着N的增大,时间必然会增加,不像哈希表可以以O(1)的时间复杂度找到存取位置,然而在一定N内的时间复杂度是可以容忍的。然而压缩列表利用巧妙的编码技术除了存储内容尽可能的减少不必要的内存开销,将数据存储于连续的内存区域。除此之外还有减少内存碎片的作用。

dict

dict 可以是压缩列表(ziplist)和哈希表(hashtable)两种,哈希表基于数组实现,发生哈希冲突时通过链表来解决。只有同时满足下面两个条件时,才会使用压缩列表:哈希中元素数量小于 512 个,哈希中所有键值对的键和值字符串长度都小于64字节。只可能由压缩列表转化为哈希表,不能反过来。

rehash

Redis Dict 中定义了两张哈希表,是为了后续字典的扩展作 Rehash 之用:

1
2
3
4
5
6
7
8
/* 字典结构定义 */
typedef struct dict {
dictType *type; // 字典类型
void *privdata; // 私有数据
dictht ht[2]; // 哈希表[两个]
long rehashidx; // 记录rehash 进度的标志,值为-1表示rehash未进行
int iterators; // 当前正在迭代的迭代器数
} dict;

在进行扩容或者缩容的时候,可以直接将所有的键值对 rehash 到新一个新哈希表中,这是因为数据量比较小。在实际大数据量下,rehash 不是一次性完成的,是分多次渐进式地完成的。ht[0] 是存放数据的 table,作为非扩容时使用,ht[1] 只有正在进行扩容时才会使用,长度为ht[0]的两倍。

扩容时,单线程 A 负责把数据从 ht[0] copy 到 ht[1] 中。如果这时有其他线程进行读操作会先去 ht[0] 中找,找不到再去 ht[1] 中找,写操作直接写在 ht[1] 中,删操作和读操作一样。

set

内部实现为整数集合(intset)或哈希表(hashtable)。集合在使用哈希表时,值全部被置为 null。只有同时满足下面两个条件时,集合才会使用压缩列表:集合中元素数量小于 512 个,集合中所有元素都是整数值。只可能由整数集合转化为哈希表,不能反过来。

sortedset

sortedset 又叫 zset,可以给每一个元素加一个 score 属性,内部的元素会按照 score 来实现,可以得到每一个元素的排名,也可以通过 score 的范围来获取一批元素。zset 内部使用了两个数据结构,hash 和跳跃表,hash 方便关联元素 value 和 score,可以通过元素 value 找到相应的 score 值。跳跃列表给元素通过 value 排序,可通过 score 的范围获取元素列表。

只有同时满足下面两个条件时,才会使用压缩列表:有序集合中元素数量小于 128 个,有序集合中所有成员长度都不足 64 字节。只可能由压缩列表转化为跳跃表,不能反过来。

持久化

作为一个内存数据库,一旦 Redis 退出服务器中的数据也会消失。为了解决这个问题,Redis 提供了持久化机制,也就是把内存中的数据保存到磁盘当中,避免数据意外丢失。Redis 提供了两种持久化方案:RDB 持久化和 AOF 持久化,一个是快照的方式,一个是类似日志追加的方式。

RDB

RDB 持久化是通过快照的方式,在指定的时间间隔内将内存中的数据集快照写入磁盘。在保存 RDB 文件时,服务器进程只需 fork 一个子进程来完成 RDB 文件的创建,父进程不需要做 IO 操作。如果数据比较重要并且可以承受数分钟的数据丢失,比如用作缓存的应用可以使用 RDB。

在配置文件中设置 save <seconds> <changes> 规则,可以自动间隔性执行 bgsave 命令进行持久化。比如 save 10 100 当时间到 10 秒时,如果至少有 100 个 key 发生变化就会自动触发 bgsave 命令创建快照。

AOF

开启 AOF 持久化功能后,服务器每执行一个写命令,都会把该命令以协议格式先追加到 aof_buf 缓存区的末尾,而不是直接写入文件,避免每次有命令都直接写入硬盘,减少硬盘 IO 次数。什么时候把 aof_buf 缓冲区的内容写入保存在 AOF 文件中,Redis 提供了多种策略:

  1. appendfsync always:将 aof_buf 缓冲区的所有内容写入并同步到 AOF 文件,每个写命令同步写入磁盘。
  2. appendfsync everysec:将 aof_buf 缓存区的内容写入 AOF 文件,每秒同步一次,该操作由一个线程专门负责。
  3. appendfsync no:将 aof_buf 缓存区的内容写入 AOF 文件,什么时候同步由操作系统来决定。

随着时间的推移,Redis 执行的写命令会越来越多,AOF 文件也会越来越大,过大的 AOF 文件可能会对 Redis 服务器造成影响,如果使用 AOF 文件来进行数据还原所需时间也会越长。AOF 重写的目的就是减小 AOF 文件的体积,不过值得注意的是:AOF 文件重写并不需要对现有的 AOF 文件进行操作,而是通过读取服务器当前的数据库状态来实现的。文件重写可分为手动触发和自动触发,会执行 bgrewriteaof 命令,该命令的执行跟 bgsave 触发快照时类似的,都是先 fork 一个子进程做具体的工作。

AOF 文件是一个只进行追加的日志文件,相比 RDB 数据更完整安全性更高,对于相同的数据集,AOF 文件的体积要大于 RDB 文件,数据恢复也会比较慢。根据所使用的 fsync 策略,AOF 的速度可能会慢于 RDB。

多路 IO 复用

Redis 是基于单线程实现,和 nginx 一样基于 epool 一直可在 linux 服务器实现数十万的并发连接。同时单线程的模型,也避免了多线程下各种锁争夺和上下文切换。

高可用

Redis-Cluster

Redis 集群采用了完全去中心化的模式。Redis 把所有的 key 分成了 16384 个 slot,每个 Redis 实例负责其中一部分 slot。

对于 meta 数据的存储,Codis 是存储在 Zookeeper 中的,Redis 官方维护集群元数据采用的是 gossip 协议,所有节点都持有一份元数据,不同的节点如果出现了元数据的变更,就不断将元数据发送给其它的节点,让其它节点也进行元数据的变更。gossip 协议包含多种类型的消息:

  1. meet:某个节点发送 meet 给新加入的节点,让新节点加入集群中,然后新节点就会开始与其它节点进行通信。
  2. ping:每个节点都会频繁给其它节点发送 ping,其中包含自己的状态还有自己维护的集群元数据,互相通过 ping 交换元数据。
  3. pong:返回 ping 和 meeet,包含自己的状态和其它信息,同时用于信息广播和更新。
  4. fail:某个节点判断另一个节点 fail 之后,就发送 fail 给其它节点,通知其它节点某个节点宕机。

redis cluster 从 4.0 开始不在采取哨兵模式来对 master-slave 来进行监听。如果一个节点认为另外一个节点宕机,那么就是 pfail,如果一个节点认为某个节点 pfail 了,那么会在 gossip ping 消息中,ping 给其他节点,如果超过半数的节点都认为 pfail 了,那么就会变成 fail。

对宕机的 master node,从其所有的 slave node 中,选择一个切换成 master node。每个从节点,都根据自己对 master 复制数据的 offset,来设置一个选举时间,offset 越大也就是复制数据越多的从节点,选举时间越靠前,优先进行选举。所有的 master node 开始 slave 选举投票,给要进行选举的 slave 进行投票,如果大部分 master node 都投票给了某个从节点,那么选举通过,那个从节点可以切换成 master。从节点执行主备切换,从节点切换为主节点。理论上而言,不管是哨兵还是 gossip 都是有可能丢数据的。

Codis

目前我们公司是采用 Codis 来实现分布式 Redis 集群部署的。Codis 可以分为两部分,proxy 和 group。proxy 可基于 zookeeper 多实例部署,负责转发请求到对应的 group。group 负责具体的数据存储是 redis 进程所在,group 内部可一主多备部署,基于 redis-sentinel 实现 ha。

Codis 中也有 slot 的概念,每一个 group 会负责某一部分 slot,codis-proxy 会负责转发 client 到合适的 slot 里边。slot 和 group 之间的对应的关系存储在 zookeeper 中,所以 proxy 可以无状态部署,能很好的处理扩容和缩蓉导致的 slot 关系变更的问题。

architecture