1. A method, comprising: performing, by a computer system: storing a plurality of objects in a memory, wherein each of the plurality of objects comprises a user key and a version identifiers; 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 the particular user key and a new, unique version identifier 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; and subsequent to said storing the delete marker object and subsequent to performing one or more mutating operations specifying the particular user key after said storing the delete marker object, determining whether the delete marker object is no longer needed to ensure correct operation of the computer system in response to requests to perform operations that specify the particular user key; and in response to determining that the delete marker object is no longer needed to ensure correct operation of the computer system in response to requests to perform operations that specify the particular user key, deleting the delete marker object from the memory.