面向分布式流处理系统的故障检测及容错策略

任海鹏，汪学文，方继才

安徽机电职业技术学院信息工程系，安徽芜湖，241002

面向分布式流处理系统的故障检测及容错策略

任海鹏，汪学文，方继才

安徽机电职业技术学院信息工程系，安徽芜湖，241002

为解决智能手机主要依靠的客户端-服务器计算模式所面临的蜂窝网络瓶颈问题，提出将智能手机作为分布式计算平台，直接在手机上处理感应数据的方法，设计一种可以直接在智能手机上运行的分布式流处理系统MobiStreams。研究在智能手机上部署DSPS系统所面临的故障检测及容错策略问题，利用部署在美国的一项SignalGuru手机应用进行性能评估。仿真结果表明：从服务器平台迁移到智能手机平台有效解决了蜂窝网络的瓶颈问题。与传统基于服务器的DSPSs相比，吞吐量提升0.78～42.6倍，延时降低10%～94.8%。

智能手机；分布式数据流处理系统；故障检测；容错策略；吞吐量；延时

1 相关研究

目前大多数智能手机[1-2]都配有主频达1.5～2.0GHz的四核CPU，比如三星的Galaxy S4、联想的K860i和华为的Ascend P6，此外，八核智能手机已经面市。然而，当前系统和应用往往仅把手机当作数据采集工具，将手机的感知数据通过蜂窝网络发送给服务器进行处理[3-4]。由于蜂窝网络速度慢、开销大等缺陷，所以这些系统在采用蜂窝网络后存在诸多容错问题[5-7]。当前用于智能手机端的实时数据分析计算模式为分布式流处理系统(Distributed Stream Processing Systems, DSPSs)，如IBM的InfoSphere Streams[8]，Yahoo的S4[9]和Streambase[10]。这些DSPSs的核心硬件平台往往是可靠性较高的服务器集群。

当DSPSs从服务器集群转移到与ad-hoc WiFi相连的智能手机上时，在容错方面带来了巨大挑战。电量有限、移动性和可靠性有限的无线网络，均有可能导致智能手机出现故障。现有的这些容错方案均针对服务器，在智能手机上性能有限，原因如下：一是智能手机平台的故障模型与之前研究时的假设有很大不同，之前研究假设即使发生小规模(往往是单节点)故障也足以满足大多数实际应用的要求。对智能手机平台，往往会有多个手机同时故障，如多个手机用户同时离开通信区域，或者WiFi连接中断。二是以前的容错方案要求通过网络发送大量附加数据，给DSPS应用的性能带来了巨大开销，而智能手机平台的手机到手机ad-hoc WiFi网络带宽有限。因此，将当前的容错方案简单地用于智能手机平台将会降低系统性能。为此，本文提出将智能手机作为分布式计算平台，直接在手机上处理感应数据，以避免客户端-服务器计算模式的缺点。设计可直接在智能手机上运行的DSPS系统MobiStreams。

2 目标应用

MobiStreams的设计受到交通领域中SignalGuru手机应用的启发，SignalGuru可以预测交叉路口红绿灯的转换时间，并向司机建议最优行驶速度以便到达路口时亮绿灯。车辆通过这种方式可以在通过路口时一路通行，从而降低耗油量。SignalGuru利用了挡风玻璃上安装的智能手机，当手机靠近交叉路口时抓拍路口图片，然后通过ad-hoc WiFi网络与附近的手机共享图片，并一起学习信号转换模式。SignalGuru的核心是通过颜色(红、黄、绿)滤波、形态(圆圈，箭头)滤波、和运动滤波(交通灯总是在路边)从图片中检测出交通信号的图像处理算法。然后，利用支持向量机训练和预测转换模式。路口车辆上的智能手机运行DSPS系统时就是执行上述步骤。预测结果发送给道路上的下个路口，以便司机提前知道交通信号转换时间。DSPS系统在每个路口的运行方式见图1。摄像头数据发送给S1，每个元组包含一个图片。先前路口的数据发送给S0，每个元组包含预测的交通信号转换时间。这些时间将被广播给所有附近智能手机。

图1 SignalGuru应用示例

