System and method for logical deletion of stored data objects

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.

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.