面向存算分離架構的混合粒度緩存策略

梅文娟, 蔡 鵬

（華東師范大學 數據科學與工程學院, 上海 200062）

0 引 言

隨著信息時代數據量的增加, 數據庫管理系統正逐漸從本地部署轉向云端[1-5], 以實現更高的彈性和更低的成本. 現代云數據庫采用存儲和計算分離(存算分離)架構, 將計算和存儲分離到通過網絡連接的不同服務器層中, 簡化了資源配置并實現了獨立的資源擴展. 存儲層提供可靠的持久化存儲服務,如Amazon Web Service (AWS) 簡單云存儲 (Simple Storage Service, S3)[6]、Azure Blob 存儲[7]、阿里云對象存儲服務(object storage service, OSS)[8]和Google Cloud Storage[9]等對象存儲, 以及HDFS[10](hadoop distributed file system)類的分布式文件系統是當下云數據庫存儲層的可選方案. 計算層則由多個計算節點組成, 負責數據庫的解析、查詢、計算等過程. 然而, 面對存算分離架構, 研究者必須重新考慮分布式數據庫管理系統的一個基本原則: 將計算移動到數據而不是將數據移動到計算. 傳統的Share-Nothing 體現了這一原則, 并將數據存儲在本地磁盤上; 而當前的存算分離架構中的網絡通常具有比本地磁盤更低的帶寬, 從而可能成為性能瓶頸. 緩存是減輕網絡瓶頸的一個重要的方向, 其主要思想是將熱數據保留在計算層, 從而減少計算層和存儲層之間傳輸的數據量, 如Snowflake[11]和帶有 Alluxio 緩存服務的Presto[12]、Redshift[13]層在 Redshift Spectrum[14]中用戶可控制內容的緩存.

作為存儲層的分布式文件系統, 如HDFS[10]; 或是對象存儲, 如Amazon 的S3[6], 其針對小文件的讀寫效率都很低. 由于文件系統元數據的管理和開銷, 處理大量小文件是分布式文件系統面臨的挑戰,這也被描述為小文件問題[15]. 在基于MergeTree 的數據庫, 如 ClickHouse 中, 會產生很多的小文件;ClickHouse 在插入、刪除和數據合并的時候都會存在大量讀寫或修改小文件的操作. 這些小文件及小文件操作對存儲層非常不友好, 會大大降低系統的性能.

MergeTree 引擎在合并數據時, 會將多個小文件合并成一個大文件, 由于數據的分布情況不均勻,導致某些分區的文件數過多, 從而產生大量的小文件. S3 對小文件修改和訪問的性能并不好.ClickHouse 本身已經實現了從遠程存儲端到S3 的緩存, 并在系統初始化時定義了緩存段的大小, 但是其固定緩存段大小時, 并沒有考慮緩存粒度與內存是否適配; 除此之外, 緩存段大小的固定還會導致緩存空間的浪費. 因為緩沖區緩存某一段連續的數據往往是因為其中的一小部分為熱數據, 而剩下的大部分緩沖區的緩存空間被大量不常用的冷數據占用, 故不能有效地達到提高數據訪問效率的目的.

本文提出了一種混合粒度緩存管理方案, 簡稱為HG-Buffer (hybrid granularity buffer). 其關鍵思想是將SSD 緩沖區組織成對象(object)和塊(block)這兩個粒度的緩存: 對象是數據存儲到對象存儲中的粒度; 塊則是數據在本地磁盤上存儲的粒度. 同時本文增了一個新度量—熱塊率, 來自適應地選擇數據緩存的位置, 即根據該度量量化頁面中熱塊的比率, 從而判斷將數據是存儲在基于對象的緩沖區(對象緩沖區, Object Buffer), 還是存儲在基于塊的緩沖區(塊緩沖區, Block Buffer). 綜上所述,本文有以下幾方面的貢獻.

(1) HG-Buffe 使用2 個基于對象的緩沖區和一個基于塊的緩沖區來組織緩沖池, 可以適應訪問模式, 并根據熱塊率來選擇Object Buffer 或 Block Buffer. 基于此機制, HG-Buffer 基于有限的SSD 空間可容納更多的熱數據, 從而提高了命中率和整體的性能.

(2) Object Buffer 里的熱塊被移動到Block Buffer 之后, 會失去局部性的優點, 數據訪問的速度亦會降低. 與此同時, 如果一個被驅逐的對象是一個熱塊占比很高的對象, 將其中的熱塊移動到Block Buffer 會有大量的遷移成本. 為了解決這個問題, HG-Buffer 引入了一個熱塊率的度量來量化一個對象的熱塊占比, 從而決定數據是存儲在Block Buffer 還是存儲在Object Buffer.

(3) 給出了HG-Buffer 的詳細架構和詳細算法, 包括讀操作、刪除操作、更新操作的相關算法.

(4) 對幾種不同的工作負載進行了實驗, 以評估 HG-Buffer 的性能, 并將其與SSD 直接二級緩存、SSD 擴展內存等傳統緩存方案進行了對比. 結果表明, HG-Buffer 可以顯著提高數據讀寫的效率.此外, 多變的SSD 緩存空間大小實驗亦表明了 HG-Buffer 的魯棒性.

