Atomicity of Updates (or All-or-Nothing)

For more info about our services contact : help@bestpfe.com

Table of contents

List of Tables
List of Figures
1 Introduction
1.1 Contributions
1.1.1 Part I – Cure: Strong semantics meets high availability and low-latency
1.1.2 Part II – The three-way trade-off for transactional reads
2 System Model
2.1 Cloud Service Architecture
2.2 Tight Latency and Availability requirements
2.2.1 The effects of latency
2.2.2 The effects of downtimes
2.3 Geo-distribution and the CAP theorem
2.3.1 CP designs
2.3.2 AP designs
3 Storage Semantics
3.1 Transactions – ACID properties
3.1.1 Moving away from, back to ACID
3.2 Atomicity of Updates (or All-or-Nothing)
3.3 Transactional Isolation Levels (Consistency Criteria)
3.3.1 Notation
3.3.2 Concurrency control
3.3.2.1 Lock-based concurrency control
3.3.2.2 Multi-version concurrency control (MVCC)
3.3.2.3 Choosing a technique
3.3.2.4 Mixing them
3.3.3 Anomalies
3.3.3.1 Dirty read
3.3.3.2 Non-repeatable read
3.3.3.3 Lost update
3.3.3.4 Write skew
3.3.3.5 Non-monotonic snapshots
3.3.3.6 Read Skew
3.3.3.7 Real-time violation
3.3.3.8 Order Violation
3.3.4 CP (Strong) Isolation
3.3.4.1 Strict Serialisability (SS) – no anomalies
3.3.4.2 Serialisability (S) – relaxing real-time ordering
3.3.4.3 Snapshot Isolation (SI) – removing serialisability checks from read operations
3.3.4.4 Update Serialisability (US) – non-monotonic snapshots
3.3.4.5 Parallel Snapshot Isolation (PSI)
3.3.5 AP (Weak) Isolation
3.3.5.1 Transactional Causal Consistency (TCC)
3.3.5.2 Read Atomic (RA)
3.3.5.3 Read Committed (RC and RCÅ)
3.3.5.4 No Isolation (NI)
3.3.6 Summary of anomalies allowed/disallowed by Isolation levels
3.4 Session guarantees
3.5 Single-object Consistency and Isolation
3.5.1 CP Consistency
3.5.1.1 Linearisability
3.5.2 AP Consistency
3.5.2.1 Causal consistency
3.5.2.2 Eventual Consistency
3.5.2.3 Ensuring Convergence
I Cure: strong semantics meets high availability and low latency
4 Introduction to Part I
5 Overview of Cure
5.1 Transactional Programming Model
5.2 Programming interface
5.3 Design – causal consistency
5.3.1 Updates applied in causal order for high availability
5.3.2 Dependency stabilisation for scalability
5.3.3 Vector clocks for serving fresh data
6 Protocol description
6.1 Notation and definitions
6.2 Transaction Execution
6.3 Replication and stable snapshot computation
6.4 Correctness
6.5 Discussion
6.5.1 Session Guarantees
6.5.2 Efficient SS computation
6.5.3 Garbage Collection
6.5.4 Support for CRDTs
7 Evaluation of Cure
7.1 Setup
7.2 Cure’s scalability
7.3 Comparison to other systems
8 Conclusion of Part I
II The three-way trade-off: Read Isolation, Latency and Freshness
9 Introduction to Part II
10 Requirements
10.1 Transactions
10.2 Snapshot guarantees
10.2.1 Committed Visibility
10.2.2 Order-Preserving Visibility
10.2.3 Atomic Visibility
10.3 Delay
10.3.1 Minimal Delay
10.3.2 Bounded delay
10.3.3 Mutex reads/writes (or unbounded delay)
10.4 Freshness
10.4.1 Latest Freshness
10.4.2 Stable Freshness
10.4.3 Concurrent Freshness
10.5 Optimal reads
11 The three-way trade-off
11.1 Notation and Definitions
11.2 Impossibility of optimal reads under ordered visibility
11.3 What freshness is compatible with minimal delay?
11.3.1 Optimal reads under Committed Visibility
11.3.2 Order-Preserving visibility and concurrent freshness
11.3.3 Minimal-delay Atomic Visibility requires stable freshness
11.4 What is possible under latest freshness?
11.5 Isolated reads with bounded delays and concurrent freshness.
12 Unexplored Isolation Levels
12.0.1 CV-US and OP-US
12.0.2 TCC¡
12.0.3 PSI¡
13 Minimal-delay protocol design
13.1 Cure recapitulation
13.2 Changes to the base protocol
13.3 Transaction execution overview
13.3.1 Transaction Coordinator (Algorithm 13.1)
13.3.2 Partitions (Algorithm 13.2)
13.4 Protocol particularities and correctness
13.5 Stabilisation protocol
13.6 Causal consistency: session guarantees
13.6.1 Read your writes
13.6.2 Monotonic Reads
14 Evaluation
14.1 Implementation
14.2 Setup
14.3 Experiments
14.3.1 Single-shot read-only transactions
14.3.2 Facebook-like read-only transactions.
15 Conclusion of Part II
IIIRelated Work
16 Causal Consistency for Cloud Deployments
16.1 Causally-Consistent Systems
16.1.1 Single-machine Causal Consistency
16.2 Strongly-Consistent Systems Enforcing Causal Consistency
17 Comparison of Transactional Systems
17.0.1 Weakly-consistent systems
17.0.2 Strongly-consistent systems
18 Conclusion
Bibliography