沈靖 蔡鵬

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

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

中圖分類(lèi)號(hào)： TP392 文獻(xiàn)標(biāo)志碼： A DOI： 10.3969/j.issn.1000-5641.201921011

0 引言

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

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

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

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

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

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

1 LDFI 原理

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

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

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

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

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

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

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

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

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

[ 參 考 文 獻(xiàn)]

[ 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é)任編輯： 李 藝）