关于go:花了很长时间重新设计了-SDB-的存储模型

从上一篇中，咱们曾经设计好了 List 数据结构在 kv 存储中的数据模型。

这一篇，咱们介绍下 SDB 在 List 数据结构中的锁模型设计。

咱们从新回顾下 List 数据模型图：

能够看出，每个 List 都蕴含 N 个版本，每个版本都有 meta key、deleted key、ttl key。其作用如下：

meta key
- 存储 List 的 meta 信息，如元素个数、是否删除、ttl、版本号等。
deleted key
- 能够依据该 key 检索被删除的 List，用于数据回收。
ttl key
- 能够依据该 key 检索被带有 ttl 的 List，用于数据回收。

每个元素在 List 上都蕴含一个 seq key 和 value key。其作用如下：

seq key
- 用于程序遍历 List 元素。
value key
- 用于在 List 中删除某元素。

Q：用户同时进行写入操作申请：LLPush、LRPush、LDel、LRem 等，如何加锁？

A：因为这类申请会操作 meta key。为了保障一致性，SDB 会依照用户写入的 key 进行加锁。实际上，SDB 外部保护了多把锁，每个 key hash 后会取到对应的锁，而后对该锁进行加锁操作。伪代码如下：

var lockers []*sync.RWMutex

// 写操作加锁
func wlock(key []byte) {getLocker(key).Lock()}

// 读操作加锁
func wUnLock(key []byte) {getLocker(key).Unlock()}

// 依据 key 获取锁
func getLocker(key []byte) *sync.RWMutex {checksum := crc16.Checksum(key, crc16.IBMTable)
    return lockers[int(checksum)%len(lockers)]
}

Q：为什么不思考每个 key 一把锁，而是多个 key 通过 hash 后共用一把锁？

A：如果每个 key 一把锁，可能会呈现锁太多带来的性能损耗。尽管多个 key 通过 hash 后会共用一把锁，但每次用户的写入申请应该是疾速返回的，写锁锁住的工夫应该是不会太长的。

Q：用户的写入操作和 LCount、LRange 的加锁逻辑是什么？

A：针对 LCount，只是读取 meta 信息，不须要做额定的加锁解决。而 LRange 操作是遍历 key 的，为了避免在遍历的时候，对该 List 进行了写入操作带来的数据凌乱问题。SDB 对该操作加了读锁，伪代码如下：

// 写操作加锁
func rlock(key []byte) {getLocker(key).RLock()}

// 读操作加锁
func rUnLock(key []byte) {getLocker(key).RUnlock()}

Q：deleted 数据回收工作和用户的写入申请加锁逻辑是怎么的？

A：因为 SDB 是采纳多版本的设计，用户的写入申请只会操作最新版本的 meta key 等，而 deleted 数据回收工作不会回收最新版本的数据，所以二者不存在抵触的问题，不须要额定加锁。

Q：ttl 数据回收工作和用户的写入申请加锁逻辑是怎么的？

A：因为 SDB 是采纳多版本的设计，用户的写入申请只会操作最新版本的 meta key 等，而 ttl 数据回收工作可能会回收最新版本的数据，所以二者不存在抵触的问题。这二者存在以下组合：

用户申请 LLPush（LRPush 同理）+ ttl 数据回收工作同时进行
- 假如 listA 最高版本号是 3，行将过期，meta 信息是：{count=3, version=3, ttl=1, nextSeq=4, deleted=false}，蕴含了元素是：[a, b, c]。而 LLPush 的元素是：[a, d]。– LPush 获取到最高版本号 3，发现未过期（行将过期）。所以会往版本号 3 写入 [a, d] 数据 + meta {count=5, version=3, ttl=1, nextSeq=6, deleted=false} 信息和元素 [a, d]。– ttl 数据回收工作只回收了版本号 3 的 meta key：{count=3, version=3, ttl=1, nextSeq=4, deleted=false} 和数据：[a, b, c]。
- 总结：这种状况不须要加锁，只须要在每次 LPush 是再保障写入一次 ttl key 即可。等下一次回收工作还会回收该 listA 的版本号 3 的所有数据。
用户申请 LDel + ttl 数据回收工作同时进行
- 假如删除 listA 最高版本号是 3，对 listA 进行删除，同时 ttl 数据回收工作发现 listA 行将过期。
- 总结：这种状况不须要加锁，ttl 数据工作会回收一次 listA 数据，deleted 数据回收也会回收一次 listA 数据。
- LRem 同理。

SDB 背地的思考 ———— List 数据结构锁模型设计