Project Topics
Get Complete Project Material File(s) Now! »
Update Serializability (US)
Update serializability, introduced by Garcia-Molina and Wiederhold [57], guarantees that update transactions are serialized with respect to other update transactions. Read-only transactions only need to take consistent snapshots, and always commit unilaterally. Thus, unlike SER, US does not guarantee a serial order among read-only transactions. This leads to the anomaly called long fork [136] or non-monotonic snapshot for read-only transactions. Consider the following history hnms. Read-only transaction Ta takes snapshot {x0, y2}, and Tb takes snapshot {x1, y0}, where x0øx1 and y0ø y2. hnms = ra(x0) r1(x0).w1(x1).c1 rb(x1).cb rb(y0) r2(y0).w2(y2).c2 ra(y2).ca Alice executing Ta observes the effect of transaction T2 but not T1. Bob, is executing Tb, observes the effect of T1 but not T2. By using session guarantees, one can easily disallow this anomaly in for a client.
The rationale behind US is that read-only transactions dominate updates in many workloads, and that ensuring consistent snapshots is usually enough for many read-only transactions. US is also extended to aborted transactions called Extended Update Serializability (EUS) by Hansdah and Patnaik [68]. Therefore, aborted transactions should also observe consistent snapshots. In Section 2.2.7, we explain in detail the rationale of reading a consistent snapshot for aborted transactions.
Snapshot Isolation (SI)
Snapshot isolation (SI) introduced by Berenson et al. [22] is one of the most famous consistency criteria supported by many DBMSes (e.g., Oracle [110], PostgreSQL [108], and Microsoft SQL Server [95]). In Snapshot isolation (SI), a transaction reads its own consistent snapshot, and aborts only if it write-conflicts with a previously-committed concurrent transaction. A readonly transactions never conflicts with any other transaction and always commits. Moreover, unlike SSER, SER or US, update transactions abort only if they write-conflict with a concurrent transaction. This allows some transactions to commit while they would have aborted if they were serialized.
Unlike previous consistencies, SI also considers a start point for a transaction. A start point of a transaction Ti (denoted as si) is the first operation invoked by Ti. The start point of a transaction is then used to order the transaction with all other transactions.
Generalized Snapshot Isolation (GSI)
Elnikety et al. [49] generalize SI, under the name Generalized Snapshot Isolation (GSI). GSI distinguishes between a transaction’s start point (i.e., the time of the transaction’s first operation), and an abstract snapshot point. The read rules are then defined with respect to the snapshot points and not start points. Therefore, the start point in Adya’s definition plays the same role as snapshot point in Elnikety’s one, and they are considered equivalent [43].
Parallel Snapshot Isolation (PSI)
With the emergence of new Internet based applications, like social networks, the need for highly scalable yet geographically replicated transactional systems has increased substantially over the past few years. Sovran et al. [136] note that SI requires snapshots to form a total order, which does not scale well. To address this problem, Sovran et al. [136] define Parallel Snapshot Isolation (PSI), a new consistency criterion suitable for geo-replicated systems. It allows the relative commit order of non-conflicting transactions to vary between replicas. Thus, PSI does not totally order transactions’ snapshots. Under PSI, both read-only and update transactions might observe non-monotonic snapshots. Moreover, since PSI is weaker than SI, it also has the write-skew anomaly. Based on the formal model given in [136], a history h guarantees PSI if the following properties hold:
(i) Site Snapshot Read. All read operations should read the most recent committed version at the transaction’s site (i.e., a data center that the transaction starts its execution), and before the time the transaction started.
(ii) No write-write Conflict. No two concurrent write-conflicting transactions both commit.
(iii) Commit Causality Across Sites. Causality between transactions is maintained at all sites.
Causal Serializability (CSER)
Causal serializability (CSER) [109] is very similar to PSI. It ensures the following properties:
• Transactions from the same client are sequential.
• Transactions respect read-from dependency.
• Transactions updating the same objects are observed in the same order by all replicas of those objects. However, unlike PSI, CSER is not a multi-version consistency criterion, and does not require reading committed values. Hence some anomalies defined previously (like non-monotonic snapshots) are not observable with CSER.
Consistency Criteria for Software Transactional Memory
To make concurrent programming easier, and to provide developers with a convenient abstraction, Shavit and Touitou [133] introduce a new method called Software Transactional Memory (STM). With STM, threads of an application synchronize with each other via transactions. Although some STMs ensure conventional consistency criteria (like SER or SI), Guerraoui and Kapalka [63] argue that these criteria are not suitable for STMs because these consistencies are applied only to committing transactions. Thus, they do not preclude a transaction from reading an inconsistent state as long as it later aborts. Behaviors of the transactions that abort are not considered harmful in managed environments (such as databases) since transactions can run in isolation through sandboxing techniques. However, executing a transaction in unmanaged environments is harmful, and can cause a whole application to crash [63, 137]. For instance, an STM transaction that reads an inconsistent state would cause a divide-by-zero exception. For the sake of completeness, in the remainder of this section, we briefly review consistency criteria introduced for STMs.
Opacity: Guerraoui and Kapalka [63] introduce Opacity as the strongest consistency criterion a transactional system can provide. It strengthens SSER by considering also aborting transactions. A transaction system ensures Opacity if: (i) every concurrent execution of committed transactions along with read-prefixes of aborted transactions3 is equivalent to some serial execution, and (ii) this serial execution respects real-time orderings among transactions. Virtual World Consistency (VWC): Opacity requires that all read prefixes of aborted transactions observe exactly the same causal path. Imbs and Raynal [73] argue that it is more conservative than needed. They introduce a weaker consistency criterion called VWC. VWC requires that: (i) all committed transactions be SSER; (ii) every read-prefix of an aborted transaction reads values that are consistent with respect to its causal past.
Genuine Partial Replication (GPR)
Replication improves both locality and availability. In full replication, every replica must perform all updates, therefore it does not scale. Partial replication addresses this problem, by replicating only a subset of the data at each replica. The idea is that if transactions would communicate only over the minimal number of replicas, synchronization and computation overhead would be reduced. However, in the general case, the overlap of transactions cannot be predicted; therefore, many partial replication protocols in fact perform system-wide global consensus [15, 131] or communication [136]. This approach negates the potential advantages of partial replication.To address this issue, Schiper et al. [127] introduce genuine partial replication: a transaction communicates only with the replicas that store some object read or written in the transaction. GPR is also called the minimality property by Fritzke and Ingels [55]. We call the set of replicas storing objects read or written by transaction Ti, the replicas concerned by Ti. With GPR, non-conflicting transactions do not interfere with each other, and the intrinsic parallelism of a workload can be exploited, ensuring that throughput scales linearly with the number of nodes.
Definition 3.1 (Genuine Partial Replication). A transactional system ensures Genuine Partial Replication if, for any transaction Ti, only processes that replicate objects concerned by Ti make steps to execute Ti.
In addition to scalability advantages, GPR also improves availability of a transactional system. Failures of a replica that is not concerned by a transaction does not halt the execution of that transaction. This improves the availability of the system. For instance, consider a banking application, in which accounts of American branches are replicated in the US, and accounts of European branches are stored in the EU. Under GPR, transactions among EU accounts can execute and finish even when EU and US sites are partitioned.
We note that GPR is equivalent to the concept of strictly disjoint access parallelism in an STM. An STM is strictly disjoint-access-parallel when non-conflicting transactions never contend on the same base object, that is on any object in use at the implementation level [64]. In order to have a more fine-grained comparison among transactional protocols that are not GPR, we define two additional properties of interest in what follows:
Definition 3.2 (Committing Replicas). The set of replicas that is involved in commitment of transaction Ti is called the committing replicas of Ti. Some transactional protocols (such as Walter [136]) perform asynchronous propagation to all replicas once a transaction commits. To capture these attributes, we define affected replicas as the set of all replicas that are affected (either by sending or receiving a message) due to execution of a transaction. Note that the set of committing replicas of Ti is always subset of the set of replicas affected by Ti.
Table of contents :
List of Tables
List of Figures
1 Introduction
1.1 Contributions
1.1.1 Part I
1.1.2 Part II
1.2 Outline of the thesis
Part I: Ensuring Consistency in Transactional Data Stores
2 Background
2.1 Model
2.1.1 Objects & transactions
2.1.2 Histories
2.1.3 Distributed System
2.1.3.1 Failure Models
2.1.3.2 Synchrony Assumptions
2.1.3.3 Failure Detectors
2.1.4 Replication
2.1.5 Transactional Commitment
2.1.5.1 Atomic Commitment Approach
2.1.5.2 Total Ordering Approach
2.1.5.3 Partial Ordering Approach
2.2 Strong Consistency Criteria
2.2.1 Strict Serializability (SSER)
2.2.2 Full Serializability (SER)
2.2.3 Update Serializability (US)
2.2.4 Snapshot Isolation (SI)
2.2.4.1 Generalized Snapshot Isolation (GSI)
2.2.5 Parallel Snapshot Isolation (PSI)
2.2.6 Causal Serializability (CSER)
2.2.7 Consistency Criteria for Software Transactional Memory
2.2.8 Anomaly Comparison
2.3 Liveness and Progress
3 Catalog of Transactional Protocols Supporting Partial Replication
3.1 Scalability Properties
3.1.1 Wait-Free Queries (WFQ )
3.1.2 Genuine Partial Replication (GPR )
3.1.3 Minimal Commitment Synchronization
3.1.4 Forward Freshness
3.2 Review of Transactional Protocols Supporting Partial Replication
3.2.1 SSER
3.2.2 SER
3.2.3 US
3.2.4 SI
3.2.5 PSI
4 Scalability of Strong Consistency Criteria
4.1 Decomposing SI
4.1.1 Absence of Cascading Aborts (ACA)
4.1.2 Consistent and Strictly Consistent Snapshots (SCONS)
4.1.3 Snapshot Monotonicity (MON)
4.1.4 Write-Conflict Freedom
4.1.5 The Decomposition
4.2 The impossibility of SI with GPR
4.3 Discussion
4.3.1 SSER and Opacity
4.3.2 SER
4.3.3 PSI
4.3.4 Circumventing The Impossibility Result
4.4 Conclusion
5 NMSI : Non-monotonic Snapshot Isolation
5.1 Definition of NMSI
5.2 Jessy: a Protocol for NMSI
5.2.1 Taking Consistent Snapshots
5.2.2 Transaction Lifetime in Jessy
5.2.3 Execution Protocol
5.2.4 Termination Protocol
5.2.5 Sketch of Proof
5.2.5.1 Safety Properties
5.2.5.2 Scalability Properties
5.3 Ensuring Obstruction-Freedom
5.4 Empirical study
5.4.1 Implementation
5.4.2 Setup and Benchmark
5.4.3 Experimental Results
5.5 Conclusion
6 G-DUR: Generic Deferred Update Replication
6.1 Overview
6.2 Execution
6.2.1 Version Tracking
6.2.2 Picking a Version
6.3 Termination
6.3.1 Group Communication
6.3.2 Two-Phase Commit
6.3.3 Fault-Tolerance
6.4 Realizing Protocols
6.4.1 P-Store
6.4.2 S-DUR
6.4.3 GMU
6.4.4 Serrano07
6.4.5 Walter
6.4.6 Jessy2pc
6.5 Implementation
6.6 Case Study
6.6.1 Setup and Benchmark
6.6.2 Comparing Transactional Protocols
6.6.3 Understanding Bottlenecks
6.6.4 Pluggability Capabilities
6.6.5 Dependability
6.6.5.1 Disaster Prone
6.6.5.2 Disaster Tolerant
6.7 Related Work
6.8 Conclusion
Part II: Ensuring Consistency in Non-Transactional Data Stores
7 Tuba: A Self-Configurable Cloud Storage System
7.1 Introduction
7.2 System Overview
7.2.1 Tuba Features from Pileus
7.2.2 Tuba’s New Features
7.3 Configuration Service (CS)
7.3.1 Constraints
7.3.2 Cost Model
7.3.3 Selection
7.3.4 Operations
7.3.4.1 Adjust the Synchronization Period
7.3.4.2 Add/Remove Secondary Replica
7.3.4.3 Change Primary Replica
7.3.4.4 Add Primary Replica
7.3.4.5 Summary
7.4 Client Execution Modes
7.5 Implementation
7.5.1 Communication
7.5.2 Client Operations
7.5.2.1 Read Operation
7.5.2.2 Single-primary Write Operation
7.5.2.3 Multi-primary Write Operation
7.5.3 CS Reconfiguration Operations
7.5.4 Fault-Tolerance
7.6 Evaluation
7.6.1 Setup and Benchmark
7.6.2 Macroscopic View
7.6.3 Microscopic View
7.6.4 Fast Mode vs. Slow Mode
7.6.5 Scalability of the CS
7.7 Related Work
7.8 Conclusion
8 Conclusion
8.1 Future Work
Part III: Appendix
A Proof of SI Decomposition
B Correctness of Jessy
B.1 Safety
B.2 Liveness and Progress
C Résumé de la thèse
C.1 Résumé
C.2 Introduction
C.2.1 Contributions
C.2.1.1 Partie I
C.2.1.2 Partie II
C.3 Passage à l’échelle du Critère de Cohérence Forte
C.3.1 Décomposition SI
C.3.1.1 Annulation en cascade (Absence of Cascading Aborts)
C.3.1.2 Instantanés cohérents et strictement cohérents
C.3.1.3 Instantané monotone
C.3.2 Write-Conflict Freedom
C.3.3 La décomposition
C.3.4 L’impossibilité de SI avec GPR
C.4 Non-monotonic Snapshot Isolation
C.5 Generic Deferred Update Replication
C.6 Un Système de Stockage Cloud Auto-Configurable
Bibliography
