System and methods for removing obsolete data in a distributed system of hybrid storage and compute nodes

1. A non-transitory machine-readable medium having executable instructions to cause one or more processing units to perform a method to garbage collect in a distributed storage system, the method comprising:

generating a live object map of live objects stored on the distributed storage system in a plurality of block segments distributed across a plurality of storage controller servers, wherein the live object map is a probabilistic data structure storing a list of valid objects;

scanning the plurality of block segments to generate segment summary statistics, wherein the segment summary statistics indicates the number of live objects stored in the plurality of block segments; and

compacting each of the plurality of block segments that have a low utilization based on the segment summary statistics.

2. The non-transitory machine-readable medium of claim 1 , wherein the probabilistic data structure is a bloom filter.

3. The non-transitory machine-readable medium of claim 1 , wherein the generating the live object map comprises:

traversing a metadata tree; and

adding an object to the live object map for each entry in the metadata tree.

4. The non-transitory machine-readable medium of claim 1 , wherein generating the live object map comprises:

adding list of objects being deduplicated to the live object map.

5. The non-transitory machine-readable medium of claim 1 , wherein the generating the live object map comprises:

traversing a metadata tree for entry having the same generation number; and

adding an object to the live object map for each entry in the metadata tree.

6. The non-transitory machine-readable medium of claim 1 , wherein the scanning comprises:

building a keylist for the segment; and

verifying the number of live keys in the live object map.

7. The non-transitory machine-readable medium of claim 1 , wherein the compacting comprises:

moving live keys of the segment forward;

adding a tombstone for remaining keys of the segment; and

deleting the segment.

8. A computerized method that garbage collects in a distributed storage system, the method comprising:

generating a live object map of live objects stored on the distributed storage system in a plurality of block segments distributed across a plurality of storage controller servers, wherein the live object map is a probabilistic data structure storing a list of valid objects;

scanning the plurality of block segments to generate segment summary statistics, wherein the segment summary statistics indicates the number of live objects stored in the plurality of block segments; and

compacting each of the plurality of block segments that have a low utilization based on the segment summary statistics.

9. The computerized method of claim 8 , wherein the probabilistic data structure is a bloom filter.

10. The computerized method of claim 8 , wherein the generating the live object map comprises:

traversing a metadata tree; and

adding an object to the live object map for each entry in the metadata tree.

11. The computerized method of claim 8 , wherein generating the live object map comprises:

adding list of objects being deduplicated to the live object map.

12. The computerized method of claim 8 , wherein the generating the live object map comprises:

traversing a metadata tree for entry having the same generation number; and

adding an object to the live object map for each entry in the metadata tree.

13. The computerized method of claim 8 , wherein the scanning comprises:

building a keylist for the segment; and

verifying the number of live keys in the live object map.

14. The computerized method of claim 8 , wherein the compacting comprises:

moving live keys of the segment forward;

adding a tombstone for remaining keys of the segment; and

deleting the segment.

15. A distributed storage system to garbage collect in a distributed storage system, the distributed storage system comprising:

an interconnection network; and

a plurality of storage controllers, interconnected by the interconnection network, wherein each of the plurality of storage controllers includes,

a garbage collection module that performs garbage collection in the distributed storage system, the garbage collection module including,

a live object map module that generates a live object map of live objects stored on the distributed storage system in a plurality of block segments distributed across a plurality of storage controller servers, wherein the live object map is a probabilistic data structure storing a list of valid objects;

a segment cleaner, coupled to the live object map, that scans the plurality of block segments to generate segment summary statistics, wherein the segment summary statistics indicates the number of live objects stored in the plurality of block segments; and

segment compacter, coupled to the segment cleaner, that compacts each of the plurality of block segments that have a low utilization based on the segment summary statistics.

16. The distributed storage system of claim 15 , wherein the probabilistic data structure is a space-efficient approximate membership data-structure.

17. The distributed storage system of claim 15 , wherein segment compacter includes a segment drop module that moves live keys of the segment forward, adds a tombstone for remaining keys of the segment, and deletes the segment.

18. A non-transitory machine-readable medium having executable instructions to cause one or more processing units to perform a method to garbage collect in a distributed storage system, the method comprising:

generating a live object map of live objects stored on the distributed storage system in a plurality of block segments distributed across a plurality of storage controller servers, wherein the generating the live object includes,

traversing a metadata tree, and

adding an object to the live object map for each entry in the metadata tree;

scanning the plurality of block segments to generate segment summary statistics, wherein the segment summary statistics indicates the number of live objects stored in the plurality of block segments; and

compacting each of the plurality of block segments that have a low utilization based on the segment summary statistics.

19. A non-transitory machine-readable medium having executable instructions to cause one or more processing units to perform a method to garbage collect in a distributed storage system, the method comprising:

generating a live object map of live objects stored on the distributed storage system in a plurality of block segments distributed across a plurality of storage controller servers, wherein the generating the live object includes,

adding list of objects being deduplicated to the live object map;

scanning the plurality of block segments to generate segment summary statistics, wherein the segment summary statistics indicates the number of live objects stored in the plurality of block segments; and

compacting each of the plurality of block segments that have a low utilization based on the segment summary statistics.

20. A non-transitory machine-readable medium having executable instructions to cause one or more processing units to perform a method to garbage collect in a distributed storage system, the method comprising:

generating a live object map of live objects stored on the distributed storage system in a plurality of block segments distributed across a plurality of storage controller servers;

scanning the plurality of block segments to generate segment summary statistics, wherein the segment summary statistics indicates the number of live objects stored in the plurality of block segments, wherein the scanning includes,

building a keylist for the segment; and

verifying the number of live keys in the live object map; and

compacting each of the plurality of block segments that have a low utilization based on the segment summary statistics.