How can a search engine answer billions of queries in a blink?

A search engine answers billions of queries by never asking one machine to do it alone. Its index is cut into pieces called shards, each shard is copied onto several servers, and every question is sent to many machines at once before their answers are merged. The engine is part of a distributed computing system that can span many data centers around the world.

The growth has been dizzying. In early 1994 the World Wide Web Worm, an early search engine, got about 1,500 queries a day. By November 1997 AltaVista claimed roughly 20 million a day. By 2012 Google was handling more than 3.5 billion searches per day, from an index of over 30 trillion pages.

A 2003 report showed how Google kept up. At peak it served about 1,000 queries a second, and instead of expensive supercomputers it used a cluster of some 15,000 ordinary PCs, with software written to cope with the ones that failed. Its index was split by document into shards, and each shard was copied onto several servers; as traffic grew, Google added more copies so that more machines could answer at once. A web server sends each query out to the index servers, merges and ranks what comes back, then adds page summaries, spelling suggestions and ads.

Speed sometimes means settling for less. Google's 1998 prototype stopped searching once it had found 40,000 matching documents, to put a limit on response time, even though that might return sub-optimal results. Disks were the other enemy: a disk seek took about 10 milliseconds, and in early 2001 Google moved its whole index into memory, cutting waiting times sharply. All of this costs energy: in 2009 Google claimed a single search used about 1 kilojoule, enough to warm a litre of water by about a quarter of a degree.