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

OOP 2021 - Eventual Consistency - Du musst kein...

OOP 2021 - Eventual Consistency - Du musst keine Angst haben

Der Trend zu hochskalierenden Cloud-Anwendungen, die auf datengetriebene Features setzen, ist ungebrochen und immer mehr Anwendungen laufen nur noch unter Eventual Consistency. Nebenläufige Änderungen auf inkonsistenten Daten können zu Replikations-Anomalien wie Lost Updates führen, deren Behandlung selbst für erfahrene Software-Architekt:innen eine Herausforderung darstellt. Der Vortrag vereint die neuesten Forschungsergebnisse und Lessons Learned aus mehreren Case Studies mit konkreten Entwurfsmustern für Architekt:innen.

susannebraun

February 11, 2021
Tweet

More Decks by susannebraun

Other Decks in Technology

Transcript

  1. © Fraunhofer IESE EVENTUAL CONSISTENCY Du musst keine Angst haben…

    Susanne Braun 11.02.2021 OOP Digital Oder doch?
  2. © Fraunhofer IESE 2 Pat Helland Database & Distributed Systems

    Guru Architect of multiple transaction & database systems (e.g. DynamoDB) Worked at Microsoft, Amazon, SalesForce, … “There is an interesting connection between fault tolerance, offlineable systems, and the need for application-based eventual consistency.” application-based eventual consistency fault tolerance, offlineable systems Conference on Innovative Data Systems Research, 2009
  3. © Fraunhofer IESE 3 “Correlating” Quality Attributes Fault Tolerance Resilience

    Loose Coupling Availability Scalability Offline Capability Network Partition Tolerance Low Latency Responsiveness
  4. © Fraunhofer IESE 4 Eric Brewer Distributed Systems Researcher Coined

    the CAP theorem, Contributed to Spanner Prof. emeritus University of California, Berkeley, works now for Google “But we forfeit C and I of ACID for availability, graceful degradation and performance.” ACM Symposium on Principles of Distributed Computing, 2000
  5. © Fraunhofer IESE 5 ACID vs. BASE ACID BASE Strong

    Consistency (in the sense of one-copy-consistency) Isolation (in the sense of one-copy-serializability) Pessimistic Synchronization (global locks, synchronous update propagation) Global Commits (2PC, majority consensus, …) Atomicity Consistency Isolation Durability Eventual Consistency (stale data & approximate answers) Availability (top priority) Optimistic Synchronization (no locks, asynchronous update propagation) Independent Local Commits (conflict resolution, reconciliation, …) Atomicity Consistency Isolation Durability ? Database is in a consistent state & all invariants are being met! This is about Concurrency Control! This is about Convergence!
  6. © Fraunhofer IESE 6 Consistency vs. Isolation “Consistency tries to

    mask the distributed nature of the system” “Isolation tries to mask the effects of concurrent execution” Make it appear as one system! Make it appear I am the only user of the system!
  7. © Fraunhofer IESE 7 Douglas Terry Distributed Systems Researcher Coined

    the term Eventual Consistency in the 90ties Former Prof. University of California, Berkeley, worked for Microsoft, Samsung, AWS “A system providing eventual consistency guarantees that replicas would eventually converge to a mutually consistent state, i.e., to identical contents, if update activity ceased.” Int. Conference on Parallel and Distributed Information Systems, 1994
  8. © Fraunhofer IESE 8 Douglas Terry Distributed Systems Researcher Coined

    the term Eventual Consistency in the 90ties Former Prof. University of California, Berkeley, worked for Microsoft, Samsung, AWS “A system providing eventual consistency guarantees that replicas would eventually converge to a mutually consistent state, i.e., to identical contents, if update activity ceased.” Int. Conference on Parallel and Distributed Information Systems, 1994 Pragmatic Definition A system provides eventual consistency if: (1)each update operation is eventually received by each replica (2)non-commutative update operations are performed in the same order at each replica (3)the outcome of a sequence of update operations is the same at each replica (determinism) Replicated Data Management for Mobile Computing, 2008
  9. © Fraunhofer IESE 9 Eventual Consistency Remember: The only guarantee

    you get: convergence to identical state Outdated Data Conflicts Potential Concurrency Anomalies Events / Operations coming out of order Application needs to handle: Huge source of human error!
  10. © Fraunhofer IESE 10 Eventual Consistency Remember: You do not

    get any isolation guarantees like ‘Repeatable Read’ Hard to test Issues emerge randomly in production … are hard to reproduce … are hard to debug Application needs to handle concurrency control: Huge source of human error!
  11. © Fraunhofer IESE 11 Consistency in Non-Transactional Distributed Storage Systems

    Source: ACM Computing Surveys, Vol. 49, No. 1, Article 19, 2016
  12. © Fraunhofer IESE 12 Pat Helland Database & Distributed Systems

    Guru Architect of multiple transaction & database systems (e.g. DynamoDB) Worked at Microsoft, Amazon, SalesForce, … “… it is time for us to move past the examination of eventual consistency in terms of updates and storage systems. The real action comes when examining application-based operation semantics.” in terms of Reads and Writes application-based operation semantics in terms of updates and storage Conference on Innovative Data Systems Research, 2009 eventual consistency systems
  13. © Fraunhofer IESE 13 Architecture Layers according to DDD Infrastructure

    Layer Domain Layer Application Layer DB :SELECT Statement DB :UPDATE Statement Application Service :Transaction Method Domain Service :Service Method Aggregate Repository :Query Method (findBy…) Aggregate :Update Method DB :BOT DB :EOT DIP DIP Low level Read / Write Operations Fine Grained Business Operations Coarse Grained Business Operations User Stories Domain Operations Eventual Consistency Goal Business Semantics
  14. © Fraunhofer IESE 14 Recap Concurrency Control in Relational DBs

    n A schedule of concurrent transactions is conflict-serializable iff the conflict graph is acyclic and compatible with the execution order of the conflicting operations Time R(a) W(a) R(a) W(a) R(b) W(b) R(b) W(b) Transactions T1, T2: T1 T2 Conflict graph: Conflict graph is cyclic ⇢ No conflict serializability ⇢ Schedule would be rejected
  15. © Fraunhofer IESE 15 Business Semantics - Banking t R(a)

    W(a) R(a) W(a) R(b) W(b) R(b) W(b) Withdraw(a) T1 Deposit(b) Withdraw(a) Deposit(b) T2
  16. © Fraunhofer IESE 16 Multilevel Transactions (Weikum et al. 1992)

    n If at each level the conflict serialization graph is acyclic then the multilevel schedule is in total multilevel serializable n Exploit semantics of operations in level-specific conflict relations that reflect the commutativity / compatibility of operations n Transactions are decomposed into operations and the operations again into sub-operations on multiple levels n Transactions, Business operations, Low-level read and write operations n At each level a conflict relationship is defined n read-write conflicts and write-write conflicts on the same data item conflict at the lowest level n Non-commutative operations are conflicting on the level of business operations In practice comparable to serializability! Goal: Increase number of operations that can run concurrently!
  17. © Fraunhofer IESE 17 Business Semantics - Banking t R(a)

    W(a) R(a) W(a) R(b) W(b) R(b) W(b) Withdraw(a) T1 Deposit(b) Withdraw(a) Deposit(b) T2 1 2 3 Low level Read / Write Operations Domain Operations Transactions
  18. © Fraunhofer IESE 18 Multilevel Transactions Example (Weikum et al.

    1992) t R(a) W(a) R(a) W(a) R(b) W(b) R(b) W(b) Withdraw(a) T1 Deposit(b) Withdraw(a) Deposit(b) T2 Conflict graph at level of domain operations: Conflict graph at level of transactions: ⌀ 1 2 3 Low level Read / Write Operations Domain Operations Transactions Withdraw(a) Withdraw(a) Deposit(b) Deposit(b) Conflict graph is acyclic at each level! 2 1 3 2
  19. © Fraunhofer IESE 19 Architecture Layers according to DDD Infrastructure

    Layer Domain Layer Application Layer Application Service :Transaction Method DB :SELECT Statement DB :UPDATE Statement Domain Service :Service Method Aggregate Repository :Query Method (findBy…) Aggregate :Update Method DB :BOT DB :EOT DIP DIP Low level Read / Write Operations Fine Grained Business Operations Coarse Grained Business Operations Business Semantics User Stories Domain Operations Eventual Consistency Goal
  20. © Fraunhofer IESE 21 Pat Helland Database & Distributed Systems

    Guru Architect of multiple transaction & database systems (e.g. DynamoDB) Worked at Microsoft, Amazon, SalesForce, … Conference on Innovative Data Systems Research, 2009 A C I D 2.0 Associative Commutative Idempotent Distributed (ab)c = a(bc) ab = ba aa = a Operations executed out of order…
  21. © Fraunhofer IESE 22 B e s t P r

    a c t i c e Popular Examples in Scientific Publications Commutative Operations o.domainOperation1(..) o.domainOperation2(..) = o.domainOperation2(..) o.domainOperaton1(..) ‘o’ is some Aggregate / Entity / Domain Service Counters - Integer Addition Sets – Insert Banking – Withdraw Banking – Deposit
  22. © Fraunhofer IESE 25 Annette Bieniusa CRDT Guru Co-Creator of

    AntidoteDB Worked at INRIA with Marc Shapiro, TU Kaiserslautern
  23. © Fraunhofer IESE 26 CRDTs are grounded in algebraic theories

    of monotonic semilattices Conflict-Free Replicated Data Types (CRDTs) CRDTs ship with commutative merge operations designed to be a least upper bound (LUB) of the conflicting operations. Intuitive Example: Amazon’s Shopping Card* Consider LUB as union of different object states produced at different replicas Shopping Card - Soap - Lotion Shopping Card - Lotion - Brush Merge Shopping Card - Soap - Lotion - Brush Deleted items might reappear * Werner Vogels, Communications of the ACM, Volume 52, Issue 1, 2009
  24. © Fraunhofer IESE 27 B e s t P r

    a c t i c e Incremental Operations Example: ‘Incremental Operations’ List – Append Note: list.add(’a’) list.add(‘b’) != list.add(‘b’) list.add(‘a’) Text - Insert Counters - Increment Incremental Operations evaluate the current state in order to derive the updated value. READ(state) WRITE(state) Updating Domain Operation State Access
  25. © Fraunhofer IESE 28 B e s t P r

    a c t i c e “Distributed” Operations Concurrent operations can be executed in a different order on different replicas. Example: Concurrent operations Domain Operations need the ability to produce intended updates if executed on different states on different replicas! Replica 1 Replica 2 Operation Operation Operation Operation Operation
  26. © Fraunhofer IESE 29 Collaborative Text Editing Replica 1 Replica

    2 insert(6, ‘r’) insert(1, ‘e’) insert(2, ‘l’) insert(6, ‘r’) “Hlo Wold” “Hlo World” “Helo Wold” “Hello Wold” “Hello rWold”
  27. © Fraunhofer IESE 33 B e s t P r

    a c t i c e Beware of Domain Invariants Model Domain Invariants explicitly! Examples: Banking – Withdraw withdraw(amount) { … assert(balance > dispoLimit) } Durability ?
  28. © Fraunhofer IESE 35 Pat Helland Database & Distributed Systems

    Guru Architect of multiple transaction & database systems (e.g. DynamoDB) Worked at Microsoft, Amazon, SalesForce, … “Immutability Changes Everything” ACM Queue, Volume 13, Issue 9, 2016
  29. © Fraunhofer IESE 36 C l a s s i

    f i c a t i o n 1st Level Classification of Replicated Aggregates Mutable ? Observed Aggregates* No Concurrent In-Place Updates ? Yes No Derived Aggregates* Multiple Updaters ? Yes Dedicated Aggregates Nontrivial Aggregates Yes No * “Append-Only Computing” – Helland 2015 Observed Aggregates: • Time series data (machine sensor data, market data, …) • Domain events Derived Aggregates: • Machine generated data (recommendations, …) • Timeline or newsfeed data Dedicated Aggregates: • User generated data (reviews, social media posts, ...) • Dedicated master data (user profiles, account settings) E x a m p l e s
  30. © Fraunhofer IESE 37 C l a s s i

    f i c a t i o n 2nd Level Classification of Nontrivial Aggregates Activity Aggregates Collaboration Result Aggregates Reference Aggregates Dedicated Aggregates Derived Aggregates Observed Aggregates Update Frequency in Peak Times Update Simultaneity in Peak Times Concurrency Anomaly Probability low improbable low - Nontrivial Aggregates Reference Aggregates Examples: • Master data (CRM data, resources, products, …) • Values (Valid currencies, product types, gender, …) • Meta data (Tags, descrtiptive data of raw data, ..)
  31. © Fraunhofer IESE 38 C l a s s i

    f i c a t i o n 2nd Level Classification of Nontrivial Aggregates Activity Aggregates Collaboration Result Aggregates Reference Aggregates Dedicated Aggregates Derived Aggregates Observed Aggregates Update Frequency in Peak Times Update Simultaneity in Peak Times Concurrency Anomaly Probability low high improbable probable low high - Nontrivial Aggregates Reference Aggregates Examples: • Master data (CRM data, resources, products, …) • Values (Valid currencies, product types, gender, …) • Meta data (Tags, descrtiptive data of raw data, ..) Activity Aggregates Examples: • State data of workflows, business processes, … • Coordination data of joint activities (agricultural field operation, meeting, …) • Task management data, Kanban board data, …
  32. © Fraunhofer IESE 39 C l a s s i

    f i c a t i o n 2nd Level Classification of Nontrivial Aggregates Activity Aggregates Collaboration Result Aggregates Reference Aggregates Dedicated Aggregates Derived Aggregates Observed Aggregates Update Frequency in Peak Times Update Simultaneity in Peak Times Concurrency Anomaly Probability low high very high improbable probable highly probable low high very high - Nontrivial Aggregates Reference Aggregates Examples: • Master data (CRM data, resources, products, …) • Values (Valid currencies, product types, gender, …) • Meta data (Tags, descrtiptive data of raw data, ..) Activity Aggregates Examples: • State data of workflows, business processes, … • Coordination data of joint activities (agricultural field operation, meeting, …) • Task management data, Kanban board data, … Collaboration Result Aggregates Examples: • Result data of collaborative knowledge work (CAD model, crop rotation plan, whiteboard diagram, …) • Text data as result of collaborative authorship (manuals, scientific papers, meeting protocols, …)
  33. © Fraunhofer IESE 40 C l a s s i

    f i c a t i o n 2nd Level Classification of Nontrivial Aggregates Activity Aggregates Collaboration Result Aggregates Reference Aggregates Dedicated Aggregates Derived Aggregates Observed Aggregates Update Frequency in Peak Times Update Simultaneity in Peak Times Concurrency Anomaly Probability “Technical Immutability Border” low high very high improbable probable highly probable low high very high - low improbable Nontrivial Aggregates
  34. © Fraunhofer IESE 41 B e s t P r

    a c t i c e Concurrency Anomalies Impact Assessment Concurrency Anomaly Probability Fixing Costs of Data Corruption low high very high very high high very high moderate very high moderate Reference Aggregates Activity Aggregates Collaboration Result Aggregates Dedicated Aggregates Derived Aggregates Observed Aggregates low Consequences of Data Corruption critical major critical minor depends critical Nontrivial Aggregates “Technical Immutability Border” Trivial Aggregates A Classification of Replicated Data for the Design of Eventually Consistent Domain Models, S. Braun, S. Dessloch, ICSA 2020
  35. © Fraunhofer IESE 42 Eventual Consistency is standard Estimation -

    Frequency of Distribution Trad. Enterprise IS (ERP, CRM, Workflow Management) Social Media Apps (Facebook, Twitter) Next Data-Intensive Systems (Smart Farming, Industrie 4.0) 30% 30% 9 % 45% 4% 1% 20% 20% 20% 20% “Technical Immutability Border” Reference Aggregates Activity Aggregates Collaboration Result Aggregates Dedicated Aggregates Derived Aggregates Observed Aggregates 1 % 50% 20% 30 %
  36. © Fraunhofer IESE 43 Trivial Aggregates First n Whenever feasible,

    model aggregates as trivial aggregates* B e s t P r a c t i c e P a t t e r n A n t i - P a t t e r n StockItems StockItem productId: String number: int 1..* 1 In-place Updates Nontrivial Activity Aggregate GoodsReceiepts OrderConfirmations Observed Aggregates StockItems StockItem productId: String number: int 1 Derived Aggregate Calculated periodically or on demand Technical Immutability 1..* * See also: Event Sourcing & CQRS (Command Query Responsibility Segregation)
  37. © Fraunhofer IESE 44 Dedicated Aggregates are Solitary n Design

    dedicated data as self-contained aggregate B e s t P r a c t i c e P a t t e r n A n t i - P a t t e r n Operation Field Assignment DocumentationRecords DocRecord 1..* 1 Nontrivial Activity Aggregate Dedicated to single user Operation Field Assignment DocumentationRecords DocRecord 1..* 1 Nontrivial Activity Aggregate Cross-aggregate reference Dedicated Aggregate 1..* 1..* 1 1 1 1 1 1 1..* 1..*
  38. © Fraunhofer IESE 45 Separation of Aggregate Classes n Whenever

    feasible, keep data of different classes in separate aggregates B e s t P r a c t i c e P a t t e r n A n t i - P a t t e r n Operation Field Assignment Nontrivial Activity Aggregate Reference data that is rarely updated Operation Field Assignment Nontrivial Activity Aggregate Reference Aggregate Cross-aggregate reference 1..* 1..* 1..* 1 1 1
  39. © Fraunhofer IESE 46 Derived Aggregates are idempotent n The

    calculation of the state of a derived aggregate should be idempotent & deterministic B e s t P r a c t i c e
  40. © Fraunhofer IESE 47 Do not Forget the Master n

    Consider using Primary Copy Replication, if transactional guarantees are required B e s t P r a c t i c e P a t t e r n A n t i - P a t t e r n Update Everywhere Primary Copy A A A A A A < A Update Update Update Update Update Update Update A A A A A A < A Update
  41. © Fraunhofer IESE 48 Future Work n ECD3 – Eventually

    Consistent Domain Driven Design n Best Practices & Software Architecture Design Guidelines n Framework Towards Multilevel Transactions n Action Research Study n Workshops with Practitioners EventuallyConsistentDDD/design-guidelines We’ re on Github!
  42. © Fraunhofer IESE 51 #Thanx #StayHome Fraunhofer IESE, Kaiserslautern Susanne

    Braun Software Developer & Architect [email protected] @susannebraun EventuallyConsistentDDD/design-guidelines