1 相關工作

1.1 存算分離背景以及緩存方法

隨著互聯網的發展, 數據量不斷增加, 數據分析的要求也日益增加. 與此同時, 網絡傳輸的速度也在不斷提高. 為了有更好的擴展性和穩定性, 數據庫管理系統供應商正在向云端轉移. 云端數據庫系統受益于彈性、獨立擴展計算和存儲的能力、增強的吞吐量和規模經濟等特性[3], 將架構分成存儲層和計算層: 計算層是一個個無狀態的節點, 其多個節點構成一個計算組, 系統通過對計算組中節點的增減來實現計算層的擴縮容; 對于存儲層而言, 云端數據庫系統越來越多地采用AWS 簡單云存儲(S3)[6,16]、Azure Blob 存儲[7]、阿里云對象存儲服務(OSS)[8]和谷歌云存儲[9]等對象存儲作為其底層存儲解決方案. 雖然云端數據庫系統也可以采用無共享架構, 但許多云原生數據庫選擇分解計算層和存儲層, 這帶來了成本更低、容錯更簡單和硬件利用率更高的好處. 許多云原生數據庫最近都遵循存算分離架構進行開發, 包括SparkSQL[17]、Aurora[18-19]、Redshift Spectrum[14]、Athena[20]、Presto[12]、Hive[3]、Snowflake[11]和Vertica EON[21-22]模式. 雖然存儲計算分離架構聽起來與共享磁盤架構相似, 但它們實際上存在顯著差異. 在共享磁盤架構中, 磁盤通常是集中的, 因此很難橫向擴展系統. 相比之下, 存算分離架構像計算層一樣水平擴展存儲層, 且還在存儲層提供非平凡的計算, 而磁盤只是共享磁盤架構中的被動存儲設備.

由于較高的網絡延遲和較低帶寬遠程存儲, 在計算節點緩存數據是存算分離緩存系統中不可或缺的一步. 雖然本地存儲是有限的, 但是它的訪問速度比共享存儲更快, 通過熱數據保存在計算層本地存儲如SSD 中, 可以加速數據查詢訪問的速度. 典型的例子包括Alluxio[12]分析加速器、 Databricks Delta 緩存[1], 以及Snowflake 緩存層[11].

Alluxio 提供分布式共享緩存服務, 其分層存儲可以同時利用內存和磁盤 (SSD/HDD (hard disk drive)), 通過自動優化數據放置策略, 來提高內存和磁盤的性能和可靠性. 與此同時, 它還維護了緩存一致性. Alluxio 的緩存對用戶是透明的, 它通過將數據存儲在計算節點和遠程存儲的同一位置進行緩存數據的映射管理. Alluxio 的熱數據可以保存多個副本, 對多次訪問的熱數據可以并行I/O(input/output), 從而提高訪問效率, 其副本的數量由集群活動動態決定.

Snowflake[11]對數據文件名進行一致性哈希, 將客戶的輸入文件集分配給節點, 一個文件只能緩存在其散列的節點上. Snowflake 使用傳統的兩層機制, 每個節點實現一個本地LRU (least recently used)策略用于從本地內存到本地SSD 的逐出, 以及一個獨立的LRU 策略用于從本地SSD 到遠程持久數據存儲的逐出. Snowflake 緩存的數據包括計算結果和可查詢的數據, 其中計算結果的緩存包括過去24 h 內執行的每個查詢的結果, 這些查詢結果可跨虛擬計算組進行使用. 因此, 在數據未被修改的前提下, 返回給一個用戶的查詢結果可用于系統上執行相同查詢的任何其他用戶. 而SQL 查詢使用的緩存數據則是在每次查詢時, 從遠程存儲中檢索數據, 并將其緩存在SSD 和內存中.

Databricks 的 I/O[1]緩存通過使用中間數據格式, 在節點的本地存儲中創建遠程文件的副本來加速數據讀取. 每當必須從遠程位置獲取文件時, 數據都會自動緩存到計算節點, 然后在計算節點執行相同數據的連續讀取, 從而顯著提高讀取速度. Databricks 的 delta 自動維護文件的一致性, 檢測底層數據文件的更改并緩存.

Crystal[23]是微軟提出的緩存組件, 它認為不同的數據庫管理系統都有自己的緩存實現和不同的數據格式, 在實現上具有非常大的重復性. 為了解決這個問題, Crystal 按照大多數數據庫系統都支持的API (application programming interface), 為各類系統實現了一個公共的緩存服務, 不僅支持熱數據的緩存, 還會緩存查詢的中間結果, 可以滿足大多數系統的要求.

除了在計算節點緩存熱數據, 利用存儲層的計算能力將部分計算下推也是緩解存算分離架構下網絡瓶頸的方式之一. FlexPushdownDB[24]將計算下推和緩存相結合, 在查詢執行的階段, 對執行計劃中的算子進行評估, 以降低查詢的響應延遲為目標, 并采用加權LFU (least frequently used)的方式來決定緩存哪些數據.

