CN107330094B - Bloom filter tree structure and key-value pair storage method for dynamically storing key-value pairs - Google Patents

Abstract

The invention discloses a bloom filter tree structure for dynamically storing key value pairs and a key value pair storage method, wherein the bloom filter tree structure comprises a complete d-branch tree; the method is characterized in that each node of each complete d-ary tree is a bloom filter; each leaf node of each full d-ary tree represents a value; the storage unit size of each node is half of that of the parent node of the node, and the root node comprises d × k different hash functions, that is, the root node comprises d hash groups, and each group comprises k hash functions. The invention can greatly reduce the time for collecting query, reduce resource consumption, process dynamically arrived data and adapt to network environment in the application fields of generating a large amount of data and needing key value pair query, such as database interactive query, resource positioning in high-speed network, computer network monitoring and the like.

Description

Bloom filter tree structure and key-value pair storage method for dynamically storing key-value pairs

technical field

The invention relates to the field of computer network and computer system storage, in particular to the application field of high-performance and high-throughput interactive query, in particular to an extensible Bloom tree storage structure and method for key-value pairs.

Background technique

In recent years, with the rapid development of computers, the size of collections in databases, networks and other applications has grown exponentially. Storing and querying key-value pairs (key, value) is a common task in computer systems, which requires designing a corresponding key-value pair storage data structure to support fast key-value pair query. Key-value pair operations often appear in networks and storage systems, such as key-value databases MongoDB and CouchDB. Each unique key key put into the key-value pair storage system corresponds to a value. For example, (3, 5) is a key-value pair with key key 3 and value value 5. Store (3, 5) in After the key-value pair is stored in the system, you can query the key (key) as 3 and get the value (value) as 5.

Designing efficient key-value pair storage and query structures brings great challenges. In a Layer 2 switch, a MAC address is associated with a unique port. When a frame is to be forwarded, the search engine will query the MAC table of the destination address of the frame to be forwarded. Therefore, the problem of mapping a MAC address to a port is transformed into a key-value pair query problem. At this time, the MAC address The address is regarded as the key, and the port number to be queried becomes the value. Since MAC addresses are continuously added to the list, the size of the element is unknown. If the cell structure is used to store these key-value pairs, it will consume a lot of space, and it will consume a lot of time to find the value of the corresponding key; if the static Bloom filter structure is used to store the key-value pairs, it can only process Static data, which is very unrealistic in practical applications. Therefore, in a high-speed computer network, how to efficiently store this information and quickly query the corresponding key-value pair becomes a challenge.

Bloom filter is a space-saving and query-efficient data structure, which can meet the needs of efficient resource interaction and search in today's life, and can effectively represent data sets. Bloom filter has been widely used in various computer systems since it was proposed by B.Bloom in 1970 to represent huge data sets and improve query efficiency. The essence of the Bloom filter structure is to map the elements in the set to a bit vector through k hash functions. While the Bloom filter achieves its efficient representation of the set, there is a certain false positive (an element does not belong to the set but is misjudged as belonging to the set) false positive rate when performing element query, but there is no false negative (an element does not belong to the set). It belongs to the set and is misjudged as not belonging to the set) misjudgment, which has higher efficiency in query and storage.

But traditional bloom filters can only support subordinate queries of whether an element exists in a collection. If the element is key, it can only support the subordinate query of whether the key exists in the collection, but cannot support the (key, value) operation. Because Bloom filters cannot store values directly, you cannot use traditional Bloom filters to operate on key-value pairs. To make the Bloom filter support the basic operations of key-value pairs, it is necessary to improve the traditional Bloom filter and design a new Bloom filter structure.

SUMMARY OF THE INVENTION

The technical problem to be solved by the present invention is to provide a Bloom filter tree structure and a key-value pair storage method for dynamically storing key-value pairs in view of the deficiencies of the prior art.

