# 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)