一种基于主动哈希和布隆过滤器的高效缓存方法

摘要

一种基于主动哈希和布隆过滤器的高效缓存方法，其步骤如下：一、计算关键词哈希值，定位对应链表；二、计算过滤表坐标，读取标记位值；三、检测所有标记位，若全1则无法过滤，进行四，只要有0，即可判断关键词不存在，可进行过滤，进行十一；四、遍历链表下一节点；五、判断该节点数据是否匹配关键词，“是”进行六，“否”进行七；六、查询命中，读取该节点访问次数并判断该值是否超过链表最大访问次数，“是”进行八，“否”进行十；七、判断下一节点是否为空，“是”回到四，“否”进行十一；八、判断节点是否处于链表头部，“是”进行十，“否”进行九；九、移动节点至链表表头；十、更新链表最大访问次数；十一、返回查询失败。

说明书

（一）技术领域：

本发明基于主动哈希和布隆过滤器的高效缓存方法，可用于高速缓存中数据的高效查 找，属于计算机技术应用领域。

（二）技术背景：

现如今的很多系统，如：电子病历（Electronic Healthcare Record，简称EHR）、域名系统 （Domain Name System，简称DNS）等具有数据量大、具备高度隐私性、数据类型多样等 特点，造成其安全存储、查找操作的复杂性和艰巨性。对这样数据的处理除了完成基本功能 之外，还必须考虑CPU和内存等物理因素，同时要防范常见的网络攻击，如拒绝服务攻击 （Deny of Service，简称DoS）。

高速缓存是为了提高数据查找效率而设置的，针对查询流量大等特点，存储时需要采用 哈希链式存储，并且由于数据查找操作频繁，因此对查找算法的要求很高。采用哈希均匀的 算法是查找效率提高的前提，所以，必须对哈希算法进行优化。对于查找命中的情况，如果 能够尽量减少平均查找长度，对于大量查找操作，其好处是明显的。另外，由于实际中攻击 者往往大量发送不存在的查询请求，以实施DoS攻击，因此针对查找失败的情况，也要进 行算法的优化，避免CPU资源被大量耗尽。

哈希表是一个非常有用的、非常基础的数据结构，在数据的查找方面尤其重要，应用的 非常广泛。然而，任何事物都有两面性，哈希也存在缺点，即数据的局部集中性会使散列的 性能急剧下降，且越集中，性能越低。数据集中，即搜索键在通过哈希函数运算后，得到同 一个结果，指向同一个桶，这时便产生了数据冲突。通常解决数据冲突的方法有：拉链法和 开地址法。拉链法我们用的非常多，即存在冲突时，简单的将元素链在当前桶的最后元素的 尾部。

分离链接法的做法是将哈希到同一个值的所有元素保留到一个表中，为方便起见，这些 表都有表头，因此，表的实现与普通的链表相同。如果空间很紧，可以避免表头。

在传统的哈希表查找算法中，对于访问频繁的关键字，如果在生成哈希表的时候将该节 点置于某一链表的后部，则每次都要进行相当多次的链表遍历才能查找到该项，势必会增加 平均查找长度，降低效率。

事实上很多事物和现象都存在一个延续性原理，即在最近一段时间内不曾访问过的也在 不久的将来访问的可能性也较小。该思想在操作系统的页面淘汰算法中大量使用。一种主动 的哈希查找算法也是基于此思想得出的。对于电子病历库来说，如果一个病人的病历在一段 时间内没有被访问到，则意味着该病历在不久的将来访问的可能性也比较小。为减少平均查 找长度，可将该项向后移动。对不频繁访问节点的向后移动可以转化成对最近访问链表节点 的向前移动。在主动的哈希查找算法中，当访问某个节点时，则将该节点前移至链表的表头。 以此来减少整个访问过程中的平均查找长度。

对于传统的主动哈希查找算法，虽然已经减小了平均查找长度，但是也存在一定的弊端。 可以考虑下面情况。

