一種 KV 存儲的 GC 優化實踐

作者:vivo 互聯網服務器團隊 - Yuan Jian Wei

從內部需求出發,我們基於 TiKV 設計了一款兼容 Redis 的 KV 存儲。基於 TiKV 的數據存儲機制,對於窗口數據的處理以及過期數據的 GC 問題卻成爲一個難題。本文希望基於從 KV 存儲的設計開始講解,到 GC 設計的逐層優化的過程,從問題的存在到不同層面的分析,可以給讀者在類似的優化實踐中提供一種參考思路。

一、背景介紹

當前公司內部沒有統一的 KV 存儲服務,很多業務都將 Redis 集羣當作 KV 存儲服務在使用,但是部分業務可能不需要 Redis 如此高的性能,卻承擔着巨大的機器資源成本(內存價格相對磁盤來說更加昂貴)。爲了降低存儲成本的需求,同時儘可能減少業務遷移的成本,我們基於 TiKV 研發了一套磁盤 KV 存儲服務。

1.1 架構簡介

以下對這種 KV 存儲 (下稱磁盤 KV) 的架構進行簡單描述,爲後續問題描述做鋪墊。

1.1.1 系統架構

磁盤 KV 使用目前較流行的計算存儲分離架構,在 TiKV 集羣上層封裝計算層(後稱 Tula)模擬 Redis 集羣(對外表現是不同的 Tula 負責某些 slot 範圍),直接接入業務 Redis 客戶端。

圖 1:磁盤 KV 架構圖示

業務寫入數據基於 Tula 轉換成 TiKV 中存儲的 KV 對,基於類似的方式完成業務數據的讀取。

**注意:**Tula 中會選舉出一個 leader,用於進行一些後臺任務,後續詳細說。

1.1.2 數據編碼

TiKV 對外提供的是一種 KV 的讀寫功能,但是 Redis 對外提供的是基於數據結構提供讀寫能力(例如 SET,LIST 等),因此需要基於 TiKV 現有提供的能力,將 Redis 的數據結構進行編碼,並且可以方便地在 TiKV 中進行讀寫。

TiKV 提供的 API 比較簡單:基於 key 的讀寫接口,以及基於字典序的迭代器訪問。

因此,Tula 層面基於字典序的機制,對 Redis 的數據結構基於字典序進行編碼,便於訪問。

注意:TiKV 的 key 是可以基於字典序進行遍歷(例如基於某個前綴進行遍歷等),後續的編碼,機制基本是基於字典序的特性進行設計

爲了可以更好地基於字典序排列的搜索特性下對數據進行讀寫,對於複雜的數據結構,我們會使用另外的空間去存放其中的數據(例如 SET 中的 member,HASH 中的 field)。而對於簡單的數據結構(類似 STRING),則可以直接存放到 key 對應的 value 中。

爲此,我們在編碼設計上,會分爲 metaKey 和 dataKey。metaKey 是基於用戶直接訪問的 key 進行編碼,是編碼設計中直接對外的一層;dataKey 則是 metaKey 的存儲指向,用來存放複雜數據結構中的具體內部數據。

另外,爲了保證訪問的數據一致性,我們基於 TiKV 的事務接口進行對 key 的訪問。

(1)編碼 & 字段

以下以編碼中的一些概念以及設定,對編碼進行簡述。

key 的編碼規則如下:

圖片

圖 2:key 編碼設計圖示

以下對字段進行說明

以下基於 SET 類型的 SADD 指令, 對編碼進行簡單演示:

圖 3: SADD 指令的編碼設計指令圖示

  1. 基於 userKey, 通過 metaKey 的拼接方式, 拼接 metaKey 並且訪問

  2. 訪問 metaKey 獲取 value 中的

  3. 基於 value 中的 uuid, 生成需要的 dataKey

  4. 寫入生成的 dataKey

(2)編碼實戰

編碼實戰中,會以 SET 類型的實現細節作爲例子,描述磁盤 KV 在實戰中的編碼細節。

在這之前,需要對 metaKey 的部分實現細節進行了解

(3)metaKey 存儲細節

所有的 metaKey 中都會存儲下列數據。

圖片

