Data storage space recovery

• US 9,817,578 B2
• Filed: 06/05/2015
• Issued: 11/14/2017
• Est. Priority Date: 06/05/2015
• Status: Expired due to Fees

• Current Assignee: eBay Inc.
• Original Assignee: eBay Inc.
• Inventors: Rao, Vinay Pundalika, Lewis, Mark S., Povzner, Anna
• Primary Examiner(s): PORTKA, GARY J
• Application Number:
  US14/732,605
• Publication Number:
  US 20160357450A1
• Time in Patent Office: 893 Days
• Field of Search: 707813, 707814, 707817, 707818, 707820, 711161, 711162, 711165
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: G06F 12/0261 using reference counting
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0631 by allocating resources to storage systems
• CPC Class Codes: G06F 3/0644 Management of space entities, e.g. partitions, extents, pools
• CPC Class Codes: G06F 3/0647 Migration mechanisms
• CPC Class Codes: G06F 3/0683 Plurality of storage devices

Abstract

Storage space is reclaimed by cleaning and compacting data objects where data objects are stored by immutable storage. A storage area of which space needs to be reclaimed is identified. Active and stale data objects stored in a storage area are identified, and only active data objects are transferred to a shadow storage area from the storage area when recovering storage space. I/O operations can be fulfilled from the storage area and the shadow storage area. Compaction requests and I/O requests are throttled according to QOS parameters. Recovery of storage space does not cause a failure to meet performance requirements for any storage volume.

Claims

1. A computer-implemented method of managing storage of data objects to a data storage environment comprising a plurality of storage nodes, the method comprising:

receiving write requests for data objects;

storing the data objects at the storage nodes according to the write requests;

updating a storage manager catalog that maps data object identifications (DOIDs) for the data objects with actual storage locations of the data objects, wherein the DOID for a data object is calculated based on content of the data object;

wherein, if the data object is a revised version of a previously stored data object, the revised data object has a different DOID than the previously stored data object, the revised data object is stored at a different storage location than the previously stored data object and without overwriting the previously stored data object, and the storage manager catalog is updated to reflect that the previously stored data object has been superseded by the revised version by decreasing a count of a number of instances of the previously stored data object by one and increasing a count of a number of instances of the revised data object by one;

identifying a storage area to recover storage space, the storage area storing data objects that are indicated as stale or active in the storage manager catalog; and

recovering the storage space while fulfilling read and write requests;

wherein the process of recovering storage space is implemented as compaction requests to compact the data objects from the storage area to a shadow storage area, the compaction requests being interspersed with read and write requests to the storage nodes, and

wherein read requests for the active data objects are fulfilled from the storage area and write requests for new data objects are fulfilled using the shadow storage area during the process of recovering storage space.

2. The method of claim 1 wherein the process of recovering storage space does not consume more than ten percent of the maximum I/O operations per second for any storage node.

3. The method of claim 1 wherein the process of recovering storage space does not increase average latency for read and write requests to any storage node by more than ten percent.

4. The method of claim 1 wherein the data objects are organized into storage volumes, and the process of recovering storage space does not cause a failure to meet performance requirements for any storage volume.

5. The method of claim 1 further comprising adjusting a rate at which the process of recovering storage space is performed.

6. The method of claim 1 wherein read and write requests to the storage nodes are managed by a system queue, and the compaction requests and the read and write requests in the system queue are throttled according to QOS parameters.

7. The method of claim 1 wherein recovering the storage space comprises:

for the storage area of a storage node containing the stale data objects;

creating the shadow storage area;

for each data object stored in the storage space;

responsive to determining that the data object is active as indicated in the storage manager catalog, copying the data object from the storage area to the shadow storage area;

responsive to determining that the data object is stale as indicated in the storage manager catalog, keeping the data object in the storage area without copying the data object to the shadow storage area; and

after copying of the active data objects stored in the storage space to the shadow storage area is completed, cutting over from the storage area to the shadow storage area.

8. The method of claim 1, wherein write requests for all data objects are fulfilled using the shadow storage area.

