Reference
- http://www.zhai14.com/blog/strenghen-comprehension-on-dirty-read-and-phantom.html
- https://www.aneasystone.com/archives/2017/10/solving-dead-locks-one.html
Overview
A transaction is a way for an application to group several reads and writes together into a logical unit. Conceptually, all the reads and writes in a transaction are executed as one operation:
either the entire transaction succeeds (commit) or it fails (abort, rollback)
Transaction 简化了应用对数据库的访问,使 error handling 变得简单,因为无需考虑 partial failure。
Widely used isolation levels(解决数据库的并发读写问题):
- read committed
- snapshot isolation(repeatable read)
- serialization
Race conditions:
Dirty reads: 一个 client 读取了另一个 client 尚未提交的写。
Dirty writes: 而当事务 A 更新时，事务 A 还没提交，事务 B 就也过来进行更新，覆盖了事务 A 提交的更新数据。Almost all transaction implementations prevent dirty writes.
Read skew(Repeatable Read): A client sees different parts of the database at different points in time。snapshot isolation level(MVCC) 可以防止 read skew。
Lost updates: read-modify-write cycle 下容易发生,snapshot isolation level 可以防止该问题。
Write skew: Only serializable isolation prevents this anomaly.
Phantom reads: Snapshot isolation prevents straightforward phantom reads, but phantoms in the context of write skew require special treatment, such as index-range locks.
only serializable isolation protects against all of these issues. We discussed three different approaches to implementing serializable transactions:
Literally executing transactions in a serial order: 如果您可以使每个事务的执行速度非常快，并且事务吞吐量足够低，可以在单个CPU核心上处理，那么这是一个简单而有效的选项。
Two-phase locking
Serializable snapshot isolation (SSI):It uses an optimistic approach, allowing transactions to proceed without blocking.
The Slippery Concept of a Transaction
Nosql 牺牲一致性来保证可用性; Relation db 使用 transaction 来保证强一致性。说到底么有孰优孰劣,都是根据场景的 trade-off。
The meaning of ACID
Atomicity
在 ACID 语境下, Atomicity 不是关于并发的原子性,而是: The ability to abort a transaction on error and have all writes from that transaction discarded is the defining feature of ACID atomicity.
Consistency
this idea of consistency depends on the application’s notion of invariants, and it’s the application’s responsibility to define its transactions correctly so that they preserve consistency。
指的是应用程序(不是数据库)需要保证数据读写保证其应用程序的约束条件,以保证一致性。
Isolatoin(处理 concurrency problems)
Isolation in the sense of ACID means that concurrently executing transactions are isolated from each other: they cannot step on each other’s toes.
Durability
Durability is the promise that 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.
Single-Object and Multi-Object Operations
To recap, in ACID, atomicity and isolation describe what the database should do if a client makes several writes within the same transaction.
- Single-object writes
单条数据的读写也面临容错问题,比如当一条 10K 的 json 写入一半时网络断掉,所以对于 single-object, 存储也要提供 atomicity(可以用 log 实现) 和 isolation(可以用加锁的方式实现)。
- The need for multi-object transactions
single-object 事物无法满足所有的场景,如更新数据的时候需同步更新二级索引,所以 multi-object transaction 是需要的。
- Handling errors and aborts
Retrying an aborted transaction is a simple and effective error handling mechanism, 但是也会导致很多问题,比如不断重试对 server 造成压力。
Weak Isolation Levels
Serializable isolation means that the database guarantees that transactions have the same effect as if they ran serially (i.e., one at a time, without any concurrency)
但是 Serializable isolation has a performance cost, 所以 It’s therefore common for systems to use weaker levels of isolation, which protect against some concurrency issues, but not all。
Read Committed
保证:
- no dirty reads: 脏读会读取到不一致的数据
- no dirty writes: usually by delaying the second write until the first write’s transaction has committed or aborted.
实现:
使用 row-level lock 实现,当一个 transaction 修改一个 object(row or document) 时,必须先获取这个 object 的锁直到 transaction 完成才释放。在 transaction 期间,其他 transaction 会读取到旧值。
Snapshot Isolation and Repeatable Read
使用 Snapshot Isolation 来解决 repeatable read 的问题。
The idea is that each transaction reads from
a consistent snapshotof the database,Snapshot isolation is a boon for long-running, read-only queries such as backups and analytics.
实现: multi-version concurrency control (MVCC):
- 写: use write locks to prevent dirty writes
- 读: a key principle of snapshot isolation is readers never block writers, and writers never block readers。所以 the database must potentially keep several different committed versions of an object 来实现 snapshot 的效果。
Visibility rules for observing a consistent snapshot
Put another way, an object is visible if both of the following conditions are true:
- At the time when the reader’s transaction started, the transaction that created the object had already committed.
- The object is not marked for deletion, or if it is, the transaction that requested deletion had not yet committed at the time when the reader’s transaction started.
Indexes and snapshot isolation
have the index simply point to all versions of an object and require an index query to filter out any object versions that are not visible to the current transaction
use an append-only/copy-on-write variant that does not overwrite pages of the tree when they are updated, but instead creates a new copy of each modified page.
With append-only B-trees, every write transaction (or batch of transactions) creates a new B-tree root, and a particular root is a consistent snapshot of the database at the point in time when it was created.
Preventing Lost Updates
Atomic write operations
实现:
- 一种方法是使用排他锁,taking an exclusive lock on the object when it is read so that no other transaction can read it until the update has been applied.
- 一种方式是 simply force all atomic operations to be executed on a single thread.
Explicit locking
如果 db 提供的 atomic write operations 不足, 就需要在应用层面提供锁机制来解决并发写带来的问题。
Automatically detecting lost updates
An alternative is to allow them to execute in parallel and, if the transaction manager detects a lost update, abort the transaction and force it to retry its read-modify-write cycle.
An advantage of this approach is that databases can perform this check efficiently in conjunction with snapshot isolation.
Compare-and-set
The purpose of this operation is to avoid lost updates by allowing an update to happen only if the value has not changed since you last read it。如:
1 | -- This may or may not be safe, depending on the database implementation |
Write Skew and Phantoms(幻读)
This effect, where a write in one transaction changes the result of a search query in another transaction, is called a
phantomWrite skewcan occur if two transactions read the same objects, and then update some of those objects (different transactions may update different objects).
怎么解决?
- use a serializable isolation level
- probably to explicitly lock the rows that the transaction depends on
- materializing conflicts: it takes a phantom and turns it into a lock conflict on a concrete set of rows that exist in the database。
Serializability
Serializable isolation: It guarantees that even though transactions may execute in parallel, the end result is the same as if they had executed one at a time, serially, without any concurrency
3 种实现方式:
- Literally executing transactions in a serial order
- Two-phase locking
- Optimistic concurrency control techniques such as serializable snapshot isolation
Actual Serial Execution
Encapsulating transactions in stored procedures
在使用 single-threaded serial transaction 的 db 中,db 和 client 进行交互式的事务非常的低效,所以一般 the application must submit the entire transaction code to the database ahead of time, as a stored procedure.
Serial execution 总结:
- Every transaction must be small and fast
- It is limited to use cases where the active dataset can fit in memory·
- Write throughput must be low enough to be handled on a single CPU core。
- Cross-partition transactions are possible,但是很耗资源
Two-Phase Locking(2PL)
In 2PL, writers don’t just block other writers; they also block readers and vice versa.
Two Phase:
- first phase: (while the transaction is executing) is when the locks are acquired
- second phase: (at the end of the transaction) is when all the locks are released.
Implementation
having a lock on each object in the database. The lock can either be in shared mode or in exclusive mode. 读取的时候获取共享锁,写的时候获取排他锁。可以允许同时多个读,但是读会阻塞写,写会阻塞其他读和写。
Performance
For this reason, databases running 2PL can have quite unstable latencies, and they can be very slow at high percentiles if there is contention in the workload.
Predicate locks(谓词锁)
The key idea here is that a predicate lock applies even to objects that do not yet exist in the database, but which might be added in the future (phantoms).
Index-range locks
Serializable Snapshot Isolation(SSI)
基于 snapshot isolation 技术, SSI adds an algorithm for detecting serialization conflicts among writes and determining which transactions to abort.
It provides full serializability, but has only a small performance penalty compared to snapshot isolation.
缺陷: 当有大量事务访问 the same objects,可能会导致大量的事务 abort。
优势: 当 contention between transactions is not too high 时,相比悲观并发技术会有更好的性能。而且 Like under snapshot isolation, writers don’t block readers, and vice versa。
Decisions based on an outdated premise
2 种 db 检测 query result might have changed 的方式:
Detecting stale MVCC reads:
When the transaction wants to commit, the database checks whether any of the ignored writes have now been committed. If so, the transaction must be aborted.
By avoiding unnecessary aborts, SSI preserves snapshot isolation’s support for long-running reads from a consistent snapshot.
Detecting writes that affect prior reads:
When a transaction writes to the database, it must look in the indexes for any other transactions that have recently read the affected data. it simply notifies the transactions that the data they read may no longer be up to date.
Performance
The rate of aborts significantly affects the overall performance of SSI.
so SSI requires that read-write transactions be fairly short (long-running read-only transactions may be okay). However, SSI is probably less sensitive to slow transactions than two-phase locking or serial execution.
