引言

事务管理是日常开发过程中绕不开的技术，引入事务的目的是为了保证数据持久化过程中的 一致性(Consistency) 。事务的概念最初是源于数据库，但今天的信息系统中，所有需要保证数据正确性（一致性）的场景下，包括但不限于数据库、缓存、事务内存、消息、队列、对象文件存储等等，都有可能会涉及到事务处理。这篇总结主要是总结清楚事务的来龙去脉，无关具体的某个中间件。深度推荐《周志明的软件架构课》

定义事务的ACID

• 原子性（Atomic）同一业务处理过程中，事务保证了多项对数据的修改，要么全部成功，要么全部失败。
• 隔离性（Isolation）在不同的业务处理过程中，事务保证了各自读写的业务数据相互不可见，不会彼此影响。
• 持久性（Durability）事务保证了当业务处理完成后，事务提交后能够被持久化，不会丢失。
• 一致性（Consistency）一致性。利用A, I, D 保证了业务数据的一致性。

A, I, D是手段，C 是目的。 ACID更像是凑单词。

本地事务（局部事务）Local Transaction

• 本地事务是指仅操作特定单一事务资源，不需要全局事务管理器进行协调的事务。

• 本地事务是最基础的一种事务处理方案，通常只适用于单个服务使用单个数据源的场景，它是直接依赖于数据源（通常是数据库系统）本身的事务能力来工作的。

• 本地事务的开启、终止、提交、回滚、嵌套、设置隔离级别、乃至与应用代码贴近的传播方式，全部都要依赖底层数据库的支持。

