We Hear You Like Papers: Eventual Consistency

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