SDB ：纯 golang 开发、数据结构丰富、持久化的 NoSQL 数据库
试想以下业务场景：
- 计数服务：对内容的点赞、播放等数据进行统计
- 评论服务：发布评论后，查看某个内容的评论列表
- 推荐服务：每个用户有一个包含内容和权重推荐列表
以上几个业务场景，都可以通过 MySQL + Redis 的方式实现。 这里的问题是：MySQL 更多的是充当持久化的能力，Redis 充当的是在线服务的读写能力。
那么只使用 Redis 行不行？ 答案是否定的，因为 Redis 无法保证数据不丢失。
那有没有一种存储能够支持高级的数据结构，并能够将数据进行持久化的呢？
答案是：非常少的。有些数据库要么是支持的数据结构不够丰富，要么是接入成本太高，要么是不可控。
为了解决上述问题，SDB 产生了。
- 纯 golang 开发，核心代码不超过 1k，代码易读
- 数据结构丰富
- 持久化
- 监控
- 支持 prometheus + grafana 监控方案
- 限流
- 支持每秒 qps 的限流策略
- 慢查询查看
- 可查看慢查询的请求，进行分析
- 编写接口文档
- 实现更多的 api (2021.12.30)
- String
- SetNX
- GetSet
- MGet
- MSet
- List
- LMembers
- Set
- SMembers
- Sorted Set
- ZMembers
- String
- 支持更丰富的数据结构 (2021.01.20)
- Bitmap
- Hash
- geo hash
- reverted index
- vector search
- 集群方案设计 (2021.01.30)
- 搭建 admin web ui
sh ./scripts/quick_start.sh默认使用 pebble 存储引擎。启动后，端口会监听 9000 端口
package main
import (
"github.com/yemingfeng/sdb/pkg/pb"
"golang.org/x/net/context"
"google.golang.org/grpc"
"log"
)
func main() {
conn, err := grpc.Dial(":9000", grpc.WithInsecure())
if err != nil {
log.Printf("faild to connect: %+v", err)
}
defer conn.Close()
// 连接服务器
c := pb.NewSDBClient(conn)
setResponse, err := c.Set(context.Background(),
&pb.SetRequest{Key: []byte("hello"), Value: []byte("world")})
log.Printf("setResponse: %+v, err: %+v", setResponse, err)
getResponse, err := c.Get(context.Background(),
&pb.GetRequest{Key: []byte("hello")})
log.Printf("getResponse: %+v, err: %+v", getResponse, err)
}| 参数名 | 含义 | 默认值 |
|---|---|---|
| store.engine | 存储引擎，可选 pebble、level、badger | pebble |
| store.path | 存储目录 | ./db |
| server.grpc_port | grpc 监听的端口 | 9000 |
| server.http_port | http 监控的端口，供 prometheus 使用 | 8081 |
| server.rate | 每秒 qps 的限制 | 30000 |
| server.slow_query_threshold | 慢查询记录的阈值，单位为 ms | 100 |
| 接口 | 参数 | 描述 |
|---|---|---|
| Set | key, value | 设置 kv |
| MSet | keys, values | 设置一组 kv |
| SetNX | key, value | 当 key 不存在时，设置 value |
| SetGet | key, value | 设置 kv，并返回原始值，当原始值不存在时，返回 nil |
| Get | key | 获取 key 对应的 value |
| MGet | keys | 获取一组 key 对应的 value |
| Del | key | 删除一个 key |
| Incr | key, delta | 对 key 进行加 delta 操作，如果 value 不为数字，则抛出异常。如果 value 不存在，则 value = delta |
| 接口 | 参数 | 描述 |
|---|---|---|
| LPush | key, values | 把 values 追加到 key 数组后面 |
| LPop | keys, values | 删除 key 数组中的所有的 values 元素 |
| LRange | key, offset, limit | 按数组顺序遍历 key，从 0 开始。如果 offset = -1，则从后向前遍历 |
| LExist | key, values | 判断 values 是否存在 key 数组中 |
| LDel | key | 删除某个 key 数组 |
| LCount | key | 返回 key 数组中的元素个数，时间复杂度较高，不推荐使用 |
| LMembers | key | 按数组顺利遍历 key。时间复杂度较高，不推荐使用 |
| 接口 | 参数 | 描述 |
|---|---|---|
| SPush | key, values | 把 values 加到 key 集合中 |
| SPop | keys, values | 删除 key 集合中的所有的 values 元素 |
| SExist | key, values | 判断 values 是否存在 key 集合中 |
| SDel | key | 删除某个 key 集合 |
| SCount | key | 返回 key 集合中的元素个数，时间复杂度较高，不推荐使用 |
| SMembers | key | 按 value 大小遍历 key。时间复杂度较高，不推荐使用 |
| 接口 | 参数 | 描述 |
|---|---|---|
| ZPush | key, tuples | 把 values 加到 key 有序集合中，按 tuple.score 从小到大排序 |
| ZPop | keys, values | 删除 key 有序集合中的所有的 values 元素 |
| ZRange | key, offset, limit | 按 score 大小，从小到大遍历 key。如果 offset = -1，则按 score 从大到小开始遍历 |
| ZExist | key, values | 判断 values 是否存在 key 有序集合中 |
| ZDel | key | 删除某个 key 有序集合 |
| ZCount | key | 返回 key 有序集合中的元素个数，时间复杂度较高，不推荐使用 |
| ZMembers | key | 按 score 大小，从小到大遍历 key。时间复杂度较高，不推荐使用 |
| 接口 | 参数 | 描述 |
|---|---|---|
| BFCreate | key, n, p | 创建 bloom filter，n 是元素个数，p 是误判率 |
| BFDel | key | 删除某个 key bloom filter |
| BFAdd | key, values | 把 values 加入到 bloom filter 中。当 bloom filter 未创建时，将抛出异常 |
| BFExist | key, values | 判断 values 是否存在 key bloom filter 中 |
| 接口 | 参数 | 描述 |
|---|---|---|
| HLLCreate | key | 创建 hyper log log |
| HLLDel | key | 删除某个 key hyper log log |
| HLLAdd | key, values | 把 values 加入到 hyper log log 中。当 hyper log log 未创建时，将抛出异常 |
| HLLCount | key | 获取某个 hyper log log 的去重元素个数 |
| 接口 | 参数 | 描述 |
|---|---|---|
| Subscribe | topic | 订阅某个 topic |
| Publish | topic, payload | 向某个 topic 发布 payload |
测试脚本：benchmark
测试机器：MacBook Pro (13-inch, 2016, Four Thunderbolt 3 Ports)
处理器：2.9GHz 双核 Core i5
内存：8GB
测试结果： peek QPS > 12k，avg QPS > 7k，set avg time < 70ms，get avg time < 0.2ms
- 打开 grafana：http://localhost:3000 （注意替换 ip 地址）
- 新建 prometheus datasources：http://host.docker.internal:9090 （如果使用 docker 安装则为这个地址。如果 host.docker.internal 无法访问，就直接替换 prometheus.yml 文件的 host.docker.internal 为自己的 ip 地址就行）
- 将 scripts/dashboard.json 文件导入 grafana dashboard
最终效果可参考：性能测试的 grafana 图
SDB 项目最核心的问题是数据存储方案的问题。
首先，我们不可能手写一个存储引擎。这个工作量太大，而且不可靠。 我们得在开源项目中找到适合 SDB 定位的存储方案。
SDB 需要能够提供高性能读写能力的存储引擎。 单机存储引擎方案常用的有：B+ 树、LSM 树、B 树等。
还有一个前置背景，golang 在云原生的表现非常不错，而且性能堪比 C 语言，开发效率也高，所以 SDB 首选使用纯 golang 进行开发。
那么现在的问题变成了：找到一款纯 golang 版本开发的存储引擎，这是比较有难度的。收集了一系列资料后，找到了以下开源方案：
- LSM 树
- go-leveldb ：是一个 unstable 的项目，无法使用
- syndtr-goleveldb
- badger
- pebble
- B+ 树
- boltdb-bolt ：是废弃的项目，无法使用
- etcd-bolt ：主要是用于分布式环境下的数据同步，无法应对高并发的数据读写
综合来看，golangdb、badger、pebble 这三款存储引擎都是很不错的。
为了兼容这三款存储引擎，SDB 提供了抽象的接口 ，进而适配这三个存储引擎。
SDB 已经通过上面三款存储引擎解决了数据存储的问题了。 但如何在 KV 的存储引擎上支持丰富的数据结构呢？
以 pebble 为例子，首先 pebble 提供了以下的接口能力：
- set(k, v)
- get(k)
- del(k)
- batch
- iterator
接下来，我以支持 List 数据结构为例子，剖析下 SDB 是如何通过 pebble 存储引擎支持 List 的。
List 数据结构提供了以下接口：LPush、LPop、LExist、LRange、LCount。
如果一个 List 的 key 为：[hello]，该 List 的列表元素有：[aaa, ccc, bbb]，那么该 List 的每个元素在 pebble 的存储为：
| pebble key | pebble value |
|---|---|
| l/hello/{unique_ordering_key1} | aaa |
| l/hello/{unique_ordering_key2} | ccc |
| l/hello/{unique_ordering_key3} | bbb |
List 元素的 pebble key 生成策略：
- 数据结构前缀：List 都以 l 字符为前缀，Set 是以 s 为前缀...
- List key 部分：List 的 key 为 hello
- unique_ordering_key：生成方式是通过雪花算法实现的，雪花算法保证局部自增
- pebble value 部分：List 元素真正的内容，如 aaa、ccc、bbb
为什么这么就能保证 List 的插入顺序呢？
这是因为 pebble 是 LSM 的实现，内部使用 key 的字典序排序。为了保证插入顺序，SDB 在 pebble key 中增加了 unique_ordering_key 作为排序的依据，从而保证了插入顺序。
有了 pebble key 的生成策略，一切都变得简单起来了。我们看看 LPush、LPop、LRange 的核心逻辑：
func LPush(key []byte, values [][]byte) (bool, error) {
batchAction := store.NewBatchAction()
defer batchAction.Close()
for _, value := range values {
batchAction.Set(generateListKey(key, util.GetOrderingKey()), value)
}
return batchAction.Commit()
}在写入到 pebble 的时候，key 的生成是通过 unique_ordering_key 的方案。 无法直接在 pebble 中找到 List 的元素在 pebble key。在删除一个元素的时候，需要遍历 List 的所有元素，找到 value = 待删除的元素，然后进行删除。核心逻辑如下：
func LPop(key []byte, values [][]byte) (bool, error) {
batchAction := store.NewBatchAction()
defer batchAction.Close()
store.Iterate(&store.IteratorOption{Prefix: generateListPrefixKey(key)},
func(key []byte, value []byte) {
for i := range values {
if bytes.Equal(values[i], value) {
batchAction.Del(key)
}
}
})
return batchAction.Commit()
}和删除逻辑类似，通过 iterator 接口进行遍历。 这里对反向迭代做了额外的支持 允许 Offset 传入 -1，代表从后进行迭代。
func LRange(key []byte, offset int32, limit int32) ([][]byte, error) {
index := int32(0)
res := make([][]byte, limit)
store.Iterate(&store.IteratorOption{
Prefix: generateListPrefixKey(key), Offset: int(offset), Limit: int(limit)},
func(key []byte, value []byte) {
res[index] = value
index++
})
return res[0:index], nil
}以上就实现了对 List 的数据结构的支持。
其他的数据结构大体逻辑类似，其中 sorted_set 更加复杂些。可以自行查看。
聪明的大家可以看出，LPop 的逻辑在数据量很大的情况下，非常耗性能。是因为我们在存储引擎中是无法知道 value 对应的 key 的，需要需要将 List 中的元素全部 load 出来后，挨个判断，才能进行删除。
为了降低时间复杂度，提高性能。 还是以 List: [hello] -> [aaa, ccc, bbb] 为例子。存储模型将改成如下：
正排索引结构【不变】：
| pebble key | pebble value |
|---|---|
| l/hello/{unique_ordering_key1} | aaa |
| l/hello/{unique_ordering_key2} | ccc |
| l/hello/{unique_ordering_key3} | bbb |
辅助索引结构
| pebble key | pebble value |
|---|---|
| l/hello/aaa/{unique_ordering_key1} | aaa |
| l/hello/ccc/{unique_ordering_key2} | ccc |
| l/hello/bbb/{unique_ordering_key3} | bbb |
有了这个辅助索引后，我们可以通过前缀检索的方式，判断 List 是否存在某个 value 的元素。从而降低时间复杂度，提高性能。 这里面还需要在写入元素时，将辅助索引写入，所以核心逻辑将改成：
func LPush(key []byte, values [][]byte) (bool, error) {
batch := store.NewBatch()
defer batch.Close()
for _, value := range values {
id := util.GetOrderingKey()
batch.Set(generateListKey(key, id), value)
batch.Set(generateListIdKey(key, value, id), value)
}
return batch.Commit()
}
func LPop(key []byte, values [][]byte) (bool, error) {
batch := store.NewBatch()
defer batch.Close()
for i := range values {
store.Iterate(&engine.PrefixIteratorOption{Prefix: generateListIdPrefixKey(key, values[i])},
func(storeKey []byte, storeValue []byte) {
if bytes.Equal(storeValue, values[i]) {
batch.Del(storeKey)
infos := strings.Split(string(storeKey), "/")
id, _ := strconv.ParseInt(infos[len(infos)-1], 10, 64)
batch.Del(generateListKey(key, id))
}
})
}
return batch.Commit()
}解决完了存储和数据结构的问题后，SDB 面临了【最后一公里】的问题是通讯协议的选择。
SDB 的定位是支持多语言的，所以需要选择支持多语言的通讯框架。
grpc 是一个非常不错的选择，只需要使用 SDB proto 文件，就能通过 protoc 命令行工具自动生成各种语言的客户端，解决了需要开发不同客户端的问题。
SDB 的集群方案其实是在规划中的，之前也考虑了 TiKV 集群方案和 Redis 集群方案。
但目前 SDB 把注意力放在持久化、数据结构上。增加更多的数据结构，并将易用性做到极致。之后再实现集群方案。
感谢开源的力量，这里就不一一列举了，请大家移步 go.mod