1.2 ClickHouse 和S3 的存算分離方案

ClickHouse[25]是一個OLAP (online analytical processing)系統列存數據庫, 可以快速地對數據進行實時或批量的分析. 其最典型的特征是MergeTree 引擎. MergeTree 引擎是ClickHouse 內部存儲引擎之一, 專門用于處理大規模數據的插入、更新和查詢. 它基于列式存儲和合并樹 (MergeTree) 的概念, 提供了高性能和可擴展的數據處理能力. 其主要特點如下.

(1) 列式存儲結構: 將同一列的數據存儲在一起, 可以大大提高分析查詢中的效率, 使ClickHouse適用于大規模的聚合查詢和復雜的分析任務.

(2) 分區與排序: 將數據按照指定的分區鍵和排序鍵進行劃分和排序. 分區鍵用于將數據水平分割成多個獨立的分區; 排序鍵用于在每個分區內按特定順序存儲數據. 這種方式可以提高查詢性能和過濾效果.

(3) 合并: MergeTree 引擎使用合并操作來優化數據的存儲和查詢, 將相鄰的分區按照一定的策略進行合并, 從而減少了分區數量, 提高了查詢性能. 合并操作是通過后臺線程異步執行的, 不會對正在進行的查詢產生影響.

(4) 支持數據更新: MergeTree 引擎支持數據的插入、更新和刪除等操作. 因此, 在MergeTree 引擎中, 數據的更新并不會直接修改原始數據, 而是通過增加新的數據版本來處理更新操作. 這種增量數據更新的方式可以有效地處理大規模數據的更新需求.

ClickHouse 和S3 的存算分離方案是一種數據存儲和計算分離的架構, 旨在提高大規模數據處理的性能和效率. 這種方案基于ClickHouse 的分布式計算能力和S3 的高可靠性和低成本存儲. 在這種架構下, 數據首先在S3 中進行持久性存儲; 當系統需要這些數據進行查詢或分析時, ClickHouse 通過與S3 進行交互, 將數據加載到ClickHouse 集群中進行計算. 具體為, ClickHouse 集群通過連接到S3 的接口, 將需要處理的數據從S3 中讀取到內存中進行計算. 首先, 由于數據存儲和計算被分離開來, 因此, 可以在不影響存儲的情況下, 靈活地對計算集群進行擴展或縮小; 其次, S3 提供了高可靠性和低成本的存儲, 因此, 可以節約存儲成本; 最后, 結合ClickHouse 的高性能和分布式計算能力, 可以快速地對大規模數據進行查詢和分析.

MergeTree 引擎在合并數據時, 會將多個小文件合并成一個大文件. 但是在某些情況下, 由于數據的分布不均勻, 會導致某些分區的文件數過多, 從而產生大量的小文件. ClickHouse 和S3 的存算分離方案下, 數據都存放在S3 中, 但是S3 對小文件的修改和訪問的性能并不友好, 所以S3 作為對象存儲訪問的性能具有很大的局限性. 圖1 展現了當前ClickHouse 中MergeTree 引擎與S3 結合的存算方案的數據映射關系: 每一次插入數據, MergeTree 引擎會生成一個文件, 這個文件被稱為part 文件; 每一個part 文件中的數據文件都被存儲到了S3; 每個數據文件包含多個以塊(block)為單位的數據,ClickHouse 存儲數據文件到S3. 磁盤中的數據文件中不再存放數據本身, 而是存放其與S3 的映射關系, 如圖1 中的part 數據內容. 其中, ttdfdsfdd 字符串就是當前數據文件對應的S3 的文件的鍵, 從上往下第一行的數字(32)表示當前元數據的版本, 第二行數字代表數據文件所包含的對象文件的數量和總大小(1, 30), 第三行及以下的每一行數字代表每個對象文件的大小以及對象文件的鍵. 當一個ClickHouse 需要某一個塊數據的時候, ClickHouse 首先通過訪問S3 從而獲取到對應的數據文件, 然后將數據文件緩存到本地磁盤, 再從數據文件中獲取對應的塊數據. 整個過程增加了將數據文件傳輸到計算節點的網絡開銷, 同時本地有限的SSD 緩存空間也被不需要的數據文件浪費.

圖1 ClickHouse 和S3 的數據映射關系Fig. 1 Mapping relationship between ClickHouse and S3 data

ClickHouse 可以設置本地文件系統上的目錄來為遠程文件系統保存指定大小的緩存, 如cache_path/012/0123456789abcdef0123456789abcdef/111111_last. 其中, cache_path 是指緩存在本地系統上的位置; 0123456789abcdef0123456789abcdef 是遠程文件系統上文件路徑; 012 是文件路徑的哈希值的前3 個十六進制字母; 111111 是文件中緩存段的起始偏移量 (十進制); last 用于標記緩存段,是系統讀取的目標文件中的結束. ClickHouse 將整個條目作為一個緩存粒度, 緩存管理器使用簡單的LRU 進行熱數據的識別和替換. 因此, 大的緩存段被緩存并作為一個整體被逐出. 簡而言之, 雖然ClickHouse 本身已經實現了遠程存儲端到S3 的緩存, 但是ClickHouse 也存在一些問題: ClickHouse會在系統初始化的時候定義緩存段的大小, 且這個大小是固定的, 并沒有考慮緩存粒度與內存是否適配的問題; ClickHouse 本身基于MergeTree 引擎, 其存儲層的文件在不斷地修改和合并, 文件大小多變, 所以固定大小的緩存粒度會造成其性能的下降; 除此之外, 因需要某一部分的數據, 而緩存一整個緩存段數據, 也會導致緩存空間的浪費.

