69. A computer-accessible memory medium comprising program instructions, wherein the program instructions are configured to implement a searchable data service on a plurality of nodes, wherein the searchable data service is configured to: receive service requests from a plurality of client applications via a web services platform configured to provide a web service interface to the searchable data service, wherein the service requests comprise query requests and storage requests, and wherein the web service interface provides a common message endpoint to the plurality of client applications to send the query requests and storage requests; process received storage requests on the plurality of nodes to store searchable data service objects specified in the storage requests in respective searchable indexes for a plurality of independent data stores used by the client applications, wherein the searchable indexes are on the plurality of nodes, wherein the data stores are on one or more storage devices each on a network and separate from the one or more computer devices that implement the plurality of nodes configured to participate in the searchable data service, wherein each searchable index stores searchable data service objects for a particular one of the plurality of independent data stores such that each searchable index provides a complete index for only one of the independent data stores, wherein each searchable data service object specifies two or more attributes of a particular entity in a particular data store, and wherein the attributes include a unique entity identifier for locating the particular entity in the particular data store; process received query requests on the plurality of nodes, wherein each received query request is processed to locate a set of one or more searchable data service objects from the searchable indexes that satisfy the query request wherein the query request specifies one of the searchable indexes; and return at least the entity identifiers from the set of one or more searchable data service objects that satisfy the query request to the client applications in accordance with the web service interface.
83. The computer-accessible memory medium as recited in claim 69 , wherein the program instructions are configured to implement two or more of the plurality of nodes as storage nodes each configured to: persistently store a partition of a particular searchable index; replicate the partition to another storage node in accordance with an anti-entropy protocol; and communicate subsequent storage requests for the replicated partition to the other storage node in accordance with a gossip protocol to update the replica of the partition on the other storage node.