redis作為一個內存資料庫，在擁有極高讀寫性能的同時，提供了豐富的數據結構：string、hash、list、set、zset，成為了構建高並髮網站不可或缺的一部分。

但redis並非是完美的，譬如：

  1. 內存很貴，而且並不是無限容量的，所以我們不可能將大量的數據存放到一臺機器。
  2. 非同步複製並不能保證 Redis 的數據安全。
  3. Redis 提供了 transaction mode，但其實並不滿足 ACID 特性。
  4. Redis 提供了集羣支持，但也不能支持跨多個節點的分散式事務。

理想情況下的KV存儲需要滿足以下條件：

  • 兼容redis現有協議（使業務段端可以無感知遷移）
  • 將數據存儲在多臺機器上（基於hash/range分片），並且擁有多重備份
  • 單個存儲節點的宕機，不影響整個系統的正常運轉（或者可以基於備份自動恢復）
  • 支持集羣成員變更（添加/刪除存儲節點）
  • 相對於redis，性能損失(延遲，吞吐量 ...等)要在可接受範圍內
  • 對於監控、命名空間 ... 提供更好的支持

1. ConfigServer + DataServer 架構

上述架構，由一個中心控制節點（config server）和一系列的服務節點（data server）組成。

  • config server 負責管理所有的data server，並維護data server的狀態信息；為了保證高可用（High Available），config server可通過hearbeat 以一主一備形式提供服務；
  • data server 對外提供各種數據服務，並以心跳的形式將自身狀況彙報給config server；所有的 data server 地位都是等價的。

在讀寫數據的時候，client首先連接config server獲取整個集羣的數據分佈表，確定將要讀寫的key位於哪一個data server實例。數據分佈表具有version的概念，client在讀寫數據的時候，必須要帶上version信息。

