一种自适应分布式布隆过滤器的数据写入方法和装置与流程

1.本技术涉及计算机通信领域，尤其涉及一种自适应分布式布隆过滤器的数据写入方法和装置。


背景技术：

2.近年来，随着产品业务的发展，很多业务场景需要对数据进行去重，如网页url去重、垃圾邮件识别、曝光内容去重、大集合重复元素判断、缓存穿透等，而采用布隆过滤器便可以很好的解决这一问题。
3.布隆过滤器(bloom filter)是1970年由布隆提出的，它实际上是由一个很长的二进制向量和一系列随机映射函数组成的。布隆过滤器的优点是空间效率和查询时间都比一般的算法要好的多。
4.但是布隆过滤器，不能直接删除数据，比如在需要近7天曝光不重复的场景下，无法直接使用布隆过滤器，因为如果不删除数据，布隆过滤器的存储容量会一直增长，因此需要一个自适应的布隆过滤器来解决需要布隆过滤器容量一直增长的问题。


技术实现要素：

5.有鉴于此，本技术提供一种自适应分布式布隆过滤器的数据写入方法和装置。
6.本技术第一方面提供一种自适应分布式布隆过滤器的数据写入方法，基于布隆过滤器组实现，所述布隆过滤器组包括第一布隆过滤器和第二布隆过滤器；所述方法包括：
7.根据在第一布隆过滤器和/或第二布隆过滤器中写入数据的情况设置所述布隆过滤器组的状态；
8.获取所述布隆过滤器组的当前状态，根据所述当前状态以及第一布隆过滤器和/或第二布隆过滤器对应数组集合中的一号元素总个数和/或二号元素总个数对第一布隆过滤器或第二布隆过滤器进行初始化，以将数据写入第一布隆过滤器和/或第二布隆过滤器，同时更新并记录一号元素总个数和/或二号元素总个数。
9.进一步地，所述根据在第一布隆过滤器和/或第二布隆过滤器中写入数据的情况设置布隆过滤器组的状态具体包括：数据初始写入第一布隆过滤器时，将布隆过滤器组的状态设置为0；数据正在写入第一布隆过滤器且写入的数据总数小于第一布隆过滤器的容量的一半时，将布隆过滤器组的状态设置为1；数据正在同时写入第一布隆过滤器和第二布隆过滤器时，将布隆过滤器组的状态设置为2；数据只写入第二布隆过滤器且写入的数据总数小于第二布隆过滤器的容量的一半时，将布隆过滤器组的状态设置为3；数据只写入第二布隆过滤器且同时已写入其容量的一半的数据时，将布隆过滤器组的状态设置为4。
10.进一步地，所述对第一布隆过滤器或第二布隆过滤器进行初始化具体包括：首先获取预配置的容量；然后根据预配置的容量和期望的误判率计算第一布隆过滤器或第二布隆过滤器对应的数组的长度以及最优哈希函数的个数；最后根据所述数组的长度和所述最优哈希函数的个数对第一布隆过滤器或第二布隆过滤器进行初始化以获取第一布隆过滤
器或第二布隆过滤器的容量，并记录第一布隆过滤器或第二布隆过滤器中写入数据的第一开始时间或第二开始时间。
11.进一步地，所述获取预配置的容量还包括：根据第一布隆过滤器或第二布隆过滤器中写入数据的第一开始时间或第二开始时间和当前时间采用扩容公式计算以获取预配置的容量。
12.进一步地，所述扩容公式的表达式为：
[0013][0014]
其中，c'表示预配置的容量，t
expecttime
为期望数据多久后删除的时间，t
cur
为当前时间，t
start
为写入数据的开始时间，c为布隆过滤器的总容量。
[0015]
进一步地，所述数组的长度的表达式为：
[0016][0017]
其中，m为数组的长度，c表示预配置的容量，p表示期望的误判率；
[0018]
所述最优哈希函数的个数的表达式为：
[0019][0020]
其中，k为最优哈希函数的个数，c是插入到第一布隆过滤器中的元素个数。
[0021]
进一步地，所述方法还包括：获取布隆过滤器组的状态，并根据该状态获取对应的布隆过滤器数据，根据所述布隆过滤器组数据计算以查询待删除元素是否包含在第一布隆过滤器或第二布隆过滤器对应的数组集合中。
[0022]
进一步地，所述布隆过滤器数据包括第一布隆过滤器或第二布隆过滤器的容量、数组的长度和最优哈希函数的个数；和/或
[0023]
所述查询待删除元素是否包含在第一布隆过滤器或第二布隆过滤器对应的数组集合中具体为：根据所述布隆过滤器数据计算并判断元素映射到数组的k个点是否均等于1，若全部等于1，则该元素包含在第一布隆过滤器或第二布隆过滤器对应的数组集合中；否则，则该元素不在第一布隆过滤器或第二布隆过滤器对应的数组集合中。
[0024]
本技术第二方面提供一种自适应分布式布隆过滤器的数据写入装置，包括一个或多个处理器，用于实现上所述的自适应分布式布隆过滤器的数据写入方法。
[0025]
本技术第三方面提供一种计算机可读存储介质，其上存储有程序，该程序被处理器执行时，用于实现上述的自适应分布式布隆过滤器的数据写入方法。
[0026]
本技术提供的自适应分布式布隆过滤器的数据写入方法和装置，本技术通过使用第一布隆过滤器和第二布隆过滤器这两个布隆过滤器，可以滚动重置布隆过滤器，从而解决布隆过滤器中数据无法删除造成容量一直增长的问题；本技术根据实际期望的过期时间进行容量重置，同时根据历史写入数据的速率实现未来容量的自动扩容，具有一定的自适应性，如此即可在数据写入量暴增的时候自适应重置布隆过滤器，以将数据写入布隆过滤器中。
附图说明
[0027]
图1为本技术提供的自适应分布式布隆过滤器的数据写入方法的流程图；
[0028]
图2为本技术提供的数据单写入第一布隆过滤器的示意图；
[0029]
图3为本技术提供的数据双写入布隆过滤器组的示意图；
[0030]
图4为本技术提供的数据单写入第二布隆过滤器的示意图；
[0031]
图5为本技术提供的自适应分布式布隆过滤器的数据写入装置的一种结构示意图。
具体实施方式
[0032]
这里将详细地对示例性实施例进行说明，其示例表示在附图中。下面的描述涉及附图时，除非另有表示，不同附图中的相同数字表示相同或相似的要素。以下示例性实施例中所描述的实施方式并不代表与本技术相一致的所有实施方式。相反，它们仅是与如所附权利要求书中所详述的、本技术的一些方面相一致的装置和方法的例子。
[0033]
在本技术使用的术语是仅仅出于描述特定实施例的目的，而非旨在限制本技术。在本技术和所附权利要求书中所使用的单数形式的“一种”、“所述”和“该”也旨在包括多数形式，除非上下文清楚地表示其他含义。还应当理解，本文中使用的术语“和/或”是指并包含一个或多个相关联的列出项目的任何或所有可能组合。
[0034]
应当理解，尽管在本技术可能采用术语第一、第二、第三等来描述各种信息，但这些信息不应限于这些术语。这些术语仅用来将同一类型的信息彼此区分开。例如，在不脱离本技术范围的情况下，第一信息也可以被称为第二信息，类似地，第二信息也可以被称为第一信息。取决于语境，如在此所使用的词语“如果”可以被解释成为“在
……
时”或“当
……
时”或“响应于确定”。
[0035]
本技术提供一种自适应分布式布隆过滤器的数据写入方法和装置，能够解决直接使用布隆过滤器容量一直增长的问题，同时可以根据实际期望的过期时间进行容量重置，并能够适配写入速度是实现容量自动扩容。
[0036]
参见图1，本技术提供的自适应分布式布隆过滤器的数据写入方法，基于布隆过滤器组实现，布隆过滤器组包括第一布隆过滤器b1和第二布隆过滤器b2，通过两段布隆过滤器可以实现数据的循环删除，并通过数据写入速率，自动扩容对应的容量，该方法具有高度的自适应性，无需人工干预。具体包括以下步骤：
[0037]
(1)根据在第一布隆过滤器b1和/或第二布隆过滤器b2中写入数据的情况设置布隆过滤器组的状态，其中，布隆过滤器组的状态包括0、1、2、3和4五种状态。
[0038]
本实施例中，根据在第一布隆过滤器b1和/或第二布隆过滤器b2中写入数据的情况给布隆过滤器组设置五种状态，分别是：数据初始写入第一布隆过滤器b1时，将布隆过滤器组的状态设置为0，即status＝0；数据正在写入第一布隆过滤器b1且写入的数据总数小于第一布隆过滤器b1的容量的一半时，将布隆过滤器组的状态设置为1，即status＝1；数据正在同时写入第一布隆过滤器b1和第二布隆过滤器b2时，将布隆过滤器组的状态设置为2，即status＝2；数据只写入第二布隆过滤器b2且写入的数据总数小于第二布隆过滤器b2的容量的一半时，将布隆过滤器组的状态设置为3，即status＝3；数据只写入第二布隆过滤器b2且同时已写入其容量的一半的数据时，将布隆过滤器组的状态设置为4，即status＝4。
[0039]
(2)查询布隆过滤器组的当前状态，并根据该状态以及一号元素总个数num1或二号元素总个数num2执行相应的操作将数据写入到对应的第一布隆过滤器b1和/或第二布隆过滤器b2中，同时更新并记录第一布隆过滤器和/或第二布隆过滤器对应数组集合中的一号元素总个数num1和/或二号元素总个数num2，将待删除元素从第一布隆过滤器b1和/或第二布隆过滤器b2对应的数组集合中删除。
[0040]
应当理解的是，将数据写入布隆过滤器意味着在布隆过滤器所表示的数组集合中增加元素。
[0041]
(2.1)查询布隆过滤器组的当前状态，判断当前状态是否为0，若为0，则对第一布隆过滤器b1进行初始化以获取第一布隆过滤器b1的容量c1和写入数据的第一开始时间starttime1，并将布隆过滤器组的状态更新为1，将数据写入第一布隆过滤器b1同时更新并记录第一布隆过滤器b1对应数组集合中的一号元素总个数num1；否则，则执行步骤(2.2)。
[0042]
需要说明的是，布隆过滤器具有一定的误判率。具体地，假设数组的长度为m，并使用k个hash函数，c是要插入到布隆过滤器中的元素个数，则误判率的表达式为：
[0043][0044]
其中，p表示误判率。
[0045]
本实施例中，对第一布隆过滤器b1进行初始化具体为：首先根据预配置的容量和期望的误判率计算第一布隆过滤器b1对应的数组的长度以及最优哈希(hash)函数的个数；然后根据该数组的长度和最优哈希函数的个数对第一布隆过滤器b1进行初始化以获取第一布隆过滤器b1的容量c1，并记录第一布隆过滤器b1中写入数据的第一开始时间starttime1。
[0046]
应当理解的是，预配置的容量和期望的误判率可以根据实际情况进行预设；第一布隆过滤器b1对应的数组的长度与第一布隆过滤器b1的容量c1相对应。
[0047]
进一步地，根据预配置的容量和期望的误判率可以获取数组的长度，即：当布隆过滤器中的元素个数已知时，期望的误判率为p，预配置的容量为c，那么二进制位数组的长度的计算公式为：
[0048][0049]
进一步地，最优哈希函数的个数的获取方法具体为：如果m是数组长度，c是插入的元素个数，k是hash函数的个数，其计算公式为：
[0050][0051]
本实施例中，将数据写入初始化后的第一布隆过滤器b1中，更新并记录第一布隆过滤器b1所对应数组集合中的一号元素总个数num1。示例性地，将第一个数据写入第一布隆过滤器b1时，原有的一号元素总个数num1为0，更新以后的一号元素总个数num1为1，即将一个数据写入第一布隆过滤器b1中时，此时的一号元素总个数num1在原有的一号元素总个数num1的基础上加1，相应地，当前第一布隆过滤器b1所对应数组集合中的一号元素总个数表示为：num1＝num1+1。
[0052]
(2.2)判断当前状态是否为1，若为1，则查询并判断一号元素总个数num1是否大于等于第一布隆过滤器b1的容量c1的一半，若一号元素总个数num1大于等于第一布隆过滤器b1的容量c1的一半，则重置第二布隆过滤器b2以将待删除元素从第二布隆过滤器b2对应的数组集合中删除，对第二布隆过滤器b2进行初始化以获取第二布隆过滤器b2的容量c2和写入数据的第二开始时间starttime2，并将布隆过滤器组的状态更新为2，将数据同时写入第一布隆过滤器b1和第二布隆过滤器b2中，同时更新并记录第一布隆过滤器b1对应数组集合中的一号元素总个数num1和第二布隆过滤器b2对应数组集合中的二号元素总个数num2；否则，则将数据写入第一布隆过滤器b1同时更新并记录第一布隆过滤器b1对应数组集合中的一号元素总个数num1；若不为1，则执行步骤(2.3)。
[0053]
本实施例中，重置第二布隆过滤器b2的内容包括第二布隆过滤器b2的容量c2、写入数据的第二开始时间starttime2及其对应的数组集合中的二号元素总个数num2。应当理解的是，将第二布隆过滤器b2重置即可删除第二布隆过滤器b2对应的数组集合中的待删除元素。
[0054]
本实施例中，对第二布隆过滤器b2进行初始化具体为：首先根据第一布隆过滤器b1中写入数据的第一开始时间starttime1和当前时间采用扩容公式计算出新的容量；然后根据新的容量和期望的误判率计算第二布隆过滤器b2对应的数组的长度以及最优哈希函数的个数；最后根据该数组的长度和最优哈希函数的个数对第二布隆过滤器b2进行初始化以获取第二布隆过滤器b2的容量c2，并记录第二布隆过滤器b2中写入数据的第二开始时间starttime2。
[0055]
应当理解的是，第二布隆过滤器b2对应的数组的长度与第二布隆过滤器b2的容量c2相对应。
[0056]
进一步地，扩容公式的通用表达式为：
[0057][0058]
其中，c表示新的容量，即为预配置的容量，t
expecttime
为期望数据多久后删除的时间，t
cur
为当前系统时间，t
start
为写入数据的开始时间，c'为布隆过滤器的总容量，c
mix
为常量，代表默认最小值。
[0059]
通过将相关的参数代入上述扩容公式即可计算出初始化第二布隆过滤器b2对应的新的容量，其表达式为：
[0060][0061]
其中，c2表示第二布隆过滤器b2的容量c2，即为计算的新的容量，t
expecttime
为期望数据多久后删除的时间，t
cur
为当前时间，t
start1
表示第一布隆过滤器b1中写入数据的第一开始时间starttime1，c1表示第一布隆过滤器b1的容量c1。
[0062]
应当理解的是，通过上述扩容公式计算出的新的容量可以作为预配置的容量，与期望的误判率共同计算数组的长度以及最优哈希函数的个数。
[0063]
类似地，再根据新的容量即c2和期望的误判率采用数组的长度公式计算第二布隆
过滤器b2对应的数组的长度，即进一步采用最优哈希函数的个数公式计算第二布隆过滤器b2对应的最优哈希函数的个数，即第二布隆过滤器b2对应的最优哈希函数的个数，即最后根据数组的长度m2和最优哈希函数的个数k2对第二布隆过滤器b2进行初始化以获取第二布隆过滤器b2的容量c2，并记录第二布隆过滤器b2中写入数据的第二开始时间starttime2。
[0064]
本实施例中，在布隆过滤器组的当前状态为1时，需要先查询一号元素总个数num1；然后对一号元素总个数num1是否大于等于第一布隆过滤器b1的容量c1的一半进行判断：若一号元素总个数num1小于第一布隆过滤器b1的容量c1的一半，即num1《c1/2，表示此时写入第一布隆过滤器b1的一号元素总个数num1小于第一布隆过滤器b1容量c1的一半，此时，只需要将数据写入第一布隆过滤器b1中，同时更新并记录第一布隆过滤器b1对应数组集合中的一号元素总个数num1，已写入的元素个数加一，即num1＝num1+1，如图2所示；若一号元素总个数num1大于等于第一布隆过滤器b1的容量c1的一半，即num1》＝c1/2，表示已写入第一布隆过滤器b1的一号元素总个数num1大于等于第一布隆过滤器b1容量c1的一半，此时需要重置第二布隆过滤器b2，如此即可将待删除元素从第二布隆过滤器b2对应的数组集合中删除，同时对第二布隆过滤器b2进行初始化以获取第二布隆过滤器b2的容量c2和写入数据的第二开始时间starttime2，初始化完成后，将布隆过滤器组的状态更新为2，即status＝2，表示数据正在同时写入第一布隆过滤器b1和第二布隆过滤器b2，同时执行双写，将数据同时写入第一布隆过滤器b1和第二布隆过滤器b2中，更新并记录第一布隆过滤器b1对应数组集合中的一号元素总个数num1和第二布隆过滤器b2对应数组集合中的二号元素总个数num2，即num1＝num1+1，num2＝num2+1，如图3所示。
[0065]
(2.3)判断当前状态是否为2，若为2，则查询并判断一号元素总个数num1是否大于等于第一布隆过滤器b1的容量c1，若一号元素总个数num1大于等于第一布隆过滤器b1的容量c1，则将布隆过滤器组的状态更新为3，并停止向第一布隆过滤器b1写入数据，只将数据写入第二布隆过滤器b2同时更新并记录第二布隆过滤器b2对应数组集合中的二号元素总个数num2；否则，则将数据同时写入第一布隆过滤器b1和第二布隆过滤器b2中，同时更新并记录第一布隆过滤器b1对应数组集合中的一号元素总个数num1和第二布隆过滤器b2对应数组集合中的二号元素总个数num2；若不为2，则执行步骤(2.4)。
[0066]
本实施例中，在布隆过滤器组的当前状态为2时，需要先查询一号元素总个数num1；然后对一号元素总个数num1是否大于等于第一布隆过滤器b1的容量c1进行判断：若一号元素总个数num1小于第一布隆过滤器b1的容量c1，即num1《c1，表示此时写入第一布隆过滤器b1的一号元素总个数num1小于第一布隆过滤器b1的容量c1，此时第一布隆过滤器b1的容量未满，同时执行双写，将数据同时写入第一布隆过滤器b1和第二布隆过滤器b2中，同时更新并记录第一布隆过滤器b1对应数组集合中的一号元素总个数num1和第二布隆过滤器b2对应数组集合中的二号元素总个数num2，即num1＝num1+1，num2＝num2+1，如图3所示；若一号元素总个数num1大于等于第一布隆过滤器b1的容量c1，即num1》＝c1，表示此时写入第一布隆过滤器b1的一号元素总个数num1大于等于第一布隆过滤器b1的容量c1，此时第一布隆过滤器b1的容量已满，将布隆过滤器组的状态更新为3，即status＝3，并停止向第一布隆过滤器b1写入数据，只将数据写入第二布隆过滤器b2中，同时更新并记录第二布隆过滤
器b2对应数组集合中的二号元素总个数num2，已写入的元素个数加一，即num2＝num2+1，如图4所示。
[0067]
(2.4)判断当前状态是否为3，若为3，则查询并判断二号元素总个数num2是否大于等于第二布隆过滤器b2的容量c2的一半，若二号元素总个数num2大于等于第二布隆过滤器b2的容量c2的一半，则重置第一布隆过滤器b1以将待删除元素从第一布隆过滤器b1对应的数组集合中删除，对第一布隆过滤器b1进行初始化以获取第一布隆过滤器b1的容量c1和写入数据的第一开始时间starttime1，并将布隆过滤器组的状态更新为4，再将数据写入第二布隆过滤器b2同时更新并记录第二布隆过滤器b2对应数组集合中的二号元素总个数num2；否则，直接将数据写入第二布隆过滤器b2同时更新并记录第二布隆过滤器b2对应数组集合中的二号元素总个数num2；若不为3，则执行步骤(2.5)。
[0068]
本实施例中，重置第一布隆过滤器b1的内容包括第一布隆过滤器b1的容量c1、写入数据的第一开始时间starttime1及其对应的数组集合中的一号元素总个数num1。应当理解的是，将第一布隆过滤器b1重置即可删除第一布隆过滤器b1对应的数组集合中的待删除元素。
[0069]
本实施例中，对第一布隆过滤器b1进行初始化具体为：首先根据第二布隆过滤器b2中写入数据的第二开始时间starttime2和当前时间采用扩容公式计算出新的容量；然后根据新的容量和期望的误判率计算第一布隆过滤器b1对应的数组的长度以及最优哈希函数的个数；最后根据该数组的长度和最优哈希函数的个数对第一布隆过滤器b1进行初始化以获取第一布隆过滤器b1的容量c1，并记录第一布隆过滤器b1中写入数据的第一开始时间starttime1。
[0070]
进一步地，将相关的参数代入扩容公式即可计算出初始化第一布隆过滤器b1对应的新的容量，其表达式为：
[0071][0072]
其中，c1表示第一布隆过滤器b1的容量c1，即为计算的新的容量，t
expecttime
为期望数据多久后删除的时间，t
cur
为当前时间，t
start2
表示第二布隆过滤器b2中写入数据的第二开始时间starttime2，c2第二布隆过滤器b2的容量c2。
[0073]
应当理解的是，通过上述扩容公式计算出的新的容量可以作为预配置的容量，与期望的误判率共同计算数组的长度以及最优哈希函数的个数。
[0074]
类似地，根据新的容量即c1和期望的误判率采用数组的长度公式计算第一布隆过滤器b1对应的数组的长度，即进一步采用最优哈希函数的个数公式计算第一布隆过滤器b1对应的最优哈希函数的个数，即最后根据数组的长度m1和最优哈希函数的个数k1对第一布隆过滤器b1进行初始化以获取第一布隆过滤器b1的容量c1，并记录第一布隆过滤器b1中写入数据的第一开始时间starttime1。
[0075]
本实施例中，在布隆过滤器组的当前状态为3时，需要先查询二号元素总个数num2；然后对二号元素总个数num2是否大于等于第二布隆过滤器b2的容量c2的一半进行判断：若二号元素总个数num2小于第二布隆过滤器b2的容量c2的一半，即num2《c2/2，表示此
时写入第二布隆过滤器b2的二号元素总个数num2小于第二布隆过滤器b2的容量c2的一半，无需冗余写，直接将数据写入第二布隆过滤器b2中同时更新并记录第二布隆过滤器b2对应数组集合中的二号元素总个数num2，即num2＝num2+1，如图4所示；若二号元素总个数num2大于等于第二布隆过滤器b2的容量c2的一半，即num2》＝c2/2，表示此时写入第二布隆过滤器b2的二号元素总个数num2大于等于第二布隆过滤器b2容量c2的一半，此时重置第一布隆过滤器b1，如此即可将待删除元素从第一布隆过滤器b1对应的数组集合中删除，同时对第一布隆过滤器b1进行初始化以获取第一布隆过滤器b1的容量c1和写入数据的第一开始时间starttime1，即重新记录第一布隆过滤器b1的写入数据的第一开始时间starttime1，初始化完成后，将布隆过滤器组的状态更新为4，即status＝4，再将数据写入第二布隆过滤器b2同时更新并记录第二布隆过滤器b2对应数组集合中的二号元素总个数num2，即num2＝num2+1，如图4所示。
[0076]
(2.5)查询并判断二号元素总个数num2是否大于等于第二布隆过滤器b2的容量c2，若二号元素总个数num2大于等于第二布隆过滤器b2的容量c2，则停止向第二布隆过滤器b2写入数据，将布隆过滤器组的状态更新为1，只将数据写入第一布隆过滤器b1同时更新并记录第一布隆过滤器b1对应数组集合中的一号元素总个数num1；否则，则将数据写入第二布隆过滤器b2同时更新并记录第二布隆过滤器b2对应数组集合中的二号元素总个数num2。
[0077]
本实施例中，此时布隆过滤器组的状态为4，表示数据只写入第二布隆过滤器b2且同时已写入其容量c2的一半的数据。首先需要查询二号元素总个数num2；然后对二号元素总个数num2是否大于等于第二布隆过滤器b2的容量c2进行判断：若二号元素总个数num2小于第二布隆过滤器b2的容量c2，即num2《c2，表示此时写入第二布隆过滤器b2的二号元素总个数num2小于第二布隆过滤器b2的容量c2，继续执行单写入第二布隆过滤器b2，同时更新并记录第二布隆过滤器b2对应数组集合中的二号元素总个数num2，即num2＝num2+1，如图4所示；若二号元素总个数num2大于等于第二布隆过滤器b2的容量c2，即num2》＝c2，表示此时写入第二布隆过滤器b2的二号元素总个数num2大于等于第二布隆过滤器b2的容量c2，此时需要停止向第二布隆过滤器b2写入数据，并将布隆过滤器组的状态更新为1，即status＝1，然后只将数据写入第一布隆过滤器b1中同时更新并记录第一布隆过滤器b1对应数组集合中的一号元素总个数num1，即num1＝num1+1，如图2所示。
[0078]
在另外一些实施例中，本技术中所述的方法还包括查询待删除元素是否包含在第一布隆过滤器b1或第二布隆过滤器b2对应的数组集合中。
[0079]
(3)获取布隆过滤器组的状态，根据布隆过滤器组的状态获取对应的布隆过滤器数据，并根据布隆过滤器数据计算以查询待删除元素是否包含在第一布隆过滤器b1或第二布隆过滤器b2对应的数组集合中。
[0080]
其中，布隆过滤器数据包括第一布隆过滤器b1或第二布隆过滤器b2的容量、数组的长度和最优哈希函数的个数。
[0081]
进一步地，查询元素是否包含在第一布隆过滤器或第二布隆过滤器对应的数组集合中具体为：根据上述布隆过滤器数据计算并判断元素映射到数组的k个点是否均等于1，若全部等于1，则该元素包含在第一布隆过滤器b1或第二布隆过滤器b2对应的数组集合中；否则，则该元素不在第一布隆过滤器b1或第二布隆过滤器b2对应的数组集合中。
[0082]
本实施例中，由于写入数据会动态地在第一布隆过滤器b1和第二布隆过滤器b2中来回切换，因此需要先获取布隆过滤器组的状态，然后根据布隆过滤器组的状态获取对应的布隆过滤器数据：当布隆过滤器组的状态status＝0时，则返回空，表示暂无数据写入；当布隆过滤器组的状态status＝1或2时，则返回第一布隆过滤器b1的相关设置以获取布隆过滤器数据，即第一布隆过滤器b1的容量、数组的长度和最优哈希函数的个数，根据这些布隆过滤器数据即可判断出元素是否包含在第一布隆过滤器b1对应的数组集合中；当布隆过滤器组的状态status＝3或4时，则返回第二布隆过滤器b2的相关设置以获取布隆过滤器数据，即第二布隆过滤器b2的容量、数组的长度和最优哈希函数的个数，根据这些布隆过滤器数据即可判断出元素是否包含在第二布隆过滤器b2对应的数组集合中。
[0083]
本技术提供的自适应分布式布隆过滤器的数据写入方法和装置，本技术通过使用第一布隆过滤器和第二布隆过滤器这两个布隆过滤器，可以滚动重置布隆过滤器，从而解决布隆过滤器中数据无法删除造成容量一直增长的问题；本技术根据实际期望的过期时间进行容量重置，同时根据历史写入数据的速率实现未来容量的自动扩容，具有一定的自适应性，如此即可在数据写入量暴增的时候自适应重置布隆过滤器，以将数据写入布隆过滤器中。
[0084]
与前述自适应分布式布隆过滤器的数据写入方法的实施例相对应，本发明还提供了自适应分布式布隆过滤器的数据写入装置的实施例。
[0085]
参见图5，本发明实施例提供的一种自适应分布式布隆过滤器的数据写入装置，包括一个或多个处理器，用于实现上述实施例中的自适应分布式布隆过滤器的数据写入方法。
[0086]
本发明自适应分布式布隆过滤器的数据写入装置的实施例可以应用在任意具备数据处理能力的设备上，该任意具备数据处理能力的设备可以为诸如计算机等设备或装置。装置实施例可以通过软件实现，也可以通过硬件或者软硬件结合的方式实现。以软件实现为例，作为一个逻辑意义上的装置，是通过其所在任意具备数据处理能力的设备的处理器将非易失性存储器中对应的计算机程序指令读取到内存中运行形成的。从硬件层面而言，如图5所示，为本发明自适应分布式布隆过滤器容量的数据写入装置所在任意具备数据处理能力的设备的一种硬件结构图，除了图5所示的处理器、内存、网络接口、以及非易失性存储器之外，实施例中装置所在的任意具备数据处理能力的设备通常根据该任意具备数据处理能力的设备的实际功能，还可以包括其他硬件，对此不再赘述。
[0087]
上述装置中各个单元的功能和作用的实现过程具体详见上述方法中对应步骤的实现过程，在此不再赘述。
[0088]
对于装置实施例而言，由于其基本对应于方法实施例，所以相关之处参见方法实施例的部分说明即可。以上所描述的装置实施例仅仅是示意性的，其中所述作为分离部件说明的单元可以是或者也可以不是物理上分开的，作为单元显示的部件可以是或者也可以不是物理单元，即可以位于一个地方，或者也可以分布到多个网络单元上。可以根据实际的需要选择其中的部分或者全部模块来实现本发明方案的目的。本领域普通技术人员在不付出创造性劳动的情况下，即可以理解并实施。
[0089]
本发明实施例还提供一种计算机可读存储介质，其上存储有程序，该程序被处理器执行时，实现上述实施例中的自适应分布式布隆过滤器的数据写入方法。
[0090]
所述计算机可读存储介质可以是前述任一实施例所述的任意具备数据处理能力的设备的内部存储单元，例如硬盘或内存。所述计算机可读存储介质也可以是任意具备数据处理能力的设备，例如所述设备上配备的插接式硬盘、智能存储卡(smart media card，smc)、sd卡、闪存卡(flash card)等。进一步的，所述计算机可读存储介质还可以既包括任意具备数据处理能力的设备的内部存储单元也包括外部存储设备。所述计算机可读存储介质用于存储所述计算机程序以及所述任意具备数据处理能力的设备所需的其他程序和数据，还可以用于暂时地存储已经输出或者将要输出的数据。
[0091]
以上实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的精神和范围。

