大规模流数据处理中代价有效的弹性资源分配策略

doi:10.13229/j.cnki.jdxbgxb20190042

Abstract

Abstract:

In large-scale stream processing, resource reconfiguration in strict synchronization with changes in the stream data can guarantee the performance of application, however the resource reconfiguration cost of the system is relatively higher. Based on the idea of resource reservation and combining with the load forecasting model, this paper designs two proactive elastic resource allocation strategies from heuristic and intelligent perspective respectively, which aim to minimize the application reconfiguration cost and maximize the resource utilization. Both strategies calculate the latency of the application in the pipelined processing mode, and probabilistically guarantee the constraint of the application latency performance. Among them, the heuristic strategy uses the local threshold method for resource allocation, and the intelligent strategy adaptively allocates resources based on the reinforcement learning technology. Experimental results show that compared with the reactive strategies, these two proactive resource allocation strategies proposed in this paper both have low reconfiguration cost and high resource utilization, and the performance of the intelligent strategy is better, especially when the change of sudden load is relatively stable.

Key words: computer architecture, stream data processing, resource allocation, elastic adjustment, reinforcement learning

CLC Number:

TP391

Li-na LI,Xiao-hui WEI,Lin-lin HAO,Xing-wang WANG,Chu WANG. Cost⁃effective elastic resource allocation strategy in large⁃scale streaming data processing[J].Journal of Jilin University(Engineering and Technology Edition), 2020, 50(5): 1832-1843.

Figures/Tables 7

Table 1

Initial state of lookup table"

