Deep Dive in Redis

所以Redis适合全部数据都在内存的场景包括需要临时持久化，尤其作为缓存来使用，并支持对缓存数据进行简单处理计算；如涉及Redis与RDBMS双向同步的话，则需要引入一些复杂度。

4.1 Pipelining

Reids是一个TCP客户端-服务器模式，使用了应请求/响应协议，客户端与服务器的交互是阻塞的方式。

如下一个请求/响应事例，客户端发起4个INCR命令，服务端依次响应:

• Client:INCR X

• Server:1

• Client:INCR X

• Server:2

• Client:INCR X

• Server:3

• Client:INCR X

• Server:4

客户端与服务器通过网络连接，影响性能的关键因素往返时间（RTTRound Trip Time）则受限于网络速度，如在网速较慢情况下RTT需要250毫秒，哪怕服务器性能卓越可以每秒处理1万个请求，然而整体则客户端受网络制约只能每秒处理4个请求。即便使用了loopback接口节省RTT时间，但如果需要大量的写操作，整体性能仍不可观。

Redis引入了批处理，管道（Pipelining），即客户端可以一次发送多个命令给服务器，无须等待服务器的返回，而服务器端则回将请求放入一个有序的管道中，在执行完成后，一次性将返回值发送回客户端。

上述事例在使用Pipelining时如下，客户端通过缓冲区，一次性批量发送请求INCR，服务端则处理后统一返回结果：

• Client:INCR X

• Client:INCR X

• Client:INCR X

• Client:INCR X

• Server:1

• Server:2

• Server:3

• Server:4

4.2 Pub/Sub

Reids提供了解耦消息的发布/订阅（Pub/Sub）通信模式，Pub/Sub采用事件作为基本通信机制，支持时间（非同时），空间（无须知道具体位置）与同步（可异步模式）等解耦合，而发布与订阅则通过通道（channel）来通信。

Antirez称，最初引入Pub/Sub是应用户需求，并且Redis本身的架构已经支持Pub/Sub, 所以只用了150行代码就把Pub/Sub已实现的内部功能暴露称Pub/SubAPI。

上图为较早版本中发布消息的一段代码片段，可以看出消息保存在一个List链表数据结构中，消息的类型为messagebulk。另外，Redis也支持通配符模式匹配的订阅方式。

Pub/Sub v.s. 消息中间件

Reids的Pub/Sub与消息中间件相比，并不支持持久化，如系统宕机，网络问题等都会造成消息丢失；Redis的消息多用于实时性较高的消息推送，并不保证可靠性。Redis的消息也无法支持水平扩展，如通过增加consumer或者订阅者分组之类进行负载均衡。

性能方面，Redis的Pub/Sub与常用消息中间件如著名的RabbitMQ比较，则伯仲之间。

上图以处理10万个消息为例，在发布消息方面，RabbitMQ的耗时为Redis的75%；订阅消费消息RabbitMQ耗时为Redis的86%，可见整体性能Redis已与消息中间件相近。

4.3 LRU

LRU(Least Recently Used) 最近最久未使用算法，是多数缓存系统当内存受限时自动清理旧数据的常用常用算法之一。

当Redis使用内存达到配置maxmemory时，Redis会根据配置的policy进行数据置换处理，其中策略包括如下：

• noenviction（不清除）

• allkeys-lru（从所有数据集选择最近最少用）

• volatile-lru（从设置过期时间的数据集选择最近最少用）

• allkeys-random（所有数据集随机选取淘汰），

• volatile-random（以设置过期时间数据集中随机），

• volatile-ttl（从已设置过期过期时间的数据集中选择，非LRU）

Redis出于性能及节约内存考量，采用的并非严格意义LRU算法算法，而是近似的LRU算法，即Redis通过采样一小部分键，然后在样本池中进行LRU。当然在Redis 3.0中，算法进一步改进为维护回收候选键池，改善了性能同时更接近于LRU算法行为。

下图为官网提供Reids LRU性能测试，分别为理论LRU算法，10个样本的Redis 3.0 LRU算法，以及5个样本的Redis 2.8与3.0算法的表现，其中浅灰色表示被置换出去的key，灰色为没有被置换的key，绿色为新增的key。

测试算法较简单，首先默认导入一定数目key，之后从第一个key遍历至最后一个key（相当于按时间顺序使用过了当前遍历的key），之后再增加50%的数目触发清理策略。

可以看出，理论算法为最旧的50%被替换；同样样本为5情况下，3.0表现要优于2.8，3.0则更接近于理论值，2.8算法则略为逊色。

4.4 Transactions

