| 1 |
Locking tuples |
| 2 |
-------------- |
| 3 |
|
| 4 |
Locking tuples is not as easy as locking tables or other database objects. |
| 5 |
The problem is that transactions might want to lock large numbers of tuples at |
| 6 |
any one time, so it's not possible to keep the locks objects in shared memory. |
| 7 |
To work around this limitation, we use a two-level mechanism. The first level |
| 8 |
is implemented by storing locking information in the tuple header: a tuple is |
| 9 |
marked as locked by setting the current transaction's XID as its XMAX, and |
| 10 |
setting additional infomask bits to distinguish this case from the more normal |
| 11 |
case of having deleted the tuple. When multiple transactions concurrently |
| 12 |
lock a tuple, a MultiXact is used; see below. This mechanism can accommodate |
| 13 |
arbitrarily large numbers of tuples being locked simultaneously. |
| 14 |
|
| 15 |
When it is necessary to wait for a tuple-level lock to be released, the basic |
| 16 |
delay is provided by XactLockTableWait or MultiXactIdWait on the contents of |
| 17 |
the tuple's XMAX. However, that mechanism will release all waiters |
| 18 |
concurrently, so there would be a race condition as to which waiter gets the |
| 19 |
tuple, potentially leading to indefinite starvation of some waiters. The |
| 20 |
possibility of share-locking makes the problem much worse --- a steady stream |
| 21 |
of share-lockers can easily block an exclusive locker forever. To provide |
| 22 |
more reliable semantics about who gets a tuple-level lock first, we use the |
| 23 |
standard lock manager, which implements the second level mentioned above. The |
| 24 |
protocol for waiting for a tuple-level lock is really |
| 25 |
|
| 26 |
LockTuple() |
| 27 |
XactLockTableWait() |
| 28 |
mark tuple as locked by me |
| 29 |
UnlockTuple() |
| 30 |
|
| 31 |
When there are multiple waiters, arbitration of who is to get the lock next |
| 32 |
is provided by LockTuple(). However, at most one tuple-level lock will |
| 33 |
be held or awaited per backend at any time, so we don't risk overflow |
| 34 |
of the lock table. Note that incoming share-lockers are required to |
| 35 |
do LockTuple as well, if there is any conflict, to ensure that they don't |
| 36 |
starve out waiting exclusive-lockers. However, if there is not any active |
| 37 |
conflict for a tuple, we don't incur any extra overhead. |
| 38 |
|
| 39 |
We make an exception to the above rule for those lockers that already hold |
| 40 |
some lock on a tuple and attempt to acquire a stronger one on it. In that |
| 41 |
case, we skip the LockTuple() call even when there are conflicts, provided |
| 42 |
that the target tuple is being locked, updated or deleted by multiple sessions |
| 43 |
concurrently. Failing to skip the lock would risk a deadlock, e.g., between a |
| 44 |
session that was first to record its weaker lock in the tuple header and would |
| 45 |
be waiting on the LockTuple() call to upgrade to the stronger lock level, and |
| 46 |
another session that has already done LockTuple() and is waiting for the first |
| 47 |
session transaction to release its tuple header-level lock. |
| 48 |
|
| 49 |
We provide four levels of tuple locking strength: SELECT FOR UPDATE obtains an |
| 50 |
exclusive lock which prevents any kind of modification of the tuple. This is |
| 51 |
the lock level that is implicitly taken by DELETE operations, and also by |
| 52 |
UPDATE operations if they modify any of the tuple's key fields. SELECT FOR NO |
| 53 |
KEY UPDATE likewise obtains an exclusive lock, but only prevents tuple removal |
| 54 |
and modifications which might alter the tuple's key. This is the lock that is |
| 55 |
implicitly taken by UPDATE operations which leave all key fields unchanged. |
| 56 |
SELECT FOR SHARE obtains a shared lock which prevents any kind of tuple |
| 57 |
modification. Finally, SELECT FOR KEY SHARE obtains a shared lock which only |
| 58 |
prevents tuple removal and modifications of key fields. This lock level is |
| 59 |
just strong enough to implement RI checks, i.e. it ensures that tuples do not |
| 60 |
go away from under a check, without blocking transactions that want to update |
| 61 |
the tuple without changing its key. |
| 62 |
|
| 63 |
The conflict table is: |
| 64 |
|
| 65 |
UPDATE NO KEY UPDATE SHARE KEY SHARE |
| 66 |
UPDATE conflict conflict conflict conflict |
| 67 |
NO KEY UPDATE conflict conflict conflict |
| 68 |
SHARE conflict conflict |
| 69 |
KEY SHARE conflict |
| 70 |
|
| 71 |
When there is a single locker in a tuple, we can just store the locking info |
| 72 |
in the tuple itself. We do this by storing the locker's Xid in XMAX, and |
| 73 |
setting infomask bits specifying the locking strength. See "Infomask Bits" |
| 74 |
below for details on the bit patterns we use. |
| 75 |
|
| 76 |
MultiXacts |
| 77 |
---------- |
| 78 |
|
| 79 |
A tuple header provides very limited space for storing information about tuple |
| 80 |
locking and updates: there is room only for a single Xid and a small number of |
| 81 |
infomask bits. Whenever we need to store more than one lock, we replace the |
| 82 |
first locker's Xid with a new MultiXactId. Each MultiXact provides extended |
| 83 |
locking data; it comprises an array of Xids plus some flags bits for each one. |
| 84 |
The flags are currently used to store the locking strength of each member |
| 85 |
transaction. (The flags also distinguish a pure locker from an updater.) |
| 86 |
|
| 87 |
In earlier PostgreSQL releases, a MultiXact always meant that the tuple was |
| 88 |
locked in shared mode by multiple transactions. This is no longer the case; a |
| 89 |
MultiXact may contain an update or delete Xid. (Keep in mind that tuple locks |
| 90 |
in a transaction do not conflict with other tuple locks in the same |
| 91 |
transaction, so it's possible to have otherwise conflicting locks in a |
| 92 |
MultiXact if they belong to the same transaction). |
| 93 |
|
| 94 |
Note that each lock is attributed to the subtransaction that acquires it. |
| 95 |
This means that a subtransaction that aborts is seen as though it releases the |
| 96 |
locks it acquired; concurrent transactions can then proceed without having to |
| 97 |
wait for the main transaction to finish. It also means that a subtransaction |
| 98 |
can upgrade to a stronger lock level than an earlier transaction had, and if |
| 99 |
the subxact aborts, the earlier, weaker lock is kept. |
| 100 |
|
| 101 |
The possibility of having an update within a MultiXact means that they must |
| 102 |
persist across crashes and restarts: a future reader of the tuple needs to |
| 103 |
figure out whether the update committed or aborted. So we have a requirement |
| 104 |
that pg_multixact needs to retain pages of its data until we're certain that |
| 105 |
the MultiXacts in them are no longer of interest. |
| 106 |
|
| 107 |
VACUUM is in charge of removing old MultiXacts at the time of tuple freezing. |
| 108 |
The lower bound used by vacuum (that is, the value below which all multixacts |
| 109 |
are removed) is stored as pg_class.relminmxid for each table; the minimum of |
| 110 |
all such values is stored in pg_database.datminmxid. The minimum across |
| 111 |
all databases, in turn, is recorded in checkpoint records, and CHECKPOINT |
| 112 |
removes pg_multixact/ segments older than that value once the checkpoint |
| 113 |
record has been flushed. |
| 114 |
|
| 115 |
Infomask Bits |
| 116 |
------------- |
| 117 |
|
| 118 |
The following infomask bits are applicable: |
| 119 |
|
| 120 |
- HEAP_XMAX_INVALID |
| 121 |
Any tuple with this bit set does not have a valid value stored in XMAX. |
| 122 |
|
| 123 |
- HEAP_XMAX_IS_MULTI |
| 124 |
This bit is set if the tuple's Xmax is a MultiXactId (as opposed to a |
| 125 |
regular TransactionId). |
| 126 |
|
| 127 |
- HEAP_XMAX_LOCK_ONLY |
| 128 |
This bit is set when the XMAX is a locker only; that is, if it's a |
| 129 |
multixact, it does not contain an update among its members. It's set when |
| 130 |
the XMAX is a plain Xid that locked the tuple, as well. |
| 131 |
|
| 132 |
- HEAP_XMAX_KEYSHR_LOCK |
| 133 |
- HEAP_XMAX_SHR_LOCK |
| 134 |
- HEAP_XMAX_EXCL_LOCK |
| 135 |
These bits indicate the strength of the lock acquired; they are useful when |
| 136 |
the XMAX is not a MultiXactId. If it's a multi, the info is to be found in |
| 137 |
the member flags. If HEAP_XMAX_IS_MULTI is not set and HEAP_XMAX_LOCK_ONLY |
| 138 |
is set, then one of these *must* be set as well. |
| 139 |
|
| 140 |
Note that HEAP_XMAX_EXCL_LOCK does not distinguish FOR NO KEY UPDATE from |
| 141 |
FOR UPDATE; this is implemented by the HEAP_KEYS_UPDATED bit. |
| 142 |
|
| 143 |
- HEAP_KEYS_UPDATED |
| 144 |
This bit lives in t_infomask2. If set, indicates that the operation(s) done |
| 145 |
by the XMAX compromise the tuple key, such as a SELECT FOR UPDATE, an UPDATE |
| 146 |
that modifies the columns of the key, or a DELETE. It's set regardless of |
| 147 |
whether the XMAX is a TransactionId or a MultiXactId. |
| 148 |
|
| 149 |
We currently never set the HEAP_XMAX_COMMITTED when the HEAP_XMAX_IS_MULTI bit |
| 150 |
is set. |
| 151 |
|
| 152 |
Locking to write inplace-updated tables |
| 153 |
--------------------------------------- |
| 154 |
|
| 155 |
If IsInplaceUpdateRelation() returns true for a table, the table is a system |
| 156 |
catalog that receives systable_inplace_update_begin() calls. Preparing a |
| 157 |
heap_update() of these tables follows additional locking rules, to ensure we |
| 158 |
don't lose the effects of an inplace update. In particular, consider a moment |
| 159 |
when a backend has fetched the old tuple to modify, not yet having called |
| 160 |
heap_update(). Another backend's inplace update starting then can't conclude |
| 161 |
until the heap_update() places its new tuple in a buffer. We enforce that |
| 162 |
using locktags as follows. While DDL code is the main audience, the executor |
| 163 |
follows these rules to make e.g. "MERGE INTO pg_class" safer. Locking rules |
| 164 |
are per-catalog: |
| 165 |
|
| 166 |
pg_class systable_inplace_update_begin() callers: before the call, acquire a |
| 167 |
lock on the relation in mode ShareUpdateExclusiveLock or stricter. If the |
| 168 |
update targets a row of RELKIND_INDEX (but not RELKIND_PARTITIONED_INDEX), |
| 169 |
that lock must be on the table. Locking the index rel is not necessary. |
| 170 |
(This allows VACUUM to overwrite per-index pg_class while holding a lock on |
| 171 |
the table alone.) systable_inplace_update_begin() acquires and releases |
| 172 |
LOCKTAG_TUPLE in InplaceUpdateTupleLock, an alias for ExclusiveLock, on each |
| 173 |
tuple it overwrites. |
| 174 |
|
| 175 |
pg_class heap_update() callers: before copying the tuple to modify, take a |
| 176 |
lock on the tuple, a ShareUpdateExclusiveLock on the relation, or a |
| 177 |
ShareRowExclusiveLock or stricter on the relation. |
| 178 |
|
| 179 |
SearchSysCacheLocked1() is one convenient way to acquire the tuple lock. |
| 180 |
Most heap_update() callers already hold a suitable lock on the relation for |
| 181 |
other reasons and can skip the tuple lock. If you do acquire the tuple |
| 182 |
lock, release it immediately after the update. |
| 183 |
|
| 184 |
|
| 185 |
pg_database: before copying the tuple to modify, all updaters of pg_database |
| 186 |
rows acquire LOCKTAG_TUPLE. (Few updaters acquire LOCKTAG_OBJECT on the |
| 187 |
database OID, so it wasn't worth extending that as a second option.) |
| 188 |
|
| 189 |
Ideally, DDL might want to perform permissions checks before LockTuple(), as |
| 190 |
we do with RangeVarGetRelidExtended() callbacks. We typically don't bother. |
| 191 |
LOCKTAG_TUPLE acquirers release it after each row, so the potential |
| 192 |
inconvenience is lower. |
| 193 |
|
| 194 |
Reading inplace-updated columns |
| 195 |
------------------------------- |
| 196 |
|
| 197 |
Inplace updates create an exception to the rule that tuple data won't change |
| 198 |
under a reader holding a pin. A reader of a heap_fetch() result tuple may |
| 199 |
witness a torn read. Current inplace-updated fields are aligned and are no |
| 200 |
wider than four bytes, and current readers don't need consistency across |
| 201 |
fields. Hence, they get by with just fetching each field once. |
| 202 |
|
| 203 |
During logical decoding, caches reflect an inplace update no later than the |
| 204 |
next XLOG_XACT_INVALIDATIONS. That record witnesses the end of a command. |
| 205 |
Tuples of its cmin are then visible to decoding, as are inplace updates of any |
| 206 |
lower LSN. Inplace updates of a higher LSN may also be visible, even if those |
| 207 |
updates would have been invisible to a non-historic snapshot matching |
| 208 |
decoding's historic snapshot. (In other words, decoding may see inplace |
| 209 |
updates that were not visible to a similar snapshot taken during original |
| 210 |
transaction processing.) That's a consequence of inplace update violating |
| 211 |
MVCC: there are no snapshot-specific versions of inplace-updated values. This |
| 212 |
all makes it hard to reason about inplace-updated column reads during logical |
| 213 |
decoding, but the behavior does suffice for relhasindex. A relhasindex=t in |
| 214 |
CREATE INDEX becomes visible no later than the new pg_index row. While it may |
| 215 |
be visible earlier, that's harmless. Finding zero indexes despite |
| 216 |
relhasindex=t is normal in more cases than this, e.g. after DROP INDEX. |
| 217 |
Example of a case that meaningfully reacts to the inplace inval: |
| 218 |
|
| 219 |
CREATE TABLE cat (c int) WITH (user_catalog_table = true); |
| 220 |
CREATE TABLE normal (d int); |
| 221 |
... |
| 222 |
CREATE INDEX ON cat (c)\; INSERT INTO normal VALUES (1); |
| 223 |
|
| 224 |
If the output plugin reads "cat" during decoding of the INSERT, it's fair to |
| 225 |
want that read to see relhasindex=t and use the new index. |
| 226 |
|
| 227 |
An alternative would be to have decoding of XLOG_HEAP_INPLACE immediately |
| 228 |
execute its invals. That would behave more like invals during original |
| 229 |
transaction processing. It would remove the decoding-specific delay in e.g. a |
| 230 |
decoding plugin witnessing a relfrozenxid change. However, a good use case |
| 231 |
for that is unlikely, since the plugin would still witness relfrozenxid |
| 232 |
changes prematurely. Hence, inplace update takes the trivial approach of |
| 233 |
delegating to XLOG_XACT_INVALIDATIONS. |