本项目完整地址 simple-redis

Redis 不支持原子事务，在 multi 排队执行时，如果在入队时发生错误则放弃执行，如果在 exec 执行时错误则跳过这条命令。

Simple-Redis 支持原子事务，在 multi 排队执行时，如果在入队时发生错误则放弃执行，在 exec 执行时错误则整条命令回滚。

原子事务

watch

在数据库存储引擎层，使用了并发的 dict 记录 key 和版本号的映射关系，当写命令执行成功时版本号加一。

在 Redis 中 watch 命令用于记录一个 key 当前的版本号，将版本号记录在客户端连接的上下文中。

事务

原子事务的实现是在数据库引擎层实现的，在 multi 后客户端发出的每一条命令，数据库只会检查语法错误并将命令记录在客户端连接的上下文中。

在 exec 时，才会从客户端连接的上下文中读取所有需要执行的命令队列。exec 命令的实现方式如下：

• 首先加写锁、加读锁（watch 的 key 也会加上读锁）。
• 检查 watch 的 key 版本是否变化，如果变化则直接返回，什么都不做。
• 依次执行每一条命令，如果开启了原子事务，则会记录 undo log。
• 如果执行成功，对相应的 key 增加版本号；如果执行失败，则根据 undo log 进行回滚。

本项目完整地址 simple-redis

集群

Simple-Redis 的集群本质上就是一个分片集群，使用一致性哈希环实现。

结构体

Cluster 结构体如下，其中：

• peers 为一致性哈希，用于根据 key 选择节点。
• getters 用于和远程节点通信。

以下三个属性与分布式事务相关：

• idGenerator：雪花 ID（分布式 ID）生成器，用于生成分布式事务 ID。
• transactionMap：记录所有的分布式事务。
• coordinatorMap：记录所有的事物协调者。

1
2
3
4
5
6
7
8
9
10

// Cluster 用于和集群中的主机进行交互
type Cluster struct {
    self    string                        // 本机地址，如 127.0.0.1:6107
    peers   cluster.PeerPicker            // 一致性哈希，用于选择节点
    getters map[string]cluster.PeerGetter // 用于和远程节点通信

    idGenerator    *snowflake.Node  // snowflake id生成器，用于生成分布式事务的id
    transactionMap *dict.SimpleDict // 记录所有的分布式事务（本地）
    coordinatorMap *dict.SimpleDict // 记录事务协调者
}

getter

在和远程节点通信时，本节点就作为一个 Client。而一个 getter 维护一个远程节点的连接池（实际上一个 getter 维护多个连接池，一个数据库对应一个连接池。

集群中节点之间的通信采用连接池，是为了：

• 复用连接（复用空闲连接）。
• 增加并发性能（节点之间有多个连接）。
• 控制节点之间的连接数，不会因为节点之间的通信而影响客户端与节点之间的通信（有最大空闲连接数和最大活跃连接数的限制）。

本项目完整地址 simple-redis

性能测试

测试环境

使用的机器为 MacBook Pro 13，处理器 Intel i5 四核，内存 8GB。

测试结果

在同样的测试环境上，使用 redis-benchmark分别对 Redis 和 Simple-Redis 进行性能测试。

发送一万条请求，对 set,get,incr,lpush,rpush,lpop,rpop,sadd,hset,spop,zadd,lrange 命令进行测试。

Redis

Redis 测试结果如下：

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

zhaohan08@MacBook-Pro redis % redis-benchmark -t set,get,incr,lpush,rpush,lpop,rpop,sadd,hset,spop,zadd,lrange -n 10000 -q
SET: 93457.95 requests per second, p50=0.263 msec
GET: 96153.84 requests per second, p50=0.263 msec
INCR: 96153.84 requests per second, p50=0.263 msec
LPUSH: 100000.00 requests per second, p50=0.263 msec
RPUSH: 97087.38 requests per second, p50=0.263 msec
LPOP: 98039.22 requests per second, p50=0.263 msec
RPOP: 93457.95 requests per second, p50=0.263 msec
SADD: 93457.95 requests per second, p50=0.263 msec
HSET: 87719.30 requests per second, p50=0.271 msec
SPOP: 95238.10 requests per second, p50=0.263 msec
ZADD: 100000.00 requests per second, p50=0.263 msec
LPUSH (needed to benchmark LRANGE): 99009.90 requests per second, p50=0.263 msec
LRANGE_100 (first 100 elements): 38167.94 requests per second, p50=0.647 msec
LRANGE_300 (first 300 elements): 16366.61 requests per second, p50=1.503 msec
LRANGE_500 (first 500 elements): 10989.01 requests per second, p50=2.223 msec
LRANGE_600 (first 600 elements): 9363.30 requests per second, p50=2.639 msec

Simple-Redis

Simple-Redis 测试结果如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

zhaohan08@MacBook-Pro redis % redis-benchmark -t set,get,incr,lpush,rpush,lpop,rpop,sadd,hset,spop,zadd,lrange -n 10000 -q
WARNING: Could not fetch server CONFIG
SET: 68965.52 requests per second, p50=0.367 msec
GET: 62111.80 requests per second, p50=0.399 msec
INCR: 49751.24 requests per second, p50=0.487 msec
LPUSH: 56497.18 requests per second, p50=0.447 msec
RPUSH: 49504.95 requests per second, p50=0.503 msec
LPOP: 68965.52 requests per second, p50=0.375 msec
RPOP: 68493.15 requests per second, p50=0.375 msec
SADD: 52631.58 requests per second, p50=0.495 msec
HSET: 68027.21 requests per second, p50=0.375 msec
SPOP: 68027.21 requests per second, p50=0.383 msec
ZADD: 49751.24 requests per second, p50=0.503 msec
LPUSH (needed to benchmark LRANGE): 56818.18 requests per second, p50=0.463 msec
LRANGE_100 (first 100 elements): 25773.20 requests per second, p50=0.895 msec
LRANGE_300 (first 300 elements): 13586.96 requests per second, p50=1.775 msec
LRANGE_500 (first 500 elements): 9041.59 requests per second, p50=2.607 msec
LRANGE_600 (first 600 elements): 7704.16 requests per second, p50=3.015 msec

结论

在单机时，可以得出结论，Simple-Redis 和 Redis 是有性能差距的，具体数据如下：

• string 类型：Simple-Redis 的性能大约是 Redis 的 70%。
• list 类型：Simple-Redis 的性能大约是 Redis 的 50%。
• hash 类型：Simple-Redis 大约是 Redis 的 75%。
• set 类型：Simple-Redis 的性能大约是 Redis 的 55%。
• zset 类型：Simple-Redis 的性能大约是 Redis 的 50%。

本项目完整地址 simple-redis

本节说明 simple-redis 中的 AOF 持久化功能。AOF（append only file）是一种 Redis 持久化方式。，其优缺点总结如下：

• 优势：
  • 持久化文件是用户可以理解的。
  • 备份机制更稳健，丢失数据概率更低。
  • AOF日志文件的命令通过可读的方式进行记录，这个特性非常适合做灾难性的误删除的紧急恢复。比如某人不小心使用了flushall清空了所有数据库，只有重写操作还没有发生，那么就可以立即拷贝AOF文件，将最后一条flushall命令给删了，然后再将该AOF文件放回去，就可以通过恢复机制，自动恢复所有数据。
• 劣势：
  • 比起RDB占用更多的磁盘空间。
  • 恢复备份速度慢。
  • 每次读写都同步的话，有一定的性能压力。

AOF 持久化

数据结构

Persister 是 AOF 持久化中的核心数据结构，它从 channel 中接收消息并且将消息写入到 AOF 文件中。其中重要的字段如下：

• db：指向 simple-redis 服务器。
• tmpDBMaker：临时数据库创建函数，在进行 AOF 重写时，需要建立一个临时数据库加载 AOF 持久化文件，通过遍历临时数据库中的 key 实现 AOF 持久化文件的重写压缩。
• aofChan：需要持久化的命令（payload 包含命令、数据库编号两个字段）发送到这个管道上进行持久化。
• aofFilename：AOF 持久化文件名。
• aofFsync：AOF 刷盘策略，共有三种策略分别是FsyncAlways、FsyncEverySec、FsyncNo。
• currentDB：当前数据库编号。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

const (
   FsyncAlways   = iota // 每一个命令都会进行刷盘操作
   FsyncEverySec        // 每秒进行一次刷盘操作
   FsyncNo              // 不主动进行刷盘操作，交给操作系统去决定
)

type CmdLine [][]byte

const (
   aofQueueSize = 1 << 16
)