图1 SignalGuru应用中每个交叉口的DSPS系统，具有同一颜色的操作程序位于同一节点上。其中，S0：上一路口的数据，S1：智能手机摄像头数据，C：颜色滤波器，A：形态滤波器，M：运动滤波器，V：投票滤波器，G：组群，P：SVM预测，K：汇点(到下一路口)。在多个路口执行计算任务，DSPS系统运行于每个区域的智能手机上。不同区域的DSPS系统互相接力，即一个区域中DSPS系统的结果传递给下个区域的DSPS系统，提高了应用的覆盖范围。这个应用的结构促使我们设计MobiStreams。

3 MobiStreams的设计

MobiStreams系统的设计采用双层架构，如图2所示。其中，MobiStreams系统的高层架构可用一个有向非周期图来表示。图中的每个节点表示一个区域，箭头表示区域间的网络连接和数据流方向。MobiStreams的低层架构主要是每个区域的微结构，区域内通过ad-hoc WiFi相连的智能手机可认为是一个集群，每个智能手机就是集群中的一个节点，在每个区域的集群上运行DSPS。除了区域和智能手机外，MobiStreams系统还需要一个控制器，一种可通过蜂窝网络与区域内所有智能手机连接的服务器节点。

3.1 智能手机故障检测

MobiStreams周期性地检测每个区域的DSPS状态，采用一种新的检测点策略，通过信标来协调多个智能手机的行为，当智能手机在区域内发生突然故障，系统依靠控制器来ping每个区域内的源节点。若源节点在预定时间内无回复，则认为发生故障。每个区域内的计算节点和汇点由它们的上游相邻节点监测，若一个节点发现其下游相邻节点故障，则通过网络迅速向控制器汇报。除了下游相邻节点的故障外，节点也可非常活跃地将自己的故障汇报给控制器，如当其电池电量较低时的汇报。

图2 MobiStreams双层架构

3.2 低可靠性无线网络的检测

在检测期间，节点的状态及区域的输入数据必须存储在输出节点上，即使节点故障也可保证检测的稳定性。基于服务器的DSPS系统是在可靠性高、速度快的以太网上进行检测，但本文中检测点的保存必须依托于可靠性低、速度慢、带宽窄的ad-hoc WiFi网络。MobiStreams通过基于高可靠性和低可靠性数据传输的多阶段广播策略解决这一问题。

前几个阶段采用UDP协议。节点的检测数据分为多个1KB数据块(最后一个数据块低于1KB)。节点发送的每个UDP报文包含一个数据块，及表示运行于节点上的操作程序ID的数据块描述符，该检测点的版本以及该数据块的序号。数据块描述符很小，因此报文尺寸仍然为1KB左右。之所以采取小规模报文，是因为大规模UDP报文在进行报文分割时容易受到有损网络的影响。在接收器端，每个节点记录接收到的报文，根据UDP的数据报属性，UDP协议维持报文间的边界，只要有部分报文未被接收到，则整个报文就被丢弃。所有报文广播完毕后，发送方询问接收节点哪些报文被接收到，每个接收方返回一个位图，每一位表示相应消息被丢失(0)还是接收到(1)。位图中的位数因此等于发送方广播的消息数量。根据所有接收方的位图，发送方可以推断广播期间被丢失的消息(未被任何接收方接收到的消息)。发送方然后再次广播丢失消息，重复上述广播和询问过程，直到成本超过收益，成本和收益的概念从发送或接收到的字节数量角度定义。

图3详细描述了MobiStreams的多阶段广播过程。区域内有4个节点。发送节点的检测点数据规模为8MB (8192个消息)。

图3 包括4个智能手机的区域的UDP广播

在时刻1，发送方向节点A, B和C广播所有消息M1,…,M8192。在时刻2，发送方结束对接收方的广播和询问过程。节点A只接收到前3个消息，因此返回首部只有3个1的位图。节点B接收到所有偶数消息，因此返回0和1交叉的位图。节点C接收到所有奇数消息，因此返回1和0交叉的位图。每个位图的规模为1KB。发送方可利用这些位图进行一些计算。(1)发送方对所有位图进行AND操作，获得只包含0的位图，换句话说，每个消息至少有一个接收器未接收到。(2)发送方计算接收方接收到的字节数量。节点A, B和C接收到的字节数量分别为3KB, 4096KB和4096KB。因此，总数为8195KB。(3)发送方评估广播增益，将其计算为广播之前和之后接收到的字节数量。在广播之前，接收到的字节数量为0。因此，广播增益为8195KB个接收字节。(4)接收方计算广播成本。它已经发送了8192个消息，接收到3个位图消息，总成本是通过网络传输8195KB个消息。因为成本(8195KB)小于等于增益(8195KB)，所以发送方开始在时刻3进行第2次广播。

