Lock manager

To handle this problem, most databases are using locks and/or data versioning. Since it’s a big topic, I’ll focus on the locking part then I’ll speak a little bit about data versioning.

Pessimistic locking

The idea behind locking is:

  • if a transaction needs a data,
  • it locks the data
  • if another transaction also needs this data,
  • it’ll have to wait until the first transaction releases the data.

This is called an exclusive lock.

But using an exclusive lock for a transaction that only needs to read a data is very expensive since it forces other transactions that only want to read the same data to wait. This is why there is another type of lock, the shared lock.

With the shared lock:

  • if a transaction needs only to read a data A,
  • it “shared locks” the data and reads the data
  • if a second transaction also needs only to read data A,
  • it “shared locks” the data and reads the data
  • if a third transaction needs to modify data A,
  • it “exclusive locks” the data but it has to wait until the 2 other transactions release their shared locks to apply its exclusive lock on data A.

Still, if a data as an exclusive lock, a transaction that just needs to read the data will have to wait the end of the exclusive lock to put a shared lock on the data.

The lock manager is the process that gives and releases locks. Internally, it stores the locks in a hash table (where the key is the data to lock) and knows for each data:

  • which transactions are locking the data
  • which transactions are waiting for the data

Deadlock

But the use of locks can lead to a situation where 2 transactions are waiting forever for a data:

In this figure:

  • transaction A has an exclusive lock on data1 and is waiting to get data2
  • transaction B has an exclusive lock on data2 and is waiting to get data1

This is called a deadlock.

During a deadlock, the lock manager chooses which transaction to cancel (rollback) in order to remove the deadlock. This decision is not easy:

  • Is it better to kill the transaction that modified the least amount of data (and therefore that will produce the least expensive rollback)?
  • Is it better to kill the least aged transaction because the user of the other transaction has waited longer?
  • Is it better to kill the transaction that will take less time to finish (and avoid a possible starvation)?
  • In case of rollback, how many transactions will be impacted by this rollback?

But before making this choice, it needs to check if there are deadlocks.

The hash table can be seen as a graph (like in the previous figures). There is a deadlock if there is a cycle in the graph. Since it’s expensive to check for cycles (because the graph with all the locks is quite big), a simpler approach is often used: using a timeout. If a lock is not given within this timeout, the transaction enters a deadlock state.

The lock manager can also check before giving a lock if this lock will create a deadlock. But again it’s computationally expensive to do it perfectly. Therefore, these pre-checks are often a set of basic rules.

Two-phase locking

The simplest way to ensure a pure isolation is if a lock is acquired at the beginning of the transaction and released at the end of the transaction. This means that a transaction has to wait for all its locks before it starts and the locks held by a transaction are released when the transaction ends. It works but it produces a lot of time wasted to wait for all locks.

A faster way is the Two-Phase Locking Protocol (used by DB2 and SQL Server) where a transaction is divided into 2 phases:

  • the growing phase where a transaction can obtain locks, but can’t release any lock.
  • the shrinking phase where a transaction can release locks (on the data it has already processed and won’t process again), but can’t obtain new locks.

The idea behind these 2 simple rules is:

  • to release the locks that aren’t used anymore to reduce the wait time of other transactions waiting for these locks
  • to prevent from cases where a transaction gets data modified after the transaction started and therefore aren’t coherent with the first data the transaction acquired.

This protocol works well except if a transaction that modified a data and released the associated lock is cancelled (rolled back). You could end up in a case where another transaction reads the modified value whereas this value is going to be rolled back. To avoid this problem, all the exclusive locks must be released at the end of the transaction.

A few words

Of course a real database uses a more sophisticated system involving more types of locks (like intention locks) and more granularities (locks on a row, on a page, on a partition, on a table, on a tablespace) but the idea remains the same.

I only presented the pure lock-based approach. Data versioning is another way to deal with this problem.

The idea behind versioning is that:

  • every transaction can modify the same data at the same time
  • each transaction has its own copy (or version) of the data
  • if 2 transactions modify the same data, only one modification will be accepted, the other will be refused and the associated transaction will be rolled back (and maybe re-run).

It increases the performance since:

  • reader transactions don’t block writer transactions
  • writer transactions don’t block reader transactions
  • there is no overhead from the “fat and slow” lock manager

Everything is better than locks except when 2 transactions write the same data. Moreover, you can quickly end up with a huge disk space overhead.

Data versioning and locking are two different visions: optimistic locking vs pessimistic locking. They both have pros and cons; it really depends on the use case (more reads vs more writes). For a presentation on data versioning, I recommend this very good presentation on how PostgreSQL implements multiversion concurrency control.

Some databases like DB2 (until DB2 9.7) and SQL Server (except for snapshot isolation) are only using locks. Other like PostgreSQL, MySQL and Oracle use a mixed approach involving locks and data versioning. I’m not aware of a database using only data versioning (if you know a database based on a pure data versioning, feel free to tell me).

[UPDATE 08/20/2015] I was told by a reader that:

Firebird and Interbase use versioning without record locking.
Versioning has an interesting effect on indexes: sometimes a unique index contains duplicates, the index can have more entries than the table has rows, etc.

If you read the part on the different levels of isolation, when you increase the isolation level you increase the number of locks and therefore the time wasted by transactions to wait for their locks. This is why most databases don’t use the highest isolation level (Serializable) by default.

As always, you can check by yourself in the documentation of the main databases (for example MySQL, PostgreSQL or Oracle).

results matching ""

    No results matching ""