(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210944815.X (22)申请日 2022.08.08 (71)申请人 浙江移动信息系统集成有限公司 地址 311215 浙江省杭州市萧 山区萧山经 济技术开 发区桥南区块高新七路77号 5幢3层 (72)发明人 钱军波　汤人杰　王清　陈俊杰　 (51)Int.Cl. G06F 9/50(2006.01) (54)发明名称 一种分布式计算中缓存自适应索引机制及 查询方法 (57)摘要 本发明涉及数据库和分布式计算框架技术 领域， 特别涉及一种分布式计算中缓存自适应索 引机制及查询方法， 本发明包 括步骤1‑1， 初始化 节点间的访问概率矩阵； 步骤1 ‑2， 根据任务图进 行任务分发， 按照概率矩阵发送至相应节点； 步 骤1‑3， 收集阶段性访问指标； 步骤1 ‑4， 根据自适 应调整算法调整节点访问概率矩阵， 并回到步骤 1‑2， 本发明提供的一种分布式计算中缓存自适 应索引机制及查询方法， 能够在每f轮对索引结 构进行动态调整， 在查询阶段， 根据相关约束条 件选择合适的节点分发任务， 提高缓存利用率， 使得集群整体负载均衡 。 权利要求书3页 说明书11页 附图7页 CN 115185698 A 2022.10.14 CN 115185698 A 1.一种分布式计算中缓存自适应索引机制， 其特 征在于， 包括如下步骤： 步骤1‑1， 初始化节点间的访问概 率矩阵； 步骤1‑2， 根据任务图进行任务分发， 按照概 率矩阵发送至相应节点； 步骤1‑3， 收集阶段性访问指标； 步骤1‑4， 根据自适应调整算法调整节点访问概 率矩阵， 并回到步骤1 ‑2。 2.根据权利要求1的一种分布式计算中缓存自适应索引机制， 其特征在于， 所述步骤1 ‑ 1中， 基于节点间访问概 率矩阵， 所述 概率矩阵的构建步骤为： 步骤1‑1‑1， 集群中存在n个节点， 节点访问概率矩阵m是一个n*n大小的矩阵， 其中定义 mij为节点i有数据向节点j转移， mij∈[0， 1]； 步骤1‑1‑2， 若mij≠0表示节点i在每一轮计算中都有数据传输到节点j， 若mij＝0， 则表 示节点i数据未曾传输 到节点j； 步骤1‑1‑3， 使用邻接矩阵， 可表示为一个有向图， 结点表示节点， 边的权值表示节点间 访问概率， 其中， 如果两点间的权值小于 0.5， 则两点间不存在边。 3.根据权利要求2的一种分布式计算中缓存自适应索引机制， 其特征在于， 所述步骤1 ‑ 1中的节点访问概率矩阵的初始化阶段历史数据为空， 没有节点的权值mij≥0.5， 相应有向 图只存在N个结点。 4.根据权利要求1的一种分布式计算中缓存自适应索引机制， 其特征在于， 在所述索引 机制中步骤1 ‑3中， 阶段性访问指标构建步骤为： 步骤1‑3‑1， 在集群次完成计算任务， 将计算框架执 行信息本地化保存； 步骤1‑3‑2， 分类本地保存的文件， 包括： 每轮计算完成时间、 节点间访问关系、 每轮计 算任务DAG图、 task及executor、 RD D数据分布； 步骤1‑3‑3， 读取本地文件， 过滤语句， 提取节点的性能参数、 任务的调度关系、 缓存数 据存储情况、 节点之间访问关系。 5.根据权利要求1的一种分布式计算中缓存自适应索引机制， 其特征在于， 在结合所述 索引机制中步骤1 ‑4， 索引自适应调整算法 的输入为调整轮数f、 历史数据、 以及概率矩阵， 索引自适应调整算法算法的步骤为： 步骤1‑4‑1， 每f轮计算任务后， 查看本地历史数据任务完成时间， 确定是否调整节点访 问概率矩阵； 步骤1‑4‑2， 分析历史信息中的每 轮计算任务图， 步骤1‑4‑3， 若第i轮的计算任务与第j轮的计算任务相同， 则不调整索引， 继续分析第k 轮的计算任务， 依次判断执 行； 步骤1‑4‑4， 若第i轮与第j轮的计算任务不同， 按照节点间 的访问关系调整矩阵， 即， 若 节点a有数据传输 到节点b， 则 步骤1‑4‑5， 发生冲突 时， 即pij＝pik＝1， 初始化该行矩阵数值为1/n ‑1， 返回步骤1 ‑4‑2 继续调整矩阵直至分析 结束。 6.一种分布式计算中缓存自适应索引机制的查询方法， 其特 征在于， 包括如下步骤：权　利　要　求　书 1/3 页 2 CN 115185698 A 2步骤2‑1， 初始阶段查看历史数据本地文件中初始task的Locality  Level参数， 即最优 处理位置； 步骤2‑2， 在确定任务初始阶段节点后， 根据有向图分发任务， 如果结点i在有向图中指 向了结点j， 将节点i上任务的后续任务分发到节点j上， 若待分配任务的节点的性能p大于 等于95％， 则不再分配； 步骤2‑3， 计算节点 性能评价指标， 并计算各节点 性能指标排序结果； 步骤2‑4， 根据待分配的任务计算任务关键程度， 并得到任务关键度排序结果， 最后根 据节点性能指标和任务关键程度值计算任务分配的节点。 7.根据权利要求6的一种分布式计算中缓存自适应索引机制的查询方法， 其特征在于， 在步骤2‑3中， 节点 性能评价指标针对CPU、 内存、 I/O和网络带宽的利用率进行计算。 8.根据权利要求7的一种分布式计算中缓存自适应索引机制的查询方法， 其特征在于， 在所述步骤2‑3中， 计算节点 性能评价指标， 并计算各节点 性能指标排序结果， 具体步骤为： 步骤2‑3‑1， 通过对集群中主从节点在一段时间内的CPU采样信息计算节点的CPU利用 率， 采样信息为单轮 计算任务时间段内的计算机节点相关参数， 其中， CPUfree为CPU空闲时间(CPUfree＝Time2_F ‑Time1_F)， CPUTotal为CPU总执行时 间变化(CPU Total＝C2‑C1)， CPU总执行时间包括： Time_F为空闲时间(Free)， Time_U为用户占用时间(User)， Time_ N为改变优先级进程时间(Nice)， Ti me_S为内核占用时间(System)， Time_IOW为I O等待占用 时间(IOWaiti ng)， Time_IRQ 为硬中断占用时间， Time_SIRQ 为软中断占用时间， C2＝Time2_U+Time2_N+Time2_S+Time2_F+Time2_IOW+Time2_IRQ+Time2_SIRQ， C1＝Time1_U+Time1_N+Time1_S+Time1_F+Time1_IOW+Time1_IRQ+Time1_SIRQ， CPUusage为CPU利用率， 计算公式为 步骤2‑3‑2， 通过集群中主节点的内存使用情况计算内存利用率， 计算公式为： 步骤2‑3‑3， 通过单轮计算任务时间段内的I/O操作计算一段 时间内系统进行读写操作 的利用率， 计算公式为 其中， R_S为每一秒完成的读操作的次数， W_S为每一秒完成的写操作的次数， SVCTM为 每次I/O请求处 理的平均时间， IOusa ge值越大说明I/O负载越大； 步骤2‑3‑4， 在预定时间内， 通过系 统进行输出与输入数据量的总和与带宽的比， 计算 网络带宽综合利用率， 公式为 其中， Time＝Time2 ‑Time1(单位是秒)， Time2为单轮计算任务结束的时间， Time1为任权　利　要　求　书 2/3 页 3 CN 115185698 A 3