Incremental bloom filter rebuild for B+ trees under multi-version concurrency control

Patent metadata

Field	Value
Publication number	US-10795872-B2
Application number	US-201715398832-A
Country	US
Kind code	B2
Filing date	Jan 5, 2017
Priority date	Jun 29, 2016
Publication date	Oct 6, 2020
Grant date	Oct 6, 2020

Abstract

A method comprising: processing an update to a search tree and updating statistics, the search tree storing information about one or more objects indexed by corresponding object keys; determining to rebuild a first Bloom filter based on the statistics, the first Bloom filter associated with the search tree; generating a second Bloom filter associated with the search tree; populating the second Bloom filter as part of a tracing garbage collection process; and replacing the first Bloom filter with the second Bloom filter.

First claim

What is claimed is:

1. A method comprising:
processing an update to search tree, the search tree storing information about one or more objects indexed by corresponding object keys;
determining an estimated accuracy for a first Bloom filter based on a ratio of a tree object count and a filter object count, wherein; (i) the tree object count includes a count of objects that are currently stored in the search tree, and (ii) the filter object count includes a sum of the count of objects that are currently stored in the search tree and a count of objects that have been deleted from the search tree;
determining to rebuild the first Bloom filter based on the estimated accuracy, the first Bloom filter associated with the search tree;
generating a second Bloom filter associated with the search tree;
populating the second Bloom filter as part of a tracing garbage collection process, the populating including visiting any of a plurality of leaves in the search tree by the trace garbage collection process, and adding, to the second Bloom filter, an object key that corresponds to a leaf; and
replacing the first Bloom filter with the second Bloom filter.

2. The method of claim 1 wherein processing the update to the search tree comprises:
if the update includes adding an object to the search tree, adding Information about the object to the search tree indexed by a corresponding object key, adding the corresponding object key to the first Bloom filter, incrementing the object count, and incrementing the filter object count; and
if the update includes deleting an object to the search tree, deleting information about the object from the search tree and decrementing the tree object count.

3. The method of claim 2 further comprising;
determining a target object count for the search tree,
wherein determining to rebuild the first Bloom filter is further based on comparing the target object count and the tree object count.

4. The method of claim 3 further comprising generating the first Bloom filter having a capacity determined using the target object count for the search tree.

5. A system comprising:
one or more processors;
a volatile memory; and
a non-volatile memory storing computer program code that when executed on the processor causes execution across the one or more processors of a process operable to perform the operations of:
processing an update to a search tree, the search tree storing information about one or more objects indexed by corresponding object keys:
determining an estimated accuracy for a first Bloom filter based on a ratio of a tree object count and a filter object count, wherein; (i) the tree object count includes a count of objects that are currently stored in the search tree, and (ii) the filter object count includes a sum of the count of objects that are currently stored in the search tree and a count of objects that have been deleted from the search tree;
determining to rebuild the first Bloom filter based on the estimated accuracy, the first Bloom filter associated with the search tree;
generating a second Bloom filter associated the search tree:
populating the second Bloom filter as part of a tracing garbage collection process, the populating including visiting any of a plurality of leaves in the search tree by the trace garbage collection process, and adding, to the second Bloom filter, an object key that corresponds to a leaf; and
replacing the first Bloom filter with the second Bloom filter.

6. The system of claim 5 wherein processing the update to the search tree comprises:
if the update includes adding an object to the search tree, adding information about the object to the search tree indexed by a corresponding object key, adding the corresponding object key to the first Bloom filter, incrementing the tree object count, and incrementing the filter object count; and
if the update includes deleting an object to the search tree, deleting information about the object from the search tree and decrementing the tree object count.

7. The system of claim 6 wherein the process is further operable to perform the operation of determining a target object count for the search tree, and determining to rebuild the first Bloom filter is further based on comparing the target object count and the tree object count.

8. The system of claim 7 wherein the process is further operable to perform the operation of generating the first Bloom filter having a capacity determined using the target object count for the search tree.

9. A computer program product tangibly embodied in a non-transitory computer-readable medium, the computer-readable medium storing program instructions that are executable to:
process an update to a search tree, the search tree storing information about one or more objects indexed by corresponding object keys;
determining an estimated accuracy for a first Bloom filter based on a ratio of a tree object count and a filter object count, wherein: (i) the tree object count includes a count of objects that are currently stored in the search tree, and (ii) the filter object count includes a sum of the count of objects that are currently stored in the search tree and a count of objects that have been deleted from the search tree;
determine to rebuild the first Bloom filter based on the estimated accuracy, the first Bloom filter associated with the search tree;
generate a second Bloom filter associated with the search tree;
populate the second Bloom filter as part of a tracing garbage collection process, the populating including visiting any of a plurality of leaves in the search tree by the trace garbage collection process, and adding, to the second Bloom filter, an object key that corresponds to a leaf; and
replace the first Bloom filter with the second Bloom filter.

10. The computer program product of claim 9 wherein processing the update to the search tree comprises:
if the update includes adding an object to the search tree, adding information about the object to the search tree indexed by a corresponding object key, adding the corresponding object key to the first Bloom filter, incrementing the tree object count, and incrementing the filter object count; and
if the update includes deleting an object to the search tree, deleting information about the object from the search tree and decrementing the tree object count.

11. The computer program product of claim 10 , the computer-readable medium storm program instructions that are further executable to:
determining a target object count for the search tree,
wherein determining to rebuild the first Bloom filter is further based on comparing the target object count and the tree object count.

12. The computer program product of claim 11 , the computer-readable medium storing program instructions that are further executable to generate the first Bloom filter having a capacity determined using the target object count for the search tree.

Assignees

• Emc Ip Holding Co Llc

Inventors

• Danilov Mikhail
• Malygin Mikhail
• Tchoub Ivan
• Fedorov Alexander
• Gutsalov Nikita

Classifications

• G06F16/2246 Primary

  Trees, e.g. B+trees · CPC title

• G06F12/0261

  using reference counting · CPC title

• G06F12/0269

  Incremental or concurrent garbage collection, e.g. in real-time systems (G06F12/0261 takes precedence) · CPC title

• G06F16/2329

  using versioning · CPC title

• G06F2212/1024

  Latency reduction · CPC title