9. The method of claim 1 wherein the storage nodes are divided into partitions, and the process of recovering storage space occurs on a per-partition basis.

10. The method of claim 9 wherein the partitions are identified by DOID locators.

11. The method of claim 9 wherein a rate at which the process of recovering storage space is performed is adjustable by adjusting a number of partitions per storage node for which storage space is being recovered.

12. The method of claim 1 wherein initiation of the process of recovering storage space is based on available storage capacity.

13. The method of claim 12 wherein the process of recovering storage space is initiated when available storage space falls below ten percent of the total storage capacity.

14. The method of claim 1 wherein initiation of the process of recovering storage space is based on time.

15. The method of claim 1 wherein the storage manager catalog includes a count of a number of instances of a data object that are currently referenced, and a data object is indicated as stale in the storage manager catalog when the count is zero.

16. The method of claim 15 wherein the storage manager catalog includes a count of a number of instances of a data object that are currently referenced, and a data object is indicated as stale in the storage manager catalog when the count has remained zero for a grace period.

17. The method of claim 15 wherein the data objects are organized into storage volumes, and the storage manager catalog includes a count of a number of instances of a data object that is currently referenced for different storage volumes.

18. The method of claim 1 wherein storing the data objects at the storage nodes comprises storing new data objects sequentially within each partition in the storage nodes.

19. The method of claim 1 wherein updating the storage manager catalog comprises adding entries for new data objects sequentially within the storage manager catalog.

20. A non-transitory computer-readable storage medium storing computer program modules for managing storage of data objects to a data storage environment comprising a plurality of storage nodes, the computer program modules executable to perform steps comprising:

receiving write requests for data objects;

storing the data objects at the storage nodes according to the write requests;

updating a storage manager catalog that maps data object identifications (DOIDs) for the data objects with actual storage locations of the data objects, wherein the DOID for a data object is calculated based on content of the data object;

wherein, if the data object is a revised version of a previously stored data object, the revised data object has a different DOID than the previously stored data object, the revised data object is stored at a different storage location than the previously stored data object and without overwriting the previously stored data object, and the storage manager catalog is updated to reflect that the previously stored data object has been superseded by the revised version by decreasing a count of a number of instances of the previously stored data object by one and increasing a count of a number of instances of the revised data object by one;

identifying a storage area to recover storage space, the storage area storing data objects that are indicated as stale or active in the storage manager catalog; and

recovering the storage space while fulfilling read and write requests;

wherein the process of recovering storage space is implemented as compaction requests to compact the data objects from the storage area to a shadow storage area, the compaction requests being interspersed with read and write requests to the storage nodes, and

wherein read requests for the active data objects are fulfilled from the storage area and write requests for new data objects are fulfilled using the shadow storage area during the process of recovering storage space.

21. A data storage environment comprising:

a plurality of application nodes that send application read requests and application write requests for data objects;

a plurality of storage nodes in communication with the application nodes, the storage nodes for storing the data objects organized as storage volumes, the storage nodes comprising;

a storage manager catalog that maps data object identifications (DOIDs) for the data objects with actual storage locations of the data objects, wherein the DOD for a data object is calculated based on content of the data object;

wherein, if the data object is a revised version of a previously stored data object, the revised data object has a different DOID than the previously stored data object, the revised data object is stored at a different storage location than the previously stored data object and without overwriting the previously stored data object, and the storage manager catalog is updated to reflect that the previously stored data object has been superseded by the revised version by decreasing a count of a number of instances of the previously stored data object by one and increasing a count of a number of instances of the revised data object by one; and

a storage manager compaction module that identifies a storage area to recover storage space and recovers the storage space allocated for data objects that are indicated as stale in the storage manager catalog, wherein the process of recovering storage space is implemented as compaction requests to compact data objects stored in the storage area to a shadow storage area, the compaction requests being interspersed with read and write requests to the storage nodes,

wherein read requests for the active data objects are fulfilled from the storage area and write requests for new data objects are fulfilled using the shadow storage area during the process of recovering storage space.