基于變化數據捕獲機制的分布式緩存一致性策略①

江 勇, 苗宗利, 王 偉, 段世凱, 劉財政, 支孟軒

1(中國科學院大學, 北京 100049)2(中國科學院軟件研究所 軟件工程技術研究開發中心, 北京 100190)3(中國電子技術標準化研究院, 北京 100007)

基于變化數據捕獲機制的分布式緩存一致性策略①

江 勇1,2, 苗宗利3, 王 偉2, 段世凱1,2, 劉財政1,2, 支孟軒2

1(中國科學院大學, 北京 100049)2(中國科學院軟件研究所 軟件工程技術研究開發中心, 北京 100190)3(中國電子技術標準化研究院, 北京 100007)

分布式緩存被廣泛應用于解決傳統關系型數據庫的性能瓶頸問題, 但是當不能感知分布式緩存的第三方應用直接更新后臺數據庫時, 緩存數據會獲得不一致的狀態, 存在過時緩存問題. 本文提出一種基于變化數據捕獲機制的分布式緩存一致性策略, 集成了基于觸發器和基于日志的兩種變化數據捕獲機制實時捕獲后臺數據庫更新, 實現了數據模型自動轉換方法和SQL翻譯引擎, 實時更新緩存, 從而保障分布式緩存的一致性. 實驗模擬TPC-W測試基準中的關鍵操作, 驗證了基于日志的變化數據捕獲機制相比基于觸發器的變化數據捕獲機制有更好的數據庫性能和緩存一致性效果.

分布式緩存; 變化數據捕獲; 模型轉換; SQL翻譯

1 引言

為了應對海量數據與大規模用戶請求帶來的挑戰,解決傳統數據庫面臨的大規模數據訪問瓶頸問題, 分布式緩存被廣泛應用, 為用戶提供高性能、高可用、可伸縮的數據緩存服務. 但是, 當不能感知緩存的第三方應用程序直接更新后臺數據庫數據時, 緩存會獲得不一致的狀態, 存在過時緩存問題[1], 如圖1所示.

保持緩存和后臺數據庫數據的數據一致性一直是開發人員重點關注的問題. 現有的典型分布式緩存方案, 如Memcached[2], Redis[3], Hazelcast[4]等, 主要通過基于過期的緩存一致性策略來保持緩存和后臺數據庫的數據一致性. 每個動態的緩存條目都會創建一個默認的存在時間清除器, 在預定義的時間間隔后會清除相應的數據條目, 但是過期時間的設定是一條經驗規則, 需要開發人員對數據的準確性需求和對數據過時程度的容忍度有足夠的了解, 然后才能做出合適的決策. IBM的WebSphere eXtreme Scale[5]實現了基于輪詢的緩存一致性策略, 由緩存定期查詢數據庫以確定自上次加載以來數據是否發生了變更, 已在后臺數據庫中更新的條目失效或者使用新的數據更新緩存. 但是,這些定期查詢會給后臺數據庫帶來較大的負載壓力,輪詢機制也會消耗額外的CPU資源.

針對現有緩存方案的特點以及緩存一致性策略存在的問題, 本文提出一種基于變化數據捕獲機制[6](Change Data Capture, CDC)的緩存一致性策略, 主要包括以下三個方面內容:

(1) 變化數據捕獲機制. 設計實現關系型數據庫的數據變化捕獲機制, 實時監聽后臺數據庫的數據變化, 捕獲數據更新并傳送到分布式緩存, 支持基于觸發器和基于日志兩種方式.

(2) 數據模型自動轉換方法. 實現關系型數據模型向key-value數據模型的自動轉換, 將數據庫表中的行數據自動轉換為分布式緩存的對象數據.

(3) SQL翻譯引擎. 將變化數據捕獲機制捕獲到的SQL更新操作翻譯為緩存的key-value操作, 從而將更新同步到緩存.

2 相關工作

文獻[7,8]較為全面的介紹了變化數據捕獲技術,主要有基于表記錄、復制、基于觸發器、基于日志等多種方法, 并比較了不同方法的條件、優點、缺點和適用場合. 文獻[9]和文獻[10]分別介紹了基于觸發器和基于日志的變化數據捕獲技術, 但是文獻[9]面向的是ETLM過程的數據倉庫, 文獻[10]面向實時商業智能系統.

