1. A non-transitory computer-readable storage medium having stored thereon instructions that, upon execution by one or more computing devices, cause the one or more computing devices at least to: maintain on one or more storage devices a first version of a collection of key-value pairs, first version of the collection comprising a first version of a value; store a second version of the value in response to a request comprising a key and the second version of the value; associate an identifier of a second version of the collection with information indicative of an unaccepted state of the collection; store, on the storage device, a mapping between an extended key and the second version of the value, the extended key comprising the identifier of the second version of the collection and the key; access the first version of the value based at least in part on using the extended key to determine that the second version of the value is associated with the unaccepted state, wherein the extended key is identified by a subset of the extended key corresponding to the key; associate the identifier of the second version of the collection with information indicative of an accepted state in response to receiving information indicative of the second version of the collection being accepted; and access the second version of the value based at least in part on using the extended key to determine that the second version of the value is associated with an accepted state.