1. A method, comprising: performing, by a computer system that stores a plurality of data objects in a distributed storage system: receiving a request to store an instance of a data object in the distributed storage system, wherein the request comprises a composite key for the data object, and wherein the composite key comprises a sharable user key and one or more other elements usable to uniquely identify the instance of the data object; generating keymap information for the instance of the data object that maps the user key to a locator and the locator to the instance of the data object; applying a hash function to a portion of the composite key that is less than all of the composite key; determining a computing node on which to store the keymap information dependent on a result of said applying the hash function, wherein the computing node is one of a plurality of computing nodes that each store a portion of a distributed hash table; storing the keymap information on the determined computing node, wherein the determined computing node also stores keymap information for other data object instances that are related to the instance of the data object.