A Construction Method of Bloom Filter for Multi-layer Database Based on Hierarchical Allocation

Abstract

The invention discloses a bloom filter construction method based on a hierarchical and distributive multi-layer database. The method is characterized by comprising the steps of designing and constructing a storage structure, calculating a combination probability sum, solving the digit distributed to each layer of a Bloom filter and maintaining the storage structure; when a union operation is carried out, more Bloom filter bit digit is distributed to each key at high layer located at a multi-layer key value database (LevelDB), and less Bloom filter bit digit is distributed to keys at lower layer, wherein the false alarm rate of the Bloom filter is reduced with the increasing of the bit digit. Compared with an LevelDB traditional Bloom filter construction method, when memory overhead is ensure to be consistent with traditional memory overhead, according to the method, hard disk input and output (I / O) operation caused by false alarm of the Bloom filter can be reduced, the times of I / O of the hard disk are reduced, and average delay of LevelDB query operation is reduced; when expected times of I / O of the hard disk are ensured to be basically equal to that of a traditional method in the process of query, the memory overhead brought about by the Bloom filter is reduced.

Description

technical field [0001] The invention belongs to the technical field of computer data storage, and in particular relates to a Bloom filter construction method for hierarchically allocating the number of bits of a Bloom filter of a multi-layer key-value database system using a log merging tree as a main body. Background technique [0002] The Bloom filter (Space / time trade-offs in hash) introduced by the American Association for Computing Machinery's "1970 ACM CACM International Journal" (Communications of the ACM, Volume 13, July 1970, Question 7, Pages 422-426) coding with allowable errors) is an extremely space-efficient probabilistic data structure for checking the presence or absence of an element in a collection. When the multi-layer key-value database system (LevelDB) based on the log merge tree deployed on the hard disk that is open sourced by Google implements and uses the Bloom filter technology, it stores the key-value pairs in the file (SSTable) for each layer. A ...

AI Technical Summary

Problems solved by technology

[0003] The purpose of the present invention is to propose a method for constructing a Bloom filter based on hierarchical allocation of multi-layer databases, so as to make up for the existing defect of assigning fixed bits to each key in each file in each layer, and to ensure that the distribution On the premise that the storage space overhead of the Bloom filter is the same as before, reduce the hard disk input / output (I / O) operations caused by the false positives of the Bloom filter in the query operation of LevelDB, improve the query operation speed of LevelDB, or in Ensure that the overall false positive rate of the LevelDB Bloom filter is basically the same as before, and reduce the storage space, that is, the memory overhead

Images