Rui's Blog
Search
K

4.2 Large Scale Data Storage

MapReduce

Motivation

  • Challenges w/ traditional programming models (MPI)
    • Deadlock is possible: Blocking communication can cause deadlock
    • Large overhead from communication mismanagement
    • Load imbalance
    • Hard to code
  • Challenges with commodity clusters
    • Web datasets can be very large
    • Standard architectures are emerging -- how to organize computations on this storage?
  • Solutions
    • Use distributed storage
      • 6-24 disks attached to a blade, 32-64 blades in a rack connected by Ethernet
    • Push computations down to storage
  • Stable storage becomes a first order problem. Answer: Distributed File System
    • Typical usage pattern
      • Huge files (100s of GB to TB)
      • Data is rarely updated in place
      • Reads and appends are common

TODO

CAP Theorem & Eventual Consistency

CAP & Eventual Consistency

  • Consistency models for distributed systems: ACID, BASE, Paxos
  • CAP theorem (Eric Brewer, 2002; started as conjecture, proven in 2002?): You can have just two of Consistency, Availability, and Partition Tolerance
    • Consistency: All nodes see the same data at the same time
    • Availability: A guarantee that every request receives a response about whether it was successful or failed
    • Partition tolerance: The system continues to operate despite arbitrary message loss or failure of part of the system
  • Data centers should weaken consistency for faster response

ACID & BASE

  • ACID
    • Atomicity: Even if transactions have multiple operations, does them to completion (commit) or rolls back so that they leave no effect (abort)
    • Consistency: A transaction that runs on a correct database leaves it in a correct/consistent state
    • Isolation: It looks as if each transaction ran all by itself. Basically says "we'll hide any concurrency"
    • Durability: Once a transaction commits, updates can't be lost or rolled back

Zookeeper & Paxos

Distributed Key-Value Store

Scalable Databases

Publish-Subscribe Queues (Kafka)