花了好长时间，重新设计了 SDB 的存储模型

[Aidenboss]

SDB 背后的思考 ———— List 数据模型设计

---

我们借助 LSM / B+ 树的实现，已经有了可靠的 kv 存储引擎了 。回顾下我们具备的能力，是一个巨大的、持久化的 sortedMap 。提供的接口是：

• get(key)
• set(key, value)
• delete(key)
• scan(minKey, maxKey)

那么，我们如何根据上述接口，实现 List 数据结构呢？我们希望 List 数据结构提供以下能力：

• LLPush(key, values)
  • 从 list 左边增加元素
• LRPush(key, values)
  • 从 list 右边增加元素
• LCount(key)
  • 获取 list 的元素个数
• LRem(key, values)
  • 从 list 删除某些元素
• LDel(key)
  • 删除 list
• LRange(key, offset, limit)
  • 遍历 key ，offset 指从第几个位置开始遍历，limit 代表遍历多少个元素
• LTtl(key, ttl)
  • 指定 list 过期时间

存储模型图

List meta 设计

为了应对上述的操作，每个 list 对应 N 个 meta 。其中 meta 包含：

• version （版本号）
• count (元素个数)
• nextSeq (下一个元素的 seq)
• deleted (是否删除)
• ttl (过期时间)

meta 在 sortedMap 的 key 称为 metaKey ，其生成规则 = lm:{key}:{version}。其中 version 是通过雪花算法实现全局自增的。假设有一个 listA ，则它的 meta 在 sortedMap 的数据可能是：

list	version	metaKey	meta 信息
listA	0	lm:listA:0	{version=0, count=10, nextSeq=11, deleted=true, ttl=0}
listA	1	lm:listA:1	{version=1, count=3, nextSeq=4, deleted=true, ttl=0}
listA	2	lm:listA:2	{version=2, count=15, nextSeq=16, deleted=false, ttl=0}

可以看出，每个 list 的 meta 是包含多版本的。SDB 只会认为最高版本的 meta 是有效的，非最高版本的 meta 和对应的元素会在后台任务中回收数据。

List 元素在 sortedMap 中的存储结构

List 中每个元素都包含了 seqKey 和 valueKey 。生成规则是：

• seqKey = ls:{key}:{version}:{seq}:{value}
• valueKey = lv:{key}:{version}:{value}:{seq}

假设有一个 listA ，它的最高版本是 3 ，其元素列表如：[a, b, c]。 则每个元素在 sortedMap 中存储的数据如：

元素	seqKey	valueKey
a	ls:listA:3:0:a	lv:listA:3:a:0
b	ls:listA:3:1:b	lv:listA:3:b:1
c	ls:listA:3:2:c	lv:listA:3:c:2

由于 sortedMap 是有序的，在遍历 list 时，我们可以通过 seqKey 进行遍历。这样我们可以顺序得到元素 a 、b 、c 。

为了实现快速删除 list 中的某个元素，我们可以借助 valueKey 实现快速删除元素。

List ttl 设计

为了支持 List 过期功能。SDB 在 List meta 中增加了 ttl 字段。 假设 listA 在版本 3 中设置了 ttl=10 ，则在 sortedMap 中 listA 的 meta 数据可能是：

list	version	metaKey	meta 信息
listA	0	lm:listA:0	{version=0, count=10, nextSeq=11, deleted=true, ttl=0}
listA	1	lm:listA:1	{version=1, count=3, nextSeq=4, deleted=true, ttl=0}
listA	2	lm:listA:2	{version=2, count=15, nextSeq=16, deleted=false, ttl=0}
listA	3	lm:listA:3	{version=3, count=8, nextSeq=9, deleted=false, ttl=10}

当读取 listA meta 时，会读到最后一行，发现 ttl < 当前时间，则认为该 listA 数据是不存在的。

List 回收 deleted 数据

由于 SDB 采用的是标记删除。假设有一个 listA ，其操作流程如下：

