乐趣区

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

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 同理。
退出移动版