CAP, and More Consistency Models
CAP theorem
• Fault model now considers network partitioning (i.e., message lost, beyond fail-stop failure) happens
Copyright By PowCoder代写 加微信 powcoder
• FLP considers fail-stop only
• CAP adds a focus on availability
• Tradeoff on
• Choosing C over A
• Your request may timeout • Choosing A over C
• Your request returns
• But the results might not be the latest or consistent
Consistency Model for RSM
l Strongly related to ordering l Because of CAP
l Internet companies prefer to keep A, so sacrifice C
l From Strong to Weak
l From no divergence across replicas to allowing divergence
n Linearizable consistency (a.k.a. strong consistency) n Sequential consistency (=total ordering)
n Causal consistency
n FIFO consistency
n Eventual consistency
Consistency models
l Linearizable consistency (a.k.a strong consistency)
l All operations appear to have executed atomically in an order that is consistent with the global
real-time ordering of operations. (Herlihy & Wing, 1991)
l “Behave like a single machine”: (1) total order, (2) order match real-time (3) reads its own write
l Sequential consistency (total order)
l All operations appear to have executed atomically in some order that is consistent with the order seen at individual nodes and that is equal at all nodes. (Lamport, 1979)
Eventual Consistency
l No lost updates
l Eventually your updates will be propagated to all replicas
l Order doesn’t matter
l Add Iphone first vs add iphone case first to your shopping cart doesn’t matter
l No safety:
l Some reads will base their work w/o seeing your update
l Need application-level reconciliation that is suitable to individual applications l Shopping cart in Amazon (Dynamo)
n Added item never lost
l But deleted item can be resurfaced ^_^”
n Add-to-cart(Cola)
n Add-to-cart(iPhone13)
n Delete(Cola)
n Add-to-cart(iPhone13 case)
n Network partition, client restart, whatoever
n Get-cart()àonly see iPhone 13
n Add-to-cart(iMac) //allow it to carry on
n Get-cart() -> see everything back: Cola, iPhone13, iPhone 13 case, iMac
l The point is,
l the iMac is added on an obsolete shopping-cart but it is still there
Eventual Consistency
l E.g., CRDT (Conflict-free Replicated Data Type) l An abstract data type whose all possible internal states
form a lattice
l Two instances of a CRDT can be merged
l Eventually, the states of two CRDT replicas that may have seen different orders can always be merged into a new final state (the tip of the lattice) that incorporates all the inputs seen by both.
l https://crdt.tech/
https://www.serverless.com/blog/crdt-explained-supercharge-serverless-at-edge
Causal Consistency
l Remember “I lost my son” and “Thanks God” example? l Best consistency in the potential presence of P:
Consistency vs
l Recently, from C vs A to C vs S
l “The first principle of successful scalability is to batter the consistency mechanisms down to a minimum, move them off the critical path, hide them in a rare visited corner of the system, and then make it as hard as possible for application developers to get permission to use them”
l By James Hamilton (AWS VP)
l That is, the coordination used for upkeeping consistency (e.g., Paxos, Raft,
2PC) is the bottleneck of both throughput and scalability l 90% of time can spend on waiting for coordination
l How can we avoid coordination as Hamilton recommend?
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com