$30 off During Our Annual Pro Sale. View Details »

We Hear You Like Papers: Eventual Consistency

We Hear You Like Papers: Eventual Consistency

Given at Women Who Code Sydney IT meetup

Resources: https://github.com/CaitieM20/Talks/tree/master/SoWeHearYouLikePapers

Caitie McCaffrey

December 07, 2016
Tweet

More Decks by Caitie McCaffrey

Other Decks in Technology

Transcript

  1. Papers
    We hear you like

    View Slide

  2. @Caitie
    Caitie 

    McCaffrey

    View Slide

  3. Distributed
    Systems

    View Slide

  4. Service Service
    Service
    We Are All
    Building
    Distributed
    Systems

    View Slide

  5. Twitter
    Services

    View Slide

  6. View Slide

  7. academic
    Papers

    View Slide

  8. Eventual
    Consistency

    View Slide

  9. 1983 1995
    Thinking Consistency
    Detection of
    Mutual
    Inconsistency
    in Distributed
    Systems
    Managing
    Update Conflicts
    in Bayou, a
    Weakly
    Connected
    Replicated
    Storage System
    Brewer's
    conjecture &
    the feasibility of
    consistent,
    available,
    partition-tolerant
    web services
    2002

    View Slide

  10. 2015
    2011
    Conflict-free
    replicated Data
    Types
    Feral Concurrency
    Control: An Empirical
    Investigation of
    Modern Application
    Integrity
    Thinking Consistency

    View Slide

  11. Service
    Service
    Service
    Applications Before

    View Slide

  12. Service
    Service
    Service
    Applications Before

    View Slide

  13. ApplicationsNow
    Service
    Service
    Service

    View Slide

  14. 1983

    View Slide

  15. High
    availability

    View Slide

  16. High
    availability
    “In some environments
    it is desirable or
    necessary to permit
    users to continue
    modifying resources
    such as files when the
    network is partitioned”

    View Slide

  17. Origin
    Points
    &
    Version
    Vectors

    View Slide

  18. Version Vectors
    “A Version Vector for a file f is a sequence of n
    pairs, where n is the number of sites at which f
    is stored … the ith vector entry counts the
    number Vi of updates to f made at site Si”

    View Slide

  19. Compatible Version Vectors


    View Slide



  20. Incompatible Version Vectors

    View Slide

  21. ABCD
    Partition Graph
    C:0, D:0>

    View Slide

  22. ABCD
    AB CD
    Partition Graph
    C:0, D:0>
    C:0, D:0>
    C:0, D:0>

    View Slide

  23. ABCD
    AB CD
    Partition Graph
    C:0, D:0>
    C:0, D:0>
    C:0, D:0>

    View Slide

  24. ABCD
    AB CD
    D
    BC
    A
    Partition Graph
    T2
    C:0, D:0>
    C:0, D:0>
    C:0, D:0>
    C:0, D:0>
    C:0, D:0>

    View Slide

  25. ABCD
    AB CD
    D
    BC
    A
    Partition Graph
    T2
    C:0, D:0>

    C:0, D:0>

    C:0, D:0>
    No Conflict!

    View Slide

  26. ABCD
    AB CD
    D
    BC
    A
    Partition Graph
    T2
    C:0, D:0>
    C:0, D:0>
    C:0, D:0>
    C:0, D:0>
    C:0, D:0>
    C:0, D:0>

    View Slide

  27. ABCD
    AB CD
    D
    BC
    A
    Partition Graph
    T2
    C:0, D:0>
    C:0, D:0>
    C:0, D:0>
    C:0, D:0>
    C:0, D:0>
    C:1, D:0>

    View Slide

  28. ABCD
    AB CD
    D
    BC
    A
    BCD
    Partition Graph
    T2
    C:0, D:0>
    C:0, D:0>
    C:0, D:0>
    C:0, D:0>
    C:0, D:0>
    C:1, D:0>

    View Slide

  29. ABCD
    AB CD
    D
    BC
    A
    BCD
    Partition Graph
    T2
    C:0, D:0>
    C:0, D:0>

    C:0, D:0>
    C:0, D:0>

    No Conflict!

    View Slide

  30. ABCD
    AB CD
    D
    BC
    A
    BCD
    Partition Graph
    T2
    C:0, D:0>
    C:0, D:0>
    C:0, D:0>
    C:0, D:0>
    C:0, D:0>
    C:1, D:0>
    C:1, D:0>

    View Slide

  31. ABCD
    AB CD
    D
    BC
    A
    BCD
    Partition Graph
    T2
    C:0, D:0>
    C:0, D:0>
    C:0, D:0>
    C:0, D:0>
    C:0, D:0>
    C:1, D:0>
    C:1, D:0>
    ABCD

    View Slide

  32. ABCD
    AB CD
    D
    BC
    A
    BCD
    ABCD
    Partition Graph
    T2
    C:0, D:0>
    C:0, D:0>
    C:0, D:0>
    C:0, D:0>

    C:1, D:0>

    Conflict!

    View Slide

  33. Conflict Resolution
    “A conflict detection
    mechanism, while valuable,
    has increased effect if
    there is also a method for
    reconciling conflicts
    automatically”

    View Slide

  34. 1995

    View Slide

  35. Bayou Summary
    System designed for weak connectivity
    Eventual consistency via application-
    defined dependency checks and
    developer defined merge procedures
    Epidemic algorithms to replicate state

    View Slide

  36. “Applications must be
    aware of and integrally
    involved in conflict
    detection and resolution”
    Terry et. al

    View Slide

  37. Bayou Take aways & thoughts
    “Humans would
    rather deal with
    the occasional
    unresolvable
    conflict than
    incur the
    adverse impact
    on availability”

    View Slide

  38. 2002

    View Slide

  39. CAP Theorem
    PARTITION TOLERANCE
    CONSISTENCY AVAILABILITY

    View Slide

  40. Consistency
    Models
    Linearizable
    Sequential
    Causal
    Pipelined random
    access memory
    Read your write Monotonic read Monotonic write
    Write from read
    CP Consistency
    AP Consistency

    View Slide

  41. 2011

    View Slide

  42. CRDTs Summary
    Mathematical properties & epidemic
    algorithms / gossip protocols
    Strong Eventual Consistency - apply
    updates immediately, no conflicts, or
    rollbacks via

    View Slide

  43. CRDTs
    * Stolen from Chris Meiklejohn
    in practice

    View Slide

  44. Applying rollbacks is
    hard
    Restrict operation
    space to get provably
    convergent systems
    Active area of research
    Resolving Conflicts

    View Slide

  45. Applying rollbacks is
    hard
    Restrict operation
    space to get provably
    convergent systems
    Active area of research
    Resolving Conflicts

    View Slide

  46. 2015

    View Slide

  47. Feral mechanisms for keeping DB integrity
    Application-level mechanisms
    Analyzed 67 open source Ruby on
    Rails Applications
    Unsafe > 13% of the time 

    (uniqueness & foreign key constraint violations)

    View Slide

  48. Concurrency control is hard!
    Availability is important to application
    developers
    Home-rolling your own concurrency
    control or consensus algorithm is very
    hard and difficult to get correct!

    View Slide

  49. Eventual Consistency
    We want highly available systems so we must use
    weaker forms of consistency (remember CAP)
    Application semantics helps us make better
    tradeoffs
    Do not recreate the wheel, leverage existing
    research allows us to not repeat past mistakes
    Forced into a feral world but this may change soon!
    Tl;DR

    View Slide

  50. @Caitie
    Thank you!

    View Slide

  51. @Caitie
    Thank you!
    Follow
    your
    dreams!

    View Slide