Assignment

Homework 6 Log-based recovery, distributed concurrency control

1. Recovery: Assuming a redo-only recovery, what should the database do to recover if the

following is the contents of the log upon recovery:

• T1 write X: was 3, now 6

• T2 write Y: was 2, now 0

• T1 commit

• T3 write X: was 6, now 4

• T2 commit

2. Recovery: Assuming a undo-redo recovery, what should the database do to recover if the

following is the contents of the log upon recovery:

• T1 write X: was 3, now 6

• T2 write Y: was 2, now 0

• T1 commit

• Checkpoint

• T3 write X: was 6, now 4

• T2 write Z: was 1, now 5

• T3 commit

3. Suppose we have a MongoDB database with 4 replicas:

• Replica 1 is the primary, the others are secondaries

• Replica 1 writes document A and replicas 2 and 3 get the updated document

• Replica 1 writes document B, but crashes before updating any of the secondaries

• Replica 2 detects that replica 1 has crashed

• How does the system recover?

• What happens to documents A and B?

4. Suppose we have a MongoDB database with 4 replicas:

• Replica 1 is the primary, the others are secondaries

• Replica 1 writes document A and replica 2 gets the updated document

• A partition occurs: replicas 1 and 2 are in one partition, while replicas 3 and 4 are

in the other partition (the 2 partitions now cannot communicate)

• Replicas 1 and 3 detect the partition

• What does the system do?

• Discuss what you think should be done with document A, and why.

5. Suppose we had a distributed database which uses locking where a transaction must lock

all copies to do a write, 1 copy to do a read. If a transaction T1 cannot get a lock because

of a conflicting lock by another transaction T2, then T1 is put on a queue for the lock.

What happens in the following schedule (this is like the 2-phase locking questions). Each

operation is preceded by the transaction issuing the request. Each row should be treated

as happening concurrently on the 3 servers during one time period, so (unrealistically),

the execution is synchronized.

Server 1 Server 2 Server 3

T1:Read(A) T2:Read(A) T3:Read(B)

T1:Write(A) T2:Write(B) T2:Write(B)

T2:Write(B) T1:Write(A) T3:Read(A)

T1:Write(A)

T3:Commit

T2:Commit

T1:Commit