技术特征：
1.一种自适应分布式布隆过滤器的数据写入方法，其特征在于，基于布隆过滤器组实现，所述布隆过滤器组包括第一布隆过滤器和第二布隆过滤器；所述方法包括：根据在第一布隆过滤器和/或第二布隆过滤器中写入数据的情况设置所述布隆过滤器组的状态；获取所述布隆过滤器组的当前状态，根据所述当前状态以及第一布隆过滤器和/或第二布隆过滤器对应数组集合中的一号元素总个数和/或二号元素总个数对第一布隆过滤器或第二布隆过滤器进行初始化，以将数据写入第一布隆过滤器和/或第二布隆过滤器，同时更新并记录一号元素总个数和/或二号元素总个数。2.根据权利要求1所述的自适应分布式布隆过滤器的数据写入方法，其特征在于，所述根据在第一布隆过滤器和/或第二布隆过滤器中写入数据的情况设置布隆过滤器组的状态具体包括：数据初始写入第一布隆过滤器时，将布隆过滤器组的状态设置为0；数据正在写入第一布隆过滤器且写入的数据总数小于第一布隆过滤器的容量的一半时，将布隆过滤器组的状态设置为1；数据正在同时写入第一布隆过滤器和第二布隆过滤器时，将布隆过滤器组的状态设置为2；数据只写入第二布隆过滤器且写入的数据总数小于第二布隆过滤器的容量的一半时，将布隆过滤器组的状态设置为3；数据只写入第二布隆过滤器且同时已写入其容量的一半的数据时，将布隆过滤器组的状态设置为4。3.根据权利要求1所述的自适应分布式布隆过滤器的数据写入方法，其特征在于，所述对第一布隆过滤器或第二布隆过滤器进行初始化具体包括：首先获取预配置的容量；然后根据预配置的容量和期望的误判率计算第一布隆过滤器或第二布隆过滤器对应的数组的长度以及最优哈希函数的个数；最后根据所述数组的长度和所述最优哈希函数的个数对第一布隆过滤器或第二布隆过滤器进行初始化以获取第一布隆过滤器或第二布隆过滤器的容量，并记录第一布隆过滤器或第二布隆过滤器中写入数据的第一开始时间或第二开始时间。4.根据权利要求3所述的自适应分布式布隆过滤器的数据写入方法，其特征在于，所述获取预配置的容量还包括：根据第一布隆过滤器或第二布隆过滤器中写入数据的第一开始时间或第二开始时间和当前时间采用扩容公式计算以获取预配置的容量。5.根据权利要求4所述的自适应分布式布隆过滤器的数据写入方法，其特征在于，所述扩容公式的表达式为：其中，c'表示预配置的容量，t
expecttime
为期望数据多久后删除的时间，t
cur
为当前时间，t
start
为写入数据的开始时间，c为布隆过滤器的总容量。6.根据权利要求3所述的自适应分布式布隆过滤器的数据写入方法，其特征在于，所述数组的长度的表达式为：其中，m为数组的长度，c表示预配置的容量，p表示期望的误判率；所述最优哈希函数的个数的表达式为：
其中，k为最优哈希函数的个数，c是插入到第一布隆过滤器中的元素个数。7.根据权利要求1所述的自适应分布式布隆过滤器的数据写入方法，其特征在于，所述方法还包括：获取布隆过滤器组的状态，并根据该状态获取对应的布隆过滤器数据，根据所述布隆过滤器组数据计算以查询待删除元素是否包含在第一布隆过滤器或第二布隆过滤器对应的数组集合中。8.根据权利要求1所述的自适应分布式布隆过滤器的数据写入方法，其特征在于，所述布隆过滤器数据包括第一布隆过滤器或第二布隆过滤器的容量、数组的长度和最优哈希函数的个数；和/或所述查询待删除元素是否包含在第一布隆过滤器或第二布隆过滤器对应的数组集合中具体为：根据所述布隆过滤器数据计算并判断元素映射到数组的k个点是否均等于1，若全部等于1，则该元素包含在第一布隆过滤器或第二布隆过滤器对应的数组集合中；否则，则该元素不在第一布隆过滤器或第二布隆过滤器对应的数组集合中。9.一种自适应分布式布隆过滤器的数据写入装置，其特征在于，包括一个或多个处理器，用于实现权利要求1-8中任一项所述的自适应分布式布隆过滤器的数据写入方法。10.一种计算机可读存储介质，其特征在于，其上存储有程序，该程序被处理器执行时，用于实现权利要求1-8中任一项所述的自适应分布式布隆过滤器的数据写入方法。

技术总结
本申请提供了一种自适应分布式布隆过滤器的数据写入方法和装置，该方法基于布隆过滤器组实现，布隆过滤器组包括第一布隆过滤器和第二布隆过滤器，首先根据在第一布隆过滤器和/或第二布隆过滤器中写入数据的情况设置所述布隆过滤器组的状态；然后获取所述布隆过滤器组的当前状态，根据所述当前状态以及第一布隆过滤器和/或第二布隆过滤器对应数组集合中的一号元素总个数和/或二号元素总个数对第一布隆过滤器或第二布隆过滤器进行初始化，以将数据写入第一布隆过滤器和/或第二布隆过滤器，同时更新并记录一号元素总个数和/或二号元素总个数。本申请在写入数据时，能够自适应重置布隆过滤器，删除数据，实现布隆过滤器的自动扩容。自动扩容。


技术研发人员：黄肖飞
受保护的技术使用者：北京陌陌信息技术有限公司
技术研发日：2023.05.25
技术公布日：2023/8/24