CN1322707C - 话单剔重方法 - Google Patents

Abstract

本发明提出了一种高性能、强稳定的话单剔重方法，以解决现有技术存在的性能缓慢，效率低的问题。该方法包含以下步骤：a.从话单文件各话单中提取关键域信息，将该关键域信息和内存页面中其他话单的关键域信息进行比较；b.如果该关键域信息和内存页面中其他话单的关键域信息相同，则当前话单属于重单，否则将该关键域信息保存至内存页面中。本发明利用系统内存剔除重单，因为内存操作速度很快，完全能够满足高性能、强稳定性的要求；本发明通过内存中的页面和磁盘上的页面文件根据需要进行交换来解决有限内存和大数据量的矛盾，使应用本发明的系统能够达到很高性能，且能实现处理性能与数据量无关。

Description

话单剔重方法

技术领域

本发明涉及通讯技术领域，具体来说是一种广泛应用于通讯领域中的计费结算系统的话单剔重方法。

背景技术

在通讯技术领域，由于交换机的原因，或者由于从交换机到计费结算系统的各个中间处理环节的原因，或者由于业务需求变换的原因，都可能导致计费结算系统重复处理某些话务，从而产生重单。所述的重单，即重复话单，其包含有完全重复话单、交叉话单，完全重复话单是指两张话单完全相同，交叉话单是指两张话单的通话时间有重叠。

计费系统在对话单入库之前，必须剔除一定时间范围内的重单，即剔重，否则有可能出现用户的详细话单中出现完全相同的两条(或多条)话单，引起用户的投诉。而在结算系统也必须剔重重单，否则多方结算就会得到不一致的摊分结果。

现有技术普通采用数据库的技术进行话单剔重处理，如计费系统一般在数据库中，利用数据库的唯一索引特性完成话单剔重。

但是，上述现有技术在目前数据量不太大的情况下尚能满足性能需求的，但是随着电信业务的发展，新业务不断增加，结算关系越来越复杂，数据量也相应地迅速增加，数据库的性能会随着记录数的增加迅速下降，导致现有的计费结算系统性能缓慢，效率很低，剔重处理方法已经成为计费结算系统的性能瓶颈。

技术内容

针对上述情形，本发明提出了一种高性能、强稳定的话单剔重方法，以解决现有技术存在的性能缓慢，效率低的问题。

本发明的解决方案是这样的：一种话单剔重方法，其中，该方法包含以下步骤：

a、从话单文件各话单中提取关键域信息，将该关键域信息和内存页面中其他话单的关键域信息进行比较，找到最接近的页面，所述页面是指，内存中的页面和磁盘上的页面文件；

b、如果该关键域信息中的开始时间或/和终止时间没有落在该关键域信息所述最接近的页面覆盖的时间段范围内，则将该关键域信息保存至一个新的页面或将其加入到所述最接近的页面中，否则进行下一步；

c、将该关键域信息和该最接近的页面中已有话单记录的关键域信息进行比较，判断是否重单，如果重单，那么进行剔重处理，否则将关键域信息加入该页面中。

其中，所述步骤a具体包括以下步骤：

a1、从话单文件中提取话单记录的关键域信息；

a2、然后根据该话单记录的起始时间或/和终止时间同页面中的页面覆盖的时间段属性进行比较，找到所述最接近的页面；

a3、若该最接近的页面不在内存中，就将该最接近的页面加载到内存中。

所述步骤a1中的关键域信息是指话单中用于剔重的关键域，包含有主叫号码、被叫号码、通话时长、开始时间、终止时间、话单标志，该关键域信息根据不同类型的话单这些关键域及其个数有所不同。

所述步骤a中的页面中，每一个页面覆盖一段时间范围内的话单，页面大小基本均匀，且各自页面覆盖的时间范围不重复，其至少包含有：页面中的话单数属性、页面覆盖的时间段属性。

而所述找到最接近的页面是通过以页面索引文件形式存在的AVL(Adelson-Velsky Landis)搜索树的方式定位的。

其中，所述步骤c更具体包括以下步骤：

c1、将该关键域信息中的主叫号码和被叫号码在该最接近的页面中搜索，获得主叫号码和被叫号码相同的一组话单；

