System and method for logical deletion of stored data objects

• US 8,504,758 B1
• Filed: 09/21/2010
• Issued: 08/06/2013
• Est. Priority Date: 09/21/2010
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: McHugh, Jason G., Denny-Brown, Derek E. II, Gattu, Praveen K., Ten-Pow, Michael A.
• Primary Examiner(s): Thai, Tuan
• Assistant Examiner(s): LI, ZHUO H
• Application Number:
  US12/886,757
• Time in Patent Office: 1,050 Days
• Field of Search: 711/100, 711/108, 711/113, 711/115, 711/135, 711/154, 711/E12.001, 711/E12.026, 711/E12.037, 707/705, 707/737, 707/638, 707/662, 707/781, 707/782, 726/2, 726/5, 726/8
• US Class Current: 711/100
• CPC Class Codes: G06F 11/1435 using file system or storage system metadata
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 12/1466 Key-lock mechanism
• CPC Class Codes: G06F 16/162 Delete operations erasing in storage systems G06F3/0652
• 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/2329 using versioning
• CPC Class Codes: G06F 2201/80 Database-specific techniques
• CPC Class Codes: G06F 2201/84 Using snapshots, i.e. a logical point-in-time copy of the data
• CPC Class Codes: G06F 2212/1052 Security improvement
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0622 in relation to access
• 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]
• CPC Class Codes: G06F 3/0671 In-line storage system
• CPC Class Codes: G06F 3/0673 Single storage device

Abstract

Systems and methods for providing object versioning in a storage system may support the logical deletion of stored objects. In response to a delete operation specifying both a user key and a version identifier, the storage system may permanently delete the specified version of an object having the specified key. In response to a delete operation specifying a user key, but not a version identifier, the storage system may create a delete marker object that does not contain object data, and may generate a new version identifier for the delete marker. The delete marker may be stored as the latest object version of the user key, and may be addressable in the storage system using a composite key comprising the user key and the new version identifier. Subsequent attempts to retrieve the user key without specifying a version identifier may return an error, although the object was not actually deleted.

Claims

1. A method, comprising:

performing, by a computer system that stores a plurality of objects in a memory, wherein each of the plurality of objects comprises a composite key and object data, and wherein each composite key comprises a user key and a version identifier;

receiving a request to perform a delete operation, wherein the request to perform a delete operation specifies a particular user key but does not specify a version identifier;

in response to said receiving;

creating a delete marker object comprising a new composite key, wherein the delete marker object does not contain object data, and wherein said creating comprises;

generating a new, unique version identifier for the delete marker object; and

concatenating the new, unique version identifier for the delete marker object and the particular user key to generate the new composite key for the delete marker object;

refraining from deleting any of the plurality of objects previously stored in the memory in response to said receiving; and

storing the delete marker object in the memory, wherein the presence of the delete marker object in the memory indicates a logical deletion of the particular user key;

receiving a second request to perform a delete operation, wherein the second request to perform a delete operation specifies a second user key and a second, unique version identifier; and

in response to receiving the second request;

deleting an object stored in the memory that has a composite key comprising the second user key and the second, unique version identifier.

2. The method of claim 1, further comprising, subsequent to said storing the delete marker object:

receiving a request to retrieve an object, wherein the request specifies the particular user key; and

in response to receiving the request to retrieve an object;

returning an error indication; and

refraining from returning object data contained in any of the plurality of objects stored in the memory.

3. The method of claim 1, further comprising, subsequent to said storing the delete marker object:

receiving a third request to perform a delete operation, wherein the third request specifies the particular user key but does not specify a version identifier; and

in response to receiving the third request;

creating a second delete marker object comprising a second composite key, wherein the second delete marker object does not contain object data, and wherein creating the second delete marker comprises;

generating a second, unique version identifier; and

concatenating the second, unique version identifier and the particular user key to generate the second composite key;

refraining from deleting any of the plurality of objects stored in the memory or the delete marker object; and

storing the second delete marker object in the memory.

4. The method of claim 1, further comprising, subsequent to said storing the delete marker object:

receiving a third request to perform a delete operation, wherein the third request specifies the particular user key and the new, unique version identifier; and

in response to receiving the third request, deleting the delete marker object from the memory.

5. The method of claim 1, further comprising, subsequent to said storing the delete marker object:

receiving a request to list all object versions stored in the memory; and

in response to receiving the request to list all object versions, returning data representing a list of all object versions stored in the memory, wherein the list comprises the delete marker object.

6. A method, comprising:

performing, by a computer system that stores a plurality of objects in a memory, wherein each of the plurality of objects comprises a user key and a version identifier;

receiving a request to perform a delete operation, wherein the request to perform a delete operation specifies a particular user key but does not specify a version identifier; and

