Google platform
Encyclopedia
Google
requires large computational resources in order to provide their services. This article describes the technological infrastructure
behind Google's websites, as presented in the company's public announcements.
included:
x86 PCs
running customized versions of Linux
. The goal is to purchase CPU generations that offer the best performance per dollar, not absolute performance, how this is measured is unclear but is likely to incorporate running costs of the entire server and CPU power consumption could be significant factor. Servers as of 2009 consisted of a custom made open top server containing two processors (each with an unknown number of cores or interconnected processing units) a considerable amount of RAM spread over 8 DIMM slots housing double height DIMMS and two SATA hard drives connected through a standard ATX sized power supply. According to First April publication by CNET, Each server has a novel 12 volt battery to reduce costs and improve power efficiency
Estimates of the power required for over 450,000 servers range upwards of 20 megawatts, which cost on the order of US$2 million per month in electricity charges. The combined processing power of these servers might reach from 20 to 100 petaflops
.
Specifications:
The exact size and whereabouts of the data centers Google uses are unknown, and official figures remain intentionally vague. A very old estimate (from 2000 while Google was in its infancy and had one product), Google's server farm
consisted of 6,000 processors, 12,000 common IDE disks (2 per machine, and one processor per machine), at four sites: two in Silicon Valley
, California and one in Virginia
. Each site had an OC-48
(2488 Mbit/s) internet connection and an OC-12
(622 Mbit/s) connection to other Google sites. The connections are eventually routed down to 4 × 1 Gbit/s lines connecting up to 64 racks, each rack holding 80 machines and two Ethernet switches.
s resolve www.google.com into multiple IP addresses via Round Robin
policy. Furthermore, this acts as the first level of load balancing
and directs the client to different Google clusters. A Google cluster has thousands of server
s and once the client has connected to the server additional load balancing is done to send the queries to the least loaded web server. This makes Google one of the largest and most complex content delivery network
s.
Racks
are custom-made and contain 40 to 80 servers (20 to 40 1U
servers on either side), while new servers are 2U Rackmount systems. Each rack has a switch. Servers are connected via a 100 Mbit/s Ethernet
link to the local switch. Switches are connected to core gigabit
switch using one or two gigabit uplinks.
; Atlanta, Georgia
; Reston, Virginia
; Lenoir, North Carolina
; and Goose Creek, South Carolina
. In Europe, the largest known centers are in Eemshaven
and Groningen in the Netherlands
and Mons
, Belgium
. Google's Oceania
Data Center is claimed to be located in Sydney
, Australia
.
, on the Columbia River
, approximately 80 miles from Portland
. Codenamed "Project 02", the $600 million complex was built in 2006 and is approximately the size of two football
fields, with cooling towers four stories high. The site was chosen to take advantage of inexpensive hydroelectric power, and to tap into the region's large surplus
of fiber optic cable, a remnant of the dot-com boom. A blueprint of the site has appeared in print.
announced that they had sold the Summa paper mill
in Hamina
, Finland
to Google for 40 million Euros. Google plans to invest 200 million euros on the site to build a data center. For Google the reason to choose this location was the availability of renewable energy close by.
. Google filed a patent application for this technology in 2003.
, Java
, and Python
are favored over other programming languages. For example, the back-end of Gmail is written in Java and the back-end of Google Search is written in C++. Google has acknowledged that Python has played an important role from the beginning, and that it continues to do so as the system grows and evolves.
The software that runs the Google infrastructure includes:
Google has developed several abstractions which it uses for storing most of its data:
, thus reducing the latency time.
To lessen the effects of unavoidable hardware
failure, software is designed to be fault tolerant. Thus, when a system goes down, data is still available on other servers, which increases reliability.
. Such an index allows obtaining a list of documents by a query word. The index is very large due to the number of documents stored in the servers.
The index is partitioned by document IDs into many pieces called shards
. Each shard is replicated
onto multiple servers. Initially, the index was being served from hard disk drives, like it's done in traditional information retrieval
(IR) systems. Google dealt with increasing volume of queries by increasing number of replicas of each shard and thus increasing number of servers. Soon they had found that they had enough servers to keep a copy of the whole index in main memory (although with low replication or no replication at all), and in early 2001 Google switched to an in-memory index system. This switch had "radically changed many design parameters" of their search system, and allowed them to enjoy a big increase in throughput and a big decrease in latency of queries.
In June 2010 Google rolled out a next-generation indexing and serving system called "Caffeine" which can continuously crawl and update search index. Previously, Google updated its search index in batches using a series of MapReduce
jobs. The index was separated into several layers, some of which were updated faster than the others, and the main layer wouldn't be updated for as long as two weeks. With Caffeine the entire index is updated incrementally on a continuous basis. Later Google revealed a distributed data processing system called "Percolator" which is said to be the basis of Caffeine indexing system.
Some details about Google's inverted index compression schemes have been made public.
Google
Google Inc. is an American multinational public corporation invested in Internet search, cloud computing, and advertising technologies. Google hosts and develops a number of Internet-based services and products, and generates profit primarily from advertising through its AdWords program...
requires large computational resources in order to provide their services. This article describes the technological infrastructure
Infrastructure
Infrastructure is basic physical and organizational structures needed for the operation of a society or enterprise, or the services and facilities necessary for an economy to function...
behind Google's websites, as presented in the company's public announcements.
Original hardware
The original hardware (circa 1998) that was used by Google when it was located at Stanford UniversityStanford University
The Leland Stanford Junior University, commonly referred to as Stanford University or Stanford, is a private research university on an campus located near Palo Alto, California. It is situated in the northwestern Santa Clara Valley on the San Francisco Peninsula, approximately northwest of San...
included:
- Sun Ultra II with dual 200 MHzHertzThe hertz is the SI unit of frequency defined as the number of cycles per second of a periodic phenomenon. One of its most common uses is the description of the sine wave, particularly those used in radio and audio applications....
processors, and 256 MBMegabyteThe megabyte is a multiple of the unit byte for digital information storage or transmission with two different values depending on context: bytes generally for computer memory; and one million bytes generally for computer storage. The IEEE Standards Board has decided that "Mega will mean 1 000...
of RAM. This was the main machine for the original Backrub system. - 2 × 300 MHz Dual Pentium IIPentium IIThe Pentium II brand refers to Intel's sixth-generation microarchitecture and x86-compatible microprocessors introduced on May 7, 1997. Containing 7.5 million transistors, the Pentium II featured an improved version of the first P6-generation core of the Pentium Pro, which contained 5.5 million...
Servers donated by Intel, they included 512 MB of RAM and 10 × 9 GBGigabyteThe gigabyte is a multiple of the unit byte for digital information storage. The prefix giga means 109 in the International System of Units , therefore 1 gigabyte is...
hard drives between the two. It was on these that the main search ran. - F50 IBM RS/6000RS/6000RISC System/6000, or RS/6000 for short, is a family of RISC and UNIX based servers, workstations and supercomputers made by IBM in the 1990s. The RS/6000 family replaced the IBM RT computer platform in February 1990 and was the first computer line to see the use of IBM's POWER and PowerPC based...
donated by IBMIBMInternational Business Machines Corporation or IBM is an American multinational technology and consulting corporation headquartered in Armonk, New York, United States. IBM manufactures and sells computer hardware and software, and it offers infrastructure, hosting and consulting services in areas...
, included 4 processors, 512 MB of memory and 8 × 9 GB hard drives. - Two additional boxes included 3 × 9 GB hard drives and 6 x 4 GB hard drives respectively (the original storage for Backrub). These were attached to the Sun Ultra II.
- IBM disk expansion box with another 8 × 9 GB hard drives donated by IBM.
- Homemade disk box which contained 10 × 9 GB SCSISCSISmall Computer System Interface is a set of standards for physically connecting and transferring data between computers and peripheral devices. The SCSI standards define commands, protocols, and electrical and optical interfaces. SCSI is most commonly used for hard disks and tape drives, but it...
hard drives.
Current hardware
Servers are commodity-classCommodity computing
Commodity computing is to use large numbers of already available computing components for parallel computing to get the greatest amount of useful computation at low cost. It is computing done in commodity computers as opposed to high-cost supermicrocomputers or boutique computers...
x86 PCs
Personal computer
A personal computer is any general-purpose computer whose size, capabilities, and original sales price make it useful for individuals, and which is intended to be operated directly by an end-user with no intervening computer operator...
running customized versions of Linux
Linux
Linux is a Unix-like computer operating system assembled under the model of free and open source software development and distribution. The defining component of any Linux system is the Linux kernel, an operating system kernel first released October 5, 1991 by Linus Torvalds...
. The goal is to purchase CPU generations that offer the best performance per dollar, not absolute performance, how this is measured is unclear but is likely to incorporate running costs of the entire server and CPU power consumption could be significant factor. Servers as of 2009 consisted of a custom made open top server containing two processors (each with an unknown number of cores or interconnected processing units) a considerable amount of RAM spread over 8 DIMM slots housing double height DIMMS and two SATA hard drives connected through a standard ATX sized power supply. According to First April publication by CNET, Each server has a novel 12 volt battery to reduce costs and improve power efficiency
Estimates of the power required for over 450,000 servers range upwards of 20 megawatts, which cost on the order of US$2 million per month in electricity charges. The combined processing power of these servers might reach from 20 to 100 petaflops
FLOPS
In computing, FLOPS is a measure of a computer's performance, especially in fields of scientific calculations that make heavy use of floating-point calculations, similar to the older, simpler, instructions per second...
.
Specifications:
- In 2002; upwards of 15,000 servers ranging from 533 MHz Intel CeleronCeleronCeleron is a brand name given by Intel Corp. to a number of different x86 computer microprocessor models targeted at budget personal computers....
to dual 1.4 GHz Intel Pentium IIIPentium IIIThe Pentium III brand refers to Intel's 32-bit x86 desktop and mobile microprocessors based on the sixth-generation P6 microarchitecture introduced on February 26, 1999. The brand's initial processors were very similar to the earlier Pentium II-branded microprocessors...
. - One or more 80 GB hard disks per server (2003)
- 2–4 GB of memory per machine (2004)
- A 2005 estimate by Paul Strassmann has 200,000 servers, while unspecified sources claimed this number to be upwards of 450,000 in 2006.
- ~ 16 GB RAM, 2 TB disk space per machine (2009)
The exact size and whereabouts of the data centers Google uses are unknown, and official figures remain intentionally vague. A very old estimate (from 2000 while Google was in its infancy and had one product), Google's server farm
Server farm
A server farm or server cluster is a collection of computer servers usually maintained by an enterprise to accomplish server needs far beyond the capability of one machine. Server farms often have backup servers, which can take over the function of primary servers in the event of a primary server...
consisted of 6,000 processors, 12,000 common IDE disks (2 per machine, and one processor per machine), at four sites: two in Silicon Valley
Silicon Valley
Silicon Valley is a term which refers to the southern part of the San Francisco Bay Area in Northern California in the United States. The region is home to many of the world's largest technology corporations...
, California and one in Virginia
Virginia
The Commonwealth of Virginia , is a U.S. state on the Atlantic Coast of the Southern United States. Virginia is nicknamed the "Old Dominion" and sometimes the "Mother of Presidents" after the eight U.S. presidents born there...
. Each site had an OC-48
Optical Carrier
Optical Carrier transmission rates are a standardized set of specifications of transmission bandwidth for digital signals that can be carried on Synchronous Optical Networking fiber optic networks...
(2488 Mbit/s) internet connection and an OC-12
Optical Carrier
Optical Carrier transmission rates are a standardized set of specifications of transmission bandwidth for digital signals that can be carried on Synchronous Optical Networking fiber optic networks...
(622 Mbit/s) connection to other Google sites. The connections are eventually routed down to 4 × 1 Gbit/s lines connecting up to 64 racks, each rack holding 80 machines and two Ethernet switches.
Hardware details considered sensitive
In a 2008 book, reporter Randall Stross wrote: "Google's executives have gone to extraordinary lengths to keep the company's hardware hidden from view. The facilities are not open to tours, not even to members of the press." He wrote this based on interviews with staff members and his experience of visiting the company.Network topology
When a client computer attempts to connect to Google, several DNS serverDomain name system
The Domain Name System is a hierarchical distributed naming system for computers, services, or any resource connected to the Internet or a private network. It associates various information with domain names assigned to each of the participating entities...
s resolve www.google.com into multiple IP addresses via Round Robin
Round-robin scheduling
Round-robin is one of the simplest scheduling algorithms for processes in an operating system. As the term is generally used, time slices are assigned to each process in equal portions and in circular order, handling all processes without priority . Round-robin scheduling is simple, easy to...
policy. Furthermore, this acts as the first level of load balancing
Load balancing (computing)
Load balancing is a computer networking methodology to distribute workload across multiple computers or a computer cluster, network links, central processing units, disk drives, or other resources, to achieve optimal resource utilization, maximize throughput, minimize response time, and avoid...
and directs the client to different Google clusters. A Google cluster has thousands of server
Server (computing)
In the context of client-server architecture, a server is a computer program running to serve the requests of other programs, the "clients". Thus, the "server" performs some computational task on behalf of "clients"...
s and once the client has connected to the server additional load balancing is done to send the queries to the least loaded web server. This makes Google one of the largest and most complex content delivery network
Content Delivery Network
A content delivery network or content distribution network is a system of computers containing copies of data placed at various nodes of a network....
s.
Racks
19-inch rack
A 19-inch rack is a standardized frame or enclosure for mounting multiple equipment modules. Each module has a front panel that is wide, including edges or ears that protrude on each side which allow the module to be fastened to the rack frame with screws.-Overview and history:Equipment designed...
are custom-made and contain 40 to 80 servers (20 to 40 1U
Rack unit
A rack unit or U is a unit of measure used to describe the height of equipment intended for mounting in a 19-inch rack or a 23-inch rack...
servers on either side), while new servers are 2U Rackmount systems. Each rack has a switch. Servers are connected via a 100 Mbit/s Ethernet
Ethernet
Ethernet is a family of computer networking technologies for local area networks commercially introduced in 1980. Standardized in IEEE 802.3, Ethernet has largely replaced competing wired LAN technologies....
link to the local switch. Switches are connected to core gigabit
Gigabit
The gigabit is a multiple of the unit bit for digital information or computer storage. The prefix giga is defined in the International System of Units as a multiplier of 109 , and therefore...
switch using one or two gigabit uplinks.
Data centers
Google has numerous data centers scattered around the world. At least 12 significant Google data center installations are located in the United States. The largest known centers are located in The Dalles, OregonThe Dalles, Oregon
The Dalles is the largest city and county seat of Wasco County, Oregon, United States. The name of the city comes from the French word dalle The Dalles is the largest city and county seat of Wasco County, Oregon, United States. The name of the city comes from the French word dalle The Dalles is...
; Atlanta, Georgia
Atlanta, Georgia
Atlanta is the capital and most populous city in the U.S. state of Georgia. According to the 2010 census, Atlanta's population is 420,003. Atlanta is the cultural and economic center of the Atlanta metropolitan area, which is home to 5,268,860 people and is the ninth largest metropolitan area in...
; Reston, Virginia
Reston, Virginia
Reston is a census-designated place in Fairfax County, Virginia, United States, within the Washington, D.C. metropolitan area. The population was 58,404, at the 2010 Census and 56,407 at the 2000 census...
; Lenoir, North Carolina
Lenoir, North Carolina
Lenoir is a city in Caldwell County, North Carolina, United States. The population was 18,228 at the 2010 census. It is the county seat of Caldwell County. Lenoir is located in the Blue Ridge foothills. The city also contains the Brushy Mountains, a spur of the Blue Ridge Mountains...
; and Goose Creek, South Carolina
Goose Creek, South Carolina
Goose Creek is a city in Berkeley county in the U.S. state of South Carolina. The population was 35,938 at the 2010 census. Most of the Naval Weapons Station Charleston is in Goose Creek. As defined by the U.S. Office of Management and Budget, and used by the U.S...
. In Europe, the largest known centers are in Eemshaven
Eemshaven
thumb|right|[[Satellite]] [[image]] of the Ems [[estuary]] showing the location of Eemshaven Eemshaven is a seaport in Groningen, Netherlands....
and Groningen in the Netherlands
Netherlands
The Netherlands is a constituent country of the Kingdom of the Netherlands, located mainly in North-West Europe and with several islands in the Caribbean. Mainland Netherlands borders the North Sea to the north and west, Belgium to the south, and Germany to the east, and shares maritime borders...
and Mons
Mons
Mons is a Walloon city and municipality located in the Belgian province of Hainaut, of which it is the capital. The Mons municipality includes the old communes of Cuesmes, Flénu, Ghlin, Hyon, Nimy, Obourg, Baudour , Jemappes, Ciply, Harmignies, Harveng, Havré, Maisières, Mesvin, Nouvelles,...
, Belgium
Belgium
Belgium , officially the Kingdom of Belgium, is a federal state in Western Europe. It is a founding member of the European Union and hosts the EU's headquarters, and those of several other major international organisations such as NATO.Belgium is also a member of, or affiliated to, many...
. Google's Oceania
Oceania
Oceania is a region centered on the islands of the tropical Pacific Ocean. Conceptions of what constitutes Oceania range from the coral atolls and volcanic islands of the South Pacific to the entire insular region between Asia and the Americas, including Australasia and the Malay Archipelago...
Data Center is claimed to be located in Sydney
Sydney
Sydney is the most populous city in Australia and the state capital of New South Wales. Sydney is located on Australia's south-east coast of the Tasman Sea. As of June 2010, the greater metropolitan area had an approximate population of 4.6 million people...
, Australia
Australia
Australia , officially the Commonwealth of Australia, is a country in the Southern Hemisphere comprising the mainland of the Australian continent, the island of Tasmania, and numerous smaller islands in the Indian and Pacific Oceans. It is the world's sixth-largest country by total area...
.
Project 02
One of the larger Google data centers is located in the town of The Dalles, OregonThe Dalles, Oregon
The Dalles is the largest city and county seat of Wasco County, Oregon, United States. The name of the city comes from the French word dalle The Dalles is the largest city and county seat of Wasco County, Oregon, United States. The name of the city comes from the French word dalle The Dalles is...
, on the Columbia River
Columbia River
The Columbia River is the largest river in the Pacific Northwest region of North America. The river rises in the Rocky Mountains of British Columbia, Canada, flows northwest and then south into the U.S. state of Washington, then turns west to form most of the border between Washington and the state...
, approximately 80 miles from Portland
Portland, Oregon
Portland is a city located in the Pacific Northwest, near the confluence of the Willamette and Columbia rivers in the U.S. state of Oregon. As of the 2010 Census, it had a population of 583,776, making it the 29th most populous city in the United States...
. Codenamed "Project 02", the $600 million complex was built in 2006 and is approximately the size of two football
American football
American football is a sport played between two teams of eleven with the objective of scoring points by advancing the ball into the opposing team's end zone. Known in the United States simply as football, it may also be referred to informally as gridiron football. The ball can be advanced by...
fields, with cooling towers four stories high. The site was chosen to take advantage of inexpensive hydroelectric power, and to tap into the region's large surplus
Dark fiber
A dark fiber or unlit fiber is an unused Optical fiber, available for use in fiber-optic communication.The term dark fiber was originally used when referring to the potential network capacity of telecommunication infrastructure, but now also refers to the increasingly common practice of leasing...
of fiber optic cable, a remnant of the dot-com boom. A blueprint of the site has appeared in print.
Summa papermill
In February 2009, Stora EnsoStora Enso
Stora Enso Oyj is a Finnish pulp and paper manufacturer, formed by the merger of Swedish mining and forestry products company Stora and Finnish forestry products company Enso-Gutzeit Oy in 1998. It is headquartered in Helsinki, and it has approximately 29,000 employees...
announced that they had sold the Summa paper mill
Paper mill
A paper mill is a factory devoted to making paper from vegetable fibres such as wood pulp, old rags and other ingredients using a Fourdrinier machine or other type of paper machine.- History :...
in Hamina
Hamina
Hamina is a town and a municipality of Finland. It is located in the province of Southern Finland and is part of the Kymenlaakso region. The town has a population of and covers an area of ofwhich is water. The population density is...
, Finland
Finland
Finland , officially the Republic of Finland, is a Nordic country situated in the Fennoscandian region of Northern Europe. It is bordered by Sweden in the west, Norway in the north and Russia in the east, while Estonia lies to its south across the Gulf of Finland.Around 5.4 million people reside...
to Google for 40 million Euros. Google plans to invest 200 million euros on the site to build a data center. For Google the reason to choose this location was the availability of renewable energy close by.
Modular Container Data Centers
Since 2005, Google has been moving to a containerized modular data centerGoogle Modular Data center
The Google Modular Data Center is a set of data center containers used by Google as its servers. They were revealed on April 1, 2009, during the first Google Data Center Efficiency Summit in Mountain View, California. The data centers are rumored to cost $600 million USD each, and use from 50 to...
. Google filed a patent application for this technology in 2003.
Software
Most of the software stack that Google uses on their servers was developed in-house. It is believed that C++C++
C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell...
, Java
Java (programming language)
Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities...
, and Python
Python (programming language)
Python is a general-purpose, high-level programming language whose design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...
are favored over other programming languages. For example, the back-end of Gmail is written in Java and the back-end of Google Search is written in C++. Google has acknowledged that Python has played an important role from the beginning, and that it continues to do so as the system grows and evolves.
The software that runs the Google infrastructure includes:
- Google Web Server — Custom Linux-based Web server that Google uses for its online services; according to Google, this is not based on ApacheApache HTTP ServerThe Apache HTTP Server, commonly referred to as Apache , is web server software notable for playing a key role in the initial growth of the World Wide Web. In 2009 it became the first web server software to surpass the 100 million website milestone...
. - Storage systems:
- Google File SystemGoogle File SystemGoogle File System is a proprietary distributed file system developed by Google Inc. for its own use. It is designed to provide efficient, reliable access to data using large clusters of commodity hardware...
and its successor, Colossus - BigTableBigTableBigTable is a compressed, high performance, and proprietary database system built on Google File System , Chubby Lock Service, SSTable and a few other Google technologies; it is currently not distributed nor is it used outside of Google, although Google offers access to it as part of their Google...
— structured storage built upon GFS/Colossus - Spanner — planet-scale structured storage system, next generation of BigTable stack
- Google File System
- Chubby lock service
- Borg — job scheduling and monitoring system
- MapReduceMapReduceMapReduce is a software framework introduced by Google in 2004 to support distributed computing on large data sets on clusters of computers. Parts of the framework are patented in some countries....
and Sawzall programming languageSawzall (programming language)Sawzall is a procedural domain-specific programming language, used by Google to process large numbers of individual log records. Sawzall was first described in 2003, and the szl runtime was open-sourced in August 2010... - Indexing/search systems:
- TeraGoogle — Google's large search index (launched in early 2006), designed by Anna Paterson of CuilCuilCuil was a search engine that organized web pages by content and displayed relatively long entries along with thumbnail pictures for many results. Cuil said it had a larger index than any other search engine, with about 120 billion web pages. It went live on July 28, 2008...
fame. - Caffeine (Percolator) — continuous indexing system (launched in 2010).
- TeraGoogle — Google's large search index (launched in early 2006), designed by Anna Paterson of Cuil
Google has developed several abstractions which it uses for storing most of its data:
- Protocol buffersProtocol BuffersProtocol Buffers are a serialization format with an interface description language developed by Google. The original Google implementation for C++, Java and Python is available under a free software, open source license....
— "Google's lingua franca for data", a binary serialization format which is widely used within the company. - SSTableSSTableSSTable is an on-disk file format that represents a string-to-string mapping. It is an immutable system so that once written, the map remains unchanged....
(Sorted Strings Table) — a persistent, ordered, immutable map from keys to values, where both keys and values are arbitrary byte strings. It is also used as one of the building blocks of BigTable. - RecordIO — a sequence of variable sized records.
Software development practices
Most operations are read-only. When an update is required, queries are redirected to other servers, so as to simplify consistency issues. Queries are divided into sub-queries, where those sub-queries may be sent to different ducts in parallelParallel computing
Parallel computing is a form of computation in which many calculations are carried out simultaneously, operating on the principle that large problems can often be divided into smaller ones, which are then solved concurrently . There are several different forms of parallel computing: bit-level,...
, thus reducing the latency time.
To lessen the effects of unavoidable hardware
Computer hardware
Personal computer hardware are component devices which are typically installed into or peripheral to a computer case to create a personal computer upon which system software is installed including a firmware interface such as a BIOS and an operating system which supports application software that...
failure, software is designed to be fault tolerant. Thus, when a system goes down, data is still available on other servers, which increases reliability.
Index
Like most search engines, Google indexes documents by building a data structure known as inverted indexInverted index
In computer science, an inverted index is an index data structure storing a mapping from content, such as words or numbers, to its locations in a database file, or in a document or a set of documents...
. Such an index allows obtaining a list of documents by a query word. The index is very large due to the number of documents stored in the servers.
The index is partitioned by document IDs into many pieces called shards
Shard (database architecture)
A database shard is a horizontal partition in a database or search engine. Each individual partition is referred to as a shard or database shard.- Database architecture :...
. Each shard is replicated
Replication (computer science)
Replication is the process of sharing information so as to ensure consistency between redundant resources, such as software or hardware components, to improve reliability, fault-tolerance, or accessibility. It could be data replication if the same data is stored on multiple storage devices, or...
onto multiple servers. Initially, the index was being served from hard disk drives, like it's done in traditional information retrieval
Information retrieval
Information retrieval is the area of study concerned with searching for documents, for information within documents, and for metadata about documents, as well as that of searching structured storage, relational databases, and the World Wide Web...
(IR) systems. Google dealt with increasing volume of queries by increasing number of replicas of each shard and thus increasing number of servers. Soon they had found that they had enough servers to keep a copy of the whole index in main memory (although with low replication or no replication at all), and in early 2001 Google switched to an in-memory index system. This switch had "radically changed many design parameters" of their search system, and allowed them to enjoy a big increase in throughput and a big decrease in latency of queries.
In June 2010 Google rolled out a next-generation indexing and serving system called "Caffeine" which can continuously crawl and update search index. Previously, Google updated its search index in batches using a series of MapReduce
MapReduce
MapReduce is a software framework introduced by Google in 2004 to support distributed computing on large data sets on clusters of computers. Parts of the framework are patented in some countries....
jobs. The index was separated into several layers, some of which were updated faster than the others, and the main layer wouldn't be updated for as long as two weeks. With Caffeine the entire index is updated incrementally on a continuous basis. Later Google revealed a distributed data processing system called "Percolator" which is said to be the basis of Caffeine indexing system.
Some details about Google's inverted index compression schemes have been made public.
Server types
Google's server infrastructure is divided in several types, each assigned to a different purpose:- Google web servers coordinate the execution of queries sent by users, then format the result into an HTMLHTMLHyperText Markup Language is the predominant markup language for web pages. HTML elements are the basic building-blocks of webpages....
page. The execution consists of sending queries to index servers, merging the results, computing their rank, retrieving a summary for each hit (using the document server), asking for suggestions from the spelling servers, and finally getting a list of advertisements from the ad server. - Data-gathering servers are permanently dedicated to spideringWeb crawlerA Web crawler is a computer program that browses the World Wide Web in a methodical, automated manner or in an orderly fashion. Other terms for Web crawlers are ants, automatic indexers, bots, Web spiders, Web robots, or—especially in the FOAF community—Web scutters.This process is called Web...
the Web. Google's web crawler is known as GoogleBot. They update the index and document databases and apply Google's algorithms to assign ranks to pages. - Each index server contains a set of index shards. They return a list of document IDs ("docid"), such that documents corresponding to a certain docid contain the query word. These servers need less disk space, but suffer the greatest CPU workload.
- Document servers store documents. Each document is stored on dozens of document servers. When performing a search, a document server returns a summary for the document based on query words. They can also fetch the complete document when asked. These servers need more disk space.
- Ad servers manage advertisements offered by services like AdWordsAdWordsGoogle AdWords is Google's main advertising product and main source of revenue. Google's total advertising revenues were USD$28 billion in 2010. AdWords offers pay-per-click advertising, cost-per-thousand advertising, and site-targeted advertising for text, banner, and rich-media ads. The AdWords...
and AdSenseAdSenseGoogle AdSense which is a program run by Google Inc. allows publishers in the Google Network of content sites to automatically serve text, image, video, and rich media adverts that are targeted to site content and audience. These adverts are administered, sorted, and maintained by Google, and they...
. - SpellingSpellingSpelling is the writing of one or more words with letters and diacritics. In addition, the term often, but not always, means an accepted standard spelling or the process of naming the letters...
servers make suggestions about the spelling of queries.
Further reading
- Shankland, Stephen, CNET news "Google uncloaks once-secret server." April 1, 2009.
External links
- Google Research Publications
- Web Search for a Planet: The Google Cluster Architecture (Luiz André Barroso, Jeffrey Dean, Urs Hölzle)
- Underneath the Covers at Google: Current Systems and Future Directions (Talk given by Jeff Dean at Google I/O conference in May 2008)