Probabilistic summary data structure based encoding for garbage collection

1. A method of performing garbage collection of an allocated address space in one or more storage devices, wherein the allocated address space has stored therein blocks of data that are referenced by a set of one or more active storage trees and blocks of data that are no longer referenced by the set of one or more active storage trees, the method comprising:

identifying the blocks of data that are referenced by the set of one or more storage trees by walking the set of one or more active storage trees;

encoding the referenced blocks of data into a probabilistic summary data structure, wherein encoding the referenced blocks of data into the probabilistic summary data structure comprises;

initializing the probabilistic summary data structure to zero;

performing a set of one or more hash functions on the referenced blocks, wherein the set of one or more hash functions generates a set of one or more offset values; and

setting bits in the probabilistic summary data structure that are at offsets equal to the set of one or more offset values generated by the hash functions; and

cleaning the allocated address space based on the probabilistic summary data structure to remove those blocks of data that are no longer referenced.

2. The method of claim 1 , wherein performing the set of one or more hash functions on the referenced blocks includes performing the hash functions on the identifications of the referenced blocks or on the data within the referenced blocks.

3. The method of claim 2 , wherein cleaning the allocated address space based on the probabilistic summary data structure comprises:

performing the following for each block of data within the allocated address space:

generating a bit vector for the block of data comprising:

performing the set of one or more hash functions on the block of data to generate a set of one or more offset values;

setting bits in the bit vector that are at offsets equal to the set of one or more offset values generated by the hash functions; and

comparing the bit vector with the probabilistic summary data structure to determine if the block is referenced;

copying the determined referenced block of data to an unallocated address space within the storage device; and

marking the allocated address space as unallocated.

4. The method of claim 3 , wherein new data overwrites the blocks of data stored in the previously allocated address space marked as unallocated.

5. The method of claim 1 , wherein the probabilistic summary data structure erroneously indicates that at least one non-referenced block is a referenced block.

6. The method of claim 1 , wherein a size of the probabilistic summary data structures fits within a memory of a computing device that is coupled to the one or more storage devices.

7. A method of performing garbage collection in a range of addresses to

be cleaned within an allocated address space of one or more storage devices, wherein the allocated address space has stored therein blocks of data that are referenced by a set of one or more active storage trees and blocks of data that are no longer referenced by the set of one or more active storage trees, the method comprising:

determining the range of addresses to be cleaned within an allocated address space;

encoding blocks of data within the range of addresses to be cleaned into a first probabilistic summary data structure, wherein encoding blocks of data within the range of addresses to be cleaned into the first probabilistic summary data structure comprises:

initializing the first probabilistic summary data structure to zero; and

performing the following for each block of data within the range of addresses to be cleaned:

performing a first set of one or more hash functions on the block of data, wherein each of the first set of one or more hash functions generates a set of one or more offset values; and

setting bits in the first probabilistic summary data structure that are at offsets equal to the set of one or more offset values generated by the first set of one or more hash functions;

identifying blocks of data that are referenced by the set of one or more active storage trees by walking the set of one or more active storage trees;

determining those blocks of data that are both referenced by the set of one or more active storage trees and within the range of addresses to be cleaned based on the first probabilistic summary data structure;

encoding the blocks of data that are both referenced and within the range of addresses to be cleaned into a second probabilistic summary data structure; and

cleaning the range of addresses to be cleaned within the allocated address space based on the second probabilistic summary data structure to remove those blocks of data that are no longer referenced.

8. The method of claim 7 , wherein performing the first set of one or more hash functions on the block of data comprises performing the first set of one or more hash functions on an identification of the block or on the data within the block.

9. The method of claim 8 , wherein determining those blocks of data that are both referenced by the set of one or more active storage trees and within the range of addresses to be cleaned based on the first probabilistic summary data structure comprises:

generating a bit vector for each referenced block comprising:

performing the first set of one or more hash functions on the referenced blocks of data, wherein each of the first set of one or more hash functions generates a set of one or more offset values;