in response to said receiving;

generating a new, unique version identifier;

creating a delete marker object comprising the particular user key and the new, unique version identifier;

refraining from deleting any of the plurality of objects previously stored in the memory in response to said receiving; and

storing the delete marker object in the memory, wherein the presence of the delete marker object in the memory indicates a logical deletion of the particular user key.

7. The method of claim 6, wherein the user key and the unique version identifier of each object form a composite key for the object.

8. The method of claim 6, wherein at least some of the plurality of objects stored in the memory further comprise object data.

9. The method of claim 6, wherein the delete marker object does not contain object data.

10. The method of claim 6, wherein the delete marker object becomes the latest object version that is stored in the memory that comprises the particular user key.

11. The method of claim 6, further comprising, subsequent to said storing the delete marker object:

receiving a request to retrieve an object, wherein the request specifies the particular user key; and

in response to receiving the request to retrieve an object;

returning an error indication; and

refraining from returning object data contained in any of the plurality of objects stored in the memory.

12. The method of claim 6, further comprising, subsequent to said storing the delete marker object:

receiving a second request to perform a delete operation, wherein the second request specifies the particular user key but does not specify a version identifier; and

in response to receiving the second request;

generating a second, unique version identifier;

creating a second delete marker object comprising the second, unique version identifier and the particular user key;

refraining from deleting any of the plurality of objects stored in the memory; and

storing the second delete marker object in the memory.

13. The method of claim 6, further comprising, subsequent to said storing the delete marker object:

receiving a second request to perform a delete operation, wherein the second request specifies a user key and a version identifier; and

in response to receiving the second request, deleting an object from the memory comprising the specified user key and the specified version identifier.

14. The method of claim 13, wherein the specified user key is the particular user key, wherein the specified version identifier is the new, unique version identifier, and wherein said deleting an object comprises deleting the delete marker object.

15. The method of claim 13, further comprising:

determining whether the second request was received from a requester that has permission to delete the object comprising the specified user key and the specified version identifier;

wherein said deleting the object is performed in response to determining that the second request was received from a requester that has permission to delete the object comprising the specified user key and the specified version identifier.

16. The method of claim 6, further comprising:

prior to said receiving a request to perform a delete operation, and prior to enabling an object versioning feature for the memory;

receiving an earlier request to perform a delete operation, wherein the earlier request specifies a user key, but does not specify a version identifier; and

in response to receiving the earlier request, deleting an object previously stored in the memory and comprising the specified user key and a special sentinel version identifier, wherein the special sentinel version identifier indicates that the object was stored in the memory while the object versioning feature was off or suspended for the memory.

17. The method of claim 6, further comprising:

suspending an object versioning feature for the memory;

receiving a second request to perform a delete operation, wherein the second request specifies a user key, but does not specify a version identifier; and

in response to receiving the second request;

creating a second delete marker object comprising a special, sentinel version identifier and the specified user key; and

storing the second delete marker object in the memory.

18. The method of claim 17, wherein creating the second delete marker comprises:

deleting object data contained in an object previously stored in the memory and comprising the specified user key and the special sentinel version identifier; and

marking the object previously stored in the memory and comprising the specified user key and the special sentinel version identifier as a delete marker object.

19. A system, comprising:

a data store that stores a plurality of objects, wherein each of the plurality of objects comprises a user key and a version identifier;

one or more processors;

a memory coupled to the one or more processors and storing program instructions that when executed by the one or more processors cause the one or more processors to perform;

receiving a request to perform a delete operation, wherein the request to perform a delete operation specifies a particular user key but does not specify a version identifier; and

in response to said receiving;

generating a new, unique version identifier;

creating a delete marker object comprising the particular user key and the new, unique version identifier;

refraining from deleting any of the plurality of objects previously stored in the data store in response to said receiving; and

storing the delete marker object in the data store, wherein the presence of the delete marker object in the data store indicates a logical deletion of the particular user key.

20. The system of claim 19, wherein the user key and the unique version identifier of each object form a composite key for the object.

21. The system of claim 19, wherein at least some of the plurality of objects stored in the data store further comprise object data.

22. The system of claim 21, wherein the delete marker object does not contain object data.

23. The system of claim 19, wherein the delete marker object becomes the latest object version that is stored in the data store that comprises the particular user key.

24. The system of claim 19, wherein when executed by the one or more processors, the program instructions further cause the one or more processors to perform, subsequent to said storing the delete marker object:

receiving a request to retrieve an object, wherein the request specifies the particular user key; and

in response to receiving the request to retrieve an object;

returning an error indication; and

refraining from returning object data contained in any of the plurality of objects stored in the data store.

