Debian Codegraph @

src/backend/access/heap/README.tuplock

raw
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.