在緩存一致性策略方面, 文獻[11]介紹了同步進制實現分布式緩存的強一致性, 每次更新數據時, 會同步更新所有緩存結點, 然后返回. 這種機制適用于以讀請求為主的應用場景, 而當數據更新操作頻繁時,強一致性的同步機制會顯著增加系統響應時間. 文獻[12]實現了在緩存增強的SQL系統上的緩存強一致性,并提出了IQ框架, 同時滿足ACID屬性, 但是分布式緩存受到CAP理論的約束, 該方法并不能夠在分布式緩存中適用; 文獻[13]將基于觸發器的數據捕獲技術應用到緩存, 保障緩存的一致性, 提出了一種面向ORM框架的緩存中間件, 是數據捕獲技術的一次成功應用. 但是該文獻重點在于緩存的ORM訪問方式, 對數據捕獲技術在緩存中的應用討論得并不夠細致.

上述相關工作中, 有將CDC應用到數據倉庫和智能系統的, 但是仍缺少將CDC技術與分布式緩存的集成; 有的實現了緩存的強一致性, 但是存在場景限制,只適合讀請求為主的場景; 有的提出創新的緩存一致性框架, 但并不適合分布式緩存. 本文重點關注將變化數據捕獲技術應用到分布式緩存中需解決的模型轉換, SQL翻譯等問題, 并用兩種方式實現變化數據捕獲.

針對現有緩存方案的特點以及緩存一致性策略存在的問題, 本文提出一種基于變化數據捕獲機制的緩存一致性策略, 通過在源系統中添加觸發器和獲取關系型數據庫日志兩種方式實現變化數據捕獲機制, 然后實現關系型數據模型向key-value數據模型的自動轉換, 最后解析SQL, 更新緩存, 實現數據從關系型數據庫到分布式緩存的自動同步.

3.1 變化數據捕獲機制

變化數據捕獲技術是基于對數據源改變部分的數據識別、數據獲取和數據傳送技術來實現的, 在數據源數據發生變化時, 將實時捕獲變更的數據并同步更新到分布式緩存中, 從而保障分布式緩存的一致性.本文實現基于觸發器和基于日志兩種變化數據捕獲機制, 并對比其優缺點.

3.1.1 基于觸發器的變化數據捕獲

通過在關系型數據庫中設置觸發器并設計一張日志表與源數據表相關聯, 當源數據表數據發生變化時,通過觸發器機制自動記錄數據變化到日志表. 同時,監聽線程實時監聽日志表信息, 獲取最新的數據變化,并通過數據傳送渠道將變更數據更新到緩存.

3 面向分布式緩存的變化數據捕獲機制

該方法的重點在于觸發器的設計. 觸發器一共有三種類型, 分別對應數據庫的插入, 刪除, 更新操作,任何數據表的變更操作, 都會觸發觸發器, 從而在觸發器日志表產生記錄. 圖2是針對數據庫test中的orders表插入操作時創建的觸發器.

圖2 觸發器實例

3.1.2 基于日志的變化數據捕獲

關系型數據庫都管理著一個事務日志, 其中記錄了對數據庫內容和元數據所做的更改. 基于日志的變化數據捕獲, 以關系型數據庫的事務日志為基礎, 并對其進行實時監控, 一旦源數據庫發生數據變化, 就進行實時捕獲, 對需要實時同步的數據進行捕獲, 如圖3所示.

圖3 基于日志的變化數據捕獲

基于日志的變化數據捕獲需要訪問關系型數據庫的事務日志, 并解析日志產生對應的更新SQL操作.但是事務日志通常以二進制的形式存在, 如果沒有官方文檔, 我們很難理解事務日志的內容. 本文利用開源工具open-replicator[14]實現基于日志的變化數據捕獲, open-replicator可以高效地解析Mysql的二進制日志, 并實時產生監聽事件.

3.1.3 變化數據捕獲機制比較

表1從應用條件、編程代價、性能, 移植性等方面比較了基于觸發器的變化數據捕獲機制和基于日志的變化數據捕獲機制.

表1 兩種不同變化數據捕獲機制對比

3.2 數據模型轉換方法

分布式緩存以key/value形式存儲數據, 有利于緩存節點的橫向擴展, 其中key和value均為數據對象,而在關系型數據庫中, 數據以表的形式進行存儲, 因此要實現數據庫向分布式緩存數據的自動同步, 首先要實現關系型數據模型向key/value數據模型的自動轉換, 圖4是數據模型轉換實例.

