Redis Notes

Redis Architecture Design

Redis is generally known as a single-process, single-thread model. This is not true. Redis also runs multiple backend threads to perform backend cleaning works, such as cleansing the dirty data and closing file descriptors. In Redis, the main thread is responsible for the major tasks, including but not limited to: receiving the connections from clients, processing the connection read/write events, parsing requests, processing commands, processing timer events, and synchronizing data. Only one CPU core runs a single process and single thread. For small packets, a Redis server can process 80k to 100k QPS. A larger QPS is beyond the processing capacity of a Redis server. A common solution is to partition the data and adopt multiple servers in distributed architecture. However, this solution also has many drawbacks. For example, too many Redis servers to manage; some commands that are applicable to a single Redis server do not work on the data partitions; data partitions cannot solve the hot spot read/write problem; and data skew, redistribution, and scale-up/down become more complex. Due to restrictions of the single process and single thread, we hope that the multi-thread can be reconstructed to fully utilize the advantages of the SMP multi-core architecture, thus increasing the throughput of a single Redis server. To make Redis multi-threaded, the simplest way to think of is that every thread performs both I/O and command processing. However, as the data structure processed by Redis is complex, the multi-thread needs to use the locks to ensure the thread security. Improper handling of the lock granularity may deteriorate the performance.

We suggest that the number of I/O threads should be increased to enable an independent I/O thread to read/write data in the connections, parse commands, and reply data packets, and still let a single thread process the commands and execute the timer events. In this way, the throughput of a single Redis server can be increased.

单进程-单线程的优缺点

Single Process and Single Thread Model

Advantages

Due to restrictions of the single-process and single-thread model, time-consuming operations (such as dict rehash and expired key deletion) are broken into multiple steps and executed one by one in Redis implementation. This prevents execution of an operation for a long time and therefore avoids long time blocking of the system by an operation. The single-process and single-thread code is easy to compile, which reduces the context switching and lock seizure caused by multi-process and multi-thread.

Disadvantages

• Only one CPU core can be used, and the multi-core advantages cannot be utilized.
• For heavy I/O applications, a large amount of CPU capacity is consumed by the network I/O operations. Applications that use Redis as cache are often heavy I/O applications. These applications basically have a high QPS, use relatively simple commands (such as get, set, and incr), but are RT sensitive. They often have a high bandwidth usage, which may even reach hundreds of megabits. Thanks to popularization of the 10-GB and 25-GB network adapters, the network bandwidth is no longer a bottleneck. Therefore, what we need to think about is how to utilize the advantages of multi-core and performance of the network adapter.

单线程模型会严重影响整体的吞吐量，CPU计算过程中，整个IO调度都是被阻塞的。

为什么 Redis 使用单线程而不是多线程模型？

• Ease of programming - Writing a multi-threaded program can be trickier. Sometimes multi-threading may not work, locks can block other threads.
• Concurrency can be achieved on single threaded system. Concurrency is not parallism.
• CPU is not bottleneck - Usually network is bottleneck. CPUs are very fast. If application is designed right, i.e. avoiding blocking IO, threading will be near the bottom of the list to worry about.
• Cost effective deployment - Such applications can work on any machine having at least a single CPU core.

由于单线程无法发挥多核的优势，所以可以考虑改造为多线程，但需要考虑所增加的复杂度。

Multi-Thread Model and Implementation

Thread Model

There are three thread types, namely:

• Main thread
• I/O thread
• Worker thread

由一个主线程和多个 IO 线程组成。

• Main thread: Receives connections, creates clients, and forwards connections to the I/O thread.
• I/O thread: Processes the connection read/write events, parses commands, forwards the complete parsed commands to the worker thread for processing, sends the response packets, and deletes connections.
• Worker thread: Processes commands, generates the client response packets, and executes the timer events.
• The main thread, I/O thread, and worker thread are driven by events separately.
• Threads exchange data through the lock-free queue and send notifications through tunnels.

                                                Memcached Redis
Sub-millisecond latency                             Yes Yes
Developer ease of use                               Yes Yes
Data partitioning                                   Yes Yes
Support for a broad set of programming languages    Yes Yes
Advanced data structures                            -   Yes
Multithreaded architecture                          Yes -
Snapshots                                           -   Yes
Replication                                         -   Yes
Transactions                                        -   Yes
Pub/Sub                                             -   Yes
Lua scripting                                       -   Yes
Geospatial support                                  -   Yes

Redis Datastructures

Redis的 5 种对象类型：

• string
• hash
• list
• set
• sorted set

Redis Memory model

丰富的类型是 Redis 相对于Memcached等的一大优势。在了解了 Redis 5 种对象类型用法和特点的基础上，进一步了解 Redis 的内存模型，对Redis的使用会有很大帮助!