圖 4:metaKey 編碼設計圖示

  1. **uuid:**每一個 metaKey 都會有一個對應的 uuid,表示這個 key 的唯一身份。

  2. **create_time:**保存該元數據的創建時間

  3. **update_time: **保存該元數據的最近更新時間

  4. **expire_time: **保存過期時間

  5. **data_type: **保存該元數據對應的數據類型,例如 SET,HASH,LIST,ZSET 等等。

  6. **encode_type: **保存該數據類型的編碼方式

(4)SET 實現細節

基於 metaKey 的存儲內容,以下基於 SET 類型的數據結構進行講解。

SET 類型的 dataKey 的編碼規則如下:

因此,SET 的 dataKey 編碼如下:

圖 5:SET 數據結構 dataKey 編碼設計圖示

以下把用戶可以訪問到的 key 稱爲 user-key。集合中的元素使用 member1,member2 等標註。

這裏,可以梳理出訪問邏輯如下:

圖片

圖 6:SET 數據結構訪問流程圖示

簡述上圖的訪問邏輯:

  1. 基於 user-key 拼接出 metaKey,讀取 metaKey 的 value 中的 uuid。

  2. 基於 uuid 拼接出 dataKey,基於 TiKV 的字典序遍歷機制獲取 uuid 下的所有 member。

1.1.3 過期 & GC 設計

對標 Redis,目前在 user-key 層面滿足過期的需求。

因爲存在過期的數據,Redis 基於過期的 hash 進行保存。但是如果磁盤 KV 在一個 namespace 下使用一個 value 存放過期的數據,顯然在 EXPIRE 等指令下存在性能問題。因此,這裏會有獨立的編碼支持過期機制。

鑑於過期的數據可能無法及時刪除(例如 SET 中的元素),對於這類型的數據需要一種 GC 的機制,把數據完全清空。

(1)編碼設計

針對過期以及 GC(後續會在機制中詳細說),需要額外的編碼機制,方便過期和 GC 機制的查找,處理。

爲了可以方便地找到過期的 key(下稱 expireKey),基於字典序機制,優先把過期時間的位置排到前面,方便可以更快地得到 expireKey。

編碼格式如下:

圖片

圖 7:expireKey 編碼設計圖示

其中:

目前除了 STRING 類型,其他的類型因爲如果在一次過期操作中把所有的元素都刪除,可能會存在問題:如果一個 user-key 下面的元素較多,過期進度較慢,這樣 metaKey 可能會長期存在,佔用空間更大。

因此使用一個 GC 的 key(下稱 gcKey)空間,安排其他線程進行掃描和清空。

編碼格式如下:

圖片

圖 8:gcKey 編碼設計圖示

(2)機制描述

基於前面的編碼,可以對 Tula 內部的過期和 GC 機制進行簡述。

因爲過期和 GC 都是基於事務接口,爲了減少衝突,Tula 的 leader 會進行一些後臺的任務進行過期和 GC。

因爲前期已經對過期的 user-key 進行了 slot 分開,expireKey 天然可以基於併發的線程進行處理,提高效率。

圖 9:過期機制處理流程圖示

簡述上圖的過期機制:

  1. 拉起各個過期作業協程,不同的協程基於分配的 slot,拼接協程下的 expire-key-prefix,掃描 expireKey

  2. 掃描 expireKey,解析得到 user-key

  3. 基於 user-key 拼接得到 metaKey,訪問 metaKey 的 value,得到 uuid

  4. 根據 uuid,添加 gcKey

  5. 添加 gcKey 成功後,刪除 metaKey

就目前來說,過期速度較快,而且 key 的量級也不至於讓磁盤 KV 存在容量等過大負擔,基於 hash 的過期機制目前表現良好。

目前的 GC 機制比較落後:基於當前 Tula 的 namespace 的 GC 前綴(gc-key-prefix),基於 uuid 進行遍歷,並且刪除對應的 dataKey。

圖 10:GC 機制處理流程圖示

簡述上圖的 GC 機制:

  1. 拉起一個 GC 的協程,掃描 gcKey 空間

  2. 解析掃描到的 gcKey,可以獲得需要 GC 的 uuid

  3. 基於 uuid,在 dataKey 的空間中基於字典序,刪除對應 uuid 下的所有 dataKey

