sdb

README

SDB ：纯 golang 开发、数据结构丰富、持久化、简单易用的 NoSQL 数据库

---

为什么需要 SDB？

试想以下业务场景：

• 计数服务：对内容的点赞、播放等数据进行统计
• 评论服务：发布评论后，查看某个内容的评论列表
• 推荐服务：每个用户有一个包含内容和权重推荐列表

以上几个业务场景，都可以通过 MySQL + Redis 的方式实现。

MySQL 在这个场景中充当了持久化的能力，Redis 提供了在线服务的读写能力。

上面的存储要求是：持久化 + 高性能 + 数据结构丰富。能不能只使用一个存储就满足上面的场景呢？

答案是：非常少的。有些数据库要么是支持的数据结构不够丰富，要么数据结构不够丰富，要么是接入成本太高。。。。。。

为了解决上述问题，SDB 产生了。

---

SDB 简单介绍

• 纯 golang 开发，核心代码不超过 1k，代码易读
• 数据结构丰富
  • string
  • list
  • set
  • sorted set
  • bloom filter
  • hyper log log
  • bitset
  • map
  • geo hash
  • pub sub
• 持久化
  • 兼容 pebble 、leveldb 、badger 存储引擎
• 监控
  • 支持 prometheus + grafana 监控方案
• cli
  • 简单易用的 cli
• 限流
  • 支持每秒 qps 的限流策略

---

架构

---

快速使用

直接使用编译好的二进制文件

可到 Release 页面下载对应的操作系统版本

压缩后有 sdb 和 cli 两个文件。直接运行即可。

shell 启动服务器

sh ./scripts/start_sdb.sh

默认使用 pebble 存储引擎。

shell 启动 cli

sh ./scripts/start_cli.sh

输入 help 可查看支持的所有操作

命令遵循接口文档，以 List 操作为例子：

客户端使用

package main

import (
	pb "github.com/yemingfeng/sdb/pkg/protobuf"
	"golang.org/x/net/context"
	"google.golang.org/grpc"
	"log"
)

func main() {
	conn, err := grpc.Dial(":10000", grpc.WithInsecure())
	if err != nil {
		log.Printf("faild to connect: %+v", err)
	}
	defer func() {
		_ = 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)
}

---

性能测试

测试脚本：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

---

规划

• 编写接口文档
• 实现更多的 api (2021.12.30)
  • String
    • SetNX
    • GetSet
    • MGet
    • MSet
  • List
    • LMembers
    • LLPush
  • Set
    • SMembers
  • Sorted Set
    • ZMembers
• 支持更丰富的数据结构 (2021.01.20)
  • bitset
  • map
  • geo hash
• sdb-cli (2021.03.10)
• 搭建 admin web ui

---

接口文档

string

接口	参数	描述
Set	key, value	设置 kv
MSet	keys, values	设置一组 kv
SetNX	key, value	当 key 不存在时，设置 value
Get	key	获取 key 对应的 value
MGet	keys	获取一组 key 对应的 value
Del	key	删除一个 key
Incr	key, delta	对 key 进行加 delta 操作，如果 value 不为数字，则抛出异常。如果 value 不存在，则 value = delta

list

接口	参数	描述
LRPush	key, values	从 key 数组后面追加 values
LLPush	key, values	从 key 数组前面追加 values
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。时间复杂度较高，不推荐使用

set

接口	参数	描述
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。时间复杂度较高，不推荐使用

sorted set

接口	参数	描述
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。时间复杂度较高，不推荐使用

bloom filter

接口	参数	描述
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 中

hyper log log

接口	参数	描述
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 的去重元素个数

bitset

接口	参数	描述
BSCreate	key, size	创建 bitset。size 会进行二次幂对齐
BSDel	key	删除某个 key bitset
BSSetRange	key, start, end, value	将 key [start, end) 范围的 bit 设置为 value
BSMSet	key, bits, value	将 key bits 设置为 value
BSGetRange	key, start, end	获取 key [start, end) 范围的 bit
BSMGet	key, bits	获取 key bits 的 bit
BSMCount	key	获取 key bit = 1 的个数
BSMCountRange	key, start, end	获取 key [start, end) bit = 1 的个数

map

接口	参数	描述
MPush	key, pairs	把 pairs KV 对加到 key map 中
MPop	key, keys	删除 key map 中所有的 keys 元素
MExist	key, keys	判断 keys 是否存在 key map 中
MDel	key	删除某个 key map
MCount	key	返回 key map 中的元素个数，时间复杂度较高，不推荐使用
MMembers	key	按 pair.key 大小遍历 pair。时间复杂度较高，不推荐使用

geo hash

接口	参数	描述
GHCreate	key, precision	创建 geo hash，precision 代表精度。
GHDel	key	删除某个 geo hash
GHAdd	key, points	将 points 加入到 geo hash 中，point 中的 id 作为唯一标识
GHPop	key, ids	删除某 points
GHGetBoxes	key, point	返回和某 point 在 key geo hash 相同 box 的 point 列表，会按照距离从小到大排序
GHGetNeighbors	key, point	返回在 key geo hash 中距离 point 最近的 point 列表，会按照距离从小到大排序
GHCount	key	返回 key geo hash 中的元素个数，时间复杂度较高，不推荐使用
GHMembers	key	返回 key geo hash 中所有的 point 列表。时间复杂度较高，不推荐使用

page

接口	参数	描述
PList	dataType, key, offset, limit	查询某个 dataType 下已有的元素。key 如果不为空，则获取该 dataType 下 key 的元素。

pub sub

接口	参数	描述
Subscribe	topic	订阅某个 topic
Publish	topic, payload	向某个 topic 发布 payload

---

监控

安装 docker 版本 grafana、prometheus（可跳过）

