聊聊原美圖開源的 kv 存儲 titan

市面上開源 kv 輪子一大堆,架構上都是 rocksdb 做單機引擎,上層封裝 proxy, 對外支持 redis 協議,或者根據具體業務邏輯定製數據類型,有面向表格 table 的,有做成列式存儲的

國內公司大部分都有自己的輪子,開發完一代目拿到 KPI 走人,二代目繼續填坑,三四代淪爲邊緣。即使開源也很難有持續的動力去維護,比如本文要分享的 美圖 titan[1],很多優化的 proposals[2] 都沒實現,但是做爲學習項目值得研究,萬一哪天二次開發呢

整體架構

Titan 代碼 1.7W 行,純 go 語言實現。server 層只負責處理用戶請求,將 redis 數據結構映射成 rocskdb key/value, 底層使用 tikv 集羣

站在巨人的肩膀上,titan 無需考濾數據 rebalance, 不關心數據存儲副本同步,這也是爲什麼代碼量如此少

壓測 [3] 數據只有 2018 年的,性能一般,latency 也沒區分 99 和 95 分位。如果基於最新版本的 tikv 集羣測試效果可能更好

數據類型實現

目前數據結構只實現了 string, set, zset, hash, list, 有些也只是部分支持,只能說夠用

持久化的 kv 輪子,難點就是如何把 redis 數據結構與 rocksdb key/value 做映射。原來單進程天然實現的原子性很難實現,維護一種數據涉及多個 key, 如果分佈在多個 instance 進程又涉及了分佈式事務,吞吐自然降低很多

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

性能問題,比如 HLEN 操作,本來 redis O(1) 操作,如果在 titan  的 hash metakey 中維護 len 記錄,那麼高併發寫刪 hash 時就會有大量衝突。再比如 zset 數據結構,zrange, zrangebyscore, zrangebylex 需要將 member, score 分別編碼存儲,用空間換時間

String

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

MetaKey 中 namespace 用於實現多租戶隔離,但也只是邏輯上的,畢竟資源仍然是共用的,dbid 類似 redis db0, db1 ...

ExpireKey 用於主動過期數據,後臺任務定期掃。每個類型都有,後面省略不表

MetaValue 前 42 字節爲屬性信息,後面纔是真正的用戶 value. 時間字段表示創建,更新,過期 timestamp, 被動過期時會檢查 ExpireAt. uuid 用於唯一標識 key, titan 主動 GC 會用到

Type 表示數據類型

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 字節,前 42 字節一樣,後 8 字節維護集合 Set 成員數量信息。也就是說後續的 SCARD 是 O(1),但同時刪除增加都要修改 MetaValue

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

Zset

與集合一樣,zset MetaKey/MetaValue 內容一樣

DataKey 內容基本一樣,DataValue 是 score 值,同時也維護了 score -> member 映射的 ScoreKey, 用於空間換時間方便 zrangebyscore 查詢

Hash

注意這裏 hash 的 MetaValue 並沒有維護成員 Len 信息,所以當 HLEN 時要遍歷 range 整個 data key 空間,爲什麼這麼做呢?

titan 作者說 hash 寫併發時會有大量的事務衝突,所以選擇不維護。後來他們提出一個方案,對 MetaKey 拆分成多個 slot,儘可能減少衝突,同時還能提高 HELN 性能,不過後來也沒實現

List

List 有兩種結構,一個是 ziplist, value 是用 pb 將多個元素編碼在一起, 另外一個是 linkedlist. 當前實現沒看到 ziplist 到 linkedlist 的轉換,其實對於持久化存儲來說,只用 linkedlist 足夠了

MetaValue 後 24 字節分別維護了 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
}

DataKey 編碼 index 信息,DataValue 就是值

事務衝突

由於 titan 整體都是小事務,所以對於 tikv 事務開啓了 1PC 和 AsyncCommit, 來提高整體吞吐量。對於衝突的事務,titan 儘可能重試證執行成功

關於 affinity 親緣性問題,titan 想將一個類型的 key 儘可能放到一個 tikv 實例中,當前沒有實現,很難,不好搞。可以說 tikv 減少了持久化 kv 開發難度,也束縛了靈活性

刪除 GC

Delete 時,刪除 MetaKey,如果存在 TTL 那麼刪除 ExpireKey, 對於非 String,將 DataKey 扔到 sys namespace 中

$sys{namespace}:{sysDatabaseID}:GC:{datakey}

後臺 doGC 調用 gcDeleteRange 慢慢刪除,由於 DataKey 中存在 uuid, 基本不會重複,不影響用戶重新創建相同 key

Flushdb 操作也非常重,理論上可以給所有 key 編碼時帶上 version, 這樣可以快速 flush 快速回滾

運維周邊

代碼開源只是第一步,周邊生態建設好用的人才多。目前看 tikv 運維 pingcap 有很多文檔,基本夠用了,做好參數上的調優

監控,故障處理,做好 chaos 故障注入測試

數據一致性校驗,異構同步 redis 等等目前看都是缺失的

小結

目前 titan 的狀態離真正 production ready 還差若干個 P0 故障,OOM 內存被打爆,spike 流量把集羣打跨

代碼還有些書寫瑕疵,想要用的同學,有能力二次開發的做好集羣壓測,故障注入,限流,千萬不要急於上線,隨時做好回滾的準備

參考資料

[1]

美團 titan: "https://github.com/distributedio/titan",

[2]

優化 proposals: "https://github.com/distributedio/titan/tree/master/proposals",

[3]

titan benchmark: "https://github.com/distributedio/titan/blob/master/docs/benchmark/benchmark.md",

本文由 Readfog 進行 AMP 轉碼,版權歸原作者所有。
來源https://mp.weixin.qq.com/s/JzOIhpxGDBoEERj-MuPDCg