為了避免上述問題的產生, 本文將小的塊文件進行合并, 并將多個part 文件等數據合并為一個文件存儲到S3, 以減輕小文件讀寫的壓力; 同時提出了混合緩存策略, 將緩存的粒度分成塊粒度和S3 上的對象粒度, 以減少本地緩存空間的浪費, 并降低多余的網絡開銷.

2 HG-Buffer 架構

在存算分離的架構下, 對象存儲對小文件的讀寫效率是很大的性能瓶頸. ClickHouse 在寫入的時候會產生大量的小文件, 從而導致了系統性能的降低. 如果按照對象存儲適用的粒度, 將本地的小文件合并成大文件上傳到對象存儲, 同樣會產生另外的問題: 合并后的大文件中, 有的數據是熱數據, 有的數據是冷數據, 冷/熱數據在大文件中的占比也都不盡相同; 如果大文件中的熱數據占比高, 將大文件緩存到節點中是有效的; 當大文件中的熱數據占比較低的時候, 大文件中的冷數據就占用了有限的緩存空間, 無助于提高查詢性能; 但是如果不緩存熱數據占比較低的大文件, 又因其存在少量的熱數據, 這個大文件會被頻繁訪問, 這個時候就會產生巨大的網絡開銷.

為了克服上述問題, 本文提出了HG-Buffer. HG-Buffer 的想法和貢獻可以概括為以下幾點.

(1) HG-Buffer 使用一個塊緩沖區(Block Buffer)和2 個對象緩沖區(Object Buffer)來組織整個SSD 緩沖區空間. 如果Object Buffer 的對象將要被驅逐出去, Object Buffer 中的熱塊就會被移動到Block Buffer, 此時Object Buffer 的空間就得以釋放, 為后續的請求提供更多的緩沖空間. 有了這種機制, HG-Buffer 基于有限的SSD 空間可容納更多的熱數據, 從而提高命中率和整體的性能.

(2) Object Buffer 的熱塊被移動到Block Buffer 之后, 會失去局部性的優點, 數據訪問的速度會降低. 如果一個將被驅逐的對象是一個熱塊率高的對象, 將其中的熱塊移動到Block Buffer 不僅會使其失去局部性的優點, 還會有大量的遷移成本. 因此, HG-Buffer 引入了一個熱塊率的概念來量化一個對象的熱塊占比.

(3) HG-Buffer 的后臺線程會執行塊數據和對象數據在Block Buffer 和Object Buffer 之間的遷移.實驗證明, HG-Buffer 的效率比普通的二級緩存策略更好, HG-Buffer 在不同的SSD 空間下具有魯棒性.

圖2 顯示了HG-Buffer 的總體架構, 緩沖區部分由3 個子緩沖區組成: Normal Buffer 和Object Buffer 是對象粒度的緩沖區; Block Buffer 是基于塊粒度的緩沖區. 因為計算節點和對象存儲之間的數據交換必須以對象(object)為單位, 所以使用Normal Buffer 緩存從對象存儲中讀取的對象數據.Object Buffer 用于存儲熱塊率高的對象數據, 熱塊率高的對象數據中包含了大量的熱塊, 所以它們被整體緩存到Object Buffe. Block Buffer 存儲來自Normal Buffer 中被驅逐的對象數據中的熱塊. HGBuffer 中的熱塊率是指對象數據中熱點塊的比例: 一方面, 更高的熱塊率意味著一個對象中包含更多的熱塊, 此時對象中的數據更適合由對象粒度緩沖區管理器管理; 另一方面, 較低的熱塊率意味著緩存整個對象數據沒有意義, 將熱點塊單獨取出并使用塊粒度緩沖區管理熱點塊的方式會使訪問效率更高.

圖2 HG-Buffer 的架構Fig. 2 Architecture of HG-Buffer

當查詢引擎請求數據時, 緩沖區管理器首先在內存緩沖區緩存中查找數據, 如果未找到該塊數據,則在通過數據文件中的映射關系到SSD 緩存中查找該塊; 如果仍未查找到該塊數據, 則從對象存儲中檢索它 (具有更高的延遲), 并將它緩存到計算節點中的Normal Buffer. 隨著數據老化, 按照LRU 算法, 數據最終從Normal Buffer 緩存中逐出, 并將根據熱塊率存儲到Block Buffer 或Object Buffer 中.在Block Buffer 和Object Buffer 中, 數據的更新算法同樣是按照LRU 算法進行的. 當數據完全從SSD 緩存中被逐出, 這些被逐出的數據會被簡單地丟棄. 插入的新數據或是更新的數據總是使用新的對象鍵寫出到對象存儲, 然后更新本地數據與新塊的映射關系.

