73. The computer-accessible memory medium as recited in claim 69 , wherein the program instructions are configured to implement the searchable data service on the plurality of nodes as: one or more storage nodes configured to persistently store the searchable indexes; one or more query nodes each configured to maintain a local query cache of responses to previous query requests; and one or more coordinator nodes each configured to: receive service requests from the web services platform; forward each storage request to one or more of the storage nodes; and forward each query request to one or more of the query nodes.
77. The computer-accessible memory medium as recited in claim 73 , wherein each of the query nodes is configured to: receive a query request from a coordinator node; access the local query cache on the query node to determine if the query request can be satisfied from the local query cache; if the query request can be satisfied from the local query cache, return at least the entity identifiers from a set of one or more searchable data service objects from the local query cache that satisfy the query request to a client application that initiated the query request in accordance with the web service interface; if the query request cannot be satisfied from the local query cache, forward the query request to one or more of the storage nodes.