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 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 obtain 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] [5] [6] [7]}

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 ^{[8] [9] [10]} and PostgreSQL versions prior to 9.1, ^{[11] [12] [13]} 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. ^[14]

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. ^[15] This implementation of serializability is well-suited to multiversion concurrency control databases, and has been adopted in PostgreSQL 9.1, ^{[12] [13] [16]} where it is known as Serializable Snapshot Isolation (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.

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, S2CID   2316540
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, S2CID   1815415
5. 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, Vancouver, Canada, June 2008, ISBN   978-1-60558-102-6 (SIGMOD 2008 best paper award)
6. 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, Vancouver, Canada, June 2008, ISBN   978-1-60558-102-6 (SIGMOD 2008 best paper award)
7. Alan Fekete (2009), "Snapshot Isolation and Serializable Execution", Presentation, Page 4, 2009, The university of Sydney (Australia). Retrieved 16 September 2009
8. Oracle Database Concepts 10g Release 1 (10.1) Chapter 13 : Data Concurrency and Consistency — Oracle Isolation Levels
9. Ask Tom : On Transaction Isolation Levels
10. Ask Tom : "Serializable Transaction"
11. PostgreSQL 9.0 Documentation: 13.2.2.1. Serializable Isolation versus True Serializability
12. PostgreSQL 9.1 press release
13. PostgreSQL 9.1.14 Documentation: 13.2.3. Serializable Isolation Level
14. Stuntz, Craig. "Multiversion Concurrency Control Before InterBase". Archived from the original on October 23, 2007. Retrieved October 30, 2014.
15. 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)
16. 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. S2CID   16006111.

Further reading

• Bettina Kemme, Gustavo Alonso, A new approach to developing and implementing eager database replication protocols, ACM Transactions on Database Systems (TODS), v.25 n.3, p. 333-379, Sept. 2000.
• Gerhard Weikum, Gottfried Vossen, Transactional information systems: theory, algorithms, and the practice of concurrency control and recovery, Morgan Kaufmann, 2002, ISBN   1-55860-508-8
• Yi Lin, Bettina Kemme, Marta Patiño-Martínez, Ricardo Jiménez-Peris. Middleware based data replication providing snapshot isolation. Proceedings of the 2005 ACM SIGMOD international Conf., 2005.
• Marta Patiño-Martinez, Ricardo Jiménez-Peris, Bettina Kemme, Gustavo Alonso. MIDDLE-R: Consistent database replication at the middleware level. ACM Transactions on Computer Systems (TOCS). Volume 23 Issue 4. Pages 375-423.
• Khuzaima Daudjee, Kenneth Salem, Lazy Database Replication with Snapshot Isolation, VLDB 2006: pages 715-726