| 1 |
src/backend/storage/buffer/README |
| 2 |
|
| 3 |
Notes About Shared Buffer Access Rules |
| 4 |
====================================== |
| 5 |
|
| 6 |
There are two separate access control mechanisms for shared disk buffers: |
| 7 |
reference counts (a/k/a pin counts) and buffer content locks. (Actually, |
| 8 |
there's a third level of access control: one must hold the appropriate kind |
| 9 |
of lock on a relation before one can legally access any page belonging to |
| 10 |
the relation. Relation-level locks are not discussed here.) |
| 11 |
|
| 12 |
Pins: one must "hold a pin on" a buffer (increment its reference count) |
| 13 |
before being allowed to do anything at all with it. An unpinned buffer is |
| 14 |
subject to being reclaimed and reused for a different page at any instant, |
| 15 |
so touching it is unsafe. Normally a pin is acquired via ReadBuffer and |
| 16 |
released via ReleaseBuffer. It is OK and indeed common for a single |
| 17 |
backend to pin a page more than once concurrently; the buffer manager |
| 18 |
handles this efficiently. It is considered OK to hold a pin for long |
| 19 |
intervals --- for example, sequential scans hold a pin on the current page |
| 20 |
until done processing all the tuples on the page, which could be quite a |
| 21 |
while if the scan is the outer scan of a join. Similarly, a btree index |
| 22 |
scan may hold a pin on the current index page. This is OK because normal |
| 23 |
operations never wait for a page's pin count to drop to zero. (Anything |
| 24 |
that might need to do such a wait is instead handled by waiting to obtain |
| 25 |
the relation-level lock, which is why you'd better hold one first.) Pins |
| 26 |
may not be held across transaction boundaries, however. |
| 27 |
|
| 28 |
Buffer content locks: there are two kinds of buffer lock, shared and exclusive, |
| 29 |
which act just as you'd expect: multiple backends can hold shared locks on |
| 30 |
the same buffer, but an exclusive lock prevents anyone else from holding |
| 31 |
either shared or exclusive lock. (These can alternatively be called READ |
| 32 |
and WRITE locks.) These locks are intended to be short-term: they should not |
| 33 |
be held for long. Buffer locks are acquired and released by LockBuffer(). |
| 34 |
It will *not* work for a single backend to try to acquire multiple locks on |
| 35 |
the same buffer. One must pin a buffer before trying to lock it. |
| 36 |
|
| 37 |
Buffer access rules: |
| 38 |
|
| 39 |
1. To scan a page for tuples, one must hold a pin and either shared or |
| 40 |
exclusive content lock. To examine the commit status (XIDs and status bits) |
| 41 |
of a tuple in a shared buffer, one must likewise hold a pin and either shared |
| 42 |
or exclusive lock. |
| 43 |
|
| 44 |
2. Once one has determined that a tuple is interesting (visible to the |
| 45 |
current transaction) one may drop the content lock, yet continue to access |
| 46 |
the tuple's data for as long as one holds the buffer pin. This is what is |
| 47 |
typically done by heap scans, since the tuple returned by heap_fetch |
| 48 |
contains a pointer to tuple data in the shared buffer. Therefore the |
| 49 |
tuple cannot go away while the pin is held (see rule #5). Its state could |
| 50 |
change, but that is assumed not to matter after the initial determination |
| 51 |
of visibility is made. |
| 52 |
|
| 53 |
3. To add a tuple or change the xmin/xmax fields of an existing tuple, |
| 54 |
one must hold a pin and an exclusive content lock on the containing buffer. |
| 55 |
This ensures that no one else might see a partially-updated state of the |
| 56 |
tuple while they are doing visibility checks. |
| 57 |
|
| 58 |
4. It is considered OK to update tuple commit status bits (ie, OR the |
| 59 |
values HEAP_XMIN_COMMITTED, HEAP_XMIN_INVALID, HEAP_XMAX_COMMITTED, or |
| 60 |
HEAP_XMAX_INVALID into t_infomask) while holding only a shared lock and |
| 61 |
pin on a buffer. This is OK because another backend looking at the tuple |
| 62 |
at about the same time would OR the same bits into the field, so there |
| 63 |
is little or no risk of conflicting update; what's more, if there did |
| 64 |
manage to be a conflict it would merely mean that one bit-update would |
| 65 |
be lost and need to be done again later. These four bits are only hints |
| 66 |
(they cache the results of transaction status lookups in pg_xact), so no |
| 67 |
great harm is done if they get reset to zero by conflicting updates. |
| 68 |
Note, however, that a tuple is frozen by setting both HEAP_XMIN_INVALID |
| 69 |
and HEAP_XMIN_COMMITTED; this is a critical update and accordingly requires |
| 70 |
an exclusive buffer lock (and it must also be WAL-logged). |
| 71 |
|
| 72 |
5. To physically remove a tuple or compact free space on a page, one |
| 73 |
must hold a pin and an exclusive lock, *and* observe while holding the |
| 74 |
exclusive lock that the buffer's shared reference count is one (ie, |
| 75 |
no other backend holds a pin). If these conditions are met then no other |
| 76 |
backend can perform a page scan until the exclusive lock is dropped, and |
| 77 |
no other backend can be holding a reference to an existing tuple that it |
| 78 |
might expect to examine again. Note that another backend might pin the |
| 79 |
buffer (increment the refcount) while one is performing the cleanup, but |
| 80 |
it won't be able to actually examine the page until it acquires shared |
| 81 |
or exclusive content lock. |
| 82 |
|
| 83 |
|
| 84 |
Obtaining the lock needed under rule #5 is done by the bufmgr routines |
| 85 |
LockBufferForCleanup() or ConditionalLockBufferForCleanup(). They first get |
| 86 |
an exclusive lock and then check to see if the shared pin count is currently |
| 87 |
1. If not, ConditionalLockBufferForCleanup() releases the exclusive lock and |
| 88 |
then returns false, while LockBufferForCleanup() releases the exclusive lock |
| 89 |
(but not the caller's pin) and waits until signaled by another backend, |
| 90 |
whereupon it tries again. The signal will occur when UnpinBuffer decrements |
| 91 |
the shared pin count to 1. As indicated above, this operation might have to |
| 92 |
wait a good while before it acquires the lock, but that shouldn't matter much |
| 93 |
for concurrent VACUUM. The current implementation only supports a single |
| 94 |
waiter for pin-count-1 on any particular shared buffer. This is enough for |
| 95 |
VACUUM's use, since we don't allow multiple VACUUMs concurrently on a single |
| 96 |
relation anyway. Anyone wishing to obtain a cleanup lock outside of recovery |
| 97 |
or a VACUUM must use the conditional variant of the function. |
| 98 |
|
| 99 |
|
| 100 |
Buffer Manager's Internal Locking |
| 101 |
--------------------------------- |
| 102 |
|
| 103 |
Before PostgreSQL 8.1, all operations of the shared buffer manager itself |
| 104 |
were protected by a single system-wide lock, the BufMgrLock, which |
| 105 |
unsurprisingly proved to be a source of contention. The new locking scheme |
| 106 |
avoids grabbing system-wide exclusive locks in common code paths. It works |
| 107 |
like this: |
| 108 |
|
| 109 |
* There is a system-wide LWLock, the BufMappingLock, that notionally |
| 110 |
protects the mapping from buffer tags (page identifiers) to buffers. |
| 111 |
(Physically, it can be thought of as protecting the hash table maintained |
| 112 |
by buf_table.c.) To look up whether a buffer exists for a tag, it is |
| 113 |
sufficient to obtain share lock on the BufMappingLock. Note that one |
| 114 |
must pin the found buffer, if any, before releasing the BufMappingLock. |
| 115 |
To alter the page assignment of any buffer, one must hold exclusive lock |
| 116 |
on the BufMappingLock. This lock must be held across adjusting the buffer's |
| 117 |
header fields and changing the buf_table hash table. The only common |
| 118 |
operation that needs exclusive lock is reading in a page that was not |
| 119 |
in shared buffers already, which will require at least a kernel call |
| 120 |
and usually a wait for I/O, so it will be slow anyway. |
| 121 |
|
| 122 |
* As of PG 8.2, the BufMappingLock has been split into NUM_BUFFER_PARTITIONS |
| 123 |
separate locks, each guarding a portion of the buffer tag space. This allows |
| 124 |
further reduction of contention in the normal code paths. The partition |
| 125 |
that a particular buffer tag belongs to is determined from the low-order |
| 126 |
bits of the tag's hash value. The rules stated above apply to each partition |
| 127 |
independently. If it is necessary to lock more than one partition at a time, |
| 128 |
they must be locked in partition-number order to avoid risk of deadlock. |
| 129 |
|
| 130 |
* A separate system-wide spinlock, buffer_strategy_lock, provides mutual |
| 131 |
exclusion for operations that access the buffer free list or select |
| 132 |
buffers for replacement. A spinlock is used here rather than a lightweight |
| 133 |
lock for efficiency; no other locks of any sort should be acquired while |
| 134 |
buffer_strategy_lock is held. This is essential to allow buffer replacement |
| 135 |
to happen in multiple backends with reasonable concurrency. |
| 136 |
|
| 137 |
* Each buffer header contains a spinlock that must be taken when examining |
| 138 |
or changing fields of that buffer header. This allows operations such as |
| 139 |
ReleaseBuffer to make local state changes without taking any system-wide |
| 140 |
lock. We use a spinlock, not an LWLock, since there are no cases where |
| 141 |
the lock needs to be held for more than a few instructions. |
| 142 |
|
| 143 |
Note that a buffer header's spinlock does not control access to the data |
| 144 |
held within the buffer. Each buffer header also contains an LWLock, the |
| 145 |
"buffer content lock", that *does* represent the right to access the data |
| 146 |
in the buffer. It is used per the rules above. |
| 147 |
|
| 148 |
* The BM_IO_IN_PROGRESS flag acts as a kind of lock, used to wait for I/O on a |
| 149 |
buffer to complete (and in releases before 14, it was accompanied by a |
| 150 |
per-buffer LWLock). The process starting a read or write sets the flag. When |
| 151 |
the I/O is completed, be it by the process that initiated the I/O or by |
| 152 |
another process, the flag is removed and the Buffer's condition variable is |
| 153 |
signalled. Processes that need to wait for the I/O to complete can wait for |
| 154 |
asynchronous I/O by using BufferDesc->io_wref and for BM_IO_IN_PROGRESS to be |
| 155 |
unset by sleeping on the buffer's condition variable. |
| 156 |
|
| 157 |
|
| 158 |
Normal Buffer Replacement Strategy |
| 159 |
---------------------------------- |
| 160 |
|
| 161 |
There is a "free list" of buffers that are prime candidates for replacement. |
| 162 |
In particular, buffers that are completely free (contain no valid page) are |
| 163 |
always in this list. We could also throw buffers into this list if we |
| 164 |
consider their pages unlikely to be needed soon; however, the current |
| 165 |
algorithm never does that. The list is singly-linked using fields in the |
| 166 |
buffer headers; we maintain head and tail pointers in global variables. |
| 167 |
(Note: although the list links are in the buffer headers, they are |
| 168 |
considered to be protected by the buffer_strategy_lock, not the buffer-header |
| 169 |
spinlocks.) To choose a victim buffer to recycle when there are no free |
| 170 |
buffers available, we use a simple clock-sweep algorithm, which avoids the |
| 171 |
need to take system-wide locks during common operations. It works like |
| 172 |
this: |
| 173 |
|
| 174 |
Each buffer header contains a usage counter, which is incremented (up to a |
| 175 |
small limit value) whenever the buffer is pinned. (This requires only the |
| 176 |
buffer header spinlock, which would have to be taken anyway to increment the |
| 177 |
buffer reference count, so it's nearly free.) |
| 178 |
|
| 179 |
The "clock hand" is a buffer index, nextVictimBuffer, that moves circularly |
| 180 |
through all the available buffers. nextVictimBuffer is protected by the |
| 181 |
buffer_strategy_lock. |
| 182 |
|
| 183 |
The algorithm for a process that needs to obtain a victim buffer is: |
| 184 |
|
| 185 |
1. Obtain buffer_strategy_lock. |
| 186 |
|
| 187 |
2. If buffer free list is nonempty, remove its head buffer. Release |
| 188 |
buffer_strategy_lock. If the buffer is pinned or has a nonzero usage count, |
| 189 |
it cannot be used; ignore it go back to step 1. Otherwise, pin the buffer, |
| 190 |
and return it. |
| 191 |
|
| 192 |
3. Otherwise, the buffer free list is empty. Select the buffer pointed to by |
| 193 |
nextVictimBuffer, and circularly advance nextVictimBuffer for next time. |
| 194 |
Release buffer_strategy_lock. |
| 195 |
|
| 196 |
4. If the selected buffer is pinned or has a nonzero usage count, it cannot |
| 197 |
be used. Decrement its usage count (if nonzero), reacquire |
| 198 |
buffer_strategy_lock, and return to step 3 to examine the next buffer. |
| 199 |
|
| 200 |
5. Pin the selected buffer, and return. |
| 201 |
|
| 202 |
(Note that if the selected buffer is dirty, we will have to write it out |
| 203 |
before we can recycle it; if someone else pins the buffer meanwhile we will |
| 204 |
have to give up and try another buffer. This however is not a concern |
| 205 |
of the basic select-a-victim-buffer algorithm.) |
| 206 |
|
| 207 |
|
| 208 |
Buffer Ring Replacement Strategy |
| 209 |
--------------------------------- |
| 210 |
|
| 211 |
When running a query that needs to access a large number of pages just once, |
| 212 |
such as VACUUM or a large sequential scan, a different strategy is used. |
| 213 |
A page that has been touched only by such a scan is unlikely to be needed |
| 214 |
again soon, so instead of running the normal clock sweep algorithm and |
| 215 |
blowing out the entire buffer cache, a small ring of buffers is allocated |
| 216 |
using the normal clock sweep algorithm and those buffers are reused for the |
| 217 |
whole scan. This also implies that much of the write traffic caused by such |
| 218 |
a statement will be done by the backend itself and not pushed off onto other |
| 219 |
processes. |
| 220 |
|
| 221 |
For sequential scans, a 256KB ring is used. That's small enough to fit in L2 |
| 222 |
cache, which makes transferring pages from OS cache to shared buffer cache |
| 223 |
efficient. Even less would often be enough, but the ring must be big enough |
| 224 |
to accommodate all pages in the scan that are pinned concurrently. 256KB |
| 225 |
should also be enough to leave a small cache trail for other backends to |
| 226 |
join in a synchronized seq scan. If a ring buffer is dirtied and its LSN |
| 227 |
updated, we would normally have to write and flush WAL before we could |
| 228 |
re-use the buffer; in this case we instead discard the buffer from the ring |
| 229 |
and (later) choose a replacement using the normal clock-sweep algorithm. |
| 230 |
Hence this strategy works best for scans that are read-only (or at worst |
| 231 |
update hint bits). In a scan that modifies every page in the scan, like a |
| 232 |
bulk UPDATE or DELETE, the buffers in the ring will always be dirtied and |
| 233 |
the ring strategy effectively degrades to the normal strategy. |
| 234 |
|
| 235 |
VACUUM uses a ring like sequential scans, however, the size of this ring is |
| 236 |
controlled by the vacuum_buffer_usage_limit GUC. Dirty pages are not removed |
| 237 |
from the ring. Instead, WAL is flushed if needed to allow reuse of the |
| 238 |
buffers. Before introducing the buffer ring strategy in 8.3, VACUUM's buffers |
| 239 |
were sent to the freelist, which was effectively a buffer ring of 1 buffer, |
| 240 |
resulting in excessive WAL flushing. |
| 241 |
|
| 242 |
Bulk writes work similarly to VACUUM. Currently this applies only to |
| 243 |
COPY IN and CREATE TABLE AS SELECT. (Might it be interesting to make |
| 244 |
seqscan UPDATE and DELETE use the bulkwrite strategy?) For bulk writes |
| 245 |
we use a ring size of 16MB (but not more than 1/8th of shared_buffers). |
| 246 |
Smaller sizes have been shown to result in the COPY blocking too often |
| 247 |
for WAL flushes. While it's okay for a background vacuum to be slowed by |
| 248 |
doing its own WAL flushing, we'd prefer that COPY not be subject to that, |
| 249 |
so we let it use up a bit more of the buffer arena. |
| 250 |
|
| 251 |
|
| 252 |
Background Writer's Processing |
| 253 |
------------------------------ |
| 254 |
|
| 255 |
The background writer is designed to write out pages that are likely to be |
| 256 |
recycled soon, thereby offloading the writing work from active backends. |
| 257 |
To do this, it scans forward circularly from the current position of |
| 258 |
nextVictimBuffer (which it does not change!), looking for buffers that are |
| 259 |
dirty and not pinned nor marked with a positive usage count. It pins, |
| 260 |
writes, and releases any such buffer. |
| 261 |
|
| 262 |
If we can assume that reading nextVictimBuffer is an atomic action, then |
| 263 |
the writer doesn't even need to take buffer_strategy_lock in order to look |
| 264 |
for buffers to write; it needs only to spinlock each buffer header for long |
| 265 |
enough to check the dirtybit. Even without that assumption, the writer |
| 266 |
only needs to take the lock long enough to read the variable value, not |
| 267 |
while scanning the buffers. (This is a very substantial improvement in |
| 268 |
the contention cost of the writer compared to PG 8.0.) |
| 269 |
|
| 270 |
The background writer takes shared content lock on a buffer while writing it |
| 271 |
out (and anyone else who flushes buffer contents to disk must do so too). |
| 272 |
This ensures that the page image transferred to disk is reasonably consistent. |
| 273 |
We might miss a hint-bit update or two but that isn't a problem, for the same |
| 274 |
reasons mentioned under buffer access rules. |
| 275 |
|
| 276 |
As of 8.4, background writer starts during recovery mode when there is |
| 277 |
some form of potentially extended recovery to perform. It performs an |
| 278 |
identical service to normal processing, except that checkpoints it |
| 279 |
writes are technically restartpoints. |