试想以下业务场景:
以上几个业务场景,都可以通过 MySQL + Redis 的方式实现。 这里的问题是:MySQL 更多的是充当持久化的能力,Redis 充当的是在线服务的读写能力。
那么只使用 Redis 行不行? 答案是否定的,因为 Redis 无法保证数据不丢失。
那有没有一种存储能够支持高级的数据结构,并能够将数据进行持久化的呢?
答案是:非常少的。有些数据库要么是支持的数据结构不够丰富,要么是接入成本太高,要么是不可控。
为了解决上述问题,SDB 产生了。
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 |
测试脚本: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 图
SDB 项目最核心的问题是数据存储方案的问题。
首先,我们不可能手写一个存储引擎。这个工作量太大,而且不可靠。 我们得在开源项目中找到适合 SDB 定位的存储方案。
SDB 需要能够提供高性能读写能力的存储引擎。 单机存储引擎方案常用的有:B+ 树、LSM 树、B 树等。
还有一个前置背景,golang 在云原生的表现非常不错,而且性能堪比 C 语言,开发效率也高,所以 SDB 首选使用纯 golang 进行开发。
那么现在的问题变成了:找到一款纯 golang 版本开发的存储引擎,这是比较有难度的。收集了一系列资料后,找到了以下开源方案:
综合来看,golangdb、badger、pebble 这三款存储引擎都是很不错的。
为了兼容这三款存储引擎,SDB 提供了抽象的 接口 ,进而适配这三个存储引擎。
SDB 已经通过上面三款存储引擎解决了数据存储的问题了。 但如何在 KV 的存储引擎上支持丰富的数据结构呢?
以 pebble 为例子,首先 pebble 提供了以下的接口能力:
接下来,我以支持 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 的插入顺序呢?
这是因为 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