1 of 56

Lab 4 Part 3: Transactions

CSE 452 Fall 2024

Last “Content” Section of the Quarter! ╰(*°▽°*)╯

Distributed Systems in a nutshell

2 of 56

So, how do we finish this quarter?

Lab 4 Part 2 design doc is due Friday (February 28th)
Lab 4 Part 1 and Problem Set 6 due next Tuesday (March 4th)
Lab 4 Part 2 code is due March 11th (just under 2 weeks)
Problem Set 7 due March 14th (last day of dead week)
Lab 4 Part 3, as well as everything lingering, is due March 19th (Wed finals week)– last day to submit anything for this class

3 of 56

Goal of Lab 4 Part 3

Support transactions across multiple keys potentially located across different replica groups

Transactions can be:

Series of reads
Series of writes
Swaps - new one :)

Use Two-Phase Locking to acquire locks during transaction.
Why can’t we just use Paxos? Because each group is responsible for a different set of shards and we want to support transactions across shards/replica groups.

4 of 56

The number of design decisions on this lab is astronomical - we can’t possibly hope to cover every design issue you can run into, but here are some of the more important points.

5 of 56

The Good News

Two-phase commit is relatively uncomplicated on its own - compared to Paxos it is much easier to understand!
We’re just introducing 2PC on top of Paxos to handle some new operations
The lab is worth less points than previous labs - only 190, compared to 355 (Lab 3) and 260 (Lab 4 Part 2), plus the additional 45 (Lab 4 Part 1)

6 of 56

The Bad News

Deadlock, deadlock, deadlock. System can get stuck, and it can be hard to debug! (lots of possible design pitfalls)
Search tests explode easily because of the enormous amount of messages
Cumulative nature of the lab - Lab 4 Part 3 relies heavily on Lab 3 (Paxos), Lab 4 Part 1 (Shard Controller), and Lab 4 Part 2 (Sharding and Reconfiguration) - bugs in older labs may show up

7 of 56

Two-phase Commit refresher

Keys partitioned over different hosts
Many groups involved with transactions
One coordinator per transaction

Note that you can be a coordinator for one transaction and participant for another - this should not deadlock!

Acquire locks on all data read/written; release after commit

8 of 56

Lab 4 Part 3: Hints

All ShardStoreServer nodes tag their transaction-handling messages with their configuration number.

Servers reject any prepare requests coming from different configurations, causing the transaction to abort.

Servers delay reconfigurations when there are outstanding locks for keys (i.e., there are transactions pending in the previous configuration).

9 of 56

Transactions

interface Transaction extends KVStoreCommand {

Set<String> readSet();

Set<String> writeSet();

Set<String> keySet(); // union of readSet and writeSet

KVStoreResult run(Map<String, String> db);

}

Implementations of Transaction

MultiGet : Read one or more keys across replica groups

Set<String> keys

MultiPut : Write one or more keys across replica groups

Map<String, String> values

Swap : Given two keys, swap their values

String key1, key2

Your goal: implement support for these 3 types of Transactions

10 of 56

Operations

MultiGet(set of keys): Get values for list of keys -> MultiGetResult(set of key-value pairs)

MultiPut(map of (key, value)): Put corresponding value into each key -> MultiPutOK

Swap(foo, bar): Swap old value of foo so it is new value of bar, and vice versa -> SwapOK

11 of 56

Two-Phase Commit (100m)

What if we treat these commands down into a series of Gets and Puts?

Identify all replica groups involved in transaction

Highest group ID can be coordinator

Prepare Phase

Acquire read-write locks (all); abort if any lock can’t be acquired (wound-wait)
Retrieve values of keys if you need them

Commit Phase

Put values of keys if you need to
Finish transaction and release locks (all)

Note that you can combine 2+3, and 4+5.

12 of 56

Roles for groups

What are the two roles a group can have and how they related to 2PC?

Groups can have two roles: participant and coordinator.

Coordinator initiates the prepare and commit phases
Participants respond with acks/oks

13 of 56

