Map-Reduce and Cluster Architecture

• Map-Reduce covers distributed file systems, computational models, scheduling and data flow, and refinements.
• Single node architecture consists of CPU, memory, and disk.
• Single node architecture is used for machine learning, statistics, and "classical" data mining.

Google Example

• Analyzing 10 billion web pages demonstrates the motivation for distributed computing.
• The average webpage size is 20KB.
• The total size of 10 billion webpages is 200 TB.
• With a disk read bandwidth of 50 MB/sec, it would take 4 million seconds (46+ days) to read all the data.

Cluster Architecture

• Cluster architecture uses a 2-10 Gbps backbone between racks.
• There is 1 Gbps between any pair of nodes in a rack.
• Each rack contains 16-64 commodity Linux nodes (servers/computers).
• In 2011, it was estimated that Google had 1 million machines.

Cluster Computing Challenges

• Node failures are a significant challenge in cluster computing.
• A single server can stay up for 3 years (1000 days).
• A cluster with 1000 servers experiences approximately 1 failure per day.
• A cluster with 1 million servers experiences approximately 1000 failures per day.
• Storing data persistently and keeping it available when nodes fail is a challenge.
• Dealing with node failures during long-running computations is a challenge.
• Network bottleneck is a challenge, as network bandwidth is 1 Gbps.
• Moving 10TB of data takes approximately 1 day.
• Distributed programming is hard and requires a simple model to hide complexity.

Map-Reduce Solution

• Map-Reduce addresses cluster computing challenges.
• It stores data redundantly on multiple nodes for persistence and availability.
• It moves computation close to data to minimize data movement.
• It uses a simple programming model to hide the complexity.

Redundant Storage Infrastructure & Distributed File System

• A distributed file system provides a global file namespace, redundancy, and availability.
• Examples of distributed file systems are Google GFS and Hadoop HDFS.
• Typical usage patterns involve huge files (100s of GB to TB).
• Updates to data are rare and reads and appends are common.
• Data is kept in "chunks" spread across machines.
• Each chunk is replicated on different machines for redundancy.
• Replication ensures persistence and availability.
• Chunk servers also serve as compute servers.
• Bringing computation to data is crucial.
• Files are split into contiguous chunks (16-64MB).
• Each chunk is usually replicated 2x or 3x.
• Replicas are ideally kept in different racks.
• A master node keeps track of where files are stored.
• The master node is also known as the Name Node in Hadoop’s HDFS.
• The master node stores metadata about where files are stored.
• The master node might be replicated.
• A client library for file access communicates with the master to find chunk servers.
• The client library connects directly to chunk servers to access data.