NoSQL - Map reduce

• Inspired by functional programming (e.g., Lisp, Haskell)

• Map

  • Generates intermediate results from input data

  • Input: aggregates

  • Output: key-value pairs

  • Each map task is independent → safely parallelizable

• Reduce

  • Aggregates intermediate results

  • Input: multiple map outputs with the same key

  • Output: a combined value per key

• Analogies:

  • Map ≈ SQL GROUP BY

  • Reduce ≈ SQL AGGREGATE

• Not bound to a specific architecture

• Can be realized in:

  • Distributed memory environments (e.g., clusters)

    • Often use centralized coordination with a single master

    • Examples: Google, Hadoop

  • Shared memory environments (e.g., multi-core machines)

    • Can use decentralized coordination, such as hash-based

    • Examples: Phoenix (Stanford), C++ with PThreads

• Address network traffic issues by reducing data locally first

• Apply reduce function locally (pre-aggregation) before global reduction

• Transfers less data across the network

• Steps:

  • Map

  • Local Reduce

  • Shuffle and Sort

  • Global Reduce

• Composability:

  • Output type of reduce must match input type of map

  • Allows nesting: reduce(key, [C, reduce(key, [A, B])]) == reduce(key, [C, A, B])

• Confluence:

  • Idempotency: Reapplying reduce does not change the result

  • Order-agnosticism: Result doesn’t depend on order of values:

    reduce(key, [A, B]) == reduce(key, [B, A])

• No coordinating master needed

• Works with consistent hashing

• MAP: Logic sent to nodes, applied locally based on hashed input data, clockwise

• REDUCE: Logic sent to nodes, applied locally based on hashed intermediate results, also clockwise

• Nodes act as workers, executing tasks based on hash values

Drawbacks:

• No traditional RDBMS optimization (no indexes, no query optimizer)

• Incompatible with common DB tools (e.g., BI, mining tools)

• No high-level query languages, only low-level operations

Enhancements:

• Sawzall (Google): scripting language for MapReduce generation

• Pig (Yahoo): higher-level scripting with SQL-like constructs

• These tools make MapReduce more accessible for data analysts