• 估算Redis内存使用量。目前为止，内存的使用成本仍然相对较高，使用内存不能无所顾忌；根据需求合理的评估Redis的内存使用量，选择合适的机器配置，可以在满足需求的情况下节约成本。
• 优化内存占用。了解Redis内存模型可以选择更合适的数据类型和编码，更好的利用Redis内存。
• 分析解决问题。当Redis出现阻塞、内存占用等问题时，尽快发现导致问题的原因，便于分析解决问题。

Redis占用内存的情况及如何查询、不同的对象类型在内存中的编码方式、内存分配器（jemalloc）、简单动态字符串（SDS）、RedisObject等

1. Redis内存统计

在客户端通过 redis-cli 连接服务器后, 使用 info 命令可以查看内存使用情况

2. Redis内存划分

除了数据以外，Redis的其它部分也会占用内存。

1、数据
作为数据库，数据是最主要的部分，这部分占用的内存会统计在used_memory中。

Redis 提供的 5 种类型是对外提供的。实际上，在Redis内部，每种类型可能有2种或更多的内部编码实现。此外，Redis在存储对象时，并不是直接将数据扔进内存，而是会对对象进行各种包装：如RedisObject、SDS等。

2、进程本身运行需要的内存
Redis 主进程本身运行肯定需要占用内存，如代码、常量池等等。这部分内存大约几兆，在大多数生产环境中与Redis数据占用的内存相比可以忽略。这部分内存不是由jemalloc分配，因此不会统计在used_memory中。

补充说明：除了主进程外，Redis创建的子进程运行也会占用内存，如Redis执行AOF、RDB重写时创建的子进程。当然，这部分内存不属于Redis进程，也不会统计在used_memory和used_memory_rss中。

3、缓冲内存

缓冲内存包括：
客户端缓冲区：存储客户端连接的输入输出缓冲；
复制积压缓冲区：用于部分复制功能；
AOF缓冲区：用于在进行AOF重写时，保存最近的写入命令。

在了解相应功能之前，不需要知道这些缓冲的细节。这部分内存由jemalloc分配，因此会统计在used_memory中。

4、内存碎片
内存碎片是Redis在分配、回收物理内存过程中产生的。例如，如果对数据更改频繁，而且数据之间的大小相差很大，可能导致Redis释放的空间在物理内存中并没有释放，但Redis又无法有效利用，这就形成了内存碎片。内存碎片不会统计在used_memory中。

内存碎片的产生与对数据进行的操作、数据的特点等都有关。此外，与使用的内存分配器也有关系——如果内存分配器设计合理，可以尽可能的减少内存碎片的产生。后面将要说到的jemalloc便在控制内存碎片方面做的很好。

如果Redis服务器中的内存碎片已经很大，可以通过安全重启的方式减小内存碎片。因为重启之后，Redis重新从备份文件中读取数据，在内存中进行重排，为每个数据重新选择合适的内存单元，减小内存碎片。

3. Redis 数据存储的细节

。。。

Redis 内部使用一个redisObject对象来表示所有的key和value。redisObject主要的信息包括数据类型（type）、编码方式(encoding)、数据指针（ptr）、虚拟内存（vm）等。type代表一个value对象具体是何种数据类型，encoding是不同数据类型在redis内部式。

String 类型

字符串是Redis值的最基础的类型。Redis中使用的字符串是通过包装的，基于c语言字符数组实现的简单动态字符串(simple dynamic string, SDS)一个抽象数据结构。

SDS 源码

struct sdshdr {
    int len; //len表示buf中存储的字符串的长度。
    int free; //free表示buf中空闲空间的长度。
    char buf[]; //buf用于存储字符串内容。
};

SDS 与 C 字符串的比较

SDS 在 C 字符串的基础上加入了free和len字段，带来了很多好处：

获取字符串长度：SDS是O(1)，C字符串是O(n)。

缓冲区溢出：使用C字符串的API时，如果字符串长度增加（如strcat操作）而忘记重新分配内存，很容易造成缓冲区的溢出；而SDS由于记录了长度，相应的API在可能造成缓冲区溢出时会自动重新分配内存，杜绝了缓冲区溢出。

修改字符串时内存的重分配：对于C字符串，如果要修改字符串，必须要重新分配内存（先释放再申请），因为如果没有重新分配，字符串长度增大时会造成内存缓冲区溢出，字符串长度减小时会造成内存泄露。而对于SDS，由于可以记录len和free，因此解除了字符串长度和空间数组长度之间的关联，可以在此基础上进行优化——空间预分配策略（即分配内存时比实际需要的多）使得字符串长度增大时重新分配内存的概率大大减小；惰性空间释放策略使得字符串长度减小时重新分配内存的概率大大减小。