Two-Phase Commit (10,000m)

In the Prepare Phase the coordinator gathers information about the state of the keys in the transaction.

In the Commit Phase the coordinator tells everyone what to update their state to

14 of 56

Two-Phase Commit (One Approach)

There are many ways to do two-phase commit. We will talk about one!

The code for this part of the lab can become complex; it is nice if you can handle MultiGet, MultiPut, and Swap the same way…

What if we treat each command as a series of Gets and Puts?

15 of 56

R2

R1

R3

R{1,2,3} are replica groups. Each is a set of ShardStoreServers, each with a Paxos subnode.

Client

keys={a}

keys={b,c}

keys={d,e}

State: {b:x}

State: {d:y}

16 of 56

R2

R1

R3

Client

keys={a}

keys={b,c}

keys={d,e}

Swap(keys={b,d})

Client sends a request to the Coordinator. Coordinator is the max({replica group ids involved in this transaction}). In this case, R3 (for key=d) and R2 (key=b) are involved, max(3,2) = 3. So replica group 3 is coordinator.

State: {b:x}

State: {d:y}

Step 1

Client identify all participating groups, and talk to coordinator (highest ID).
Incoming messages are first replicated like in part 2.

17 of 56

R2

R1

R3

Client

keys={a}

keys={b,c}

keys={d,e}

Coordinator sends Prepare messages to all participants in the transaction. Participant should lock keys involved in transaction.

