System and method for logical deletion of stored data objects

• US 9,563,578 B2
• Filed: 01/11/2016
• Issued: 02/07/2017
• 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., Gattu, Praveen Kumar, Ten-Pow, Michael A., Denny-Brown, Derek Ernest II
• Primary Examiner(s): LI, ZHUO H
• Application Number:
  US14/992,915
• Publication Number:
  US 20160124870A1
• Time in Patent Office: 393 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 comprises a user key and a version identifier, wherein at least two of the plurality of objects further comprise object data, and wherein at least two versions of at least two of the plurality of objects correspond to respective access control lists;

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, from a requester, to retrieve a particular access control list corresponding to a particular object version of a particular object from the data store, wherein the request specifies a user key; and

in response to receiving the request to retrieve the particular access control list;

determining whether the particular object version is a delete marker object comprising the specified user key, wherein the presence of a delete marker object comprising the specified user key in the data store indicates a prior logical deletion of the particular object from the data store;

determining whether the requester has permission to retrieve the particular access control list;

in response to determining that the particular object version is a delete marker object comprising the specified user key, returning an error indication;

in response to determining that the requester does not have permission to retrieve the particular access control list, returning an error indication; and

in response to determining that the particular object version is not a delete marker object and that the requester has permission to retrieve the particular access control list, returning the particular access control list.

2. The system of claim 1, wherein the version identifier of the particular object version is specified in the request to retrieve the particular access control list.

3. The system of claim 1,

wherein the request to retrieve the particular access control list does not specify a version identifier;

wherein when executed by the one or more processors, the program instructions further cause the one or more processors to perform;

determining the version identifier of a latest object version that includes the specified user key; and

wherein the version identifier of the particular object version corresponding to the particular access control list is the version identifier of the latest object version that includes the specified user key.

4. The system of claim 1, wherein the delete marker object does not contain object data.

5. The system of claim 1, wherein when executed by the one or more processors, the program instructions further cause the one or more processors to perform, prior to receiving the request to retrieve the particular access control list:

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

in response to receiving the request to perform a delete operation;

generating a new, unique version identifier;

creating the delete marker object, wherein the delete marker object comprises the specified user key and the new, unique version identifier, and wherein the delete marker object becomes the latest object version that is stored in the memory that comprises the specified user key; and

refraining from deleting the plurality of objects previously stored in the memory in response to receiving the request to perform a delete operation; and

storing the delete marker object in the data store.

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

receiving a request to perform a delete operation, wherein the request to perform a delete operation includes the specified user key and a version identifier of the delete marker object; and

in response to receiving the request to perform a delete operation, deleting the delete marker object from the data store.

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

receiving a request to perform an operation to list user keys of the objects stored in the data store; and

in response to receiving the request to perform an operation to list user keys;

returning a list of user keys contained in object versions stored in the data store, wherein the list does not include user keys contained in delete marker objects that are the latest object versions containing those user keys.

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

receiving a request to perform an operation to list all object versions stored in the data store; and

in response to receiving the request to perform an operation to list all object versions;

returning a list of all object versions stored in the data store, wherein the list includes all delete marker objects stored in the data store.

9. The system of claim 1, 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 request to perform a delete operation, wherein the request specifies a user key, but does not specify a version identifier; and

in response to receiving the request to perform a delete operation;

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.

10. The system of claim 9, wherein creating the second delete marker object 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.

11. 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, from a requester, to add an access control list to a particular object version of a particular object stored in a data store on one or more of the one or more computers, wherein the request specifies a user key, wherein the data store stores a plurality of objects, wherein each of the plurality of objects comprises a user key and a version identifier, and wherein the presence of a delete marker object comprising a particular user key in the data store indicates a prior logical deletion of a corresponding object from the data store; and

in response to receiving the request to add the access control list, in response to determining that the particular object version is not a delete marker object and in response to determining that the requester has permission to add the access control list to the particular object version, setting the access control list for the particular object version.

12. The non-transitory, computer-readable storage medium of claim 11,

wherein the request to add the access control list to the particular object version specifies a user key but does not specify a version identifier corresponding to the particular object version;

and

in response to receiving the request to add the access control list to the particular object version;

determining whether the latest object version stored in the data store that contains the specified user key is a delete marker object; and

in response to determining that the latest object version stored in the data store that contains the specified user key is a delete marker object;

returning an error indication; and

refraining from adding the access control list to the plurality of objects stored in the data store.

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

receiving a request to perform an operation to list all object versions stored in the data store; and

in response to receiving the request to perform an operation to list all object versions;

returning a list of all object versions stored in the data store, wherein the list includes one or more delete marker objects that are stored in the data store.

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

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

in response to receiving the request to perform a delete operation;

generating a new, unique version identifier;

creating a delete marker object, wherein the delete marker object comprises the specified user key and the new, unique version identifier, and wherein the delete marker object becomes the latest object version that is stored in the data store that comprises the specified user key; and

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

storing the delete marker object in the data store.

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

receiving a request to perform a delete operation, wherein the request specifies a user key and a version identifier, and wherein the specified user key and version identifier pair identifies a delete marker object; and

in response to receiving the request to perform a delete operation, deleting the delete marker object from the data store.

16. The non-transitory, computer-readable storage medium of claim 11, wherein delete marker objects stored in the data store do not contain object data.

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

suspending an object versioning feature for the data store;

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

in response to receiving the request to perform a delete operation;

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

storing the new delete marker object in the data store;

wherein creating the new 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.

18. A method, comprising:

receiving a request, from a requester, to modify a particular access control list that corresponds to a particular object version of a particular object stored in a data store on one or more computers, wherein the request specifies a user key, wherein the data store stores a plurality of objects, wherein each of the plurality of objects comprises a user key and a version identifier, and wherein the presence of a delete marker object comprising a particular user key in the data store indicates a prior logical deletion of a corresponding object from the data store; and

in response to receiving the request to modify the particular access control list, in response to determining that the particular object version is not a delete marker object and in response to determining that the requester has permission to modify the particular access control list, overwriting at least a portion of the particular access control list for the particular object version.

19. The method of claim 18, further comprising, in response to receiving a different request to modify the particular access control list:

determining whether the latest object version stored in the data store that contains the specified user key is a delete marker object, wherein the request to modify the particular access control list does not specify a version identifier corresponding to the particular object version; and

in response to determining that the latest object version stored in the data store that contains the specified user key is a delete marker object, returning an error indication.

20. The method of claim 18, further comprising, in response to receiving a different request, from a different requester, to modify the particular access control list:

determining whether the different requester has permission to modify the particular access control list; and

in response to determining that the different requester does not have permission to modify the particular access control list;

returning an error indication; and

refraining from modifying the particular access control list.