高钰(1992-), 女, 博士, 主要研究领域为软件工程, 系统测试, 系统可靠性
王栋(1996-), 男, 博士生, CCF学生会员, 主要研究领域为程序分析, 软件可靠性
戴千旺(1998-), 男, 硕士, 主要研究领域为软件可靠性, 数据库系统测试
窦文生(1984-), 男, 博士, 副研究员, CCF专业会员, 主要研究领域为程序分析, 软件工程
魏峻(1970-), 男, 博士, 研究员, 博士生导师, CCF高级会员, 主要研究领域为软件工程, 网络分布式计算
分布式系统的可靠性和可用性至关重要. 然而, 不正确的失效恢复机制及其实现会引发失效恢复缺陷, 威胁分布式系统的可靠性和可用性. 只有发生在特定时机的节点失效才会触发失效恢复缺陷, 因此, 检测分布式系统中的失效恢复缺陷具有挑战性. 提出了一种新方法Deminer来自动检测分布式系统中的失效恢复缺陷. 在大规模分布式系统中观察到, 同一份数据(即共用数据)可能被一组I/O写操作存储到不同位置(如不同的存储路径或节点). 而打断这样一组共用数据写操作执行的节点失效更容易触发失效恢复缺陷. 因此, Deminer以共用数据的使用为指导, 通过自动识别和注入这类容易引发故障的节点失效来检测失效恢复缺陷. 首先, Deminer追踪目标系统的一次正确执行中关键数据的使用. 然后, Deminer基于执行轨迹识别使用共用数据的I/O写操作对, 并预测容易引发错误的节点失效注入点. 最后, Deminer通过测试预测的节点失效注入点以及检查故障征兆来暴露和确认失效恢复缺陷. 实现了Deminer原型工具, 并在4个流行的开源分布式系统ZooKeeper、HBase、YARN和HDFS的最新版本上进行了验证. 实验结果表明Deminer方法能够有效检测分布式系统中的失效恢复缺陷. Deminer已经检测到6个失效恢复缺陷.
The critical reliability and availability of distributed systems are threatened by crash recovery bugs caused by incorrect crash recovery mechanisms and their implementations. The detection of crash recovery bugs, however, can be extremely challenging since these bugs only manifest themselves when a node crashes under special timing conditions. This study presents a novel approach Deminer to automatically detect crash recovery bugs in distributed systems. Observations in the large-scale distributed systems show that node crashes that interrupt the execution of related I/O write operations, which store a piece of data (i.e., common data) in different places, e.g., different storage paths or nodes, are more likely to trigger crash recovery bugs. Therefore, Deminer detects crash recovery bugs by automatically identifying and injecting such error-prone node crashes under the usage guidance of common data. Deminer first tracks the usage of critical data in a correct run. Then, it identifies I/O write operation pairs that use the common data and predicts error-prone injection points of a node crash on the basis of the execution trace. Finally, Deminer tests the predicted injection points of the node crash and checks failure symptoms to expose and confirm crash recovery bugs. A prototype of Deminer is implemented and evaluated on the latest versions of four widely used distributed systems, i.e., ZooKeeper, HBase, YARN, and HDFS. The experimental results show that Deminer is effective in finding crash recovery bugs. Deminer has detected six crash recovery bugs.
随着越来越多的数据与计算从本地往云端迁移, 大规模分布式系统已经在大型互联网, 如阿里巴巴、百度、腾讯、谷歌等得到广泛部署应用, 如存储系统[
在所有的失效场景中, 导致不一致系统状态的节点失效更易引发失效恢复缺陷. 我们观察到, 在分布式系统中, 一个节点会把同一份数据通过多个I/O写操作存储在节点外多个位置(也就是多个I/O写操作使用共用数据), 例如集群中其他节点或一个存储系统如本地文件系统或分布式文件系统HDFS中. 一个节点失效会导致该节点内所有的内存状态立刻丢失, 而被这个节点存储在节点外的数据则依然可以被访问并影响系统后续的行为. 如果一个节点失效打断一对共用数据写操作的执行, 则会导致不一致的系统状态, 进一步可能使后续的恢复行为失败.
一个正确的失效恢复例子
失效恢复缺陷难以避免. 在分布式系统中, 用“锁”来保护一组操作的执行不被节点失效所打断非常困难. 同时, 对于开发者而言, 预见所有可能导致不一致系统状态的节点失效场景具有挑战. 另外, 由于导致不一致系统状态的节点失效必须发生在特定的时机, 且使用共用数据的I/O写操作可能具有非常小的缺陷触发时间窗口, 因此在内部测试(in-house testing)中提早暴露失效恢复缺陷也十分困难. 此外, 失效恢复缺陷难以检测和诊断. 例如,
最近已经有一些研究可以用于检测与节点失效相关的缺陷[
本文中, 我们提出了Deminer, 一种新的分布式系统失效恢复缺陷检测方法. Deminer通过在使用共用数据的I/O写操作之间注入节点失效和节点重启来检测失效恢复缺陷. 我们通过分析真实的分布式系统以及真实的失效恢复缺陷, 总结了3种缺陷模式. 基于缺陷模式, Deminer首先通过观察目标系统的一次正确执行来追踪目标系统中的数据使用, 然后根据执行轨迹识别使用共用数据的相关I/O写操作对, 并预测会导致不一致系统状态的、容易引发错误的节点失效注入点. 最后, Deminer测试每一个预测的节点失效注入点, 注入相应的节点失效事件及节点重启事件, 并通过检查故障征兆识别失效恢复缺陷.
我们已经实现了Deminer工具原型, 并在4个流行的开源分布式系统ZooKeeper[
本文第1节通过一个真实的失效恢复缺陷来阐述本文的研究动机, 并介绍了我们的缺陷模式和面临的挑战. 第2节介绍本文的缺陷检测方法. 第3节介绍了方法的具体实现. 第4节通过实验验证了所提方法的有效性. 第5节介绍了所提方法的局限性. 第6节介绍了分布式系统故障注入及缺陷检测研究现状. 第7节总结全文.
在本节中, 我们首先通过一个真实的失效恢复缺陷引入我们的研究动机, 然后介绍我们的缺陷模型, 最后介绍我们的缺陷检测方法所面临的主要技术挑战.
在分布式系统中, 使用同一份数据的I/O写操作通常被期待一起执行. 打断这些操作执行的节点失效会导致不一致的系统状态. 如果不一致的系统状态无法被后续的恢复过程正确处理, 就会引发失效恢复缺陷. 如
一个ZooKeeper中的失效恢复缺陷示例(实线箭头表示消息; 虚线箭头表示节点内数据流)
当一个leader节点开始工作时, 它首先会启动一个线程来等待新的follower节点的连接请求(第4行). 随后leader节点提出了当前的epoch值, 并在收到集群中大多数follower节点的响应后, 把新的epoch值保存在epoch域变量(第1行)中. 随后, leader节点用新的epoch值设置当前事务ID (即zxid, 第6行), 并且用新的zxid更新ZooKeeper数据库(第7行).
此时, 一个ZooKeeper节点被启动并决定跟随当前leader节点, 并与leader节点同步(第17–20行). 该follower节点首先通过LEADERINFO消息(①→②)从leader节点收到最新的事务ID. 然后follower节点从另一个消息snapshot消息(③→④)中反序列化快照数据用于数据同步. LEADERINFO消息和snapshot消息都传输了同一份数据, 即新的epoch值. 随后, follower节点首先把当前内存数据状态保存在snapshot文件中(⑤), 然后将新的epoch值保存在currentEpoch文件中(⑥). 在这个例子中, I/O写操作⑤和⑥使用共用数据, 即源自leader节点的新的epoch值.
当follower节点在⑤和⑥之间失效时, snapshot文件将保存最新的epoch值, 而currentEpoch文件仍然保存着旧的epoch值. 这两个文件中不一致的epoch值将导致该follower节点无法在没有人工干预的情况下重启. 如果follower节点在更新snapshot文件前失效, 或在更新currentEpoch文件后失效, 则follower节点不会从snapshot文件中读到一个更大的epoch值, 因此能够成功重启.
要触发我们在第1.1 节描述的失效恢复缺陷, Deminer需要在使用同一份数据的I/O写操作之间注入节点失效及相应的节点重启. 下面, 我们将详细介绍我们分析总结的缺陷模式. 该缺陷模式指导了Deminer方法的设计.
相关术语如下: 本文中, I/O写操作指可以把数据存储在节点外的存储系统更新操作或节点间的消息发送操作. 在本文中, 我们考虑3种存储系统: 本地文件系统、分布式文件系统HDFS和分布式key-value存储系统ZooKeeper. 由同一个节点所执行的多个I/O写操作可能使用同一份数据(我们称为共用数据), 并把该数据存储在节点外多个位置(我们称为目标路径), 比如不同的节点或存储路径. 我们把这些使用共用数据的I/O写操作称为共用数据写操作. 由于我们主要考虑分布式系统中不同目标路径下数据的不一致, 而不是考虑传统文件系统中关注的打断对同一个目标文件的更新所引发的不一致, 因此我们只关注具有不同目标路径的共用数据写操作.
如
失效恢复缺陷中的共用数据写操作对(→表示消息; 灰色项表示因节点失效而消失的项)
● 单节点共用数据写操作相关失效恢复缺陷. 如
特别地, 存储系统更新操作
● 跨节点共用数据写操作相关失效恢复缺陷. 如
● 分散节点共用数据写操作相关失效恢复缺陷. 如
根据我们总结的3个缺陷模式, 暴露失效恢复缺陷的关键是共用数据写操作对的识别, 以及在这些共用数据写操作对之间注入节点失效和节点重启来产生容易导致失效恢复缺陷的、不一致的系统状态.
我们需要解决如下两个主要挑战: (1)哪些共用数据的不一致更易引发失效恢复缺陷? 追踪系统中每份数据的使用过程会引入巨大的性能开销, 并且只有关键数据的不一致才蕴含着失效恢复缺陷. (2)如何识别使用共用数据的I/O写操作对? 一份关键数据可能在多个节点中多次传播, 要判断该数据是否最终被两个具有不同目标路径的I/O写操作所使用具有挑战.
为了解决以上两个挑战, Deminer通过分析真实分布式系统和失效恢复缺陷来决定要追踪的关键数据类型, 例如从用户请求以及特定文件等中获得的用户数据和元数据, 从而在避免引入巨大性能开销的情况下尽可能考虑到分布式系统中所有容易引发错误的数据. 然后Deminer通过动态分布式系统数据追踪和离线执行轨迹分析来获得目标系统的一次执行中, 所有I/O写操作使用的关键数据来源. 基于分析结果, Deminer可以把使用共用数据的两个I/O写操作识别为共用数据写操作对.
Deminer检测失效恢复缺陷的方法流程如
Deminer方法流程
根据我们前面定义的缺陷模式, Deminer需要监测目标系统中的关键数据(主要是用户数据和元数据)的使用, 动态追踪它们如何在分布式集群中传播, 以及这些数据是否最终被一个I/O写操作(即存储系统写操作和消息发送操作)所使用. 对每一个使用关键数据的I/O写操作, 我们记录相应的信息, 最终生成一组系统I/O写操作执行轨迹.
要判断两个I/O写操作是否使用共用数据, 我们需要分析每个I/O写操作所使用的数据来源. 我们通过动态污点追踪技术来追踪我们所关心的数据.
● 节点内数据追踪. Deminer基于一个动态污点追踪系统Phosphor[
对于
● 跨节点数据追踪. 对跨节点传播的数据进行追踪, 关键是要将通过消息发送出去的数据在消息发送端和消息接收端进行匹配. 因此Deminer为每一个RPC调用以及socket消息生成一个随机数(即消息ID), 并通过为RPC调用以及socket消息增加额外的参数或字段来传播消息ID. Deminer会在消息发送端记录相应的消息ID, 并在消息接收端用消息ID为收到的数据生成污点标签. 据此, Deminer可以在离线分析阶段(第2.2 节)进行跨节点数据流分析.
对于一个分布式系统, 可能的数据来源, 也就是数据最初产生的地方, 主要包括用户请求、存储系统、物理设备的实时监测值、应用中的常量等. 而在这些数据源中, 只有关键数据的不一致才更容易引发失效恢复缺陷. 因此, 决定Deminer要追踪的关键数据至关重要.
一方面, 追踪系统中所有数据的使用情况是不现实的, 这会带来巨大的性能开销. 例如, 对本文实验中所用的目标系统和工作负载, 如果追踪所有数据的使用情况, 会造成内存溢出(OOM), 系统无法运行. 进一步而言, 追踪所有的数据也是不必要的. 对系统中所有数据进行追踪会使Deminer识别到大量不重要的共用数据写操作对. 例如, 一组具有相同消息类型的消息发送操作会由于使用了共用数据(即消息类型值)而被识别为一组共用数据写操作. 然而这些消息发送操作可能除了消息类型值以外没有其他共用数据, 在这些操作之间注入节点失效很可能不会引发失效恢复缺陷. 另一方面, 如果追踪的数据范围过小, 可能会导致遗漏重要的共用数据写操作对, 从而引入漏报. 而由开发者来人工指定每一个关键数据又是一项繁冗且容易出错的任务.
Deminer的解决方法是在不引入巨大性能开销的情况下, 尽可能地对所有可能蕴含失效恢复缺陷的数据进行追踪. 我们通过观察真实分布式系统发现, 用户数据和元数据的不一致更易引发失效恢复缺陷. 其中用户数据指系统用户创建和拥有的数据, 例如用户创建的表格数据. 而元数据指用来表示系统状态的数据, 例如某个节点的状态信息、某个表格的存储位置等. 这些数据的不一致容易导致复杂的系统状态. 对这些不一致状态的不正确处理更容易引发严重的后果, 例如使用户读取到不一致的数据等. 具体而言, Deminer考虑以下4类数据作为关键数据: (1)从用户指定的存储路径, 包括本地文件、HDFS文件和ZooKeeper节点znode中读到的数据. 这些存储目录下保存着用户数据和系统元数据; (2)系统特定数据, 例如nanoTime和currentTimeMillis, 这些数据常用作元数据的一部分, 如Job ID; (3)从用户请求中获得的数据, 这些数据往往包含用户关心的数据和配置信息, 例如ZooKeeper中的create请求, 会将用户所要创建的znode路径信息以及对应的znode值传给集群; (4)从目标集群中其他节点发送的消息中获得的数据. Deminer考虑此类数据是因为无法在节点间动态传播污点标签. 通过考虑这4类数据, Deminer尽可能对分布式系统中的大多数数据来源进行追踪, 以减少缺陷漏报.
一旦关键数据被目标系统获取, Deminer就会为其生成一个唯一的污点标签(如
一个污点标签组成
污点标签字段 | 值 |
污点标签ID | long类型的数值 |
数据源 | 对于从存储系统中读到的数据, 用路径字符串来表示;
|
节点ID | 生成该污点标签的节点IP和进程标识符 (PID)的组合 |
基于我们的缺陷模式, Deminer会为每一个使用关键数据的I/O写操作生成一条记录. 这些I/O写操作包括消息发送操作以及对存储系统(即本地文件系统、分布式文件系统HDFS和分布式键值存储ZooKeeper)的创建/删除/更新操作.
一个直观地识别I/O写操作的方法是在JRE层插入代码来追踪用于发送消息和操作文件的Java API的使用. 然而, 在JRE层进行追踪, 难以获得应用于HDFS和ZooKeeper的I/O操作的相关信息, 例如存储路径. 在JRE层, 所有对HDFS和ZooKeeper的操作都会被识别为消息发送操作. 从一串消息字节中对路径字符串和存储数据进行区分十分困难. 此外, 对分布式系统而言, 为消息增加装饰信息(如消息头)或对消息进行加密是一种常见的方式. 在JRE层, 将原本的消息内容和装饰信息以及用于加密的数据进行区分十分困难. 这会导致大量消息发送操作会被识别为共用数据写操作. 例如, 许多消息用相同的数据进行加密.
因此, Deminer选择在应用层追踪RPC调用和socket发送操作, 在应用层追踪对HDFS和ZooKeeper的操作, 以及在JRE层追踪本地文件相关操作. 对于HDFS和ZooKeeper, Deminer通过监测目标系统对它们的客户端API的使用来追踪相应的I/O操作, 并通过插桩代码来获取目标路径.
当一个I/O写操作使用关键数据时, Deminer会为其生成一条如后文
执行轨迹记录组成
执行轨迹记录字段 | 值 |
操作类型 | 存储系统I/O写操作或消息发送操作 |
目标路径ID | 用路径字符串来表示存储系统写操作的目标路径
|
污点标签 | 该操作所使用的关键数据对应的污点标签 |
调用栈 | 调用栈 |
时间戳 | 由RDTSCP 指令获得的纳秒级别本地时间戳计数 |
节点ID | 执行该操作的节点IP和进程标识符 (PID)的组合 |
线程ID | 执行该操作的线程哈希值 |
根据预定义的缺陷模式, 由同一个节点所执行的、具有不同目标路径ID且使用共用数据的I/O写操作对是一对共用数据写操作. Deminer根据记录的系统执行轨迹, 比较每两个I/O写操作相对应的执行记录内容来判断这两个I/O写操作是否为一对共用数据写操作. 其中, 判断两个执行记录是否使用共用数据, 一方面是通过直接比较两个记录所使用的污点标签交集是否为空来获得, 另一方面是基于污点标签以及消息ID来进行跨节点数据流分析, 比较两个记录是否共用由另一个节点获得的、经由消息传播到本地节点的数据所对应的污点标签. 具体的共用数据写操作对识别过程如算法1所示.
算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
算法1以第2.1 节生成的I/O写操作记录(即records)作为输入. 对于records中的任意两个I/O写记录
对于由同一个节点收集的记录(第6行), 算法1首先直接计算这两个记录对应的污点标签的交集(第7行). 如果它们有非空的污点标签交集, Deminer则直接把这两个I/O写记录识别为一对共用数据写操作. 例如, 对于
如果两个记录的污点标签交集为空(第8–9行), 例如
给定一个污点标签, Deminer基于该污点标签的数据源信息来寻找它对应的远端污点标签. 对于一个污点标签
节点失效注入点表示应该在什么位置注入一个容易引发错误的节点失效事件. 根据预定义的缺陷模式, Deminer会在两个共用数据写操作之间注入节点失效来使前一个I/O写操作被执行, 而后一个I/O写操作失败, 从而产生不一致的系统状态. Deminer的目标是找到能测试更多不一致的系统状态以及更多失效恢复行为的节点失效注入点.
● 失效类型. 根据缺陷模式, Deminer会生成两种类型的失效注入点: 本地失效和远端失效. 对于由节点
● 失效注入点生成. 对于一个共用数据写操作对
对于一组具有相同失效类型、相同的后一个操作以及不需要翻转原来共用数据写操作对执行顺序的故障注入点, Deminer只保留前一个操作具有最大时间戳的失效注入点. 这是因为为了避免引入错误和性能开销, Deminer在缺陷触发阶段只控制与被测共用数据写操作对相关的I/O写操作的执行顺序, 并假设目标系统的其他I/O写操作在缺陷触发阶段和执行轨迹追踪阶段的执行序列相同. 对于一个节点失效注入点, Deminer在前一个操作执行之后, 后一个操作将要执行之前注入节点失效. 因此具有相同的后一个操作的失效注入点蕴含着相同的不一致状态. 例如对两个具有相同失效类型(
Deminer会自动测试每一个生成的失效注入点, 并通过观察故障征兆来确认一个失效恢复缺陷是否出现.
由于节点失效和重启都会触发恢复行为, Deminer对于每一个失效注入点会同时向目标系统注入一个节点失效事件以及相应的节点重启事件. 具体而言, 我们的故障模型如下所述. 在每次测试运行中, 只有一个节点失效注入点会被测试. 对一个失效注入点, 一个节点失效首先会被注入到目标节点中. 在随机等待一段时间后(1 min以内), 失效的节点会被重启. Deminer之所以使用这种简单的故障模型, 是因为我们之前关于分布式系统中失效恢复缺陷的实证研究[
在缺陷触发阶段, Deminer会启动一个故障注入控制器来控制整个测试过程. 在一次测试运行中, 在执行轨迹追踪阶段使用的工作负载会以触发模式执行. 而故障注入控制器会选择一个节点失效注入点进行测试, 并控制工作负载的启动和停止、故障的注入、故障征兆检查以及缺陷报告的生成. 以失效注入点
在故障注入过程中, 当失效注入点的后一个操作
对于每个被测的工作负载, 我们会根据领域知识, 人工书写特定的检查器来检测故障征兆. 具体而言, 我们的检查器会检查一般的故障征兆(如运行日志中的FATAL、ERROR和Exception, 以及节点崩溃), 也会检查操作特定的故障征兆(例如操作返回错误代码或者读取到过时数据). 基于我们已经实现的检查器, 用户很容易就可以为其他工作负载实现特定检查器. 在实际使用中, 测试人员可以通过为特定目标系统下的特定工作负载设计更为精细的故障征兆检查器来减少缺陷漏报和缺陷误报.
对于操作特定的故障征兆(如操作返回错误代码), Deminer在工作负载运行过程中通过检查某个操作的运行返回结果来进行确认. 对于一般性故障征兆(如节点宕机、错误日志等), Deminer在节点失效和重启被注入、工作负载运行结束之后等待15 s (该数值可配置)再进行检查. 此时, 目标系统的所有恢复操作更可能都已完成, 从而可以检测系统的恢复结果是否出错. 此外, Deminer还会在一次测试开始之后检测工作负载是否在特定运行时间之内(平均运行时间的2倍)完成来检测挂起错误.
Deminer被实现为一个命令行工具并且支持JVM 1.8版本. 使用Deminer主要需要4个步骤: (1)通过运行一行命令生成一个Java运行环境的插桩版本; (2)配置集群中的每一个节点使其使用插桩后的JRE并使用Deminer用于运行时插桩, 然后以执行轨迹追踪模式启动集群并运行一个工作负载; (3)从每一个节点收集记录的执行轨迹, 然后通过运行一行命令来生成共用数据写操作对和节点失效注入点; (4)配置目标系统以触发模式运行, 启动故障注入控制器来测试预测的失效注入点. 最后, 对于每一个没有通过检查器的失效注入点, Deminer会为其生成一个缺陷报告.
Deminer使用ASM[
对于RPC调用, 最新的Hadoop和HBase版本基于Protocol buffer来实现RPC. 对于HBase RPC接口, Deminer通过检查接口类名是否以“Service$BolockingInterface”结尾来获得. 对于Hadoop RPC接口, Deminer通过预先指定获得. 然后Deminer根据RPC接口可以很容易获得相应的RPC方法. 对于socket, ZooKeeper中的所有socket消息都继承了一个Record超类. Deminer基于Record对象如何被使用来识别socket的发送和接收.
我们在流行的开源分布式系统上对Deminer进行了验证, 来回答如下3个研究问题: (1) Deminer能否有效检测分布式系统中的失效恢复缺陷? (2) Deminer与其他节点失效注入方法比较如何? (3) Deminer性能开销如何?
我们选择了4个流行的开源分布式系统对Deminer进行验证: 分布式文件系统HDFS (HD); 分布式资源管理系统YARN (YA); 分布式NoSQL数据库HBase (HB); 分布式协调服务ZooKeeper (ZK). 这4个分布式系统具有不同的功能, 并且实现了不同的失效恢复机制.
HDFS使用复制机制将一个数据块的副本存储在多个DataNode上来容忍DataNode的失效. HDFS也允许在一个集群中运行两个或多个冗余的NameNode节点来容忍NameNode节点的失效.
YARN通过ResourceManager高可用性来避免单点失效问题. 此外, YARN也提供配置允许ResourceManager在重启之后保持正常工作, 以及允许NodeManager在重启之后不丢失运行在该节点上的活动容器.
HBase依靠ZooKeeper来维护配置信息、从节点(RegionServer)和客户端之间的交互以及分布式同步. 当一个HMaster节点失效后, 另一个备用的HMaster节点会被激活并接管集群. 当一个RegionServer节点失效后, 所有位于该节点上的数据分区 (即region, HBase上的最小存储和负载单元)会被转移到另外一个RegionServer节点上. HBase中的失效恢复机制使得HBase集群和集群中的数据在节点失效时仍然可以被访问.
ZooKeeper在集群中大多数节点启动的情况下可以保持正常工作, 因此它可以容忍集群中少数节点宕机. ZooKeeper中的每个节点都维护一个数据目录, 其中保存着快照文件(snapshot)和事务日志文件(transactional log). 这些文件保存着一个ZooKeeper节点中的znode持久化副本. 节点重启后可以从这些文件中恢复数据.
为了验证Deminer在检测分布式系统失效恢复缺陷上的有效性, 我们把Deminer应用于目标系统的最新发布版本上. 对于HBase, 它的版本1仍被支持和开发, 因此我们也在它的最新版本1上进行了测试.
目标系统实验设置
System | Workload |
HDFS 3.3.1 | 1. Put/move file, read/write file |
2. Read/write file + failover NameNode | |
YARN 3.3.1 | 1. Run WordCount |
HBase 2.4.8/HBase 1.7.1 | 1. Create/read/update/truncate/delete table |
2. Create/read/delete table + failover HMaster | |
3. Create/read/delete table + failover meta server | |
ZooKeeper 3.6.3 | 1. Create/read/update/delete znodes |
2. Create/update znode + failover leader node |
对于HDFS, 我们设计了两个工作负载来测试文件系统操作和NameNode故障转移. HDFS被配置使用2个副本, 使用quorum journal manager (QJM)来允许HDFS的高可用性, 并且基于ZooKeeper进行自动故障转移. 文件系统操作工作负载运行在一个拥有2个NameNode节点和3个DataNode节点的集群上. 而NameNode故障转移工作负载则运行在一个拥有3个NameNode节点和3个DataNode节点的集群上.
对于YARN, 我们创建了一个工作负载来在拥有两个ResourceManager和两个NodeManager的节点上运行WordCount应用. YARN集群被配置为ResourceManager高可用以及ResourceManager基于ZooKeeper进行保留工作模式的重启(Work-preserving RM restart). 此外YARN集群运行在一个具有一个NameNode节点和一个DataNode节点的HDFS集群之上.
对于HBase 1.7.1 (HB-1)和HBase 2.4.8 (HB-2), 我们设计了3个工作负载: 在一个拥有两个HMaster节点和两个RegionServer节点的集群上运行表管理操作; 在一个拥有3个HMaster节点和两个RegionServer节点的集群上运行HMaster故障转移; 在一个拥有两个HMaster节点和3个RegionServer节点的集群上运行meta Region-Server故障转移. 每个HBase集群都运行在一个拥有1个NameNode节点和1个DataNode节点的HDFS集群和一个拥有3个节点的ZooKeeper集群上.
对于ZooKeeper, 我们创建了两个工作负载: 在一个拥有3个节点的集群上运行znode共用数据写操作; 在一个拥有5个节点的集群上运行leader故障转移.
我们之前的实证研究工作[
我们用Docker 19.03.3在几台虚拟机上部署目标系统集群. 虚拟机中的操作系统使用Ubuntu 20.04和JVM 1.8. 主机采用64位CentOS Linux 7.3.1611系统、JVM 1.8、两个16核2.10 GHz Intel(R) Xeon(R) Gold 6130 CPU和125 GB RAM. 离线分析部分(即共用数据写操作对识别和节点失效点预测)以及故障注入控制器运行在主机上. 所有的轨迹追踪阶段和离线分析阶段的性能数值都是3次运行所得的平均值. 基准性能是在没有代码插桩的情况下度量得到的.
Deminer触发的失效恢复缺陷
Bug ID | Failure symptom | Reboot | Random |
hb26370 | Misleading error message | × | √ |
hb26391 | Data staleness | × | × |
hb26420 | Cluster out of service | × | √ |
zk4283 | Node downtime | √ | × |
zk4416 | Node downtime | √ | × |
hd16381 | Operation failure | × | × |
Deminer通过
如
每个系统中出现的不同测试故障数
System | Failures | Bugs | False Pos. | Can’t Repr. |
注: *表示HB2中的一个故障和HB1中的一个故障具有相同的缺陷根因 (hb26370) | ||||
HDFS | 11 | 1 | 8 | 2 |
YARN | 2 | 0 | 2 | 0 |
HB2 | 16 | 1* | 15 | 0 |
HB1 | 15 | 3* | 9 | 3 |
ZK | 8 | 2 | 6 | 0 |
Total |
我们进一步研究了Deminer所产生的误报. 大多数误报(38/40)是由不合适的故障征兆检查器、预期的故障以及可以被系统容忍的故障导致. 例如, 在HBase的一个误报中, Deminer向meta RegionServer注入了一个节点失效和重启. 随后在工作负载结束之后Deminer开始检查目标系统. 然而此时位于失效节点上的元数据表还没有被恢复, 使得该测试在检查器检查时, 由于没有可用的元数据表而使测试没有通过. 实际上, 在等待一段时间之后, 元数据表会被成功恢复. 在另一个ZooKeeper的误报中, follower节点在与leader节点同步的过程中抛出了空指针异常, 使得测试没有通过故障征兆检查器. 然而这个故障可以被集群所容忍. 该follower节点会重新进入leader选举阶段并重新与leader节点进行同步.
我们注意到虽然一些故障可以被集群容忍, 开发者也不确定对这些故障的处理是否会产生问题. 在另一个HBase的误报中, 测试由于遇到“TableNotFoundException: No state found for table”异常而没有通过检查器. HBase集群通过忽略该异常来容忍这个故障. 然而, 开发者也不确定这样的处理是否正确, 并在代码中留下注释信息: “is it safe to just return false here?”
我们通过缺陷hb26420来说明Deminer触发缺陷的过程. 在hb26420中, 当一个主节点
Deminer成功识别到
我们把Deminer和随机故障(即节点失效)注入方法进行了比较. 在随机故障注入方法中, 每个工作负载会被运行与Deminer预测的失效注入点数目相同的次数. 在每次测试运行中, 我们会随机选择目标集群中的一个节点注入节点失效及相应的节点重启. 我们在0和最长运行时长之间随机选择一个时间偏移值注入节点失效. 在随机等待30 s以内的时间后重新启动失效的节点. 如果一次测试运行在到达失效注入点前结束, 则节点失效和重启不会被注入到这次测试中. 我们在随机故障注入中使用和Deminer相同的检查器来检查故障征兆, 并通过分析运行日志来确认真实的缺陷.
随机故障注入测试结果
System | Test | Runs | Triggered | Time (h) | Known bugs |
HDFS | 1 | 874 | 775 | 41 | 0 (1) |
2 | 290 | 251 | 13 | ||
YARN | 1 | 412 | 355 | 40 | 0 (0) |
HB2 | 1 | 1 191 | 679 | 94 | 0 (1) |
2 | 347 | 210 | 13 | ||
3 | 327 | 292 | 29 | ||
HB1 | 1 | 1 171 | 879 | 56 | 2 (3) |
2 | 457 | 266 | 18 | ||
3 | 594 | 492 | 38 | ||
ZK | 1 | 292 | 181 | 4 | 0 (2) |
2 | 2 108 | 1 610 | 37 |
我们没有把Deminer与别的故障注入方法进行比较. 这是因为其他故障注入方法没有公开可用的工具、难以使用或者被设计为检测其他类型的失效相关缺陷. 此外, 其他故障注入方法在没有复杂分析和建模的情况下也很难比随机故障注入表现更好.
为了度量Deminer的性能开销, 我们在应用Deminer时记录了几个如
Deminer性能开销
System | Test | Baseline (s) | Tracing | Analysis | Triggering | |||||||
Slowdown | Trace size (MB) | Records | Related pairs | Crashes | Runs | Triggered | Time (h) | |||||
HDFS | 1 | 71 | 2.8× | 7.4 | 254 | 1 499 | 874 | 1 353 | 166 | 92 | ||
2 | 63 | 4.3× | 4.5 | 212 | 401 | 290 | 728 | 146 | 54 | |||
YARN | 1 | 36 | 8.6× | 43.2 | 955 | 1 456 | 412 | 1 064 | 108 | 92 | ||
HB2 | 1 | 41 | 3.7× | 3.5 | 237 | 3 989 | 1 191 | 490 | 297 | 41 | ||
2 | 47 | 3.7× | 2.9 | 201 | 1 042 | 347 | 264 | 153 | 26 | |||
3 | 103 | 1.9× | 1.9 | 180 | 972 | 327 | 220 | 131 | 37 | |||
HB1 | 1 | 44 | 2.5× | 4.0 | 249 | 5 701 | 1 711 | 1 103 | 386 | 106 | ||
2 | 37 | 3.3× | 1.9 | 161 | 1 089 | 457 | 502 | 154 | 51 | |||
3 | 121 | 1.7× | 2.6 | 266 | 1 865 | 594 | 1 048 | 167 | 127 | |||
ZK | 1 | 7 | 5.4× | 0.8 | 96 | 154 | 292 | 226 | 196 | 8 | ||
2 | 15 | 5.7× | 1.6 | 362 | 2 835 | 2 108 | 3 783 | 983 | 264 |
在执行轨迹追踪阶段, 相比于基准运行时间, Deminer在YARN上引入了8.6倍的性能开销. 而在其他系统上, Deminer只引入了1.7–5.7倍的性能开销(Slowdown列). 引入性能开销的主要因素是污点标签的传播. 另外一个重要因素是我们在运行时对目标系统进行插桩. 如果我们提前通过静态方式对目标系统进行插桩可以使所费时长更短. Deminer产生的执行轨迹记录在0.8–43.2 MB之间(Trace size列). 对于每个工作负载, 我们得到了96–955个使用了关键数据的I/O写记录(Records列).
不同工作负载下的离线分析阶段耗时都较小. 对于大多数测试, 离线分析部分都可以在1 min以内完成. 对于YARN, 离线分析时间达到了5 min. Deminer识别到的共用数据写操作对在154–5701之间(Related pairs列), 而生成的节点失效注入点在290–2108之间(Crashes列).
在缺陷触发阶段, 测试迭代次数在220–3783之间(Runs列). 对于某些失效注入点的测试会耗尽最大尝试次数(即5次). 而在触发阶段推测的happens-before关系会使得Deminer跳过对一些不可执行的失效注入点的测试. 成功触发的失效注入点的个数在108–983之间(Triggered列). 整个测试时长在8–264 h之间(Time列). 特别地, 在缺陷触发阶段, 每次测试运行的平均时长(Time/Runs)要大于执行轨迹追踪阶段的运行时长. 这是因为我们在缺陷触发阶段会注入节点失效和重启, 引发额外的恢复行为. 通过配置Deminer减少对每个失效注入点的最大测试尝试次数, 以及配置目标系统在失效检测过程中使用更小的超时时间, 可以减少测试时长.
考虑到分布式系统十分复杂, 以上的结果说明Deminer在应用于真实分布式系统方面具有有效性.
在本节, 我们将讨论方法的局限性以及潜在的威胁.
(1)共用数据写操作对识别. Deminer的高效性和有效性取决于识别到的共用数据写操作对的质量. 第1个影响共用数据写操作对识别质量的因素是我们追踪的数据. 不是所有从消息和用户指定的存储路径中获得的数据的不一致都蕴含着失效恢复缺陷. 在未来的工作中, 我们考虑挖掘更有价值的数据来进行追踪. 第2个影响共用数据写操作对质量的因素是分布式系统数据流追踪的准确度. 基于消息ID的节点间数据流追踪是一种粗粒度的解决方案, 有可能引入误报. 此外, 缺乏本地文件系统的数据流追踪也会造成漏报. 我们将在未来的工作中提出更精确的数据流追踪方案.
(2)节点失效注入点生成与触发. Deminer目前只控制被测失效注入点中相关的I/O写操作的执行顺序, 这会导致缺陷漏报. 在未来的研究工作中, Deminer可以通过控制所有I/O写操作的执行顺序以及一些其他的非确定性事件(如线程创建、用户请求)的执行顺序来更精确地控制目标系统的运行, 从而减少缺陷漏报. 另外, Deminer通过在运行时等待一段时间的方式来推测可能的happens-before关系. 等待时间设置不合理也可能会造成缺陷漏报. 在未来的研究工作中, Deminer可以通过追踪更多的事件来进行更准确的happens-before关系分析, 从而减少漏报.
(3)缺陷检测. 对于一对共用数据写操作, 在它们之间注入节点失效可以导致不一致的系统状态. 然而这个不一致的状态可能被后续的恢复过程所容忍. 例如一些分布式系统(如HDFS)以复制的方式来存储数据, 提高系统的可靠性. 在用于复制数据的几个共用数据写操作之间发生的节点失效通常可以被系统所容忍. 这是因为对于这类分布式系统, 容忍这样的节点失效是它们要考虑的一个主要问题. 在未来的工作中, 考虑通过影响预估分析来过滤掉一些可能被系统所容忍的故障注入点. 另外, 缺陷检测结果依赖于故障征兆检查器的质量. 在未来的工作中, 我们可以通过设计更为精细的故障征兆检查器来减少缺陷漏报和缺陷误报. 也可以通过更准确的目标系统运行时监测来识别系统恢复行为是否完成, 并在所有恢复行为完成后应用故障征兆检查器来减少缺陷漏报和缺陷误报.
对有效性的威胁方面, 我们在4个流行开源分布式系统的最新版本上对Deminer进行了验证. 然而, 实验结果可能无法反映Deminer在其他系统上的实验结果. 但是, 通过选择具有不同功能(即分布式文件系统、分布式资源协调系统、分布式NoSQL数据库和分布式同步服务)和各种恢复恢复机制(例如自动故障转移、同步、备份等)的分布式系统, 力求在系统选择上做到不偏不倚.
(1)故障注入. 故障注入是分布式系统中暴露缺陷的一种常用技术. 故障注入框架例如Chaos Monkey[
最近的工作也提出基于协议感知或领域知识来进行故障注入. CORDS[
(2)模型检查. 分布式系统模型检查器[
(3)分布式系统缺陷检测. FCatch[
(4)验证. 许多分布式协议(例如Paxos[
失效恢复缺陷影响分布式系统的可用性和可靠性, 而此类缺陷往往只有节点失效发生在特定时机时才会被触发, 因此检测此类缺陷具有挑战性. 本文提出了一种共用数据导向的分布式系统失效恢复缺陷检测方法Deminer. Deminer通过动态追踪关键数据在运行时的使用来识别使用共用数据的相关I/O写操作对, 并在这些共用数据写操作对之间自动注入节点失效和节点重启来触发失效恢复缺陷. Deminer已经在4个流行的开源分布式系统上检测到6个失效恢复缺陷. 我们的实验表明Deminer在失效恢复缺陷检测方面具有有效性.
Chang F, Dean J, Ghemawat S, Hsieh WC, Wallach DA, Burrows M, Chandra T, Fikes A, Gruber RE. Bigtable: A distributed storage system for structured data. ACM Transactions on Computer Systems, 2008, 26(2): 4. [doi: 10.1145/1365815.1365816]
http://iepg.org/iepg/2009-11-ietf76/dean-keynote-ladis2009.pdf]]>
http://www.jos.org.cn/1000-9825/5651.htm]]>
http://www.jos.org.cn/1000-9825/5651.htm]]>
https://github.com/Netflix/SimianArmy/wiki/Chaos-Monkey]]>
https://github.com/jepsen-io/jepsen]]>
TM. 2020. http://zookeeper.apache.org]]>
https://hbase.apache.org]]>
https://hadoop.apache.org/docs/stable/hadoop-yarn/hadoop-yarn-site/YARN.html]]>
https://hadoop.apache.org/docs/r1.2.1/hdfs_design.html]]>
https://asm.ow2.io/]]>
Lamport L. The part-time parliament. ACM Transactions on Computer Systems, 1998, 16(2): 133–169. [doi: 10.1145/279227.279229]
+. In: Proc. of the 1st Int’l Symp. on Dependable Software Engineering: Theories, Tools, and Applications. Nanjing: Springer, 2015. 284–299.]]>
https://coq.inria.fr/]]>
https://lamport.azurewebsites.net/tla/tla.html]]>