存取二进制数据：SDS 可以，C 字符串不可以。因为C字符串以空字符作为字符串结束的标识，而对于一些二进制文件（如图片等），内容可能包括空字符串，因此C字符串无法正确存取；而SDS以字符串长度len来作为字符串结束标识，因此没有这个问题。

此外，由于SDS中的buf仍然使用了C字符串（即以‘\0’结尾），因此SDS可以使用C字符串库中的部分函数。但是需要注意的是，只有当SDS用来存储文本数据时才可以这样使用，在存储二进制数据时则不行（‘\0’不一定是结尾）。

参考：
https://blog.csdn.net/tTU1EvLDeLFq5btqiK/article/details/81140409
https://blog.csdn.net/qq_26624661/article/details/79269740

Redis 实现分布式锁？

锁的本质就是互斥，保证任何时候能有一个客户端持有同一个锁，如果考虑使用redis来实现一个分布式锁，最简单的方案就是在实例里面创建一个键值，释放锁的时候，将键值删除。但是一个可靠完善的分布式锁需要考虑的细节比较多，我们就来看看如何写一个正确的分布式锁。

单机版分布式锁 SETNX

setNX 命令作用是 SET if Not eXists，我们利用它来实现一个简单的锁。

锁的获取：

SET <resource_name> <my_random_value> NX PX 30000

锁的释放：

if redis.call("get", KEYS[1]) == ARGV[1] then
    return redis.call("del",KEYS[1])
else
    return 0
end

几个细节需要注意：

• 首先在获取锁的时候我们需要设置设置超时时间。设置超时时间是为了，防止客户端崩溃，或者网络出现问题以后锁一直被持有。真个系统就死锁了。

• 使用 setNX 命令，保证查询和写入两个步骤是原子的

• 在锁释放的时候我们判断了KEYS[1]) == ARGV[1]，在这里 KEYS[1]是从redis里面取出来的value，ARGV[1]是上文生成的my_random_value。之所以进行以上的判断，是为了保证锁被锁的持有者释放。我们假设不进行这一步校验：

  • 客户端A获取锁，后发线程挂起了。时间大于锁的过期时间。
  • 锁过期后，客户端B获取锁。
  • 客户端A恢复以后，处理完相关事件，向redis发起 del命令。锁被释放
  • 客户端C获取锁。这个时候一个系统中同时两个客户端持有锁。

造成这个问题的关键，在于客户端B持有的锁，被客户端A释放了。

• 锁的释放必须使用 lua 脚本，保证操作的原子性。锁的释放包含了 get，判断，del 三个步骤。如果不能保证三个步骤的原子性，分布式锁就会有并发问题。

注意了以上细节，一个单redis节点的分布式锁就达成了。

在这个分布式锁中还是存在一个单点的redis。也许你会说，Redis是 master-slave的架构，发生故障的时候切换到slave就好，但是Redis的复制是异步的。

如果在客户端A在master上拿到了锁。
在master将数据同步到slave上之前，master宕机。
客户端B就从slave上又一次拿到了锁。
这样由于Master的宕机，造成了同时多人持有锁。如果你的系统可用接受短时时间内，有多人持有锁。这个简单的方案就能解决问题。

但是如果解决这个问题。Redis的官方提供了一个Redlock的解决方案。

RedLock 的实现

为了解决，Redis 单点的问题。Redis的作者提出了RedLock的解决方案。方案非常的巧妙和简洁。
RedLock的核心思想就是，同时使用多个Redis Master来冗余，且这些节点都是完全的独立的，也不需要对这些节点之间的数据进行同步。

假设我们有 N 个 Redis 节点，N 应该是一个大于 2 的奇数。RedLock 的实现步骤:

• 取得当前时间
• 使用上文提到的方法依次获取 N 个节点的 Redis 锁。
• 如果获取到的锁的数量大于 （N/2+1）个，且获取的时间小于锁的有效时间(lock validity time)就认为获取到了一个有效的锁。锁自动释放时间就是最初的锁释放时间减去之前获取锁所消耗的时间。
• 如果获取锁的数量小于 （N/2+1），或者在锁的有效时间(lock validity time)内没有获取到足够的说，就认为获取锁失败。这个时候需要向所有节点发送释放锁的消息。
  对于释放锁的实现就很简单了。向所有的 Redis 节点发起释放的操作，无论之前是否获取锁成功。

同时需要注意几个细节：

重试获取锁的间隔时间应当是一个随机范围而非一个固定时间。这样可以防止，多客户端同时一起向 Redis 集群发送获取锁的操作，避免同时竞争。同时获取相同数量锁的情况。（虽然概率很低）
如果某 master 节点故障之后，回复的时间间隔应当大于锁的有效时间。

