| 1 |
src/backend/storage/lmgr/README-SSI |
| 2 |
|
| 3 |
Serializable Snapshot Isolation (SSI) and Predicate Locking |
| 4 |
=========================================================== |
| 5 |
|
| 6 |
This code is in the lmgr directory because about 90% of it is an |
| 7 |
implementation of predicate locking, which is required for SSI, |
| 8 |
rather than being directly related to SSI itself. When another use |
| 9 |
for predicate locking justifies the effort to tease these two things |
| 10 |
apart, this README file should probably be split. |
| 11 |
|
| 12 |
|
| 13 |
Credits |
| 14 |
------- |
| 15 |
|
| 16 |
This feature was developed by Kevin Grittner and Dan R. K. Ports, |
| 17 |
with review and suggestions from Joe Conway, Heikki Linnakangas, and |
| 18 |
Jeff Davis. It is based on work published in these papers: |
| 19 |
|
| 20 |
Michael J. Cahill, Uwe Röhm, and Alan D. Fekete. 2008. |
| 21 |
Serializable isolation for snapshot databases. |
| 22 |
In SIGMOD '08: Proceedings of the 2008 ACM SIGMOD |
| 23 |
international conference on Management of data, |
| 24 |
pages 729-738, New York, NY, USA. ACM. |
| 25 |
http://doi.acm.org/10.1145/1376616.1376690 |
| 26 |
|
| 27 |
Michael James Cahill. 2009. |
| 28 |
Serializable Isolation for Snapshot Databases. |
| 29 |
Sydney Digital Theses. |
| 30 |
University of Sydney, School of Information Technologies. |
| 31 |
http://hdl.handle.net/2123/5353 |
| 32 |
|
| 33 |
|
| 34 |
Overview |
| 35 |
-------- |
| 36 |
|
| 37 |
With true serializable transactions, if you can show that your |
| 38 |
transaction will do the right thing if there are no concurrent |
| 39 |
transactions, it will do the right thing in any mix of serializable |
| 40 |
transactions or be rolled back with a serialization failure. This |
| 41 |
feature has been implemented in PostgreSQL using SSI. |
| 42 |
|
| 43 |
|
| 44 |
Serializable and Snapshot Transaction Isolation Levels |
| 45 |
------------------------------------------------------ |
| 46 |
|
| 47 |
Serializable transaction isolation is attractive for shops with |
| 48 |
active development by many programmers against a complex schema |
| 49 |
because it guarantees data integrity with very little staff time -- |
| 50 |
if a transaction can be shown to always do the right thing when it is |
| 51 |
run alone (before or after any other transaction), it will always do |
| 52 |
the right thing in any mix of concurrent serializable transactions. |
| 53 |
Where conflicts with other transactions would result in an |
| 54 |
inconsistent state within the database or an inconsistent view of |
| 55 |
the data, a serializable transaction will block or roll back to |
| 56 |
prevent the anomaly. The SQL standard provides a specific SQLSTATE |
| 57 |
for errors generated when a transaction rolls back for this reason, |
| 58 |
so that transactions can be retried automatically. |
| 59 |
|
| 60 |
Before version 9.1, PostgreSQL did not support a full serializable |
| 61 |
isolation level. A request for serializable transaction isolation |
| 62 |
actually provided snapshot isolation. This has well known anomalies |
| 63 |
which can allow data corruption or inconsistent views of the data |
| 64 |
during concurrent transactions; although these anomalies only occur |
| 65 |
when certain patterns of read-write dependencies exist within a set |
| 66 |
of concurrent transactions. Where these patterns exist, the anomalies |
| 67 |
can be prevented by introducing conflicts through explicitly |
| 68 |
programmed locks or otherwise unnecessary writes to the database. |
| 69 |
Snapshot isolation is popular because performance is better than |
| 70 |
serializable isolation and the integrity guarantees which it does |
| 71 |
provide allow anomalies to be avoided or managed with reasonable |
| 72 |
effort in many environments. |
| 73 |
|
| 74 |
|
| 75 |
Serializable Isolation Implementation Strategies |
| 76 |
------------------------------------------------ |
| 77 |
|
| 78 |
Techniques for implementing full serializable isolation have been |
| 79 |
published and in use in many database products for decades. The |
| 80 |
primary technique which has been used is Strict Two-Phase Locking |
| 81 |
(S2PL), which operates by blocking writes against data which has been |
| 82 |
read by concurrent transactions and blocking any access (read or |
| 83 |
write) against data which has been written by concurrent |
| 84 |
transactions. A cycle in a graph of blocking indicates a deadlock, |
| 85 |
requiring a rollback. Blocking and deadlocks under S2PL in high |
| 86 |
contention workloads can be debilitating, crippling throughput and |
| 87 |
response time. |
| 88 |
|
| 89 |
A new technique for implementing full serializable isolation in an |
| 90 |
MVCC database appears in the literature beginning in 2008. This |
| 91 |
technique, known as Serializable Snapshot Isolation (SSI) has many of |
| 92 |
the advantages of snapshot isolation. In particular, reads don't |
| 93 |
block anything and writes don't block reads. Essentially, it runs |
| 94 |
snapshot isolation but monitors the read-write conflicts between |
| 95 |
transactions to identify dangerous structures in the transaction |
| 96 |
graph which indicate that a set of concurrent transactions might |
| 97 |
produce an anomaly, and rolls back transactions to ensure that no |
| 98 |
anomalies occur. It will produce some false positives (where a |
| 99 |
transaction is rolled back even though there would not have been an |
| 100 |
anomaly), but will never let an anomaly occur. In the two known |
| 101 |
prototype implementations, performance for many workloads (even with |
| 102 |
the need to restart transactions which are rolled back) is very close |
| 103 |
to snapshot isolation and generally far better than an S2PL |
| 104 |
implementation. |
| 105 |
|
| 106 |
|
| 107 |
Apparent Serial Order of Execution |
| 108 |
---------------------------------- |
| 109 |
|
| 110 |
One way to understand when snapshot anomalies can occur, and to |
| 111 |
visualize the difference between the serializable implementations |
| 112 |
described above, is to consider that among transactions executing at |
| 113 |
the serializable transaction isolation level, the results are |
| 114 |
required to be consistent with some serial (one-at-a-time) execution |
| 115 |
of the transactions [1]. How is that order determined in each? |
| 116 |
|
| 117 |
In S2PL, each transaction locks any data it accesses. It holds the |
| 118 |
locks until committing, preventing other transactions from making |
| 119 |
conflicting accesses to the same data in the interim. Some |
| 120 |
transactions may have to be rolled back to prevent deadlock. But |
| 121 |
successful transactions can always be viewed as having occurred |
| 122 |
sequentially, in the order they committed. |
| 123 |
|
| 124 |
With snapshot isolation, reads never block writes, nor vice versa, so |
| 125 |
more concurrency is possible. The order in which transactions appear |
| 126 |
to have executed is determined by something more subtle than in S2PL: |
| 127 |
read/write dependencies. If a transaction reads data, it appears to |
| 128 |
execute after the transaction that wrote the data it is reading. |
| 129 |
Similarly, if it updates data, it appears to execute after the |
| 130 |
transaction that wrote the previous version. These dependencies, which |
| 131 |
we call "wr-dependencies" and "ww-dependencies", are consistent with |
| 132 |
the commit order, because the first transaction must have committed |
| 133 |
before the second starts. However, there can also be dependencies |
| 134 |
between two *concurrent* transactions, i.e. where one was running when |
| 135 |
the other acquired its snapshot. These "rw-conflicts" occur when one |
| 136 |
transaction attempts to read data which is not visible to it because |
| 137 |
the transaction which wrote it (or will later write it) is |
| 138 |
concurrent. The reading transaction appears to have executed first, |
| 139 |
regardless of the actual sequence of transaction starts or commits, |
| 140 |
because it sees a database state prior to that in which the other |
| 141 |
transaction leaves it. |
| 142 |
|
| 143 |
Anomalies occur when a cycle is created in the graph of dependencies: |
| 144 |
when a dependency or series of dependencies causes transaction A to |
| 145 |
appear to have executed before transaction B, but another series of |
| 146 |
dependencies causes B to appear before A. If that's the case, then |
| 147 |
the results can't be consistent with any serial execution of the |
| 148 |
transactions. |
| 149 |
|
| 150 |
|
| 151 |
SSI Algorithm |
| 152 |
------------- |
| 153 |
|
| 154 |
As of 9.1, serializable transactions in PostgreSQL are implemented using |
| 155 |
Serializable Snapshot Isolation (SSI), based on the work of Cahill |
| 156 |
et al. Fundamentally, this allows snapshot isolation to run as it |
| 157 |
previously did, while monitoring for conditions which could create a |
| 158 |
serialization anomaly. |
| 159 |
|
| 160 |
SSI is based on the observation [2] that each snapshot isolation |
| 161 |
anomaly corresponds to a cycle that contains a "dangerous structure" |
| 162 |
of two adjacent rw-conflict edges: |
| 163 |
|
| 164 |
Tin ------> Tpivot ------> Tout |
| 165 |
rw rw |
| 166 |
|
| 167 |
SSI works by watching for this dangerous structure, and rolling |
| 168 |
back a transaction when needed to prevent any anomaly. This means it |
| 169 |
only needs to track rw-conflicts between concurrent transactions, not |
| 170 |
wr- and ww-dependencies. It also means there is a risk of false |
| 171 |
positives, because not every dangerous structure is embedded in an |
| 172 |
actual cycle. The number of false positives is low in practice, so |
| 173 |
this represents an acceptable tradeoff for keeping the detection |
| 174 |
overhead low. |
| 175 |
|
| 176 |
The PostgreSQL implementation uses two additional optimizations: |
| 177 |
|
| 178 |
* Tout must commit before any other transaction in the cycle |
| 179 |
(see proof of Theorem 2.1 of [2]). We only roll back a transaction |
| 180 |
if Tout commits before Tpivot and Tin. |
| 181 |
|
| 182 |
* if Tin is read-only, there can only be an anomaly if Tout committed |
| 183 |
before Tin takes its snapshot. This optimization is an original |
| 184 |
one. Proof: |
| 185 |
|
| 186 |
- Because there is a cycle, there must be some transaction T0 that |
| 187 |
precedes Tin in the cycle. (T0 might be the same as Tout.) |
| 188 |
|
| 189 |
- The edge between T0 and Tin can't be a rw-conflict or ww-dependency, |
| 190 |
because Tin was read-only, so it must be a wr-dependency. |
| 191 |
Those can only occur if T0 committed before Tin took its snapshot, |
| 192 |
else Tin would have ignored T0's output. |
| 193 |
|
| 194 |
- Because Tout must commit before any other transaction in the |
| 195 |
cycle, it must commit before T0 commits -- and thus before Tin |
| 196 |
starts. |
| 197 |
|
| 198 |
|
| 199 |
PostgreSQL Implementation |
| 200 |
------------------------- |
| 201 |
|
| 202 |
* Since this technique is based on Snapshot Isolation (SI), those |
| 203 |
areas in PostgreSQL which don't use SI can't be brought under SSI. |
| 204 |
This includes system tables, temporary tables, sequences, hint bit |
| 205 |
rewrites, etc. SSI can not eliminate existing anomalies in these |
| 206 |
areas. |
| 207 |
|
| 208 |
* Any transaction which is run at a transaction isolation level |
| 209 |
other than SERIALIZABLE will not be affected by SSI. If you want to |
| 210 |
enforce business rules through SSI, all transactions should be run at |
| 211 |
the SERIALIZABLE transaction isolation level, and that should |
| 212 |
probably be set as the default. |
| 213 |
|
| 214 |
* If all transactions are run at the SERIALIZABLE transaction |
| 215 |
isolation level, business rules can be enforced in triggers or |
| 216 |
application code without ever having a need to acquire an explicit |
| 217 |
lock or to use SELECT FOR SHARE or SELECT FOR UPDATE. |
| 218 |
|
| 219 |
* Those who want to continue to use snapshot isolation without |
| 220 |
the additional protections of SSI (and the associated costs of |
| 221 |
enforcing those protections), can use the REPEATABLE READ transaction |
| 222 |
isolation level. This level retains its legacy behavior, which |
| 223 |
is identical to the old SERIALIZABLE implementation and fully |
| 224 |
consistent with the standard's requirements for the REPEATABLE READ |
| 225 |
transaction isolation level. |
| 226 |
|
| 227 |
* Performance under this SSI implementation will be significantly |
| 228 |
improved if transactions which don't modify permanent tables are |
| 229 |
declared to be READ ONLY before they begin reading data. |
| 230 |
|
| 231 |
* Performance under SSI will tend to degrade more rapidly with a |
| 232 |
large number of active database transactions than under less strict |
| 233 |
isolation levels. Limiting the number of active transactions through |
| 234 |
use of a connection pool or similar techniques may be necessary to |
| 235 |
maintain good performance. |
| 236 |
|
| 237 |
* Any transaction which must be rolled back to prevent |
| 238 |
serialization anomalies will fail with SQLSTATE 40001, which has a |
| 239 |
standard meaning of "serialization failure". |
| 240 |
|
| 241 |
* This SSI implementation makes an effort to choose the |
| 242 |
transaction to be canceled such that an immediate retry of the |
| 243 |
transaction will not fail due to conflicts with exactly the same |
| 244 |
transactions. Pursuant to this goal, no transaction is canceled |
| 245 |
until one of the other transactions in the set of conflicts which |
| 246 |
could generate an anomaly has successfully committed. This is |
| 247 |
conceptually similar to how write conflicts are handled. To fully |
| 248 |
implement this guarantee there needs to be a way to roll back the |
| 249 |
active transaction for another process with a serialization failure |
| 250 |
SQLSTATE, even if it is "idle in transaction". |
| 251 |
|
| 252 |
|
| 253 |
Predicate Locking |
| 254 |
----------------- |
| 255 |
|
| 256 |
Both S2PL and SSI require some form of predicate locking to handle |
| 257 |
situations where reads conflict with later inserts or with later |
| 258 |
updates which move data into the selected range. PostgreSQL didn't |
| 259 |
already have predicate locking, so it needed to be added to support |
| 260 |
full serializable transactions under either strategy. Practical |
| 261 |
implementations of predicate locking generally involve acquiring |
| 262 |
locks against data as it is accessed, using multiple granularities |
| 263 |
(tuple, page, table, etc.) with escalation as needed to keep the lock |
| 264 |
count to a number which can be tracked within RAM structures. This |
| 265 |
approach was used in PostgreSQL. Coarse granularities can cause some |
| 266 |
false positive indications of conflict. The number of false positives |
| 267 |
can be influenced by plan choice. |
| 268 |
|
| 269 |
|
| 270 |
Implementation overview |
| 271 |
----------------------- |
| 272 |
|
| 273 |
New RAM structures, inspired by those used to track traditional locks |
| 274 |
in PostgreSQL, but tailored to the needs of SIREAD predicate locking, |
| 275 |
are used. These refer to physical objects actually accessed in the |
| 276 |
course of executing the query, to model the predicates through |
| 277 |
inference. Anyone interested in this subject should review the |
| 278 |
Hellerstein, Stonebraker and Hamilton paper [3], along with the |
| 279 |
locking papers referenced from that and the Cahill papers. |
| 280 |
|
| 281 |
Because the SIREAD locks don't block, traditional locking techniques |
| 282 |
have to be modified. Intent locking (locking higher level objects |
| 283 |
before locking lower level objects) doesn't work with non-blocking |
| 284 |
"locks" (which are, in some respects, more like flags than locks). |
| 285 |
|
| 286 |
A configurable amount of shared memory is reserved at postmaster |
| 287 |
start-up to track predicate locks. This size cannot be changed |
| 288 |
without a restart. |
| 289 |
|
| 290 |
To prevent resource exhaustion, multiple fine-grained locks may |
| 291 |
be promoted to a single coarser-grained lock as needed. |
| 292 |
|
| 293 |
An attempt to acquire an SIREAD lock on a tuple when the same |
| 294 |
transaction already holds an SIREAD lock on the page or the relation |
| 295 |
will be ignored. Likewise, an attempt to lock a page when the |
| 296 |
relation is locked will be ignored, and the acquisition of a coarser |
| 297 |
lock will result in the automatic release of all finer-grained locks |
| 298 |
it covers. |
| 299 |
|
| 300 |
|
| 301 |
Heap locking |
| 302 |
------------ |
| 303 |
|
| 304 |
Predicate locks will be acquired for the heap based on the following: |
| 305 |
|
| 306 |
* For a table scan, the entire relation will be locked. |
| 307 |
|
| 308 |
* Each tuple read which is visible to the reading transaction |
| 309 |
will be locked, whether or not it meets selection criteria; except |
| 310 |
that there is no need to acquire an SIREAD lock on a tuple when the |
| 311 |
transaction already holds a write lock on any tuple representing the |
| 312 |
row, since a rw-conflict would also create a ww-dependency which |
| 313 |
has more aggressive enforcement and thus will prevent any anomaly. |
| 314 |
|
| 315 |
* Modifying a heap tuple creates a rw-conflict with any transaction |
| 316 |
that holds a SIREAD lock on that tuple, or on the page or relation |
| 317 |
that contains it. |
| 318 |
|
| 319 |
* Inserting a new tuple creates a rw-conflict with any transaction |
| 320 |
holding a SIREAD lock on the entire relation. It doesn't conflict with |
| 321 |
page-level locks, because page-level locks are only used to aggregate |
| 322 |
tuple locks. Unlike index page locks, they don't lock "gaps" on the page. |
| 323 |
|
| 324 |
|
| 325 |
Index AM implementations |
| 326 |
------------------------ |
| 327 |
|
| 328 |
Since predicate locks only exist to detect writes which conflict with |
| 329 |
earlier reads, and heap tuple locks are acquired to cover all heap |
| 330 |
tuples actually read, including those read through indexes, the index |
| 331 |
tuples which were actually scanned are not of interest in themselves; |
| 332 |
we only care about their "new neighbors" -- later inserts into the |
| 333 |
index which would have been included in the scan had they existed at |
| 334 |
the time. Conceptually, we want to lock the gaps between and |
| 335 |
surrounding index entries within the scanned range. |
| 336 |
|
| 337 |
Correctness requires that any insert into an index generates a |
| 338 |
rw-conflict with a concurrent serializable transaction if, after that |
| 339 |
insert, re-execution of any index scan of the other transaction would |
| 340 |
access the heap for a row not accessed during the previous execution. |
| 341 |
Note that a non-HOT update which expires an old index entry covered |
| 342 |
by the scan and adds a new entry for the modified row's new tuple |
| 343 |
need not generate a conflict, although an update which "moves" a row |
| 344 |
into the scan must generate a conflict. While correctness allows |
| 345 |
false positives, they should be minimized for performance reasons. |
| 346 |
|
| 347 |
Several optimizations are possible, though not all are implemented yet: |
| 348 |
|
| 349 |
* An index scan which is just finding the right position for an |
| 350 |
index insertion or deletion need not acquire a predicate lock. |
| 351 |
|
| 352 |
* An index scan which is comparing for equality on the entire key |
| 353 |
for a unique index need not acquire a predicate lock as long as a key |
| 354 |
is found corresponding to a visible tuple which has not been modified |
| 355 |
by another transaction -- there are no "between or around" gaps to |
| 356 |
cover. |
| 357 |
|
| 358 |
* As long as built-in foreign key enforcement continues to use |
| 359 |
its current "special tricks" to deal with MVCC issues, predicate |
| 360 |
locks should not be needed for scans done by enforcement code. |
| 361 |
|
| 362 |
* If a search determines that no rows can be found regardless of |
| 363 |
index contents because the search conditions are contradictory (e.g., |
| 364 |
x = 1 AND x = 2), then no predicate lock is needed. |
| 365 |
|
| 366 |
Other index AM implementation considerations: |
| 367 |
|
| 368 |
* For an index AM that doesn't have support for predicate locking, |
| 369 |
we just acquire a predicate lock on the whole index for any search. |
| 370 |
|
| 371 |
* B-tree index searches acquire predicate locks only on the |
| 372 |
index *leaf* pages needed to lock the appropriate index range. If, |
| 373 |
however, a search discovers that no root page has yet been created, a |
| 374 |
predicate lock on the index relation is required. |
| 375 |
|
| 376 |
* Like a B-tree, GIN searches acquire predicate locks only on the |
| 377 |
leaf pages of entry tree. When performing an equality scan, and an |
| 378 |
entry has a posting tree, the posting tree root is locked instead, to |
| 379 |
lock only that key value. However, fastupdate=on postpones the |
| 380 |
insertion of tuples into index structure by temporarily storing them |
| 381 |
into pending list. That makes us unable to detect r-w conflicts using |
| 382 |
page-level locks. To cope with that, insertions to the pending list |
| 383 |
conflict with all scans. |
| 384 |
|
| 385 |
* GiST searches can determine that there are no matches at any |
| 386 |
level of the index, so we acquire predicate lock at each index |
| 387 |
level during a GiST search. An index insert at the leaf level can |
| 388 |
then be trusted to ripple up to all levels and locations where |
| 389 |
conflicting predicate locks may exist. In case there is a page split, |
| 390 |
we need to copy predicate lock from the original page to all the new |
| 391 |
pages. |
| 392 |
|
| 393 |
* Hash index searches acquire predicate locks on the primary |
| 394 |
page of a bucket. It acquires a lock on both the old and new buckets |
| 395 |
for scans that happen concurrently with page splits. During a bucket |
| 396 |
split, a predicate lock is copied from the primary page of an old |
| 397 |
bucket to the primary page of a new bucket. |
| 398 |
|
| 399 |
* The effects of page splits, overflows, consolidations, and |
| 400 |
removals must be carefully reviewed to ensure that predicate locks |
| 401 |
aren't "lost" during those operations, or kept with pages which could |
| 402 |
get re-used for different parts of the index. |
| 403 |
|
| 404 |
|
| 405 |
Innovations |
| 406 |
----------- |
| 407 |
|
| 408 |
The PostgreSQL implementation of Serializable Snapshot Isolation |
| 409 |
differs from what is described in the cited papers for several |
| 410 |
reasons: |
| 411 |
|
| 412 |
1. PostgreSQL didn't have any existing predicate locking. It had |
| 413 |
to be added from scratch. |
| 414 |
|
| 415 |
2. The existing in-memory lock structures were not suitable for |
| 416 |
tracking SIREAD locks. |
| 417 |
* In PostgreSQL, tuple level locks are not held in RAM for |
| 418 |
any length of time; lock information is written to the tuples |
| 419 |
involved in the transactions. |
| 420 |
* In PostgreSQL, existing lock structures have pointers to |
| 421 |
memory which is related to a session. SIREAD locks need to persist |
| 422 |
past the end of the originating transaction and even the session |
| 423 |
which ran it. |
| 424 |
* PostgreSQL needs to be able to tolerate a large number of |
| 425 |
transactions executing while one long-running transaction stays open |
| 426 |
-- the in-RAM techniques discussed in the papers wouldn't support |
| 427 |
that. |
| 428 |
|
| 429 |
3. Unlike the database products used for the prototypes described |
| 430 |
in the papers, PostgreSQL didn't already have a true serializable |
| 431 |
isolation level distinct from snapshot isolation. |
| 432 |
|
| 433 |
4. PostgreSQL supports subtransactions -- an issue not mentioned |
| 434 |
in the papers. |
| 435 |
|
| 436 |
5. PostgreSQL doesn't assign a transaction number to a database |
| 437 |
transaction until and unless necessary (normally, when the transaction |
| 438 |
attempts to modify data). |
| 439 |
|
| 440 |
6. PostgreSQL has pluggable data types with user-definable |
| 441 |
operators, as well as pluggable index types, not all of which are |
| 442 |
based around data types which support ordering. |
| 443 |
|
| 444 |
7. Some possible optimizations became apparent during development |
| 445 |
and testing. |
| 446 |
|
| 447 |
Differences from the implementation described in the papers are |
| 448 |
listed below. |
| 449 |
|
| 450 |
* New structures needed to be created in shared memory to track |
| 451 |
the proper information for serializable transactions and their SIREAD |
| 452 |
locks. |
| 453 |
|
| 454 |
* Because PostgreSQL does not have the same concept of an "oldest |
| 455 |
transaction ID" for all serializable transactions as assumed in the |
| 456 |
Cahill thesis, we track the oldest snapshot xmin among serializable |
| 457 |
transactions, and a count of how many active transactions use that |
| 458 |
xmin. When the count hits zero we find the new oldest xmin and run a |
| 459 |
clean-up based on that. |
| 460 |
|
| 461 |
* Because reads in a subtransaction may cause that subtransaction |
| 462 |
to roll back, thereby affecting what is written by the top level |
| 463 |
transaction, predicate locks must survive a subtransaction rollback. |
| 464 |
As a consequence, all xid usage in SSI, including predicate locking, |
| 465 |
is based on the top level xid. When looking at an xid that comes |
| 466 |
from a tuple's xmin or xmax, for example, we always call |
| 467 |
SubTransGetTopmostTransaction() before doing much else with it. |
| 468 |
|
| 469 |
* PostgreSQL does not use "update in place" with a rollback log |
| 470 |
for its MVCC implementation. Where possible it uses "HOT" updates on |
| 471 |
the same page (if there is room and no indexed value is changed). |
| 472 |
For non-HOT updates the old tuple is expired in place and a new tuple |
| 473 |
is inserted at a new location. Because of this difference, a tuple |
| 474 |
lock in PostgreSQL doesn't automatically lock any other versions of a |
| 475 |
row. We don't try to copy or expand a tuple lock to any other |
| 476 |
versions of the row, based on the following proof that any additional |
| 477 |
serialization failures we would get from that would be false |
| 478 |
positives: |
| 479 |
|
| 480 |
o If transaction T1 reads a row version (thus acquiring a |
| 481 |
predicate lock on it) and a second transaction T2 updates that row |
| 482 |
version (thus creating a rw-conflict graph edge from T1 to T2), must a |
| 483 |
third transaction T3 which re-updates the new version of the row also |
| 484 |
have a rw-conflict in from T1 to prevent anomalies? In other words, |
| 485 |
does it matter whether we recognize the edge T1 -> T3? |
| 486 |
|
| 487 |
o If T1 has a conflict in, it certainly doesn't. Adding the |
| 488 |
edge T1 -> T3 would create a dangerous structure, but we already had |
| 489 |
one from the edge T1 -> T2, so we would have aborted something anyway. |
| 490 |
(T2 has already committed, else T3 could not have updated its output; |
| 491 |
but we would have aborted either T1 or T1's predecessor(s). Hence |
| 492 |
no cycle involving T1 and T3 can survive.) |
| 493 |
|
| 494 |
o Now let's consider the case where T1 doesn't have a |
| 495 |
rw-conflict in. If that's the case, for this edge T1 -> T3 to make a |
| 496 |
difference, T3 must have a rw-conflict out that induces a cycle in the |
| 497 |
dependency graph, i.e. a conflict out to some transaction preceding T1 |
| 498 |
in the graph. (A conflict out to T1 itself would be problematic too, |
| 499 |
but that would mean T1 has a conflict in, the case we already |
| 500 |
eliminated.) |
| 501 |
|
| 502 |
o So now we're trying to figure out if there can be an |
| 503 |
rw-conflict edge T3 -> T0, where T0 is some transaction that precedes |
| 504 |
T1. For T0 to precede T1, there has to be some edge, or sequence of |
| 505 |
edges, from T0 to T1. At least the last edge has to be a wr-dependency |
| 506 |
or ww-dependency rather than a rw-conflict, because T1 doesn't have a |
| 507 |
rw-conflict in. And that gives us enough information about the order |
| 508 |
of transactions to see that T3 can't have a rw-conflict to T0: |
| 509 |
- T0 committed before T1 started (the wr/ww-dependency implies this) |
| 510 |
- T1 started before T2 committed (the T1->T2 rw-conflict implies this) |
| 511 |
- T2 committed before T3 started (otherwise, T3 would get aborted |
| 512 |
because of an update conflict) |
| 513 |
|
| 514 |
o That means T0 committed before T3 started, and therefore |
| 515 |
there can't be a rw-conflict from T3 to T0. |
| 516 |
|
| 517 |
o So in all cases, we don't need the T1 -> T3 edge to |
| 518 |
recognize cycles. Therefore it's not necessary for T1's SIREAD lock |
| 519 |
on the original tuple version to cover later versions as well. |
| 520 |
|
| 521 |
* Predicate locking in PostgreSQL starts at the tuple level |
| 522 |
when possible. Multiple fine-grained locks are promoted to a single |
| 523 |
coarser-granularity lock as needed to avoid resource exhaustion. The |
| 524 |
amount of memory used for these structures is configurable, to balance |
| 525 |
RAM usage against SIREAD lock granularity. |
| 526 |
|
| 527 |
* Each backend keeps a process-local table of the locks it holds. |
| 528 |
To support granularity promotion decisions with low CPU and locking |
| 529 |
overhead, this table also includes the coarser covering locks and the |
| 530 |
number of finer-granularity locks they cover. |
| 531 |
|
| 532 |
* Conflicts are identified by looking for predicate locks |
| 533 |
when tuples are written, and by looking at the MVCC information when |
| 534 |
tuples are read. There is no matching between two RAM-based locks. |
| 535 |
|
| 536 |
* Because write locks are stored in the heap tuples rather than a |
| 537 |
RAM-based lock table, the optimization described in the Cahill thesis |
| 538 |
which eliminates an SIREAD lock where there is a write lock is |
| 539 |
implemented by the following: |
| 540 |
1. When checking a heap write for conflicts against existing |
| 541 |
predicate locks, a tuple lock on the tuple being written is removed. |
| 542 |
2. When acquiring a predicate lock on a heap tuple, we |
| 543 |
return quickly without doing anything if it is a tuple written by the |
| 544 |
reading transaction. |
| 545 |
|
| 546 |
* Rather than using conflictIn and conflictOut pointers which use |
| 547 |
NULL to indicate no conflict and a self-reference to indicate |
| 548 |
multiple conflicts or conflicts with committed transactions, we use a |
| 549 |
list of rw-conflicts. With the more complete information, false |
| 550 |
positives are reduced and we have sufficient data for more aggressive |
| 551 |
clean-up and other optimizations: |
| 552 |
|
| 553 |
o We can avoid ever rolling back a transaction until and |
| 554 |
unless there is a pivot where a transaction on the conflict *out* |
| 555 |
side of the pivot committed before either of the other transactions. |
| 556 |
|
| 557 |
o We can avoid ever rolling back a transaction when the |
| 558 |
transaction on the conflict *in* side of the pivot is explicitly or |
| 559 |
implicitly READ ONLY unless the transaction on the conflict *out* |
| 560 |
side of the pivot committed before the READ ONLY transaction acquired |
| 561 |
its snapshot. (An implicit READ ONLY transaction is one which |
| 562 |
committed without writing, even though it was not explicitly declared |
| 563 |
to be READ ONLY.) |
| 564 |
|
| 565 |
o We can more aggressively clean up conflicts, predicate |
| 566 |
locks, and SSI transaction information. |
| 567 |
|
| 568 |
* We allow a READ ONLY transaction to "opt out" of SSI if there are |
| 569 |
no READ WRITE transactions which could cause the READ ONLY |
| 570 |
transaction to ever become part of a "dangerous structure" of |
| 571 |
overlapping transaction dependencies. |
| 572 |
|
| 573 |
* We allow the user to request that a READ ONLY transaction wait |
| 574 |
until the conditions are right for it to start in the "opt out" state |
| 575 |
described above. We add a DEFERRABLE state to transactions, which is |
| 576 |
specified and maintained in a way similar to READ ONLY. It is |
| 577 |
ignored for transactions that are not SERIALIZABLE and READ ONLY. |
| 578 |
|
| 579 |
* When a transaction must be rolled back, we pick among the |
| 580 |
active transactions such that an immediate retry will not fail again |
| 581 |
on conflicts with the same transactions. |
| 582 |
|
| 583 |
* We use the PostgreSQL SLRU system to hold summarized |
| 584 |
information about older committed transactions to put an upper bound |
| 585 |
on RAM used. Beyond that limit, information spills to disk. |
| 586 |
Performance can degrade in a pessimal situation, but it should be |
| 587 |
tolerable, and transactions won't need to be canceled or blocked |
| 588 |
from starting. |
| 589 |
|
| 590 |
|
| 591 |
R&D Issues |
| 592 |
---------- |
| 593 |
|
| 594 |
This is intended to be the place to record specific issues which need |
| 595 |
more detailed review or analysis. |
| 596 |
|
| 597 |
* WAL file replay. While serializable implementations using S2PL |
| 598 |
can guarantee that the write-ahead log contains commits in a sequence |
| 599 |
consistent with some serial execution of serializable transactions, |
| 600 |
SSI cannot make that guarantee. While the WAL replay is no less |
| 601 |
consistent than under snapshot isolation, it is possible that under |
| 602 |
PITR recovery or hot standby a database could reach a readable state |
| 603 |
where some transactions appear before other transactions which would |
| 604 |
have had to precede them to maintain serializable consistency. In |
| 605 |
essence, if we do nothing, WAL replay will be at snapshot isolation |
| 606 |
even for serializable transactions. Is this OK? If not, how do we |
| 607 |
address it? |
| 608 |
|
| 609 |
* External replication. Look at how this impacts external |
| 610 |
replication solutions, like Postgres-R, Slony, pgpool, HS/SR, etc. |
| 611 |
This is related to the "WAL file replay" issue. |
| 612 |
|
| 613 |
* UNIQUE btree search for equality on all columns. Since a search |
| 614 |
of a UNIQUE index using equality tests on all columns will lock the |
| 615 |
heap tuple if an entry is found, it appears that there is no need to |
| 616 |
get a predicate lock on the index in that case. A predicate lock is |
| 617 |
still needed for such a search if a matching index entry which points |
| 618 |
to a visible tuple is not found. |
| 619 |
|
| 620 |
* Minimize touching of shared memory. Should lists in shared |
| 621 |
memory push entries which have just been returned to the front of the |
| 622 |
available list, so they will be popped back off soon and some memory |
| 623 |
might never be touched, or should we keep adding returned items to |
| 624 |
the end of the available list? |
| 625 |
|
| 626 |
|
| 627 |
References |
| 628 |
---------- |
| 629 |
|
| 630 |
[1] http://www.contrib.andrew.cmu.edu/~shadow/sql/sql1992.txt |
| 631 |
Search for serial execution to find the relevant section. |
| 632 |
|
| 633 |
[2] A. Fekete et al. Making Snapshot Isolation Serializable. In ACM |
| 634 |
Transactions on Database Systems 30:2, Jun. 2005. |
| 635 |
http://dx.doi.org/10.1145/1071610.1071615 |
| 636 |
|
| 637 |
[3] Joseph M. Hellerstein, Michael Stonebraker and James Hamilton. 2007. |
| 638 |
Architecture of a Database System. Foundations and Trends(R) in |
| 639 |
Databases Vol. 1, No. 2 (2007) 141-259. |
| 640 |
http://db.cs.berkeley.edu/papers/fntdb07-architecture.pdf |
| 641 |
Of particular interest: |
| 642 |
* 6.1 A Note on ACID |
| 643 |
* 6.2 A Brief Review of Serializability |
| 644 |
* 6.3 Locking and Latching |
| 645 |
* 6.3.1 Transaction Isolation Levels |
| 646 |
* 6.5.3 Next-Key Locking: Physical Surrogates for Logical Properties |