In order to solve the above-mentioned technical problems, the technical solution adopted in the present invention is: a Bloom filter tree structure for dynamically storing key-value pairs, including a complete d-ary tree; each node of each complete d-ary tree is A Bloom filter; each leaf node of each complete d-ary tree represents a value value; the storage unit size of each node is half of the storage unit size of the parent node of the node, and the root node includes d×k There are different hash functions, that is, the root node includes d hash groups, and each group includes k hash functions.

Correspondingly, the present invention also provides a method for storing key-value pairs in a Bloom filter tree structure, comprising:

Insertion operation: When a key-value pair (key, value) needs to be inserted, first check whether the value has been inserted into the Bloom filter. If it has not been inserted, a subsequent operation of adding a new value is required; if the value already exists in the Bloom filter In the Bloom filter tree, the key-value pair is inserted directly, the leaf node corresponding to the value is searched according to the value, the position code of the leaf node is obtained, a unique path from the root node to the leaf node is determined, and the root node is calculated. Two sets of hash functions, that is, use k hash functions h _(i,1) ,h _(i,2) ,...,h _(i,k) for the key, and calculate h _(i,1) (key) ,h _(i,2) (key),...,h _(i,k) (key),; where i represents the group number of the selected hash function, i=1 or 2; The hash value is stored in the array A, and the hash value calculated by i=2 is stored in the array B; then, according to the first bit code of the leaf node, a set of values in the A and B arrays are selected at the root node for insertion, That is, perform a right-shift zero-bit operation on the A or B array, and then obtain the next Bloom filter that needs to be inserted according to the first bit code of the leaf node, and then select A, A group of values in the B array is shifted to the right by one bit to obtain the insertion position and inserted; continue the above operation, and insert the key into each layer of Bloom filter until the leaf node corresponding to the value is inserted;

Query operation: When you need to query the value corresponding to a key value key, first, calculate the two sets of hash functions h _(i,1) (key),h _(i,2) (key),...,h of the root node. _(i,k) (key) (i=1 or 2), save their values in the two arrays of A and B respectively; at the root node, query the location units corresponding to the values of the two arrays of A and B, respectively, Find the first code value; according to the obtained code value, go to the next node to continue the query, at this time, perform a right-shift operation on the two arrays A and B, and query at the corresponding position unit to obtain a code value; continue Carry out the above operations until the leaf node is found, and finally obtain a complete encoded value, and perform the decoding operation according to the encoding of the leaf node to obtain the corresponding value;

Add new value operation: To add a new value to the Bloom filter, there are two cases: if the original Bloom filter is a binary tree that is not full, when a new value needs to be added, directly in Add a new leaf node at the end of the Bloom filter, which represents the newly added value; if the original Bloom filter is a full binary tree, add a new Bloom filter above the root node , the size of the newly added bloom filter is twice the root node of the original bloom filter tree, at this point, the new bloom filter becomes a new bloom filter tree The root node of the original Bloom filter becomes the left subtree of the new root node, and then a full binary tree that is one level less than the original Bloom filter tree is created as the right subtree of the new root node. Subtree, move all the positions set to 1 on the original root node to the left by one place, and insert them into the new root node. At this time, the two sets of _H3 hash functions of the new root node are more than the original two sets of _H3 hash functions. One more layer, that is, select one more row in the basis function, and continue to add new leaf nodes at the end of the Bloom filter.

In the inserting operation, the method for selecting the array to be inserted at the root node is as follows: if the encoded value is 0, select the A array, and if the encoded value is 1, select the B array.

In the insertion operation, according to the first code of the leaf node, the method for obtaining the next Bloom filter that needs to be inserted into the operation is: if the code value is 0, the left node is operated; if the code value is 1, then Operate the right node.

Compared with the prior art, the present invention has the beneficial effects as follows: the present invention can greatly reduce the application fields in which a large amount of data is generated and the key-value pair query needs to be performed, such as database interactive query, resource location in high-speed network, computer network monitoring, etc. Set query time, reduce resource consumption, process dynamically arriving data, and adapt to the network environment.

Description of drawings

