線性驅動的分布式數據庫容錯性自動化測試

沈靖 蔡鵬

摘要： 大規模的分布式數據庫中， 諸如網絡分區、信息丟失、節點宕機等軟硬件故障無法避免. 為了提高分布式數據庫的可靠性、驗證容錯協議的正確性， 分布式數據庫應定期進行故障注入測試， 即在系統運行過程中人為引發故障. 然而各種故障的組合空間太大， 無法枚舉. 已有的測試方法： 一類是隨機式故障組合， 其實現方法簡單但不能保證探索了所有的故障組合; 另一類是通過專業知識分析系統構成并設計的故障組合， 其測試結果更加完善但不具備普及性. 以線性數據驅動的故障注入測試LDFI （Lineage-DrivenFault Injection） 為原型， 在分布式數據庫的基礎上，實現了一種同時具有完備性和普及性的自動化故障注入測試工具. 實驗結果表明， 該測試工具能夠以更少的測試案例， 發現隨機式故障注入無法發現的復合故障組合所引起的系統漏洞（bug）， 提高了數據庫的可信度.

關鍵詞： 分布式; 線性數據; 自動化; 故障注入

中圖分類號： TP392 文獻標志碼： A DOI： 10.3969/j.issn.1000-5641.201921011

0 引言

分布式數據庫的復雜性使數據庫系統無法避免故障發生. 針對分布式場景中可能出現的故障， 如網絡延遲、丟包、節點宕機[1-2] 等， 開發人員設計了各類容錯協議來應對這些錯誤的發生， 如數據備份[3-4]、領導者選舉[5] 等. 盡管有這么多應對措施， 分布式數據庫開發者依舊不能保證自身設計的協議能在故障發生時讓系統繼續正常提供服務， 實際使用過程中還是會出現很多bug[6-9]. 這就需要故障注入測試主動觸發實際應用中可能出現的錯誤， 驗證容錯協議的正確性繼而提高分布式數據庫的可靠性.

故障注入測試主要由兩部分組成： 故障注入框架和設計測試案例. 故障注入框架[10-12] 通過各種工具模擬分布式數據庫可能產生的故障， 如最簡單的方法就是通過強制進程下線來模擬節點宕機， 現在也有許多開源的故障注入框架. 而如何設計故障發生的場景是測試的重點. 主要的設計方式有兩類：啟發式和隨機式故障注入. 啟發式的方法， 如SAMC （Semantic-Aware Model Checking）[13] 依賴于測試人員對于整個分布式數據庫的理解程度， 需要測試人員有足夠深度和廣度的專業知識， 因為測試人員知道了整個系統在什么樣的場景下可能會發生錯誤， 才能夠設計出特定的故障注入方案來驗證容錯協議的正確性. 啟發式的前提要求太高， 一般測試人員不能保證對每個系統都有足夠深的理解， 不具備普及性， 所以更為常見的是隨機式故障注入. 隨機式故障注入中具有代表性的是ChaosEngineering[14]， 測試人員通常在實際的應用場景上隨機地向數據庫中注入故障， 以此檢驗容錯協議的正確性. 隨機式故障注入的主要優點是簡單和通用， 但隨機式注入故障不可能考慮所有可能發生的錯誤場景， 而且很難發現涉及多個節點和多個故障組合的復合錯誤場景. 隨機測試只能提高系統的可信度， 不能保證容錯協議的正確性.

理想的測試案例不僅能測試出系統bug， 還能保證通過測試的分布式數據庫容錯協議的正確性.任何生成的測試案例都應該針對容錯協議的薄弱點， 而不是無意義的， 如LDFI[15] 就是針對分布式數據庫中對正確結果有貢獻的數據和操作所制訂的測試案例. 本文在LDFI 的啟發下， 通過分析分布式數據庫運行過程中所產生的線性數據和操作流程， 在可能影響正確結果的步驟中注入故障， 檢測容錯協議能否保證系統依舊得到正確的結果. 本文主要的貢獻如下.

