| 1 |
src/backend/storage/freespace/README |
| 2 |
|
| 3 |
Free Space Map |
| 4 |
-------------- |
| 5 |
|
| 6 |
The purpose of the free space map is to quickly locate a page with enough |
| 7 |
free space to hold a tuple to be stored; or to determine that no such page |
| 8 |
exists and the relation must be extended by one page. As of PostgreSQL 8.4 |
| 9 |
each relation has its own, extensible free space map stored in a separate |
| 10 |
"fork" of its relation. This eliminates the disadvantages of the former |
| 11 |
fixed-size FSM. |
| 12 |
|
| 13 |
It is important to keep the map small so that it can be searched rapidly. |
| 14 |
Therefore, we don't attempt to record the exact free space on a page. |
| 15 |
We allocate one map byte to each page, allowing us to record free space |
| 16 |
at a granularity of 1/256th of a page. Another way to say it is that |
| 17 |
the stored value is the free space divided by BLCKSZ/256 (rounding down). |
| 18 |
We assume that the free space must always be less than BLCKSZ, since |
| 19 |
all pages have some overhead; so the maximum map value is 255. |
| 20 |
|
| 21 |
To assist in fast searching, the map isn't simply an array of per-page |
| 22 |
entries, but has a tree structure above those entries. There is a tree |
| 23 |
structure of pages, and a tree structure within each page, as described |
| 24 |
below. |
| 25 |
|
| 26 |
FSM page structure |
| 27 |
------------------ |
| 28 |
|
| 29 |
Within each FSM page, we use a binary tree structure where leaf nodes store |
| 30 |
the amount of free space on heap pages (or lower level FSM pages, see |
| 31 |
"Higher-level structure" below), with one leaf node per heap page. A non-leaf |
| 32 |
node stores the max amount of free space on any of its children. |
| 33 |
|
| 34 |
For example: |
| 35 |
|
| 36 |
4 |
| 37 |
4 2 |
| 38 |
3 4 0 2 <- This level represents heap pages |
| 39 |
|
| 40 |
We need two basic operations: search and update. |
| 41 |
|
| 42 |
To search for a page with X amount of free space, traverse down the tree |
| 43 |
along a path where n >= X, until you hit the bottom. If both children of a |
| 44 |
node satisfy the condition, you can pick either one arbitrarily. |
| 45 |
|
| 46 |
To update the amount of free space on a page to X, first update the leaf node |
| 47 |
corresponding to the heap page, then "bubble up" the change to upper nodes, |
| 48 |
by walking up to each parent and recomputing its value as the max of its |
| 49 |
two children. Repeat until reaching the root or a parent whose value |
| 50 |
doesn't change. |
| 51 |
|
| 52 |
This data structure has a couple of nice properties: |
| 53 |
- to discover that there is no page with X bytes of free space, you only |
| 54 |
need to look at the root node |
| 55 |
- by varying which child to traverse to in the search algorithm, when you have |
| 56 |
a choice, we can implement various strategies, like preferring pages closer |
| 57 |
to a given page, or spreading the load across the table. |
| 58 |
|
| 59 |
Higher-level routines that use FSM pages access them through the fsm_set_avail() |
| 60 |
and fsm_search_avail() functions. The interface to those functions hides the |
| 61 |
page's internal tree structure, treating the FSM page as a black box that has |
| 62 |
a certain number of "slots" for storing free space information. (However, |
| 63 |
the higher routines have to be aware of the tree structure of the whole map.) |
| 64 |
|
| 65 |
The binary tree is stored on each FSM page as an array. Because the page |
| 66 |
header takes some space on a page, the binary tree isn't perfect. That is, |
| 67 |
a few right-most leaf nodes are missing, and there are some useless non-leaf |
| 68 |
nodes at the right. So the tree looks something like this: |
| 69 |
|
| 70 |
0 |
| 71 |
1 2 |
| 72 |
3 4 5 6 |
| 73 |
7 8 9 A B |
| 74 |
|
| 75 |
where the numbers denote each node's position in the array. Note that the |
| 76 |
tree is guaranteed complete above the leaf level; only some leaf nodes are |
| 77 |
missing. This is reflected in the number of usable "slots" per page not |
| 78 |
being an exact power of 2. |
| 79 |
|
| 80 |
A FSM page also has a next slot pointer, fp_next_slot, that determines where |
| 81 |
to start the next search for free space within that page. The reason for that |
| 82 |
is to spread out the pages that are returned by FSM searches. When several |
| 83 |
backends are concurrently inserting into a relation, contention can be avoided |
| 84 |
by having them insert into different pages. But it is also desirable to fill |
| 85 |
up pages in sequential order, to get the benefit of OS prefetching and batched |
| 86 |
writes. The FSM is responsible for making that happen, and the next slot |
| 87 |
pointer helps provide the desired behavior. |
| 88 |
|
| 89 |
Higher-level structure |
| 90 |
---------------------- |
| 91 |
|
| 92 |
To scale up the data structure described above beyond a single page, we |
| 93 |
maintain a similar tree-structure across pages. Leaf nodes in higher level |
| 94 |
pages correspond to lower level FSM pages. The root node within each page |
| 95 |
has the same value as the corresponding leaf node on its parent page. |
| 96 |
|
| 97 |
The root page is always stored at physical block 0. |
| 98 |
|
| 99 |
For example, assuming each FSM page can hold information about 4 pages (in |
| 100 |
reality, it holds (BLCKSZ - headers) / 2, or ~4000 with default BLCKSZ), |
| 101 |
we get a disk layout like this: |
| 102 |
|
| 103 |
0 <-- page 0 at level 2 (root page) |
| 104 |
0 <-- page 0 at level 1 |
| 105 |
0 <-- page 0 at level 0 |
| 106 |
1 <-- page 1 at level 0 |
| 107 |
2 <-- ... |
| 108 |
3 |
| 109 |
1 <-- page 1 at level 1 |
| 110 |
4 |
| 111 |
5 |
| 112 |
6 |
| 113 |
7 |
| 114 |
2 |
| 115 |
8 |
| 116 |
9 |
| 117 |
10 |
| 118 |
11 |
| 119 |
3 |
| 120 |
12 |
| 121 |
13 |
| 122 |
14 |
| 123 |
15 |
| 124 |
|
| 125 |
where the numbers are page numbers *at that level*, starting from 0. |
| 126 |
|
| 127 |
To find the physical block # corresponding to leaf page n, we need to |
| 128 |
count the number of leaf and upper-level pages preceding page n. |
| 129 |
This turns out to be |
| 130 |
|
| 131 |
y = n + (n / F + 1) + (n / F^2 + 1) + ... + 1 |
| 132 |
|
| 133 |
where F is the fanout (4 in the above example). The first term n is the number |
| 134 |
of preceding leaf pages, the second term is the number of pages at level 1, |
| 135 |
and so forth. |
| 136 |
|
| 137 |
To keep things simple, the tree is always constant height. To cover the |
| 138 |
maximum relation size of 2^32-1 blocks, three levels is enough with the default |
| 139 |
BLCKSZ (4000^3 > 2^32). |
| 140 |
|
| 141 |
Addressing |
| 142 |
---------- |
| 143 |
|
| 144 |
The higher-level routines operate on "logical" addresses, consisting of |
| 145 |
- level, |
| 146 |
- logical page number, and |
| 147 |
- slot (if applicable) |
| 148 |
|
| 149 |
Bottom level FSM pages have level of 0, the level above that 1, and root 2. |
| 150 |
As in the diagram above, logical page number is the page number at that level, |
| 151 |
starting from 0. |
| 152 |
|
| 153 |
Locking |
| 154 |
------- |
| 155 |
|
| 156 |
When traversing down to search for free space, only one page is locked at a |
| 157 |
time: the parent page is released before locking the child. If the child page |
| 158 |
is concurrently modified, and there no longer is free space on the child page |
| 159 |
when you land on it, you need to start from scratch (after correcting the |
| 160 |
parent page, so that you don't get into an infinite loop). |
| 161 |
|
| 162 |
We use shared buffer locks when searching, but exclusive buffer lock when |
| 163 |
updating a page. However, the next slot search pointer is updated during |
| 164 |
searches even though we have only a shared lock. fp_next_slot is just a hint |
| 165 |
and we can easily reset it if it gets corrupted; so it seems better to accept |
| 166 |
some risk of that type than to pay the overhead of exclusive locking. |
| 167 |
|
| 168 |
Recovery |
| 169 |
-------- |
| 170 |
|
| 171 |
The FSM is not explicitly WAL-logged. Instead, we rely on a bunch of |
| 172 |
self-correcting measures to repair possible corruption. |
| 173 |
|
| 174 |
First of all, whenever a value is set on an FSM page, the root node of the |
| 175 |
page is compared against the new value after bubbling up the change is |
| 176 |
finished. It should be greater than or equal to the value just set, or we |
| 177 |
have a corrupted page, with a parent somewhere with too small a value. |
| 178 |
Secondly, if we detect corrupted pages while we search, traversing down |
| 179 |
the tree. That check will notice if a parent node is set to too high a value. |
| 180 |
In both cases, the upper nodes on the page are immediately rebuilt, fixing |
| 181 |
the corruption so far as that page is concerned. |
| 182 |
|
| 183 |
VACUUM updates all the bottom-level FSM pages with the correct amount of free |
| 184 |
space on corresponding heap pages, as it proceeds through the heap. This |
| 185 |
goes through fsm_set_avail(), so that the upper nodes on those pages are |
| 186 |
immediately updated. Periodically, VACUUM calls FreeSpaceMapVacuum[Range] |
| 187 |
to propagate the new free-space info into the upper pages of the FSM tree. |
| 188 |
|
| 189 |
As a result when we write to the FSM we treat that as a hint and thus use |
| 190 |
MarkBufferDirtyHint() rather than MarkBufferDirty(). Every read here uses |
| 191 |
RBM_ZERO_ON_ERROR to bypass checksum mismatches and other verification |
| 192 |
failures. We'd operate correctly without the full page images that |
| 193 |
MarkBufferDirtyHint() provides, but they do decrease the chance of losing slot |
| 194 |
knowledge to RBM_ZERO_ON_ERROR. |
| 195 |
|
| 196 |
Relation extension is not WAL-logged. Hence, after WAL replay, an on-disk FSM |
| 197 |
slot may indicate free space in PageIsNew() blocks that never reached disk. |
| 198 |
We detect this case by comparing against the actual relation size, and we mark |
| 199 |
the block as full in that case. |
| 200 |
|
| 201 |
TODO |
| 202 |
---- |
| 203 |
|
| 204 |
- fastroot to avoid traversing upper nodes with just 1 child |
| 205 |
- use a different system for tables that fit into one FSM page, with a |
| 206 |
mechanism to switch to the real thing as it grows. |