Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Riak and Distributed Systems Tradeoffs

Riak and Distributed Systems Tradeoffs

An overview of the tradeoffs that went into building Riak and why they matter. (This deck borrows HEAVILY from a previous talk given by Andy Gross.)

Mark Phillips

June 26, 2012
Tweet

More Decks by Mark Phillips

Other Decks in Technology

Transcript

  1. Examples • Compilers trade space for speed when inlining code

    • Image and audio compression trade CPU/ fidelity loss for space • Databases trade consistency for availability in failure scenarios Tuesday, June 26, 12
  2. FooDB: The end of the tradeoff game! - Someone lying

    to you. DERPBase beats the CAP Theorem! - Someone lying to you. Tuesday, June 26, 12
  3. CAP • The fundamental, most-discussed tradeoff • When a network

    partition (message loss) occurs, laws of physics make you choose: • Consistency OR • Availability • No system can “beat the CAP theorem” Tuesday, June 26, 12
  4. PACELC • Nuance added by Daniel Abadi • When Partitioned,

    trade off Availability vs. Consistency • Else • Trade off Latency and Consistency Tuesday, June 26, 12
  5. • Location of data is determined based on a hash

    of the key • Provides even distribution of storage and query load • Trades off advantages gained from locality • range queries • aggregates Tuesday, June 26, 12
  6. Virtual Nodes • Unit of addressing, concurrency in Riak •

    Each host manages many vnodes • Riak *could* manage all host-local storage as a unit and gain efficiency, but would lose • simplicity in cluster resizing • failure isolation Tuesday, June 26, 12
  7. Append-Only Stores • All writes are appends to a file

    • This provides crash-safety, fast writes • Tradeoff: must periodically compact/merge files to reclaim space • Causes periodic pauses while compaction occurs that must be masked/mitigated Tuesday, June 26, 12
  8. Bitcask After the append completes, an in-memory structure called a

    ”keydir” is updated. A keydir is simply a hash table that maps every key in a Bitcask to a fixed-size structure giving the file, offset, and size of the most recently written entry for that key. When a write occurs, the keydir is atomically updated with the location of the newest data. The old data is still present on disk, but any new reads will use the latest version available in the keydir. As we’ll see later, the merge process will eventually remove the old value. Reading a value is simple, and doesn’t ever require more than a single disk seek. We look up the key in our keydir, and from there we read the data using the file id, position, and size that are returned from that lookup. In many cases, the operating system’s filesystem read-ahead cache makes this a much faster operation than would be otherwise expected. Tradeoff: Index must fit in memory Low Latency: All reads = hash lookup + 1 seek All writes = append to file Tuesday, June 26, 12
  9. Handoff and Rebalancing • When nodes are added to a

    cluster, data must be rebalanced • Rebalancing causes disk, network load • Tradeoff: speed of convergence vs. effects on cluster performance Tuesday, June 26, 12
  10. Vector Clocks • Provide happened-before relationship between events • Riak

    tags each object with vector clock • Tradeoff: space, speed, complexity for safety Tuesday, June 26, 12
  11. Gossip Protocol • Nodes “gossip” their view of cluster state

    to each other • Tradeoffs: • atomic modifications of cluster state for no SPOF • complexity for fault tolerance Tuesday, June 26, 12
  12. Sane Defaults • Speed vs. Safety • Riak ships with

    N=3, R=W=2 • Bad for microbenchmarks, good for production use, durability • Mongo ships with W=0 • Good for benchmarks, horrible and insane for durability, production use. Tuesday, June 26, 12
  13. Erlang • Best language ever: • for distributed systems glue

    code • for safety, fault tolerance • Sometimes you want: • Destructive operations • Shared memory Tuesday, June 26, 12
  14. NIFs to the rescue? • Use NIFs for speed, interfacing

    with native code, but: • You make the Erlang VM only as reliable as your C code • NIFs block the scheduler Tuesday, June 26, 12
  15. General Tradeoffs We don’t rush to add new features Even

    popular ones that everyone wants Until we know they wont force us to screw up one of our fundamental tradeoffs! Tuesday, June 26, 12