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

Deterministic Parallel and Distributed Programm...

Deterministic Parallel and Distributed Programming with Clojure

Quick Intro to deterministic parallelism. Practical examples in Clojure. LVar(s), CRDT(s), Bloom, Derflow and others.

Oleksii Kachaiev

July 03, 2014
Tweet

More Decks by Oleksii Kachaiev

Other Decks in Programming

Transcript

  1. About me • CTO at Attendify.com • Clojure, Erlang, Go,

    Haskell • Fn.py library author • CPython & Storm contributor
  2. STM

  3. Why Determinism? • easy to reason about • easy to

    maintain • less bugs • less bugs that you can’t reproduce on your machine • less data losses (no data losses?) • provable correctness
  4. Why Determinism? • you should know why determinism is good

    if you listen to Clojure conference talks • we will talk about "ordering non-determinism" only (there’re many other reasons however)
  5. Parallel • > 1 independent workers (actors?) • loose coordination

    • great opportunities • … at a high price
  6. Distribution • More parallelism (!) • For lower latency •

    For storage replication • For HA • And more … but more non-determinism factors • Unpredictable latencies • "Random" workers crash
  7. Consensus • Non-distributed: locks, semaphores etc • Distributed: 2p-commit, paxos,

    zab, raft • … but this price is too high in many cases! • … you’re trading availability in most cases
  8. Theory • "Logic and Lattices for Distributed Programming" http://goo.gl/5q7CJF •

    "CRDTs: Consistency without concurrency control" http://goo.gl/Ouu4sc • "A comprehensive study of Convergent and Commutative Replicated Data Types" http://goo.gl/I1alMi • "A Lattice-Theoretical Approach to Deterministic Parallelism with Shared State" http://goo.gl/cdv1UK
  9. Practice • mobile application • chat message stream • k-ordered

    message IDs • "latest viewed message" mark • offline-mode support
  10. LVar • Haskell library lvish • Monotonically growing, lattice-based data

    structures • determinism VS. quasi-determinism • threshold reads • freezing variables
  11. Bloom • disorderly programming • state represented with lattices (few

    built-in) and collections (table, scratch, channel) • runtime implementation as Ruby DSL • static analysis tools (points of order) • visualisation tools
  12. Derflow • Deterministic dataflow programming • Growing set of single-assignment

    variables • Operations: declare, bind, read/wait • Streams: produce/consume • Erlang implementation: http://goo.gl/lnnfVd
  13. Why Clojure? • strong concurrency primitives (atom) • immutable data

    types • CRDT library "knockbox" (dead?) • not that much done for distributed computing (riak_core in Erlang) • one can use Akka/Pulsar • aphyr/jepsen for testing partition tolerance • a big room for experiments
  14. Links • "Eventually Consistent Data Structures" http://goo.gl/HgtIzY • "Knockbox, an

    Eventual Consistency Toolkit" http://goo.gl/r5XxRH • "LVars: lattice-based data structures for deterministic parallelism" http:// goo.gl/IJljEQ • "MVar, IVar, and LVar programs in Haskell" http://goo.gl/dF36k4 • "Distributed deterministic dataflow programming for Erlang" http://goo.gl/ y2oH0P • "Sync Free" http://goo.gl/qXZHnb