每组有k个哈希函数。一个叶节点就表示一个value，根据叶节点的编码可以得到一条由根节点到叶节点的唯一路径。根据叶节点编码，如果编码值为0，则对第一组哈希函数进行移位操作；如果编码值为1，则对第二组哈希函数进行移位操作。图1中

就是

得来的，

就是

得来的，而

是

得来的，

是

得来的。Figure 1 is a schematic diagram of the structure of a Bloom tree, which combines a Bloom filter with the structure of a binary tree, and each node is a Bloom filter. The root node has two sets of _H3 hash functions

Each group has k hash functions. A leaf node represents a value, and a unique path from the root node to the leaf node can be obtained according to the encoding of the leaf node. According to the leaf node encoding, if the encoded value is 0, the first group of hash functions is shifted; if the encoded value is 1, the second group of hash functions is shifted. In Figure 1

that is

come,

that is

come, and

Yes

come,

Yes

come.

Figure 2 is a schematic diagram of the operation of adding a new value to an underfilled binary tree. When a value that does not exist in a leaf node needs to be inserted, if the binary tree is not a full binary tree, a leaf node can be added directly at the end of the tree to represent the inserted value. The leaf node coded as 11 in the figure is the newly added value.

其中

是由

得到，将原二叉树根节点中所有置向左移一位，插入到level 3中；而

则是从原来的基矩阵中比

多选取一行即可。此时构建了一棵新的未满二叉树，可以直接在树的末尾添加叶节点，表示插入的value。如图中编码为100的叶节点就是新添加的value。Figure 3 is a schematic diagram of the operation of adding a new value to a full binary tree. When a value that does not exist in a leaf node needs to be inserted, if the binary tree is a full binary tree, a leaf node cannot be added to the original tree. At this time, it is necessary to extend one level up, as shown in the newly added level 3 in Figure 3. The original binary tree becomes the left subtree of level 3, and a full binary tree with one level less than the original binary tree is constructed as the right subtree of level 3. At this time, there are also two sets of H3 hash functions at level ₃

in

By

Get, move all the positions in the root node of the original binary tree one bit to the left, and insert it into level 3; and

is compared from the original basis matrix

Just select more than one row. At this point, a new under-full binary tree is constructed, and a leaf node can be added directly at the end of the tree to represent the inserted value. The leaf node coded as 100 in the figure is the newly added value.

Figure 4 is the detailed information of the implementation environment data, including data source, data time, and packet size. The present embodiment is compared with the research results in recent years, including: Bloom Tree is a paper in INFOCOM in 2014 "Bloom tree: A search tree based on bloom filters for multiple-set membership testing", a structure that combines tree and bloom filter structures for key-value pair queries, the algorithm uses d on each bloom filter node The group hash function is calculated from the root node until the leaf node corresponding to the value is found. This algorithm can only process static data; COMB is the paper "Fast dynamic multiple-set membership testing" in IEEE/ACM Transactions on Networking in 2012 A key-value pair query algorithm based on Bloom filter proposed by usingcombinatorial bloom filters", the algorithm encodes the value value, selects the appropriate number of Bloom filters for the known number of value groups and the number of bloom filters that need to be interpolated. The number of Bloom filters. When querying, you need to query all Bloom filters to get the corresponding codes.