HG-Buffer 將與其數據相關的元數據信息放入內存. 元數據信息是指與塊相關的一些信息, 包含塊的大小、塊在云存儲上的ID、塊在SSD 緩存中的位置, 以及塊是否被緩存等信息. HG-Buffer 中塊的數量很多, 無法將3 個緩沖區中所有的塊元數據信息都加載到內存, 塊元數據信息通常存儲在SSD 上的數據映射文件中. 為了加速查詢的效率和減少訪問磁盤(I/O)的次數, HG-Buffer 在內存中另外存儲了Block Buffer 中熱塊的元數據. 所以, Block Buffer 中的塊和塊元信息在內存中保持著一個映射關系表, 這個關系表可以表示Block Buffer 中所有的塊信息, 即塊的位置信息, 以及塊的訪問頻次信息. 存儲Block Buffer 中塊的元信息的原因有二: 一是Block Buffer 中的塊本就已失去了局部性原理的訪問優點, 如果每次還要去SSD 中獲取塊的位置信息, 然后再去SSD 中獲取塊數據, 這樣的兩次隨機I/O 會導致速度的大大下降; 二是Block Buffer 中的塊相對于Object Buffer 的塊的數量更少,Object Buffer 中對象的塊是連續的, 訪問速度更快, 所以如果存儲Block Buffer 中的塊信息, 則比存儲Object Buffer 的元數據信息的價值更高, 收益更大. 為了加快查詢塊的速度, 在內存中元數據的存儲方式是哈希表. 由于Block Buffer 內的數據量不是固定的, Block Buffere 的大小也不是固定的, 所以內存中的元數據組織方式是可擴展哈希表. 可擴展哈希表可以根據數據量的大小動態地改變哈希表的大小, 從而更高效地使用內存數據, 加快查詢速度.

3 緩沖區物理布局

混合粒度緩存層使用計算節點的SSD 作為對象存儲的緩存. 數據在S3 上的粒度和系統存取數據的粒度是不同的, 本文稱前者為對象, 后者為塊. 以一個讀操作為例, ClickHouse 收到一個查詢請求,需要訪問某個塊數據: 如果內存和計算節點SSD 中均沒有這些數據, ClickHouse 則需要從S3 上獲取該塊數據對應的對象文件, 然后將對象數據放入SSD 緩存; ClickHouse 計算節點從SSD 緩沖區中的對象中獲取需要的塊數據, 然后將這個塊數據直接放入內存, 從而完成查詢請求.

對象文件包含對象的頭信息和多個塊數據: 對象的頭信息包含一個visitBitmap 用于保存對象中每個塊的訪問信息, 即熱度信息; 每個塊都是一個壓縮數據塊, 由頭信息和壓縮數據這兩個部分組成.每個壓縮塊的體積大小控制在64 kB 左右; 頭信息固定使用9 B 表示, 具體由1 個uint8 (1 B)和2 個uint32 (4 B)整型組成, 分別代表了使用的壓縮算法類型、壓縮后的數據大小和壓縮前的數據大小. 塊的具體數據格式如圖2 所示. 每個對象文件由多個塊組成, S3 訪問文件到最佳的大小是17 MB, 所以每個對象的大小是16 MB 到20 MB. 對象文件的排列如圖3 所示, 數據文件的元信息中每一行包含了塊的基本信息, 即塊數據壓縮后的大小、每個塊的S3 鍵信息, 以及塊在對象文件中的序號.

圖3 對象和塊的數據布局關系Fig. 3 Data layout of objects and blocks

關于本地SSD 上緩沖區的組織形式, 本文有兩種選擇: 第一種是將所有緩存數據存儲在一個由HG-Buffer 內部管理的文件中, 并使用扁平文件管理的方式; 第二種是將緩存數據存儲在一個由操作系統維護的目錄結構中. 關于空間的分配, 第一種方式需要HG-Buffer 將一個文件分成多個塊, 然后管理該文件內的空間, 同時還需要兼顧文件的碎片管理; 而第二種方式只需將塊數據或對象數據映射的文件直接進行I/O, 其余部分交給操作系統管理即可. 從這點來看, 第二種方式的實現更為簡單. 所以本文采用基于目錄的方式.

HG-Buffer 的緩沖區在物理上的布局是將緩存的數據存儲在一個由操作系統維護的目錄結構中,其所包含的3 個緩沖區分別放在不同的目錄文件下. 因為數據文件的數量很大, 如果只是扁平化的目錄, 查找需要的數據會非常麻煩, 所以通過哈希(Hash)函數將數據文件變成樹形結構. 每一個存儲在對象存儲上的文件都有一個獨特的鍵, 如S3 上存儲的文件對應的鍵是隨機的字符串. 為了維護平衡的目錄樹, HG-Buffer 依賴Hash 算法從對象鍵生成路徑前綴, 也就是說, 給定對象鍵、目錄樹的最大高度以及每個目錄的最大子文件樹, 可以進行如下的計算.

