一种基于多路并行处理的多集查找插入与查找优化方法

1.本发明属于多集查找领域，具体涉及一种基于多路并行处理的多集查找插入与查找优化方法。
背景技术：
：：2.近似成员查找是大数据领域常用的方法，经典的成员资格查询方法有布隆过滤器(bloomfilter，bf)、布谷鸟过滤器(cuckoofilter，cf)和商过滤器(quotientfilter，qf)，这种结构能够回答被检查的元素是否隶属于某个特定集合。bf结构简单而速度快，但无法删除元素；cf内存代价较小，但存在容量限制；qf进一步提升了空间效率，然而，qf的更新复杂度较高。针对bf的无法删除、cf的容量和负载以及qf的查询速率问题，诸多变种诸如计数布隆过滤器(countingbloomfilter)、一致性布谷鸟过滤器(consistentcuckoofilter)以及混合计数器商过滤器(mixed-countersquotientfilter)应运而生。3.而随着网络数据包分类、物理地址(mac)表查询等领域数据复杂度的提升，例如经典的mac表场景需要区分10000个表项以及数十个端口之间的关系，只是确认元素在单一集合中的成员资格查找就逐渐无法满足需求，因此多集查找得到学者们的重视。多集查找是一种在大数据领域常见的算法，该算法可以对属于不同子集的数据进行所属集合的查找，假设给定k个无交集的集合s1、…、sk，其中有一个集合中有元素e，多集查找负责处理元素e属于哪个集合的问题。4.目前比较流行的多集查找方法主要有索引集合表(iset)、差异布隆过滤器(differencebloomfilter，dbf)以及平衡多哈希颜色表(balancedmulti-hashcolortable，bmct)等。iset创意性的将基于bf的索引过滤器(indexfilter，if)与哈希表结合起来，利用if快速计算存储索引，利用哈希表存储键的指纹，同时加入了校验码机制，确保了足够低的假阳率。dbf则利用了bf的特征，适当改进后使其拥有了多集查找的能力，虽然查询速度很快，但随之而来的是假阳率上升的问题。而bmct是一个利用哈希表以及bf进行多集查找的数据结构，它使用图的算法对该插入过程进行了批量化实现，这一方案显著提升了结构的空间效率以及插入速度，但是bmct并未提供批量处理查询元素的方法。技术实现要素：5.本发明针对现有技术无法解决bmct中未解决的批量处理查询元素的不足，设计并实现一种基于多路并行处理的多集查找插入与查找优化方法。本发明结构上由哈希表、bf以及多个计算资源组成，这里的计算资源可以是一个线程，也可以是一台计算机设备。将待查找数据队列化，并为其计算哈希表以及在bf中对应的索引。将查询过程分为多个并行处理的任务，这些任务将独立查询并输出对应的结果。对于过程中可能发生的碰撞而言，将通过将元素通过哈希函数散列到多个索引位置，且每个索引位置设置多个存放数据的槽来解决。6.本发明提供一种基于多路并行处理的多集查找插入与查找优化方法，包括如下步骤：7.s1，初始化多集查找结构操作。设置多集查找的各项参数，包括多集查找结构中使用hash函数的数目，hash表的每个子表中bucket数目以及每个bucket中slot的数目，然后为其分配相应的内存空间。8.s2，向完成初始化的多集查找结构中插入元素数据。多集查找结构中插入数据的格式为键值对，其中不同元素的“值”必须不同，但是“键”可以为同一值。9.s3，多集查找结构接收待查询数据。待查询数据在进入多集查找结构前被组织为一个队列，随后进入多集查找结构进行多路查询处理，处理完成的数据将被输出。10.进一步地，步骤s1中的多集查找结构由hash表与bf组织而成，hash表拥有与设置hash函数数目相同的子表数目，以便并行操作。slot是存放元素对应数据的基本单元，而bucket是可索引的最小单位，每个bucket包含至少一个slot，而hash表的每个子表都由bucket构成。11.进一步地，步骤s2中包含如下步骤：12.s21，将待插入键值对中的值输入多集查找结构中的hash函数组，得到对应每个hash子表的位置索引信息。其中hash函数组包含与多集查找结构中hash子表相同数目的hash函数，每个hash函数是相互独立的。13.s22，将位置索引信息分别对应输入每个hash子表，获取对应bucket的负载情况。这里的负载情况对应bucket中存有数据的slot占比。14.s23，选择所有hash子表中负载最小的bucket(若所有子表对应位置负载都相同，则随机选择插入的bucket)，插入键值对数据中的键。插入键的过程中，首先检验该bucket中已存放数据的slot是否存放相同的键，若是，则不再重复存放，否则，选择bucket中空的slot存放该键信息。15.s24，向bf中插入“值|键”，其中“|”为连接运算符。16.s25，返回插入结果。若所有hash子表中对应位置的bucket都没有空的slot，则返回插入失败，否则返回插入成功。17.进一步地，步骤s3中的待查询数据组织形式都为一个值，而非键值对。18.进一步地，步骤s3中包含如下步骤：19.s31，将参与多路并行查找的计算资源组织为数组进行管理，并将待查询数据按照先后顺序组织为队列形式。20.s32，主计算资源将待查询数据输入多集查找结构中的hash函数组，得到对应各个子表中的位置索引。21.s33，主计算资源循环访问计算资源数组，寻找空闲计算资源，并将待查询数据以及其位置索引信息提交给对应计算资源，随后退出计算资源数组。主计算资源进入数组的位置为上一次主计算资源找到空闲计算资源的下一个位置。22.s34，计算资源得到待查询数据以及位置索引信息后，访问hash子表中的对应位置，获取该位置中存取的所有数据，并将所有数据组织为候选集合。随后对待查询数据与候选集合中的元素一一执行“|”运算，这里的“|”为连接运算符，并验证bf中该运算结果的成员资格。若该运算结果是bf的成员，则表示该元素是待查询数据的键，将其作为结果输出，否则输出该元素不存在于多集查找结构中。23.s35，重复执行s31至s34，直至存放待查询数据的队列被清空，或多集查找结构被关闭。24.本发明有益效果：本发明将哈希表、bf以及多个计算资源组成，将待查找数据队列化，并为其计算哈希表以及在bf中对应的索引，将查询过程分为多个并行处理的任务，这些任务将独立查询并输出对应的结果，进一步提升了多集查找的查询速度，减少了大数据场景下待查询数据积压的情况。本发明还使用负载均衡提高了整体结构的紧凑型同时还保持了较高的精度。附图说明25.图1：布隆过滤器原理图；26.图2：多集查找结构中hash表的结构示意图；具体实施方式27.下面结合附图对本发明进行详细说明，一种基于多路并行处理的多集查找插入与查找优化方法，包括如下详细步骤：28.步骤1、结构初始化29.设置多集查找的各项参数，包括多集查找结构中使用hash函数的数目，hash表的每个子表中bucket数目以及每个bucket中slot的数目，slot是存放元素对应数据的基本单元，而bucket是可索引的最小单位，每个bucket包含至少一个slot，而hash表的每个子表都由bucket构成。30.服务端根据需求为多集查找结构设置合适的容量，随后根据容量为多集查找结构分配相应的hash表以及bf内存空间。需要注意的是，bf的精度随着其负载的增加而减少，这是由bf的特性决定的，bf检验一个元素需要根据其hash函数组得到的位置索引信息，检查对应位置的位是否都为1，而随着bf负载的增加，bf内将会有大量的位被设置为“1”，此时检查一个未插入元素，其通过hash函数组生成位置索引对应的位都等于“1”的概率就会增加，故需根据需求合理设置bf大小。同时，根据设置与需求，具体化计算资源的形式，这里计算资源可以是一台计算机，也可以是一个线程，布隆过滤器工作原理如图1所示。31.步骤2、插入成员数据32.成员数据的组织形式为键值对，将这些键值对输入多集查找结构中的hash函数组，得到对应于各个子表的位置索引，并通过位置索引获取各子表中对应位置的负载情况，最后选择负载最小的位置容纳该键值对中的键。hash表的结构如图2所示。在插入过程中，需要检验该键是否已插入，检验方式为遍历位置索引对应的各bucket中是否有slot存放相同的键，若是，表示该键已插入，不再需要重复插入。这种做法提升了多集查找结构的紧凑性。具体过程如下：33.s21，将待插入键值对中的值输入多集查找结构中的hash函数组，得到对应每个hash子表的位置索引信息。其中hash函数组包含与多集查找结构中hash子表相同数目的hash函数，每个hash函数是相互独立的。34.s22，将位置索引信息分别对应输入每个hash子表，获取对应bucket的负载情况。这里的负载情况对应bucket中存有数据的slot占比。35.s23，选择所有hash子表中负载最小的bucket(若所有子表对应位置负载都相同，则随机选择插入的bucket)，插入键值对数据中的键。插入键的过程中，首先检验该bucket中已存放数据的slot是否存放相同的键，若是，则不再重复存放，否则，选择bucket中空的slot存放该键信息。36.s24，向bf中插入“值|键”，其中“|”为连接运算符。37.s25，返回插入结果。若所有hash子表中对应位置的bucket都没有空的slot，则返回插入失败，否则返回插入成功。38.步骤3、多集查找结构接收数据，进行多集查找39.多集查找结构接收数据，检验该数据的成员资格并输出该数据对应的键。若该数据是bf的成员，则输出结果为该数据对应的键，否则输出false以表明该键不是bf的成员。多集查找结构中用来处理子任务的资源为计算资源，具体可表现为一个线程，或是一台计算机。具体过程如下：40.s31，将参与多路并行查找的计算资源组织为数组进行管理，并将待查询数据按照先后顺序组织为队列形式。41.s32，主计算资源将待查询数据输入多集查找结构中的hash函数组，得到对应各个子表中的位置索引。42.s33，主计算资源循环访问计算资源数组，寻找空闲计算资源，并将待查询数据以及其位置索引信息提交给对应计算资源，随后退出计算资源数组。主计算资源进入数组的位置为上一次主计算资源找到空闲计算资源的下一个位置。43.s34，计算资源得到待查询数据以及位置索引信息后，访问hash子表中的对应位置，获取该位置中存取的所有数据，并将所有数据组织为候选集合。随后对待查询数据与候选集合中的元素一一执行“|”运算，并验证bf中该运算结果的成员资格。若该运算结果是bf的成员，则表示该元素是待查询数据的键，将其作为结果输出，否则输出该元素不存在于多集查找结构中。44.所述bf验证成员资格的过程如下：将需要验证的结果输入bf中，bf使用自身的hash函数组处理数据，并得到与hash函数组数目相同的位置索引，最后bf使用这些位置索引检查bf结构中对应的位，若这些位都等于“1”，则该结果为bf中的成员，否则该结果不是bf中的成员。45.s35，重复执行s31至s34，直至存放待查询数据的队列被清空，或多集查找结构被关闭。46.步骤4、重复步骤3，直到多集查找结构被关闭或是部署平台出现异常。当前第1页12当前第1页12
技术特征：
1.一种基于多路并行处理的多集查找插入与查找优化方法，其特征在于，包括如下步骤：s1，初始化多集查找结构：设置多集查找的各项参数，然后为其分配相应的内存空间；s2，向完成初始化的多集查找结构中插入元素数据，多集查找结构中插入数据的格式为键值对，其中不同元素的“值”必须不同；s3，多集查找结构接收待查询数据：待查询数据在进入多集查找结构前被组织为一个队列，随后进入多集查找结构进行多路查询处理，处理完成的数据将被输出。2.根据权利要求1所述的一种基于多路并行处理的多集查找插入与查找优化方法，其特征在于，在s1中，所述的各项参数，包括多集查找结构中使用hash函数的数目，hash表的每个子表中bucket数目以及每个bucket中slot的数目。3.根据权利要求2所述的一种基于多路并行处理的多集查找插入与查找优化方法，其特征在于，在s1中，所述的多集查找结构由hash表与布隆过滤器bf组成；hash表拥有与设置hash函数数目相同的子表数目；slot是存放元素对应数据的基本单元；bucket是可索引的最小单位，每个bucket包含至少一个slot，hash表的每个子表都由bucket构成。4.根据权利要求3所述的一种基于多路并行处理的多集查找插入与查找优化方法，其特征在于，步骤s2具体过程如下：s21，将待插入键值对中的值输入多集查找结构中的hash函数组，得到对应每个hash子表的位置索引信息，其中hash函数组包含与多集查找结构中hash子表相同数目的hash函数，每个hash函数是相互独立的；s22，将位置索引信息分别对应输入每个hash子表，获取对应bucket的负载情况；s23，选择所有hash子表中负载最小的bucket，插入键值对数据中的键；插入键的过程中，首先检验该bucket中已存放数据的slot是否存放相同的键，若是，则不再重复存放，否则，选择bucket中空的slot存放该键信息；s24，向bf中插入“值|键”，其中“|”为连接运算符；s25，返回插入结果，若所有hash子表中对应位置的bucket都没有空的slot，则返回插入失败，否则返回插入成功。5.根据权利要求4所述的一种基于多路并行处理的多集查找插入与查找优化方法，其特征在于，在s22中，所述负载情况为bucket中存有数据的slot占比。6.根据权利要求4所述的一种基于多路并行处理的多集查找插入与查找优化方法，其特征在于，在s23中还包括，当所有子表对应位置负载都相同时，则随机选择插入的bucket。7.根据权利要求1所述的一种基于多路并行处理的多集查找插入与查找优化方法，其特征在于，步骤s3中的待查询数据组织形式均为一个值。8.根据权利要求6或7所述的一种基于多路并行处理的多集查找插入与查找优化方法，其特征在于，步骤s3中具体过程如下：s31，将参与多路并行查找的计算资源组织为数组进行管理，并将待查询数据按照先后顺序组织为队列形式；s32，主计算资源将待查询数据输入多集查找结构中的hash函数组，得到对应各个子表中的位置索引；
s33，主计算资源循环访问计算资源数组，寻找空闲计算资源，并将待查询数据以及其位置索引信息提交给对应计算资源，随后退出计算资源数组；主计算资源进入数组的位置为上一次主计算资源找到空闲计算资源的下一个位置；s34，计算资源得到待查询数据以及位置索引信息后，访问hash子表中的对应位置，获取该位置中存取的所有数据，并将所有数据组织为候选集合；随后对待查询数据与候选集合中的元素一一执行“|”运算，并验证bf中该运算结果的成员资格；若该运算结果是bf的成员，则表示该元素是待查询数据的键，将其作为结果输出，否则输出该元素不存在于多集查找结构中；s35，重复执行s31至s34，直至存放待查询数据的队列被清空，或多集查找结构被关闭。9.根据权利要求8所述的一种基于多路并行处理的多集查找插入与查找优化方法，其特征在于，在s34中bf验证成员资格的过程如下：将验证的结果输入bf中，bf使用自身的hash函数组处理数据，并得到与hash函数组数目相同的位置索引，最后bf使用这些位置索引检查bf结构中对应的位，若这些位都等于“1”，则该结果为bf中的成员，否则该结果不是bf中的成员。

技术总结
本发明公开了一种基于多路并行处理的多集查找插入与查找优化方法，该方法首先初始化多集查找结构操作，设置多集查找结构的各项参数，并分配相应的内存空间。其次向完成初始化的多集查找结构中插入元素数据，多集查找结构中插入数据的格式为键值对，其中不同元素的“值”必须不同，但是“键”可以为同一值。最后多集查找结构接收待查询数据，待查询数据在进入结构前被组织为一个队列，随后进入结构进行多路查询处理，处理完成的数据将被输出。本发明提升了多集查找的查询速度，减少了大数据场景下待查询数据积压的情况，在提高了整体结构的紧凑型同时还保持了较高的精度。紧凑型同时还保持了较高的精度。紧凑型同时还保持了较高的精度。


技术研发人员：黄钰淦 薛梅婷 曾艳 任永坚 张纪林 袁俊峰
受保护的技术使用者：杭州电子科技大学
技术研发日：2023.07.24
技术公布日：2023/10/11