假设有 A，B，C 三个 Redis 节点。
客户端 foo 获取到了 A、B 两个锁。
这个时候 B 宕机，所有内存的数据丢失。
B 节点恢复。
这个时候客户端bar重新获取锁，获取到B，C两个节点。
此时又有两个客户端获取到锁了。

所以如果恢复的时间将大于锁的有效时间，就可以避免以上情况发生。同时如果性能要求不高，甚至可以开启Redis的持久化选项。

总结
了解了Redis分布式的实现以后，其实觉得大多数的分布式系统其实原理很简单，但是为了保证分布式系统的可靠性需要注意很多的细节，琐碎异常。
RedLock算法实现的分布式锁就是简单高效，思路相当巧妙。

虽然看上去 RedLock 实现了分布式锁，但是网上有人（Martin Kleppmann）对这种实现发出了批评，他先是提出了两个使用锁的原因：

1）提升效率，用锁来保证一个任务没有必要被执行两次。比如（很昂贵的计算）
2）保证正确，使用锁来保证任务按照正常的步骤执行，防止两个节点同时操作一份数据，造成文件冲突，数据丢失。

然后，其指出，对于第一种原因，我们对锁是有一定宽容度的，就算发生了两个节点同时工作，对系统的影响也仅仅是多付出了一些计算的成本，没什么额外的影响。这个时候 使用单点的 Redis 就能很好的解决问题，没有必要使用RedLock，维护那么多的Redis实例，提升系统的维护成本。

对于第二种原因，对正确性严格要求的场景（比如订单，或者消费），就算使用了 RedLock 算法仍然不能保证锁的正确性。

因为，RedLock 只是保证了锁的高可用性，并没有保证锁的正确性。

Martin给出了一个解决的方案，增加一个 token-fencing，它是单调递增的，我们可以把其理解为一个乐观锁，所以 RedLock 是一个严重依赖系统时钟的分布式系统

最后， Redis 作者 antirez 还打出了一个暴击，既然 Martin 提出的系统使用 fecting token 保证数据的顺序处理。还需要 RedLock，或者别的分布式锁 干啥？？

Redis 数据库实现与键过期

1）Redis 的数据库实现

主要在 server.h/redisServer/ 中

1. redisServer

struct redisServer{
    redisDb *db; // 保存 db 的数组
    int dbnum;   // db 的数量
    ...
}

2. redisDb

typedef struct redisDb {
    dict *dict;                 /* The keyspace for this DB */
    dict *expires;              /* Timeout of keys with a timeout set */
    dict *blocking_keys;        /* Keys with clients waiting for data (BLPOP)*/
    dict *ready_keys;           /* Blocked keys that received a PUSH */
    dict *watched_keys;         /* WATCHED keys for MULTI/EXEC CAS */
    int id;                     /* Database ID */
    long long avg_ttl;          /* Average TTL, just for stats */
} redisDb;

3. dict

总体来说 redis 的 server 包含若干个（默认16个） redisDb 数据库。

Redis 是一个 kv 存储的键值对数据库。其中字典 dict 保存了数据库中的所有键值对。

在执行对键的读写操作的时候，Redis 还要做一些额外的维护动作：

• 维护 hit 和 miss 两个计数器。用于统计 Redis 的缓存命中率。
• 更新键的 LRU 时间，记录键的最后活跃时间。
• 如果在读取的时候发现键已经过期，Redis 先删除这个过期的键然后再执行余下操作。
• 如果有客户对这个键执行了 WATCH 操作，会把这个键标记为 dirty，让事务注意到这个键已经被改过。
• 没修改一次 dirty 会增加1。
• 如果服务器开启了数据库通知功能，键被修改之后，会按照配置发送通知。

2）Redis 键过期的策略

我们可以看到 redisDb 结构体中 expires 就是用来保存过期时间的。

对于过期的判断逻辑很简单：

• 在 expires 字典中检查 key 是否存在。
• 如果 key 存在，判断 value 的时间戳是否小于当前系统时间戳。

key的删除有三种策略：

• 定时删除，Redis定时的删除内存里面所有过期的键值对，这样能够保证内存友好，过期的key都会被删除，但是如果key的数量很多，一次删除需要CPU运算，CPU不友好。
• 惰性删除，只有 key 在被调用的时候才去检查键值对是否过期，但是会造成内存中存储大量的过期键值对，内存不友好，但是极大的减轻CPU 的负担。
• 定时部分删除，Redis定时扫描过期键，但是只删除部分，至于删除多少键，根据当前 Redis 的状态决定。

这三种策略就是对时间和空间有不同的倾向。Redis 为了平衡时间和空间，采用了后两种策略，惰性删除和定时部分删除。

惰性删除比较简单，不做过多介绍。主要讨论一下定时部分删除。

过期键的定时删除的策略由 expire.c/activeExpireCycle() 函数实现，server.c/serverCron() 定时的调用 activieExpireCycle() 。