一种大数据环境下的动态路由查询方法与流程

摘要: 本发明涉及分布式数据存储与查询,具体而言,尤其涉及一种大数据环境下的动态路由查询方法。背景技术:1、随着大数据技术在电子商务、物联网设备数据采集以及分布式存储系...
一种大数据环境下的动态路由查询方法与流程

本发明涉及分布式数据存储与查询,具体而言,尤其涉及一种大数据环境下的动态路由查询方法。

背景技术:

1、随着大数据技术在电子商务、物联网设备数据采集以及分布式存储系统中的广泛应用,海量数据通常需要按照特定路由键分散存储于分布式集群内的多个物理节点上以实现存储容量与访问处理能力的水平扩展,现有的路由查询方法普遍采用哈希取模划分或者范围划分的方式建立路由键到物理节点的映射规则,即预先设定固定数量的哈希桶或者固定的区间边界,客户端发起的读写请求经由该映射规则被路由控制模块定位到对应的物理节点,该类映射规则一旦在系统初始化阶段确定,后续运行过程中通常保持不变,路由请求的处理路径完全依赖预先设定好的静态规则完成。

2、然而,实际生产环境中数据在各路由键上的分布特征以及各路由键对应的访问频次会随着业务发展持续发生变化,当某一路由键对应的数据存储规模或者访问请求频次显著超过其他路由键时,负责承载该路由键的物理节点即成为整个系统的性能瓶颈,形成数据倾斜问题,现有技术针对该问题通常在路由机制之外单独增加统计模块,通过异步方式采集各节点的负载数据并在检测到倾斜后触发人工预设阈值的再均衡操作,该类方案存在统计模块与路由计算路径相互独立导致的数据滞后与口径不一致问题,存在人工预设阈值本身依然固定不变导致响应能力受限的问题,存在未区分数据存储规模倾斜与访问频次倾斜两类不同性质问题而采用同一套处理机制导致不必要资源开销的问题,还存在路由规则调整过程依赖停机窗口或者复杂双写机制导致对上层业务存在侵入性的问题,上述问题共同表明现有技术尚未能够从路由机制本身出发解决数据倾斜问题,而是依赖外部补救措施对已经发生的倾斜进行事后处理。

技术实现思路

1、本发明的目的在于提供及一种大数据环境下的动态路由查询方法,以解决现有技术存在的问题。

2、本发明提供了一种大数据环境下的动态路由查询方法,包括以下步骤:路由控制模块接收客户端发起的路由请求,从路由请求中解析出对应的路由键;路由控制模块依据路由键在槽位树数据结构中执行定位计算,沿槽位树数据结构从根节点向下逐层比对哈希取值区间或范围区间,确定路由键所归属的叶子槽位;路由控制模块在完成定位计算的同一次请求处理过程中,对叶子槽位所挂载的双通道统计结构执行增量更新,其中存储量通道针对写入类请求采用概要数据结构对叶子槽位当前承载的数据条目规模执行插入操作,访问量通道针对读请求和写请求按照公式一执行指数加权移动平均更新:,其中,ai(t)表示叶子槽位i在第t个统计周期结束时刻的访问量通道估计值,ci(t)表示叶子槽位i在第t个统计周期内接收到的路由请求次数,ai(t−1)表示叶子槽位i在上一个统计周期结束时刻的访问量通道估计值,α为衰减系数且取值范围为大于零且小于一的实数;路由控制模块判断是否满足决策评估触发条件,决策评估触发条件包括固定统计周期到达的周期性触发条件和单次访问量通道估计值超过预设突变阈值的事件驱动触发条件;若满足决策评估触发条件,路由控制模块读取叶子槽位以及与叶子槽位处于槽位树数据结构同一父节点之下的兄弟槽位各自的存储量通道估计值和访问量通道估计值,按照公式二计算叶子槽位的综合负载失衡系数:,其中,φi表示叶子槽位i的综合负载失衡系数,si表示叶子槽位i的存储量通道估计值,s表示兄弟槽位存储量通道估计值的算术平均值,ai(t)表示叶子槽位i在第t个统计周期的访问量通道估计值,a表示兄弟槽位访问量通道估计值的算术平均值,w1与w2分别为存储量通道和访问量通道对应的权重系数且二者之和为一;若综合负载失衡系数超过预设失衡阈值,路由控制模块将叶子槽位的标识连同综合负载失衡系数输入在线学习决策器,在线学习决策器针对分裂、合并、复制以及维持不变四类候选动作分别按照公式三计算置信上界评分,并选取评分最高的候选动作作为执行动作:,其中,ui,a表示叶子槽位i对候选动作a的置信上界评分,ri,a表示候选动作a在叶子槽位i历史执行记录中的平均负载改善回报,平均负载改善回报由候选动作执行前后综合负载失衡系数的下降幅度折算得到,ni,a表示候选动作a在叶子槽位i上历史累计被选中执行的次数,ni表示叶子槽位i累计触发决策评估的总次数,c为探索系数;若执行动作为分裂或合并,路由控制模块对槽位树数据结构执行相应的分裂操作或合并操作,并针对操作后产生的新槽位映射关系建立影子路由表,影子路由表中同时保留调整前的旧槽位映射关系与调整后的新槽位映射关系,写请求按照旧槽位映射关系写入并通过变更日志方式异步复制到新槽位映射关系所指向的物理位置,读请求按照旧槽位映射关系读取;路由控制模块在影子路由表存续期间按照公式四计算一致性水位线:,其中,w(τ)表示时刻τ的一致性水位线,dold表示分裂操作或合并操作触发时刻旧槽位映射关系下待迁移的数据总量,dnew(τ)表示时刻τ新槽位映射关系下已通过变更日志方式追平的数据量,在一致性水位线达到预设完成阈值时,将路由表生效版本指针从旧槽位映射关系原子化切换到新槽位映射关系;路由控制模块将执行动作执行完成后对应统计周期综合负载失衡系数的下降幅度作为回报值写回在线学习决策器针对执行动作的历史执行记录,用于更新平均负载改善回报与历史累计被选中执行的次数。