（1） 將線性數據應用在故障測試工具上， 實現了具備更高可信度和普及性， 不需要太多專業領域知識的自動故障注入測試工具.

（2） 介紹了如何克服將理論模型實現在具體應用過程中所遇到的困難， 希望能為開發測試工具的研究者提供經驗和教訓.

本文后續內容是： 第1 章敘述LDFI 的原理; 第2 章詳述測試工具是如何實現的、過程中所遇到的挑戰有哪些; 第3 章介紹實驗結果; 第4 章是結論和相關工作.

1 LDFI 原理

LDFI 原型系統（稱為Molly） 使用Dedalus[16] （基于datalog 編寫的可執行規范語言） 編寫分布式程序和模擬分布式數據庫在各種故障下的執行操作. 主要原理是， 容錯協議通過冗余的方法預防系統某一組件出現問題， 即從初始狀態到預期結果， 系統會有多種方式達到同樣的結果. 這些冗余的操作如果全部枚舉會花費大量時間， 且不能保證完全遍歷了所有情況. 相對的， LDFI 選擇從系統正確執行的結果反推到起始狀態， 從中枚舉出存在潛在問題的步驟， 在這些步驟中執行故障注入， 針對性地生成測試案例， 驗證系統容錯協議的正確性.

1.1 線性數據

線性數據[12，17-18] 能抽象出分布式數據庫節點間通信和數據持久化的過程， 并且能夠更加直觀地檢測到系統為了確保結果正確而執行的冗余操作; 憑借線性數據， 能夠知道所有對正確結果有貢獻的操作和元數據. LDFI 利用線性數據的特點生成測試案例， 在分布式數據庫正確運行后， 從執行結果不斷回溯系統上一步的操作. 這樣的遞歸過程最后會產生一個譜系圖， 揭示所有對正確結果有貢獻的操作和數據; 通過故障注入就能打斷其中某一步驟， 從而得到容錯協議為了確保系統正確性而執行的冗余操作. 舉例說明， 圖1 是一個簡單的日志持久化的過程. 在分布式數據庫中為了保證數據不丟失， 往往會在多臺機器上備份數據. 衡量一條日志是否正確持久化的標準是， 這條日志是否在所有存活且和主機有聯系的機器上被存儲. 從這樣一個正確的結果回溯： 這條日志被認為是持久化的原因是， 它既存儲在節點A 上又存儲在節點B 上; 這條日志能在節點上被存儲是因為用戶嘗試了多次廣播， 將日志發送給了節點A 和節點B. 通過這樣的回溯過程， 就能得到圖1 這樣的流程圖. 通過圖1 可得出導致日志持久化的譜系圖

4 結論和相關工作

本文根據線性數據的特點， 改造優化了故障注入測試工具; 盡管在細節方面為了確保Cedar 原有的架構兼容了部分操作， 如多次執行測試案例來近似的控制故障注入的時機， 但是確保了且沒有改變利用線性數據的主要思想. 在以后的工作中， 要盡可能想辦法去彌補這些缺點.

本文的主要目的是分享如何將一個研究性的理論原型轉換成實際的應用， 而在轉換的過程中又遇到了哪些兼容性的問題， 又是如何在保證原有理論的主體思想不變的同時克服這些問題， 希望這些內容和經驗能對相關工作者有所幫助， 有所借鑒.

實現故障注入測試工具所需要的基礎條件之一是故障注入框架. 故障注入框架， 網上有很多的開源版本， 諸如阿里巴巴最近開源了一個名為Chao Blade 的故障注入平臺， 相對來說容易實現. 值得注意的是， LDFI 實現自動化生成測試方案的關鍵取決于獲取系統內部通信過程的細粒度的線性數據.鑒于這種特性， 在以后的工作中， 應該多考慮一些分布式數據庫如何跟蹤數據在系統中的傳遞過程.例如， 通過網絡作為監控， 或者利用Open Tracing 的功能來監控元數據的變化過程. 細粒度的線性數據不僅能為故障注入測試提供幫助， 也能幫助開發人員更好地理解分布式數據庫內部是如何運作的，運維人員也能更好地管理分布式數據庫的狀態， 及時發現數據庫的異常問題.

