Copying garbage collector for B+ trees under multi-version concurrency control

• US 10,133,770 B2
• Filed: 06/27/2016
• Issued: 11/20/2018
• Est. Priority Date: 12/16/2015
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Inventors: Danilov, Mikhail, Malygin, Mikhail, Tchoub, Ivan, Wang, Chen, Srivastav, Shashwat, Fomin, Andrey
• Primary Examiner(s): Morrison, Jay A
• Application Number:
  US15/193,141
• Publication Number:
  US 20170177652A1
• Time in Patent Office: 876 Days
• CPC Class Codes: G06F 16/2272 Management thereof
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0652 Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

Structures and processes for garbage collection of search trees under Multi-Version Concurrency Control (MVCC). Such search trees may be used to store data within a distributed storage system. A process detects live search tree elements using tracing and then identify storage chunks having no live elements as garbage to be reclaimed. The process can be paused and resumed to reduce impact on other system processing. To reduce disk fragmentation, a garbage collector may copy pages between chunks prior to reclaiming chunk capacity. Also described is a resource efficient scheduler for a garbage collection.

Claims

1. A method for use with a distributed storage system comprising a plurality of storage devices, the method comprising:

traversing a plurality of search trees to identify one or more elements stored in underpopulated storage chunks of the distributed storage system;

generating a plurality of copy requests corresponding to the identified elements, each of the copy requests corresponding to a different respective one of the identified elements;

merging the plurality of copy requests with one or more co-pending data update requests, the merging including discarding a copy request from the plurality of copy requests in response to detecting that the copy request corresponds to an element that is due to be modified by one of the co-pending data update requests;

executing any remaining, copy requests in the plurality of copy requests by copying respective ones of the identified elements that correspond to the remaining copy requests from the underpopulated storage chunks to different storage chunks; and

reclaiming storage capacity corresponding to the underpopulated storage chunks.

2. The method of claim 1 wherein modifying the element by one of the co-pending data update requests includes at least one of updating the element and dereferencing the element.

3. The method of claim 1 wherein traversing the plurality of search trees to identify one or more elements in underpopulated storage chunks comprises detecting whether any storage chunk in the distributed storage system is underpopulated based on whether a capacity of the storage chunk meets a predetermined threshold.

4. The method of claim 1, wherein the traversing of the plurality of search trees is interrupted when a predetermined number of elements stored in underpopulated storage chunks have been identified.

5. The method of claim 1 further comprising:

determining a number of unused storage chunks;

determining a number of underpopulated storage chunks; and

wherein the storage capacity corresponding to the underpopulated storage chunks is reclaimed based upon the number of unused storage chunks and the number of underpopulated storage chunks.

6. The method of claim 5 wherein the search trees include search trees associated with multiple different replication groups, wherein determining a number of unused storage chunks comprises determining a number of unused storage chunks associated with all search trees associated with the same replication group.

7. The method of claim 6 wherein determining a number of underpopulated storage chunks comprises determining a number of underpopulated storage chunks associated with all search trees associated with the same replication group.

8. The method of claim 6 wherein reclaiming storage capacity comprises reclaiming storage capacity for storage chunks associated with search trees in the same replication group.

9. The method of claim 5 wherein determining a number of underpopulated storage chunks comprises determining a number of underpopulated storage chunks having an age greater than a predetermined threshold age.

10. A distributed storage system comprising:

a plurality of storage devices;

two or more storage nodes configured to;

traverse a plurality of search trees to identify one or more elements stored in underpopulated storage chunks of the distributed storage system;

generate a plurality of copy requests corresponding to the identified elements, each of the copy requests corresponding to a different respective one of the identified elements;

merge the plurality of copy requests with one or more co-pending data update requests by discarding a copy request from the plurality of copy requests in response to detecting that the copy request corresponds to an element that is due to be modified by one of the co-pending data update requests;

execute any remaining copy requests in the plurality of copy requests by copying respective ones of the identified elements that correspond to the remaining copy requests from the underpopulated storage chunks to different storage chunks; and

reclaim storage capacity corresponding to the underpopulated storage chunks.

11. The system of claim 10 wherein modifying the element by one of the co-pending data update requests includes at least one of updating the element and dereferencing the element.

12. The system of claim 10 wherein traversing the plurality of search trees to identify elements stored within underpopulated storage chunks include detecting whether any storage chunk in the distributed storage system is underpopulated based on whether a capacity of the storage chunk meets a predetermined threshold.

13. The system of claim 10 wherein the traversal of the plurality of search trees is interrupted when a predetermined number of elements stored in underpopulated storage chunks have been identified.

14. The system of claim 10 wherein the storage nodes are further configured to:

determine a number of unused storage chunks;

determine a number of underpopulated storage chunks; and

wherein the storage capacity corresponding to the underpopulated storage chunks is reclaimed based upon the number of unused storage chunks and the number of underpopulated storage chunks.

15. The system of claim 14 wherein the storage nodes include a first pair of storage nodes in a first replication group and second pair of storage nodes in a second replication group, wherein the search trees include search trees associated with multiple different replication groups, and wherein the storage nodes are configured to determine a number of unused storage chunks for all search trees associated with the same replication group.

16. The system of claim 15 wherein the storage nodes are configured to determine a number of underpopulated storage chunks for all search trees associated with the same replication group.

17. The system of claim 15 wherein the storage nodes are configured to reclaim storage capacity for storage chunks associated with search trees in the same replication group.

18. The system of claim 14 wherein the storage nodes are configured to determine a number of underpopulated storage chunks having an age greater than a predetermined threshold age.