第18章-发布与订阅

publish
subscribe，unsubscribe
psubscribe，punsubscribe
pubsub

18.1 频道的订阅与退订

redis将所有频道的订阅关系都保存在字典pubsub_channels中：

1
2
3


struct redisServer {
	dict *pubsub_channels 
}

键是channel的名字，值是订阅这个频道的客户端链表

18.1.1 频道的订阅

18.1.2 频道的退订

18.2 pattern的订阅与退订

redis将所有pattern的订阅存在链表pubsub_patterns中：

1
2
3
4
5
6
7
8


struct redisServer {
	list *pubsub_patterns;
}

typedef struct pubsubPattern {
	redisClient *client;
	robj *pattern;
} pubsubPattern; 

18.2.1 订阅pattern

18.2.2 退订pattern

18.3 发送消息

18.3.1 将消息发送给频道订阅者

18.3.2 将消息发送给模式订阅者

18.4 查看订阅信息

18.4.1 PUBSUB CHANNELS

18.4.2 PUBSUB NUMSUB

18.4.3 PUBSUB NUMPAT

第19章-事务

事务提供了一种将多个命令请求打包，然后一次性、按顺序地执行多个命令的机制，并且在事务执行期间，服务器不会中断事务而改去执行其他客户端的命令请求，它会将事务中的所有命令都执行完毕，然后再去执行其他客户端的命令请求。

19.1 事务的实现

19.1.1 事务开始

MULTI命令可以将执行该命令的客户端从非事务状态切换至事务状态，通过在客户端状态的flags属性中打开REDIS_MULTI标识来完成

19.1.2 命令入队

客户端在事务状态下，服务器会：

遇到exec, discard, watch, multi这四个命令中的一个将会立即执行
遇到其他命令将放入事务队列，并返回QUEUED回复

事务队列：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


typedef struct redisClient {
	multiState mstate; 
} redisClient; 

typedef struct multiState {
	multiCmd *commands; 
	int count;
} multiState;

typedef struct multiCmd {
	robj **argv;
	int argc;
	struct redisCommand *cmd;
} multiCmd; 

19.1.3 事务执行

用伪代码描述流程：

1
2
3
4
5
6
7
8
9


def EXEC():
	reply_queue = []
	for argv, argc, cmd in client.mstate.commands:
		reply = execute_command(cmd, argv, argc)
		reply_queue.append(reply)
	client.flags &= ~REDIS_MULTI
	client.mstate.count = 0
	release_transaction_queue(client.mstate.commands)
	send_reply_to_client(client, reply_queue)

19.2 WATCH命令的实现

在exec命令执行之前，监视任意数量的数据库键，并在exec命令执行时，检查被监视的键是否至少有一个已经被修改过了，如果是，服务器将拒绝执行事务，并向客户端返回代表事务执行失败的空回复。

19.2.1 使用watch命令监视数据库键

1
2
3


typedef struct redisDb {
	dict *watched_keys;   // 键是被监视的key，值是链表，记录所有监视该键的客户端
}

19.2.2 监视机制的触发

所有对数据库进行修改的命令，如set, lpush, sadd, zrem, del, flushdb等，在执行后都会调用multi.c/touchWatchKey函数对watched_keys字典进行检查，查看是否有客户端正在监视刚刚被命令修改过的数据库键。若有，则会将监视被修改键的客户端的REDIS_DIRTY_CAS标识打开，表示该客户端的事务安全性已经被破坏。伪代码：

1
2
3
4


def touchWatchKey(db, key):
	if key in db.watched_keys:
		for client in db.watched_keys[key]:
			client.flags |= REDIS_DIRTY_CAS

19.2.3 判断事务是否安全

当服务器接收到一个客户端发来的exec命令时，服务器会根据这个客户端是否打开了REDIS_DIRTY_CAS标识来决定是否执行事务

19.2.4 一个完整的WATCH事务执行过程

19.3 事务的ACID性质

原子性
- 指的是提交的原子性，要么事务里的命令都提交，要么都不提交。
- 如果事务里存在命令执行失败，那么不会回滚，会继续执行事务中后续的命令。
一致性
- 解决了三个可能出错的地方：
  - 入队错误
  - 执行错误
  - 服务器停机
隔离性
- 单线程运行事务，天生具有隔离性
持久性
- 由配置决定

第20章-Lua脚本

eval
script load
evalsha

20.1 创建并修改lua环境

Redis服务器创建并修改Lua环境的整个过程由以下步骤组成：