圖4 數據模型轉換實例

(1) 分布式緩存key的生成方法

生成分布式緩存的key, 首先要考慮兩個問題: ①key的唯一性: 由于分布式緩存一般以Map的結構存在, key的唯一性是Map存儲數據的必要條件; ②key的易用性: 分布式緩存中, 會計算key的哈希值從而確定數據的具體分布, 一個合理的key需保障哈希值的易計算, 同時, 分布式緩存的數據讀取都以key為基礎, 如果key的生成過于復雜, 在數據讀取時都會帶來不必要的性能開銷. 為了保證key的唯一性和易用性, 本文中的key都以字符串的形式存在, 對于數據庫中的單一主鍵情形, 直接選取數據庫表中的主鍵作為數據對象的key, 對于數據庫表中的多主鍵情況,將多列主鍵通過特殊間隔符組合拼接, 生成單一的key, 對數據庫表中沒有明確指定主鍵的情況, 采用主鍵自增方式, 為每個value對象維護一個整數自增變量作為對應的key值.

(2) value的生成方法

生成分布式緩存的value, 重點需考慮的是value的通用性. 由于關系型數據庫中不同表的數據含有不同的結構, 如何將不同表數據統一生成Map中的value,是本文重點考慮的問題. 本文將一張數據庫表映射轉換成一個Map, 數據庫表中的一條記錄對應Map中的一組key/value鍵值對. 通過數據庫表的元信息為每個表動態生成一個數據對象類, 類中屬性的類型和關系型數據庫屬性的類型一一對應, 所有數據對象類含有同一父類, 這樣, 為數據庫表的每條記錄生成的每個對象實例, 都能存儲到同一結構的Map中.

(3) Map的索引

關系型數據庫中的索引信息是提供高效數據訪問的正確手段. 本文為了將關系型數據庫的索引信息同步到分布式緩存, 專門設計了索引管理器. 在數據同步到緩存之前, 首先會利用數據庫表的元信息創建對應的分布式Map, 同時會提取數據庫列索引信息, 在Map中加入對應的索引. 在基于索引的查詢過程中,加入索引的Map可以快速尋址到對應的value對象.

3.3 SQL翻譯引擎

通過變化數據捕獲機制獲得的監聽事件往往以SQL的形式存在, 而分布式緩存的操作是基于key/value存儲的操作, SQL翻譯引擎負責將SQL翻譯成基于key/value存儲的可執行序列.

對數據庫的更新主要來源于Insert, Delete, Update三類語句, 本文主要翻譯這三類語句. SQL作為一種結構化查詢語言, 具有復雜的語法和完備的事務能力,使用key/value存儲結構難以完整兼容所有SQL, 并且對于復雜的嵌套、統計等語法效率會很低下. 本文目前支持的SQL語法如下:

(1) INSERT INTO ＜表名＞[(＜屬性列1＞[, ＜屬性列2＞…])] VALUES (＜常量1＞[, ＜常量2＞…]);

(2) DELETE FROM ＜表名＞ [WHERE ＜條件＞];

(3) UPDATE ＜表名＞ SET ＜列名＞=＜表達式＞[, ＜列名＞=＜表達式＞…] [WHERE ＜條件＞];

其中, 表達式支持常量的任意算術運算組成的表達式, 條件支持BETWEEN, IN, LIKE, EXISTS, IS NULL, 布爾條件表達式, 等式表達式等.

為了在key-value存儲系統上執行SQL, 本文定義了3種謂詞: 基本謂詞(basic_predicate)、關系謂詞(relation_predicate)、執行謂詞(execute_predicate), 如表2所示. 基本謂詞表示查詢條件, 如大于, like, exists等,每個基本謂詞是一系列基本k-v操作的封裝, 可直接在分布式緩存中執行; 關系謂詞表示多個謂詞之間的與/或關系; 執行謂詞分成插入謂詞(insert_predicate)、更新謂詞(update_predicate)、刪除謂詞(delete_predicate), 表示三種不同的基于鍵值對的數據更新操作.

表2 謂詞定義

在增刪改三類數據更新請求中, 更新語句的解析與執行相對來說較為復雜, 算法1描述了更新語句的解析執行過程. 首先, SQL解析后會生成一顆抽象語法樹, 同時生成關系謂詞列表(relation_predicate_list),然后從關系謂詞列表中順序提取基本謂詞, 依據基本謂詞可從分布式緩存中獲取對應的Value對象: map[table].getValue(basic_predicate), 再依據關系謂詞中的邏輯關系和基本謂詞獲得的Value對象, 獲得更新語句過程中的查詢結果, 更新謂詞會對該查詢結果對應的數據進行更新.