• 向 listA 增加元素 a
• 删除整个 listA
• 向 listA 增加元素 b
• 删除整个 listA
• 向 listA 增加元素 c

则 listA 的 meta 在 sortedMap 存储的数据如：

list	version	metaKey	meta 信息
listA	0	lm:listA:0	{version=0, count=1, nextSeq=1, deleted=true, ttl=0}
listA	1	lm:listA:1	{version=1, count=1, nextSeq=1, deleted=true, ttl=0}
listA	2	lm:listA:2	{version=2, count=1, nextSeq=1, deleted=false, ttl=0}

元素在 sortedMap 存储的数据如：

list	version	元素	seqKey	valueKey
listA	0	a	ls:listA:0:0:a	lv:listA:0:a:0
listA	1	b	ls:listA:1:0:b	lv:listA:1:b:0
listA	2	c	ls:listA:2:0:c	lv:listA:2:c:0

会发现 listA 记录中 version=0 和 version=1 相关数据都可以回收。

为了支持快速回收无效数据，SDB 为 deleted 的 list 版本增加了 deletedKey ，如 listA 的 deletedKey 在 sortedMap 的数据是：

list	version	deletedKey
listA	0	ld:listA:0
listA	1	ld:listA:1

SDB 会定时扫描 deletedKey 并回收相关数据。

List 回收 ttl 数据

和 SDB 实现的标记删除一样，SDB 也会存在大量过期的数据，假设对 listA 的操作流程如下：

• 向 listA 增加元素 a
• 设置 listA ttl=1 （会快速过期）
• 向 listA 增加元素 b
• 设置 listA ttl=1 （会快速过期）
• 向 listA 增加元素 c

则 listA 的 meta 在 sortedMap 存储的数据如：

list	version	metaKey	meta 信息
listA	0	lm:listA:0	{version=0, count=1, nextSeq=1, deleted=false, ttl=1}
listA	1	lm:listA:1	{version=1, count=1, nextSeq=1, deleted=false, ttl=1}
listA	2	lm:listA:2	{version=2, count=1, nextSeq=1, deleted=false, ttl=0}

元素在 sortedMap 存储的数据如：

list	version	元素	seqKey	valueKey
listA	0	a	ls:listA:0:0:a	lv:listA:0:a:0
listA	1	b	ls:listA:1:0:b	lv:listA:1:b:0
listA	2	c	ls:listA:2:0:c	lv:listA:2:c:0

会发现 listA 记录中 version=0 和 version=1 相关数据都可以回收。

为了支持快速回收无效数据，SDB 为 ttl 的 list 版本增加了 ttlKey ，如 listA 的 ttlKey 在 sortedMap 的数据是：

list	version	ttlKey
listA	0	lt:listA:0
listA	1	lt:listA:1

SDB 会定时扫描 ttlKey 并回收相关数据

List 增加元素

假设 listA 最高版本号是 0 ，有元素 [a, b, c]。则其元素在 sortedMap 存储的数据是：

list	version	元素	seqKey	valueKey
listA	0	a	ls:listA:0:0:a	lv:listA:0:a:0
listA	0	b	ls:listA:0:1:b	lv:listA:0:b:1
listA	0	c	ls:listA:0:2:c	lv:listA:0:c:2

可以看出，seqKey 是用来控制遍历 list 顺序的。假设向 listA 左边增加元素 d ，右边增加元素 e ，则数据如下：

list	version	元素	seqKey	valueKey
listA	0	d	ls:listA:0:-3:d	lv:listA:0:d:-3
listA	0	a	ls:listA:0:0:a	lv:listA:0:a:0
listA	0	b	ls:listA:0:1:b	lv:listA:0:b:1
listA	0	c	ls:listA:0:2:c	lv:listA:0:c:2
listA	0	e	ls:listA:0:4:e	lv:listA:0:e:4

可以看出 SDB 通过在元素上使用负的 seq ，达到了左边和右边增加元素的功能。