25. The system of claim 19, wherein when executed by the one or more processors, the program instructions further cause the one or more processors to perform, subsequent to said storing the delete marker object:

receiving a second request to perform a delete operation, wherein the second request specifies the particular user key but does not specify a version identifier; and

in response to receiving the second request;

generating a second, unique version identifier;

creating a second delete marker object comprising the second, unique version identifier and the particular user key;

refraining from deleting any of the plurality of objects stored in the data store; and

storing the second delete marker object in the data store.

26. The system of claim 19, wherein when executed by the one or more processors, the program instructions further cause the one or more processors to perform, subsequent to said storing the delete marker object:

receiving a second request to perform a delete operation, wherein the second request specifies a user key and a version identifier; and

in response to receiving the second request, deleting an object from the data store comprising the specified user key and the specified version identifier.

27. The system of claim 26, wherein the specified user key is the particular user key, wherein the specified version identifier is the new, unique version identifier, and wherein said deleting an object comprises deleting the delete marker object.

28. The system of claim 26, wherein when executed by the one or more processors, the program instructions further cause the one or more processors to perform:

determining whether the second request was received from a requester that has permission to delete the object comprising the specified user key and the specified version identifier;

wherein said deleting the object is performed in response to determining that the second request was received from a requester that has permission to delete the object comprising the specified user key and the specified version identifier.

29. The system of claim 19, wherein when executed by the one or more processors, the program instructions further cause the one or more processors to perform:

prior to said receiving a request to perform a delete operation, and prior to enabling an object versioning feature for the data store;

receiving an earlier request to perform a delete operation, wherein the earlier request specifies a user key, but does not specify a version identifier; and

in response to receiving the earlier request, deleting an object previously stored in the data store and comprising the specified user key and a special sentinel version identifier, wherein the special sentinel version identifier indicates that the object was stored in the data store while the object versioning feature was off or suspended for the data store.

30. The system of claim 19, wherein when executed by the one or more processors, the program instructions further cause the one or more processors to perform:

suspending an object versioning feature for the data store;

receiving a second request to perform a delete operation, wherein the second request specifies a user key, but does not specify a version identifier; and

in response to receiving the second request;

creating a second delete marker object comprising a special, sentinel version identifier and the specified user key; and

storing the second delete marker object in the data store.

31. The system of claim 30, wherein creating the second delete marker comprises:

deleting object data contained in an object previously stored in the data store and comprising the specified user key and the special sentinel version identifier; and

marking the object previously stored in the data store and comprising the specified user key and the special sentinel version identifier as a delete marker object.

32. A non-transitory, computer-readable storage medium storing program instructions that when executed on one or more computers cause the one or more computers to perform:

receiving a request to perform a delete operation in regard to one of a plurality of objects stored in a data store, wherein each of the plurality of objects comprises a user key and a version identifier, wherein the request to perform a delete operation specifies a particular user key but does not specify a version identifier; and

in response to said receiving;

generating a new, unique version identifier;

creating a delete marker object comprising the particular user key and the new, unique version identifier;

refraining from deleting any of the plurality of objects previously stored in the memory in response to said receiving; and

storing the delete marker object in the memory, wherein the presence of the delete marker object in the memory indicates a logical deletion of the particular user key.

33. The non-transitory, computer-readable storage medium of claim 32, wherein when executed on the one or more computers, the program instructions further cause the one or more computers to perform, subsequent to said storing the delete marker object:

receiving a request to retrieve an object, wherein the request specifies the particular user key; and

in response to receiving the request to retrieve an object;

returning an error indication; and

refraining from returning object data contained in any of the plurality of objects stored in the data store.

34. The non-transitory, computer-readable storage medium of claim 32, wherein when executed on the one or more computers, the program instructions further cause the one or more computers to perform, subsequent to said storing the delete marker object:

receiving a second request to perform a delete operation, wherein the second request specifies the particular user key but does not specify a version identifier; and

in response to receiving the second request;

generating a second, unique version identifier;

creating a second delete marker object comprising the second, unique version identifier and the particular user key;

refraining from deleting any of the plurality of objects stored in the data store; and

storing the second delete marker object in the data store.

35. The non-transitory, computer-readable storage medium of claim 32, wherein when executed on the one or more computers, the program instructions further cause the one or more computers to perform:

prior to said receiving a request to perform a delete operation, and prior to enabling an object versioning feature for the data store;

receiving an earlier request to perform a delete operation, wherein the earlier request specifies a user key, but does not specify a version identifier; and

in response to receiving the earlier request, deleting an object previously stored in the data store and comprising the specified user key and a special sentinel version identifier, wherein the special sentinel version identifier indicates that the object was stored in the data store while the object versioning feature was off or suspended for the data store.