假设某关键词的访问频率很低，在某一时刻，有一个该词的访问，按照主动哈希查找算 法，在访问完该词后，需将该词提至链表头部，之后，该词一直没有访问过，则在有限的一 段时间里（该段时间指从该词被访问到该链表其余节点均被访问）有些节点被排在该词之后。 这种情况下，必然会增加整个链表的平均查找长度。另外，这种方法对于链表的排序修改过 于频繁，也增加了系统的负担。

基于以上原因，已有人提出一种改进的主动哈希查找算法。该算法并非对于每个访问到 的节点都前移至表头，而是先作判断，如果该节点属于经常访问的则将其移至表头，如果是 偶尔访问到的，则不做位置移动。

至此，问题转化成为如何判定哪些节点属于“经常访问”的。对这个性质的评判标准成 为该算法的重点。可以称对节点访问的经常性为“访问度”。在这里，可以用对该节点访问 的时间间隔作为判断依据。“时戳”记录了最近一次访问该项的时间，用1970年1月1号零 点距该时间的秒数表示。

在这里，将某个节点的访问度描述成当前访问时间和上一次访问时间的时间差（用秒来 计算）的倒数，时间间隔越长，则访问度越小。

在哈希表节点中还设置了一个“平均值”为对应链表各节点“访问度”的平均。当访问 到一个节点时，如果新计算的“访问度”不小于“平均值”，则将该节点移动至表头；否则， 节点位置不动。比较之后，要更新节点的“平均值”为新的平均值。

本发明就是针对EHR、DNS这类特殊数据库系统的高速缓存，提供一种基于主动哈希和 布隆过滤器的高效缓存方法。

（三）发明内容：

1、目的：

本发明提供一种基于主动哈希和布隆过滤器的高效缓存方法，以实现查找效率的大幅提 高。

（1）采用能均匀哈希的字符串哈希函数具有较好的散列效果（一个理想的哈希存储结 构如图1所示）。因此要实现高效查找，故急需选用可能均匀的哈希函数。

（2）在传统的主动哈希中（传统的主动哈希如图2所示），对链表的排序修改过于频繁， 也增加了系统的负担。因此要实现高效查找，故急需对原有的主动哈希进行改进。

（3）哈希拉链算法没有考虑查找频率，从而使得总体的查找效率较低，尤其当大量查 找失败时，拉链算法的效率急剧下降。因此要实现高效查找，故急需在查找时先进行有效过 滤。

2、技术方案：

本发明为一种基于主动哈希和布隆过滤器的高效缓存方法，可以有效降低查找成功时的 平均查找长度，并降低查找失败时的CPU利用率。本发明的技术方案通过哈希寻址模块、 标记管理模块、全局存储模块和高效查找模块这4个模块实现，如图3所示，各模块功能详 细介绍如下：

其中，所述的哈希寻址模块包含ELF（为一哈希算法的名称）哈希计算单元、寻址定位 单元2部分。哈希寻址模块的内部功能单元如图4所示。具体功能如下：

（1）ELF哈希单元：采用能均匀哈希的字符串哈希函数。

（2）寻址定位单元：采用分离链表法时，将冲突的哈希节点以链表形式储存。哈希结 构为数组，因此所求出的哈希值即可作为数组下标进行寻址，从而定位出该关键词所属的哈 希链表的头节点地址。找出头节点后，进行普通的链表遍历时，进行下一节点的定位，并读 取节点关键词。

其中，所述的标记管理模块包含布隆过滤表单元、缓存更新单元2部分。标记管理模块 的内部功能单元如图5所示。具体功能如下：

（1）标记生成单元：在哈希表构建同时，进行布隆过滤表的构建，这样，在查找时， 通过先检测布隆过滤表中相应位的情况，可排除不存在的关键词，避免链表的遍历。此外， 该模块还包含定时功能，否则，当一段时间以后，布隆过滤器的标记为全部占满，失去其应 有的作用。

（2）标记清除单元：设置一个计时周期，例如，24小时（即以天为计时周期），清空 过滤器标记、统计信息和哈希表数据结构，重新进行存储。

其中，所述的全局存储模块包含全局数组单元、全局统计量单元2部分。全局存储模块 的内部功能单元如图6所示。具体功能如下：

（1）哈希表数组单元：为所有哈希链表的表头所在地址；

（2）过滤表数组单元：为布隆过滤表；

