SDB ：纯 golang 开发、数据结构丰富、持久化的 NoSQL 数据库
简单介绍
- 纯 golang 开发，核心代码不超过 1k，代码易读
- 数据结构丰富
- 持久化
背后的思考
SDB 为什么会存在？
试想以下业务场景：
- 计数服务：对内容的点赞、播放等数据进行统计
- 评论服务：发布评论后，查看某个内容的评论列表
- 推荐服务：每个用户有一个包含内容权重的推荐列表
以上几个业务场景，都可以通过 MySQL + Redis 的方式实现。 这里的问题是：MySQL 更多的是充当持久化的能力，Redis 充当的是在线服务的读写能力。
那么只使用 Redis 行不行？ 答案是否定的，因为 Redis 无法保证数据不丢失。
那有没有一种存储能够支持高级的数据结构，并能够将数据进行持久化的呢？
答案是：非常少的。有些数据库要么是支持的数据结构不够丰富，要么是接入成本太高，要么是不可控。
为了解决上述问题，SDB 产生了。SDB 提供了非常丰富的数据结构，并提供持久化能力。在以上场景中，将不再需要多种存储混用，只使用 SDB 就能解决数据存储、数据服务的问题。
SDB 存储引擎选型
从 SDB 为什么存在？ 可以知道，SDB 项目最核心的问题是数据存储方案的问题。
首先，我们不可能手写一个可靠的存储引擎。这个工作量太大，而且不可控。我们得在开源项目中找到适合 SDB 定位的存储方案。
SDB 需要能够提供高性能读写能力的存储引擎。 单机存储引擎方案常用的有：B+ 树、LSM 树、B 树等。
还有一个前置背景，golang 在云原生的表现非常不错，而且性能堪比 C 语言，开发效率也高，所以 SDB 首选使用纯 golang 进行开发。
那么现在的问题变成了：找到一款纯 golang 版本开发的存储引擎，这是比较有难度的。收集了一系列资料后，找到了以下开源方案：
- LSM 树
- B+ 树
分别来说说以上的项目
- go-leveldb 是一个 unstable 的项目，无法使用
- syndtr-goleveldb 未在生产环境中使用过，不敢保证稳定性
- badger 性能低 leveldb
- boltdb-bolt 是废弃的项目，无法使用
- etcd-bolt 主要是用于分布式环境下的数据同步，无法应对数据读写
其实 SDB 开始选择的是：syndtr-goleveldb。后面发现了该项目未在生产环境中使用过，所以继续寻找存储方案。
黄天不负有心人，找到了 pebble 这款存储引擎。
pebble 是基于 golang-leveldb 项目实现了 RocksDB 的 KV 存储引擎，采用了 LSM
树的设计，提供了高性能读写能力。并且在 cockroachdb 数据库使用，有不错的稳定性。
最终 SDB 选择了 pebble 作为存储引擎。
SDB 数据结构设计
SDB 已经通过 pebble 解决了存储引擎的问题。 但如何在 KV
的存储引擎上增加数据结构的逻辑呢？
首先 pebble 提供了以下的接口能力：
- set
- get
- batch
- iterator
其中 set、get 不需要多说。batch 用于批量写入，在批量场景中会使用到。最值得一提的是 iterator，由于 pebble 的 KV 存储是有序的，可以通过 iterator 进行迭代。
接下来，我以支持 List 数据结构为例子，剖析下 SDB 是如何通过 pebble 存储引擎支持 List 的。
List 数据结构提供了以下接口：LPush、LPop、LExist、LRange、LCount。
如果一个 List 的 key 为：[hello]，该 List 的列表元素有：[aaa, ccc, bbb]，那么该 List 的每个元素在 pebble 的存储为：
List 元素生成 pebble key 的策略：
- 数据结构前缀：List 都以 l 字符为前缀，Set 是以 s 为前缀…
- List key 部分：List 的 key 为 hello
- unique_ordering_key：生成方式是通过雪花算法实现的，雪花算法保证局部自增
- pebble value 部分：List 元素真正的内容，如 aaa、ccc、bbb
还有一些前规则是：pebble 是 LSM 树的实现，采用字典序对 pebble 的 key 排序，默认是从小到大排序的。 所以 List 中元素的 unique_ordering_key
生成就决定了元素在 pebble 中存储的顺序。
由于 unique_ordering_key 是自增的，也就保证了元素在 List 中的插入顺序了。
接下来，我们看看 LPush、LPop、LRange 的核心逻辑：
LPush
LPop
在写入到 pebble 的时候，key 的生成是通过 unique_ordering_key 的方案。 无法直接在 pebble 中找到 List 的元素在 pebble
key。在删除一个元素的时候，需要遍历 List 的所有元素，找到 value = 待删除的元素，然后进行删除。核心逻辑如下：
LRange
和删除逻辑类似，通过 iterator
接口进行遍历。 这里对反向迭代做了额外的支持
允许 Offset 传入 -1，代表从后进行迭代。
以上就实现了对 List 的数据结构的支持。
其他的数据结构大体逻辑类似，其中 sorted_set
更加复杂些。可以自行查看。
SDB 通讯协议方案
解决完了存储和数据结构的问题后，SDB 面临了【最后一公里】的问题是通讯协议的选择。
SDB 的定位是支持多语言的，所以需要选择支持多语言的通讯框架。
grpc 是一个非常不错的选择，只需要使用 SDB proto 文件，就能通过 protoc 命令行工具自动生成各种语言的客户端，解决了需要开发不同客户端的问题。
SDB 集群方案
SDB 的集群方案其实是在规划中的，之前也考虑了 Tikv 集群方案和 Redis 集群方案。
但目前 SDB 把注意力放在持久化、数据结构上。增加更多的数据结构，并将易用性做到极致。之后再实现集群方案。