1）创建一个基础的Lua环境，之后的所有修改都是针对这个环境进行的
2）载入多个函数库到Lua环境里面，让Lua脚本可以使用这些函数库来进行数据操作
3）创建全局表格redis，这个表格包含了对Redis进行操作的函数，比如用于在Lua脚本中执行Redis命令的redis.call函数
4）使用Redis自制的随机函数来替换Lua原有的带有副作用的随机函数，从而避免在脚本中引入副作用
5）创建排序辅助函数，Lua环境使用这个辅佐函数来对一部分Redis命令的结果进行排序，从而消除这些命令的不确定性
6）创建redis.pcall函数的错误报告辅助函数，这个函数可以提供更详细的出错信息
7）对Lua环境中的全局环境进行保护，防止用户在执行Lua脚本的过程中，将额外的全局变量添加到Lua环境中
8）将完成修改的Lua环境保存到服务器状态的lua属性中，等待执行服务器传来的Lua脚本

20.1.1 创建Lua环境

调用lua_open()创建一个新的Lua环境

20.1.2 载入函数库

Redis修改Lua环境的第一步，就是将以下函数库载入到Lua环境里面

基础库（base library）：
- 这个库包含Lua的核心（core）函数，比如assert、error、pairs、tostring、pcall等
- 另外，为了防止用户从外部文件中引入不安全的代码，库中的loadfile函数会被删除
表格库（table library）：
- 这个库包含用于处理表格的通用函数，比如table.concat、table.insert、table.remove、table.sort等
字符串库（string library）：
- 这个库包含用于处理字符串的通用函数，比如用于对字符串进行查找的string.find函数，对字符串进行格式化的string.format函数，查看字符串长度的string.len函数，对字符串进行翻转的string.reverse函数等。
数学库（math library）：
- 这个库是标准C语言数学库的接口，它包括计算绝对值的math.abs函数，返回多个数中的最大值和最小值的math.max函数和math.min函数，计算二次方根的math.sqrt函数，计算对数的math.log函数等。
调试库（debug library）：
- 这个库提供了对程序进行调试所需的函数，比如对程序设置钩子和取得钩子的debug.sethook函数和debug.gethook函数，返回给定函数相关信息的debug.getinfo函数，为对象设置元数据的debug.setmetatable函数，获取对象元数据的debug.getmetatable函数等
Lua CJSON库（http://www.kyne.com.au/~mark/software/lua-cjson.php）：
- 这个库用于处理UTF-8编码的JSON格式，其中cjson.decode函数将一个JSON格式的字符串转换为一个Lua值，而cjson.encode函数将一个Lua值序列化为JSON格式的字符串
Struct库（http://www.inf.puc-rio.br/~roberto/struct/）：
- 这个库用于在Lua值和C结构（struct）之间进行转换，函数struct.pack将多个Lua值打包成一个类结构（struct-like）字符串，而函数struct.unpack则从一个类结构字符串中解包出多个Lua值
Lua cmsgpack库（https://github.com/antirez/lua-cmsgpack）：
- 这个库用于处理MessagePack格式的数据，其中cmsgpack.pack函数将Lua值转换为MessagePack数据，而cmsgpack.unpack函数则将MessagePack数据转换为Lua值。

20.1.3 创建redis全局表格

服务器将在Lua环境中创建一个redis表格（table），并将它设为全局变量。这个redis表格包含以下函数：

用于执行Redis命令的redis.call和redis.pcall函数
用于记录Redis日志（log）的redis.log函数，以及相应的日志级别（level）常量：redis.LOG_DEBUG，redis.LOG_VERBOSE，redis.LOG_NOTICE，以及redis.LOG_WARNING
用于计算SHA1校验和的redis.sha1hex函数
用于返回错误信息的redis.error_reply函数和redis.status_reply函数。

20.1.4 使用Redis自制的随机函数来替换Lua原有的随机函数

为了保证相同的脚本可以在不同的机器上产生相同的结果，Redis要求所有传入服务器的Lua脚本，以及Lua环境中的所有函数，都必须是无副作用（side effect）的纯函数（pure function）

Redis使用自制的函数替换了math库中原有的math.random函数和math.randomseed函数，替换之后的两个函数有以下特征：

对于相同的seed来说，math.random总产生相同的随机数序列，这个函数是一个纯函数
除非在脚本中使用math.randomseed显式地修改seed，否则每次运行脚本时，Lua环境都使用固定的math.randomseed（0）语句来初始化seed。

20.1.5 创建排序辅助函数

对于一个集合键来说，因为集合元素的排列是无序的，所以即使两个集合的元素完全相同，它们的输出结果也可能并不相同。