• 启动 scripts/run_monitor.sh

配置 grafana

• 打开 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 图

---

配置参数

参数名	含义	默认值
store.engine	存储引擎，可选 pebble、level、badger	pebble
store.path	存储目录	./db
server.grpc_port	grpc 监听的端口	10000
server.http_port	http 监控的端口，供 prometheus 和主从注册使用	11000
server.rate	每秒 qps 的限制	30000
server.slow_query_threshold	慢查询记录的阈值，单位为 ms	100

---

SDB 原理之——存储引擎选型

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 原理之——数据结构设计

SDB 已经通过之前的三款存储引擎解决了数据存储的问题了。 但如何在 KV 的存储引擎上支持丰富的数据结构呢？

以 pebble 为例子，首先 pebble 提供了以下的接口能力：

• set(k, v)
• get(k)
• del(k)
• batch
• iterator

接下来，我以支持 List 数据结构为例子，剖析下 SDB 是如何通过 pebble 存储引擎支持 List 的。

List 数据结构提供了以下接口：LRPush、LLPush、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 的生成策略，一切都变得简单起来了。我们看看 LRPush、LLPush、LPop、LRange 的核心逻辑：

LRPush

func LRPush(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()
}

LLPush

LLPush 的逻辑和 LRPush 的逻辑非常类似，不同的地方在于，只要将 {unique_ordering_key} 取负数，变成最小值就可以了。 为了保证 values 内部有序，所以还得 - index。 逻辑如下：

func LLPush(key []byte, values [][]byte) (bool, error) {
	batch := store.NewBatch()
	defer batch.Close()

	for i, value := range values {
		batch.Set(generateListKey(key, -(math.MaxInt64 - util.GetOrderingKey())), value)
	}

	return batch.Commit()
}

LPop

在写入到 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()
}

LRange

和删除逻辑类似，通过 iterator 接口进行遍历。 这里对反向迭代做了额外的支持 允许 offset 传入 -1，代表从后进行迭代。

func LRange(key []byte, offset int32, limit uint32) ([][]byte, error) {
	index := int32(0)
	res := make([][]byte, limit)
	store.Iterate(&engine.PrefixIteratorOption{
		Prefix: generateListPrefixKey(key), Offset: offset, Limit: limit},
		func(key []byte, value []byte) {
			res[index] = value
			index++
		})
	return res[0:index], nil
}

以上就实现了对 List 的数据结构的支持。

其他的数据结构大体逻辑类似，其中 sorted_set 更加复杂些。可以自行查看。

LPop 优化

聪明的大家可以看出，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 LRPush(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 LLPush(key []byte, values [][]byte) (bool, error) {
	batch := store.NewBatch()
	defer batch.Close()

	for i, value := range values {
		id := -(math.MaxInt64 - 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 原理之——关系模型到 KV 模型的映射

有了上面的方案，大概知道了 KV 型存储引擎如何支持数据结构。但这种方式很粗暴，无法通用化。

参考了 TiDB 的设计 ，SDB 做了一层关系模型到 KV 结构的设计。

在 SBD 中，数据由 Collection 和 Row 构造。 其中：

• Collection 类似数据库的一张表，是逻辑概念。每个 dataType(如 List) 对应一个 Collection。一个 Collection 包含多个 Row。
• 一个 Row 包含唯一键：key、id、value、indexes，是真正存储于 KV 存储的数据。每行 row 以 rowKey 作为唯一值，rowKey = {dataType} + {key} + {id}
• 每个 row 包含 N 个索引，每个索引以 indexKey 作为唯一值，indexKey = {dataType} + {key} + idx_{indexName} + {indexValue} + {id}

以 ListCollection 为例子，该 List 的 key 为 [l1]，假设该 Collection 有 4 行 Row，每行 Row 都有 value 和 score 的索引

那么每行 Row 结构如下：

 { {key: l1}, {id: 1.1}, {value: aaa}, {score: 1.1}, indexes: [ {name: "value", value: aaa}, {name: "score", value: 1.1} ] }
 { {key: l1}, {id: 2.2}, {value: bbb}, {score: 2.2}, indexes: [ {name: "value", value: bbb}, {name: "score", value: 2.2} ] }
 { {key: l1}, {id: 3.3}, {value: ccc}, {score: 3.3}, indexes: [ {name: "value", value: ccc}, {name: "score", value: 3.3} ] } 
 { {key: l1}, {id: 4.4}, {value: aaa}, {score: 4.4}, indexes: [ {name: "value", value: aaa}, {name: "score", value: 4.4} ] }

以 id = 1.1 的 Row 为例子，dataType = 1，rowKey = 1/l1/1.1，valueIndexKey = 1/l1/idx_value/aaa/1.1, scoreIndexKey = 1/l1/idx_score/1.1/1.1 写入的数据为：

    rowKey: 1/l1/1.1 -> { {key: l1}, {id: 1.1}, {value: aaa}, {score: 1.1}, indexes: [ {name: "value", value: aaa}, {name: "score", value: 1.1} ] }
    valueIndexKey: 1/l1/idx_value/aaa/1.1, -> 1/l1/1.1
    scoreIndexKey: 1/l1/idx_score/1.1/1.1 -> 1/l1/1.1

如此，便将数据结构、KV 存储、关系模型打通。

---

SDB 原理之——通讯协议方案

解决完了存储和数据结构的问题后，SDB 面临了【最后一公里】的问题是通讯协议的选择。

SDB 的定位是支持多语言的，所以需要选择支持多语言的通讯框架。

grpc 是一个非常不错的选择，只需要使用 SDB proto 文件，就能通过 protoc 命令行工具自动生成各种语言的客户端，解决了需要开发不同客户端的问题。

---

感谢开源的力量，这里就不一一列举了，请大家移步 go.mod