算法1 更新語句執行算法

4 實驗與分析

本文從兩個方面來對比基于觸發器的變化數據捕獲機制和基于日志的變化數據捕獲機制, 一是比較不同的變化數據捕獲機制對數據庫性能的影響程度, 二是比較不同的變化數據捕獲機制在保證分布式緩存一致性時, 不一致窗口的大小.

4.1 實驗設計

本文使用TPC-W[15]基準中的關鍵業務對比驗證基于觸發器的變化數據捕獲和基于日志的變化數據捕獲. TPC-W是一款以真實電子商務應用為用例的測試基準, 可以模擬用戶訪問電子商務圖書網站時的查詢、購買等行為, 包括根據查詢書籍, 用戶注冊, 訂單管理等. 本文選取TPC-W基準中與訂單管理相關的關鍵SQL語句來進行測試, 觀察變化數據捕獲的性能特點, 選取的SQL語句為: INSERT INTO order_line (ol_id, ol_o_id, ol_i_id, ol_qty, ol_discount, ol_comments) VALUES (?, ?, ?, ?, ?, ?), , 記為SQLX, SQLX的參數使用隨機值.

實驗的負載發生端使用YCSB[16]性能測試工具,數據庫采用MySQL, 對比測試不同變化數據捕獲技術應用到分布式緩存時, 給數據庫帶來的性能影響和緩存不一致窗口的大小. 實驗環境的軟硬件配置如表3所示.

表3 實驗環境軟硬件配置

4.2 實驗結果與分析

(1) 比較兩種變化數據捕獲機制下的數據庫性能

本次實驗中, 每個線程執行SQLX 10000次, 隨機向數據庫插入10000條記錄, 通過改變線程數量, 從而改變對數據庫的壓力, 分別測試線程數為1,2,5,10時, 每個線程向數據庫插入10000條記錄所需要的時間, 即數據庫的響應時間. 實驗結果如圖5所示, 其中,橫軸代表線程的數量, 縱軸代表每個線程插入10000條記錄的平均時間, 即數據庫的響應時間. 實驗結果表明, 隨著線程數的增大, 數據庫的響應時間逐漸增大. 但是, 由于觸發器對數據庫性能的影響, 在基于觸發器的變化數據捕獲下, 數據庫的響應時間增大更明顯, 基于日志的變化數據捕獲下的數據庫性能是基于觸發器的變化數據捕獲下數據庫性能的11到21倍.

圖5 不同變化數據捕獲機制下數據庫性能對比

(2) 比較兩種變化數據捕獲機制下的緩存一致性

根據CAP理論, 在一個分布式系統中, 一致性、可用性和分區容忍性三者不可得兼. 本文中分布式緩存的一致性不是強一致性, 數據庫數據更新和緩存數據同步更新之間存在一定的不一致窗口, 不一致窗口的大小是衡量系統性能的一個重要指標.

本次實驗中, 單線程執行SQLX 10000次, 隨機向數據庫插入10000條記錄, 通過改變兩次SQL執行之間的間隔時間來改變數據的更新頻率, SQL間隔執行間隔時間越長, 數據更新頻率越低. 分別測試SQL執行間隔時間為0,1,2,5,10毫秒時, 緩存捕獲到最新數據和數據庫插入數據間的不一致時間窗口. 實驗結果如圖6所示, 其中, 橫軸代表兩次SQL執行的時間間隔,縱軸代表緩存與數據庫之間的數據不一致時間窗口.從圖6可以看到如下現象: (1)數據更新頻率越低, 緩存的一致性效果越好. 由圖可知, 隨著間隔時間的增大, 也即數據更新頻率減小, 對變化數據捕獲模塊的壓力相對也減小, 從而在更短的響應時間內將數據同步到緩存. (2)基于日志的變化數據捕獲相比基于觸發器的變化數據捕獲有更好的一致性效果. 由圖可知,在不同的時間間隔下, 基于日志的變化數據捕獲的不一致窗口都要明顯小于基于觸發器的變化數據捕獲.

圖6 不同變化數據捕獲機制下緩存一致性對比

5 總結與展望