c2、将该关键域信息中的其他信息和该话单的其他信息进行比较，判断是否重单，如果重单，那么进行剔重处理，否则将关键域信息加入该页面中。

所述内存中的页面和磁盘上的页面文件根据需要进行交换。

本发明通过充分利用话单数据的“顺序性”特点、重单数据的“局部性”和“集中性”特点，在计费系统预处理环节，利用系统内存剔除重单，因为内存操作速度很快，完全能够满足高性能、强稳定性的要求；同时本发明考虑到由于系统内存有限而话单数很多，不可能把所有话单全部加载到内存中，所以在内存中无法一次剔除所有重单，只能剔除很小时间范围内的重单，本发明通过内存中的页面和磁盘上的页面文件根据需要进行交换来解决有限内存和大数据量的矛盾，使应用本发明的系统能够达到很高性能，且能实现处理性能与数据量无关。

下面结合附图说明和具体实现方式来详细介绍本发明。

附图说明

图1是为内存页面的组织结构示意图；

图2是本实施例所述的话单剔重方法流程示意图；

图3是本实施例所述的页面索引文件的结构示意图；

图4是本实施例中话单的期望值D的示意图；

图5是本实施例中话单前后都存在临近的页面的示意图；

图6是本实施例中话单前面存在临近的页面的示意图；

图7是本实施例中话单后面存在临近的页面的示意图；

图8是本实施例中话单两边都不存在临近的页面的示意图；

图9是本实施例中话单采集不按顺序处理话单文件的示意图。

具体实现方式

为了更好地了解本实施例，首先简单介绍一下话单数据和重单数据的特点。

话单数据具有“顺序性”的特点。交换机生成的话单，一般是按照话单生成的时间，顺序送到计费结算系统的，先生成的先到达(当然也不能排除部分话单不按顺序到达的情况，但是这样的话单占话单总量的极少数)。所谓“顺序”送到计费结算系统，是指任意取两个相隔足够长时间的小区间，两个区间中的话单的通话时间没有任何重叠。

重单数据具有“局部性”和“集中性”的特点。

交换机在某些条件下会产生重复话单，而要求交换机尽可能快地送出话单，所以某一张话单以及它的所有重单都散落在一个比较小的时间窗口内，这种特性可称为“局部性”；这种情况的重单都是在话单级重复。

重复话单还可能由于计费结算系统重复采集、重复处理造成。比如采集系统由于故障，重复采集了一个话单文件，或者某一个已经完成批价的话单文件需要重新批价，这种情况的重单都是在文件级重复，这种特性可称为“集中性”。

本发明实施例应用于计费结算系统预处理环节，其总体思路是：首先将话单文件中的话单记录在计算机系统内存中进行剔重处理，其次将已经经过剔重处理的话单记录的索引数据保存在一系列的“页面”中。本实施例中的重点是页面技术的灵活运用，本实施例中页面分为：内存中的页面和磁盘上的页面文件，一般情况下内存有限而页面很多，同一时刻只能有部分页面驻留在内存中，其他页面则以磁盘文件的形式保存在硬盘上。内存中的页面和磁盘上的页面根据需要可进行交换。

因内存有限，必须限制上述页面的大小和内存中存放页面的最大数。当内存中页面达到最大数，且需要生成新的页面或者需要从磁盘上加载页面文件时，把内存中最早访问的页面换出内存。每一个页面，不管是内存中的页面，还是磁盘上的页面文件，均覆盖一段时间范围内的话单记录，页面大小基本均匀，且各自覆盖的时间范围不重复，页面至少包含属性：页面中的话单数、页面覆盖的时间段(可以用最小话单终止时间、最大话单终止时间表示)。

每一个页面中的话单记录的部分关键域作为主键存放在页面中，如GSM中可以主叫号码、被叫号码、通话时长、开始时间、终止时间、话单标志作为关键域，其中话单标志用于区分一些特殊情况：比如移动话单分为移动始发和移动终结，两种话单除了话单标志不同，其他完全一样，而三方通话和交叉话单也通过话单标志区分。