• 例如：Spring提供的事务注解，如果数据库引擎不支持那么这个注解也是无意义的。

  1 2 3 4

  @Transactional(propagation = Propagation.REQUIRED, //传播方式 rollbackFor = Exception.class, //回滚异常 isolation = ISOLATION_REPEATABLE_READ //隔离级别 )

原子性和持久性

扩展知识：ARIES 理论，现代主流数据库的事务实现都受到该理论的影响

原子性和持久性密切相关，原子性保证了事务的多个操作要么都生效要么都不生效，不会存在中间状态。持久性则保证了事务一旦生效则不会因为任何原因而导致其修改的内容被撤销或者丢失。

崩溃回复（Crash Recovery）

• 未提交事务：程序还没修改完一系列整个业务数据，数据库已经将其中一个或者两个数据的变动写入了磁盘，此时崩溃，一旦重启后，数据库必须想办法得知崩溃前发生过一次不完整的购物操作，将已经修改过的数据从磁盘中恢复成为之前没有改过的样子。
• 已提交事务：程序已经修改完了所有数据，数据还没将全部的数据写入磁盘，此时出现崩溃。重启之后数据库必须知道崩溃前发生过一次的完整操作，将还没来得及写入磁盘的数据重新写入。保证持久性。

这种数据恢复操作被称作是：崩溃恢复。

Commit Logging

为了能够顺利完成崩溃恢复，那么需要记录下数据操作的全部信息：比如修改的什么数据，位于哪个内存页和磁盘块中，从什么值改成了什么值等等，以顺序追加的文件写入方式记录的磁盘中（顺序写磁盘是高效的）。只有日志记录全部落盘，见到代表事务成功提交的“Commit Record”，数据库才会根据日志上的信息真正的对数据进行修改。修改完成后在日志中加一条“End Record”标识已经完成持久化，这种实现方式被称为“Commit Logging”

另外一种实现：Shadow Paging

SQLite Version 3采用这种方式实现。

将原来数据复制一份副本也可以称之为临时数据，原来数据保持不变，在副本数据上进行操作。再修改完成后改变“两份数据的指针”。

Shadow Paging 相对简单，但涉及到隔离性与锁时，Shadow Paging 实现的事务并发能力相对有限，因此在高性能的数据库中应用不多。

Commit Logging保证持久性：日志一旦写入Commit Logging，那么整个事务就是成功的。即使崩溃，重启后根据日志进行恢复现场，继续修改即可。

Commit Logging保证原子性：如果日志没有写入成功就发生崩溃，重启后会看到一部分没有Commit Logging的数据，那么将这部分数据标识为回滚状态即可，整个事务就像没有发生过。保证了原子性。

Commit Logging 存在一个巨大的缺陷：所有对数据的真实修改都必须发生在事务提交、日志写入了 Commit Record 之后，即使事务提交前磁盘 I/O 有足够空闲、即使某个事务修改的数据量非常庞大，占用大量的内存缓冲，无论何种理由，都决不允许在事务提交之前就开始修改磁盘上的数据，这一点对提升数据库的性能是很不利的。

Write-Ahead Logging（先写日志）

为了修复Commit Logging缺陷ARIES 提出了“Write-Ahead Logging”的日志改进方案，其名字里所谓的“提前写入”（Write-Ahead），就是允许在事务提交之前，提前写入变动数据的意思。

Write-Ahead Logging 先将何时写入变动数据，按照事务提交时点为界，分为了 FORCE 和 STEAL 两类：

• FORCE：当事务提交后，要求变动数据必须同时完成写入—则称为 FORCE，如果不强制变动数据必须同时完成写入—则称为 NO-FORCE。现实中绝大多数数据库采用的都是 NO-FORCE 策略，只要有了日志，变动数据随时可以持久化，从优化磁盘 I/O 性能考虑，没有必要强制数据写入立即进行。
• STEAL：在事务提交前，允许变动数据提前写入则称为 STEAL，不允许则称为 NO-STEAL。从优化磁盘 I/O 性能考虑，允许数据提前写入，有利于利用空闲 I/O 资源，也有利于节省数据库缓存区的内存。

Commit Logging允许NO-FORCE但是不允许STEAL。因为在事务提交前写入了一部分数据，如果发生崩溃，那么提前写入的数据就变成了脏数据。

Write-Ahead Logging允许NO-FORCE也允许STEAL，给出的解决办法是增加了Undo Log日志。当数据写入磁盘前，必须先记录Undo Log,写明修改了什么值并生成对应的回滚段。以便事务再发生崩溃恢复的时候根据Undo Log对提前写入的数据变动进行擦除。

Undo Log 现在一般被翻译为“回滚日志”，此前记录的用于崩溃恢复时重演数据变动的日志，就相应被命名为 Redo Log，一般翻译为“重做日志”。

Write-Ahead Logging 在崩溃恢复时，会以此经历以下三个阶段：

1. 分析阶段（Analysis）：从最后一次检查点Checkpoint（从这个检查点之前所有的数据都成功落盘）开始扫描日志，找出所有没有End Record的事务，组成待恢复的事务集合（一般包括 Transaction Table 和 Dirty Page Table）；
2. 重做阶段（Redo）：这个阶段依据分析阶段产生的待恢复的事务集合来重演历史（Repeat History）找出所有的包含Commit Record的日志，将它们写入磁盘，写入完成后追加一个End Record，然后移除待恢复 集合。
3. 回滚阶段（Undo）：该阶段处理经过分析、重做阶段后剩余的恢复事务集合，此时剩下的都是需要回滚的事务（被称为 Loser），根据 Undo Log 中的信息回滚这些事务。

数据库按照“是否允许 FORCE 和 STEAL”可以产生四种组合，从优化磁盘 I/O 的角度看，NO-FORCE 加 STEAL 组合的性能无疑是最高的；从算法实现与日志的角度看，NO-FORCE 加 STEAL 组合的复杂度无疑是最高的。这四种组合与 Undo Log、Redo Log 之间的具体关系如下图所示：

隔离性

隔离性保证了每个事务各自读写的相互独立性。主要是为了解决事务并发问题，有并发的地方就有锁。

• 写锁（Write Lock 也叫排他锁eXclusive Lock，简写X-Lock）：只有持有写锁的事务才能对数据进行写入操作，数据加写锁时，其它事务不能写入数据，也不能施加读锁（写锁禁止其他事务施加读锁，而不是禁止事务读取数据。）。

• 读锁（Read Lock 也叫共享锁Shared Lock，简写S-Lock）：多个事务可以对同一个数据添加读锁，添加了读锁后就不能添加写锁，所以事务不能对数据进行写入，但仍然可以读取。对持有读锁的事务，如果该事务只有一个读锁就可以直接升级为写锁，然后写入数据。

• 范围锁（Range Lock）对某个范围数据直接添加排他锁，在这个范围的数据不能被读取，也不能被写入。如 select * from books where price < 100 for update;

  请注意“范围不能写入”与“一批数据不能写入”的差别，也就是我们不要把范围锁理解成一组排他锁的集合。加了范围锁后，不仅无法修改该范围内已有的数据，也不能在该范围内新增或删除任何数据，这是一组排他锁的集合无法做到的。

可串行化（Serializable）

对事务所有读、写的数据全都加上读锁、写锁和范围锁即可（这种可串行化的实现方案称为 Two-Phase Lock）。

强度最高的隔离性。粗粒度锁，事务顺序执行那么就不会互相产生影响。但是吞吐量最低。

可重复读（Repeatable Read）

可重复读的意思是对事务所涉及到的数据加读锁和写锁，并且一直持续到事务结束，但是不再添加范围锁。

缺点：在可读事务中的幻读问题（MySQL 中的InnoDB在只读事务中不存在幻读问题，只在读写事务提升为当前读后存在这个问题）如下读事务：

1
2
3
4
5
6
7
8
9

/* 时间顺序：1，事务： T1 */
SELECT count(1) FROM books WHERE price < 100  

/* 时间顺序：2，事务： T2 */
INSERT INTO books(name,price) VALUES ('深入理解Java虚拟机',90)  

 /* 时间顺序：3，事务： T1  会查出来 T2 插入的数据，但是InnoDB不会*/
SELECT count(1) FROM books WHERE price < 100        

读提交（Read Committed）

读提交会对事务涉及到的数据加写锁，会一直持续到事务结束，加的读锁会在读完之后立马释放。

读提交有了不可重复读—-对同一行数据两次查询得到了不同的结果。

原因是读已提交的隔离级别缺乏贯穿整个事务周期的读锁，无法禁止读取过的数据发生变化。

读未提交（Read UnCommitted）

读未提交只会对事务所涉及到的数据加写锁，不会加读锁。

读未提交有了脏读—-一个事务读到了另外一个事务未提交的数据

其实，不同隔离级别以及幻读、脏读等问题都只是表面现象，它们是各种锁在不同加锁时间上组合应用所产生的结果，锁才是根本的原因。除了锁之外，以上对四种隔离级别的介绍还有一个共同特点，就是一个事务在读数据过程中，受另外一个写数据的事务影响而破坏了隔离性。针对这种“一个事务读 + 另一个事务写”的隔离问题，有一种名为“多版本并发控制”（Multi-Version Concurrency Control，MVCC）的无锁优化方案被主流的商业数据库广泛采用。

多版本并发控制MVCC（Multi-Version Concurrency Control）无锁化。

MVCC是一种读取优化策略，它的“无锁”是特指读取数据时不需要加锁。

MVCC只针对读+写的场景优化，如果是两个事务同时修改数据，即写+写的场景那么几乎没有什么优化的空间

MVCC 的基本思路是对数据库的任何修改都不会直接覆盖之前的数据，而是产生一个新版副本与老版本共存，以此达到读取时可以完全不加锁的目的。这句话里的“版本”是个关键词，你不妨将其理解为数据库中每一行记录都存在两个看不见的字段：CREATE_VERSION 和 DELETE_VERSION，这两个字段记录的值都是事务 ID（事务 ID 是一个全局严格递增的数值），然后：

1. 数据被插入时：CREATE_VERSION 记录插入数据的事务 ID，DELETE_VERSION 为空。
2. 数据被删除时：DELETE_VERSION 记录删除数据的事务 ID，CREATE_VERSION 为空。
3. 数据被修改时：将修改视为“删除旧数据，插入新数据”，即先将原有数据复制一份，原有数据的 DELETE_VERSION 记录修改数据的事务 ID，CREATE_VERSION 为空。复制出来的新数据的 CREATE_VERSION 记录修改数据的事务 ID，DELETE_VERSION 为空。

• 隔离级别是可重复读：总是读取 CREATE_VERSION 小于或等于当前事务 ID 的记录，在这个前提下，如果数据仍有多个版本，则取最新（事务 ID 最大）的。
• 隔离级别是读已提交：总是取最新的版本即可，即最近被 Commit 的那个版本的数据记录。

Comment and share

IO，英文全称是Input/Output，翻译过来就是输入/输出。平时我们听得挺多，就是什么磁盘IO，网络IO。那IO到底是什么呢？

从计算机结构定义I/O

冯诺依曼结构将计算机分为5个部分：运算器，控制器，存储器，输入设备，输出设备

从计算机架构中看I/O就是：涉及计算机核心与其他设备间数据迁移的过程，就是IO。就是从磁盘读取数据到内存，这算一次输入，对应的，将内存中的数据写入磁盘，就算输出。这就是IO的本质。

从操作系统定义I/O

分清用户空间和内核空间

内核空间是操作系统内核访问的区域，是受保护的空间，而用户空间是应用程序访问的内存区域

真正执行IO的是在内核空间

我们应用程序是跑在用户空间的，它不存在实质的IO过程，真正的IO是在操作系统执行的。即应用程序的IO操作分为两种动作：IO调用和IO执行。IO调用是由进程（应用程序的运行态）发起，而IO执行是操作系统内核的工作。此时所说的IO是应用程序对操作系统IO功能的一次触发，即IO调用。

操作系统的一次IO过程

1. IO调用：应用程序进程向操作系统内核发起调用。

2. IO执行：操作系统完成IO操作

   操作系统完成IO操作还包括两个步骤

   1. 准备数据阶段：内核等待I/O设备准备好数据

   2. 拷贝数据阶段：将数据从内核缓冲区拷贝到用户进程缓冲区

      

其实IO就是把进程的内部数据转移到外部设备，或者把外部设备的数据迁移到进程内部。外部设备一般指硬盘、socket通讯的网卡。一个完整的IO过程包括以下几个步骤：

• 应用程序进程向操作系统发起IO调用请求
• 操作系统准备数据，把IO外部设备的数据，加载到内核缓冲区
• 操作系统拷贝数据，即将内核缓冲区的数据，拷贝到用户进程缓冲区

阻塞I/O

应用程序的进程发起IO调用，但是如果内核的数据还没准备好的话，那应用程序进程就一直在阻塞等待，一直等到内核数据准备好了，从内核拷贝到用户空间，才返回成功提示，此次IO操作，称之为阻塞IO。

• 阻塞I/O典型：阻塞socket，java BIO
• 缺点：如果内核数据一直没准备好，那用户进程将一直阻塞，浪费性能，可以使用非阻塞IO优化。

非阻塞I/O 模型

I/O多路复用是一种同步I/O模型，实现一个线程可以监视多个FD（文件句柄）；一旦某个文件句柄就绪，就能够通知应用程序进行相应的读写操作。没有文件句柄就绪时会阻塞应用程序，交出CPU。多路指的是网络链接，复用指的是同一个线程（进程）

1. 应用进程向操作系统内核，发起recvfrom读取数据。

2. 操作系统内核数据没有准备好，立即返回EWOULDBLOCK错误码。

3. 应用进程轮训调用，继续向操作系统内核发起recvfrom读取数据。

4. 操作系统内核数据准备好了，从内核缓冲区拷贝到用户空间。

5. 完成调用，返回成功。

   缺点：非阻塞IO模型，简称NIO，Non-Blocking IO。它相对于阻塞IO，虽然大幅提升了性能，但是它依然存在性能问题，即频繁的轮询，导致频繁的系统调用，同样会消耗大量的CPU资源。可以考虑IO复用模型，去解决这个问题。

I/O多路复用

NIO利用无效的轮训会导致CPU资源消耗，解决这种无效轮训最好的方式就是通知机制，内核准备好数据后通知用户进程即可。

IO多路复用的核心：操作系统提供了一类函数：select, poll, epll 等同时监控多个fd操作，任何一个返回内核数据就绪，应用进程再发起recvfrom调用。

文件描述符fd（file descriptor）解释：它是计算机科学中的一个术语，形式上是一个非负整数。当程序打开一个现有文件或者创建一个新文件时，内核向进程返回一个文件描述符。

I/O复用select模式

应用进程通过调用select函数，可以同时监控多个fd，在select函数监控的fd中，只要有任何一个数据状态准备就绪了，select函数都会返回可读状态，这时应用再发起recvfrom调用。

select缺点

• 监听IO最大连接数有限，在Linux系统上一般为1024
• select函数返回后，是通过遍历fdset，找到就绪的fd。（仅仅知道有I/O发生，却不知道哪几个流，所以遍历所有流）

因为存在连接数限制，所以后来又提出了poll。与select相比，poll解决了连接数的问题，但是select和poll一样，还是需要通过文件描述符来获取已经就绪的socket。如果同时连接的大量客户端，在一时刻只有极少数就绪状态，伴随着监视的描述符数量的增长，效率也会线性下降。

I/O多路复用之epoll

1. epoll先通过epoll_ctl()来注册一个fd（文件描述符）
2. 当fd就绪时，内核会采用回调机制，迅速激活这个fd，当进程调用epoll_wait()时便得到通知。

select poll epoll区别

epoll明显优化了IO的执行效率，但在进程调用epoll_wait()时，仍然可能被阻塞。又提出了：等发出请求后，数据准备好通知，这就诞生了信号驱动IO模型。

信号IO驱动模型

信号驱动IO不再用主动询问的方式去确认数据是否就绪，而是向内核发送一个信号（调用signaction的时候建立一个sigio信号），然后应用用户进程可以去做别的事，不用阻塞。当内核数据准备好后，再通过SIGIO信号通知应用进程，数据准备好后的可读状态。应用用户进程收到信号后，立即调用recvfrom，去读取数据。

还不是完全的异步IO：数据复制到应用缓冲的时候，应用进程还是阻塞的。

真正的异步IO(AIO)

BIO，NIO和信号驱动，在数据从内核复制到缓冲区的时候都是阻塞的，都不算真正的异步IO。AIO实现了全流程的非阻塞，就是应用进程发出系统调用后，是立即返回的，但是返回的不是处理结果，而是表示提交成功的意思。等到内核数据准备好，将数据拷贝到用户进程缓冲区，发送信号通知用户进程IO操作

阻塞、非阻塞、同步、异步IO划分

参考连接

https://mp.weixin.qq.com/s/77G2NxfjZlT-icfqrHCizQ

Comment and share

Redis为什么这么快？在除了它是内存型数据库外，它的数据结构，IO模型也是它这么快速的重要原因。我们都知道Redis是单线程模型，那么Redis是如何利用单线程快速的处理高并发业务的呢？带着疑问来看下边的内容更容易理解。

Redis为什么使用单线程？

了解多线程的开销

1. 在使用多线程中，如果合理分配资源可以增加系统中处理请求操作的实体，进而能够提升同时处理的请求数，即吞吐率。但是如图所示进一步增加线程时，系统吞吐率就增长延迟了，有时甚至还会出现下降的情况。

参考文章

2. 系统中通常会存在被多线程同时访问的共享资源，比如一个共享的数据结构。当有多个线程要修改这个共享资源时，为了保证共享资源的正确性，就需要有额外的机制进行保证，而这个额外的机制，就会带来额外的开销。

   Redis 有 List 的数据类型，并提供出队（LPOP）和入队（LPUSH）操作。假设 Redis 采用多线程设计，如下图所示，现在有两个线程 A 和 B，线程 A 对一个 List 做 LPUSH 操作，并对队列长度加 1。同时，线程 B 对该 List 执行 LPOP 操作，并对队列长度减 1。为了保证队列长度的正确性，Redis 需要让线程 A 和 B 的 LPUSH 和 LPOP 串行执行，这样一来，Redis 可以无误地记录它们对 List 长度的修改。否则，我们可能就会得到错误的长度结果。这就是多线程编程模式面临的共享资源的并发访问控制问题。

3. 并发访问控制一直是多线程开发中的一个难点问题，如果没有精细的设计，比如说，只是简单地采用一个粗粒度互斥锁，就会出现不理想的结果：即使增加了线程，大部分线程也在等待获取访问共享资源的互斥锁，并行变串行，系统吞吐率并没有随着线程的增加而增加。

4. 采用多线程开发一般会引入同步原语来保护共享资源的并发访问，这也会降低系统代码的易调试性和可维护性。为了避免这些问题，Redis 直接采用了单线程模式。

单线程Redis为什么快？

1. 大部分属于内存操作
2. 高效数据库
3. IO多路复用

阻塞式I/O模型与阻塞点

阻塞式I/O处理一个GET请求流程：

1. 监听客户端请求（bind/listen）
2. 和客户端建立连接（accept）阻塞点1
3. 从socket中读取请求（recv）阻塞点2
4. 解析客户端发送请求（parse）
5. 根据请求读取键值对数据（get）
6. 向socket中写数据，最后给客户端返回结果（send）

潜在的阻塞点，分别是 accept() 和 recv()。当 Redis 监听到一个客户端有连接请求，但一直未能成功建立起连接时，会阻塞在 accept() 函数这里，导致其他客户端无法和 Redis 建立连接。类似的，当 Redis 通过 recv() 从一个客户端读取数据时，如果数据一直没有到达，Redis 也会一直阻塞在 recv()。

非阻塞式I/O

Socket 网络模型的非阻塞模式设置，主要体现在三个关键的函数调用上，如果想要使用 socket 非阻塞模式，就必须要了解这三个函数的调用返回类型和设置模式。

在 socket 模型中，不同操作调用后会返回不同的套接字类型。socket() 方法会返回主动套接字，然后调用 listen() 方法，将主动套接字转化为监听套接字，此时，可以监听来自客户端的连接请求。最后，调用 accept() 方法接收到达的客户端连接，并返回已连接套接字。

1. 针对监听套接字，我们可以设置非阻塞模式：当 Redis 调用 accept() 但一直未有连接请求到达时，Redis 线程可以返回处理其他操作，而不用一直等待。但是，你要注意的是，调用 accept() 时，已经存在监听套接字了。
2. 针对已连接套接字设置非阻塞模式：Redis 调用 recv() 后，如果已连接套接字上一直没有数据到达，Redis 线程同样可以返回处理其他操作。我们也需要有机制继续监听该已连接套接字，并在有数据达到时通知 Redis。
3. 这样才能保证 Redis 线程，既不会像基本 I/O 模型中一直在阻塞点等待，也不会导致 Redis 无法处理实际到达的连接请求或数据。

基于多路复用的高性能I/O模型

Linux中的I/O多路复用就是一个线程处理多个I/O流，就是我们经常说的select/epoll(理解IO模型)机制。

Redis单线程运行下该机制允许内核中，同时存在多个监听套接字和已连接套接字。内核会监听这些套接字上的连接请求或者数据请求。一旦有请求到达，就会交给redis线程处理，这样就实现了一个Redis线程处理多个I/O流的效果

下图就是基于多路复用的 Redis IO 模型。图中的多个 FD 就是刚才所说的多个套接字。Redis 网络框架调用 epoll 机制，让内核监听这些套接字。此时，Redis 线程不会阻塞在某一个特定的监听或已连接套接字上，也就是说，不会阻塞在某一个特定的客户端请求处理上。正因为此，Redis 可以同时和多个客户端连接并处理请求，从而提升并发性。

1. select/epoll 提供了基于事件的回调机制，即针对不同事件的发生，调用相应的处理函数。
2. select/epoll 一旦监测到 FD 上有请求到达时，就会触发相应的事件。
3. 这些事件会被放进一个事件队列，Redis 单线程对该事件队列不断进行处理。这样一来，Redis 无需一直轮询是否有请求实际发生，这就可以避免造成 CPU 资源浪费。同时，Redis 在对事件队列中的事件进行处理时，会调用相应的处理函数，这就实现了基于事件的回调。因为 Redis 一直在对事件队列进行处理，所以能及时响应客户端请求，提升 Redis 的响应性能。

Accept、Read处理流程

这两个请求分别对应 Accept 事件和 Read 事件，Redis 分别对这两个事件注册 accept 和 get 回调函数。当 Linux 内核监听到有连接请求或读数据请求时，就会触发 Accept 事件和 Read 事件，此时，内核就会回调 Redis 相应的 accept 和 get 函数进行处理。

Comment and share

众所周知redis作为内存数据库有个重要的特点 — 快。除了因为是在内存中读写快之外，那就是它的查找很快，能够快速的定位到存储位置。能够快速找到的原因基于Redis的数据结构。

数据类型

以下是Redis中的基本类型，也就是数据的保存形式，而数据结构则是这些数据类型在底层的实现。

1. String：简单动态字符串
2. List：双向链表，压缩列表
3. Hash：压缩列表，哈希表
4. Set：哈希表，整数数组
5. Sorted Set：压缩列表，跳表

String类型的底层结构只有一个简单动态字符串，而List，Hash，Set，Sorted Set都有两种底层实现结构。通常情况把这四种类型称为集合类型，特点是：一个键对应了一个集合的数据。

键和值用什么数据结构？

全局哈希表

为了实现快速访问Redis实现了一个全局哈希表保存所有键值对。一个哈希表就是一个数组，数组的每个元素称之为哈希桶。每个哈希桶中保存了键值对数据。哈希桶中的值不保存值本身，而是指向具体的指针。也就是说不管是String还是集合类型，哈希桶中的元素都是指向它们的指针。

优点：

时间复杂度为O(1)查找。

缺点：

往Redis写入大量数据后，哈希表的冲突问题和rehash可能带来的阻塞。

如何解决hash冲突 — 链式hash

Redis解决hash冲突的方式，就是链式hash（跟Java中的HashMap一样）。同一个哈希桶中的多个元素用一个链表保存，它们之间依使用指针连接

缺点：

针对链表上的查找只能采用O(n)时间复杂度的依次查找。

如何解决hash桶上链表只能依次查找慢的问题 — rehash操作

Redis会对哈希会对哈希表做Rehash操作，rehash也就是增加Hash桶数量，让逐渐增多的entry元素能够在更多的桶之间分散保存。Redis默认使用了两个全局hash表：

1. 哈希表I 和哈希表II

2. 一开始插入数据默认使用哈希表I 此时的哈希表II并没有分配空间。

3. 随着数据的逐步增加Redis开始执行Rehash，分为以下三步：

   1. 给哈希表II 分配更大的空间，例如是哈希表I的二倍。
   2. 把哈希表I 中的数据重新映射并拷贝到哈希表II 中
   3. 释放哈希表I 的空间。

   缺点：

   第二步涉及大量的数据拷贝，如果一次性把哈希表 1 中的数据都迁移完，会造成 Redis 线程阻塞，

如何避免Rehash过程中拷贝带来的线程阻塞 — 渐进式 rehash

Redis 仍然正常处理客户端请求，每处理一个请求时，从哈希表 1 中的第一个索引位置开始，顺带着将这个索引位置上的所有 entries 拷贝到哈希表 2 中；等处理下一个请求时，再顺带拷贝哈希表 1 中的下一个索引位置的 entries。如下图所示：

压缩列表

压缩列表类似于一个数组，数组中的每一个元素都对应保存着一个数据，和数组不同的是，压缩列表在表头有三个字段zlbytes(列表长度), zltail(列表尾偏移量) 和 zllen(列表entry个数)，zlend(列表结束)

如果我们要查找定位第一个元素和最后一个元素，可以通过表头三个字段的长度直接定位，复杂度是 O(1)。

而查找其他元素时，就没有这么高效了，只能逐个查找，此时的复杂度就是 O(N) 了。

跳表

有序链表只能逐一查找元素，导致操作起来非常缓慢，于是就出现了跳表。具体来说，跳表在链表的基础上，增加了多级索引，通过索引位置的几个跳转，实现数据的快速定位。

1. 从第一个元素开始，每两个元素选一个出来作为索引。

2. 这些索引再通过指针指向原始的链表。例如，从前两个元素中抽取元素 1 作为一级索引，从第三、四个元素中抽取元素 11 作为一级索引。

3. 此时，我们只需要 4 次查找就能定位到元素 33 了。

   可以看到，这个查找过程就是在多级索引上跳来跳去，最后定位到元素。这也正好符合“跳”表的叫法。当数据量很大时，跳表的查找复杂度就是 O(logN)。

数据结构时间复杂度

操作复杂度

1. 单元素操作

HGET、HSET 和 HDEL 是对哈希表做操作，所以它们的复杂度都是 O(1)；

Set 类型用哈希表作为底层数据结构时，它的 SADD、SREM、SRANDMEMBER 复杂度也是 O(1)。

集合类型支持同时对多个元素进行增删改查，例如 Hash 类型的 HMGET 和 HMSET，Set 类型的 SADD 也支持同时增加多个元素。此时，这些操作的复杂度，就是由单个元素操作复杂度和元素个数决定的。例如，HMSET 增加 M 个元素时，复杂度就从 O(1) 变成 O(M) 了。

2. 范围操作

是指集合类型中的遍历操作，可以返回集合中的所有数据

Hash 类型的 HGETALL 和 Set 类型的 SMEMBERS，或者返回一个范围内的部分数据，List 类型的 LRANGE 和 ZSet 类型的 ZRANGE。这类操作的复杂度一般是 O(N)，比较耗时，我们应该尽量避免。

Redis 从 2.8 版本开始提供了 SCAN 系列操作（包括 HSCAN，SSCAN 和 ZSCAN），这类操作实现了渐进式遍历，每次只返回有限数量的数据。这样一来，相比于 HGETALL、SMEMBERS 这类操作来说，就避免了一次性返回所有元素而导致的 Redis 阻塞。

3. 统计操作

集合类型对集合中所有元素个数的记录

LLEN 和 SCARD。这类操作复杂度只有 O(1)，这是因为当集合类型采用压缩列表、双向链表、整数数组这些数据结构时，这些结构中专门记录了元素的个数统计，因此可以高效地完成相关操作。

4.例外

是指某些数据结构的特殊记录，例如压缩列表和双向链表都会记录表头和表尾的偏移量。

对于 List 类型的 LPOP、RPOP、LPUSH、RPUSH 这四个操作来说，它们是在列表的头尾增删元素，这就可以通过偏移量直接定位，所以它们的复杂度也只有 O(1)，可以实现快速操作。

总结

Redis 的底层数据结构，这既包括了 Redis 中用来保存每个键和值的全局哈希表结构，也包括了支持集合类型实现的双向链表、压缩列表、整数数组、哈希表和跳表这五大底层结构。

Redis 之所以能快速操作键值对，一方面是因为 O(1) 复杂度的哈希表被广泛使用，包括 String、Hash 和 Set，它们的操作复杂度基本由哈希表决定，另一方面，Sorted Set 也采用了 O(logN) 复杂度的跳表。

不过，集合类型的范围操作，因为要遍历底层数据结构，复杂度通常是 O(N)。这里，我的建议是：用其他命令来替代，例如可以用 SCAN 来代替，避免在 Redis 内部产生费时的全集合遍历操作。

当然，我们不能忘了复杂度较高的 List 类型，它的两种底层实现结构：双向链表和压缩列表的操作复杂度都是 O(N)。因此，我的建议是：因地制宜地使用 List 类型。例如，既然它的 POP/PUSH 效率很高，那么就将它主要用于 FIFO 队列场景，而不是作为一个可以随机读写的集合。

实际开发中Redis各个数据结构的应用场景

引用

《Redis核心技术与实战》

Comment and share