聊聊原美圖開源的 Kv 存儲 Titan

作者：董澤潤 2023-02-06 09:44:35

國內(nèi)公司大部分都有自己的輪子，開發(fā)完一代目拿到 KPI 走人，二代目繼續(xù)填坑，三四代淪為邊緣。即使開源也很難有持續(xù)的動力去維護(hù)，比如本文要分享的美圖 titan[1]，很多優(yōu)化的 proposals[2] 都沒實(shí)現(xiàn)，但是做為學(xué)習(xí)項(xiàng)目值得研究，萬一哪天二次開發(fā)呢？

市面上開源 kv 輪子一大堆，架構(gòu)上都是 rocksdb 做單機(jī)引擎，上層封裝 proxy, 對外支持 redis 協(xié)議，或者根據(jù)具體業(yè)務(wù)邏輯定制數(shù)據(jù)類型，有面向表格 table 的，有做成列式存儲的。

整體架構(gòu)

Titan 代碼 1.7W 行，純 go 語言實(shí)現(xiàn)。server 層只負(fù)責(zé)處理用戶請求，將 redis 數(shù)據(jù)結(jié)構(gòu)映射成 rocskdb key/value, 底層使用 tikv 集群。

站在巨人的肩膀上，titan 無需考濾數(shù)據(jù) rebalance, 不關(guān)心數(shù)據(jù)存儲副本同步，這也是為什么代碼量如此少

壓測[3] 數(shù)據(jù)只有 2018 年的，性能一般，latency 也沒區(qū)分 99 和 95 分位。如果基于最新版本的 tikv 集群測試效果可能更好

數(shù)據(jù)類型實(shí)現(xiàn)

目前數(shù)據(jù)結(jié)構(gòu)只實(shí)現(xiàn)了 string, set, zset, hash, list, 有些也只是部分支持，只能說夠用

持久化的 kv 輪子，難點(diǎn)就是如何把 redis 數(shù)據(jù)結(jié)構(gòu)與 rocksdb key/value 做映射。原來單進(jìn)程天然實(shí)現(xiàn)的原子性很難實(shí)現(xiàn)，維護(hù)一種數(shù)據(jù)涉及多個(gè) key, 如果分布在多個(gè) instance 進(jìn)程又涉及了分布式事務(wù)，吞吐自然降低很多

比然我們常用 lua 腳本自定義一些業(yè)務(wù)邏輯，將涉及的多個(gè) key 用 hash tag 處理下，變成同一個(gè) redis slot, 但這在 titan 里是做不到的

性能問題，比如 HLEN? 操作，本來 redis O(1) 操作，如果在 titan 的 hash metakey 中維護(hù) len 記錄，那么高并發(fā)寫刪 hash 時(shí)就會有大量沖突。再比如 zset 數(shù)據(jù)結(jié)構(gòu)，zrange?, zrangebyscore?, zrangebylex 需要將 member, score 分別編碼存儲，用空間換時(shí)間

String

String 類型只有兩種 key: MetaKey, ExpireKey

MetaKey 中 namespace 用于實(shí)現(xiàn)多租戶隔離，但也只是邏輯上的，畢竟資源仍然是共用的，dbid 類似 redis db0, db1 ...

ExpireKey 用于主動過期數(shù)據(jù)，后臺任務(wù)定期掃。每個(gè)類型都有，后面省略不表

MetaValue 前 42 字節(jié)為屬性信息，后面才是真正的用戶 value. 時(shí)間字段表示創(chuàng)建，更新，過期 timestamp, 被動過期時(shí)會檢查 ExpireAt. uuid 用于唯一標(biāo)識 key, titan 主動 GC 會用到

Type 表示數(shù)據(jù)類型

const (
 ObjectString = ObjectType(iota)
 ObjectList
 ObjectSet
 ObjectZSet
 ObjectHash
)

Encoding 表示具體的編碼類型

const (
 ObjectEncodingRaw = ObjectEncoding(iota)
 ObjectEncodingInt
 ObjectEncodingHT
 ObjectEncodingZipmap
 ObjectEncodingLinkedlist
 ObjectEncodingZiplist
 ObjectEncodingIntset
 ObjectEncodingSkiplist
 ObjectEncodingEmbstr
 ObjectEncodingQuicklist
)

為了兼容，定義與 redis 一致

Set

MetaKey? 與 String 類型一樣，MetaValue? 一共 50 字節(jié)，前 42 字節(jié)一樣，后 8 字節(jié)維護(hù)集合 Set? 成員數(shù)量信息。也就是說后續(xù)的 SCARD 是 O(1)，但同時(shí)刪除增加都要修改 MetaValue

DataKey? 編碼了 Set 唯一 uuid 與成員 member 信息，由于集合只需要成員 member, 所以 DatValue? 是 []byte{0}

Zset

與集合一樣，zset MetaKey/MetaValue 內(nèi)容一樣

DataKey? 內(nèi)容基本一樣，DataValue? 是 score 值，同時(shí)也維護(hù)了 score -> member 映射的 ScoreKey?, 用于空間換時(shí)間方便 zrangebyscore 查詢

Hash

注意這里 hash 的 MetaValue? 并沒有維護(hù)成員 Len 信息，所以當(dāng) HLEN 時(shí)要遍歷 range 整個(gè) data key 空間，為什么這么做呢？

titan 作者說 hash 寫并發(fā)時(shí)會有大量的事務(wù)沖突，所以選擇不維護(hù)。后來他們提出一個(gè)方案，對 MetaKey 拆分成多個(gè) slot，盡可能減少沖突，同時(shí)還能提高 HELN 性能，不過后來也沒實(shí)現(xiàn)

List

List? 有兩種結(jié)構(gòu)，一個(gè)是 ziplist?, value 是用 pb 將多個(gè)元素編碼在一起, 另外一個(gè)是 linkedlist. 當(dāng)前實(shí)現(xiàn)沒看到 ziplist 到 linkedlist 的轉(zhuǎn)換，其實(shí)對于持久化存儲來說，只用 linkedlist 足夠了

MetaValue 后 24 字節(jié)分別維護(hù)了 len, lindex 和 rindex, 其中 index 類型是 float64, 為什么不是 int64 類型呢？

原因在于對于 Linsert 操作，如果插入 (2, 3) 之間，那么會失敗，但是用 float64 大概率會成功，但是考濾 float64 也有精度問題，存在失敗的概率

// calculateIndex return the real index between left and right, return ErrPerc=
func calculateIndex(left, right float64) (float64, error) {
 if f := (left + right) / 2; f != left && f != right {
  return f, nil
 }
 return 0, ErrPrecision
}