因此,GC 本來就是在 expire 之後,會存在一定的滯後性。

並且,當前的 GC 任務只能單線程操作,目前來說很容易造成 GC 的遲滯。

1.2 問題描述

1.2.1 問題現象

業務側多次反饋,表示窗口數據(定期刷入重複過期數據)存在的時候,磁盤 KV 佔用的空間特別大。

我們使用工具單獨掃描對應的 Tula 配置 namespace 下的 GC 數據結合,發現確實存在較多的 GC 數據,包括 gcKey,以及對應的 dataKey 也需要及時進行刪除。

1.2.2 成因分析

現網的 GC 過程速度比不上過期的速度。往往 expireKey 都已經沒了,但是 gcKey 很多,並且堆積。

這裏的問題點在於:前期的設計中,gcKey 的編碼並沒有像 expireKey 那樣提前進行了 hash 的操作,全部都是 uuid。

如果有一個類似的 slot 字段可以讓 GC 可以使用多個協程進行併發訪問,可以更加高效地推進 GC 的進度,從而達到滿足優化 GC 速度的目的,窗口數據的場景可以得到較好的處理。

下面結合兩個機制的優劣,分析存在 GC 堆積的原因。

圖片

圖 11:GC 堆積成因圖示

簡單來說,上圖的流程中:

  1. 過期的掃描速度以及處理速度很快,expireKey 很快及時的被清理並且添加到 gcKey 中

  2. GC 速度很慢,添加的 gcKey 無法及時處理和清空

從上圖分析可以知道:如果窗口數據的寫入完全超過的 GC 的速度的話,必然導致 GC 的數據不斷堆積,最後導致所有磁盤 KV 的存儲容量不斷上漲。

二、優化

2.1 目標

分析了原始的 GC 機制之後,對於 GC 存在滯後的情況,必然需要進行優化。

如何加速 GC 成爲磁盤 KV 針對窗口數據場景下的強需求。

但是,畢竟 TiKV 集羣的性能是有上限的,在進行 GC 的過程也應該照顧好業務請求的表現。

這裏就有了優化的基本目標:在不影響業務的正常使用前提下,對儘量減少 GC 數據堆積,加速 GC 流程。

2.2. 實踐

2.2.1 階段 1

在第一階段,其實並沒有想到需要對 GC 這個流程進行較大的變動,看可不可以從當前的 GC 流程中進行一些簡單調整,提升 GC 的性能。

GC 的流程相對簡單:

圖 12:GC 流程圖示

可以看到,如果存在 gcKey,會觸發一個批次的刪除 gcKey 和 dataKey 的流程。

最初設計存在 sleep 以及批次的原因在於減少 GC 對 TiKV 的影響,降低對現網的影響。

因此這裏可以調整的範圍比較有限:按照批次進行控制,或者縮短批次刪除之間的時間間隔。

縮短 sleep 時間(甚至縮短到 0,去掉 sleep 過程),或者提高單個批次上限。

但是這裏原生 sleep 時間並不長,而且就算提高批次個數,畢竟單線程,提高並沒有太大。

原生 GC 流程可變動的範圍比較有限,必須打破這種侷限纔可以對 GC 的速度得以更好的優化。

2.2.2 階段 2

第一階段過後,發現原有機制確實侷限比較大,如果需要真的把 GC 進行加速,最好的辦法是在原有的機制上看有沒有辦法類似 expireKey 一樣給出併發的思路,可以和過期一樣在質上提速。

但是當前現網已經不少集羣在使用磁盤 KV 集羣,併發提速必須和現網存量 key 設計一致前提下進行調整,解決現網存量的 GC 問題。

如果有一種可能,更改 GC 的 key 編碼規則,類似模擬過期 key 的機制,添加 slot 位置,應該可以原生滿足這種多協程併發進行 GC 的情況。

但是基於當前編碼方式,有沒有其他辦法可以較好地把 GC key 分散開來?

把上述問題作爲階段 2 的分析切入點,再對當前的 GC key 進行分析:

圖片

圖 13:gcKey 編碼設計圖示

考慮其中的各個字段:

分析下來,也只有 uuid 在整個 gcKey 的編碼中是變化的。

