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

Go 开源项目
1

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

为什么需要 SDB？

试想以下业务场景：

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

以上几个业务场景，都可以通过 MySQL + Redis 的方式实现。 这里的问题是：MySQL 更多的是充当持久化的能力，Redis 充当的是在线服务的读写能力。

那么只使用 Redis 行不行？ 答案是否定的，因为 Redis 无法保证数据不丢失。

那有没有一种存储能够支持高级的数据结构，并能够将数据进行持久化的呢？

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

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

SDB 简单介绍

规划

  • [x] 编写接口文档
  • [x] 实现更多的 api (2021.12.30)
    • [x] String
      • [x] SetNX
      • [x] GetSet
      • [x] MGet
      • [x] MSet
    • [x] List
      • [x] LMembers
    • [x] Set
      • [x] SMembers
    • [x] Sorted Set
      • [x] ZMembers
  • [ ] 支持更丰富的数据结构 (2021.01.20)
    • [x] Bitset
    • [ ] 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 的限制 1000
server.slow_query_threshold 慢查询记录的阈值，单位为 ms 100

接口说明

string

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

list

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

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 创建 bitset
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 的个数

pub sub

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

benchmark

监控

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

配置 grafana

最终效果可参考：性能测试的 grafana 图

SDB 背后的思考

SDB 存储引擎选型

SDB 项目最核心的问题是数据存储方案的问题。

首先，我们不可能手写一个存储引擎。这个工作量太大，而且不可靠。 我们得在开源项目中找到适合 SDB 定位的存储方案。

SDB 需要能够提供高性能读写能力的存储引擎。 单机存储引擎方案常用的有：B+ 树、LSM 树、B 树等。

还有一个前置背景，golang 在云原生的表现非常不错，而且性能堪比 C 语言，开发效率也高，所以 SDB 首选使用纯 golang 进行开发。

那么现在的问题变成了：找到一款纯 golang 版本开发的存储引擎，这是比较有难度的。收集了一系列资料后，找到了以下开源方案：

综合来看，golangdb、badger、pebble 这三款存储引擎都是很不错的。

为了兼容这三款存储引擎，SDB
提供了抽象的接口
，进而适配这三个存储引擎。

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 的核心逻辑：

LPush
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()
}
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 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 面临了【最后一公里】的问题是通讯协议的选择。

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

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

SDB 集群方案

SDB 的集群方案其实是在规划中的，之前也考虑了 TiKV 集群方案和 Redis 集群方案。

但目前 SDB 把注意力放在持久化、数据结构上。增加更多的数据结构，并将易用性做到极致。之后再实现集群方案。

感谢

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

1 个赞