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

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

整體架構(gòu)

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

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

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

數(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í)就會(huì)有大量沖突。再比如 zset 數(shù)據(jù)結(jié)構(gòu)，zrange?, zrangebyscore?, zrangebylex 需要將 member, score 分別編碼存儲(chǔ)，用空間換時(shí)間

String

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

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

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

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

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í)會(huì)有大量的事務(wù)沖突，所以選擇不維護(hù)。后來他們提出一個(gè)方案，對(duì) MetaKey 拆分成多個(gè) slot，盡可能減少?zèng)_突，同時(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í)對(duì)于持久化存儲(chǔ)來說，只用 linkedlist 足夠了

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

原因在于對(duì)于 Linsert 操作，如果插入 (2, 3) 之間，那么會(huì)失敗，但是用 float64 大概率會(huì)成功，但是考濾 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 就是值

事務(wù)沖突

由于 titan 整體都是小事務(wù)，所以對(duì)于 tikv 事務(wù)開啟了 1PC 和 AsyncCommit, 來提高整體吞吐量。對(duì)于沖突的事務(wù)，titan 盡可能重試證執(zhí)行成功

關(guān)于 affinity 親緣性問題，titan 想將一個(gè)類型的 key 盡可能放到一個(gè) tikv 實(shí)例中，當(dāng)前沒有實(shí)現(xiàn)，很難，不好搞。可以說 tikv 減少了持久化 kv 開發(fā)難度，也束縛了靈活性

刪除 GC

Delete? 時(shí)，刪除 MetaKey?，如果存在 TTL 那么刪除 ExpireKey?, 對(duì)于非 String，將 DataKey 扔到 sys namespace 中

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

后臺(tái) doGC? 調(diào)用 gcDeleteRange? 慢慢刪除，由于 DataKey 中存在 uuid, 基本不會(huì)重復(fù)，不影響用戶重新創(chuàng)建相同 key

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

運(yùn)維周邊

代碼開源只是第一步，周邊生態(tài)建設(shè)好用的人才多。目前看 tikv 運(yùn)維 pingcap 有很多文檔，基本夠用了，做好參數(shù)上的調(diào)優(yōu)

監(jiān)控，故障處理，做好 chaos 故障注入測(cè)試

數(shù)據(jù)一致性校驗(yàn)，異構(gòu)同步 redis 等等目前看都是缺失的

小結(jié)

目前 titan 的狀態(tài)離真正 production ready 還差若干個(gè) P0 故障，OOM 內(nèi)存被打爆，spike 流量把集群打跨

代碼還有些書寫瑕疵，想要用的同學(xué)，有能力二次開發(fā)的做好集群壓測(cè)，故障注入，限流，千萬(wàn)不要急于上線，隨時(shí)做好回滾的準(zhǔn)備