Debian Codegraph @

src/backend/storage/lmgr/README-SSI

raw
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