Instead of using locks, we instead have transactions on memory. This is kind of like database transactions. Memory operations either success, or get rolled back to retry later, or aborted.
Serializable
An important definition here is that of serializability. This means that transactions can run concurrently, but the final result is equivalent to some serial order.
Pros and Cons
Pros:
- No need to worry about deadlocks or lock granularity
- Just a group of code that is operationally atomic
- This is up to the implementer to make sure that things are actually atomic Cons:
- Some things cannot be rolled back (write to the screen)
- Limited transaction size
- Nested transactions?
Warning
Being able to rollback does not protect against dataraces.
Definitions
Dirty reads:
- One client reads another client’s write before they have been committed. Dirty writes:
- One client overwrites data that another client has written, but not yet committed. Transaction implementations typically prevent dirty writes. Read skew:
- A client sees different parts of the database at different points in time. This issue is prevented with snapshot isolation.
Snapshot isolation
This is where a transaction reads the entire database from a consistent snapshot at one point in time. This is implemented using multi-version concurrency control.
Lost updates:
- Two clients concurrently perform a read-modify-write cycle. One overwrites the other’s write without incorporating its changes, so data is lost. Some implementations of snapshot isolation prevent this while other require a manual lock (
SELECT FOR UPDATE) Write skew: - A transaction reads something, makes a decision based on the value it say, and writes the decision to the database. However by the time the write is made, the premise of the decision is no longer true. Only serializable isolation prevents this. Phantom reads:
- A transaction reads objects that match some search condition. Another client makes a write that affects the search results. Snapshot isolation prevents simple versions of this but not write skew.
Most concurrency problems are solved in one of three ways:
- Just executing transactions in a serial order which can be done if throughput capacity is being reached and is low enough to process on a single CPU core.
- Two phase locking allows concurrent reads but as soon as someone wants to write, a lock is required. First, the transaction gathers all locks it needs to access required data (cannot release locks in this phase), then after performing operations, it starts releasing locks where in this phase, locks cannot be acquired.
- Serializable snapshot isolation is a new algorithm that uses an optimistic approach allowing transactions to proceed without blocking which are checked when the transaction wants to commit. The transaction is aborted if the execution was not serializable.
ACID
The safety guarantees provided by transactions are ACID which stands for:
- Atomic
- Consistent
- Isolated
- Durable This means that operations in a transaction succeed or fail together, certain statements about your data are always true (invariants) which need to be maintained after a transaction, concurrently executing operations are isolated from each other and cannot step on each other’s toes, and that once a transaction has committed successfully, the data will not be forgotten even if there is a hardware fault.
Related