Week 7-9 Transactions PDF

Transactions CENG 465 Principles of Data-Intensive Systems Introduction Many things can go wrong in data systems: ▫ The database software or hardware may fail at any time. ▫ Several clients may write to the database at the same time, overwriting each other’s changes. ▫ Race conditions b...

Transactions CENG 465 Principles of Data-Intensive Systems Introduction Many things can go wrong in data systems: ▫ The database software or hardware may fail at any time. ▫ Several clients may write to the database at the same time, overwriting each other’s changes. ▫ Race conditions between clients can cause surprising bugs. Reliable system ▫ Has to deal with these faults. ▫ Ensure that they do not cause catastrophic failure of entire system. Transactions Mechanism of choice for simplifying these issues. A way for an application to group several reads and writes together into a logical unit. Ex: Transaction to transfer $50 from account A to account B: 1. read(A) 2. A := A – 50 3. write(A) 4. read(B) 5. B := B + 50 6. write(B) Transactions All the reads and writes in a transaction are executed as one operation: ▫ Either the entire transaction succeeds (commit) or ▫ It fails (abort, rollback) With transactions, error handling becomes much simpler for an application, because it doesn’t need to worry about partial failure. Transactions Purpose: To simplify the programming model for applications accessing a database. The application is free to ignore ▫ Certain potential error scenarios ▫ Concurrency issues We need to understand: ▫ What safety guarantees transactions can provide. ▫ What costs are associated with them. Transactions Transaction support: ▫ Almost all relational databases today ▫ Some nonrelational databases In the late 2000s, nonrelational (NoSQL) databases started gaining popularity: ▫ Different data models, replication, partitioning ▫ Abandoned transactions entirely ▫ Redefined the word to describe a much weaker set of guarantees Transactions Like every other technical design choice, transactions have advantages and limitations. Advantages: ▫ Data integrity: ACID properties ensure that complex operations are handled correctly, making them ideal for financial systems, e-commerce, and other applications where data integrity is paramount. ▫ Reliability: With transaction support, RDBMSs can ensure that operations are atomic and durable, which reduces the chances of data corruption or inconsistencies, even in the case of system crashes. Transactions Like every other technical design choice, transactions have advantages and limitations. Limitations: ▫ Scalability: RDBMSs are typically designed for vertical scaling which can be limiting in distributed environments where horizontal scaling is more desirable. ▫ Performance bottlenecks: Locking mechanisms used to maintain isolation can result in performance bottlenecks in high-concurrency environments. ▫ Complexity: Managing ACID transactions across distributed systems can be complex and inefficient (especially when replications and partitioning are involved) ACID The safety guarantees provided by transactions are often described by the well-known acronym ACID: Atomicity ▫ All writes will either succeed, or all will fail. ▫ Upon error, any partial writes need to be undone. Consistency ▫ A transaction, when starting to execute, must see a consistent database. ▫ When the transaction completes successfully the database must be consistent. ACID Consistency – The word consistency is terribly overloaded: ▫ Replica consistency and the issue of eventual consistency that arises in asynchronously replicated systems. ▫ In the CAP theorem, the word consistency is used to mean linearizability (we will discuss it in the next weeks). ▫ In the context of ACID, consistency refers to an application-specific notion of the database being in a “good state.” ACID Consistency – From a different point of view ▫ Consistency in ACID refers to ensuring that certain data rules (invariants) are always maintained. ▫ Example: In an accounting system, credits and debits across all accounts must always be balanced. ▫ Consistency is based on the application's definition of invariants. ▫ The application is responsible for defining and ensuring transactions that preserve these invariants. ACID Consistency - From a different point of view (cont.) ▫ The database cannot automatically ensure that the invariants are respected. ▫ If bad data violating the invariants is written, the database can't prevent it. ▫ Some specific invariants can be enforced by the database, such as: Foreign key constraints. Uniqueness constraints. ▫ However, the application ultimately defines what data is valid or invalid. ACID Isolation ▫ Concurrently executing transactions are isolated from each other. ▫ “Serializability” – “Each transaction can pretend that it is the only transaction running on the entire database.” ▫ The database ensures that when the transactions have committed, the result is the same as if they had run serially. ▫ In practice, serializable isolation is rarely used, because it carries a performance penalty. ACID Isolation Transaction to transfer $50 from account A to account B: T1 T2 1. read(A) 2. A := A – 50 3. write(A) read(A), read(B), print(A+B) 4. read(B) 5. B := B + 50 6. write(B) ACID Durability ▫ Once a transaction has committed successfully, any data it has written will not be forgotten, even if there is a hardware fault or the database crashes. Applications can still be implemented without transactions. However: ▫ Error handling becomes much more complicated without atomicity. ▫ The lack of isolation can cause concurrency problems. Isolation Concurrency issues come into play when: ▫ Read-Write / Write-Read Race conditions ▫ Write-Write Isolation Transaction isolation ▫ Hiding concurrency issues from application developers by database systems. Serializable isolation ▫ Highest level of transaction isolation ▫ Database guarantees that transactions have the same effect as if they ran serially (i.e., one at a time, without any concurrency). ▫ In practice, serializable isolation has a performance cost. Weak Isolation Levels Weaker Isolation Levels ▫ Isolation levels weaker than serializable have been implemented to provide better scalability. ▫ Concurrency problems ▫ Common for systems to use weaker levels of isolation. Even many popular relational database systems (which are usually considered “ACID”) use weak isolation. Several weak (nonserializable) isolation levels that are used in practice. Read Committed Isolation It makes two guarantees: ▫ When reading from the database, you will only see data that has been committed (no dirty reads). ▫ When writing to the database, you will only overwrite data that has been committed (no dirty writes). No Dirty Reads No Dirty Reads Transactions running at the read committed isolation level must prevent dirty reads. If a dirty read happens and then this transaction is rolled back: ▫ The dirty read allows other transactions to see a value that was never actually written. No Dirty Writes Transactions running at the read committed isolation level must prevent dirty writes. By preventing dirty writes, this isolation level avoids some kinds of concurrency problems. Read committed prevents such mishaps. Implementing Read Committed Default setting in Oracle 11g, PostgreSQL, SQL Server 2012. Preventing dirty writes ▫ Locking: Row-level locks: Exclusive locks Acquire a lock on the object. Hold that lock until the transaction is committed or aborted. Only one transaction can hold the lock for any given object. Review: Locks Lock Compatibility Matrix: Shared Lock (S) ▫ Read lock ▫ Locks out writes but allows other reads Exclusive Lock (X) ▫ Write lock ▫ Locks out all other transactions A transaction may be granted a lock on an item if the requested lock is compatible with locks already held on the item by other transactions. Implementing Read Committed Preventing dirty reads ▫ Locking: Acquire the shared lock and then release it again immediately after reading. This can hurt performance if long-running writes block other transactions. This harms the response time of read-only transactions. ▫ Alternative: Using the approach illustrated in Figure 7-4: For every object that is written, record the old committed value and return that value to all other transactions until the writing transaction completes. Read Committed Isolation Prevents dirty reads. Prevents dirty writes. However, you can have concurrency bugs when using this isolation level. ▫ Figure 7-6 Read Committed Isolation The anomaly in Figure 7-6: nonrepeatable read or read skew ▫ Nonrepeatable read: A transaction reads the same object (e.g., the same row) at least twice, but between the first and second read, the value of the read data changes because other transactions update and commit the same row's data. ▫ Read skew: A transaction sees different parts of the database at different points in time (due to write activity from other users). Nonrepeatable read is considered acceptable under read committed isolation. Snapshot Isolation and Repeatable Read Each transaction reads from a consistent snapshot of the database. ▫ The transaction sees all the data that was committed in the database at the start of the transaction. ▫ Note that some products call snapshot isolation “repeatable read.” To add to the confusion, other products mean other things by “repeatable read.” Even if the data is subsequently changed by another transaction, each transaction sees only the old data from that particular point in time. Supported by PostgreSQL, MySQL with the InnoDB storage engine, Oracle, SQL Server. Implementing Snapshot Isolation Reads do not require any locks. Readers never block writers. Writers never block readers. Implementing Snapshot Isolation Preventing dirty writes ▫ Locking: Exclusive locks A transaction that makes a write can block the progress of another transaction that writes to the same object. Preventing dirty reads ▫ Multiversion concurrency control (MVCC) Database must keep several different committed versions of an object, because various in-progress transactions may need to see the state of the database at different points in time. Implementing Snapshot Isolation MVCC-based snapshot isolation implementation in PostgreSQL (other implementations are similar): ▫ Each transaction gets a unique, always increasing transaction ID number. ▫ Every write is tracked with the transaction ID. ▫ When a transaction runs, it ignores values from transactions that were already in progress or started after it. Visibility Rules for Observing a Consistent Snapshot 1. At the start of each transaction: ▫ Database makes a list of all the other transactions that are in progress at that time. ▫ Any writes that those transactions have made are ignored, even if the transactions subsequently commit. 2. Any writes made by aborted transactions are ignored. 3. Any writes made by transactions with a later transaction ID (i.e., which started after the current transaction started) are ignored, regardless of whether those transactions have committed. 4. All other writes are visible to the application’s queries. Repeatable Read and Naming Confusion Useful isolation level, especially for read-only transactions. Many databases that implement it call it by different names: ▫ Oracle: Serializable ▫ PostgreSQL and MySQL: Repeatable Read Snapshot Isolation - Repeatable Read Isolation Prevents dirty reads. Prevents dirty writes. Prevents read skew. Another Concurrency Problem: Lost Update Until know, we discussed: ▫ What a read-only transaction can see in the presence of concurrent write. ▫ WR / RW conflicts Another issue of two transactions writing concurrently: ▫ WW conflict Lost update problem Lost Update Problem Lost Update Problem Two transactions concurrently perform a read-modify-write cycle on the same object. One transaction overwrites the other’s write without incorporating the other’s changes, so data is lost. Preventing Lost Updates: Atomic Write Operations Many databases provide atomic update operations, which remove the need to implement read-modify-write cycles in application code. ▫ UPDATE counters SET value = value + 1 WHERE key = 'foo'; Atomic operations are usually implemented by taking an exclusive lock on the object when it is read so that other transactions cannot read it until the update has been applied. Best choice: in situations where atomic operations can be used. Preventing Lost Updates: Explicit Locking If the database’s built-in atomic operations don’t provide the necessary functionality: the application explicitly locks objects that are going to be updated. ▫ Example: SQL “FOR UPDATE” clause. SELECT value FROM counters WHERE key = 'foo' FOR UPDATE; Preventing Lost Updates: Automatically Detecting Lost Updates Preventing lost updates: atomic writing operations, locking Alternative: allow them to execute in parallel ▫ If the transaction manager detects a lost update, abort the transaction and force it to retry its read-modify-write cycle. Databases can perform this check efficiently in conjunction with snapshot isolation. ▫ Oracle’s serializable, and SQL Server’s snapshot isolation levels automatically detect when a lost update has occurred and abort the offending transaction. ▫ However, MySQL/ InnoDB’s repeatable read does not detect lost updates. Preventing Lost Updates: Compare-and-Set In databases that don’t provide transactions, allowing an update to happen only if the value has not changed since you last read it. If the current value does not match what you previously read, the update has no effect, and the read-modify-write cycle must be retried. Ex: To prevent two users concurrently updating the same wiki page, you might try something like this, expecting the update to occur only if the content of the page hasn’t changed since the user started editing it: Preventing Lost Updates: Conflict Resolution and Replication Locks and compare-and-set operations assume that there is a single up- to-date copy of the data. Preventing lost updates in replicated databases ▫ Copies of data on multiple nodes. ▫ Data can potentially be modified concurrently on different nodes. ▫ Additional steps need to be taken to prevent lost updates. Preventing Lost Updates: Conflict Resolution and Replication A common approach in replicated databases: ▫ Allow concurrent writes to create several conflicting versions of a value (siblings). ▫ Use application code to resolve and merge these versions after the fact. Last write wins (LWW) conflict resolution method is prone to lost updates. ▫ Unfortunately, default in many replicated databases. Write Skew and Phantoms Two kinds of race conditions that can occur when different transactions concurrently try to write to the same objects: ▫ Dirty Writes ▫ Lost Update Write Skew and Phantoms Write Skew ▫ Another race condition that can occur between concurrent writes. ▫ Two transactions are updating two different objects. A transaction reads something, makes a decision based what it read, and writes a value dependent upon the decision. While the transaction was running, other writes to different objects have made the decision no longer correct. ▫ A generalization of the lost update problem. Write Skew and Phantoms Preventing write skews: ▫ Our options are more restricted. ▫ Atomic single-object operations don’t help, as multiple objects are involved. ▫ Automatic detection of write skew is not detectable. ▫ Best option: Serializable isolation level ▫ Second-best option: Explicit locking the rows that the transaction depends on. Write Skew and Phantoms Phantoms causing write skew “SELECT” checks some requirement by searching for rows that match. Continue based on result of the query. If continue, application makes a write and commits the transaction. The effect of the write changes the step 1 query result. (This is called a phantom). Write Skew and Phantoms Phantom reads ▫ A transaction reads objects that match some criteria. Another transaction makes a write that creates a new record that affects the search criteria. ▫ Effect where a write in one transaction changes the result set of a search query in another transaction. Write Skew and Phantoms Snapshot isolation ▫ Prevents phantoms in read-only queries. ▫ But in read-write transactions like the examples we discussed, phantoms can lead to particularly tricky cases of write skew. Serializable Isolation Level The strongest isolation level. Guarantees that even though transactions may execute in parallel, the result is same as if they has executed one at a time, serially, without any concurrency. ▫ The database prevents all possible race conditions. Actual Serial Execution Remove the concurrency entirely: to execute only one transaction at a time, in serial order on a single thread. Completely sidestep the problem of detecting and preventing conflicts between transactions. Two-Phase Locking (2PL) Widely used algorithm for serializability in databases. Reads require shared locks. Writes require exclusive locks. Reads block writes and writes block reads. ▫ In snapshot isolation: Readers never block writers, and writers never block readers. Implementing Two-Phase Locking See: Review: Locks After a transaction has acquired the lock: ▫ It must continue to hold the lock until the end of the transaction (commit or abort). First phase (while the transaction is executing): ▫ The locks are acquired. Second phase (at the end of the transaction): ▫ All the locks are released. Two-Phase Locking: Deadlock Transaction A is stuck waiting for transaction B to release its lock and vice versa. Two-Phase Locking: Deadlock ▫ Automatically detected by the database. ▫ One of the transaction is aborted so that the other can make progress. ▫ The aborted transaction needs to be retried by the application.  64 Deadlock Detection Wait-for graph ▫ Vertices: transactions ▫ Edge from Ti →Tj : if Ti is waiting for a lock held in conflicting mode by Tj. The system is in a deadlock state if and only if the wait-for graph has a cycle. Invoke a deadlock-detection algorithm periodically to look for cycles.  65 Deadlock Detection Wait-for graph without a cycle Wait-for graph with a cycle Deadlock!  66 Deadlock Prevention Strategies The locking protocol may be modified to avoid deadlock. Wait-Die: ▫ If Transaction B is older than Transaction A: Transaction B waits. ▫ Otherwise: Transaction B dies (rolls back). Wound-Wait: ▫ If Transaction B is older than Transaction A: Transaction B wounds, that is, Transaction A rolls back. ▫ Otherwise: Transaction B waits.  67 Deadlock Prevention Strategies Net effect of Wait-Die and Wound-Wait ▫ Oldest transaction wins! In both schemes, a rolled back transaction is restarted with its original timestamp.  68 Example: Wait-Die T1 T2 T1 is older so it is allowed to lock-S(A) wait. T2 is younger so it is roll backed. read(A) ▫ Its locks are released. lock-S(B) ▫ Allows T1 to proceed. read(B) lock-X(B) lock-X(A)  69 Example: Wound-Wait T1 T2 T1 is older so T2 is roll backed lock-S(A) and that allows to T1 proceed. read(A) lock-S(B) read(B) lock-X(B)  70 Deadlock Prevention Strategies Timeout-Based Schemes: ▫ A transaction waits for a lock only for a specified amount of time. After that, the wait times out and the transaction is rolled back. ▫ Ensures that deadlocks get resolved by timeout if they occur. ▫ Simple to implement. ▫ But may roll back transaction unnecessarily in absence of deadlock. ▫ Difficult to determine good value of the timeout interval. Two-Phase Locking: Predicate Locks A database with serializable isolation must prevent phantoms. ▫ Phantom - one transaction changing the results of another transaction’s search query. Predicate lock: ▫ Works similarly to the shared/exclusive lock. ▫ But rather than belonging to a particular object (e.g., one row in a table), it belongs to all objects that match some search condition. Two-Phase Locking: Predicate Locks Ex: Meeting room booking ▫ If one transaction has searched for existing bookings for a room within a certain time window, another transaction is not allowed to concurrently insert or update another booking for the same room and time range. SELECT * FROM bookings WHERE room_id = 123 AND end_time > '2018-01-01 12:00' AND start_time < '2018-01-01 13:00'; ▫ We need a predicate lock to implement this. Two-Phase Locking: Predicate Locks A predicate lock restricts access as follows: ▫ If transaction A wants to read objects matching some condition, it must acquire a shared-mode predicate lock on the conditions of the query. ▫ If another transaction B currently has an exclusive lock on any object matching those conditions, A must wait until B releases its lock before it is allowed to make its query. The key idea: A predicate lock applies even to objects that do not yet exist in the database, but which might be added in the future (phantoms). Two-Phase Locking: Index-range Locks Predicate locks do not perform well: ▫ If there are many locks by active transactions. Checking for matching locks becomes time-consuming. Most databases with 2PL actually implement index-range locking. ▫ A superset can be locked. ▫ Worst case, an entire table can be locked. Serializable Snapshot Isolation (SSI) A relatively new algorithm. Based on snapshot isolation. ▫ All reads within a transaction are made from a consistent snapshot of the database. ▫ Adds an algorithm for detecting serialization conflicts among writes and determining which transactions to abort. ▫ Builds on snapshot isolation MVCC. Serializable Snapshot Isolation (SSI) Allows concurrency and upon commit detects if any isolation was violated. Worst case: lots of transactions getting aborted. Is used both in ▫ Single-node databases (the serializable isolation level in PostgreSQL since version 9.1 ). ▫ Distributed databases (FoundationDB uses a similar algorithm). Pessimistic versus Optimistic Concurrency Control Two-phase locking: pessimistic concurrency control mechanism ▫ Based on the principle that if anything might possibly go wrong. ▫ It’s better to wait until the situation is safe again before doing anything. Serial execution: pessimistic to the extreme ▫ It is essentially equivalent to each transaction having an exclusive lock on the entire database (or one partition of the database) for the duration of the transaction. Serializable snapshot isolation: optimistic concurrency control technique ▫ Instead of blocking if something potentially dangerous happens, transactions continue anyway, in the hope that everything will turn out all right. Pessimistic versus Optimistic Concurrency Control Serializable snapshot isolation: optimistic concurrency control technique ▫ When a transaction wants to commit, the database checks whether the execution was serializable. ▫ If not serializable: The transaction is aborted and has to be retried. ▫ Only transactions that executed serializable are allowed to commit. References M. Kleppman. Designing Data-Intensive Applications: The Big Ideas Behind Reliable, Scalable, and Maintainable Systems. O'Reilly Media, Inc., 2017. A. Silberschatz, HF. Korth, S. Sudarshan, Database System Concepts, 7th Ed., McGraw-Hill, 2019.