一种高并发自动呼叫分配系统的跳表索引动态维护方法及系统与流程

摘要: 本申请涉及计算机数据处理,尤其涉及一种高并发自动呼叫分配系统的跳表索引动态维护方法及系统。背景技术:1、在自动呼叫分配(acd)系统中,为了实现高效的客户服务,...
一种高并发自动呼叫分配系统的跳表索引动态维护方法及系统与流程

本申请涉及计算机数据处理,尤其涉及一种高并发自动呼叫分配系统的跳表索引动态维护方法及系统。

背景技术:

1、在自动呼叫分配(acd)系统中,为了实现高效的客户服务,需要对大量座席的状态和优先级进行实时管理,并从中快速选择最合适的座席来处理来电。这要求底层的数据结构能够支持对座席集合的高效动态排序和查找。

2、现有技术中,一些简单的方案采用数组或链表结构来管理座席,但其插入和删除操作的时间复杂度较高,在座席数量庞大时性能低下,难以满足高并发场景的需求。为了优化性能,一些方案转而采用平衡二叉树(如红黑树)来组织数据,虽然其查找、插入和删除操作的平均时间复杂度可达到对数级别,但平衡树的实现逻辑非常复杂,尤其是在高并发环境下,为维持树的平衡而进行的旋转、变色等操作需要对较大范围的节点加锁,容易导致锁竞争激烈,从而严重影响并发性能。

3、为了兼顾性能与实现简易性,业界有方案提出使用跳表数据结构来管理座席。跳表通过构建多级索引,同样能实现对数级别的期望时间复杂度,且其实现和并发控制相比平衡树更为简单。然而,现有的跳表应用方案通常采用标准的、基于预设概率来构建多级索引的算法,并未充分考虑自动呼叫分配系统高频、动态更新的极端工况。在长期运行下,频繁的节点插入和删除会导致索引层级分布不均,出现数据倾斜,使得查询性能退化,无法自适应地维持索引结构的整体效率。此外,对于座席权重更新这一常见操作,直接在跳表结构中进行在位更新同样会引入复杂的锁机制和较高的并发冲突风险,从而成为系统的性能瓶颈。因此,如何解决跳表数据结构在长期高频动态更新下的性能稳定性、索引平衡以及并发更新效率问题,是当前技术领域亟待解决的难题。

技术实现思路

1、本申请的目的在于,解决现有技术中在自动呼叫分配等系统中使用跳表等有序数据结构时,所面临的在高并发、高频更新场景下索引结构可能退化、更新操作并发性能不佳的技术问题,从而提供一种能够自我优化、性能稳定且并发效率高的跳表索引动态维护方法及系统。

2、为实现上述目的,本申请提供了一种高并发自动呼叫分配系统的跳表索引动态维护方法及系统,应用于一跳表数据结构,所述跳表数据结构为一个存储按权重排序的座席节点的多层级有序链表,所述方法包括:在向所述跳表中插入新座席节点时,执行动态层级调整步骤,根据至少一个预设的系统运行参数,动态地调整所述新座席节点晋升至更高索引层级的晋升概率;在执行插入操作后,执行插入时索引平衡步骤,检测新插入位置的局部索引密度,若检测到的局部索引密度低于预设的密度阈值,则触发一次局部索引的优化操作;当一个已存在于所述跳表中的座席节点的权重发生变化时,执行权重更新并发优化步骤,所述步骤采用“标记-清理-重插”策略,包括:将代表该座席节点的旧节点采用原子操作在逻辑上标记为无效,根据更新后的权重创建并插入一个新座席节点,并由一后台任务清理被标记为无效的所述旧节点。

3、可选地,所述系统运行参数包括以下至少一项:系统当前的总座席数量;预设时间窗口内的座席节点操作频率。

4、可选地,在所述动态层级调整步骤中,所述晋升概率的调整包括:根据所述总座席数量,将所述晋升概率设置为一预定值,其中,所述预定值是根据一预设规则确定的,该预设规则使得所述跳表的期望总层级数量为对所述总座席数量取对数并向上取整的值。

5、可选地,所述检测局部索引密度包括:检测在新座席节点所在层级上,其与相邻索引节点之间在下一层级所包含的节点数量。

6、可选地,所述密度阈值为8个节点。

