Scalable Analytics: 1

Computational Infrastructure and Architecture

• Scalable Analytics Overview:

  • Led by prof. dr. Pieter Libin, VUB (Vrije Universiteit Brussel).

  • Focused on infrastructure and the MapReduce framework.

• Single Node Architecture:

  • Components: CPU, Memory, Disk.

  • Primary Uses: Machine Learning, Statistics, and "Classical" Data Mining.

• Cluster Architecture:

  • Structure: Multiple nodes containing Memory (Mem), Disk, and CPU connected via a Switch.

  • Rack Configuration: Each rack typically contains 16-64 nodes.

  • Networking Speeds:

    • $1\,\text{Gbps}$ between any pair of nodes in a rack.

    • $2-10\,\text{Gbps}$ backbone between racks.

  • Scale: In 2011, it was estimated that Google utilized approximately $1\,\text{M}$ machines.

• Shared Memory Models:

  • Definition: A large block of RAM that is accessible by multiple CPUs.

  • Types of Shared Memory:

    • UMA (Uniform Memory Access).

    • NUMA (Non-Uniform Memory Access): Mentioned in the context of the HP Z820 system (Katsikas, 2016).

• Processing Units Comparison:

  • CPU (Intel Core i7):

    • Pros: High flexibility.

    • Cons: Sequential execution, low efficiency.

  • GPU (Nvidia Quadro / TITAN):

    • Graphical Processing Unit: Now used for general purposes (General purpose GPUs).

    • Pros: High throughput.

    • Cons: High power consumption, relies on batch processing.

  • ASIC (Tensor Processing Unit / TPU):

    • Application-Specific Integrated Circuit: Designed as an AI accelerator for neural network machine learning.

    • Pros: Low power consumption, high performance.

    • Cons: Low flexibility after "tape out."

Large-Scale Computing and Distributed File Systems

• Motivating Example: Google Web Indexing:

  • Scale: $20+\text{ billion web pages} \times 20\,\text{KB} = 400+\text{ TB}$.

  • Constraint: A single computer reads approximately $30-35\,\text{MB/sec}$ from disk.

  • Time Requirement: It would take approximately 4 months to read the entire web using one machine.

  • Storage Requirement: Approximately $1,000$ hard drives are required to store the web data.

  • Solution: A cluster of commodity Linux nodes connected by a commodity network (ethernet).

• Challenges of High-Scale Computing:

  • How to distribute computation effectively.

  • How to make distributed programming accessible/easy.

  • Handling inevitable machine failures.

  • Solving the time-cost of copying data over networks.

• Core Philosophical Solution:

  • Bring computation close to the data: Rather than moving data to a central processor, move the processing tasks to where the data is stored.

  • Store files multiple times: Ensure reliability through redundancy.

• Distributed File System (DFS):

  • Purpose: Provides a global file namespace to store data persistently even if nodes fail.

  • Implementations: Google GFS and Hadoop HDFS.

  • Usage Patterns:

    • Handles huge files (100s of GB to TB).

    • Data is rarely updated in place.

    • Reads and appends are the primary operations.

  • Architecture:

    • Master Node: Manages the system.

    • Chunk Servers: Store the data chunks and also serve as compute servers.

    • Client Library: Handles file access.

  • Reliability:

    • Data is kept in "chunks" spread across machines.

    • Each chunk is replicated on different machines ($C0, C1, C2,$ etc.) to allow seamless recovery from disk or machine failure.

The MapReduce Programming Model

• Definition:

  • A style of programming designed for easy parallel programming, invisible management of hardware/software failures, and management of very-large-scale data.

  • Implementations include Hadoop, Spark, and Google's original MapReduce.

• Word Count Case Study:

  • Scenario 1: File is too large for memory, but all $\text{}$ pairs fit in memory.

  • Scenario 2 (The essence of MapReduce): Using UNIX commands: $\text{words(doc.txt) | sort | uniq -c}$.