本文首先分析了第三方應用不能感知分布式緩存時存在的過時緩存問題, 然后提出了一種基于數據捕獲機制的緩存一致性策略, 主要包括面向分布式緩存的兩種變化數據捕獲機制, 數據模型的自動轉換方法和SQL翻譯引擎. 通過實驗對比驗證了基于日志的變化數據捕獲技術在數據庫性能和緩存一致性效果方面的性能優勢, 但是基于觸發器的變化數據捕獲技術有其通用性, 易用性, 編程代價低等優勢.

本文中基于變化數據捕獲機制的緩存一致性策略的設計與實現并不完善, 需要在未來工作中針對以下方面進行研究與改進: (1)由于關系型數據模型的復雜性, 關系型數據的外鍵約束等尚不支持; (2)運行時動態對數據表結構的修改并不能實時映射到分布式緩存數據結構.

1 Dreibholz T, Rathgeb E P. On the performance of reliable server pooling systems. The IEEE Conference on Local Computer Networks, 2005. 30th Anniversary. IEEE. 2005. 200–208.

2 Memcached. http://memcached.org/. [2016-03-29].

3 Redis. http://redis.io/. [2016-03-29].

4 Hazelcast. http://hazelcast.org/. [2016-03-29].

5 WebSphere Extreme Scale. http://www-03.ibm.com/software/ products/en/websphere-extreme-scale/. [2016-03-29].

6 Eccles M. Pragmatic Development of Service Based Real-Time Change Data Capture[Thesis]. Aston University, 2013.

7 徐富亮,周祖德.變化數據捕獲技術研究.武漢理工大學學報:信息與管理工程版,2009,31(5):740–743.

8 林子雨,楊冬青,宋國杰,等.實時主動數據倉庫中的變化數據捕獲研究綜述.計算機研究與發展,2007,44(z3):447–451.

9 Rocha RLA, Cardoso LF, de Souza JM. Performance tests in data warehousing ETLM process for detection of changes in data origin. Data Warehousing and Knowledge Discovery. Springer Berlin Heidelberg, 2003: 129–139.

10 Shi JG, Bao YB, Leng FL, et al. Study on log-based change data capture and handling mechanism in real-time data warehouse. 2008 International Conference on Computer Science and Software Engineering. IEEE. 2008, 4. 478–481. 11 Amza C, Soundararajan G, Cecchet E. Transparent caching with strong consistency in dynamic content web sites. International Conference on Supercomputing. 2005. 264–273.

12 Ghandeharizadeh S, Yap J, Nguyen H. Strong consistency in cache augmented SQL systems. Proc. of the 15th International Middleware Conference. ACM. 2014. 181–192.

13 Gupta P, Zeldovich N, Madden S. A trigger-based middleware cache for ORMs. Acm/ifip/usenix International Conference on MIDDLEWARE. Springer-Verlag. 2011. 329-349.

14 Open-replicator. https://github.com/whitesock/open- replicator. [2016-03-29].

15 TPC-W. http://www.tpc.org/tpcw/. [2016-03-29].

16 YCSB. https://github.com/brianfrankcooper/YCSB. [2016-03-29].

Distributed Cache Coherency Strategy Based on Change Data Capture Mechanism

JIANG Yong1,2, MIAO Zong-Li3, WANG Wei2, DUAN Shi-Kai1,2, LIU Cai-Zheng1,2, ZHI Meng-Xuan212
(University of Chinese Academy of Sciences, Beijing 100049, China)3(Technology Center of Software Engineering, Institute of Software, Chinese Academy of Sciences, Beijing 100190, China) (China Electronics Standardization Institute, Beijing 100007, China)

Distributed cache is widely used to solve the performance bottleneck problem in traditional relational database, but when third-party applications that are not cache-aware update the back-end database, the distributed cache will end up in an inconsistent state, which has the problem of stale cache data. This paper proposes a distributed cache consistency strategy based on change data capture mechanism. The work integrates trigger-based and log-based change data capture mechanism that can get the real-time data from backend database, and implements data model transformation and SQL translation engine, which can update cache in real-time to guarantee distributed cache coherence. The experiment simulates the key operation in TPC-W benchmark, which verifies that the change data capture based on log has the better database performance and cache consistency effects compared with the change data capture based on trigger.

distributed cache; change data capture; model transforming; SQL translation

2016-03-21;收到修改稿時間:2016-04-08

10.15888/j.cnki.csa.005450