根据时刻2的ANDed位图，每个消息必须被重发。然后，发送方再次广播所有消息。在时刻4，发送方完成第2次广播，获得返回的位图。节点A和B接收到所有消息，因此它们返回全由1组成的位图。节点C在第2次广播时未接收到任何消息。其返回位图与上次相同。发送方利用这些位图进行相同的计算步骤。ANDed位图为1010..，表示所有偶数消息必须重传。接收到的字数总数量为20480KB。第2次广播的增益为新接收到12285KB个消息，成本为通过网络传输8195KB个消息。因为成本(8195KB)不大于增益(12285KB)，所以发送方在时刻5开始第3次广播。根据时刻4时的ANDed位图，只有偶数消息M2,M4,…,M8192被重传。在时刻6，节点C返回一个位图，表示它已经接收到除了M2的所有消息。根据相同的算法步骤，第3次广播的增益为4095KB，成本为4099KB。因此，发送方最终终止UDP广播。

UDP广播无法保证每个节点接收到所有的检测点数据。因此，引入基于可靠TCP协议的额外步骤。在该步骤中，区域内的所有节点组织为一个树。发送方也是树中的一个节点。首先从发送方开始向根节点传输数据，然后从根节点向叶节点传输。由控制器创建树结构，只当手机故障、进入或离开区域时树结构才会变化。

3.3 机动性检测

本文迄今假设智能手机在区域内静止不动，即手机进入区域后不会离开。下面进一步考虑智能手机移动情景。如图4所示，计算节点(节点D)离开区域。当D不在区域内时，节点D、B和E间的距离较大，它们之间的WiFi连接中断。然后，这些节点切换到紧急模式，采用蜂窝网络来发送元组，如图4时刻2所示。节点D、B和E向控制器汇报紧急模式。根据节点D的GPS，控制器知道节点D正在离开。然后，控制器选择区域内的另一节点替换节点D。此时，控制器选择节点F，命令D在时刻3通过蜂窝网络将其状态发送给F。一旦节点F的状态与D相同，控制器命令节点B、F和E来在时刻4重建WiFi连接。此后，该区域的DSPS系统返回正常模式，继续处理元组。离开区域的节点将在控制器处注销。这里有一种特殊情况需要特别介绍。在时刻2处，如果节点D的GPS汇报节点D仍在区域内，则有两种可能：(1)由于受到干扰，WiFi连接中断，而不是节点离开；或者(2)GPS不准确。控制器因此命令节点D、B和E暂时重建WiFi连接。如果它们在几次尝试后无法成功，则认为节点D确实离开了区域。

图4 智能手机离开时触发的行为

如果多个节点同时离开区域，则DSPS的结构仍可保持在紧急模式，但是节点间的部分网络连接将依靠蜂窝网络。该区域的DSPS可继续工作，但性能将会下降，一直持续到控制器替换了离开节点。如果部分节点离开之后区域内没有足够多的剩余节点，则控制器停止该区域的计算任务，连接该区域的上游和下游相邻节点(绕过该区域)。如果源节点或汇点离开区域，则控制器选择区域内的另一节点来替换它。因为源节点和汇点为无状态节点，所以没有必要将其状态从离开节点状态转换为新选择节点状态。然而，控制器必须命令新选择的节点相应地重建跨区域连接。如果有空闲节点离开(GPS检测出来)，则它向控制器注销自己(unregister)，删除上面存储的所有检测点数据。

4 实验评估

将MobiStreams作为iOS顶层的中间件加以部署，同时将预测交叉路口红绿灯的转换时间应用作为DSPS系统进行部署。

4.1 MobiStreams和基于服务器的DSPS

表1给出了比较结果。一个手机故障表明有个手机停止工作，手机离开表示一个手机离开区域，且离开手机的状态必须传输给区域内的另一个手机。

其中MobiStreams1为容错功能关闭，MobiStreams2 为容错功能开启且手机每5分钟离开其区域，MobiStreams3为容错功能开启且手机每5分钟故障。在这些场景中，MobiStreams的性能均优于基于服务器的DSPS。

表1 Mobistreams与基于服务器的DSPS比较

4.2 不同算法的性能比较

为了验证MobiStreams的优越性，本文定义如下容错算法并与其做比较：(1)不支持容错的baseline算法(base)；(2)活跃备用算法(rep-2)；(3)本地检测点算法(local)；(4)分布式检测算法(dist-n)。