近些年， 也有很多新的測試工具， 如Jepsen， 是開源社區比較公認的一個分布式測試框架， 它模擬實現了各類常見的系統軟硬件故障， 其測試案例則是基于隨機式的方法進行設計， 且達到了一個比較良好的覆蓋率[20]; 除此之外， 還有FlyMC[21]， 它為云系統提供了新的快速且可擴展的測試方法， 通過引入新的算法使測試工具能更快速地發現系統bug， 并且在多個系統中發現了新舊bug.

對比同類工作， 本文實現的故障注入工具專注于故障的發生對結果的影響， 與隨機的故障注入不同， 它能更加充分地探索系統可能存在的錯誤空間， 而且摒棄了無效的測試案例; 不同于啟發式的故障注入， 它不需要特定系統的專業知識， 而是從系統的結果回溯到初始狀態， 探究能夠影響系統正確結果的因素. 當然這也有一定的局限性： 因為徹底地探索分布式數據庫所有可能存在的錯誤是不切實際的. 所以本文更關注容錯協議對于分布式數據庫的影響， 這就縮小了故障發生的范圍. 尤其是對于Paxos[22]、Raft[23] 這類共識算法， 本文不能確認Paxos、Raft 在發生特定的故障組合后得到的結果是錯誤的， 因為故障的發生有可能破壞這兩者為了達到節點間一致性而設定的前置條件. 所以， 單一的故障注入方法， 都不足以完全地保證分布式數據庫的正確性， 最完善的方法應該是將諸如LDFI 和SAMC 這類啟發式方法結合在一起， 先通過LDFI 快速發現可能影響系統的bug， 確保系統能正常運行， 之后再同步進行長時間的啟發式故障注入測試證明分布式數據庫的正確性.

[ 參 考 文 獻]

[ 1 ] BAILIS P， KINGSBURY K. The network is reliable [J]. Communications of the ACM， 2014， 57（9）： 48-55. DOI： 10.1145/2643130.

[ 2 ]DEAN J. Designs， lessons and advice from building large distributed systems [R/OL]. The 3rd ACM SIGOPS International Workshopon Large Scale Distributed Systems and Middleware.（2009-10-10）[2019-08-07]. http：//www.cs.cornell.edu/projects/ladis2009/talks/dean-keynote-ladis2009.pdf.

[ 3 ]ALSBERG P A， DAY J D. A principle for resilient sharing of distributed resources [C]//Proceedings of the 2nd InternationalConference on Software Engineering. IEEE， 1976： 562-570.

[ 4 ]STONEBRAKER M. Concurrency control and consistency of multiple copies of data in distributed INGRES [J]. IEEE Transactionson Software Engineering， 1979（3）： 188-194. DOI： 10.1109/TSE.1979.234180.

[ 5 ] GARCIA-MOLINA H. Elections in a distributed computing system [J]. IEEE Transactions on Computers， 1982（1）： 48-59.

[ 6 ]LEESATAPORNWONGSA T， LUKMAN J F， LU S， et al. TaxDC： A taxonomy of non-deterministic concurrency bugs in datacenterdistributed systems [J]. ACM SIGPLAN Notices， 2016， 51（4）： 517-530. DOI： 10.1145/2954679.2872374.

[ 7 ]GAO Y， DOU W S， QIN F， et al. An empirical study on crash recovery bugs in large-scale distributed systems [C]//Proceedings ofthe 2018 26th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of SoftwareEngineering. ACM， 2018： 539-550.