绝大多数NoSQL选择不支持事务，而Reids以命令方式（MULTI, EXEC, DISCARD, WA WATCH）提供了简单的类/伪事务支持，之所以称之为类/伪事务，是因为Redis的只保证了事务必须ACID的C（一致性），I（隔离性），并不保证A（原子性）与持久性（D），Redis事务甚至不支持回滚操作。

实际上，Redis的事务提供了一种将多个命令打包并置入事务队列，之后批量一次性，有序的按照先进先出（FIFO）的顺序执行机制。事务在执行过程中不会被中断，所有命令命令执行之后，事务才结束。

Transaction v.s.Pipelining

Redis的Transaction与Pipelining都是批量执行命令，其主要差别为：

• Pipelining主要是提供了网络层面的优化，客户端通过缓存多个命令并按批次发送给服务端处理以节省网络RTT（Round Trip TIme）时间开销，但这些命令并不保证事务性（Redis的单线程保证了单个命令本身是原子的，但多个client可以发起多个命令串行执行）。

• Transaction则保证了一个client发起的事务中的命令可以连续的执行，中间不会插入其它client的命令，而此则受益于Redis的单线程模式，很容易实现。

所以，Transaction与Pipelining不但不冲突，对于批量命令甚至可以结合起来使用以达到网络优化及事务性保证双重收效。

4.5 Persistence

Redis提供了两种常用的不同级别的磁盘持久化方式，RDB与AOF（Append-Only-File）。RDB持久化在指定的时间间隔生成数据集的时间点快照（Snapshot）, AOF则类似RDMS的binlog日志。

由于单线程运行，Redis的RDB在备份时为不影响系统正常使用，借助Linux的fork命令及copy on write机制，在fork出的子进程中进行备份写RDB文件。RDB的备份相对简单并且文件小，但无法保证数据的完整性，如Redis在RDB的间隔时间内宕机，则面临丢失期间的数据。RDB较适合定期的归档备份及方便灾难恢复。

而AOF则提供了更好的持久性，Redis会将每个命令都追加到AOF文件中，并提供了三种持久化策略：

• no fsync at all：Redis不调用fsync持久化, 操作系统决定同步时机（多数30秒）

• fsync everysecond：每秒（延迟会两秒）进行一次fsync将缓冲区数据写入磁盘

• fsync always：每个命令都进行同步，持久化写入磁盘，安全但较慢

AOF后台执行的方式与RDB类似，也是借助fork开启子进程进行写入AOF文件。为了减少AOF文件的大小，Redis提了了文件压缩命令，另外支持日志重写，后台重构AOF文件以减少所需命令。

4.6 Replication

Redis支持Master/Slave主从配置，实现弱一致性，支持负载均衡，提高HA。Redis的Master可以对应多个Slave, Slave也可以级联多个Slave。通常Master负责读写服务，Slave负责读服务，Master与Slave间靠Replication定期来进行同步。

Redis的主从结构如下图所示DAG（有向无环图）：

Slave会定期给Master发送SYNC命令进行同步，如果第一次连接则进行全量同步否则增量同步。Master则启动后台快找进程saving来收集最近修改数据集所有命令并将其用db file传输给Slave。

另外，Redis从2.8版本开始支持中断后（网络断开等故障）的断点续传功能，无须重新同步。Master维护一个内存缓冲区，主从服务器都维护一个复制偏移量（offset）和master run id，当断开重新连接后，Master判断两个master run id是否相同，并根据指定的偏移量继续断点续传。

Sentinel架构

Reids Sentinel诞生于2012年（Redis 2.4版本），建议在单机Redis或者客户端模式Cluster的时候（非3.0版本Redis Cluster）采用，作为HA, Failover来使用。

Sentinel主要提供了集群管理，包括监控，通知，自动故障恢复。如上图，当其中一个master无法正常工作时，Sentinel将把一个Slave提升为Master, 从而自动恢复故障。而Sentinel本身也做到了分布式，可以部署多个Sentinel实例来监控Redis实例（建议基数，至少3个Sentinel实例来监控一组Redis Master/Slaves），多个Sentinel进程间通过Gossip协议来确定Master是否宕机，通过Agreement协议来决定是否执行故障自动迁移以及重新选主，整体设计类似ZooKeeper（应该是作者参考了当年的ZK吧？）。

Cluster架构

Redis Cluster开始设计于2011年（早于Sentinel），正式诞生于2015年愚人节，Redis 3.0，其中之苦辣酸甜只有Antirez自己知道。

如上图，从3.0开始， Redis从一个单纯的NoSQL内存数据库变成了一个真正分布式NoSQL数据库。

概括来说，所谓分布式即支持数据分片，并且自动管理故障恢复（failover）与备份（replication）。

Cluster无中心架构