type Persister struct {
   ctx         context.Context
   cancel      context.CancelFunc
   db          database.DBEngine
   tmpDBMaker  func() database.DBEngine
   aofChan     chan *payload
   aofFile     *os.File
   aofFilename string
   aofFsync    int // AOF 刷盘策略
   // aof goroutine will send msg to main goroutine through this channel when aof tasks finished and ready to shut down
   aofFinished chan struct{}
   // pause aof for start/finish aof rewrite progress
   pausingAof sync.Mutex
   // 表示正在aof重写，同时只有一个aof重写
   aofRewriting sync.WaitGroup
   currentDB    int
}

payload 包含命令、数据库编号两个字段，它表示发送给 aofChan 的数据。

1
2
3
4

type payload struct {
	cmdLine CmdLine
	dbIndex int
}

本项目完整地址 simple-redis

底层数据库

在上一节中，我们简述了 simple-redis 的工作方式，需要注意的是如 GET、SET 这样需要在某个具体的数据库中执行的命令，单机模式下 Server 会调用 Server.db.Exec 去执行这类命令。

本节我们就聊一聊 simple-redis 的底层数据库，simple-redis 的底层数据库定义在 database/engine 文件夹中。

本项目完整地址 simple-redis

Simple-Redis 服务器

在之前已经介绍了 TCP 服务器，本节介绍 Simple-Redis 服务器，这是一个应用层服务器。在 Handler 的 Handle 方法中，有这样一条命令 result := h.db.Exec(client, r.Args)，它将收到的命令交给 simple-redis 服务器去执行。

数据结构

simple-redis 服务器的被定义在 database/server.go 文件中，simple-redis 服务器的相关代码在 database 文件夹下。

simple-redis 服务器的数据结构如下，需要说明的是：

• dbSet：代表底层的数据库。
• AofPersister：AOF 持久化。
• AofFileSize：用于记录上一次 AOF 重写后的文件大小。
• rewriteWait、rewriting：用于同步 AOF 重写过程。
• closed：接收关闭信号，用于优雅的关闭（用于关闭自动 AOF 重写协程）。
• cluster：集群相关。
• publish：订阅发布相关操作。

1
2
3
4
5
6
7
8
9
10

type Server struct {
   dbSet        []*atomic.Value // *DB
   AofPersister *aof.Persister  // AOF 持久化
   AofFileSize  int64
   rewriteWait  sync.WaitGroup
   rewriting    atomic.Bool
   closed       chan struct{}
   cluster      *cluster.Cluster
   publish      publish.Publish
}

AOF 持久化、集群、发布订阅会在后面的章节中说明。

本项目完整地址 simple-redis

List

Godis 中定义了 List 接口，以定义 List 的各种操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

// Expected check whether given item is equals to expected value
type Expected func(a interface{}) bool

// Consumer traverses list.
// It receives index and value as params, returns true to continue traversal, while returns false to break
type Consumer func(i int, v interface{}) bool

type List interface {
   Add(val interface{})
   Get(index int) (val interface{})
   Set(index int, val interface{})
   Insert(index int, val interface{})
   Remove(index int) (val interface{})
   RemoveLast() (val interface{})
   RemoveAllByVal(expected Expected) int
   RemoveByVal(expected Expected, count int) int
   ReverseRemoveByVal(expected Expected, count int) int
   Len() int
   ForEach(consumer Consumer)
   Contains(expected Expected) bool
   Range(start int, stop int) []interface{}
}

数据结构

快速链表

在 godis 中，采用快速链表作为 List 的数据结构。

快速链表实际上就是一个双向链表，但是双向链表中的每一个节点不是存储一个数据，而是将数据连续存放形成一段连续的存储空间作为链表的节点。

这一段连续的存储空间在 godis 中被称为 page（每一个 page 的大小为 1024），page 的类型为空接口切片。

1
2
3
4
5
6
7
8
9

// pageSize must be even
const pageSize = 1024

// QuickList is a linked list of page (which type is []interface{})
// QuickList has better performance than LinkedList of Add, Range and memory usage
type QuickList struct {
   data *list.List // list of []interface{}
   size int
}

本项目完整地址 simple-redis

Hash 表

KV 内存数据库的核心是并发安全的哈希表，simple-redis 采用分段锁策略。将 key 分散到固定数量的 shard 中，在一个 shard 内的读写操作不会阻塞其他 shard 内的操作。

数据结构