Figures 5(a) to 5(f) are Bloom filter trees of fixed size m=2 ²⁰ bits. Under different numbers of hash functions, three different algorithms SBFT, Bloom Tree and COMB are used to process 1024 Group data, compared on the average processing time of the data. Figure 5(a) is a schematic diagram of the experimental results obtained by using the data set MAWI 1 for simulation experiments, Figure 5(b) is a schematic diagram of the experimental results obtained by using the data set MAWI 2 for simulation experiments, and Figure 5(c) is using the data set MAWI. 3. The schematic diagram of the experimental results obtained by the simulation experiment. Figure 5(d) is a schematic diagram of the experimental results obtained by the simulation experiment using the data set ClarkNet-HTTP, and Figure 5(e) is a schematic diagram of the experimental results obtained by the simulation experiment using the data set UMass. Figure 5(f) is a schematic diagram of the experimental results obtained by using the data set TKN for simulation experiments. All the data results in Fig. 5(a)-Fig. 5(f) show that for each dataset, our proposed algorithm SBFT takes the least time to process the data on average. Compared with Bloom Tree, our algorithm only needs to select d groups of hash functions at the root node for calculation, and then perform the shift operation, while BloomTree requires each node to select d groups of hash functions for calculation, which is time-consuming; and COMB is also similar. COMB needs to select multiple hash functions for each Bloom filter, which takes a lot of time. However, the number of Bloom filters that COMB needs to operate is less than that of Bloom Tree, so it takes a long time. Will be smaller than Bloom Tree.

Figure 6 is a schematic diagram of the memory consumption state when three algorithms are used to process static data. The data results show that the memory consumption of the three algorithms is the same, that is to say, our algorithm does not consume excess memory when processing the data with the least amount of time.

Figures 7(a) to 7(f) are schematic diagrams of the time-consuming situation of the three algorithms for processing data packets when the data packets increase continuously. Each group uses k=3 hash functions. Since the two algorithms of Bloom Tree and COMB operate under the condition of known data volume, the structure needs to be set up when the data packet has not been inserted. Our algorithm, on the other hand, can operate on an unknown amount of data and process data as packets arrive, which is a process of dynamically processing data. Figure 7(a) is a schematic diagram of the experimental results obtained by using the data set MAWI1 for simulation experiments, Figure 7(b) is a schematic diagram of the experimental results obtained by using the data set MAWI 2 for simulation experiments, and Figure 7(c) is a schematic diagram of the experimental results using the data set MAWI 3 Figure 7(d) is a schematic diagram of the experimental results obtained by the simulation experiment using the data set ClarkNet-HTTP, and Figure 7(e) is a schematic diagram of the experimental results obtained by using the data set UMass to carry out the simulation experiment. 7(f) is a schematic diagram of the experimental results obtained from the simulation experiment using the dataset TKN. All data results in Figure 7 show that for each data set, our algorithm processes data packets is a dynamic process, and processing data takes less time than Bloom Tree and COMB, while Bloom Tree and COMB process data packets by It is a static process and takes more time.

Figures 8(a) to 8(f) are schematic diagrams of the memory consumption of the three algorithms for processing data packets when the data packets continue to increase. Each group uses k=3 hash functions. Figure 8(a) is a schematic diagram of the experimental results obtained by using the data set MAWI 1 for simulation experiments, Figure 8(b) is a schematic diagram of the experimental results obtained by using the data set MAWI 2 for simulation experiments, and Figure 8(c) is using the data set MAWI. 3. The schematic diagram of the experimental results obtained by the simulation experiment. Figure 8(d) is a schematic diagram of the experimental results obtained by the simulation experiment using the data set ClarkNet-HTTP, and Figure 8(e) is a schematic diagram of the experimental results obtained by the simulation experiment using the data set UMass. Figure 8(f) is a schematic diagram of the experimental results obtained by using the data set TKN for simulation experiments. All the data results in Figures 8(a) to 8(f) show that for each data set, our algorithm is a dynamic process to process data packets. Our algorithm is a process of building structures while processing data, while Bloom Tree and COMB processing data packets is a static process, and the structure has been built before processing data, which also means that their structure can only process static data.

Detailed ways

When processing static data in this implementation, the selected memory size is m=2 ²⁰ bits, the root node occupies ₉₅₃₂₅ bits, the H3 hash function base matrix with 18 rows and 8 columns is selected, and the first 16 bits of the base matrix are extracted from the root node. row, k=3 hash functions are selected for each group, and the data of the group number g=1024 groups are processed, and the tree height h=10 at this time. Figure 1 is a schematic diagram of a static Bloom tree structure, from which the key-value pair insertion and query process can be analyzed.