7、可选地,所述局部索引的优化操作包括以下至少一项:临时提高该局部区域内节点的晋升概率;对该局部区域内的部分节点强制执行一次索引重建。

8、可选地,所述后台任务为一个独立的、周期性执行的清理线程。

9、可选地,所述跳表数据结构的基础层为一个双向链表。

10、本申请还提供了一种高并发自动呼叫分配系统的跳表索引动态维护系统,包括数据存储模块,所述数据存储模块用于在内存中构建并维护一个存储按权重排序的座席节点的多层级有序链表即跳表数据结构;动态层级调整模块,用于在向由所述数据存储模块维护的跳表中执行新座席节点的插入操作时,根据至少一个预设的系统运行参数动态地调整所述新座席节点晋升至更高索引层级的晋升概率,其中,所述系统运行参数包括系统当前的总座席数量;索引平衡模块,用于在执行所述插入操作后,通过检测新插入座席节点所在层级上、其与相邻索引节点之间在下一层级所包含的节点数量,来监测新插入位置的局部索引密度,并且在监测到的局部索引密度低于预设的密度阈值时,触发一次局部索引的优化操作,所述优化操作包括临时提高该局部区域内节点的晋升概率和/或对该局部区域内的部分节点强制执行一次索引重建;节点更新处理模块,用于当一个已存在于由所述数据存储模块维护的跳表中的座席节点的权重发生变化时,执行“标记-清理-重插”策略,以采用原子操作标记旧节点、插入新节点,并与一后台清理任务交互以清理所述旧节点。

11、可选地,所述系统为一客户端/服务器架构,其中所述跳表数据结构由一中心服务器维护,所述中心服务器响应来自多个客户端的请求以执行所述插入操作、以及由所述索引平衡模块和节点更新处理模块执行的功能。

12、与现有技术相比,本申请具有如下有益效果:

13、1、性能稳定,避免退化。通过动态层级调整机制和插入时索引平衡机制,本申请能够使跳表索引结构在数据量和操作模式不断变化的长期运行中,始终保持接近最优的平衡状态,有效避免了因数据倾斜导致的性能退化问题,确保了对数级别时间复杂度的稳定性。

14、2、提升了并发性能。通过采用“标记-清理-重插”策略来处理节点权重的更新,将一个复杂且易产生锁冲突的“在位更新”操作,分解为低成本的原子标记和高效的插入操作,极大地降低了写操作之间的锁竞争,显著提升了系统在高并发、高频更新场景下的吞吐量。

15、3、实现与维护简单。相较于逻辑复杂的平衡二叉树,本申请基于跳表的核心逻辑更为直观,且通过上述优化,避免了复杂的并发控制逻辑,降低了开发和维护的难度,提高了系统的健壮性。

1.一种高并发自动呼叫分配系统的跳表索引动态维护方法,应用于一跳表数据结构,所述跳表数据结构为一个存储按权重排序的座席节点的多层级有序链表,其特征在于,所述方法包括:

2.根据权利要求1所述的方法,其特征在于,所述系统运行参数包括以下至少一项:

3.根据权利要求2所述的方法,其特征在于,在所述动态层级调整步骤中,所述晋升概率的调整包括:

4.根据权利要求1所述的方法,其特征在于,所述检测局部索引密度包括:

5.根据权利要求4所述的方法,其特征在于,所述密度阈值为8个节点。

6.根据权利要求1所述的方法,其特征在于,所述局部索引的优化操作包括以下至少一项:

7.根据权利要求1所述的方法,其特征在于,所述后台任务为一个独立的、周期性执行的清理线程;且所述跳表数据结构的基础层为一个双向链表。

8.根据权利要求1所述的方法,其特征在于,在所述权重更新并发优化步骤中,将代表该座席节点的旧节点在逻辑上标记为无效的操作,是通过采用原子操作修改所述旧节点内部的逻辑标记来实现的。

9.一种高并发自动呼叫分配系统的跳表索引动态维护系统,包括数据存储模块,所述数据存储模块用于在内存中构建并维护一个存储按权重排序的座席节点的多层级有序链表即跳表数据结构;其特征在于,所述系统还包括:

10.根据权利要求9所述的系统,其特征在于,所述系统为一客户端/服务器架构,其中所述跳表数据结构由一中心服务器维护,所述中心服务器响应来自多个客户端的请求以执行所述插入操作、以及由所述索引平衡模块和节点更新处理模块执行的功能。