Skip to content

Latest commit

 

History

History
88 lines (62 loc) · 2 KB

CRDT_Roadmap.md

File metadata and controls

88 lines (62 loc) · 2 KB

Consistency without consensus in production systems

(Video Talk)

Idioms

1908's RPC's

  • Model network communication with a function call

2000 CAP_

  • Partition Tolerance
    • System continue to operate despite message loss or unavailability
  • CP Systems
    • Strong consistency up to a threshold of failure
    • Based on consistency protocols
      • Paxos (1989), Zab (2008), Raft (2013), Viewstamped Replication (1988)
  • AP Systems
    • Used by most distributed data systems
      • mongo, cassandra, riak, couch
    • Often just "less than strong consistency"
      • "system will converge, eventually"

CALM Principle

  • "Consistency as Logical Monotonicity"
  • As a system gets more messages, it should only grow in one dimension.
    • Example language: bloom language

ACID 2.0

  • Associative, Commutative, Idempotent, Distributed

CRDT

  • Conflict-free replicated data type
  • Set's are a good example
    • Let's us fix the problem over time, given some inconsistency

Failure

How can messages fail?

  • Delayed
  • Dropped
  • Delivered out of order
  • Duplicated

Examples

Addition

[x] Communative [x] Associative [ ] Idempotent

Set Unions

[x] Communative [x] Associative [x] Idempotent

Use Cases

  • Fan out on write
    • When an event happens write it to each inbox that could consume it
  • Fan in on read
    • When a read happens, collect events from outboxes

Roshi Set

  • A single outerfacing set is represented by two sets
    • Write and delete sets, merged on read

Soundcloud example

 [r] [r] [r]   [r] [r] [r]
--- pool ---- --- pool ----
-- cluster -- -- cluster --
---------- farm -----------
  • Apps write to the farm, in which the farm duplicates the request to all clusters.
  • The keys are split up in the pool (name hashing)
  • Writes just need a quorum (typically > 51%)
  • When a cluster dies, add a new one to the farm.