[ 8 ]FONSECA P， ZHANG K， WANG X， et al. An empirical study on the correctness of formally verified distributed systems[C]//Proceedings of the 12th European Conference on Computer Systems. ACM， 2017： 328-343.

[ 9 ] GANESAN A， ALAGAPPAN R， ARPACI-DUSSEAU A C， et al. Redundancy does not imply fault tolerance： Analysis of distributedstorage reactions to single errors and corruptions [J]. ACM Transactions on Storage， 2017， 13（3）： Article 20. DOI： 10.1145/3125497.

[10]DAWSON S， JAHANIAN F， MITTON T. ORCHESTRA： A fault injection environment for distributed systems [C]// Proceedings ofthe 26th International Symposium on Fault Tolerant Computing. IEEE， 1996： 404-414.

[11]GUNAWI H S， DO T， JOSHI P， et al. FATE and DESTINI： A framework for cloud recovery testing [C]// Proceedings of the 8thUSENIX Conference on Networked Systems Design and Implementation. ACM， 2011： 238-252.

[12]KANAWATI G A， KANAWATI N A， ABRAHAM J A. FERRARI： A flexible software-based fault and error injection system [J].IEEE Transactions on Computers， 1995， 44（2）： 248-260. DOI： 10.1109/12.364536.

[13]LEESATAPORNWONGSA T， HAO M Z， JOSHI P， et al. SAMC： Semantic-aware model checking for fast discovery of deep bugs incloud systems [C]// Proceedings of the 11th USENIX Symposium on Operating Systems Design and Implementation. USENIXAssociation. 2014： 399-414.

[14] BASIRI A， BEHNAM N， DE ROOIJ R， et al. Chaos engineering [J]. IEEE Software， 2016， 33（3）： 35-41. DOI： 10.1109/MS.2016.60.

[15]ALVARO P， ROSEN J， HELLERSTEIN J M. Lineage-driven fault injection [C]//Proceedings of the 2015 ACM SIGMODInternational Conference on Management of Data. ACM， 2015： 331-346.

[16]ALVARO P， MARCZAK W R， CONWAY N， et al. Dedalus： Datalog in time and space [C]//International Datalog 2.0 WorkshopDatalog 2.0 2010： Datalog Reloaded. Berlin： Springer， 2010： 262-281.

[17]BUNEMAN P， KHANNA S， TAN W C. Why and where： A characterization of data provenance [C]//International Conference onDatabase Theory. Berlin： Springer， 2001： 316-330.

[18]CUI Y， WIDOM J， WIENER J L. Tracing the lineage of view data in awarehousing environment [J]. ACM Transactions on DatabaseSystems （TODS）， 2000， 25（2）： 179-227. DOI： 10.1145/357775.357777.

[19]ALVARO P， CONWAY N， HELLERSTEIN J M， et al. Consistency analysis in bloom： A CALM and collected approach [C]// 5thBiennial Conference on Innovative Data Systems Research （CIDR 11）. 2011： 249-260.

[20]LUKMAN J F， KE H， STUARDO C A， et al. FlyMC： Highly scalable testing of complex interleavings in distributed systems[C]//Proceedings of the 14th EuroSys Conference 2019. ACM， 2019： Article number 20.

[21]MAJUMDAR R， NIKSIC F. Why is random testing effective for partition tolerance bugs？ [J]. Proceedings of the ACM onProgramming Languages， 2018， 2（POPL）： Article number 46. DOI： 10.1145/3158134.

[22]LAMPORT L. The part-time parliament [J]. ACM Transactions on Computer Systems （TOCS）， 1998， 16（2）： 133-169. DOI： 10.1145/279227.279229.

[23]ONGARO D， OUSTERHOUT J. In search of an understandable consensus algorithm [C]// Proceedings of the 2014 USENIX

Conference on USENIX Annual Technical Conference. USENIX Association， 2014： 305-320.

（責任編輯： 李 藝）