为了评估恢复开销，在场景中引入手机故障和离开事件。图5(BCP汽车容量预测和Signal Guru预测交叉路口红绿灯的转换时间)给出了在一个检测周期内有n个节点故障或离开时相关应用的性能。图5中的延时和吞吐量包括应用的停机时间和恢复时间。在该图中有三大发现。首先，无论多少个节点故障，MobiStreams总是能够恢复DSPS中的所有节点。因此，当故障节点数量上升时，故障恢复开销恒定。可以看出，MobiStreams的性能曲线(ms-8手机故障)为一条水平线。其次，dist-n的性能曲线只有n+1个点，因为它只能处理n个节点故障。rep-2的曲线只包含两个点，因为它只能处理单节点故障。rep-2和dist-n的性能远低于MobiStreams，当n变大时，dist-n的性能下降。在SignalGuru中，dist-3的曲线只包含1个点，因为它无法在5分钟内恢复系统。最后，MobiStreams的节点离开开销低于rep-2和dist-n的故障恢复开销，且在大部分情况下低于MobiStreams的故障恢复开销。这在预料之中。节点故障比节点离开复杂，因为故障会触发恢复和补救，而节点离开只需要状态传输。然而，当同时离开的手机数量较大时(图5第2个子图)，MobiStreams的离开开销可能超过故障恢复开销。笔者认为这是因为状态传输需要使用蜂窝网络通信，当许多手机同时使用蜂窝网络时，网络便会影响总体性能。因为先前的容错算法无法处理节点离开事件(它们的设计着眼于服务器)，所以只对MobiStreams进行节点离开实验。

图5 在一个检测周期内发生一次n个节点故障或离开时的相对吞吐量和延时

5 结束语

针对在智能手机上部署DSPS系统时面临的智能手机故障、低可靠性无线网络、智能手机移动情境等挑战，提出一种容错的分布式流处理系统，该系统缓解了蜂窝网络的压力。最后的仿真实验验证了该系统的有效性和性能的优越性。下一步工作的重点是对不同场景下的智能手机数据传输可靠性问题进行分析，进一步提升智能手机的应用性能。

[1]谌国风,孔俊俊,郭耀,等.一种智能手机上下文信息获取的代价模型及其应用[J].计算机科学,2014,41(11):132-136

[2]谷琼,李杰,龚雄兴.基于Android智能手机的隐私管理系统的设计与实现[J].计算机应用与软件,2014,31(1):260-263

[3]薛建彬,何凤婕.基于业务量感知的蜂窝网络中继站协作控制机制[J].兰州理工大学学报,2014,40(4):105-109

[4]林启中,张冬梅,许魁,等.蜂窝网络中M2M通信上行接入资源分配[J].应用科学学报,2015,33(2):129-141

[5]朱近康，许莉.绿色蜂窝网络的频谱效率与能效函数[J].通信学报，2013,34(1)：1-7

[6]王飞，许魁，徐友云，等.大数据无线通信面临的几点挑战与对策[J].电子技术应用，2015,41(3):12-16

[7]杨亚让,赵越.OFDMA多跳中继蜂窝网络的干扰协调策略[J].铁道学报,2015,37(1):44-50

[8]Nabi Z，Wagle R，Bouillet E.The best of two worlds:Integrating IBM InfoSphere Streams with Apache YARN[C]//2014 IEEE International Conference on Big Data.Beijing China: IEEE Press,2014:47-51

[9]Xhafa Fatos，Naranjo Victor，Caballe Santi.Processing and Analytics of Big Data Streams with Yahoo! S4[C]//2015 IEEE 29th International Conference on Advanced Information Networking and Applications.Gwangju Korea:IEEE Press,2015:263-270

[10]Botan I，Younggoo Cho，Derakhshan R，et al.A demonstration of the MaxStream federated stream processing system[C]//2010 IEEE 26th International Conference on Data Engineering.California USA:IEEE Press,2010:1093-1096

(责任编辑：汪材印)

10.3969/j.issn.1673-2006.2015.11.028

2015-08-21

安徽省质量工程教学团队项目“计算机网络技术专业教学团队”(2014jxtd099)。

任海鹏(1979-)，安徽芜湖人，硕士，讲师，主要研究方向：数据通信与无线网络．

TP393

A

1673-2006(2015)11-0107-05