如上图Redis Cluster采用了无中心结构，每个节点都保存，共享数据和集群状态，每个节点与其它所有节点通信，使用Gossip协议来传播及发现新节点，通过分区来提供一定程度可用性，当某个node的Master宕机时，Cluste会自动选举一个Slave形成一个新的Master，这里应该是借鉴，重用了Sentinel的功能。

另外，Redis Cluster并没有使用通常的一致性哈希, 而引入哈希槽的概念，Cluster中固定有16384个slot, 每个key通过CRC16校验后对16384取模来决定其对应slot的位置，而每个node负责一部分的slot管理，当node变化时，动态调整slot的分布，而数据则无须挪动。对于客户端来说，client可以向任意一个实例请求，Cluster会自动定位需要访问的slot。

上图查询路由过程中，我们随机发送到任意一个Redis实例，这个实例会按照上文提到的CRC16校验后取模定位，并转发至正确的Redis实例中。

然而，完全去中心化的架构同时也失去了一些灵活与总控能力，如可通过引入中央控制的自动发现节点的变化及时Rebalance，分区粒度的备份，故障时分区自动调整，Gossip消息的通信开销，路由表维护等。

值得一提的是，Redis的企业版/商业版Redis Labs Enterprise Cluster（RLEC）则似乎解决了我们上述问题，如引入了中央控制Cluster Manager来管理，监控，分片迁移等工作, 引入高性能Proxy隐藏幕后的路由实现等。

当然，前提是商业化付费版本了，我们也期待未来的开源Redis逐步可以引入这些概念。

Redis支持丰富的数据类型，并提供了大量简单高效的功能。为了高效使用Redis，开发设计人员需要对Redis的数据结构进行选型，如选择链表还是集合等。 下面我们快速了解一下Redis内部数据结构及其代码实现。

Redis的底层数据结构总览图：

上图列出了Redis内部底层的一些重要数据结构，包括List, Set, Hash, String等。

来看几个比较核心的的数据结构。

Redis 3.x后的redisObject如下图所示：

redisObject定义中使用了位字段（bit filed）。简单来说，redisObject定义了类型，编码方式，LRU时间，引用计数，*ptr指向实际保存值指针。

• type: redisObject的类型，字符串，列表，集合，有序集，哈希表等

• encoding: 底层实现结构，字符串，整数，跳跃表，压缩列表等

• ptr：实际指向保存值的数据结构

  
  

RedisDB内部数据结构，封装了数据库层面的信息：

从redisDB来看，几个重要属性：

• id：数据库内部编号，仅供内部操作使用，如AOF等

• dict：存放整个数据库的键值对，键为字符串，值为Redis的数据结构，如List, Set, Hash等。

• expires：键的过期时间
  

具体代码如下：

代码注释较为清晰，其中long long是C99标准新加的，64位长整型。

RedisServer代码在Redis 3.0支持Cluster后变得较复杂，我们只列出部分代码。

总体来说包含如下几个大部分：

• 通用部分：如pid进程id，数据库指针，命令字典表，Sentinel模式标志位等

• 网络信息：如port TCP监听端口，Cluster Bus监听socket, 已使用slot数量，Active的客户端列表, 当前客户端，Slaves列表等。

• 其它信息：如AOF信息，统计信息, 配置信息（如已经配置总db数量dbnum等），日志信息，Replication配置，Pub/Sub, Cluster信息，Lua脚本信息配置等等。
  

Redis的哈希表/字典是其核心数据结构之一，值得深入研究。

Redis Hash数据结构， Hash新创建时，在不影响效率情况下，Redis默认使用zipmap作为底层实现以节省空间，只有当size超出一定限制后（hash-max-zipmap-entries），Redis才会自动把zipmap转换为下图Hash Table。

上图字典的底层实现为哈希表，每个字典包含2个哈希表，ht[0], ht[1], 1号哈希表是在rehash过程中才使用的。而哈希表则由dictEntry构成。

代码层面，每个字典包含了3个内部数据结构：

• Dict：字典的根结构，包含了2个dictht，其中2作为rehashing之用

• Dictht：包含了linkedlist dictEntry

• DictEntry：包含了3个数据结构（double/uint64_6/int64t）的链表，类似Java HashMap中的Entry结构
  

Hash算法

目前Redis中引入了一些经典哈希算法，而HashTable则主要为以下两种：

• MurmurHash2 32bit算法：著名的非加密型哈希函数，能产生32位或64位哈希值，最新版本为MurmurHash3。该算法针对一个字符串进行哈希，可表现较强离散性。

• 声明：文章版权归原作者所有 部分文章转自互联网 如有侵权请联系 [邮箱地址] 删除