正因爲 uuid 的分佈應該是足夠的離散,此處提出一種比較大膽的想法:基於 uuid 的前若干位當作 hash slot,多個協程可以基於不同的前綴進行併發訪問

因爲 uuid 是一個 128bit 長度(8 個 byte)的內容,如果拿出前面的 8 個 bit(1 個 byte),可以映射到對應的 256 個 slot。

基於上述分析,uuid 的前一個 byte 作爲 hash slot 的標記,這樣,GC 流程變成:

圖 14:基於 uuid 劃分 GC 機制圖示

簡單描述下階段 2 的 GC 流程:

  1. GC 任務使用協程,分成 256 個任務

  2. 每一個任務基於前綴掃描的時候,從之前掃描到 dbid 改成後續補充一個 byte,每個協程被分配不同的前綴,進行各自的任務執行

  3. GC 任務執行邏輯和之前單線程邏輯保持不變,處理 gcKey 以及 dataKey。

這樣,基於 uuid 的離散,GC 的任務可以拆散成併發協程進行處理。

這樣的優點不容置疑,可以較好地進行併發處理,提高 GC 的速度。

基於併發的操作,GC 的耗時可以縮短超過一半。後續會有同樣條件下的數據對比。

階段 2 確實帶來一些突破:再保留原有 gcKey 設計的前提下,基於拆解 uuid 的方法使得 GC 的速度有質的提高。

但是這樣會帶來問題:對於 dataKey 較多(可以理解爲一個 HASH,或者一個 SET 的元素較多)的時候,刪除操作可能對 TiKV 的性能帶來影響。這樣帶來的副作用是:如果併發強度很高地進行 GC,因爲 TiKV 集羣寫入(無論寫入還是刪除)性能是一定的,這樣是不是可能導致業務的正常寫入可能帶來了影響?

如何可以做到兼顧磁盤 KV 日常的寫入和 GC?這成了下一個要考慮的問題。

2.2.3 階段 3

階段 2 之後,GC 的速度是得到了較大的提升,但是在測試過程中發現,如果在過程中進行寫入,寫入的性能會大幅度下降。如果因爲 GC 的性能問題忽視了現網的業務正常寫入,顯然不符合線上業務的訴求。

磁盤 KV 的 GC 還需要一種能力,可以調節 GC。

如果基於階段 2,有辦法可以在業務低峯期的時候進行更多的 GC,高峯期的時候進行讓路,也許會是個比較好的方法。

基於上面的想法,我們需要在 Tula 層面可以比較直接地知道當前磁盤 KV 的性能表現到底到怎樣的層面,當前是負荷較低還是較高,應該用怎樣的指標去衡量當前磁盤 KV 的性能?

此處我們進行過以下的一些摸索:

暫時發現 TiKV 的接口性能表現調整效果較好,因爲基於磁盤負載不能顯式反饋到 Tula 的時延表現,基於 Tula 的時延表現應該需要蒐集所有的 Tula 時延進行調整(對於同一個 TiKV 集羣接入多個不同的 Tula 集羣有潛在影響),基於 TiKV 的接口性能表現調整可以比較客觀地得到 Tula 的性能表現反饋。

在階段 1 中,有兩個影響 GC 性能的參數:

加上階段 2 併發的話,會有三個可控維度,控制 GC 的速度。

調整後的 GC 流程如下:

圖片

圖 15:自適應 GC 機制圖示

階段 3 對 GC 添加自適應機制,簡述如下:

①開啓協程,蒐集 TiKV 節點負載

②開啓協程,進行 GC

基於監控表現,可以明顯看到,GC 不會一直強制佔據 TiKV 的所有性能。當 Tula 存在正常寫入的時候,GC 的參數會響應調整,保證現網寫入的時延。

階段3之後,可以保證寫入和但是從 TiKV 的監控上看,有時候 GC 並沒有完全把 TiKV 的性能打滿。

是否有更加高效的 GC 機制,可以繼續提高磁盤 KV 的 GC 性能?

2.2.4 階段 4

基於階段 3 繼續嘗試找到 GC 性能更高的 GC 方式。

