Economical and Fault-Tolerant Load Balancing in Distributed Stream Processing Systems

Fuyuan XIAO  Teruaki KITASUKA  Masayoshi ARITSUGI  

IEICE TRANSACTIONS on Information and Systems   Vol.E95-D   No.4   pp.1062-1073
Publication Date: 2012/04/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E95.D.1062
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Data Engineering, Web Information Systems
distributed data stream processing systems (DDSPSs),  load balancing strategy,  fault-tolerance,  economical operator distribution (EOD),  

Full Text: PDF(614.4KB)>>
Buy this Article

We present an economical and fault-tolerant load balancing strategy (EFTLBS) based on an operator replication mechanism and a load shedding method, that fully utilizes the network resources to realize continuous and highly-available data stream processing without dynamic operator migration over wide area networks. In this paper, we first design an economical operator distribution (EOD) plan based on a bin-packing model under the constraints of each stream bandwidth as well as each server's CPU capacity. Next, we devise super-operator (SO) that load balances multi-degree operator replicas. Moreover, for improving the fault-tolerance of the system, we color the SOs based on a coloring bin-packing (CBP) model that assigns peer operator replicas to different servers. To minimize the effects of input rate bursts upon the system, we take advantage of a load shedding method while keeping the QoS guarantees made by the system based on the SO scheme and the CBP model. Finally, we substantiate the utility of our work through experiments on ns-3.