Hardware Evolution:
Google’s computing hardware has significantly improved over the last decade. Upgrades have resulted in a 1,000x improvement in computational power.

Web Search and Retrieval System Evolution:
Significant revisions to Google’s core web search and retrieval systems have been made over the years. Improvements include increased indexing, query handling, and update latency. User experience enhancements include faster response times and larger, more relevant indices.

Infrastructure Software Development:
Google has developed influential infrastructure software, including Big Table, MapReduce, and Protocol Buffers. These tools underlie many Google products and services.

Techniques for Building High-Performance and Reliable Systems:
Google has developed techniques for building high-performance and reliable systems. These techniques have emerged from the process of building various systems and represent general patterns useful across different systems.

Early Google Search System:
Google’s early search system was based on research conducted by Larry Page and Sergey Brin. The system utilized the link structure of the web for ranking experiments. The index was divided into partitions, and index servers computed results for their respective document subsets. Doc servers generated titles and snippets for the resulting documents.

Google’s Commodity Hardware Approach:
Google opted to build its own hardware using commodity components. This approach allowed for cost savings and customization. Early designs, such as the “corkboard” system, had lessons learned, such as avoiding shared power supplies and using insulation to protect components.

Google’s Search System in 1999:
Google’s search system in 1999 resembled the original research project but had grown in scale. An advertising system was also developed and integrated into the search system.

Adding Search Capacity:
To increase search capacity, the index data is replicated, and requests are sent to one replica for each shard.

Caching:
Caching in web search improves performance by storing the results of index results and doc requests in memory. Hit rates vary depending on factors like cache flushing frequency, query traffic mix, personalization, and query type. Caching reduces the load on back-end systems and improves query latency.

Indexing System:
In 1998-1999, Google used a simple batch indexing system without checkpointing. The system attempted to process large amounts of raw documents on disk, sort them, and create an index.

Sharding and Index Partitioning:
Google used sharding to partition the index into smaller, more manageable pieces called “index shards.” As the index grew, they needed to keep partitioning it more finely to maintain reasonable response times. This resulted in a large number of index shards, each with its own replica for fault tolerance.

Performance Challenges:
The sharding approach led to performance challenges, as every index shard required a separate disk seek for each term in a query. Disk seeks were a performance bottleneck, especially for large indexes.

Adversarial Memory and Data Corruption:
In the early days, Google’s machines lacked error-correcting memory, making data corruption a common issue. A colleague likened this situation to “programming with adversarial memory.” Google developed a file abstraction with checksums and resynchronization patterns to handle data corruption.

Data Center Design:
Google designed its own data centers with dense computational power per rack. They prioritized packing as many machines as possible into a given space to maximize efficiency. This approach allowed them to move quickly between data centers when service providers went bankrupt.

Index Growth and Traffic Increases:
Google’s index size grew by a factor of 20 between 1999 and 2001, and traffic increased by 15-20% per month. To handle this growth, they deployed more machines and made software improvements to increase index serving performance. A deal with Yahoo in 2000 doubled Google’s traffic overnight, further driving the need for scalability.

Software Improvements and Index Rollouts:
Google continuously rolled out new index versions with software improvements to enhance performance. This involved deploying new index shards and server software that delivered higher throughput. The goal was to increase index size to improve search quality while maintaining acceptable response times.

Disk I/O Limitations:
Disk-based indexing systems face challenges in fully utilizing disk bandwidth and minimizing seek times. Additional tricks like auxiliary data structures and index compression help optimize disk-based indexing, but face scalability issues.

In-Memory Indexing:
To address disk I/O limitations, Google implemented a completely in-memory index system in 2001. In-memory indexing significantly improves throughput and reduces query latency compared to disk-based systems, especially for expensive queries.

Distributed Architecture:
The in-memory indexing system employs a distributed architecture with balancers. Front-end web servers communicate with balancers, which in turn communicate with machines in each shard. Balancers aggregate results from machines within a shard and send them back to the web server.

