Multi-shard transaction
- A transaction is a group of simple operations that take effect atomically.
- A transaction as a whole (a big logical operation) must satisfy the consistency requirement of the system.
A transaction can be a one-shot or multi-shot
- One-shot: you already know all the keys/shards you need before the start, so you can fire one round of requests.
- Multi-shot: the data to read/write in later shots depend on values read in earilier shots
A general transaction contains reads and writes.
- Transactions also can be
- Read-only transaction: only contains reads and don’t modify system state
- Write-only transaction: only contains writes
Transaction examples
- Back account transfer
- Deposit and withdraw
- Maintaining symmetric relationships
- If A is a friend with B, B is a friend with A
- Order product
- Charge customer
- Decrement stock
- Ship stock
Transaction atomic commit
- Atomic commit: either all participants do something (commit) or no participant does nothing (abort)
- Replication (e.g., Raft) is about doing the same thing across datacenters to provide fault tolerance.
- Sharding is about doing different things at multiple servers in a datacenter for scalability.
- Atomic commit is about doing different things at multiple servers together.
- It concerns with multiple operations across different shards.
- Atomic commit is accomplished with Two-phase commit protocol.
Two-phase commit (2PC) ensures atomicity
Two-phase commit ensures atomicity for a single transaction that involves multiple shards.
If a transaction succeeds, all shards agree on the effect, otherwise they all abort.
Phase 1
- Coordinator sends “Prepare?” requests to all participants, inclduing itself.
- Each participant responses yes or no
- A participant voting YES must prepare itself (e.g., by locking the data) so that it will later be able to honor the commit decision
- The coordinator then examines the responses and makes the final decision:
- all Yes -> Commit
- any No -> Abort
Phase 2
- Coordinator broadcasts Commit or Abort to all participants
- If commit, the coordinator sends response to the client
- If commit, participants update their transaction state accordingly, release resources such as locks, and acknowledge the coordinator
- Otherwise, they all abort
Common reasons to abort
- Cannot acquire required lock
- Lacking memory or disk space for write
- Transaction constraint fails (e.g., Balance is not enough)
Atomicity is not enough for two concurrent transactions
Even if every transaction commits atomically, multiple transactions executing concurrently can still observe inconsistent combinations of values.
For example, suppose a transaction:
sum(A, B):
a = read(A)
b = read(B)
print(a + b)
and:
transfer(A, B):
a = read(A)
if a < 10:
abort
write(A, a - 10)
b = read(B)
write(B, b + 10)
Imagine sum executes in the middle:
transfer: read(A)
transfer: A -= 10
sum: read(A) ← sees A after deduction
sum: read(B) ← sees B before addition
transfer: B += 10
Then, the sum transaction sees a database state that never logically existed as a complete state.
Therefore, ensuring atomicity is not enough for handling concurrent transactions.
This problem leads to Serializability to determine a consistent result of multiple transactions.
Isolation Between Transactions & Schedule
Before discussing serializability, we first need to understand the underlying concepts of isolation and schedule for concurrent transactions:
- Isolation: One transaction appears to happen either completely before or completely after the other transaction.
- This also explains serializability.
- Schedule: a schedule is simply the ordering of operations from concurrent transactions.
- Given a schedule of operations, we ask:
Is that schedule in some way "equivalent" to a serial execution of transactions?
If a schedule is equivalent to a serial schedule, we call the schedule is serializable.
Serializability
A serial schedule means transactions literally run one at a time as if sequentially:
T1 completely
T2 completely
T3 completely
A concurrent schedule is serializable only if its result is equivalent to the result of some serial schedule.
Strict serializability
Serializability requires equivalence to some serial transaction ordering, but does not impose real-time ordering.
Suppose:
real time:
T1 finishes
T2 starts
Then, plain serializability could theoretically choose:
T2 -> T1
Strict serializability adds that real-time requirement. Therefore, it requires:
T1 -> T2
Thus:
Strict serializability = Serializability + real-time ordering
Conflicting operations helps us determine serializable schedule
Now that we understand isolation, schedule, and serializability, we need to know the concept of conflicting operations to help us determine which schedule is serializable.
First, we define conflicting operations:
- Two operations from different transactions are conflicitng if:
- They read and write to the same data item, or
- They write and write to the same data item
Here, “conflicting operations” itself is not a problem and in fact is normal in any interesting transactions.
It merely indicates those operations that matter as swapping the order of such can cause an inconsistent result of transactions.
More details in 12-1-More on Distributed Transactions and Concurrency Control > Serializability of schedules
Serializable schedule example
For example, suppose:
transfer: rA wA ------- rB wB C
sum: rA ---------------- rB C
For data item A, there is a conflict:
transfer wA -> sum rA
which says:
transfer -> sum
For B:
transfer wB -> sum rB
which also says:
transfer -> sum
Now both conflicts agree:
A says: transfer -> sum
B says: transfer -> sum
Then, this result is equivalent to that of some serial schedule such as:
transfer: rA wA rB wB C
sum: rA rB C
The serial schedule shows sum that comes after transfer which indicates:
A says: transfer -> sum
B says: transfer -> sum
Therefore, the interleaved execution is equivalent to the serial order:
transfer -> sum
Non-serializable schedule example
Suppose:
transfer: rA wA ------- rB wB C
sum: rA rB C
For A, there is a conflict:
transfer wA -> sum rA
which says:
transfer -> sum
For B:
sum rB -> transfer wB
which in contrast says:
sum -> transfer
Now both conflicts disagree:
A says: transfer -> sum
B says: sum -> transfer
Therefore, the interleaved execution is not equivalent to any serial order, so it is non-serializable.
Conclusion
As shown above, analyzing conflicting operations help us determine which schedule is serializable.
With this notion, we intend to enforce orderings of operations to follow some serializable schedule to ensure consistency for concurrent transactions through a technique known as Concurrency Control and algorithm known as Two-phase locking (2PL).
Concurrency Control
- Concurrent execution can violate serializability.
- Therefore, we need to control concurrent execution to enforce concurrent execution that satisfies serializability.
- This concurrency control can be accomplished by Two-phase locking (2PL)
Two-phase locking (2PL) enforces serializability
Locking
-
Locks are maintained on each shard
- Transaction requests lock for a data item
- Shard grants or denies lock
- When denied, the operation can wait
-
Lock types
- Shared: Need to have before read object
- Exclusive: Need to have before write object
Lock compatibility
| Shared (S) | Exclusive (X) | |
|---|---|---|
| Shared (S) | Y | N |
| Exclusive (X) | N | N |
| Shared locks are compatible since read doesn’t change any state. | ||
| However, execlusive locks aren’t compatible with any other lock since it changes state. Thus, we need to protect data item being changed with lock. |
Lock Manager
Every operation in transaction consults lock manager to acquire lock:
Transaction
│
▼
"Can I lock X?"
│
▼
┌───────────────┐
│ Lock Manager │
└───────────────┘
│ │
compatible incompatible
│ │
▼ ▼
proceed WAIT
Naive use of locks don’t enforce serializability
Above transactions grab locks independently for each data item, which permits the non-serializable interleaving.
Two-phase locking details
-
2PL Rule: Once a transaction has released a lock, it is not allowed to ontain any other locks
- Growing phase: transaction acquires locks
- Shrinking phase: transaction releases locks
-
In practice:
- Growing phase spans the entire transaction
- Shrinking phase is done during commit
- 2PL following such patterns is called strict 2PL
2PL Provides Strict Serializability
This section presents examples of how 2PL enforces serializability, using two-phase locking algorithm, based on the observation made for which schedule is serializable.
For example, 2PL prevents this kind of non-serializable interleaving:
Instead, the 2PL algorithm won’t allow sum a shared-lock (A) when it is already acquired by transfer for write and enforce sum to wait, blocking the transaction.
Meanwhile, transfer will continue and eventually finish its operations and release the locks.
Once the locks are released, sum operations will be allowed to continue.
Another exmaple 2PL algorithm may enforce the ordering to be is:
2PL doesn’t exploit all opportunities for concurrency
Although below schedule is serializable, 2PL won’t utilize such an order since it can’t be done under 2PL mechanism:
Instead, it will follow a pattern like:
transfer: rA wA rB wB C
sum: rA rB C
Issues with 2PL
Waiting for a lock can result in deadlock.
Suppose:
transfer1: rA wA ------ rB wB C
transfer2: rB wB ------ rA wA C
Under 2PL algorithm, the first read and write of each transfer will be granted locks.
Then, the second read and write of transfer1 is blocked since item B is locked by transfer2.
Thus, transfer2 proceeds, but soon will also be blocked for attempting to acquire lock for item A which is still occupied by transfer1.
Therefore, this ends up in deadlock.
We need ways to detect and deal with situations like this.
More deadlock details in 12-1-More on Distributed Transactions and Concurrency Control > Deadlock Example
More Control Concurrency Algorithms
- 12-1-More on Distributed Transactions and Concurrency Control > Optimistic concurrency control
- Multi-Version Concurrency Control (MVCC)
Conclusion
In conclusion, distributed concurrency control is achieved via combination of 2PC and 2PL.
This usage of mere 2PC and 2PL mechanisms explained here to ensure serializability is now obsolete, but remains as foundational base and idea of Spanner which optimizes read-only transactions, as shown in 13-1-Spanner Continued > Three different mechanisms