Redis 基础
最后更新于
最后更新于
Redis 接收到一个键值对操作后，能以微秒级别的速度找到数据，并快速完成操作。Redis 能有这么突出的表现：一方面，这是因为它是内存数据库，所有操作都在内存上完成，内存的访问速度本身就很快（内存访问 100 ns 级别）。另一方面，这要归功于它的数据结构。这是因为，键值对是按一定的数据结构来组织的，操作键值对最终就是对数据结构进行增删改查操作，所以高效的数据结构是 Redis 快速处理数据的基础。
Redis 支持的基础数据类型：String, List, Set, Sorted Set, Hash；这些数据类型中用到的基本数据结构有：简单动态字符串、双向链表、压缩列表、哈希表、跳表和整数数组。我们所说的数据类型是 Redis 中 Value 的类型，Redis 是由键值对构建的内存数据库，键都是字符串，值却有不同的类型表示。
为了实现从键到值的快速访问，Redis 使用了一个哈希表来保存所有键值对。一个哈希表，其实就是一个数组，数组的每个元素称为一个哈希桶。所以，一个哈希表是由多个哈希桶组成的，每个哈希桶中保存了键值对数据。哈希桶中的元素保存的并不是值本身，而是指向具体值的指针。这也就是说，不管值是 String，还是集合类型，哈希桶中的元素都是指向它们的指针。
Redis 之所以使用哈希表作为全局的 KV 存储，是利用了哈希表的 O(1) 时间复杂度来快速查找到键值对的特性；只需要计算键的哈希值，就可以知道它所对应的哈希桶位置，然后就可以访问相应的 entry 元素；这个查找过程主要依赖于哈希计算，和数据量的多少并没有直接关系。也就是说，不管哈希表里有 10 万个键还是 100 万个键，我们只需要一次计算就能找到相应的键。
但是哈希表有个缺点是：随着键值对的增多，hash bucket 的冲突就会随之增加，这个的解决办法是让 bucket 相同的 entry 用链表连接起来，不可避免的一个问题是这个链表有可能会很长，查找数据的效率就会变慢，在 Redis 中这是不允许的，Redis 要非常快的内存操作。
Redis 引入了 rehash 来解决冲突链过长带来的性能下将问题， rehash 的一般做法是：创建一个更大的 hash 表，把老 hash 表的数据复制到新的 hash 表，然后用新的 hash 表提供服务，但是这种方式在 Redis 中的一个问题是大量的内存复制肯能会阻塞 Redis 的线程，无法服务其他请求，会造成短暂的服务中断，无法快速访问数据。
为了解决这个问题，使用渐进式 rehash：Redis 默认使用了两个全局哈希表：哈希表 1 和哈希表 2，刚插入数据时，默认使用哈希表 1，此时的哈希表 2 并没有被分配空间。随着数据逐步增多，Redis 开始执行 rehash：
给哈希表 2 分配更大的空间，例如是当前哈希表 1 大小的两倍
把哈希表 1 中的数据重新映射并拷贝到哈希表 2 中, 但是拷贝数据时，Redis 仍然正常处理客户端请求，每处理一个请求时，从哈希表 1 中的第一个索引位置开始，顺带着将这个索引位置上的所有 entries 拷贝到哈希表 2 中；等处理下一个请求时，再顺带拷贝哈希表 1 中的下一个索引位置的 entries
释放哈希表 1 的空间
动态字符串
双向链表
压缩列表
压缩列表是一块连续的内存空间，元素之间紧挨着存储，没有任何冗余空隙。压缩列表在表头有三个字段 zlbytes、zltail 和 zllen，分别表示列表长度、列表尾的偏移量和列表中的 entry 个数；压缩列表在表尾还有一个 zlend，表示列表结束。
在压缩列表中，如果我们要查找定位第一个元素和最后一个元素，可以通过表头三个字段的长度直接定位，复杂度是 O(1)。而查找其他元素时，就没有这么高效了，只能逐个查找，此时的复杂度就是 O(N) 了。
Redis 为了节约存储空间，对 encoding 字段进行了相当复杂的设计。Redis 通过这个字段的前缀位来识别具体存储的数据形式：
00xxxxxx 最大长度位 63 的短字符串，后面的 6 个位存储字符串的位数，剩余的字节就是字符串的内容。
01xxxxxx xxxxxxxx 中等长度的字符串，后面 14 个位来表示字符串的长度，剩余的字节就是字符串的内容。
10000000 aaaaaaaa bbbbbbbb cccccccc dddddddd 特大字符串，需要使用额外 4 个字节来表示长度。第一个字节前缀是10，剩余 6 位没有使用，统一置为零。后面跟着字符串内容。不过这样的大字符串是没有机会使用的，压缩列表通常只是用来存储小数据的。
11000000 表示 int16，后跟两个字节表示整数。
11010000 表示 int32，后跟四个字节表示整数。
11100000 表示 int64，后跟八个字节表示整数。
11110000 表示 int24，后跟三个字节表示整数。
11111110 表示 int8，后跟一个字节表示整数。
11111111 表示 ziplist 的结束，也就是 zlend 的值 0xFF。
1111xxxx 表示极小整数，xxxx 的范围只能是 (0001~1101), 也就是1~13，因为0000、1110、1111都被占用了。读取到的 value 需要将 xxxx 减 1，也就是整数0~12就是最终的 value。
content 字段在结构体中定义为 optional 类型，表示这个字段是可选的，对于很小的整数而言，它的内容已经内联到 encoding 字段的尾部了。
因为 ziplist 都是紧凑存储，没有冗余空间 (对比一下 Redis 的字符串结构)。意味着插入一个新的元素就需要调用 realloc 扩展内存。取决于内存分配器算法和当前的 ziplist 内存大小，realloc 可能会重新分配新的内存空间，并将之前的内容一次性拷贝到新的地址，也可能在原有的地址上进行扩展，这时就不需要进行旧内容的内存拷贝。
如果 ziplist 占据内存太大，重新分配内存和拷贝内存就会有很大的消耗。所以 ziplist 不适合存储大型字符串，存储的元素也不宜过多。
关于 ziplist 更多的源码细节，可参考 Redis5 设计与源码分析的压缩列表章节
哈希表
跳表
整数数组
string
hash
list
set
sorted set
HyperLogLog
bitmap
GEO
stream
pub / sub
pipelining
transaction
通常说，Redis 是单线程，主要是指 Redis 的网络 IO 和键值对读写是由一个线程来完成的，这也是 Redis 对外提供键值存储服务的主要流程。但 Redis 的其他功能，比如持久化、异步删除、集群数据同步等，其实是由额外的线程执行的。可见严格来说，Redis 并不是单线程的。
对于一个多线程的系统来说，在有合理的资源分配的情况下，可以增加系统中处理请求操作的资源实体，进而提升系统能够同时处理的请求数，即吞吐率。通常情况下，采用多线程后，如果没有良好的系统设计，实际得到的结果会不尽人意。一个关键的瓶颈在于，系统中通常会存在被多线程同时访问的共享资源，比如一个共享的数据结构。当有多个线程要修改这个共享资源时，为了保证共享资源的正确性，就需要有额外的机制进行保证，而这个额外的机制，就会带来额外的开销。
并发访问控制一直是多线程开发中的一个难点问题，如果没有精细的设计，比如说，只是简单地采用一个粗粒度互斥锁，就会出现不理想的结果：即使增加了线程，大部分线程也在等待获取访问共享资源的互斥锁，并行变串行，系统吞吐率并没有随着线程的增加而增加。
通常来说，单线程的处理能力要比多线程差很多，但是 Redis 却能使用单线程模型达到每秒数十万级别的处理能力，这是为什么呢？一方面，Redis 的大部分操作在内存上完成，再加上它采用了高效的数据结构，例如哈希表和跳表，这是它实现高性能的一个重要原因。另一方面，就是 Redis 采用了多路复用机制，使其在网络 IO 操作中能并发处理大量的客户端请求，实现高吞吐率。还有一方面就是 Redis 利用单线程处理其核心流程，避免线程上下文切换和多线程所要引入的锁机制、同步机制等，所以在处理某个操作时，切忌使用耗时的命令，如复杂度是 O(n) 的命令；Redis 利用单线程处理核心操作的设计和 LMAX 团队设计 Disruptor 利用单线程处理核心业务逻辑有异曲同工之妙，LMAX 团队利用 Disruptor 实现了一个单线程的 Matching Engine，号称每秒可以处理 600 万订单。
什么是 IO 多路复用？复用在计算机领域是一种设计思想，本质是为了解决有限资源和过多使用者之间的不平衡问题，但是依赖于资源的可释放性。IO 多路复用就是协调多个可释放资源的 fd 交替共享任务处理线程，达到多个 fd 使用一个处理线程的目的，好处就是利用非常少的线程资源并发处理大量的连接，性能很高。Linux 操作系统提供了 select/epoll 等的功能，目的是提供网络 IO 的多路复用；复用是一种设计思想，应用已久，其本质是解决有限资源和过多使用者之间不平衡的问题，而且这里的有限资源具有可释放性；复用思想用在网络 IO 中，有限的资源是线程，而使用者是 socket 文件描述符，IO 多路复用就是使用有限的线程资源处理大量的网络 IO，线程可以是一个，也可以是一个线程池；IO 复用技术就是协调多个可释放资源的 FD 交替共享任务处理线程完成通信任务，实现多个 fd 对应 1 个任务处理线程。资源可释放性，举个例子理解一下：ICU 病房里的呼吸机被占用了就是不可释放的；而医护人员是可释放的，因为一个医护人员可以看护多个病房；(后面在专门分析 Linux 中的 select / epoll 是如何实现 IO 多路复用的)
Redis 正是利用了 IO 多路复用的特性，基于事件驱动实现了高性能的数据库服务，具体处理流程如下：
在 Redis 中，核心是文件事件处理器，文件可以理解为 Socket 连接、定时任务等，事件可以理解为读写事件等，文件事件处理器就是针对不同事件的处理程序；基本处理流程：Redis 的 IO 多路复用程序监听到事件到达，把事件进行封装放到指令队列中（这个队列就是一个个 socket 和它相关的事件），文件事件处理器就从指令队列中获取事件，每次取一个事件进行处理，顺序执行，比如是 AE_READABLE 事件，就关联命令请求处理器进行处理，处理完成后把 socket 的 AE_WRITABLE 事件和命令回复处理器关联。
基于单线程的 Reactor 模式开发的文件事件处理器程序，是 Redis 基于事件驱动的核心。文件事件是对Socket 操作的抽象，Socket的 事件有 accept 事件、写事件、读事件、关闭等；IO 多路复用程序负责监听多个 socket，向文件事件分派器发送产生了事件的 socket；产生的事件会放在一个队列里，通过这个队列，以有序、同步、每次一个套接字的方式向文件事件分派器传送socket，处理完成之后才会取下一个socket 文件事件处理器
如果是客户端要连接 redis，那么会为 Socket 关联连接应答处理器。
如果是客户端要写数据到 redis，那么会为 Socket 关联命令请求处理器。
如果是客户端要从 redis 读数据，那么会为 Socket 关联命令回复处理器
更加深入的学习网络 IO(网络是一个可以一直学习下去，并不断发现新天地的东西)，参考：
Linux select / epoll
TODO
AOF: Append Only File，是一种持久化机制，AOF 保存的是服务器端收到的写命令，AOF 的持久化策略:
AOF 是在 Redis 执行命令成功后写入命令到 aof 文件的，为了避免额外的检查开销，Redis 在向 AOF 里面记录日志的时候，并不会先去对这些命令进行语法检查。所以，如果先记日志再执行命令的话，日志中就有可能记录了错误的命令，Redis 在使用日志恢复数据时，就可能会出错。而写后日志这种方式，就是先让系统执行命令，只有命令能执行成功，才会被记录到日志中，否则，系统就会直接向客户端报错。所以，Redis 使用写后日志这一方式的一大好处是，可以避免出现记录错误命令的情况。
AOF 还有一个好处：它是在命令执行后才记录日志，所以不会阻塞当前的写操作。
AOF 的缺点：1. 如果刚执行完一个命令，还没有来得及记日志就宕机了，那么这个命令和相应的数据就有丢失的风险。如果此时 Redis 是用作缓存，还可以从后端数据库重新读入数据进行恢复，但是，如果 Redis 是直接用作数据库的话，此时，因为命令没有记入日志，所以就无法用日志进行恢复了。2. AOF 虽然避免了对当前命令的阻塞，但可能会给下一个操作带来阻塞风险。这是因为，AOF 日志也是在主线程中执行的，如果在把日志文件写入磁盘时，磁盘写压力大，就会导致写盘很慢，进而导致后续的操作也无法执行了。
想要获得高性能，就选择 No 策略；如果想要得到高可靠性保证，就选择 Always 策略；如果允许数据有一点丢失，又希望性能别受太大影响的话，那么就选择 Everysec 策略。
AOF 重写
AOF 是一个追加写的文件，一直追加下去，这个文件就会变的很大，文件过大就会带来一些问题：一是，文件系统本身对文件大小有限制，无法保存过大的文件；二是，如果文件太大，之后再往里面追加命令记录的话，效率也会变低；三是，如果发生宕机，AOF 中记录的命令要一个个被重新执行，用于故障恢复，如果日志文件太大，整个恢复过程就会非常缓慢，这就会影响到 Redis 的正常使用。
而且由于 AOF 存储的是一堆写命令，对重复的写命令可以合并为一条，所以对 AOF 文件进行重写，来减少重复 key，降低日志文件大小。
AOF 的重写是由后台线程 bgrewriteaof 来完成的，这也是为了避免阻塞主线程，导致数据库性能下降。
todo 一张图
AOF 重写这部分涉及到了操作系统层面的一些知识，主要是在 fork bgrewriteaof 子进程时需要做内存拷贝，如果在将父进程的内存拷贝一份给子进程，势必会阻塞父进程，在 Redis 中这是不允许的，所以就有了 COW 技术，详情参考：
在 fork 函数调用时，父进程和子进程会被 Kernel 分配到不同的虚拟内存空间中，所以在两个进程看来它们访问的是不同的内存：
在真正访问虚拟内存空间时，Kernel 会将虚拟内存映射到物理内存上，所以父子进程共享了物理上的内存空间；
当父进程或者子进程对共享的内存进行修改时，共享的内存才会以页为单位进行拷贝，父进程会保留原有的物理空间，而子进程会使用拷贝后的新物理空间；
在 Redis 服务中，子进程只会读取共享内存中的数据，它并不会执行任何写操作，只有父进程会在写入时才会触发这一机制，而对于大多数的 Redis 服务或者数据库，写请求往往都是远小于读请求的，所以使用 fork 加上写时拷贝这一机制能够带来非常好的性能，也让 BGSAVE 这一操作的实现变得非常简单。
在面向百万、千万级别的用户规模时，横向扩展的 Redis 切片集群会是一个非常好的选择。在只使用单个实例的时候，数据存在哪儿，客户端访问哪儿，都是非常明确的，但是，切片集群不可避免地涉及到多个实例的分布式管理问题。要想把切片集群用起来，我们就需要解决两大问题：
数据切片后，在多个实例之间如何分布？
客户端怎么确定想要访问的数据在哪个实例上？
切片集群是一种保存大量数据的通用机制，Redis 官方提供了 Redis Cluster 的解决方案。Redis Cluster 方案采用哈希槽（Hash Slot），来处理数据和实例之间的映射关系，一个切片集群共有 16384 个哈希槽，这些哈希槽类似于数据分区，每个键值对都会根据它的 key，被映射到一个哈希槽中。
映射过程分为两大步：首先根据键值对的 key，按照CRC16 算法计算一个 16 bit 的值；然后，再用这个 16bit 值对 16384 取模，得到 0~16383 范围内的模数，每个模数代表一个相应编号的哈希槽。
此外，在部署 Redis Cluster 时，可以使用 cluster create 命令创建集群，此时，Redis 会自动把这些槽平均分布在集群实例上。例如，如果集群中有 N 个实例，那么，每个实例上的槽个数为 16384/N 个。当然也可以使用 cluster meet 命令手动建立实例间的连接，形成集群，再使用 cluster addslots 命令，指定每个实例上的哈希槽个数。（Note: 在手动分配哈希槽时，需要把 16384 个槽都分配完，否则 Redis 集群无法正常工作。）
通过哈希槽，切片集群就实现了数据到哈希槽、哈希槽再到实例的分配。