（3）全局统计量单元：各链表最大访问次数，初始化为1。

其中，所述的高效查找模块为本方法核心模块。查找过程中，读取布隆过滤表标记位， 判断关键词是否存在，如果不存在，则返回查询失败。如果无法判断出不存在，再进行哈希 表的遍历。如果遍历过程中匹配上待查关键词，则访问次数加1，同时检查是否超过该链表 最大访问次数，若超过最大值，则移动该节点至链表头部，同时更新最大访问次数，返回查 询成功。若遍历完成后都没有找到匹配的关键词，返回查询失败。高效查找模块包含布隆过 滤单元、查询匹配单元、阈值判断单元、主动哈希单元和更新信息单元5部分。高效查找模 块的内部功能单元如图7所示。具体功能如下：

（1）布隆过滤单元：通过读取对应的标记位的0、1情况，即可做出快速判断。

（2）查询匹配单元：依此遍历每个节点，如果不匹配则继续遍历，若遍历完仍未匹配， 返回失败。若遍历过程中匹配成功，记录该节点访问次数到统计量中，同时进入阈值判断单 元；

（3）阈值判断单元：读取存储单元中的统计信息，得出该链表的最大访问次数。

（4）主动哈希单元：将节点从链表摘下，放入表头。

（5）更新信息单元：最大访问次数更新为新头部节点的访问次数值。

本发明提供的流程框图如图8所示。

本发明一种基于主动哈希和布隆过滤器的高效缓存方法，其具体步骤如下：

步骤一：计算待查找关键词的哈希值，定位对应的哈希链表；

步骤二：计算布隆过滤表标记位的坐标，找到对应的布隆过滤表中标记位值；即由高效 查找模块中的标记生成单元完成，结果保存到全局存储模块中的过滤表数组单元中；

步骤三：检测所有标记位的值，若全为1，则无法过滤，进行步骤四，只要有一位为0， 即可判断出关键词不存在，可行过滤，进行步骤十一；

步骤四：遍历链表的下一个节点；

步骤五：判断该节点的数据是否与关键词匹配，“是”进行步骤六，“否”进行步骤七；

步骤六：查询已经命中，读取该节点访问次数，判断该值是否超过该节点所述链表的最 大访问次数，“是”进行步骤八，“否”进行步骤十；所述的读取该节点访问次数，判断该值 是否超过该节点所述链表的最大访问次数是由高效查找模块中的阈值判断单元完成，其读取 的数据来源于全局存储模块中的全局统计量单元；

步骤七：判断下一个节点是否为空，“是”回到步骤四，“否”进行步骤十一；

步骤八：判断节点是否已经处于链表头部，“是”进行步骤十，“否”进行步骤九；

步骤九：移动链表至表头，先将链表从表中摘下，再插入到表头即可；

步骤十：更新表头最大访问次数；

步骤十一：返回查询失败。

其中，在步骤一中所述的计算定位对应的哈希链表节点，是由哈希寻址模块中的ELF 哈希单元和寻址定位单元完成，结果保存到全局存储模块中的哈希表数组单元中；

其中，在步骤三中所述的检测所有标记位的值由高效查找模块中的布隆过滤单元完成， 其读取的数据来源于全局存储模块中的过滤表数组单元；

其中，在步骤四中所述的遍历链表的下一个节点为计算机的基本链表操作，直接对全局 存储模块中的哈希表数组单元进行操作；

其中，在步骤五中所述的判断该节点的数据是否与关键词匹配，由高效查找模块的查询 匹配单元完成，直接对全局存储模块中的哈希表数组单元进行操作；

其中，在步骤七中所述的判断下一个节点是否为空为计算机的基本链表操作，直接对全 局存储模块中的哈希链头数组单元进行判断操作；

其中，在步骤八中所述的判断节点是否已经处于链表头部，为计算机的基本链表操作， 直接对全局存储模块中的哈希链头数组单元进行判断操作；

其中，在步骤九中所述的移动链表至表头，先将链表从表中摘下，再插入到表头即可由 高效查找模块中的主动哈希单元完成，该功能为基本链表操作的组合；