Redis将SMEMBERS这种在相同数据集上可能会产生不同输出的命令称为“带有不确定性的命令”，这些命令包括：

SINTER
SUNION
SDIFF
SMEMBERS
HKEYS
HVALS
KEYS

为了消除这些命令带来的不确定性，服务器会为Lua环境创建一个排序辅助函数__redis__compare_helper，当Lua脚本执行完一个带有不确定性的命令之后，程序会使用__redis__compare_helper作为对比函数，自动调用table.sort函数对命令的返回值做一次排序，以此来保证相同的数据集总是产生相同的输出。

20.1.6 创建redis.pcall函数的错误报告辅助函数

在这一步，服务器将为Lua环境创建一个名为__redis__err__handler的错误处理函数，当脚本调用redis.pcall函数执行Redis命令，并且被执行的命令出现错误时，__redis__err__handler就会打印出错代码的来源和发生错误的行数，为程序的调试提供方便

20.1.7 保护Lua的全局环境

在这一步，服务器将对Lua环境中的全局环境进行保护，确保传入服务器的脚本不会因为忘记使用local关键字而将额外的全局变量添加到Lua环境里面。

因为全局变量保护的原因，当一个脚本试图创建一个全局变量时，服务器将报告一个错误。

除此之外，试图获取一个不存在的全局变量也会引发一个错误

不过Redis并未禁止用户修改已存在的全局变量，所以在执行Lua脚本的时候，必须非常小心，以免错误地修改了已存在的全局变量

20.1.8 将Lua环境保存到服务器状态的lua属性里面

整个Redis服务器只需要创建一个Lua环境即可

20.2 Lua环境协作组件

Redis服务器还创建了两个用于与Lua环境进行协作的组件，它们分别是负责执行Lua脚本中的Redis命令的伪客户端，以及用于保存Lua脚本的lua_scripts字典

20.2.1 伪客户端

因为要执行redis命令，就必须有相应的客户端状态

20.2.2 lua_scripts 字典

键为lua脚本的sha1校验和，值为lua脚本

1
2
3


struct redisServer {
	dict *lua_script 
}

20.3 EVAL命令的实现

20.3.1 定义脚本函数

20.3.2 将脚本保存到lua_scripts字典中

20.3.3 执行脚本函数

整个准备和执行脚本的过程如下：

1）将EVAL命令中传入的键名（key name）参数和脚本参数分别保存到KEYS数组和ARGV数组，然后将这两个数组作为全局变量传入到Lua环境里面
2）为Lua环境装载超时处理钩子（hook），这个钩子可以在脚本出现超时运行情况时，让客户端通过SCRIPT KILL命令停止脚本，或者通过SHUTDOWN命令直接关闭服务器
3）执行脚本函数
4）移除之前装载的超时钩子
5）将执行脚本函数所得的结果保存到客户端状态的输出缓冲区里面，等待服务器将结果返回给客户端
6）对Lua环境执行垃圾回收操作

20.4 EVALSHA命令的实现

20.5 脚本管理命令的实现

20.5.1 SCRIPT FLUSH

20.5.2 SCRIPT EXISTS

20.5.3 SCRIPT LOAD

20.5.4 SCRIPT KILL

20.6 脚本复制

20.6.1 复制EVAL命令、SCRIPT FLUSH命令和SCRIPT LOAD命令

20.6.2 复制EVALSHA命令

较复杂，相同的EVALSHA命令在从服务执行时可能出现脚本未找到错误

redis要求在传播evalsha命令的时候，必须确保evalsha要执行的脚本已经被所有从服务器载入过。如果不能保证这一点，主服务器会把evalsha命令转换为一个等价的eval命令进行传播。

判断传播evalsha命令是否安全的方法
- 主服务器使用服务器状态的repl_scriptcache_dict字典记录自己已经将哪些脚本传递给了所有的服务器
- repl_scriptcache_dict字典的键是sha1校验和，值全部是NULL
- 当key出现时，则意味着这个脚本已经传播给了所有的从服务器
清空repl_scriptcache_dict字典
- 每当主服务器添加一个从服务器，主服务器都会清空自己的repl_scriptcache_dict字典
evalsha命令转换成eval命令的方法

第21章-排序

redis的sort命令可以对列表键、集合键、有序集合键的值进行排序

21.1 `SORT <key>` 命令的实现

21.2 `SORT <key> ALPHA`

21.3 asc选项和desc选项

21.4 `SORT <key> BY <pattern>`

21.5 带有ALPHA选项的BY选项的实现

21.6 `SORT <key> LIMIT <offset> <count>`

