[Go 编程语言] 花了好长时间,重新设计了 SDB 的存储模型


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 ,达到了左边和右边增加元素的功能。

发表回复

您的电子邮箱地址不会被公开。