其中，在步骤十中所述的更新表头最大访问次数由高效查找模块中的更新信息单元完 成，结果保存到全局存储模块中的全局统计量单元中；

其中，在步骤十一中所述的返回查询失败，由高效查找模块的布隆过滤单元（过滤器不 理想时，也会由查询匹配单元完成），如果为理想过滤器时，全部由布隆过滤单元完成。

3、优点及功效：

本发明提供一种基于主动哈希和布隆过滤器的高效缓存方法。该方法首先采用ELF哈希 进行均匀哈希操作，又通过主动哈希大幅减少了哈希表的平均查找长度，同时，基于布隆过 滤器的布隆过滤表，可避免了对肯定不存在的关键词进行链表遍历。该方法构建哈希表的同 时对布隆过滤表进行标记，使得其在查找过程中可以通过布隆过滤表进行布隆过滤，同时若 查找成功，也会根据访问次数与阈值的关系进行节点动态调整，实现改进的主动哈希。整个 过程仅依赖计算机基本的数据结构，操作简单易行，且易于编程实现。

其中查找频率的衡量有以下两种标准：

1）利用查找次数平均值，如果某域名的查找次数>平均查找次数，将该节点移到链表 头部。

问题：次数会产生越界问题，一旦越界，算法失去意义。

2）利用查找时间间隔倒数的平均值，查找频率=1/(当前查找时戳　上次查找时戳)。 如果某关键字的查找频率>平均查找频率，将该节点移到链表头部。

问题：如果在很短的时间内查找同一个域名，两次的时戳之差趋于0，取倒数会导致除 0异常。

因而本发明具有高效、易实现和首创性的优点。

（四）附图说明：

图1理想哈希存储示意图。

图2原始主动哈希查找示意图。

图3本发明方法模块结构图。

图4本发明哈希寻址模块内部功能单元示意图。

图5本发明布隆过滤模块内部功能单元示意图。

图6本发明全局存储模块内部功能单元示意图。

图7本发明高效查找模块内部功能单元示意图。

图8本发明一种基于主动哈希和布隆过滤器的高效缓存流程框图。

（五）具体实施方式

见图1-图8所示，本发明一种基于主动哈希和布隆过滤器的高效缓存方法，其具体实施 方式如下：

步骤一：计算待查找关键词的哈希值，定位对应的哈希链表；

步骤二：计算布隆过滤表标记位的坐标，找到对应的布隆过滤表中标记位值；所述的计 算布隆过滤表标记位的坐标，查找对应的布隆过滤表中标记位值，是由高效查找模块中的标 记生成单元完成，结果保存到全局存储模块中的过滤表数组单元中；

步骤三：检测所有标记位的值，若全为1，则无法过滤，进行步骤四，只要有一位为0， 即可判断出关键词不存在，可行过滤，进行步骤十一；

步骤四：遍历链表的下一个节点；

步骤五：判断该节点的数据是否与关键词匹配，“是”进行步骤六，“否”进行步骤七；

步骤六：查询已经命中，读取该节点访问次数后，判断该值是否超过该节点所述链表的 最大访问次数，“是”进行步骤八，“否”进行步骤十；所述的读取该节点访问次数，判断该 值是否超过该节点所述链表的最大访问次数由高效查找模块中的阈值判断单元完成，其读取 的数据来源于全局存储模块中的全局统计量单元；

步骤七：判断下一个节点是否为空，“是”回到步骤四，“否”进行步骤十一；

步骤八：判断节点是否已经处于链表头部，“是”进行步骤十，“否”进行步骤九；

步骤九：移动链表至表头，先将链表从表中摘下，再插入到表头即可；

步骤十：更新表头最大访问次数；

步骤十一：返回查询失败。

其中，在步骤一中所述的计算定位对应的哈希链表节点，是由哈希寻址模块中的ELF 哈希单元和寻址定位单元完成，结果保存到全局存储模块中的哈希表数组单元中。哈希寻址 模块中所用的ELF哈希算法是一种适合字符串型数据的均匀哈希算法。其算法把字符串的 每个字符依次相加，每次将加的结果向左移动4位，即把当前字符ASCII（现今最通用的单 字节编码系统）存入哈希结果低四位。如果加的结果大于28位，对结果向右移动24位与原 值取异或。因为如果最高的四位不为0，则说明字符多余7个，如果不处理，再加第九个字 符时，第一个字符会被移出，因此要有特殊处理。