setting bits in the bit vector that are at offsets equal to the set of one or more offset values generated by the first set of one or more hash functions; and

comparing the bit vector with the first probabilistic summary data structure to determine if the referenced block is in the range of addresses to be cleaned.

10. The method of claim 9 , wherein performing the first set of one or more hash functions on the referenced blocks of data includes performing the first set of one or more hash functions on an identification of the referenced block of data or on the data within the referenced block.

11. The method of claim 10 , wherein encoding the blocks of data into the second probabilistic summary data structure comprises:

initializing the second probabilistic summary data structure to zero; and

performing the following for each block that is both referenced and within the range of addresses to be cleaned:

performing a second set of one or more hash functions on the referenced block of data, wherein each of the second set of one or more hash functions generates a set of one or more offset values; and

setting bits in the second probabilistic summary data structure that are at offsets equal to the set of one or more offset values generated by the second set of one or more hash functions.

12. The method of claim 11 , wherein performing the second set of one or more hash functions on the referenced block of data includes performing the second set of one or more hash functions on an identification of the referenced block or on the data within the referenced block.

13. The method of claim 11 , wherein cleaning the range of addresses to be cleaned within the allocated address space based on the second probabilistic summary data structure comprises:

performing the following for each block of data within the range of addresses to be cleaned:

generating a bit vector for the block of data comprising:

performing the second set of one or more hash functions on the block of data, wherein each of the second set of one or more hash functions generates a set of one or more offset values; and

setting bits in the bit vector that are at offsets equal to the set of one or more offset values generated by the second set of one or more hash functions;

comparing the bit vector with the second probabilistic summary data structure to determine if the block of data is both referenced and within the range of addresses to be cleaned;

copying the block of data that is determined to be both referenced and within the range to be cleaned to an unallocated address space within the storage device; and

marking the range of addresses to be cleaned as unallocated.

14. The method of claim 13 , wherein new data overwrites the blocks of data stored within the range of addresses marked as unallocated.

15. The method of claim 12 , wherein performing the second set of one or more hash functions on an identification of the referenced blocks or on the data within the referenced blocks comprises:

generating a first hash based on the identification of the referenced block or the data within the referenced block; and

generating different hashes based on the first hash for the referenced block.

16. The method of claim 7 , wherein a size of the first and second probabilistic summary data structures fits within a memory of a computing device that is coupled to the one or more storage devices.

17. The method of claim 7 , wherein the probabilistic summary data structure erroneously indicates that at least one non-referenced block is a referenced block.

18. A machine-storage medium that provides instructions, which when executed by a machine, cause the machine to perform a method of garbage collecting in a range of addresses within an allocated storage space of one or more storage devices, wherein the allocated address space has stored therein blocks of data that are referenced by a set of one or more active storage trees and blocks of data that are no longer referenced by the set of one or more active storage trees, the method comprising:

determining the range of addresses to be cleaned within the allocated address space;

encoding blocks of data within the range of addresses to be cleaned into a first probabilistic summary data structure, wherein encoding blocks of data within the range of addresses to be cleaned into the first probabilistic summary data structure comprises:

initializing the first probabilistic summary data structure to zero; and

performing the following for each block of data with the range of addresses to be cleaned:

performing a first set of one or more hash functions on the block of data, wherein each of the first set of one or more hash functions generates a set of one or more offset values; and

setting bits in the first probabilistic summary data structure that are at offsets equal to the set of one or more offset values generated by the first set of one or more hash functions;

identifying blocks of data that are reference by other blocks of data by walking the set of one or more active storage trees;

determining those blocks of data that are both referenced by the set of one or more active storage trees and within the range of addresses to be cleaned based on the first probabilistic summary data structure;

encoding the blocks of data that are both referenced and within the range of addresses

to be cleaned into a second probabilistic summary data structure; and

cleaning the range of addresses to be cleaned within the allocated address space based on the second probabilistic summary data structure to remove those blocks of data that are no longer referenced.