設定:k為一個對象鍵 (或等效的數字串);f為確定目錄中允許的最大子目錄數, 且必須是2 的冪次方;h為目錄樹的最大高度. 具體算法如下.

(1)計算H(k) , 其中H(·) 是將對象鍵映射到 64 位無符號整數的Hash 函數.

(2)在radix-f中表示前面步驟計算的數.

(3)將radix-f表示的數的低位h位作為每一級路徑的目錄名, 這里h即是目錄樹的最大高度.

例如, 設最大子目錄數f=32,目錄樹的最大高度h=2 , 需要計算密鑰k=4611686018427387905的路徑. 假設H(k) 返回654321, 654321 的radix-32 為19-30-31-17, 獲取其最低2 位有效數字, 即31 和17, 將路徑構造為/cachelocation/31/17/4611686018427387905,頁面寫入SSD, 以及從SSD 讀回時使用相同的路徑. 如果在HG-Buffer 嘗試將對象寫入SSD 時, 路徑中的任何目錄或子目錄不存在, 則它們將基于這個規則創建目錄, 其中葉子目錄可以包含大于最大子目錄數的文件, 但中間目錄的子目錄數不能大于最大子目錄數.

Block Buffer、Object Buffer 和Normal Buffer 分別處于不同的根目錄下. Object Buffer 和Normal Buffer 都是基于對象存儲的鍵散列而成的路徑進行存儲, 而Block Buffer 除了需要對對象存儲的ID 進行散列, 還需要加上塊在對應對象文件中的位置, 從而可以唯一標識塊的位置.

4 HG-Buffer 的操作

4.1 只讀操作

分析型數據庫會有大量的查詢操作, 并且它的查詢操作往往是一次性對少數列的大量數據進行統計分析. 在分析型數據中, 只讀操作的占比非常高. 當存儲引擎收到一個查詢數據的請求時, 它首先查找訪問對應塊數據的元數據哈希映射表, 查看它們是否在Block Buffer 中, 然后再加載計算節點上的數據文件映射信息, 找到這些數據在HG-Buffer 中存在的位置. 如果該塊數據已經在緩沖區了, 那么直接訪問SSD 上HG-Buffer 中獲取的對應塊數據即可; 如果該塊數據不在SSD 上的HG-Buffer 中,則需要將訪問方式重新定向到對象存儲, 從對象存儲中獲取對應的對象數據, 然后將此對象數據放在Normal Buffer 中, 并修改SSD 中關于這些數據的映射數據信息.

在獲取了塊數據之后, 還需要修改塊的熱度信息. 每個緩沖區都記錄每個塊的訪問順序到日志信息, 在內存中累積到一定量之后落盤到SSD; 后臺遷移程序會通過日志信息驅逐對象數據或者是調整它的位置.

4.2 寫操作

數據庫中的寫操作分為3 種: 插入操作、刪除操作和更新操作. 數據庫的寫操作往往涉及緩存一致性的問題: 如果先更新緩存, 再寫入遠程的對象存儲, 可能出現數據不一致的問題; 如果先更新遠程的對象存儲, 再寫入本地的緩存, 則可能出現性能上的問題; 如果同一時間有大批的數據寫入, 這些數據將緩存中的熱數據都替換到了SSD 中, 但此時寫入的數據不是高熱度的數據, 這將導致SSD 緩存中原有的熱數據信息丟失, 后續的大量訪問在SSD 緩存中都不會命中, 導致大量的請求都重新定向到對象存儲, 造成對象存儲的讀寫壓力加大, 系統的性能整體下降.

為了規避上述問題, 本文在寫入數據時, 先增加新數據對應的元數據信息, 然后直接將數據寫入對象存儲, 最后將本地數據和對象存儲數據的映射關系記錄到元數據信息中. 如果整個過程中, 寫入對象存儲發生錯誤, 整個寫過程就會回滾.

對于插入操作, ClickHouse 插入數據時, 插入的一批數據將會產生一個單獨的part, 該part 文件包含其相關的所有塊數據元信息; 而在對象存儲中, 插入的數據會以對象為單位存入對象存儲, 當在對象存儲中寫入成功之后, 則需要將塊數據與對象存儲數據之間的映射關系更新到塊數據的元信息中.

對于刪除操作, ClickHouse 將對應的part 文件標記為刪除后, 后臺線程異步對標記的part 文件進行刪除. 對于HG-Buffer 而言, 刪除數據時, 首先刪除云存儲上的數據, 云存儲的數據刪除之后, 再刪除本地與part 相關的數據以及塊的元數據. 如果刪除的時候有查詢訪問這些數據, 由于數據在刪除之前都被標記為outdated, 即這些數據已經不能訪問了, 所以只能是查詢失敗, 則不會造成緩存不一致的問題.

對于更新操作, ClickHouse 將更新操作分成刪除操作和插入操作兩個部分. 在系統看來, 刪除操作中只要在part 被標記為outdated 之后, 這些數據就已經對系統不可見了; 然后再插入新數據, 插入的流程與上文所述的插入操作相同.

4.3 數據遷移