其中，在步骤二中所述的计算布隆过滤表标记位的坐标，查找对应的布隆过滤表中标记 位值，是由高效查找模块中的标记生成单元完成，结果保存到全局存储模块中的过滤表数组 单元中。标记管理模块具体实施方式为：布隆过滤表后半区下标对应连续三个字符的ASCII 码之和，元素为三字符中的第一个。前半区记录所有合法字符（0-9，a-z，A-Z,-）在各桶中 的使用情况。将出现下述几种情形：

（1）连续三字符ASCII之和第一次出现：后半区对应位赋值为三字符的第一个字符

（2）连续三字符ASCII之和重复出现：由于后半区对应位已被赋值，所以需要用到前 半区进行标记。

若三字符中第一个字符>对应位数值，则用标记区的高四位进行标记；

0x10(00010000)：表示此字符在三字符中为第一个；

0x20(00100000)：表示此字符在三字符中为第二个；

0x40(01000000)：表示此字符在三字符中为第三个；

若三字符中第一个字符<对应位数值，则用标记区的低四位进行标记；

0x01(00000001)：表示此字符在三字符中为第一个；

0x02(00000010)：表示此字符在三字符中为第二个；

0x04(00000100)：表示此字符在三字符中为第三个；

其中，在步骤三中所述的检测所有标记位的值由高效查找模块中的布隆过滤单元完成， 其读取的数据来源于全局存储模块中的过滤表数组单元；全局存储模块在具体实施中，为节 省空间，哈希表数组与过滤器数组单元可用一个二维数组实现。其中第一维对应每一个哈希 链表，第二维作为布隆过滤表使用。全局统计量单元由链表结构体中的“链表长度”成员进 行记录。

其中，在步骤四中所述的遍历链表的下一个节点为计算机的基本链表操作，直接对全局 存储模块中的哈希表数组单元进行操作；

其中，在步骤五中所述的判断该节点的数据是否与关键词匹配，由高效查找模块的查询 匹配单元完成，直接对全局存储模块中的哈希表数组单元进行操作；

其中，在步骤六中所述的读取该节点访问次数，判断该值是否超过该节点所述链表的最 大访问次数由高效查找模块中的阈值判断单元完成，其读取的数据来源于全局存储模块中的 全局统计量单元；高效查找模块进行布隆过滤时判断方法为：

（1）若后半区对应位为0，则说明该关键字一定不存在，可以直接返回“查找失败” 结果；

（2）若后半区对应位不为0，再到前半区读取对应的标记位进行判断。如果标记位有 一个为0的，则说明该关键字一定不存在，可以直接返回“查找失败”结果。

其中，在步骤七中所述的判断下一个节点是否为空为计算机的基本链表操作，直接对全 局存储模块中的哈希链头数组单元进行判断操作；

其中，在步骤八中所述的判断节点是否已经处于链表头部，为计算机的基本链表操作， 直接对全局存储模块中的哈希链头数组单元进行判断操作；

其中，在步骤九中所述的移动链表至表头，先将链表从表中摘下，再插入到表头即可由 高效查找模块中的主动哈希单元完成，该功能为基本链表操作的组合；

其中，在步骤十中所述的更新表头最大访问次数由高效查找模块中的更新信息单元完 成，结果保存到全局存储模块中的全局统计量单元中；

其中，在步骤十一中所述的返回查询失败，由高效查找模块的布隆过滤单元（过滤器不 理想时，也会由查询匹配单元完成），如果为理想过滤器时，全部由布隆过滤单元完成；

综上所述，本发明包含一种基于主动哈希和布隆过滤器的高效缓存方法，包括哈希寻址 模块、标记管理模块、全局存储模块和高效查找模块这4个模块，可用于EHR、DNS等数 据库系统高速缓存的高效查找；本发明提供的方法，在主动哈希的基础上，引入布隆过滤思 想，同时提高了查询失效时的效率。