Snapshot isolation

In databases, and transaction processing (transaction management), snapshot isolation is a guarantee that all reads made in a transaction will see a consistent snapshot of the database (in practice it reads the last committed values that existed at the time it started), and the transaction itself will successfully commit only if no updates it has made conflict with any concurrent updates made since that snapshot.

Snapshot isolation has been adopted by several major database management systems, such as InterBase, Firebird, Oracle, MySQL,[1] PostgreSQL, SQL Anywhere, MongoDB[2] and Microsoft SQL Server (2005 and later). The main reason for its adoption is that it allows better performance than serializability, yet still avoids most of the concurrency anomalies that serializability avoids (but not always all). In practice snapshot isolation is implemented within multiversion concurrency control (MVCC), where generational values of each data item (versions) are maintained: MVCC is a common way to increase concurrency and performance by generating a new version of a database object each time the object is written, and allowing transactions' read operations of several last relevant versions (of each object). Snapshot isolation has been used[3] to criticize the ANSI SQL-92 standard's definition of isolation levels, as it exhibits none of the "anomalies" that the SQL standard prohibited, yet is not serializable (the anomaly-free isolation level defined by ANSI).

In spite of its distinction from serializability, snapshot isolation is sometimes referred to as serializable by Oracle.

Definition

A transaction executing under snapshot isolation appears to operate on a personal snapshot of the database, taken at the start of the transaction. When the transaction concludes, it will successfully commit only if the values updated by the transaction have not been changed externally since the snapshot was taken. Such a write–write conflict will cause the transaction to abort.

In a write skew anomaly, two transactions (T1 and T2) concurrently read an overlapping data set (e.g. values V1 and V2), concurrently make disjoint updates (e.g. T1 updates V1, T2 updates V2), and finally concurrently commit, neither having seen the update performed by the other. Were the system serializable, such an anomaly would be impossible, as either T1 or T2 would have to occur "first", and be visible to the other. In contrast, snapshot isolation permits write skew anomalies.

As a concrete example, imagine V1 and V2 are two balances held by a single person, Phil. The bank will allow either V1 or V2 to run a deficit, provided the total held in both is never negative (i.e. V1 + V2 ≥ 0). Both balances are currently $100. Phil initiates two transactions concurrently, T1 withdrawing $200 from V1, and T2 withdrawing $200 from V2.

If the database guaranteed serializable transactions, the simplest way of coding T1 is to deduct $200 from V1, and then verify that V1 + V2 ≥ 0 still holds, aborting if not. T2 similarly deducts $200 from V2 and then verifies V1 + V2 ≥ 0. Since the transactions must serialize, either T1 happens first, leaving V1 = −$100, V2 = $100, and preventing T2 from succeeding (since V1 + (V2 − $200) is now −$200), or T2 happens first and similarly prevents T1 from committing.

If the database is under snapshot isolation(MVCC), however, T1 and T2 operate on private snapshots of the database: each deducts $200 from an account, and then verifies that the new total is zero, using the other account value that held when the snapshot was taken. Since neither update conflicts, both commit successfully, leaving V1 = V2 = −$100, and V1 + V2 = −$200.

Some systems built using multiversion concurrency control (MVCC) may support (only) snapshot isolation to allow transactions to proceed without worrying about concurrent operations, and more importantly without needing to re-verify all read operations when the transaction finally commits. This is convenient because MVCC maintains a series of recent history consistent states. The only information that must be stored during the transaction is a list of updates made, which can be scanned for conflicts fairly easily before being committed. However MVCC systems (such as MarkLogic) will use locks to serialize writes together with MVCC to gain some of the performance gains and still support the stronger "serializability" level of isolation.

Workarounds

Potential inconsistency problems arising from write skew anomalies can be fixed by adding (otherwise unnecessary) updates to the transactions in order to enforce the serializability property.[4]