延迟阈值百分比区间	收缩	不变	扩展
（0%，10%）	1.00	0.50	0.40
[10%，20%）	0.95	0.60	0.45
[20%，30%）	0.90	0.66	0.50
[30%，40%）	0.80	0.75	0.55
[40%，50%）	0.75	0.80	0.65
[50%，60%）	0.70	0.85	0.72
[60%，70%）	0.65	0.88	0.76
[70%，80%）	0.60	0.90	0.80
[80%，90%）	0.50	0.95	0.84
[90%，100%）	0.45	0.80	0.90
[100%，+ $∞$ ）	0.40	0.60	1.00

Table 1

Fig.1

Fig.2

Fig.3

Fig.4

Fig.5

Fig.6

References 19

1	Pitman A, Zanker M. Insights from applying sequential pattern mining to E-commerce click stream data[C]∥IEEE International Conference on Data Mining Workshops, Sydney, NSW, 2010: 967-975.
2	Schnitzler F, Artikis A, Weidlich M, et al. Heterogeneous stream processing and crowdsourcing for traffic monitoring: highlights[C]∥Joint European Conference on Machine Learning and Knowledge Discovery in Databases, Nancy, France, 2014: 520-523.
3	Verma A, Kumar G, Koller R. The cost of reconfiguration in a cloud[C]∥International Middleware Conference Industrial Track, New York, NY, USA, 2010: 11-16.
4	Luo Z, Qian Z. Burstiness-aware server consolidation via queuing theory approach in a computing cloud[C]∥IEEE International Symposium on Parallel & Distributed Processing, Boston, MA, USA, 2013: 332-341.
5	Sutton R S, Barto A G. Reinforcement Learning: An Introduction[M]. MIT Press, 1998.
6	Kumbhare A G, Simmhan Y, Frincu M, et al. Reactive resource provisioning heuristics for dynamic dataflows on cloud infrastructure[J]. IEEE Transactions on Cloud Computing, 2015, 3(2): 105-118.
7	De Matteis T, Mencagli G. Keep calm and react with foresight: strategies for low-latency and energy-efficient elastic data stream processing[C]∥Principles and Practice of Parallel Programming, Barcelona, Spain, 2016: 1-12.
8	李丽娜, 魏晓辉, 李翔, 等. 流数据处理中负载突发感知的弹性资源分配[J]. 计算机学报, 2018, 41(10): 2193-2208.
	Li Li-na, Wei Xiao-hui, Li Xiang, et al. Burstiness-aware elastic resource allocation in stream data processing[J]. Chinese Journal of Computers, 2018, 41(10): 2193-2208.
9	Das R, Tesauro G J, Walsh W E. Model-based and model-free approaches to autonomic resource allocation[J/OL]. [2005-11-16].
	gate.net/publication/246843416_Model-Based_and_Model-Free_Approaches_to_Autonomic_Resource_Allocation
10	Tesauro G. Online resource allocation using decompositional reinforcement learning[C]∥Proc of AAAI, Pittsburgh, Pennsylvania, 2005: 886-891.
11	Tesauro G, Jong N K, Das R, et al. A hybrid reinforcement learning approach to autonomic resource allocation[C]∥IEEE International Conference on Autonomic Computing, Dublin, Ireland, 2006: 65-73.
12	Dutreilh X, Rivierre N, Moreau A, et al. From data center resource allocation to control theory and back[C]∥IEEE International Conference on Cloud Computing, Miami, USA, 2010: 410-417.
13	Dutreilh X, Kirgizov S, Melekhova O, et al. Using reinforcement learning for autonomic resource allocation in clouds: towards a fully automated workflow[C]∥International Conference on Autonomic and Autonomous Systems, Venice, Italy, 2011: 67-74.
14	Heinze T, Pappalardo V, Jerzak Z, et al. Auto-scaling techniques for elastic data stream processing[C]∥Proceedings of the 30th IEEE International Conference on Data Engineering Workshops. Chicago, Illinois, USA, 2014: 318-321.
15	Heinze T, Ji Y, Pan Y, et al. Elastic complex event processing under varying query load[C]∥International Workshop on Big Dynamic Distributed Data, Trento, Italy, 2013: 25-30.
16	Cardellini V, Presti F L, Nardelli M, et al. Auto-scaling in data stream processing applications: a model-based reinforcement learning approach[C]∥Workshop on New Frontiers in Quantitative Methods in Informatics, Venice, Italy, 2017: 97-110.
17	Wei X, Li L, Li X, et al. Pec: proactive elastic collaborative resource scheduling in data stream processing[J]. IEEE Transactions on Parallel and Distributed Systems, 2019, 30(7): 1628-1642.
18	Bitran G R, Morabito R. State-of-the-art survey: open queueing networks: optimization and performance evaluation models for discrete manufacturing systems[J]. Production and Operations Management, 1996, 5(2): 163-193.
19	Leskovec J, Backstrom L, Kleinberg J. Meme-tracking and the dynamics of the news cycle[C]∥International Conference on Knowledge Discovery and Data Mining, Paris, France, 2009: 497-506.

Related Articles 15

[1]	Hao-tian WU,Rui-feng GUO,A-zhen PENG,Pin WANG. A low power scheduling algorithm based on constant bandwidth server considering reliability [J]. Journal of Jilin University(Engineering and Technology Edition), 2020, 50(5): 1802-1808.
[2]	Yi LIU,Ling-ling XIAO,Gai-jing WANG,Wu-jun ZHANG. Resource allocation algorithm based joint optimization for D2D communications in cellular networks [J]. Journal of Jilin University(Engineering and Technology Edition), 2020, 50(1): 306-314.
[3]	Shun YANG,Yuan⁃de JIANG,Jian WU,Hai⁃zhen LIU. Autonomous driving policy learning based on deep reinforcement learning and multi⁃type sensor data [J]. Journal of Jilin University(Engineering and Technology Edition), 2019, 49(4): 1026-1033.
[4]	JIANG Lai-wei, SHA Xue-jun, WU Xuan-li, ZHANG Nai-tong. Novel joint user association and resource allocation method in LTE-A HetNets [J]. 吉林大学学报(工学版), 2017, 47(6): 1926-1932.
[5]	WEI Xiao-hui, LIU Zhi-liang, ZHUANG Yuan, LI Hong-liang, LI Xiang. Adaptive checkpoint mechanism supporting large-scale stream data processing [J]. 吉林大学学报(工学版), 2017, 47(1): 199-207.
[6]	ZHAO Xiao-hui, YANG Wei-wei, JIN Xiao-guang. Resource allocation algorithm for different delay traffic in relay-based OFDM systems [J]. 吉林大学学报(工学版), 2015, 45(6): 2049-2055.
[7]	DONG Yue-li, GUO Quan, SUN Bin, KANG Ling. Dynamic task migration optimization for molecule docking [J]. 吉林大学学报(工学版), 2015, 45(4): 1253-1259.
[8]	TANG Rui-chun, QIU Yue, DING Xiang-qian, LI Jing. Cloud media resource allocation algorithm based on utility maximization negotiation [J]. 吉林大学学报(工学版), 2015, 45(3): 932-937.
[9]	ZHANG Qing-feng,XU Jing,LI Shan-shan. Interaction-aware parallel query scheduling strategy [J]. 吉林大学学报(工学版), 2015, 45(1): 252-260.
[10]	CHEN Jian,FAN Guang-hui,KUO Yong-hong. Hierarchical optimization algorithm for resource allocation in relay-assisted cognitive radio network [J]. 吉林大学学报(工学版), 2014, 44(5): 1498-1505.
[11]	DONG Bo,LIU Ke-ping,LI Yuan-chun. Decentralized reinforcement learning optimal control for time varying constrained reconfigurable modular robot [J]. 吉林大学学报(工学版), 2014, 44(5): 1375-1384.
[12]	REN Xiang-long, GAO De-yuan, FAN Xiao-ya, AN Jian-feng. Analysis of delay bounds for NoC based on improved asymmetric multi-channel router [J]. 吉林大学学报(工学版), 2014, 44(3): 782-787.
[13]	YE Jin-hua,LI Di,YE Feng. Dual reinforcement learning adaptive fuzzy control of wheeled mobile robot [J]. 吉林大学学报(工学版), 2014, 44(3): 742-749.
[14]	LIU Yan-heng, ZHOU Peng, WANG Jian, DENG Jun-yi. Context-aware adaptive middleware in vehicular network [J]. 吉林大学学报(工学版), 2013, 43(02): 410-416.
[15]	GUO Zhen-hua, WU Yan-xia, ZHANG Guo-yin, YANG Jie, GU Guo-chang. Basic block-level pointer analysis algorithm for C2VHDL compiler [J]. 吉林大学学报(工学版), 2013, 43(02): 417-423.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

Comments

Recommended 0

No Suggested Reading articles found!

Cost⁃effective elastic resource allocation strategy in large⁃scale streaming data processing

RICH HTML

PDF (PC)