21.7 `SORT <key> GET <pattern>`

21.8 STORE选项的实现

21.9 顺序

21.9.1 选项的执行顺序

如果按照选项来划分的话，一个SORT命令的执行过程可以分为以下四步：

1）排序：在这一步，命令会使用ALPHA、ASC或DESC、BY这几个选项，对输入键进行排序，并得到一个排序结果集
2）限制排序结果集的长度：在这一步，命令会使用LIMIT选项，对排序结果集的长度进行限制，只有LIMIT选项指定的那部分元素会被保留在排序结果集中
3）获取外部键：在这一步，命令会使用GET选项，根据排序结果集中的元素，以及GET选项指定的模式，查找并获取指定键的值，并用这些值来作为新的排序结果集
4）保存排序结果集：在这一步，命令会使用STORE选项，将排序结果集保存到指定的键上面去
5）向客户端返回排序结果集：在最后这一步，命令遍历排序结果集，并依次向客户端返回排序结果集中的元素

21.9.2 选项的摆放顺序

调用SORT命令时，除了GET选项之外，改变选项的摆放顺序并不会影响SORT命令执行这些选项的顺序

在调整SORT命令各个选项的摆放顺序时，必须小心处理GET选项

第22章-二进制位数组

setbit
getbit
bitcount
bitop

22.1 位数组的表示

使用字符串来表示位数组

22.2 `getbit`命令的实现

GETBIT命令的执行过程如下：

1）计算byte=offset÷8」，byte值记录了offset偏移量指定的二进制位保存在位数组的哪个字节
2）计算bit=（offset mod 8）+1，bit值记录了offset偏移量指定的二进制位是byte字节的第几个二进制位
3）根据byte值和bit值，在位数组bitarray中定位offset偏移量指定的二进制位，并返回这个位的值

22.3 `setbit <key> <offset> <value>`

以下是SETBIT命令的执行过程：

1）计算len=offset÷8」+1，len值记录了保存offset偏移量指定的二进制位至少需要多少字节
2）检查bitarray键保存的位数组（也即是SDS）的长度是否小于len，如果是的话，将SDS的长度扩展为len字节，并将所有新扩展空间的二进制位的值设置为0
3）计算byte=offset÷8」，byte值记录了offset偏移量指定的二进制位保存在位数组的哪个字节
4）计算bit=（offset mod 8）+1，bit值记录了offset偏移量指定的二进制位是byte字节的第几个二进制位
5）根据byte值和bit值，在bitarray键保存的位数组中定位offset偏移量指定的二进制位，首先将指定二进制位现在值保存在oldvalue变量，然后将新值value设置为这个二进制位的值
6）向客户端返回oldvalue变量的值

因为SETBIT命令执行的所有操作都可以在常数时间内完成，所以该命令的时间复杂度为O（1）。

22.4 `bitcount`命令的实现

22.4.3 二进制位统计算法（3）：variable-precision SWAR算法

统计一个位数组中非0二进制位的数量，在数学上被称为“计算汉明重量（Hamming Weight）”

目前已知效率最好的通用算法为variable-precision SWAR算法，该算法通过一系列位移和位运算操作，可以在常数时间内计算多个字节的汉明重量，并且不需要使用任何额外的内存。

算法详细推导参考：variable-precision SWAR 算法详解 - 半叠道人的文章 - 知乎

BITCOUNT命令的实现用到了查表和variable-precisionSWAR两种算法：

查表算法使用键长为8位的表，表中记录了从0000 0000到1111 1111在内的所有二进制位的汉明重量
至于variable-precision SWAR算法方面，BITCOUNT命令在每次循环中载入128个二进制位，然后调用四次32位variable-precision SWAR算法来计算这128个二进制位的汉明重量

在执行BITCOUNT命令时，程序会根据未处理的二进制位的数量来决定使用那种算法：

如果未处理的二进制位的数量大于等于128位，那么程序使用variable-precision SWAR算法来计算二进制位的汉明重量。
如果未处理的二进制位的数量小于128位，那么程序使用查表算法来计算二进制位的汉明重量。

以100MB=800000000bit来计算，BITCOUNT命令处理一个100MB长的位数组共需要执行第一个循环六百二十五万次，第二个循环零次。以500MB=4000000000bit来计算，BITCOUNT命令处理一个500MB长的位数组共需要执行第一个循环三千一百二十五万次，第二个循环零次。通过使用更好的算法，我们将计算100MB和500MB长的二进制位所需的循环次数从最开始使用遍历算法时的数亿甚至数十亿次减少到了数百万次和数千万次。

