Data Storage Space Recovery

• US 20160357450A1
• Filed: 06/05/2015
• Published: 12/08/2016
• Est. Priority Date: 06/05/2015
• Status: Active Grant

• Current Assignee: eBay Inc.
• Original Assignee: Formation Data Systems, Inc.
• Inventors: Rao, Vinay Pundalika, Lewis, Mark S., POVZNER, Anna
• Granted Patent: US 9,817,578 B2
• Time in Patent Office: Days
• 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; and

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; and

recovering storage space allocated for data objects that are indicated as stale in the storage manager catalog, wherein the process of recovering storage space is interspersed with read and write requests to the storage nodes.

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 wherein a rate at which the process of recovering storage space is performed is adjustable.

6. The method of claim 1 wherein read and write requests to the storage nodes are managed by a system queue, and the process of recovering storage space is implemented as compaction requests interspersed with read and write requests in the system queue.

7. The method of claim 1 wherein recovering storage space allocated for data objects that are indicated as stale in the storage manager catalog comprises:

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

creating a shadow storage area;

copying active data objects from the storage area to the shadow storage area, without copying stale data objects from the storage area to the shadow storage area; and

after copying is completed, cutting over from the storage area to the shadow storage area.

8. The method of claim 7 further comprising, during the copying process, read requests for active data objects stored in the storage area are fulfilled from the storage area.

9. The method of claim 7 further comprising, during the copying process, write requests for new data objects are fulfilled using the shadow storage area.

10. The method of claim 7 further comprising, during the copying process, write requests for all data objects are fulfilled using the shadow storage area.

11. 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.

12. The method of claim 11 wherein the partitions are identified by DOID locators.

13. The method of claim 11 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.

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

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

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

17. 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.

18. The method of claim 17 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.

19. The method of claim 17 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.

20. 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.

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

22. 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; and

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; and

recovering storage space allocated for data objects that are indicated as stale in the storage manager catalog, wherein the process of recovering storage space is interspersed with read and write requests to the storage nodes.

23. 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 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; and

a storage manager compaction module that recovers storage space allocated for data objects that are indicated as stale in the storage manager catalog, wherein the process of recovering storage space is interspersed with read and write requests to the storage nodes.