當整個集羣的分片信息發生變化的時候(有新data server的加入或者hash節點的重新分配），config server就會更新該version信息，由於data server與config server之間維護著heartbeat，data server可以直接感知到version的變化。當client端下次請求data server的時候，data server發現version不匹配，就會拒絕該請求，client端就會重新去config server獲取新的數據分佈表。

這種（無proxy）架構，直接讀寫數據節點，可以提供較好的性能。但由於數據分佈表version機制的存在，這種架構無法兼容redis協議。

2. TiKV + Proxy 架構

TiKV 是一個高性能，支持分散式事務的 key-value 資料庫。雖然它僅僅提供了簡單的 key-value API，但基於 key-value，我們可以構造自己的邏輯去創建更強大的應用。譬如，TiDB 通過將 database 的 schema 映射到 key-value 來支持了相關 SQL 特性。所以對於 Redis，我們也可以採用同樣的辦法 - 構建一個支持 Redis 協議的服務，將 Redis 的數據結構映射到 key-value 上面。

那麼如何基於TiKV構建一個兼容redis協議的分散式kv存儲呢？

  • Redis Protocol Layer: 實現對redis協議的支持
  • GMKV Logic Layer：將redis的數據結構轉化為底層存儲引擎支持的kv形式
  • Transactional KV API Layer：存儲引擎抽象層，與底層存儲引擎解耦，方便支持不同的存儲引擎

3. Redis 協議實現層

redisClient與redisServer之間的通信協議叫：RESP (REdis Serialization Protocol)。

RESP遵循Request-Response模型，具體實現如下:

  • Clients send commands to a Redis server as a RESP Array of Bulk Strings.
  • The server replies with one of the RESP types according to the command implementation.

在RESP中，數據的類型取決於該數據的第一個位元組：

  • For Simple Strings the first byte of the reply is "+"
  • For Errors the first byte of the reply is "-"
  • For Integers the first byte of the reply is ":"
  • For Bulk Strings the first byte of the reply is "$"
  • For Arrays the first byte of the reply is "*"

RESP Arrays 的格式如下:

  • A * character as the first byte, followed by the number of elements in the array as a decimal number, followed by CRLF.
  • An additional RESP type for every element of the Array.

redis協議官方文檔：

Redis Protocol specification - Redis?

redis.io

redcon是一個redis協議的go實現：

tidwall/redcon?

github.com圖標

4. GMKV 邏輯處理層

GMKV Logic Layer作為整個GMKV的核心，負責將redis的各種數據結構(string, list, hash, set, zset) 映射為底層存儲引擎(TiKV)支持的KV結構，通過Transactional KV API層對存儲引擎進行讀寫。

核心問題在於，如何將redis的各種數據結構以KV的形式存儲，並且提供較高的讀寫性能。一種可行的辦法是對key進行拼接，為了防止和業務的key衝突，這裡需要制定一個特殊的規則來避免衝突。

這個規則就是經典的tlv(type-length-value)規則，當然為了節省存儲空間，在不發生衝突的時候，會使用tv(type-value)規則。

4.1、 redis的string結構

string結構的前綴為：k。

比如redis有一個string類型，key是hello，value時world。

在GMKV中的key儲存為 khello，value是world。 其中前面的k是為string數據結構加的前綴，GMKV為每種數據結構定義了唯一的前綴。

4.2、 redis的hash結構

hash結構的前綴為：h。

假如我們要將一部視頻的信息存在redis中，視頻的ID為：941215，視頻包含title，url，state等欄位。依照上面的tlv規則，可以拼出三個key：h{6}941215-title, h{6}941215-url, h{6}941215-state。

"h"作為hash結構的前綴，"6"作為hash結構key的長度，"941215"作為hash結構的key，"-"作為hash結構key與field的間隔符(可省略)，"title"、"url"、 "state"作為hash結構的field，三個拼出的key所對應的value即為hash結構各個field的value。

redis的hash結構的有些命令需要獲取hash結構的所有欄位，該如何實現？

前綴遍歷：只要遍歷以h{6}941215為前綴的所有kv就可以了。

4.3、 redis的zset結構

zset結構的前綴有兩個：z和s。

  • field到score的映射：前綴為s
  • score到field的映射：前綴為z

redis的zset結構是一種很強大的數據結構，名字叫做有序集合。zset和hash很類似，不過hash裡面field的值變成了zset裡面的權重或者評分。有了評分，就涉及基於評分的排序了。

zset內部會維護field的值以及評分的排序，很多排行榜都是基於zset實現的。

假設要把某個班級所有學生的數學成績存在一個zset中，以math作為key，以a,b,c代替學生的名字作為field，對應的score作為學生的數學成績，abc的成績分別是：75，95，-80

對於field到score的映射，和hash結構類似：s{4}math{1}a、s{4}math{1}b、s{4}math{1}c

對於score到field的映射，則變成：z{4}math=75，z{4}math=95，z{4}math-80。

那麼為什麼分隔符不是+/-，而是=/-呢？

因為zset的zrangebyscore需要用前綴遍歷實現，而前綴遍歷是按照key的位元組序遍歷的。

而+的位元組序小於-，而=的位元組序大於-。為了保證遍歷的順序與score的排序保持一致，將+替換為=。

4.4、 redis的list結構

list結構的前綴為：q。

對於list結構，如果在內存中使用鏈表實現的話，就會很簡單。但是如果用kv的方式實現，我們需要一個雙向隊列。

雙向隊列可以為頭部和尾部增刪數據，我們給頭部一個遞增的序號，給尾部一個遞減的序號，則隊列中的編號一定是遞增的。

根據以上結論以及tlv規則，可以使用kv實現一個list。假設有一個key為students的list，list的前向索引和後向索引分別為：q{8}students{minseqflag}、q{8}students{maxseqflag}。

list中item的key格式為：q{8}students{seq}

對於list的大小，通常使用一個單獨的key存儲：Q{8}students。

對於lpush或者rpush時，我們先計算對應的seq，同時寫入數據然後更新seq即可。對於lpop或者rpop時，我們計算出對應的seq，同時刪除數據然後更新seq即可。對於lindex和lset操作，含義是取出或設置對應下標位置的列表值，這裡也可以計算出對應的seq，然後得到對應值或者設置值。

REDIS的有一些操作比較反人類，比如linsert和lrem操作。

lrem含義為刪除某些指定元素，linsert含義是在某些位置插入一些元素。這兩個操作不符合隊列的定義，一旦操作後，seq就不滿足連續的特徵，所以ssdb不支持這個操作。假設非要實現這要一個操作，那操作後就需要重新調整整個隊列，使其seq保持連續，那複雜度就是O(n*log(m))了。

4.5、如何支持ttl

在GMKV中，我們使用了多個kv來存儲redis的某個數據結構。那麼支持redis的ttl就變成了一件麻煩的事。

具體的實現方案是：把所有設置了過期的key放在一個固定的zset下面，zset的field就是設置了過期時間的key，而field的value則是過期的時間點(以毫秒時間展示).

根據zset按照score排序的特性，GMKV使用一個單獨的線程，從該zset中不斷的取score最小的數據，檢查如果已過期，就刪除對應的數據結構。

5. 存儲引擎抽象層

為了實現底層存儲引擎的可插拔，我們需要Transaction KV API Layer實現對底層存儲引擎(TiKV)的抽象，給上層(GMKV)讀寫提供一致的事務介面。

這樣的話，在特定場景下我們可以提供其它存儲引擎給上層使用。譬如，阿里巴巴的tair就支持mdb(緩存), rdb(緩存), ldb(存儲，基於leveldb) 等多種存儲引擎。

6. 工程實踐優化

6.1 對SSD磁碟的使用

TiKV底層採用了RocksDB作為存儲引擎，RocksDB衍生自Google的LevelDB，LevelDB採用了採用Log-Structured Merge-Tree數據結構，RocksDB/LevelDB 憑藉其優異的寫性能及不俗的讀性能成為眾多分散式組件的存儲基石。

如需更多瞭解Log-Structured Merge-Tree，可以參考之前的一篇文章：

gushitong：lsm-tree?

zhuanlan.zhihu.com圖標

RocksDB針對SSD磁碟做了諸多優化，所以在性能測試的時候務必採用SSD磁碟。

6.2 zset的score支持double類型

在對zset的介紹過程中，我們默認score為int64類型，而在redis中，score是支持浮點型的。

如果我們把int64轉換為浮點型，能否讓浮點型的位元組序與score的排序也保持一致呢，這裡可以參考PingCap-唐劉大大的一篇文章：

浮點數位元組序比較?

www.jianshu.com圖標

5.3 大對象的延遲刪除

在刪除list/hash/set/zset的時候，如果該list/hash/set/zset中的元素過多，整個刪除操作可能會變慢。

一個可行的方案是引入ObjectID機制：

  • 每個對象指向一個唯一的ObjectID
  • 刪除時RawKey時，將ObjectID及其關聯的items放入GC隊列，延遲刪除；
  • 新建時RawKey時，RawKey指向新的ObjectID；

參考鏈接：

Redis Protocol specification - Redis?

redis.io

gushitong：lsm-tree?

zhuanlan.zhihu.com圖標三篇文章瞭解 TiDB 技術內幕 - 說存儲?

pingcap.com圖標淘寶分散式NOSQL框架：Tair - 如果的事 - 博客園?

www.cnblogs.com圖標
推薦閱讀：

相關文章