如图1所示为内存页面的组织结构示意图，每个页面是一个独立的HASH表，页面在内存中以HASH表的形式存放，根据主叫和被叫号码在内存页面中搜索，得到主叫号码和被叫号码相同的一组话单，然后逐一比较查找重单和交叉话单，这样就可以充分利用HASH表的优良特性。当然，前述的在内存页面中搜索主叫号码和被叫号码相同的话单也可以采用二叉树等快速查询算法来替代HASH表，HASH表和二叉树都是现有技术，在此不再赘述。

磁盘上的页面文件存放有话单记录，话单在文件中顺序存放，新加入页面的话单追加在文件的末尾，文件中的话单不排序。内存中的页面和磁盘上的页面文件，二者进行交换时必须完成转换。

如图2所示，本实施例所述的话单剔重方法具体包括以下步骤：

第一、从话单文件各话单中提取关键域信息，将该关键域信息和内存页面中其他话单的关键域信息进行比较。

首先从话单文件中提取话单记录的关键域信息，包括：主叫号码、被叫号码、通话时长、开始时间、终止时间、话单标志。

然后根据该话单记录的起始时间(或者终止时间)和内存页面中的页面覆盖的时间段属性进行比较，搜索其对应的页面，找到最接近的内存页面；这里的搜索是通过以页面索引文件形式存在的AVL搜索树的方式定位实现的。

该AVL搜索树主要是为了便于快速搜索到和当前话单最接近的页面，本实施例为所有页面建立一个单独索引文件，其包含有：页面包含的话单总数、页面覆盖的时间范围等信息内容，称为“页面索引文件”，该页面索引文件中的一条记录对应一个页面，记录该页面的属性，如图3所示。当系统启动时候首先把该页面索引文件加载到内存中，从而为所有页面建立了一个索引。

在内存中该索引以AVL树的形式组织，其包含有若干个树节点，每个树节点对应索引文件中的一条记录。每个树节点记录页面的话单总数、时间范围、对应的文件名、是否驻留内存标志、最近访问时间、加载时间等信息。

因为AVL树是一种平衡的搜索树，所以搜索速度很快。在搜索树中每个节点代表的页面覆盖的时间范围，该范围比其左子树大而比右子树小。为了找到距离话单终止时间最近的页面，每次都必须从根节点搜索到最下层的叶子节点，但因为AVL树的平衡特点，这种搜索的最大路径长度就是树的高度，最小路径就是树的高度减1。AVL树适合于数据搜索占主要操作的场合，如果树节点频繁删除和增加则效率不高。而因为本发明中重单数据具有“局部性”、“集中性”的特点，页面交换的概率不大，AVL树增加和删除操作相对于搜索操作是非常少的，所以满足AVL树适用的条件，这正是本实施例提高性能的关键。

当系统找到最接近的内存页面或磁盘上的页面文件后，如果该页面不在内存中，就将该磁盘上的页面文件加载到内存中，以便充分利用内存的快速特性。

这里值得一提的是，因内存有限，必须限制页面的大小和内存中存放页面的最大数。当内存中页面达到最大数，且需要生成新的页面或者需要从磁盘上加载页面文件时，把内存中最早访问的页面换出内存。

交换内存页面的时候为了快速确定哪些页面可以被换出内存，为内存中所有页面建立一个索引队列，按照最近访问时间排序，每次访问一个页面的时候就把指示页面的记录调到队列的头部。当某些页面需要换出内存的时候，队列尾部的页面优先换出，已经换出内存的页面从索引中删除，最新加载的页面则添加到队列的头部(最近访问)。在发生页面交换以后需要立即更新AVL树中相应节点的信息，指示该节点表示的页面是在内存中还是在磁盘上。内存中的页面与磁盘文件一一对应，每次更新内存页面就更新相应的文件，把内存页面新增加的话单追加在磁盘文件的末尾，并更新磁盘文件覆盖的话单时间范围，其中的话单不要求排序。

第二、如果该关键域信息和内存页面中其他话单的关键域信息相同，则当前话单属于重单，将该关键域信息剔重，否则将该关键域信息保存至内存页面中。

更具体而言是指，