Insert (key, value) process: Find the leaf node corresponding to the value according to the value, get the position code of the leaf node, and then determine a unique path from the root node to the leaf node. Calculate the two sets of hash functions of the root node, and use k hash functions h _(i,1) ,h _(i,2) ,...,h _(i,k) for the key (i represents the selected hash function group number) to calculate h _(i,1) (key),h _(i,2) (key),...,h _(i,k) (key), and store their values in two arrays A, in B. Then, according to the first code of the leaf node, select a set of values in the A and B arrays at the root node for insertion (if the code value is 0, select the A array, if the code value is 1, select the B array), That is, it is equivalent to right-shifting the zero-bit operation on the A and B arrays (A>>0 or B>>0). Then, according to the first bit code of the leaf node, the next Bloom filter that needs to be inserted is obtained (if the code value is 0, the left node is operated, and if the code value is 1, the right node is operated). Then, according to the second bit code of the leaf node, select a set of values in the A and B arrays to perform a right-shift operation (A>>1 or B>>1) to obtain the insertion position. Continue to perform similar operations, inserting the key into each layer of Bloom filters until the leaf node corresponding to the value is inserted. As shown in Figure 1, assuming that the code corresponding to the value in the inserted key-value pair is 01, calculate the two sets of hash functions of the root node, and store their values in the two arrays A and B respectively; since the first bit of the code is 0 , then select array A and move 0 bits to the right of the root node, A>>0, and insert it into the root node, and then reach the left node in the next step; since the second bit of the code is 1, then select the array B and shift one bit to the right of this node B>>1 Insert into the node, the next step is to reach the right node; finally, directly move the array B to the right by two bits B>>2 to insert the node to complete the insertion operation.

Query (key) process: First, calculate the two sets of hash functions h _(i,1) (key),h _(i,2) (key),...,h _(i,k) (key) of the root node ) (i=1 or 2), where i represents the group number of the selected hash function, the hash value calculated by i=1 is stored in array A, and the hash value calculated by i=2 is stored in array B. At the root node, query the position units corresponding to the two array values of A and B respectively. If the values of the corresponding positions are all 1, it is satisfied, and the first code value is found (if the A array is satisfied, the code is 0, If the B array is satisfied, the code is 1. If it is not satisfied, the key value does not exist, and the query ends). According to the obtained code value, go to the next node to continue the query. At this time, the two arrays A and B need to be shifted to the right (A>>1, B>>1), and the corresponding position unit is queried to get a encoded value. Continue similar operations until a leaf node is found. Finally, a complete encoded value is obtained, and the corresponding value can be obtained according to the encoding of this leaf node. Figure 1 illustrates as an example: Assuming to query the key, first calculate the two sets of hash functions of the root node, and store their values in the two arrays A and B respectively; query the values of the two arrays A and B in the root node respectively. , the values in the A array are all 1 in the corresponding position unit in this node, then the first bit code is recorded as 0, and the next operation node is the left node; move the A and B arrays to the right by one bit A>>1, B>>1, query in this node respectively, the value in the B array is 1 in the corresponding position unit in this node, then record the second bit code as 1, and the next operation node is the right node; the last step, Directly move the B array to the right by two bits B>>2 to query, that is, the final verification. This step does not need to record the code value. If the verification passes, the query code is 01, and the corresponding value can be found in the table to complete the query.

When processing dynamic data in this embodiment, the operation of adding a new value can be divided into two cases: if the original Bloom tree is a binary tree that is not full, when a new value needs to be added, a new leaf can be added directly at the end of the tree node, this leaf node represents the newly added value, as shown in Figure 2, the new leaf node coded as 11; if the original Bloom tree is a full binary tree, then a new cloth needs to be added above the root node. Bloom filter, the size of this Bloom filter is twice the size of the original root node, at this time, the new Bloom filter is the new root node, and the original Bloom tree becomes this root The left subtree of the node, and then create a full binary tree that is one level less than the original Bloom tree as the right subtree of the new root node. In the new root node, the two sets of _H3 hash functions of the root node are one layer more than the original two sets of _H3 hash functions, that is, one more row is selected in the base function, and at this time, the tree can be continued. A new leaf node is added at the end of , such as the new leaf node with the code 100 in Figure 3.