基於階段 3 的優化,目前基於單個節點的 Tula 應該可以達到一個可以較高強度的 GC,並且可以給現網讓路的一種情況。

但是,實際測試的時候發現,基於單個節點的刪除,速度應該還有提升空間(從 TiKV 的磁盤 IO 可以發現,並沒有佔滿)。

這裏的影響因素很多,例如我們發現 client-go 側存在獲取 tso 慢的一些報錯。可能是使用客戶端不當等原因造成。

但是之前都是基於單個 Tula 節點進行處理。既然每個 Tula 都是模擬了 Redis 的集羣模式,被分配了 slot 區間去處理請求。這裏是不是可以借鑑分片管理數據的模式,在 GC 的過程直接讓每個 Tula 管理對應分片的 GC 數據?

這裏先 review 一次優化階段 2 的解決方式:基於 uuid 的第一個 byte,劃分成 256 個區間。leader Tula 進行處理的時候基於 256 個區間。

反觀一個 Tula 模擬的分片範圍是 16384(0-16383),而一個 byte 可以表示 256(0-255)的範圍。

如果使用 2 個 byte,可以得到 65536(0-65535)的範圍。

這樣,如果一個 Tula 可以基於自己的分片範圍,映射到 GC 的範圍,基於 Tula 的 Redis 集羣模擬分片分佈去做基於 Tula 節點的 GC 分片是可行的。

假如某個 Tula 的分片是從 startSlot 到 endSlot(範圍:0-16383),只要經過簡單的映射:

基於這樣的映射,可以直接把 Tula 的 GC 進行分配,而且基本在優化階段 2 中無縫銜接。

基於分析得出的機制如下:

圖 16:多 Tula 節點 GC 機制圖示

可以簡單地描述優化之後的 GC 流程:

① 基於當前拓撲劃分當前 Tula 節點的 startHash 與 endHash

② 基於步驟 1 的 startHash 與 endHash,Tula 分配協程進行 GC,和階段 2 基本一致:

基於節點分開之後,可以滿足在每個節點併發地前提下,各個節點不相干地進行 GC。

基於併發的操作,GC 的耗時可以在階段 2 的基礎上繼續縮短。後續會有同樣條件下的數據對比。

基於節點進行併發,可以更加提高 GC 的效率。

但是我們在這個過程中也發現,client-go 的使用上可能存在不當的情況,也許調整 client-go 的使用後可以獲得更高的 GC 性能。

三、優化結果對比

我們基於一個寫入 500W 的 SET 作爲寫入數據。其中每一個 SET 都有一個元素,元素大小是 4K。

因爲階段 2 和階段 4 的提升較大,性能基於這兩個進行對比:

圖片

表 1:各階段 GC 耗時對照表

可以比較明顯地看出:

  1. 階段 2 之後的 GC 時延明顯縮減

  2. 階段 4 之後的 GC 時延可以隨着節點數的增長存在部分縮減

四、後續計劃

階段 4 之後,我們發現 Tula 的單節點性能應該有提升空間。我們會從以下方面進行入手:

  1. 補充更多的監控項目,讓 Tula 更加可視,觀察 client-go 的使用情況。

  2. 基於上述調整跟進 client-go 在不同場景下的使用情況,嘗試找出 client-go 在使用上的瓶頸。

  3. 嘗試調整 client-go 的使用方式,在 Tula 層面提高從指令執行,到 GC,過期的性能。

五、總結

回顧我們從原來的單線程 GC,到基於編碼機制做到了多線程 GC,到爲了減少現網寫入性能影響,做到了自適應 GC,再到爲了提升 GC 性能,進行多節點 GC。

GC 的性能提升階段依次經歷了以下過程:

  1. 單進程單協程

  2. 單進程多協程

  3. 多進程多協程

突破點主要在於進入階段 2(單進程多協程)階段,設計上的困難主要來源於:已經存在存量數據,我們需要兼顧存量數據的數據分佈情況進行設計,這裏我們必須在考慮存量的 gcKey 存在的前提下,原版 gcKey 的編碼設計與基於字典序的遍歷機制對改造造成的約束。

但是這裏基於原有的設計,還是有空間進行一些二次設計,把原有的問題進行調優。

這個過程中,我們認爲有幾點比較關鍵:

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