一种基于最大流的分布式存储系统中查询任务最优分配算法

摘要：

分布式存储系统多采用数据分区和多副本机制来处理海量数据并提供高可用性.为了提高读写效率,现有系统在将任务分发给不同节点时往往需要考虑数据分区的情况,并使得任务分配能够保证数据本地性.然而,给定一个需要访问多个数据分区的查询任务,现有系统没有充分考虑节点的实际负载情况,导致虽然任务的分配满足数据本地性,但集群查询响应速度仍受到制约.该文提出一种在分布式存储系统中查询任务的节点分配算法,该算法不仅考虑了数据本地性,还利用了多副本机制确保节点间的负载均衡.算法的基本思想是将任务分配问题转化为最大流问题,并通过二分查找寻求最优分配方案.在实验阶段,该文首先通过模拟实验验证该算法的正确性,之后将该算法集成到Cassandra中作为一种新的负载均衡策略,并与Cassandra原生的两种策略进行性能对比.实验证明,该文提出的算法使得查询性能优于Cassandra原生的策略,平均查询时间缩短为原有策略的50％,某些情况下可以缩短为11％.

关键词：数据分区、数据本地性、查询优化、最大流、负载均衡、分布式存储系统

所属期刊栏目：42

分类号：TP311(计算技术、计算机技术)

资助基金：国家重点研发计划项目2016YFB1000701;国家自然科学基金61802224,U1509213;北京市科委创新基地培育与发展专项Z171100002217096;教育部博士后科学基金2017M620784

在线出版日期：2019-09-23（万方平台首次上网日期，不代表论文的发表时间）

页数：共15页

页码：1858-1872