Transactions And Concurrency Control

Front 1

Three important atomicity requirements

Back 1

1) Execution of a collection of ops is all or none
2) Interleaved executions appear to be indivisible
3) Update of a replicated object is atomic

Front 2

Atomicity

Back 2

Property in which actions completely occur, or do not occur at all

Front 3

Durability

Back 3

A committed transaction is permanent

Front 4

Two phase commit protocol

Back 4

A protocol that achieves all or none atomicity.

Front 5

Transaction manager

Back 5

Manages client transactions by making requests to the scheduler. Each client may have its own transaction manager. This allows separation of the transaction code from the client code.

Front 6

Scheduler

Back 6

Manages a concurrency control protocol. The protocol is either to prevent (locks), avoid (2PL with timestamps), or validate (optimistic concurrency control) transactions for consistency.

Front 7

Two synchronization points in 2PC protocol

Back 7

Pre-commit and commit

Front 8

In 2pc, what records the status of a transaction if a failure occurs?

Back 8

the activity log

Front 9

In 2pc, who initiates voting?

Back 9

The coordinator

Front 10

How is the activity log used?

Back 10

Activity log is replayed to recover after a failure, either to redo committed transactions or undo uncommitted transactions.

Front 11

4 Steps of a 2pc from the coordinator perspective

Back 11

Pre-commit
1) Write the precommit record into the activity log (tells the previous status if a failure occurs)
2) Multicast a vote request to all participants.
3) Participants receive the request, flush updates to the activity log, and respond. If the precommit test is positive, participants send a YES to the coordinator (or NO if failure).

Commit
4) If coordinator collects all YESs within the timeout, it commits the transaction by writing a commit to the activity log, releases the transactions resources, and sends a COMMIT to all participants.
Otherwise, the coordinator aborts the transaction and sends an ABORT to all participants.

Front 12

Serializability

Back 12

A series of interleaved actions are equivalent to that of a sequence of actions.

Front 13

Basic idea of Locking, and 2PL for transactions

Back 13

In locking, shared objects are locked before they can be accessed, and released before the end of a transaction. In 2PL a new lock cannot be acquired after the release of a lock.

Front 14

What are the two phases of 2PL?

Back 14

A growing phase, and a shrinking phase.

Front 15

How is 2PL related to 2PC?

Back 15

2PL extends the idea of 2PC into transactions with multiple shared resources.

Front 16

What is the potential for deadlocks in 2PL?

Back 16

When one resource is locked, and waiting for another resource. There could be someone else holding the other resource, waiting for a taken resource.

Front 17

Why not release locks in 2PL as soon as we are done with that resource?

Back 17

It could cause rolling aborts if something goes wrong after the first release.

Front 18

What is strict 2PL?

What does it prevent?

Back 18

In strict 2PL a transaction only releases its locks at commit or abort.

It prevents rolling aborts and simplifies the implementation.

Front 19

Two ways to deal with deadlock in 2PL

Back 19

1. Timestamp ordering: Each transaction receives a unique timestamp, older transactions then get priority over younger transactions to resolve conflicts.
2. Resource ordering. Resources are always acquired in some fixed order.

Front 20

What kind of concurrency control approach is basic 2PL?

Back 20

Pessimistic, we don't execute unless we get all the locks. Requires a lot of communication, but guarantees serialization.

Front 21

Describe an optimistic concurrency control approach

Back 21

With basic 2PL or just timestamp ordering, we only execute when all locks are acquired. To be more optimistic, we could assume we will get all the locks, then validate at the end. If one didn't acquire all the locks exclusively, just abort and try again. This could be done using a 2PC protocol.

Front 22

What are the three stages of optimistic concurrency control?

Back 22

1) Execution: create a local space, get a copy of all resources, and compute.
2) Validation: check if there was overlap for the used resources.
3) Update: If valid, send out the update to other processes.

Front 23

2 basic election types:

Back 23

1) extrema finding: based on a global priority
2) preference-based: based on voting by locality, reliability estimation, etc.

Front 24

What is the difference between leader election and mutual exclusion?

Back 24

In elections, a process may yield to other processes as long as someone succeeds. Whereas in mutual exclusion a process competes until it succeeds.

Front 25

Describe a complete topology

Back 25

Each process in a group can reach any other process.

Front 26

Describe the bully algorithm

Back 26

An extrema-finding election algorithm. Each process has a global priority, and the process with the highest priority is elected.

Front 27

Describe a logical ring election

Back 27

One process initiates a vote, then passes a token with his priority, each later process adds their priority and id, and when the originating process gets the token back, the one with the highest priority is elected.

Front 28

Describe a tree topology election

Back 28

Use a spanning tree as a structure, then broadcast to all nodes through the tree. Needs a minimum spanning tree to be effective.

Front 29

3PC main difference from 2PC

Back 29

Non-blocking. Places an upper bound on the amount of time required before a transaction commits or aborts. Guarantees locks are released after some timeout.

Front 30

3PC disadvantage

Back 30

Networks split into pieces would continue in pieces.

Front 31

3PC Coordinator steps

Back 31

1. Uncertain - receive request, send canCommit?

2. Prepared
If (failure, timeout, or No)
send abort
else //got yes from all
send preCommit

3. Committed
If (fails in prepared)
commit after timeout)
else if (all acks are received)
commit

Front 32

3PC Client/Cohort steps

Back 32

1. Receive canCommit?
If (agree)
send yes
else
send no

2. In prepared
if (abort, fails, or times out)
abort
else
//preCommit received
send ACK
Commit