1、如果该关键域信息中的终止时间没有落在该关键域信息最接近的内存页面覆盖的时间段范围内，则将该关键域信息保存至一个新的页面或将其加入到最接近的页面中，否则进行下一步；

其中，若当前新的话单没有落在任何一个页面的时间范围内，则话单可能需要加入最近的页面中，也可能需要创建新的页面。

首先定义一个“期望值”，代表一个时长(设为D)，表示当前新的话单期望加入最近页面的时间范围，如图4所示，若某个页面(设为P)覆盖的时间段与话单的期望范围重复，则可将话单合入页面中，同时需要更新页面覆盖的时间段；若话单的“期望值”比较大，话单的期望范围也可能覆盖多个页面，这时需要搜索到距离最近的页面，把话单合入该页面中。

当然考虑到页面的生成必须尽可能保持大小均匀，防止生成太大的或者太小的页面。若太大使页面交换的性能降低，从而降低总体性能；若太小导致页面数量太多，从而降低操作系统的性能。页面大小的控制可以依据页面包含的话单数和页面覆盖的时段长度而定。

话单的终止时间和页面之间的位置关系可能有四种情况：

(1)、话单的前后都存在临近的页面

如图5所示，这时话单既可以合入P1中也可以合入P2中，根据P1和P2的大小作选择，把话单合入较小的一个页面中，并调整合并以后页面覆盖的时间范围。此时不应该创建新的页面，否则将造成页面太小。这种情况使页面P1和P2不断接近，但是互相之间不会重叠。

(2)、话单的前面存在临近的页面

如图6所示，若页面P的尺寸没有超过最大值，则把话单合入页面P中，并调整合并以后页面覆盖的时间范围。若页面的尺寸超过了最大值，则创建一个新的页面包含该话单。这种情况导致页面P从右往左生长。

(3)、话单的后面存在临近的页面

如图7所示，若页面P的尺寸没有超过最大值，则把话单合入页面P中，并调整合并以后页面覆盖的时间范围。若页面的尺寸超过了最大值，则创建一个新的页面包含该话单。这种情况导致页面P从左往右生长。

(4)、话单的两边都不存在临近的页面

如图8所示，此时话单不能合入任何已经存在的页面中，创建一个新的页面包含该话单。

有一种意外情况是：当采集不按顺序处理话单文件的时候可能造成这种情况，如图9所示，首先处理话单文件File1，生成一系列页面，然后处理File4，File4中第一张话单的终止时间有很大“跳跃”。如果File4的话单合入File1产生的页面中将导致很大的页面，因为后续File2、File3的话单都会加入同一个页面中，所以File4中第一张话单必须存放在新的页面中。

2、将该关键域信息和该最接近的内存页面中已有话单记录的关键域信息进行比较，判断是否重单，如果重单，那么进行剔重处理，否则将关键域信息加入该内存页面中。

具体而言是指，首先将该关键域信息中的主叫号码和被叫号码在该最接近的内存页面中搜索，获得主叫号码和被叫号码相同的一组话单，该话单只需要包含四个域：通话时长、开始时间、终止时间、话单标志。

其次，将该关键域信息中的其他信息和该话单的其他信息进行比较，即比较通话时长、开始时间、终止时间、话单标志四个域，判断是否重单，如果重单，那么进行剔重处理，否则将关键域信息加入该内存页面中。前述的剔重处理可以是将当前的重单从当前话单文件中删除，也可以是将当前的重单另存为其他格式的文件后待处理，如发送给用户进行校验核对等。

下面假设某个系统每个月需要处理70亿张话单，使用4G内存进行剔重处理，下面可以估算出采用本实施例所述方法后的处理性能。

平均每分钟的话单数：7,000,000,000/30/24/60＝16.2万(张)

每张话单用于剔重的信息和其所占的空间有：主叫号码(12字节)、被叫号码(12字节)、通话时长(4字节)、开始时间(4字节)、终止时间(4字节)、话单标志(1字节)。

每张话单需要保存37字节的数据，操作系统为了存放37字节的数据需要分配分配64字节的内存块。按照50％的内存利用率，4G内存有2G被用来存放数据，则4G内存可存放3355.4万张话单，即相当于207分钟的话单量。