定义 Dict 接口，该接口表示一个哈希表的操作：

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

// Consumer is used to traversal dict, if it returns false the traversal will be break
type Consumer func(key string, val interface{}) bool

// Dict is interface of a key-value data structure
type Dict interface {
	Get(key string) (val interface{}, exists bool)
	Len() int
	Put(key string, val interface{}) (result int)
	PutIfAbsent(key string, val interface{}) (result int)
	PutIfExists(key string, val interface{}) (result int)
	Remove(key string) (result int)
	ForEach(consumer Consumer)
	Keys() []string
	RandomKeys(limit int) []string
	RandomDistinctKeys(limit int) []string
	Clear()
}

定义 ConcurrentDict 实现了 Dict 接口，ConcurrentDict 为并发安全的哈希表。将 key 映射到不同的 shard 中，不同 shard 上的操作是不会相互影响的，提高了并发性。

注意，这里 shard 的数量恒为 2 的整数幂。

1
2
3
4
5
6
7
8
9
10

type ConcurrentDict struct {
	table      []*shard
	count      int64
	shardCount int
}

type shard struct {
	m     map[string]interface{}
	mutex sync.RWMutex
}

本项目完整地址 simple-redis

RESP 协议

simple-redis 的通信使用 RESP 协议，Redis 自 2.0 版本起使用了统一的协议 RESP（REdis Serialization Protocol，Redis 序列化协议），该协议易于实现，计算机可以高效的进行解析且易于被人类读懂。

RESP 是一个二进制安全的文本协议，工作于 TCP 协议上。RESP 以行作为单位，客户端和服务器发送的命令或数据一律以 \r\n （CRLF）作为换行符。

RESP 的五种格式

RESP 定义了 5 种格式：

• 简单字符串（Simple String）：服务器用来返回简单的结果，比如 OK。非二进制安全，不允许换行。
• 错误信息（Error）：服务器用来返回简单的错误信息，比如 ERR Invalid Synatx。非二进制安全，且不允许换行。
• 整数（Integer）：llen、scard 等命令的返回值，64位有符号整数。
• 字符串（Bulk String）：二进制安全字符串。
• 数组（Array，又称 Multi Bulk Strings）：Bulk String 数组，客户端发送指令以及 lrange 等命令响应的格式。

RESP 通过第一个字符表示格式：

• 简单字符串：以 + 开始，如 +OK\r\n。
• 错误：以 - 开始，如 -ERR Invalid Syntax\r\n。
• 整数：以 : 开始，如 :1\r\n。
• 字符串：以 $ 开始。Bulk String 有两行，第一行为 $+正文长度，第二行为实际内容。$-1 表示 nil，当使用 get 查询一个不存在的 key 时，响应为 nil。
• 数组：以 * 开始。第一行为 *+数组长度，其后是相应数量的 Bulk String。

本项目完整地址 simple-redis

客户端连接

在上一篇文章中，Handler 在 Handle 方法中，对于一个新的连接 conn 要初始化一个客户端与服务器连接的抽象 connect.Connection。这个结构体定义在 redis/connection/conn.go 中。

Connection 结构体

Connection 的结构体定义如下，有一些字段需要说明：

• sendingData：用于优雅的结束连接。当结束连接时会等待，直到数据发送完成或者超时。
• password：当配置了 password 后，当发送 auth 命令时就会修改这个字段，数据库服务器就会检查这个字段是否是正确的。
• selectedDB：当客户端发送 select 命令时，就会修改此字段的值，用于控制当前客户端处于哪个数据库中。
• isMulti，queue，syntaxErrQueue，watching，TxID：与事务相关的字段。
• subscribeChannels：记录客户端订阅的频道。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

// Connection represents a connection with a client
type Connection struct {
   conn net.Conn

   // wait until finish sending data, used for graceful shutdown
   sendingData wait.Wait

   // lock while server sending response
   mu sync.Mutex

   // password may be changed by CONFIG command during runtime, so store the password
   password string

   // selected db
   selectedDB int

   isMulti        bool              // 表明是否在 multi 开启事务中
   queue          [][][]byte        // 事务中排队的命令
   syntaxErrQueue []redis.Reply     // 事务中的语法错误
   watching       map[string]uint32 // 正在WATCH的key值
   TxID           string            // 事务ID，在分布式事务中用到

   subscribeChannels map[string]struct{} // 订阅的频道
}