Benefits of In-Memory Indexing:
In-memory indexing offers several advantages: Increased throughput due to the elimination of disk seeks. Reduced query latency, particularly for expensive queries. Improved scalability and reliability.

Continued Use of Cache and Doc Servers:
Cache and doc servers continue to play a role in the in-memory indexing system, functioning in a similar manner as in the disk-based indexing system.

Challenges of In-Memory Index Systems:
In-memory index systems can face challenges due to variance caused by randomized cron jobs. Randomized cron jobs can lead to uneven resource usage across machines, causing performance issues. Fixing cron jobs at regular intervals, such as every five minutes, can result in better performance, as all machines would experience a slight hiccup simultaneously, affecting a smaller number of queries.

Issues with the “Circle of Life” Query:
The query “circle of life” was computationally expensive due to the commonality of the individual words and their rarity as a phrase on the web. The query resulted in excessive I/O operations (30 gigabytes) as the system searched for documents containing the three words in sequence. The member system’s speed is attributed to its low seek cost, allowing for quick movement within the posting list in memory.

Variance in In-Memory Index Systems:
In-memory index systems can experience variance as the query touches thousands of machines instead of dozens, unlike the member system. Randomized cron jobs, intended to distribute housekeeping tasks across machines, can negatively impact performance in in-memory index systems. Randomization leads to uneven resource usage, with at least one machine experiencing increased activity at any given time, resulting in reduced CPU or network bandwidth.

Availability and Queries of Death:
Single replica design in modern search engines raises concerns about availability. Important documents are replicated across multiple machines to prevent loss. Queries of death cause unexpected crashes due to software bugs or unexpected query inputs.

Canary Requests:
Canary requests are sent to a single machine before broadcasting to multiple machines. If the canary request fails, it indicates a query of death, and the request is rejected. This approach minimizes server crashes and helps identify problematic queries.

Index Server and Doc Server Unification:
In 2004, Google unified index servers and doc servers into a multi-level tree query distribution system. Leaf servers handle both index and document requests, providing improved scalability.

Repository Manager and Shard-Based Index:
A repository manager oversees the index, consisting of numerous shards. New shards are gradually added, eliminating the need for monolithic index switches. Cache servers store partial results, reducing the load on the index servers.

New Format:
Google redesigned its search index format to improve performance and facilitate experimentation.

Single Flat Position Space:
The new format uses a single flat position space instead of the old two-level document identifier followed by word position.

Compactness and Speed:
The new format needed to be compact, so a byte-aligned variable length integer encoding was chosen.

Variable Length Integer Encoding:
Variable length integer encoding uses seven bits out of every byte to encode seven bits of a value, with a continuation bit indicating if another byte follows.

Optimized Encoding:
To improve decoding speed, a 3-bit prefix is used to indicate the number of bytes in the full encoding, allowing for faster decoding with fewer branches and less shifting.

Encoding Streams of Numbers:
The index format efficiently encodes streams of numbers using a combination of delta encoding and variable length integer encoding.

Encoding Formats:
Encodes groups of four numbers into a single byte prefix, followed by the numbers themselves. Prefix contains length information for each number. Decoding is fast, utilizing a lookup table and parallel processing. Alternative encoding formats exist, offering trade-offs between speed and memory usage.

Universal Search:
Introduced in 2007 to search all available corpora (e.g., web documents, books, news) simultaneously. Performance challenges due to increased traffic and varying ranking functions. Relevance determination based on query results, rather than solely relying on query analysis. Interleaving and separate sections used to organize results from different corpora.

Infrastructure Evolution:
Commodity hardware with rack-level switches. Common failures include individual machine or disk drive failures, switch problems, and long-distance link outages. Software-based reliability and availability due to frequent hardware failures.

Requirements for Large-Scale Computing:
Persistent data storage with high availability, not relying on single machines or racks. High read and write bandwidth to stored data. Ability to run large-scale computations reliably without individual machine failures.

