New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Unit 6: Concurrency #40
Comments
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Lock-based Concurrency Control and Recovery From Failures
Lesson Introduction: Lock-based Concurrency Control
Database systems are equipped with lock-based protocols to ensure that any transaction to a database cannot read or write data until it acquires an appropriate lock on the transaction. In a big data system where thousands of transactions can be executed simultaneously, it is critical to control the concurrency of transactions.
We will learn about the family of approaches called Lock-Based Concurrency Control. You will learn about the most widely used protocol, the Strict Two-phase Locking, or Strict 2PL.
Topic: Lock-Based Concurrency Control
First, using a dependency graph, we can tell whether a schedule is conflict serializable or not.
Lock based concurrency control
Strict Two-phase Locking (Strict 2PL) Protocol
To be more clear, before reading a transaction A, R(A), it needs to acquire shared lock, S(A). Whenever a transaction wants to write a data item W(A), it needs to acquire exclusive lock X(A).
It calls Two-phase because the transaction goes to two main phases.
There is a separate module in the database system called lock manager, it controls all the locking going up, all the transactions, or the concurrency control module in the database system has to call the lock manager to acquire locks. So the lock manager basically receives locks and releases all locks as well.
Simple rule:
As we can see. Shared on Shared is allowed, otherwise, not allowed
We have to wait for the transaction to release the lock first if it has an exclusive lock in order to acquire a shared or exclusive lock on it.
And if we want to have an exclusive lock, we have to wait for a shared lock also to be released.
Deadlock
A deadlock means that one transaction wants to acquire a lock on a data item A, and this data item A is already locked by another transaction B. At the same time, this other transaction B also wants to acquire a lock on a data item A that is already also locked by transaction B. They both waiting for each other, and it leads to a deadlock because nobody will release the lock until the other one does.
Deadlock Detection
Ti => Tj
To detect deadlock, we periodically check for cycles in the graph. if there is a cycle, it means we have a deadlock and we have to break the cycle by aborting one of the transactions that are causing the cycle
No deadlocks because of no cycle ⬆️
deadlocks because of cycle ⬆️
Topic: Database Recovery
As we already know from the previous unit, a transaction is a collection of actions that make consistent transformations of system states while preserving system consistency. There might be temporarily in an inconsistent state during execution in the middle, but that is fine. As long as the beginning and the end of the transaction are consistent states.
If we have a deadlock, for example, we may need to abort the transaction that causes the deadlock.
However, aborting a transaction is a failure.
Type of Failures:
Local Recovery Management - Architecture
Main memory is smaller than the persistent storage so you have to select a few pages that we can actually store in the buffer. When computers shut down, all data in RAM is wiped out.
That is why we have a Recovery manager
Recovering From a Crash
This way, we ensure that we recover from failure. Transactions that are committed, are redone again, we are fine. For transactions that did not commit before the crash, they don't have a commit record in the log, undo them, and run them again later
Knowledge Check: Lock-Based Concurrency Control
(This is the type of lock a transaction needs to acquire in order to read from a database)
(This is the type of lock a transaction needs to acquire in order to write to a database.)
(Lock-based concurrency control is managed by a specific database module called lock manager)
Unit 5 & 6: Practice Quiz
BEGIN
A=A+100
B=A+100
END
A = 100 + 100 = 200
B = 200 + 100 = 300
A=200, B=300
(A database can process multiple transactions concurrently by interleaving them.)
(This is the type of lock a transaction needs to acquire in order read from a database.)
T1: A=A+100, B=A-100
T2: A=A1.06, B=B1.06
Assuming T1 arrives first, what will be the final values of A and B if the database management system interleaves transactions?
T1: A = 500 + 100 = 600
T2: A = 600 * 1.06 = 636
T1: B = 636 - 100 = 536
T2: B = 536 * 1.06 = 568.16
A=636, B=568.16
Unit 5 & 6: Graded Quiz
(The atomicity principle states that all of the components of a transaction run in their entirety or none of them run at all)
(A database transaction needs to obtain a shared lock in order to read data from a database)
(Reading data from a database does not require an exclusive lock; a shared lock is sufficient)
T1: A=A+10, B=A+10
T2: A=A*1.1, B=B*1.1
Assuming T1 arrives first, what will be the final values of A and B if the two transactions are processed using a serial schedule?
T1: A = 0 + 10 = 10
T1: B = 10 + 10 = 20
T2: A = 10 * 1.1 = 11
T2: B = 20 * 1.1 = 22
A=11, B=22
T1: A=A+10, B=A+10
T2: A=A1.1, B=B1.1
Assuming T1 arrives first, what will be the final values of A and B if the database management system interleaves transactions?
T1: A = 0 + 10 = 10
T2: A = 10 = 10 * 1.1 = 11
T1: B = 11 + 10 = 21
T2: B = 21 * 1.1 = 23.1
A=11, B=23.1
(Database management systems implement transaction interleaving in order to achieve concurrency, which is the ability of a database to execute multiple transactions simultaneously)
(This is the definition of the isolation principle of database transactions)
(Isolation means that concurrent changes are invisible, which implies serializability)
The text was updated successfully, but these errors were encountered: