Looking For Higher Rankings in Google Organic? Get Back To The BasicsAddress Core Algorithm Principles and Drive Natural Keyword Rankings Google Architecture OverviewHere's a high level overview of the Google spidering and algorithm ranking system and how it works ... and it involves so much more than links.
Most of Google is implemented in C or C++ for efficiency and can run in either Solaris or Linux. In Google, the web crawling (downloading of web pages) is done by several distributed
crawlers or bot agents known as Googlebot spiders.
There is a
URLserver that sends lists of URLs to be
fetched to the crawlers. Web pages fetched by googlebots are then sent to Google's
storeserver. The storeserver then compresses and stores the web pages into a repository. Every web page has an associated ID number called a
docID which is assigned whenever a new URL is parsed out of a web page.
The indexing function is performed by the
indexer and the sorter. The indexer performs a number of functions. It reads the repository, uncompresses the documents, and parses them. Each document is converted into a set of
word occurrences called hits. The hits record the word, position in document, an approximation of font size, and capitalization.
The indexer distributes these hits into a set of "barrels", creating a partially sorted forward index. The indexer performs another important function. It parses out all the links in every web page and stores important information about them in an anchors file. This file contains enough information to determine where each link points from and to, and the text of the link.
The URLresolver reads the anchors file and converts relative URLs into absolute URLs and in turn into docIDs. It puts the anchor text into the forward index, associated with the docID that the anchor points to. It also generates a database of links which are pairs of docIDs. The links database is used to compute PageRanks for all the documents.
The sorter takes the barrels, which are sorted by docID and resorts them by wordID to generate the inverted index. This is done in place so that little temporary space is needed for this operation. The sorter also produces a list of wordIDs and offsets into the inverted index. A program called
DumpLexicon takes this list together with the lexicon produced by the indexer and generates a new lexicon to be used by the searcher.
The searcher is run by a web server and uses the lexicon built by DumpLexicon together with the inverted index and the PageRanks to answer queries. Major Data StructuresGoogle's data structures are optimized so that a large document collection can be crawled, indexed, and searched with little cost. Although, CPUs,
private student loans, and bulk input output rates have improved dramatically over the years, a disk seek still requires about 10 ms to complete. Google is designed to avoid disk seeks whenever possible, and this has had a considerable influence on the design of the data structures.
BigFilesBigFiles are virtual files spanning multiple file systems and are addressable by 64 bit integers. The allocation among multiple file systems is handled automatically.
The BigFiles package also handles allocation and deallocation of file descriptors, since the operating systems do not provide enough for our needs. BigFiles also support rudimentary compression options.
Repository Repository Data Structure The repository contains the full HTML of every web page.
Each page is compressed using zlib. The choice of compression technique is a tradeoff between speed and compression ratio. We chose zlib's speed over a significant improvement in compression offered by bzip. The compression rate of bzip was approximately 4 to 1 on the repository as compared to zlib's 3 to 1 compression. In the repository, the documents are stored one after the other and are prefixed by docID, length, and URL as can be seen. The repository requires no other data structures to be used in order to access it. This helps with data consistency and makes development much easier; Google rebuilds all the other data structures from only the repository and a file which lists crawler errors.
Document IndexThe document index keeps information about each document. It is a fixed width ISAM (Index Sequential Access Mode) index, ordered by docID.
The information stored in each entry includes the current document status, a pointer into the repository, a document checksum, and various statistics including doc scores. If the document has been crawled, it also contains a pointer into a variable width file called docinfo which contains its URL and title. Otherwise the pointer points into the URLlist which contains just the URL. This design decision was driven by the desire to have a reasonably
compact data structure, and the ability to fetch a record in one disk seek during a search. Additionally, there is a file which is used to convert URLs into docIDs. It is a list of URL checksums with their corresponding docIDs and is sorted by checksum. In order to find the docID of a particular URL, the URL's checksum is computed and a
binary search is performed on the checksums file to find its docID. URLs may be converted into docIDs in batch by doing a merge with this file. This is the technique the URLresolver uses to turn URLs into docIDs. This batch mode of update is crucial because otherwise Google must perform one seek for every link which assuming one disk would take more than a 7 weeks to cover the Google link dataset.
LexiconThe lexicon has several different forms. The current implementation keeps the lexicon in memory on a machine with 256 MB of main memory. The current lexicon contains 14 million words (though some rare words were not added to the lexicon). It is implemented in two parts -- a list of the words (concatenated together but separated by nulls) and a hash table of pointers. For various functions, the list of words has some auxiliary information.
Hit ListsA hit list corresponds to a list of occurrences of a particular word in a particular document including position, font, and capitalization information. Hit lists account for most of the space used in both the forward and the inverted indices. Because of this, it is important to represent them as efficiently as possible. We considered several alternatives for encoding position, font, and capitalization -- simple encoding (a triple of integers), a compact encoding (a hand optimized allocation of bits), and Huffman coding. In the end we chose a hand optimized compact encoding since it required far less space than the simple encoding and far less bit manipulation than Huffman coding. Google's compact encoding uses two bytes for every hit. There are two types of hits: fancy hits and plain hits. Fancy hits include hits occurring in a URL, title, anchor text, or meta tag. Plain hits include everything else. A plain hit consists of a capitalization bit, font size, and 12 bits of word position in a document. Font size is represented relative to the rest of the document using three bits with 7 values as 111 is the flag that signals a fancy hit. A fancy hit consists of a capitalization bit, the font size set to 7 to indicate it is a fancy hit, 4 bits to encode the type of fancy hit, and 8 bits of position. For anchor hits, the 8 bits of position are split into 4 bits for position in anchor and 4 bits for a hash of the docID the anchor occurs in. This helps Google with limited phrase searching. Google uses font size relative to the rest of the document because when searching, you do not want to rank otherwise identical documents differently just because one of the documents is in a larger font.
Looking to Secure and Maintain Premium Keyword Rankings in Google?
Get Back to the Basics.
Address The Principles of the Algorithms.
At Google and Peak Positions Its All About Code!
Discover Algorithm Synchronization > an exclusive Peak Positions Technology.