3、通过上述技术方案在路由请求的同一次处理过程中同步完成路由定位计算与双通道统计结构的增量更新,使得数据存储规模与访问请求频次两类负载信号能够以近乎实时的方式反映到综合负载失衡系数的计算结果中,再由在线学习决策器依据历史执行记录动态计算各候选动作的置信上界评分并持续修正决策依据本身,使得分裂、合并、复制与维持不变四类动作的选取标准随集群实际运行状况不断自我调整而非依赖固定不变的人工阈值,同时借助影子路由表维持新旧路由映射关系的双活过渡并依据一致性水位线实现原子化切换,使得路由规则的动态调整过程对上层业务保持透明,整体上使路由映射关系具备了随数据实际分布特征持续自适应调整的能力,同时不依赖路由机制之外的旁路统计系统与事后补救流程。

4、进一步地,执行动作为分裂时,路由控制模块依据叶子槽位内数据在哈希取值区间或范围区间上的分布密度确定分裂边界,将叶子槽位对应的区间划分为两段并生成两个子槽位,两个子槽位在槽位树数据结构中作为叶子槽位的子节点接入,叶子槽位归属的数据依据分裂边界分别归属到两个子槽位。

5、进一步地,执行动作为合并时,路由控制模块在槽位树数据结构中查找与叶子槽位对应的兄弟槽位,将叶子槽位与兄弟槽位各自对应的区间合并为一段并生成一个父槽位,父槽位在槽位树数据结构中替代原有的两个叶子节点,叶子槽位与兄弟槽位归属的数据统一归属到父槽位。

6、进一步地,执行动作为复制时,路由控制模块为叶子槽位在其他物理节点上创建只读副本,并按照预设权重将叶子槽位后续接收到的读请求分流至各只读副本所在的物理节点,复制操作不改变槽位树数据结构,且不产生数据迁移。

7、进一步地,存储量通道所采用的概要数据结构占用亚线性存储空间,插入操作使叶子槽位的存储量通道估计值随实际写入的数据条目持续累积。

8、进一步地,路由表生效版本指针切换到新槽位映射关系之后,路由控制模块对旧槽位映射关系所占用的存储资源执行延迟回收。

9、进一步地,综合负载失衡系数中,当存储量通道对应的分量大于访问量通道对应的分量时,在线学习决策器针对叶子槽位选取的执行动作为分裂或合并中的一种;当访问量通道对应的分量大于存储量通道对应的分量时,在线学习决策器针对叶子槽位选取的执行动作为复制。

10、进一步地,历史执行记录包括候选动作在叶子槽位上历史累计被选中执行的次数与叶子槽位累计触发决策评估的总次数,路由控制模块依据更新后的历史执行记录重新计算后续置信上界评分。

11、本发明的有益效果:

12、1.通过将双通道统计结构的更新与路由定位计算合并在同一次请求处理过程中完成,避免了现有技术中统计模块与路由计算路径相互独立所导致的负载感知滞后与统计口径不一致问题,提升了倾斜发现与响应的及时性。

13、2.通过在综合负载失衡系数中分别引入存储量通道与访问量通道两项分量,并依据两项分量的相对大小分别匹配分裂合并操作与复制操作两类代价不同的应对策略,避免了将存储规模倾斜与访问频次倾斜两类性质不同的问题采用同一套处理机制所带来的不必要迁移开销。

14、3.通过在线学习决策器依据历史执行记录持续更新各候选动作的置信上界评分,使分裂、合并、复制与维持不变四类动作的选取标准具备随集群实际运行状况自我修正的能力,同时借助影子路由表与一致性水位线实现路由规则调整过程中新旧映射关系的平滑过渡与原子切换,避免了对上层业务造成的停机或者侵入式改造。