有小伙伴问我 SDB 的锁模型，我重新梳理了一下

[Aidenboss]

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

---

从上一篇中，我们已经设计好了 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 同理。

[gaodq]

list 中间添加或删除元素是怎么处理的呢

[Aidenboss]

@gaodq 这是一个非常好的问题。我参考了 tendis 和 kvrocks 的实现： https://github.com/Tencent/Tendis/blob/unstable/src/tendisplus/commands/list.cpp#L1425

https://github.com/apache/incubator-kvrocks/blob/unstable/src/redis_list.cc#L326

发现他们都是采用了顺序后移的方式，复杂度是 O(n)。SDB 会好好考虑如何实现这个逻辑。