Prepare(command=MultiGet(keys={b,d})

State: {b:x}

State: {d:y}

Step 2 (Prepare Phase)

Coordinator sends out prepares with gets to all replica groups involved in transaction.

18 of 56

R2

R1

R3

Client

keys={a}

keys={b,c}

keys={d,e}

State: {b:x}

State: {d:y}

Step 3 (Prepare Phase)

Coordinator sends out prepares with gets to all replica groups involved in transaction.
Upon validating, prepare participants check if key locked

If locked -> abort
Else -> lock & PrepareOk

Each replica group responds with PrepareOK �(including the information on what it’s responding to and current state of the keys it has for that transaction)

PrepareOK(MultiGetResult(b: x))

PrepareOK(MultiGetResult(d: y))

19 of 56

R2

R1

R3

Client

keys={a}

keys={b,c}

keys={d,e}

Coordinator combines info from PrepareOk’s and runs transaction on the state

(performing a swap in this case)

Phase 1 results:

{b:x} + {d:y} = {b:x, d:y}

Result after transaction:

{b:y, d:x}

State: {b:x}

State: {d:y}

Step 3.5

Execute intermediate transaction logic if applicable. (process swap)

20 of 56

R2

R1

R3

Client

keys={a}

keys={b,c}

keys={d,e}

Coordinator sends Commit to Participants with what values should be in the keys.

Participants update only the keys they’re responsible for.

Commit(MultiPut({b:y, d:x})

Result after transaction:

{b:y, d:x}

Step 4

Upon receiving PrepareOk from ALL participants, coordinator sends out commit with puts to all participants

State: {b:y}

State: {d:x}

21 of 56

R2

R1

R3

Client

keys={a}

keys={b,c}

keys={d,e}

Result after transaction:

{b:y, d:x}

Step 5

Upon receiving Commit, participants perform write, unlock locks, and reply back to coordinator

CommitOK()

State: {d:x}

State: {b:y}

22 of 56

R2

R1

R3

Client

keys={a}

keys={b,c}

keys={d,e}

Coordinator responds with appropriate response

Reply(SwapOk)

State: {b:x}

State: {d:y}

Step 6

Coordinator replies back to the client once ALL CommitOk are received and results are combined.

23 of 56

Transaction Success and Failure

How are transaction success or failure indicated for all servers?
Transactions will either end in a COMMIT if they are successful, or an ABORT if they failed

In either case, all servers that sent a PrepareOk back to the coordinator MUST respond to a commit or abort message from that coordinator with a CommitAck or an AbortAck, depending on what the coordinator sent
In other words, if you accept a coordinator’s prepare request, you are agreeing to do whatever that coordinator tells you to do!

24 of 56

Transaction Failures

One of the participant’s transaction keys is already locked
There’s a shard move in progress, and key is no longer at that group
Participant can PaxosReplicate a PrepareNotOK, reply abort

25 of 56

Preserving Transaction Atomicity within Configurations

How is Transaction atomicity maintained within Configurations?

All this is in the spec:

All ShardStoreServer nodes tag their transaction-handling messages with their configuration number.
Servers reject any prepare requests coming from different configurations, causing the transaction to abort.
Servers delay reconfigurations when there are outstanding locks for keys (i.e., there are transactions pending in the previous configuration).

26 of 56

Two-Phase Commit (One Approach)

Goal: Allows all participants to arrive at same conclusion.

Pick a coordinator (i.e leader of the transaction)
Coordinator sends out prepares to all replica groups (participants) responsible for a given key and participants do Gets
Participants check if any key involved in the transaction is locked

If any key is locked, reply with PrepareNotOk
Otherwise, reply PrepareOK (with Get values) and lock the key to prevent reads and writes on it

If Coordinator received PrepareOKs from all groups, send out Commits with Puts
If commit, participants perform write, unlock keys, and reply back to coordinator
Coordinator replies back to the client once all CommitOks are received and Results are combined

27 of 56

Important Design Tips

Groups can have two roles: participant and coordinator.
Remember to handle case where coordinator is also a participant

Send your group a message (can blow up search state) OR
Act as if your group received a message

Need to track multiple ongoing (active) transactions at each leader/group
Recall each handler must run to completion - think about what the state of the node looks like after handlers run, and don’t leave your server in a stuck/deadlocked state

28 of 56

Transactions and Configurations

Should transactions happen atomically in one configuration, or are they allowed to span multiple configurations?

Ensure transactions stay within one configuration - you need to do some special handling for this (more on next slide)
Allow transactions to happen across multiple configurations - you COULD do this, but we (and the spec) STRONGLY recommend you don’t try this - it can be much harder and there’s tons of edge cases.

Feel free to ask how this might be accomplished if you’re curious - there are no slides on this

29 of 56

The Messy Cases

Coordinator receives a new configuration that moves one of the keys in the txn

Coordinator and participants aren’t in same configuration

Any committed transaction must complete before applying new config
Any in progress transaction (in prepare phase) can be aborted, client will retry

There’s a shard move in progress, and key is no longer at that group
Participant can PaxosReplicate a PrepareNotOK, reply abort

30 of 56

The Messy Cases

Transactions probably need an attempt / retry #

When transaction is retried, the coordinator needs to reach out *again* to all participants as part of a new attempt (not just resend of previous message)
Attempt # so participants can tell different transaction attempts apart
Attempt may have different configurations - diff coordinator, participants

31 of 56

Safe to ignore messages with outdated config???

R2

R1

R3

keys={a} config = 2

keys={b,c}

Config = 3

keys={d,e}

R3 in reconfig, receives a Prepare Request from R1

State: {b:x}

State: {d:y}

Prepare, config = 2

keys={a} config = 3

PrepareNotOk, config = 3

32 of 56

Deadlocked? Abort!

Release the locks and try again!
Pros:

Feasible because it’s easy to cancel a prepared transaction

Rollback unnecessary because KVStore not modified

If nothing is locked, efficient: can send all prepares at same time

Cons:

Progress is not guaranteed; retry may collide (unlikely but possible - probably not the biggest issue for you in this lab)
Need to know that all groups hear Abort

Group may receive a Prepare without you hearing PrepareOk

33 of 56

The Danger Zone - Pitfalls

When designing, make sure to think about adversarial cases
Make sure old messages (from previously terminated transactions, as one example) can’t interfere with the current state of the system!
Be careful about ignoring messages - think about if it’s possible for any clusters to get stuck in deadlock scenarios
How do you protect against new configurations showing up and potentially messing everything up?
How do you make sure transactions don’t interfere with each other? A group could be a participant AND a coordinator at the same time

34 of 56

Tips

Groups can be in two roles: participant and coordinator. May need to handle sending messages to your own group (i.e. if a given group is both a participant and coordinator).

Similar to how in Paxos, nodes can be both acceptors/proposers.

Keep track of ongoing (active) transactions at each node �(each transaction could keep track of a set of keys that are currently locked)
What happens if coordinator receives an abort?

It may be the case that coordinator config is out of sync

Participants may reject prepare from coordinator (e.g., if key is already locked)

If coordinator learns of a new config while receiving prepare responses, the coordinator should finish any outstanding transactions, send out aborts as a response to other transactions if needed and process the config change. Then client will retry and will start a new transaction.
This means each transaction should have an attempt / retry # associated with it. If a transaction needs to be retried, the coordinator needs to reach out to all participants again as part of a new attempt #. Attempt # needed so participants can differentiate different transaction attempts from a given coordinator. Needs to deal with attempts from different configs.

35 of 56

Coordinator-as-a-Leader Designs

Coordinator should essentially “lead” a transaction
Invariants:

The coordinator is the FIRST to lock down on a transaction (other groups ignore if they realize they won’t be the coordinator for the group)
The coordinator is the LAST to terminate in a transaction (only after hearing back from everyone else, whether those are commits or aborts, does the coordinator declare that the transaction is done)

36 of 56

Deadlock or cyclic waiting: the problem

Recall: deadlock across threads/processes (332, 451)

Thread/Process A holds resource X, waiting for resource Y
Thread/Process B holds resource Y, waiting for resource X

This can happen in 2PC.

G1

G2

G3

G4

keys={k1}

keys={k2}

keys={k3}

keys={k4}

Write(k4, k2, k1)

Write(k3, k2, k1)

References from 332: https://courses.cs.washington.edu/courses/cse332/22sp/lectures/lecture20/Lecture20.pdf, section 9 of https://homes.cs.washington.edu/~djg/teachingMaterials/spac/sophomoricParallelismAndConcurrency.pdf.

References from 451: https://courses.cs.washington.edu/courses/cse451/22sp/lectures/09.5-synch-review.pdf, “deadlock”, see the dining lawyers problem

We don’t need to think about shard movement. Most of the complexity here can be found even without thinking of shard movement.

In the example, the color of the key corresponds to the transaction for which it locked the key.

G4 is waiting for key k1 from G1; that key is locked because of the transaction coordinated by G3.
G3 is waiting for the key k2 from G2; that key is locked because of the transaction coordinated by G4.

37 of 56

Deadlock solution: abort (the 2PC way)

Release the locks and try again!

Aborts are sent from G4 to G1, from G3 to G2
G3 tells G2 and G4 tells G1 to unlock and not perform the operation
Try to acquire the locks again

Pros:

Feasible because it’s easy to cancel a prepared transaction

Rollback unnecessary because KVStore not modified

If nothing is locked, efficient: can send all prepares at same time

Cons:

Progress is not guaranteed; retry may collide (unlikely but possible)
Need to know that all groups hear Abort

Group may receive a Prepare without you hearing PrepareOk

38 of 56

Deadlock solution: lock ordering (the 332 and 451 way)

Avoid cyclic waiting altogether

Prepare groups in decreasing order of group id.
Coordinator who has prepared the lowest ID will eventually commit/abort*

Pros:

Non-coordinator participants never abort

Coordinator can defer coordination if they can’t lock a required key
Each attempt is uniquely identifiable by configNum of coordinator

Can avoid a separate attempt/retry num – less bookkeeping

Assuming the config stabilizes, progress will be made

“stabilizes” means everyone hears about view and moves complete

Cons:

In the happy path, need several more RTTs (cannot send at same time).

Possibly efficient enough for lab 4.3, but recommended to avoid this.
Sending commits/aborts can be done all at once.

*you will still need to abort because it’s possible that you’re coordinating in a config numbered j but you later hear about config j+1 – the group you are currently sending to may not be sending PrepareOk because they no longer own the relevant shard, so in that case, you should abort.

This way is suggested in 332 because you don’t need to rollback (there are probably other reasons but this is one of them). You may be doing some work that you can’t easily undo; if you release the locks and try again, you would need to undo the changes. Here, there’s nothing to undo, so that’s not an advantage for this approach – but the slides explain why you might consider doing this.

This fixes the deadlock example shown earlier because it’s not possible for G3 to have locked G1 before G2. It would first lock G2, then lock G1. In that example, G1’s key k1 would not be locked, so G4 can finish its transaction; then G3 finishes its transaction once G4 finishes committing.

RTT -> round trip time

39 of 56

Aborts

Make sure that the aborts you receive are valid �(right transaction, config, and attempt number)

Valid aborts from the coordinator should unlock the locks

Safe to send aborts as long as you haven’t sent a prepare_ok for the current attempt
Coordinator should accept AbortOks to end the transaction attempt
Cases when aborts can happen:

Coordinator sends prepare for a transaction but key is locked on participant

Replicate abort on Paxos subnodes, send back Abort to coordinator
Coordinator should end up trying again with a new round of prepares

Participant has higher config number than coordinator’s config number

What should happen when the participant is in the middle of a reconfiguration?

40 of 56

Potential workflow for part 3

Tackling the entire two-phase commit process at once can be difficult, so one suggestion of what order to get things done is

Transactions that are all on one shard (no 2PC), as well as transactions that span shards within one group (no 2PC). [Should pass test 1 for part 3]

Depending on how you implement this, can get 105/190 points!

2-phase commit to everyone (involved), coordinator logic, transaction attempts:

Sending Prepares and locking keys, PrepareOks
Commits and CommitOks
Sending Aborts for different configuration, already locked keys, processing AbortOks
Retry transaction if necessary/possible
Adding logic for interaction with reconfigurations

Note: Sending to everyone (involved) would require getting AbortOks from everyone (involved) if an abort happens

Note: 3. is the bulk of the work because you need these messages and also timers to retry as necessary (for Prepares, Commits, Aborts) [can delay timers until unreliable tests]

41 of 56

What are the two roles a group can have in the 2PC protocol?

42 of 56

What are the two roles a group can have in the 2PC protocol?

Coordinator or Participant

43 of 56

How does each type of server learn that a transaction succeeded/failed?

44 of 56

How does each type of server learn that a transaction succeeded/failed?

Leader knows success if prepareOK from all participants

Any prepareNotOK means transaction failed

Participants know transaction failed if they replied prepareNotOK

Otherwise, participants wait for phase 2, leader tells them

45 of 56

What should the coordinator and participants do in the case of a failed transaction?

46 of 56

What should the coordinator and participants do in the case of a failed transaction?

Coordinator needs to notify participants
Participants need to unlock keys

47 of 56

Should transactions happen entirely in one configuration, or are they allowed to span multiple configurations?

48 of 56

Should transactions happen entirely in one configuration, or are they allowed to span multiple configurations?

One configuration!

49 of 56

How do we ensure a transaction completes entirely in one configuration?

50 of 56

How do we ensure a transaction completes entirely in one configuration?

Participants reject prepare requests from other configurations

51 of 56

What should the coordinator do when it receives a new configuration during a transaction?

52 of 56

What should the coordinator do when it receives a new configuration during a transaction?

Delay reconfiguration until outstanding transactions are completed

53 of 56

What should the coordinator do when it discovers a participant isn’t in the same configuration?

54 of 56

How can we differentiate the same transaction occurring across multiple configurations? (transactions may need to be retried if we terminate it due to configuration mismatch).

55 of 56

Suppose we are a participant that just underwent reconfiguration, can we safely ignore transaction messages from an outdated configuration?

56 of 56

Suppose we are a participant that just underwent reconfiguration, can we safely ignore transaction messages from an outdated configuration?

No, should reply prepareNotOK–this transaction may be blocking coordinator’s reconfiguration