Materialize the conflict
Add a special conflict table, which both transactions update in order to create a direct write–write conflict.
Promotion
Have one transaction "update" a read-only location (replacing a value with the same value) in order to create a direct write–write conflict (or use an equivalent promotion, e.g. Oracle's SELECT FOR UPDATE).

In the example above, we can materialize the conflict by adding a new table which makes the hidden constraint explicit, mapping each person to their total balance. Phil would start off with a total balance of $200, and each transaction would attempt to subtract $200 from this, creating a write–write conflict that would prevent the two from succeeding concurrently. However, this approach violates the normal form.

Alternatively, we can promote one of the transaction's reads to a write. For instance, T2 could set V1 = V1, creating an artificial write–write conflict with T1 and, again, preventing the two from succeeding concurrently. This solution may not always be possible.

In general, therefore, snapshot isolation puts some of the problem of maintaining non-trivial constraints onto the user, who may not appreciate either the potential pitfalls or the possible solutions. The upside to this transfer is better performance.

Terminology

Snapshot isolation is called "serializable" mode in Oracle[5][6][7] and PostgreSQL versions prior to 9.1,[8][9][10] which may cause confusion with the "real serializability" mode. There are arguments both for and against this decision; what is clear is that users must be aware of the distinction to avoid possible undesired anomalous behavior in their database system logic.

History

Snapshot isolation arose from work on multiversion concurrency control databases, where multiple versions of the database are maintained concurrently to allow readers to execute without colliding with writers. Such a system allows a natural definition and implementation of such an isolation level.[3] InterBase, later owned by Borland, was acknowledged to provide SI rather than full serializability in version 4,[3] and likely permitted write-skew anomalies since its first release in 1985.[11]

Unfortunately, the ANSI SQL-92 standard was written with a lock-based database in mind, and hence is rather vague when applied to MVCC systems. Berenson et al. wrote a paper in 1995[3] critiquing the SQL standard, and cited snapshot isolation as an example of an isolation level that did not exhibit the standard anomalies described in the ANSI SQL-92 standard, yet still had anomalous behaviour when compared with serializable transactions.

In 2008, Cahill et al. showed that write-skew anomalies could be prevented by detecting and aborting "dangerous" triplets of concurrent transactions.[12] This implementation of serializability is well-suited to multiversion concurrency control databases, and has been adopted in PostgreSQL 9.1,[9][10][13] where it is referred to as "Serializable Snapshot Isolation", abbreviated to SSI. When used consistently, this eliminates the need for the above workarounds. The downside over snapshot isolation is an increase in aborted transactions. This can perform better or worse than snapshot isolation with the above workarounds, depending on workload.

In 2011, Jimenez-Peris et al. filed a patent [14] where it was shown how it was possible to scale to many millions of update transactions per second with a new method for attaining snapshot isolation in a distributed manner. The method is based on the observation that it becomes possible to commit transactions fully in parallel without any coordination and therefore removing the bottleneck of traditional transactional processing methods. The method uses a commit sequencer that generates commit timestamps and a snapshot server that advances the current snapshot as gaps are filled in the serialization order. This method is the base of the database LeanXcale.[15] The first implementation of this method was made in 2010 as part of the CumuloNimbo European Project.[16]

gollark: Do you NOT know of ssh_config?
gollark: To NOT have people do things manually by hand constantly?!?!?!!?
gollark: But the decision maths A level stuff available to me appears to be bad.
gollark: Sure.
gollark: Doesn't require doing it *manually*.

References
  1. "MySQL :: MySQL 8.0 Reference Manual :: 15.5.2.3 Consistent Nonlocking Reads". dev.mysql.com. Retrieved 2018-08-27.
  2. Multiversion concurrency control in MongoDB, MongoDB CTO: How our new WiredTiger storage engine will earn its stripes
  3. Berenson, Hal; Bernstein, Phil; Gray, Jim; Melton, Jim; O'Neil, Elizabeth; O'Neil, Patrick (1995), "A Critique of ANSI SQL Isolation Levels", Proceedings of the 1995 ACM SIGMOD international Conference on Management of Data, pp. 1–10, arXiv:cs/0701157, doi:10.1145/223784.223785, ISBN 978-0897917315
  4. Fekete, Alan; Liarokapis, Dimitrios; O'Neil, Elizabeth; O'Neil, Patrick; Shasha, Dennis (2005), "Making Snapshot Isolation Serializable", ACM Transactions on Database Systems, 30 (2): 492–528, CiteSeerX 10.1.1.503.3169, doi:10.1145/1071610.1071615, ISSN 0362-5915
  5. Oracle Database Concepts 10g Release 1 (10.1) Chapter 13 : Data Concurrency and Consistency — Oracle Isolation Levels
  6. Ask Tom : On Transaction Isolation Levels
  7. Ask Tom : "Serializable Transaction"
  8. PostgreSQL 9.0 Documentation: 13.2.2.1. Serializable Isolation versus True Serializability
  9. PostgreSQL 9.1 press release
  10. PostgreSQL 9.1.14 Documentation: 13.2.3. Serializable Isolation Level
  11. Stuntz, Craig. "Multiversion Concurrency Control Before InterBase". Retrieved October 30, 2014.
  12. Michael J. Cahill, Uwe Röhm, Alan D. Fekete (2008) "Serializable isolation for snapshot databases", Proceedings of the 2008 ACM SIGMOD international conference on Management of data, pp. 729–738, ISBN 978-1-60558-102-6 (SIGMOD 2008 best paper award)
  13. Ports, Dan R. K.; Grittner, Kevin (2012). "Serializable Snapshot Isolation in PostgreSQL" (PDF). Proceedings of the VLDB Endowment. 5 (12): 1850–1861. arXiv:1208.4179. CiteSeerX 10.1.1.294.3803. doi:10.14778/2367502.2367523.
  14. , JIMÉNEZ-PERIS, Ricardo & Marta PATIÑO-MARTINEZ, "System and method for highly scalable decentralized and low contention transactional processing"
  15. "LeanXcale". leanxcale.com. Retrieved 2017-08-20.
  16. Jimenez-Peris, Ricardo; Patiño-Martinez, Marta; Magoutis, Kostas; Bilas, Angelos; Brondino, Ivan (April 2012). "CumuloNimbo: A Highly-Scalable Transaction Processing Platform as a Service". Ercim News.

Further reading
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.