沈靖 蔡鵬

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

關(guān)鍵詞： 分布式; 線性數(shù)據(jù); 自動化; 故障注入

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

0 引言

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

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

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

（1） 將線性數(shù)據(jù)應(yīng)用在故障測試工具上， 實現(xiàn)了具備更高可信度和普及性， 不需要太多專業(yè)領(lǐng)域知識的自動故障注入測試工具.

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

本文后續(xù)內(nèi)容是： 第1 章敘述LDFI 的原理; 第2 章詳述測試工具是如何實現(xiàn)的、過程中所遇到的挑戰(zhàn)有哪些; 第3 章介紹實驗結(jié)果; 第4 章是結(jié)論和相關(guān)工作.

1 LDFI 原理

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

1.1 線性數(shù)據(jù)

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

4 結(jié)論和相關(guān)工作

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

本文的主要目的是分享如何將一個研究性的理論原型轉(zhuǎn)換成實際的應(yīng)用， 而在轉(zhuǎn)換的過程中又遇到了哪些兼容性的問題， 又是如何在保證原有理論的主體思想不變的同時克服這些問題， 希望這些內(nèi)容和經(jīng)驗?zāi)軐ο嚓P(guān)工作者有所幫助， 有所借鑒.

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

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

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

[ 參 考 文 獻]

[ 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.

（責(zé)任編輯： 李 藝）