22.5 BITOP命令的实现

第23章-慢查询日志

Redis的慢查询日志功能用于记录执行时间超过给定时长的命令请求，用户可以通过这个功能产生的日志来监视和优化查询速度。

服务器配置有两个和慢查询日志相关的选项：

slowlog-log-slower-than选项指定执行时间超过多少微秒（1秒等于1000 000微秒）的命令请求会被记录到日志上
slowlog-max-len选项指定服务器最多保存多少条慢查询日志。

23.1 慢查询记录的保存

23.2 慢查询日志的阅览和删除

23.3 添加新日志

第24章-监视器

通过执行MONITOR命令，客户端可以将自己变为一个监视器，实时地接收并打印出服务器当前处理的命令请求的相关信息

每当一个客户端向服务器发送一条命令请求时，服务器除了会处理这条命令请求之外，还会将关于这条命令请求的信息发送给所有监视器

24.1 成为监视器

伪代码：

1
2
3
4
5
6
7


def MONITOR():
    #打开客户端的监视器标志
    client.flags |= REDIS_MONITOR
    #将客户端添加到服务器状态的monitors链表的末尾
    server.monitors.append(client)
    #向客户端返回OK
    send_reply("OK")

24.2 向监视器发送命令信息

服务器在每次处理命令请求之前，都会调用replicationFeedMonitors函数，由这个函数将被处理的命令请求的相关信息发送给各个监视器

第18章-发布与订阅#

18.1 频道的订阅与退订#

18.1.1 频道的订阅#

18.1.2 频道的退订#

18.2 pattern的订阅与退订#

18.2.1 订阅pattern#

18.2.2 退订pattern#

18.3 发送消息#

18.3.1 将消息发送给频道订阅者#

18.3.2 将消息发送给模式订阅者#

18.4 查看订阅信息#

18.4.1 PUBSUB CHANNELS#

18.4.2 PUBSUB NUMSUB#

18.4.3 PUBSUB NUMPAT#

第19章-事务#

19.1 事务的实现#

19.1.1 事务开始#

19.1.2 命令入队#

19.1.3 事务执行#

19.2 WATCH命令的实现#

19.2.1 使用watch命令监视数据库键#

19.2.2 监视机制的触发#

19.2.3 判断事务是否安全#

19.2.4 一个完整的WATCH事务执行过程#

19.3 事务的ACID性质#

#

第20章-Lua脚本#

20.1 创建并修改lua环境#

20.1.1 创建Lua环境#

20.1.2 载入函数库#

20.1.3 创建redis全局表格#

20.1.4 使用Redis自制的随机函数来替换Lua原有的随机函数#

20.1.5 创建排序辅助函数#

20.1.6 创建redis.pcall函数的错误报告辅助函数#

20.1.7 保护Lua的全局环境#

20.1.8 将Lua环境保存到服务器状态的lua属性里面#

20.2 Lua环境协作组件#

20.2.1 伪客户端#

20.2.2 lua_scripts 字典#

20.3 EVAL命令的实现#

20.3.1 定义脚本函数#

20.3.2 将脚本保存到lua_scripts字典中#

20.3.3 执行脚本函数#

20.4 EVALSHA命令的实现#

20.5 脚本管理命令的实现#

20.5.1 SCRIPT FLUSH#

20.5.2 SCRIPT EXISTS#

20.5.3 SCRIPT LOAD#

20.5.4 SCRIPT KILL#

20.6 脚本复制#

20.6.1 复制EVAL命令、SCRIPT FLUSH命令和SCRIPT LOAD命令#

20.6.2 复制EVALSHA命令#

第21章-排序#

21.1 SORT <key> 命令的实现#

21.2 SORT <key> ALPHA#

21.3 asc选项和desc选项#

21.4 SORT <key> BY <pattern>#

21.5 带有ALPHA选项的BY选项的实现#

21.6 SORT <key> LIMIT <offset> <count>#

21.7 SORT <key> GET <pattern>#

21.8 STORE选项的实现#

21.9 顺序#

21.9.1 选项的执行顺序#

21.9.2 选项的摆放顺序#

第22章-二进制位数组#

22.1 位数组的表示#

22.2 getbit命令的实现#

22.3 setbit <key> <offset> <value>#

22.4 bitcount命令的实现#

22.5 BITOP命令的实现#

第23章-慢查询日志#

23.1 慢查询记录的保存#

23.2 慢查询日志的阅览和删除#

23.3 添加新日志#

第24章-监视器#

24.1 成为监视器#

24.2 向监视器发送命令信息#

#