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.