System and method for logical deletion of stored data objects

• US 9,235,476 B2
• Filed: 03/30/2015
• Issued: 01/12/2016
• Est. Priority Date: 09/21/2010
• Status: Expired due to Fees

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: McHugh, Jason G., Gattu, Praveen Kumar, Ten-Pow, Michael A., Denny-Brown, Derek Ernest II
• Primary Examiner(s): LI, ZHUO H
• Application Number:
  US14/673,808
• Publication Number:
  US 20150205677A1
• Time in Patent Office: 288 Days
• US Class Current: 1/1
• 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 system, comprising:

a data store that stores a plurality of objects, wherein each of the plurality of objects is identified by a combination of a corresponding key and a corresponding version identifier;

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

receive a request to perform a delete operation specifying a key;

determine whether the request to perform the delete operation specifies a version identifier corresponding to the key specified in the request; and

in response to determining that the request does not specify a version identifier corresponding to the specified key;

generate a new, unique version identifier;

create a delete marker object identified by the specified key and the new, unique version identifier;

refrain from deleting, in response to receiving the request to perform a delete operation, any of the plurality of objects previously stored in the data store; and

store 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 specified key.

2. The system of claim 1, wherein the key and the version identifier of each object form a composite key for the object.

3. The system of claim 2, wherein at least some of the plurality of objects stored in the data store further comprise object data, and wherein the composite key is stored with the object.

4. The system of claim 1, wherein the delete marker object becomes the latest object version that is stored in the data store corresponding to the specified key.

5. The system of claim 1, wherein the data store is part of a network-based data storage service, and wherein the request to perform the delete operation is received from a particular user of a plurality of users of the network-based data storage service.

6. The system of claim 1, wherein the data store is part of a network-based data storage service, and wherein the request to perform the delete operation is received via an application program interface (API) of the network-based data storage service from a client application or process.

7. The system of claim 1, wherein the program instructions are further executable by the one or more processors to cause the one or more processors to:

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

in response to receiving the second request;

generate a second, unique version identifier;

create a second delete marker object identified by the second, unique version identifier and the specified key;

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

store the second delete marker object in the data store.

8. The system of claim 1, wherein the program instructions are further executable by the one or more processors to cause the one or more processors to:

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

in response to receiving the second request, delete an object from the data store identified by both the specified particular key and the specified version identifier.

9. 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:

determine, in response to receiving a request to perform a delete operation that specifies a particular key, whether the request to perform the delete operation specifies a version identifier for the particular key;

wherein the particular key and a version identifier collectively identify a particular object of a plurality of objects stored in a data store; and

in response to determining that the request does not specify a version identifier for the particular key;

generate a new, unique version identifier;

create a delete marker object identified by the particular key and the new, unique version identifier;

refrain from deleting, in response to receiving the request to perform a delete operation, any of the plurality of objects stored in the data store; and

store 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 key.

10. The non-transitory, computer readable storage medium of claim 9, wherein the program instructions when executed on the one or more computers further cause the one or more computers to make the delete marker object become the latest object version that is stored in the memory corresponding to the particular key.

11. The non-transitory, computer readable storage medium of claim 9, wherein the delete marker object does not contain object data.

12. The non-transitory, computer readable storage medium of claim 9, wherein at least some of the plurality of objects stored in the data store comprise object data and wherein the program instructions when executed on the one or more computers further cause the one or more computers to:

receive, subsequent to storing the delete marker object, a request to retrieve an object, wherein the request specifies the particular key; and

in response to receiving the request to retrieve the object;

return an error indication; and

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

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

generate, in response to receiving a second request to perform a delete operation, a second, unique version identifier, wherein the second request specifies the particular key but does not specify a version identifier;

create a second delete marker object identified by the second, unique version identifier and the particular key;

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

store the second delete marker object in the data store.

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

in response to receiving a second request to perform a delete operation, wherein the second request specifies a key and a version identifier, delete an object from the data store identified by the specified key and the specified version identifier.

15. The non-transitory, computer readable storage medium of claim 14, wherein the specified key is the particular key, wherein the specified version identifier is the new, unique version identifier, and wherein said delete an object comprises deleting the delete marker object.

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

store the new unique version identifier in a data store separate from the data store storing the plurality of objects.

17. A method, performed by one or more computers, comprising:

receiving, by the one or more computers, a request to perform a delete operation, wherein the request specifies a particular key;

wherein the particular key and a version identifier collectively identify a particular object of a plurality of objects stored in a data store;

determining whether the request to perform the delete operation specifies a version identifier for the particular key; and

in response to determining that the request does not specify a version identifier for the particular key;

generating a new, unique version identifier;

creating a delete marker object identified by the particular key and the new, unique version identifier;

refraining from deleting, in response to receiving the request to perform a delete operation, any of the plurality of objects previously stored in the data store; 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 key.

18. The method of claim 17, wherein at least some of the plurality of objects stored in the data store comprise object data, and wherein the method further comprises, subsequent to said storing the delete marker object:

receiving a request to retrieve an object, wherein the request specifies the particular 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.

19. The method of claim 17, 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 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 identified by the second, unique version identifier and the particular 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.

20. The method of claim 17, 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 key and the new unique version identifier; and

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