每個對象文件移動到SSD 上時, 每個對象中只能包含限定數目的塊數據. 按照本文所定的規格,平均每個對象數據的大小是17 MB, 每個塊數據的大小是64 kB, 則一個對象文件中最多能夠存儲272 個塊數據. 本文在對象數據頭信息中存儲了visitbitmap, 每一位都對應一個塊數據. 如果一個塊數據沒有被訪問, 那么它對應的標記是0; 如果塊已經被訪問過, 那么它對應的標識就是1. 當一個對象即將被移除的時候, 這些被訪問過的塊數據就是熱塊. 本文通過vistbitmap 中標識為1 的統計值除以整體的熱塊個數來計算熱塊率. 如果一個熱塊率超過預定閾值, 那么這個對象數據在被驅逐時, 就應該被放入Object Buffer; 反之, 則將對象數據中的熱塊取出放入Block Buffer.

HG-Buffer 的緩存分成3 個部分: Normal Buffer、Block Buffer 和Object Buffer. 當數據從共享存儲中遷移到計算節點時, 數據首先緩存在Normal Buffer; 當Normal Buffer 滿了, 則需要將數據遷移到Block Buffer 或者是Object Buffer. Block Buffer 存儲熱塊率低的塊, Object Buffer 存儲熱塊率高的塊. 雖然數據會在這3 個緩沖區之間遷移, 但是數據的元數據信息和數據的熱度信息不會因為數據的遷移而改變. 對于計算節點而言, 每一個塊信息都有一個唯一的標識, 即塊在共享存儲的鍵和在對應對象文件中的位置是唯一的. 共享存儲中, 每一個塊都存儲在一個對象中, 對象是共享存儲中存儲數據的單位, 所以每個塊的標識為對象的共享存儲鍵加上塊在對象文件中的位置. 塊的元數據信息包括塊數據在共享存儲上的標識、塊數據在HG-Buffer 緩存中的映射關系, 以及塊的大小等信息. 當發生數據遷移時, 元數據中塊在HG-Buffer 中的映射關系會改變, 其余的元信息以及元數據的位置則不會改變.

如果Normal Buffer 滿了, 則按照LRU 的緩存替換規則, 將Normal Buffer 的內容替換掉. 如果被驅逐的對象是熱塊率高于閾值的, 則將其放入Object Buffer; 反之, 則將對象中熱度高的塊數據放入Block Buffer; 如果Object Buffer 滿了, 則需要將對象中的數據逐出. 上文已介紹過, 在數據更新的時候, 會刪除緩存區和共享存儲中的塊, 再插入新的塊, 臟數據回寫的問題就不存在了. 所以Object Buffer 中不會有更新的塊數據, 逐出的對象數據會直接被拋棄. 同理, Block Buffer 被逐出的數據也是這樣的處理.

4.4 熱塊率

熱塊率是決定一個對象數據是否留在緩沖區的重要指標, 其定義是熱塊的總數據量除以對象的數據量, 即熱塊在對象中的占比. 關于設置熱塊率的大小, 本文使用緩沖區的大小與數據庫總大小的比值為熱塊率的閾值. 當一個對象的熱塊率超過這個閾值, 它就可以被放入Object Buffer; 反之, 則需要將其中的熱塊抽取放入Block Buffer.

接下來, 從理論上分析HG-Buffer 的效率. 假設緩沖區與數據庫大小的比值為T, HG-Buffer 中Normal Buffer、 Block Buffer、Object Buffer 的占比分別為N、B、O, 其中熱塊率的閾值及緩沖區與數據庫大小的比值相同, 也為T. 針對ClickHouse 現有的單一粒度緩沖區策略, 其熱數據占比最高為T.對于HG-Buffer, Block Buffer 熱數據的承載量 (Hhot,Blo) 為

Object Buffer 熱數據的承載量 (Hhot,Obj) 為

Normal Buffer 熱數據的承載量 (Hhot,Nor) 為

則整體HG-Buffer 的熱數據承載量 (Hhot,HG) 為

這里, 1-T代表不是熱塊的概率. 公式(1)中, 第一個 ( 1-T) 代表有 1-T概率的數據會被Normal Buffer 淘汰下來; 第二個 ( 1-T) 代表被淘汰的數據中有 1-T的數據不是熱塊, 所以這部分數據會被放在Block Buffer 中.

首先, 假設緩沖區的大小是數據庫大小的20%, 即熱塊率的閾值為20%. 現有普通的緩沖區管理器, 最好的情況下熱數據的緩存率為20%. 然后對HG-Buffer, 假設Normal Buffer、Block Buffer 和Object Buffer 的緩存率大小分別是20%、40%和40%. 因此, Normal Buffer 中包含了4%的熱數據量,Block Buffer 能承載的熱數據量最少為25.6%, 而其中Object Buffer 的熱數據量為6.4%. 這三者整體加起來的熱數據量估計為36%, 大于普通的緩沖區管理器.

5 實驗評估

本文實驗基于5 臺Linux 服務器組成的集群環境, 每臺Linux 服務器有相同的軟件和硬件配置:Intel(R) Xeon(R) Silver 4110 CPU@2.10 GHz; 128 GB 內存; 10 GB/s 以太網; CentOS Linux release 7.8.2003 操作系統, ClickHouse 版本為22.3.2.2-lts. 實驗評估HG-Buffer 的有效性和魯棒性評估.