Claims (3)

1. A method for storing key-value pairs in a Bloom filter tree structure, the Bloom filter tree structure includes a complete d-ary tree, and each node of each complete d-ary tree is a Bloom Filter; each leaf node of each complete d-ary tree represents a value value; the storage unit size of each node is half of the storage unit size of the parent node of the node, and the root node includes d×k different The hash function, that is, the root node includes d hash groups, and each group includes k hash functions; it is characterized in that, it includes: Insertion operation: When a key-value pair (key, value) needs to be inserted, first check whether the value has been inserted into the Bloom filter. If it has not been inserted, a subsequent operation of adding a new value is required; if the value already exists in the Bloom filter In the Bloom filter tree, the key-value pair is inserted directly, the leaf node corresponding to the value is searched according to the value, the position code of the leaf node is obtained, a unique path from the root node to the leaf node is determined, and the root node is calculated. Two sets of hash functions, that is, k hash functions h _i,1 ,hi _,2 ,...,hi _,k are used for the key to calculate h _i,1 key,hi _,2 key,... ,h _i,k key, where i represents the group number of the selected hash function, i=1 or 2; the hash value calculated by i=1 is stored in array A, and the hash value calculated by i=2 is stored in In the array B; then, according to the first bit code of the leaf node, select a set of values in the A and B arrays at the root node for insertion, that is, perform a right-shift zero-bit operation on the A or B array, and then according to the first bit of the leaf node. One-bit encoding to get the next Bloom filter that needs to be inserted, and then according to the second-bit encoding of the leaf node, select a set of values in the A and B arrays to perform a right-shift operation to obtain the insertion position, and perform Insert; continue the above operation, insert the key into each layer of Bloom filter until the leaf node corresponding to the value is inserted; Query operation: When you need to query the value corresponding to a key value key, first, calculate the two sets of hash functions of the root node h _i,1 key,h _i,2 key,...,hi _,k key, i=1 Or 2, save their values in the two arrays of A and B respectively; at the root node, query the position units corresponding to the values of the two arrays A and B, and find the first code value; according to the obtained code value , go to the next node to continue the query, at this time, perform the right-shift operation on the two arrays A and B, and query the corresponding position unit to get a coded value; continue the above operation until the leaf node is found, and finally get A complete encoded value, decoded according to the leaf node code to obtain the corresponding value; Add new value operation: To add a new value to the Bloom filter, there are two cases: if the original Bloom filter is a binary tree that is not full, when a new value needs to be added, directly in Add a new leaf node at the end of the Bloom filter, which represents the newly added value; if the original Bloom filter is a full binary tree, add a new Bloom filter above the root node , the size of the newly added bloom filter is twice the root node of the original bloom filter tree, at this point, the new bloom filter becomes a new bloom filter tree The root node of the original Bloom filter becomes the left subtree of the new root node, and then a full binary tree that is one level less than the original Bloom filter tree is created as the right subtree of the new root node. Subtree, move all the positions set to 1 on the original root node to the left by one place, and insert them into the new root node. At this time, the two sets of _H3 hash functions of the new root node are more than the original two sets of _H3 hash functions. One more layer, that is, select one more row in the basis function, and continue to add new leaf nodes at the end of the Bloom filter. 2. method according to claim 1, is characterized in that, in described inserting operation, the method that selects the array to be inserted at root node is: if the coding value is 0, then selects the A array, if the coding value is 1, Then select B array. 3. method according to claim 1, is characterized in that, in described insert operation, according to the first code of leaf node, the method that obtains the Bloom filter that needs to carry out insert operation next is: if coded value If it is 0, operate the left node, if the encoded value is 1, operate the right node.

Images