1
Q
Single & Multi-user systems
A
- DBMS can be classified according to the number of users that can use a system concurrently
- Single-user systems are only accessible by one user at a time
- Typically used in PC apps
- Sqllite is a typical single user DBMS
- Single-user systems are only accessible by one user at a time
- Multi-user systems allow many users to connect and access data simultaneously
- Examples:
- Banking systems, Stock exchanges
- Web applications
- Online games
- Virtually all large systems will have a DB of some form behind the scenes
- Examples:
2
Q
Transactions
A
- A transaction is a logical unit of database processing that includes one or more DB access operations
- Can include INSERT, DELETE, UPDATE, SELECT
- Transactions may be defined within an application program
- May also be specified interactively using SQL statements
- BEGIN TRANSACTION and END TRANSACTION statements specify transaction boundaries
- All DB operations between these statements are considered as being part of the same transaction
3
Q
Transaction operations
A
- BEGIN transaction – marks the beginning of a transaction
- READ or WRITE – file reading/writing operations
- END transaction – marks the end of transaction execution, all read/write operations within the transaction have ended.
- At this point it may be necessary to check that changes can be permanently applied to the database or whether the changes need to be aborted.
- COMMIT transaction – Signals successful completion so that all changes can safely be permanently written to the DB
- ROLLBACK or ABORT – Signals unsuccessful completion so that all changes that have been made are undone
4
Q
Transaction states
A
5
Q
Desirable properties of transactions
A
- All transactions should exhibit the following properties, often called the ACID poperties
- Atomic – a transaction is an atomic unit of processing; it should be performed in it’s entirety or not at all
- Consistent - a transaction should preserve consistency, meaning if it is completely executed from beginning to end, without interference from other transaction it should take database from one consistent state to another
- Isolated – a transaction should appear as though it is being executed in isolation from other transactions, even though many transactions may be executing concurrently. No transaction should interfere with any other concurrent transactions
- Durable – The changes applied to the database by a committed transaction must persist in the database. These changers must not be lost because of any failure
6
Q
ACID properties are enabled by concurrency control and recovery methods
A
- Concurrency control methods – provide mechanisms for ensuring that the database is kept in a consistent state throughout the execution of concurrent transactions
- Recovery methods – provide mechanisms to recover from from failed transactions and other failure states while ensuring data
consistency
7
Q
Why do we need concurrency controls?
A
- Several problems can arise when concurrent transactions execute in an uncontrolled fashion
- The lost update problem
- The temporary update problem
- The incorrect summary problem
8
Q
The lost update problem
A
- Two transactions that access the same database items have their operations interleaved in a way that makes the value of some database item incorrect
9
Q
The temporary update problem
A
- One transaction updates a database item and then fails for some reason. The updated item is accessed by another transaction before it is changed back to it’s original value.
- Also known as the “dirty read” problem
10
Q
The incorrect summary problem
A
- One transaction is calculating an aggregate summary function on a number of records while other transactions are updating some of these records
- The aggregate function may calculate some values before they are updated and others after they are updated
- A variant is the unrepeatable read problem where transaction T reads an item twice and the item is changed by another transaction T’ between the two reads
- T receives different values for two reads of the same item
11
Q
Why do we need recovery?
A
- DBMS is responsible for ensuring that
- All operations in a transaction are completed successfully and there effect is recorded permanently in the database
- The transaction has no adverse effect on the database or any other transaction
- DBMS must not permit some operation of a transaction T to be applied to DB while other operations of T are not
- Even if transaction fails after executing some of it’s operations but not all of them
12
Q
Atomicity of transactions
A
- Either
- A. Every instruction in transaction appears to occur
- B. None of them appear to occur
- DBMS must not allow some but not all to occur
- May happen if a failure occurs during a transaction
- Could allow inconsistencies in data
13
Q
Types of failure
A
- System crash
- Hardware, software or network error occurs during transaction execution
- Transaction or system error
- Operation in the transaction may cause it to fail
- E.g. int overflow, division by zero
- Invalid parameter values or logical programming error
- Transaction may be interrupted by a user
- Operation in the transaction may cause it to fail
14
Q
Types of failure: local errors or exceptions
A
- Certain conditions whose occurrence may necessitate cancellation
- E.g. data not found
- Concurrency control enforcement
- Currency control method may decide to abort transaction and restart it later because it might interfere with other transactions or because several transactions are deadlocked
- Disk failure
- Some disk blocks may lose their data because of read/write malfunction or physical disk issue, may happen during transaction operation
15
Q
Types of failure: local errors or exceptions 2
A
- Physical problems, catastrophic failure
- Power failure
- Fire, theft, sabotage
- Human error
- System crashes, transaction errors, local errors, concurrency control enforcement are more common than disk failures or catastrophes
- For former the system must keep sufficient info to recover from failure
- For latter effective backup techniques must be in place
16
Q
The system log
A
- Used to recover from failures
- Keeps track of all transaction operations that affect values of DB items
- This info may be needed during recovery
- Log is kept on disk
- Not affected by any type of failure except media or catastrophic failures
- Can be periodically backed up to archival storage to safeguard against catastrophic failures
- A smart DBA keeps system logs on separate disks from data and OS files (ideally
with redundant disk storage)
- Not affected by any type of failure except media or catastrophic failures
17
Q
Log records – types of entries
A
18
Q
The system log 2
A
- Recovery protocols mostly do not require read_item operations be written to system log
- If log is used for other purposes such as auditing such entries are included
- All permanent changes to DB occur within transactions
- Even if no explicit transaction declared by user/app
- Recovery from a transaction failure requires either undoing or redoing all transaction operations from the log
- This will return the DB to a consistent state after a failure
19
Q
The system log
Aborted Transactions
A
- Aborted transactions
- Trace backwards through the log and reset (undo) all items changed by write_item operations in the transaction back to their old values
- Committed transactions: transactions whose updates are written in the log but a failure occurs before we can be sure all the updates have been applied to DB permanently
- Trace forward through log and set all items changed by write_item operations in transaction to their new values
20
Q
The system log
If system crashes
A
- If system crashes, we can (for example) UNDO the effect of every write operation of a transaction T by tracing backwards through the log and resetting all items changed back to their old values
- We can also REDO by going forward in the log
21
Q
Transaction states
System log
A
22
Q
Commit point
A
- All instructions in a transaction have been successful and logged
- Beyond this point, the transaction is COMMITTED and all the changes made are permanently recorded in the DB
- DBMS then writes [commit, T] to the log
- On system failure, look for [start_transaction] markers which are not matched by a [commit] marker
- If we find one, we UNDO all actions associated with that transaction in the log
23
Q
Transaction schedules
A schedule
A
- A schedule S of n transactions, T1 , T2
, T3…Tn is an ordering of the operations of the transactions- The ordering is subject to the constraint that for each transaction Ti that participates in S, the operations of Ti in S must appear in the same order as they appear in Ti
24
Q
Transaction schedule
A
- Schedule is the ordering of the transactions
- You can see here they have been interleaved, this is an example of non serial schedule
25
Serial schedules
* A serial schedule with no interleaving
* We could have performed all buy transactions before sell transaction and still had consistent result
26
Non serial schedules
* Non serial schedule resulting in lost update
27
Serialisability of schedules
* It is possible to write a nonserial schedule of T1 and T2 which gives a consistent result
* A schedule S of n transactions is serializable if it is equivalent to some serial schedule of the same n transactions
* Two schedules S1 and S2 are equivalent if
* Every read operation in S2 must read the same value in the corresponding read operation in S1
* The last value written into the database for every item should be the same for both S1 and S2
28
Serialisability of schedules 2
29
Serial and Non-serial
* We could enforce only serial schedules
* But we would end up going against the desirable time sharing property of efficiency
* Can we come up with a way of producing a non-serial schedule which is equivalent to a serial schedule and thus produces a consistent result?
30
*Can we come up with a way of producing a non-serial schedule which is
equivalent to a serial schedule and thus produces a consistent result?
*Concurrency Control to the rescue!
* Binary Locking
* 2-phase Locking
* Deadlock
31
Concurrency control techniques
* Used to ensure the non-interference (isolation) property of concurrently executing transactions
* Protocols that guarantee serialisability of schedules
* Locking based protocols
* Timestamp based protocols
* Others e.g. multi-version protocols
* In this unit we consider locking based protocols
32
Locking techniques
* Lock
* A variable associated with a data item that describes the status of the item with respect to possible operations that can be applied to it
* Locks are a means of synchronising the access to the database by concurrent transactions
* Generally there is one lock for each data item
33
Binary locks
* Can have two states or values
* Locked and unlocked (or 1 and 0 for simplicity)
* A distinct lock is associated with each database item X
* Lock value = 1 (locked)
* X cannot be accessed by an operation that requests the item
* Lock value = 0 (unlocked or free)
* X can be accessed by an operation that requests the item
34
Binary locks: Interface functions
* Lock (X)
* Current value or state of the lock
* Two possible states: 1 (locked) or 0 (unlocked)
* Two operations
* Lock_item (X)
* Unlock_item (X)
35
Binary Locks
Lock_item(x)
36
Binary Locks
Unlock_item (x)
* Note: this only applies to locks held by the process attempting the unlock operation!
37
Shared and exclusive locks
Binary locks are too restrictive
* At most one transaction can hold a lock
* Shared lock
* Also known as a read lock
* Several transactions can hold a shared lock on data item X if they all access X for reading purposes only
* Exclusive lock
* Also known as a write lock
* If a transaction is to write to an item X it must hold an exclusive lock
38
Shared and exclusive locks 2
* Lock (X)
* Three possible states: read-locked, write-locked and unlocked
* Three operations
* Read_lock(X)
* Write_lock(X)
* Unlock(X)
* One way of implementing the above three operations it to track the number of transactions that hold a shared lock on an item
* No_of_reads(X)
39
Read_lock(X)
40
Write_lock(X)
41
Unlock(X)
42
Lock conversion
* A transaction that already holds a lock on an item can be allowed, under certain conditions, to convert the lock from one locked state to another
* If a transaction T is the only transaction holding a read lock on an item it can upgrade it to a write lock
* A transaction may initially hold a write lock on an item and then later downgrade it to a read lock
43
Lock granularity
Granularities
* A database item for locking purposes can be:
* A database record
* An individual field of a database record
* A disk block
* A whole file
* The whole database
* Fine granularity
* Small item sizes
* Coarse granularity
* Large item sizes
44
Fine v coarse granularity
The coarser the granuality
the lower is the degree of concurrency
permitted
* Example: Granularity level is a disk block
* When a transaction T1 wishes to lock a record A, it must lock the whole disk block X
* If another transaction T2 wishes to lock a different record B in the same block X, it is forced to right
* If the granularity level was a record then T2
will be able to proceed as it will be locking a different item
45
Fine v coarse granularity
The finer the granularity
* The finer the granularity, the larger the number of active locks to be handled by the lock manager
* More lock and unlock operations higher overhead
* More storage space required for the lock table
46
Fine v coarse granularity
* What is the best level of granularity?
* Depends on the type of transactions involved
* If a transaction typically accesses a small number of records it is better to have locking granularity to be a single record
* If a transaction typically accesses many records in the same file it is better to have the locking granularity to be a disk block or a file
* Some locking protocols support multiple granularity level locking
* Some DBMS may perform lock escalation during a transaction to consolidate resources
47
What about serialisability?
* Use of binary locks or shared/exclusive locks does not guarantee serialisability on it’s own
* Let’s add locking to the sell and buy transactions from last time…
48
Sell and Buy with Locking
49
Sell and Buy with Locking 2
50
Two phase locking
* It turns out there is a simple protocol that guarantees serialisability if all transactions follow it
* All locking operations precede the first unlock operation
* An expanding or growing phase (phase 1)
* A shrinking phase (phase 2)
* A transaction following the protocol is divided into these two phases
51
Two phase locking
* Expanding or growing phase
* New locks on items can be acquired, but none can be released
* If lock conversion is allowed then upgrading of locks (read-locked to write-locked) must be carried out during this phase
52
Two phase locking
* Shrinking phase
* Existing locks can be released but no new locks can be acquired
* If lock conversion is allowed then downgrading of locks (writelocked to read-locked) must be carried out during this phase
53
Two phase locking 2
* Locking/unlocking instructions do not have to be sequential (or grouped together), other activities can take place in between locking/unlicking instructions
* As long as all locking is completed before the first unlock, we are following the 2PL protocol
54
Apply 2PL to sell and buy
Sell()
* Ordering our locks/unlocks into expanding/shrinking phases
* As you can see, we ask for a readlock, then immediately upgrade to a write-lock
55
Apply 2PL to sell and buy
Buy()
* Just ask for a write lock to begin with
* The two unlocks at the end of both are remnants of asking for a read-lock, unlocking it and then asking for write-lock
* If we ask for a write-lock to begin we just need to do one unlock at end
56
Apply 2PL to sell and buy
* This is a bit trivial, just looks like we are using semaphores to enforce mutual exclusion
57
Deadlock: sounds ominous
* Let us consider the situation where a process requires exclusive to two (or more) records
* Both processes A & B wish to access records 1 & 2
* Consider transactions T1 and T2
* There are various strategies to overcome this problem
58
Deadlock prevention protocols
* What to do with a transaction involved in a possible deadlock situation?
* Should it be blocked and made to wait?
* Should it be aborted?
* Should it pre-empt and abort another transaction?
Timing out deadlocks
* A waiting process will only wait so long. It then ‘times out’ and relinquishes any active locks it holds
* It then waits some arbitrary length of time before trying to apply it’s lock again
59
Timing out deadlocks
* The arbitrary amount of time waited should be different for each transaction.
* Can be difficult to decide what this amount of time should be
60
Timing out locks: broken locks
* Some form of timeout may be used to prevent clients from locking database resources forever
* What happens if a lock holder ‘dies’
* With the ability to abort a client’s transaction, a DBMS can break a client’s lock so that other, waiting clients can have a chance to access the locked data
* Choosing transaction to abort is known as victim selection
* VS algorithm should ideally seek to minimise cost of redoing an aborted transaction
* Typical the transaction that has made fewest changes (usually younger transactions)
61
Timing out locks: broken locks 2
* Break locks only when they have timed out and some other transaction is trying to gain a conflicting lock
* A lock whose time limit has been reached is called vulnerable because a request by another transaction will cause it to be broken
* A transaction, some of whose locks have been broken, cannot commit because the transaction has not seen a consistent view of the data
* This is why a client requesting to commit a transaction may result in it’s being aborted instead
62
Timing out locks: broken locks 3
* This approach is known as pessimistic
* We expect trouble and so we put mechanisms in place to avoid it arising
* The ‘timestamp’ approach is known as optimistic
* If trouble arises we detect it and deal with the consequences
63
Appendix: Another statement of the lock
algorithms for shared and exclusive locks
Read_lock(X)
64
Appendix: Another statement of the lock
algorithms for shared and exclusive locks
Write_lock(X)
65
Appendix: Another statement of the lock
algorithms for shared and exclusive locks
Unlock(X)