Google File System (GFS):
Developed in 2003, optimized for large files (hundreds of MB to GB). Master manages file system metadata and data distribution. Data spread across chunk servers, replicated for fault tolerance. Clients read data directly from chunk servers.

Cluster Characteristics:
Clusters consist of 5,000 to 20,000 machines with homogeneous hardware configurations. Each machine runs a chunk server process, and a GFS master exists within the cluster. Scheduling system coordinates tasks and manages machine failures. Distributed lock service facilitates communication and configuration sharing among processes. User-level jobs, such as index servers and batch production jobs, run on top of this infrastructure.

Introduction:
MapReduce is a programming model for large-scale data processing designed to handle massive datasets. It allows users to express computations as a series of map and reduce functions, simplifying parallel processing.

Benefits of MapReduce:
Parallelization: MapReduce enables parallelization of computations across multiple machines, significantly reducing computation time. Fault Tolerance: The framework handles machine failures and recovers lost work automatically. Scalability: MapReduce is highly scalable, allowing users to process vast amounts of data efficiently.

MapReduce Programming Model:
Map Function: Extracts relevant information from the input data and generates intermediate key-value pairs. Shuffle and Sort: The framework shuffles and sorts intermediate data by key, grouping similar keys together. Reduce Function: Combines and aggregates intermediate data associated with each key to produce the final output.

Example:
Generating map tiles from geographic features: Map Function: Determines which map tiles each feature intersects with and emits feature data to those tiles. Shuffle and Sort: Clusters intermediate data by tile key. Reduce Function: Renders the features for each tile into a JPEG image.

Implementation Details:
Master-Worker Architecture: Master: Coordinates the computation, assigns tasks to workers, and handles fault tolerance. Workers: Execute map and reduce tasks, generating and processing intermediate data. Data Locality: Workers process data stored on local disks, minimizing network traffic. Network Shuffling: Intermediate data is transferred across the network to group similar keys together.

Fault Tolerance:
MapReduce automatically re-executes failed tasks on different machines, ensuring data integrity. Fine-grained Tasks: Breaking computations into small tasks enables faster recovery and dynamic load balancing.

Conclusion:
MapReduce simplifies large-scale data processing by providing a structured programming model. It offers benefits such as parallelization, fault tolerance, and scalability. The underlying implementation handles complex details, allowing users to focus on their computations.

MapReduce Backup Tasks:
MapReduce can create backup copies of slow tasks near the end of the map or reduce phase, allowing the job to complete faster. Multiple copies of a map task are run, with the first to finish winning.

MapReduce Locality Optimization:
MapReduce attempts to schedule map tasks to be local to the machine or at least on the same rack as the input file blocks. This optimization reduces the amount of data transferred over the network.

MapReduce Usage Statistics:
MapReduce processes about an exabyte of data per month and runs 4 million jobs per month.

Spanner:
Spanner is a system designed to run as a single instance across multiple data centers. It provides a single global namespace for data, making it easier to manage data across data centers. Spanner supports a mix of strong and weakly consistent operations across data centers.

Spanner Architecture:
Spanner zones are semi-autonomous, allowing for continued functioning and load balancing within a zone even during network partitions. After network disruptions, Spanner aims to recover a consistent view of the data. Users specify high-level data storage preferences, such as the desired number of data copies and regional distribution, rather than specific data center locations.

Design Principles for Distributed Systems:
Breaking large software systems into separate subsystems enables independent development and deployment by small teams. Clear interfaces between subsystems facilitate collaboration and reduce dependencies between teams. Distributed services provide natural interface points for modular development and scalability. Engineering offices worldwide can contribute to system development by owning and managing specific services.

Choosing the Best Solution:
Consider both qualitative (ease of understanding, interface cleanliness) and quantitative (performance) aspects when evaluating design alternatives. Use back-of-the-envelope calculations to estimate system performance without building and measuring multiple versions.

Important Numbers to Know:
Data centers are far apart, resulting in significant network latencies. Memory is much faster than disks, emphasizing the need for efficient data access strategies. Simple compression algorithms can significantly reduce network bandwidth usage. Disk seeks should be avoided whenever possible.

Optimizing System Design:
Use back-of-the-envelope calculations to compare design alternatives and identify performance bottlenecks. Consider caching strategies and pre-computation to improve system responsiveness. Understand the performance characteristics of underlying systems to make informed design decisions.

Listening to User Feedback:
When gathering user requirements, focus on commonalities and identify the most frequently requested features. Prioritize the development of features that benefit the majority of users. Consider accommodating additional popular features if resources allow.

Avoid Complexity Overload:
Adding too many features can lead to a complex system that compromises other clients. Listen to user needs and translate them into features that address their underlying problems. Avoid building infrastructure just for the sake of it; it should address real needs. Don’t over-engineer for hypothetical uses; focus on likely potential uses.

Use Your Own Infrastructure:
Iterating on your infrastructure while building on top of it enables quick feedback and adaptation. Get rapid feedback from users of your infrastructure.

Design for Growth:
Anticipate which parameters of your system will grow and by how much. Consider the scalability limitations of different designs. A completely distributed state may not be necessary; a centralized component can simplify reasoning and provide oversight. Keep the centralized component from becoming a scalability bottleneck.

Wide Fan-In Tree:
Introduce a tree structure to avoid network and CPU bottlenecks when sending requests to many machines. The parent node is responsible for sending requests to a subset of leaves and filtering responses. Co-locate responsibility so that a parent node talks to leaves on the same rack, optimizing network usage.

Backup Requests for Latency Minimization:
Spawn backup requests near the end of computation to take the first one that finishes, reducing latency. Useful in query serving systems with multiple replicas.

Multiple Smaller Units of Work per Machine:
Minimize recovery time and enable load balancing by assigning multiple smaller units of work to each machine. If a machine crashes, other machines can quickly pick up the work chunks. Provides flexibility for load balancing by adjusting the number of work chunks.

Elastic Systems:
Design systems to adapt to varying loads, including unexpected overloads. Automatically scale capacity based on traffic patterns. Implement strategies to handle overload, such as reducing search depth, dropping non-essential features, and employing more aggressive load balancing.

Opportunities in the Current Era:
The convergence of computational power, large data sets, and powerful client devices creates exciting opportunities for new research. Explore ways to leverage these resources to create innovative applications and services.

Application Resource Requirements:
Application resource requirements are specified in terms of tasks, each with its own set of properties like CPU cores, memory, and disk space. The scheduling system manages these tasks, fitting them into available resources.

Resource Dimensions and Node-Centricity:
Resource requirements are multidimensional, primarily involving memory, CPU, network, and disk. The approach is node-centric, focusing on individual nodes rather than coordinating with network management.

Infrastructure Challenges:
One major challenge is managing services across multiple data centers, due to the complexity of existing infrastructure. Simplification of tools and processes for cross-data center deployments is a key area of focus.

Data Growth and Storage Trends:
While the textual web is growing slower than hardware storage capabilities, high-quality video content is generating massive data and bandwidth demands. Keeping up with this data growth poses a significant challenge for infrastructure.

Energy Efficiency:
Power usage in data centers is a critical concern. Efforts are underway to optimize software and hardware for energy proportionality and reduce power consumption.

MapReduce and PageRank:
MapReduce is effective for certain tasks, particularly when quick and dirty solutions are needed. For highly optimized tasks like PageRank, customized systems may be more efficient. MapReduce chains with multiple reduce steps are sometimes used.

Google Instant and Infrastructure Impact:
Google Instant prefetches search results based on user input. It involves tagging requests as predictive prefetches to prioritize them during overload situations. The main impact on infrastructure is increased resource requirements due to prefetching.

Distributed Transactions within a Single Data Center:
Google has limited experience with distributed transactions in a single data center. Avoiding distributed transactions in the past led to hand-rolled protocols, causing issues. Spanner, a newer system, incorporates distributed transactions, addressing this concern.