1. A system, comprising: a plurality of computing nodes configured to implement: a web services interface configured to receive, according to a web services protocol, client requests for access to data objects, wherein a given one of said client requests for access to a given one of said data objects includes a key value corresponding to said given data object; a plurality of storage nodes configured to store replicas of said data objects, wherein each of said replicas is accessible via a respective locator value, and wherein each of said locator values is unique within said system; a keymap instance configured to store a respective keymap entry for each of said data objects, wherein for said given data object, said respective keymap entry includes said key value and each locator value corresponding to each stored replica of said given data object; and a coordinator configured to receive said client requests for access to said data objects from said web services interface, wherein in response to said given client request, said coordinator is configured to access said keymap instance to identify one or more locator values corresponding to said key value and, for a particular one of said one or more locator values, to access a corresponding storage node to retrieve a corresponding replica.