CS 448 - Project 4

Concurrency Control & Recovery

Overview

• Build a program to execute transactions in a concurrent manner
• Utilize a lock-based resource-sharing approach
• Produce logs detailing operations made every step
• Detect deadlocks through a DFS approach on a wait-for graph
• Abort transactions using logs and reverting back changes

Input

• int[] database
• “Database” that the transactions are being performed on
• RecordId = Index in range [0, 9]
• List<String> transactions
• TransactionId = Index
• Process in a round-robin order
• For size 3: 0, 1, 2, 0, 1, …

Operations

• R(recordId) → Read value stored in recordId
• Acquire a shared lock of recordId for transactionId
• W(recordId, value) → Write value to recordId
• Acquire an exclusive lock of recordId for transactionId
• C → Commit a transaction
• Release all locks held by transactionId

Lock Management

• Build helper classes and functions
• Lock
• exclusiveLockId → Records transactionId holding exclusive lock
• sharedLockIds → Records transactionsIds holding a shared lock
• LockManager
• Each recordId contains a lock
• Execute operation given relevant lock is acquired

Lock Management

• getExclusiveLock(transactionId, recordId) → bool
• No other transaction holds exclusive lock
• No other transactions holds shared lock
• Promote shared lock to exclusive
• getSharedLock(transactionId, recordId) → bool
• No transaction holds exclusive lock
• releaseSharedLock(transactionId, recordId) → void
• releaseExclusiveLock(transactionId, recordId) → void

Log Output

• Write Operation (W)
• Timestamp, Transaction ID, Record ID, Old Value, New Value, Current Transaction prior Log Timestamp
• Read Operation (R)
• Timestamp, Transaction ID, Record ID, Value Read, Current Transaction prior Log Timestamp
• Commit (C)
• Timestamp, Transaction ID, Current Transaction prior Log Timestamp

Log Meta-Data

• Timestamp (Int) → Incremented after each operation
• Previous Timestamp (Hash Table, Array, etc.) → Stores previous timestamp a given transaction IDs operation was executed
• Log (String, List<String>, etc.) → Stores the log output generated for each operation
• Helper functions for each operation

Deadlocks

• Execute operations once the relevant lock is acquired
• Skip the transaction if the lock cannot be obtained
• Deadlocks occurs when no transactions can proceed
• Construct a wait-for graph to identify and abort a transaction

Wait-For Graph

• Find recordId lock each transaction is trying to acquire
• Set(exclusiveLock) U Set(sharedLocks) \ Set(transactionId)

Detecting Cycle

• Run DFS on wait–for graph
• Maintain a stack for paths and a boolean array to track visited nodes
• Resource: https://www.geeksforgeeks.org/detect-cycle-in-a-graph/
• Find all cycles in the graph
• Within each cycle, find highest transaction ID
• From all cycles, find highest transaction ID
• This will be the transaction to abort

Abort

• Log Output (A)
• Timestamp, Transaction ID, Current Transaction prior Log Timestamp
• Transaction priority is directly related to transactionId
• Undo the operations performed by the transaction to be aborted
• Utilize the previous timestamps in each log to find prior log
• Read Operation → Do nothing
• Write Operation → Set recordId to old value