Distributing Google

We consider the problem of wide-area large-scale text search over a peer-to-peer infrastructure. A wide-area search infrastructure with billions of documents and millions of search terms presents unique challenges in terms of the amount of state that must be maintained and updated. Distributing such a system would require tens of thousands of hosts leading to the usual problems associated with node failures, churn and data migration. Localities inherent in query patterns will cause load imbalances and hot spots that can severely impair performance. In this paper, we describe an architecture for constructing a scalable search infrastructure that is designed to cope with the challenges of scale described above. Our architecture consists of a data store layer which is used to reliably store and recompute indexes over a slow timescale and a caching layer that is used to respond to most queries. Our primary insight is that the problem of efficiently retrieving a small number of relevant results must be decoupled from the problem of reliably storing potentially huge indexes. Relevant results can be quickly retrieved from caches of ranked results, which can be replicated based upon query load. An entirely different set of mechanisms, such as encoded storage and/or data partitioning, should be used to store large indexes reliably. These indexes should only be used to compute results when there is a miss in the cache.