这样，因交换机生成的重复话单具有“局部性”的特点，即某一张话单的重复话单一定落在其周围很近的时间范围内。一般情况下这个时间范围是几秒钟或者几分钟，远远小于内存中页面覆盖的时间范围，从而主机生成的重复话单绝大多数在内存中可以被完全剔除。

Sun工作站的写盘速度大于20M/S，读盘则更快，限定每个页面为10M大小，则每个页面加载的时间不会较大地影响处理性能。文件中的每条话单的头部设置一个2字节的长度，则每条话单在磁盘上占用39字节的长度，则10M的话单文件能够存放26.9万张话单，每个月70亿张话单将分散在大约2.6万个页面中，相应地生成2.6万个文件。

如果要求剔除3个月的话单，则存放剔重数据的磁盘空间必须大于：26000个/月^*10M/个^*3月/1024G/M＝761.7G。

从上述的估算数字可以看出，采用本实施例的系统完全获得了高性能、强稳定性的效果。

Claims (10)

1、一种话单剔重方法，其特征在于，该方法包含以下步骤：

a、从话单文件各话单中提取关键域信息，将该关键域信息和页面中其他话单的关键域信息进行比较，找到最接近的页面，所述页面是指，内存中的页面和磁盘上的页面文件；

b、如果该关键域信息中的开始时间或/和终止时间没有落在该关键域信息所述最接近的页面覆盖的时间段范围内，则将该关键域信息保存至一个新的页面或将其加入到所述最接近的页面中，否则进行下一步；

c、将该关键域信息和该最接近的页面中已有话单记录的关键域信息进行比较，判断是否重单，如果重单，那么进行剔重处理，否则将关键域信息加入该页面中。

2、如权利要求1所述的一种话单剔重方法，其中，所述步骤a具体包括以下步骤：

a1、从话单文件中提取话单记录的关键域信息；

a2、然后根据该话单记录的起始时间或/和终止时间同页面中的页面覆盖的时间段属性进行比较，找到所述最接近的页面；

a3、若该最接近的页面不在内存中，就将该最接近的页面加载到内存中。

3、如权利要求2所述的一种话单剔重方法，其中，所述步骤a1中的关键域信息是指话单中用于剔重的关键域，包含有主叫号码、被叫号码、通话时长、开始时间、终止时间、话单标志，该关键域信息根据不同类型的话单这些关键域及其个数有所不同。

4、如权利要求2所述的一种话单剔重方法，其中，所述步骤a中的页面中，每一个页面覆盖一段时间范围内的话单，页面大小基本均匀，且各自页面覆盖的时间范围不重复，其至少包含有：页面中的话单数属性、页面覆盖的时间段属性。

5、如权利要求2所述的一种话单剔重方法，其中，所述步骤a2中找到最接近的页面是通过以页面索引文件形式存在的AVL搜索树的方式定位的。

6、如权利要求1所述的一种话单剔重方法，其中，所述步骤c更具体包括以下步骤：

c1、将该关键域信息中的主叫号码和被叫号码在该最接近的页面中搜索，获得主叫号码和被叫号码相同的一组话单；

c2、将该关键域信息中的其他信息和该话单的其他信息进行比较，判断是否重单，如果重单，那么进行剔重处理，否则将关键域信息加入该页面中。

7、如权利要求1所述的一种话单剔重方法，其中，该内存中的页面和磁盘上的页面文件根据需要进行交换。

8、如权利要求1所述的一种话单剔重方法，其中的内存中的页面是以HASH表的形式存放。

9、如权利要求7所述的一种话单剔重方法，其中，所述交换具体包括以下步骤：

当内存中页面达到最大数，且需要生成新的页面或者需要从磁盘上加载页面文件时，把内存中最早访问的页面换出内存。

10、如权利要求9所述的一种话单剔重方法，其中，所述把内存中最早访问的页面换出内存包括以下步骤：

为内存中所有页面建立一个索引队列；

按照最近访问时间排序，每次访问一个页面的时候就把指示页面的记录调到队列的头部；

当某些页面需要换出内存的时候，队列尾部的页面优先换出，已经换出内存的页面从索引中删除，最新加载的页面则添加到队列的头部。

Images