Lecture Notes - Evolution of Google Search Engine
Jeff Dean gave a keynote Building Large Scale Information Retrieval Systems at WSDM 2009. It's actually a presentation on how Google search engine evolves during the past 10 years. Here are my notes for this lecture.
Part I - Overview of Search Engine Evolution: 1999 VS 2009
Factors to Consider when Designing a Information Retrieval System:
1. Corpus Size(# docs to be indexed)
2. QPS(Query Per Second)
3. Freshness/Update Rate
4. Query Latency
5. Complexity/Cost of Scoring/Retrieval Algorithm
Parameter Change 1999 -> 2009:
1. Corpus Size: 70M -> *B ~100X
2. QPS: ~1000X
3. Refresh: Months -> Minutes ~10000X
4. Latency: <1s> <02.s style="font-weight: bold; font-style: italic;">~5X
5. Machine Scale: ~1000X
Consider 10x Growth when designing, Rewrite for 100x Growth!
Part II - Evolution of Google Search Engine
~1997 - Circa, Research Prototype
- Simple Architecture and Focus on System Distributing/Partitioning
- Term vs Doc based Partition: Doc based Win
- Disk Based Index, DocID+Posting List with Position Attributes, Byte Aligned Encoding
~1999 - Circa, Production
- Introduced Cache
-- hit rate is low 30~60% due to index refresh and long tail query
-- very beneficial, reduce large disk i/o
-- hot term first priority to cache, hot and costy request
- Replica Index Data
-- better performance
-- better availability
Some Summary in late 1990's:
Crawler is simple batch system
- start with very few urls
- queue it when found new urls
- stop when have enough docs
Index Serving using cheap machine
- no failure handling
- added record/chunk checksum
Index Update
- once/month
- wait traffic to low -> take replica offline -> do update -> start serving
~2000 - Dealing with Growth
Situation:
- doc size:50m -> 1000m
- ~20% query traffic increase/month
- Yahoo! deal
Solution:
add machines constantly
- more index shards for larger index size
- more index replica for bigger query capacity
And improve software constantly
- better disk scheduling
- better index encoding
~2001 - Adding In-Memory Index
- enough machine memory: holding all index in mem
- machine function: replica -> micro shard holding
- balancer: cordinator
- availability: replicate important docs
~2004 - Adding Infrastructure
- Generalize tree structured query flow
- Generalize balancer concept
- New index encoding: group varint encoding
- GFS appear in production
~2007 - Universal Search
- Universal search: combine results from multiple vertical corpus
- Realtime search: fast url finding -> crawling -> indexing -> serving cycle
-
Experiment supporting: have idea -> try it on real data offline and
tune -> live experiment on small piece -> roll out and launch
Part III - Future Trends
- Cross Language Information Retrieval
- ACL in large IR system with huge amount of user and dynamic requirement
-
Automatic Construction of Efficient IR system (one bin for realtime and
regular web index with different parameter configuration)
- Info extraction from semi-structured data
[Reference]
1. Challenges in Building Large Scale Information Retrieval Systems[PDF, Video]
2. Notes by Another Blogger - https://www.searchenginecaffe.com/2009/02/jeffrey-dean-wsdm-keynote-building.html