19. The machine-storage medium of claim 18 , wherein performing the first set of one or more hash functions on the block of data includes performing the first set of one or more hash functions on an identification of the block or on the data within the block.

20. The machine-storage medium of claim 19 , wherein determining the blocks of data that are both referenced by the set of one or more active storage trees and within the range of addresses to be cleaned comprises:

performing the following for each referenced block:

generating a bit vector for each referenced block comprising:

performing the first set of one or more hash functions on the referenced block of data, wherein each of the first set of one or more hash functions generates a set of one or more offset values;

setting bits in the bit vector that are at offsets equal to the set of one or more offset values generated by the first set of one or more hash functions; and

comparing the bit vector with the first probabilistic summary data structure to determine if the referenced block is in the range of addresses to be cleaned.

21. The machine-storage medium of claim 20 , wherein encoding the blocks of data into the second probabilistic summary data structure comprises:

initializing the second probabilistic summary data structure to zero; and

performing the following for each block of data that is determined to be both referenced and within the range of addresses to be cleaned:

performing a second set of one or more hash functions on the block of data, wherein each of the second set of one or more hash functions generates a set of one or more offset values; and

setting bits in the second probabilistic summary data structure that are at offsets equal to the set of one or more offset values generated by the second set of one or more hash functions.

22. The machine-storage medium of claim 21 , wherein cleaning the range of addresses to be cleaned based on the second probabilistic summary data structure comprises:

performing the following for each block of data within the range of addresses to be cleaned:

generating a bit vector for the block of data comprising:

performing the second set of one or more hash functions on the block of data, wherein each of the second set of one or more hash functions generates a set of one or more offset values;

setting bits in the bit vector that are at offsets equal to the set of one or more offset values generated by the second set of one or more hash functions;

comparing the bit vector with the second probabilistic summary data structure to determine if the block of data is both referenced and in the range of addresses to be cleaned;

copying the block of data that is determined to be both referenced and within the range of addresses to be cleaned to an unallocated address space within the one or more storage devices; and

marking the range of addresses to be cleaned as unallocated.

23. The machine-storage medium of claim 18 , wherein a size of the first and second probabilistic summary data structures fits within a memory of a computing device that is coupled to the one or more storage devices.

24. A system for performing garbage collection within an allocated address space of one or more storage devices, wherein the allocated address space has stored therein blocks of data that are referenced by a set of one or more active storage trees and blocks of data that are no longer referenced by the set of one or more active storage trees, the system comprising:

a memory having stored therein a probabilistic summary data structure that represents blocks of data stored within the storage device that are referenced by the set of one or more active storage trees; and

a garbage collection logic comprising:

a traversal module for identifying blocks of data that are referenced by the set of one or more active storage trees by walking the set of one or more active storage trees;

an encoder for generating the probabilistic summary data structure, wherein the encoder comprises:

an intialization module to set bits within the probabilistic summary data structure to zero;

a hash module to perform a set of one or more hash functions on the referenced blocks to generate a set of one or more offset values; and

a write logic to set bits within the probabilistic summary data structure that are at offsets equal to the set of one or more offset values generated by the set of one or more hash functions; and

a collector for cleaning the allocated address space based on the probabilistic summary data structure to remove those blocks of data that are no longer referenced.

25. The system of claim 24 , wherein the collector comprises:

a bit vector generator comprising:

a hash module to perform the set of one or more hash functions on each of the blocks within the allocated address space to generate a set of one or more offset values; and

a write logic to set bits in the bit vector that are offsets equal to the set of one or more offset values;

an evaluator to compare the bit vector with the probabilistic summary data structure to determine if each of the blocks within the allocated address space is referenced;

a copier to copy the determined referenced blocks into an unallocated address space within the storage device; and

a marking module to mark the allocated address space as unallocated.

26. The system of claim 25 , wherein new data overwrites the blocks of data stored in the previously allocated address space marked as unallocated.

27. The system of claim 24 , wherein a size of the probabilistic summary data structure fits within the memory of the system.