• MapReduce Operational Overview:

  • Map Phase: Sequentially reads data and extracts relevant information to produce a set of key-value pairs. Provided by the programmer.

  • Group by Key (Sort and Shuffle): Environment collects all pairs with the same key. This phase is handled automatically by the environment.

  • Reduce Phase: Collects all values belonging to a key and aggregates, summarizes, filters, or transforms them to output a result $\text{(key, value)}$. Provided by the programmer.

• Word Count Pseudocode:

  • Map Function:

    • map(key, value): where key is the document name and value is the text.

    • for each word w in value: emit(w, 1)

  • Reduce Function:

    • reduce(key, values): where key is a word and values is an iterator over counts.

    • result = 0

    • for each count v in values: result += v

    • emit(key, result)

• MapReduce Environment Responsibilities:

  • Partitioning input data.

  • Scheduling execution across a set of machines.

  • Performing the "group by key" step.

  • Handling machine failures (pings workers periodically).

  • Managing inter-machine communication.

Execution, Data Flow, and Fault Tolerance

• Parallel Execution Structure:

  • Includes multiple Map Tasks and multiple Reduce Tasks.

  • Uses a Partitioning Function to distribute keys to specific reducers.

• Data Flow Storage:

  • Input and final output are stored on the Distributed File System (DFS).

  • Intermediate results are stored on the local File System (FS) of Map and Reduce workers.

  • Output from one task often serves as input for another.

• Task Granularity:

  • Let $M = \text{map tasks}$ and $R = \text{reduce tasks}$.

  • Rule of thumb: Make $M$ much larger than the number of nodes in the cluster ($M \gg \text{nodes}$).

  • Usually, $R$ is smaller than $M$.

  • Benefits of Fine Granularity:

    • Faster fault recovery.

    • Enables pipeline shuffling during map execution.

    • Improved dynamic load balancing.

• Dealing with Failures:

  • Map worker failure: Re-executed by the master since intermediate data on local disk is lost.

  • Reduce worker failure: Only incomplete tasks need re-execution; completed tasks are stored on DFS.

  • Master failure: The whole MapReduce job is typically aborted and restarted.

Mathematical Examples and Applications

• Host Size Calculation:

  • Input: Metadata file with lines (URL, size, date, ...).

  • Task: Find total bytes per host.

  • Logic: Group by host and sum the sizes.

• Language Model Statistics:

  • Task: Count occurrences of every 5-word sequence (n-grams) in a large corpus for statistical machine translation.

  • Map: Extract (5-word sequence, count).

  • Reduce: Combine the counts.

• Matrix-Vector Multiplication:

  • Given an $n \times n$ matrix $M$ with elements $m_{ij}$ and a vector $v$ of length $n$ with elements $v_j$.

  • The product is $x_i = \sum_{j=1}^{n} m_{ij}v_j$.

  • Map Phase: Operates on a chunk of matrix $M$. From each $m_{ij}$, it produces a key-value pair $(i, m_{ij}v_j)$. This assumes $v$ is available in memory at the node.

  • Reduce Phase: Sums all values associated with key $i$ to result in $(i, x_i)$.

  • Variant (Large Vector): If vector $v$ does not fit in main memory, divide matrix $M$ into vertical strips and vector $v$ into horizontal stripes.

• Cost Measures for Algorithms:

  1. Communication cost: The amount of data moved between nodes.

  2. Reduce-key complexity: The computational effort involved in processing keys during the reduce phase.

Available Implementations and Cloud Services

• Implementations:

  • Google: Internal proprietary system.

  • Hadoop: Open-source Java implementation using HDFS.

  • Aster Data: Cluster-optimized SQL database implementing MapReduce.

• Cloud Computing:

  • Services like Amazon's "Elastic Compute Cloud" (EC2) allow renting computing power by the hour.

  • Hadoop and Aster Data can be deployed on EC2.

• Referenced Literature:

  • Dean, J., & Ghemawat, S. (2004). MapReduce: Simplified Data Processing on Large Clusters.

  • Ghemawat, S., Gobioff, H., & Leung, S. T. (2003). The Google File System.

  • Related concepts: Functional programming primitives, NOW-Sort (1997), BAD-FS (2004), Active Disks (2001), Diamond (2004), Charlotte (1996), River (1999).