5.1 有效性實驗

(1) SSD 直接作為二級緩存: 實驗設置100 GB 容量的二級緩存和50 GB 內存緩沖區緩存, 并將該二級緩存安裝在本地連接SSD 上.

(2) 作為系統交換空間擴展: ClickHouse 的緩沖區緩存不使用二級緩存, 而是將本地連接的SSD 的額外100 GB 通過使用操作系統交換空間進行擴展, 從而將總緩沖區緩存容量增加到150 GB.

(3) SSD 上使用HG-Buffer 為緩存策略作為二級緩存: 除了50 GB 內存緩沖區緩存和100 GB 容量的二級緩存, 與此同時, 系統使用HG-Buffer 緩存策略.

實驗依賴于TPC-H 基準測試[26], TPC-H 表是使用具有HighGroup (HG)索引[27]的范圍分區創建的, 有如下示例: o_custkey、n_regionkey、s_nationkey、c_nationkey、ps_suppkey、ps_partkey 和l_orderkey. 本文依靠AWS S3[28]作為ClickHouse 的底層對象存儲.

為了模擬數據的冷暖行為, 實驗每次測試都根據順序Q1,Q1, Q2,Q2,··· ,Q22,Q22進行, 即執行查詢2 次. 每次測試緩存只會在每次測試開始前被清除一次. 在 TPC-H 基準測試的加載階段, 除索引更新之外, 數據庫數據不會被服務器多次讀取. 所以, 在大多數情況下, 這些請求可以直接從內存緩沖區緩存中得到滿足. 因此, 本文不期望二級緩存會帶來性能的提升. 盡管如此, 也不希望二級緩存的啟用而導致性能下降. 如圖4(a)所示, 只有混合粒度緩存策略即HG-Buffer 可以能實現這一目標. 對于加載數據的場景, 使用操作系統交換空間增加緩沖區緩存容量會導致性能不佳, 因為操作系統內核使用的頁面大小、緩存策略不一定與ClickHouse 的緩沖區保持一致. 為此, 沒有二級緩存的情況及混合粒度緩存策略可以實現更好的性能.

圖4 二級緩存技術TPC-H 基準比較Fig. 4 Comparison of TPC-H between second-level caches

在基準測試的查詢階段, 從圖4(b)中可以觀察到, 使用操作系統交換空間增加緩沖區緩存容量也會導致查詢執行期間的性能不佳. SSD 二級緩存的情況有緩存利用率低下的缺點, 而HG-Buffer 緩存策略克服了這一點. 為此, 本文注意到混合緩存策略的執行時間為0.78 s, 而將SSD 直接作為二級緩存的方法的執行時間為1.06 s, 在混合緩存方法的情況下, 與SSD 直接作為二級緩存相比, 查詢執行時間的減少了28.2%.

5.2 魯棒性實驗

魯棒性驗證實驗的目的是驗證HG-Buffer 在不同的系統和硬件配置下能否提供穩健的性能. 實驗中控制總緩存大小, 即內存緩沖區加上HG-Buffer 的總大小不變, 但控制HG-Buffer 緩存大小, 從而有效地控制內存緩沖區與HG-Buffer 大小的比率. 與之前的實驗一樣, 實驗運行TPC-H 基準測試的功耗模式. 對于查詢測試, 第一個測試使用150 GB 的總緩存大小, 第二個測試使用200 GB 的總緩存大小. 圖5 顯示了具有不同HG-Buffer 緩存大小的系統配置的總加載時間, 圖6 顯示了具有不同HGBuffer 緩存大小的系統配置的總查詢執行時間. 關于數據加載和查詢, 在兩組測試中觀察到一致的執行時間. 關于查詢, 從圖6 中2 個對照組可觀察到執行時間一致, 差異很小. 所以關于數據的加載和查詢, 通過實驗, 可以發現HG-Buffer 具有理想的穩健行為.

圖5 TCP-H 基準測試下不同比值下的加載時間Fig. 5 Loading time at different ratios in TCP-H benchmark

圖6 TCP-H 基準測試下不同比值的查詢時間Fig. 6 Total query execution time at different ratios in TCP-H

6 總 結

隨著信息時代數據量的增加以及以太網的發展, 數據庫管理系統正逐漸從本地部署轉向云端, 以實現更高的彈性和更低的成本. 存算分離方案是一種數據存儲和計算分離的架構, 旨在提高大規模數據處理的性能和效率. 本文基于ClickHouse 和S3 的存算分離方案, 提出了一種基于SSD 的混合粒度緩存管理方案, 簡稱為HG-Buffer. HG-Buffer 的關鍵思想是將SSD 緩存空間組織成對象和塊這兩個粒度的緩存, 其中對象是數據存儲到對象存儲中的粒度, 而塊則是數據在本地磁盤上存儲的粒度. 通過控制這兩個粒度的緩沖區可提高系統的訪問效率. 本文還通過實驗驗證了HG-Buffer 的有效性和魯棒性.