Managing data object versions in a storage service

• US 10,528,536 B1
• Filed: 05/19/2014
• Issued: 01/07/2020
• Est. Priority Date: 05/19/2014
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Gattu, Praveen Kumar, Gonen, Aykud, Nadal, Jonathan Jorge, Seth, Abhilasha, Sun, Huan, Denny-Brown, II, Derek Ernest
• Primary Examiner(s): Ly, Anh
• Application Number:
  US14/281,785
• Time in Patent Office: 2,059 Days
• Field of Search: 707609-704
• CPC Class Codes: G06F 16/1873 Versioning file systems, temporal file systems, e.g. file system supporting different historic versions of files
• CPC Class Codes: G06F 16/219 Managing data history or versioning querying versioned data G06F16/2474; querying temporal data G06F16/2477

Abstract

A method and apparatus for managing keys pertaining to data objects are disclosed. In the method and apparatus, a plurality of keys that are associated with a plurality of data objects are retained, whereby the plurality of keys are capable of being listed in accordance with an ordering scheme. The ordering scheme is used to inspect the plurality of keys to determine whether a data object associated with a key of the plurality of keys satisfies a criterion. One or more actions are taken on the key or associated data object based at least in part on determining that the criterion is satisfied, whereby an order of taking the one or more actions is a reverse of an order by which the key is listed in accordance with the ordering scheme.

Claims

1. A computer-implemented method for managing data object versions, comprising:

ordering a plurality of keys according to an ordering scheme, a key of the plurality of keys being a sequence of symbols and being associated with a version of a data object retained by a storage service, the ordering scheme permitting ordering the key of the plurality of keys in accordance with a creation time of the version of the data object;

providing an interface to cause retention of a plurality of versions of the data object;

scanning the ordered plurality of keys to identify, for the key of the plurality of keys, whether the associated version of the data object meets one or more criteria for removal from the storage service, the one or more criteria specifying a time period that the associated version of the data object is to be retained by the storage service; and

on a condition that the version of the data object meets the one or more criteria, processing the plurality of keys in a reverse order according to the ordering scheme and removing the key of the plurality of keys in accordance with the reverse order if the version of the data object that is associated with the key of the plurality of keys is found to meet the one or more criteria.

2. The computer-implemented method of claim 1, wherein:

the ordering scheme is a lexicographic ordering; and

the computer-implemented method further comprises;

receiving a request to store a first version of a first data object; and

assigning the first version of the first data object a first key based at least in part on a creation time of the first version of the first data object, the first key being capable of being sorted in accordance with the lexicographic ordering that permits ordering the first key in accordance with the creation time of the first version of the first data object.

3. The computer-implemented method of claim 1, wherein processing the plurality of keys in the reverse order further includes reevaluating if the version of the data object that is associated with the key of the plurality of keys meets the one or more criteria.

4. The computer-implemented method of claim 1, wherein the one or more criteria specify that the time elapsing from a creation time of a successor key to the key of the plurality of keys in accordance with the reverse order is greater than a threshold.

5. A system, comprising:

at least one computing device that implements one or more services that;

retain a plurality of keys, a key of the plurality of keys being associated with a data object;

provide an interface to cause retention of a plurality of versions of the data object;

utilize an ordering scheme to process the plurality of keys in a forward order to the ordering scheme to determine whether the data object associated with the key of the plurality of keys satisfies a criterion; and

take one or more actions on the key of the plurality of keys or the associated data object based at least in part on determining that the criterion is satisfied, an order of taking the one or more actions is a reverse of an order by which the key is listed in accordance with the ordering scheme, by at least visiting each key of the plurality of keys in the reverse order.

6. The system of claim 5, wherein:

the key is generated based at least in part on a creation time of the data object; and

the ordering scheme permits ordering the plurality of keys in accordance with the creation time of the associated data object.

7. The system of claim 6, wherein the creation time of the data object is an upload initiation time or an upload completion time of the data object.

8. The system of claim 5;

wherein;

the criterion specifies a maximum retention time for the data object associated with the key; and

the data object is removed from storage if a period of time elapsing from a creation time of a successor to the data object exceeds the maximum retention time.

9. The system of claim 5, wherein a key that is associated with the data object is further associated with a version of the data object.

10. The system of claim 5, wherein the one or more actions include relocating the data object to another storage service.

11. The system of claim 5, wherein the one or more services are configured to receive, from a customer of the one or more services, a policy specifying the criterion and the one or more actions to be taken due at least in part to satisfaction of the criterion.

12. The system of claim 5, wherein processing the plurality of keys further includes retrieving, for a key of the plurality of keys, metadata associated with the key or metadata associated with a successor key to the key of the plurality of keys and evaluating the metadata associated with the key or the metadata associated with the successor key to determine whether the criterion is satisfied.

13. A non-transitory computer-readable storage medium storing thereon executable instructions that, as a result of being executed by one or more processors of a computer system, cause the computer system to at least:

sort a plurality of keys in accordance with an ordering scheme, a key of the plurality of keys pertaining to a data object of a plurality of data objects;

provide an interface to cause retention of a plurality of versions of the data object;

identify a plurality of subsets of the plurality of keys;

a subset of the plurality of subsets including a group of keys of the plurality of keys, the plurality of subsets comprising an order that is in accordance with the ordering scheme;

cause the order of sorting the plurality of keys to be reversed by at least;

reversing the order of the plurality of subsets; and

for each subset of the plurality of the subsets, reversing an order of the group of keys of the subset; and

visit the plurality of keys in the reverse order to take one or more actions on a key, of the plurality of keys.

14. The non-transitory computer-readable storage medium of claim 13, wherein identifying the plurality of subsets of the plurality of keys further includes determining an identifier for each subset of the plurality of subsets.

15. The non-transitory computer-readable storage medium of claim 14, wherein the identifier is a first key or a last key of the subset as ordered according to the ordering scheme.

16. The non-transitory computer-readable storage medium of claim 14, wherein reversing the order of the plurality of subsets further includes reversing an order of the plurality of identifiers.

17. The non-transitory computer-readable storage medium of claim 13, wherein the one or more actions include at least one of removing the key or relocating a data object associated with the key.

18. The non-transitory computer-readable storage medium of claim 13, wherein the ordering scheme is based at least in part on lexicographic ordering and the ordering scheme permitting ordering the plurality of keys in accordance with a creation time of their associated plurality of data objects.

19. The non-transitory computer-readable storage medium of claim 13, wherein the instructions further comprise instructions that, as a result of being executed by the one or more processors, cause the computer system to scan the plurality of keys in accordance with the ordering scheme to determine whether a key of the plurality of keys satisfies a criterion for taking one or more actions on the key.

20. The non-transitory computer-readable storage medium of claim 19, wherein the criterion is an age of a version represented by the key.