src/backend/storage/freespace/README

   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. As a result when
 173 we write to the FSM we treat that as a hint and thus use MarkBufferDirtyHint()
 174 rather than MarkBufferDirty().
 175
 176 First of all, whenever a value is set on an FSM page, the root node of the
 177 page is compared against the new value after bubbling up the change is
 178 finished. It should be greater than or equal to the value just set, or we
 179 have a corrupted page, with a parent somewhere with too small a value.
 180 Secondly, if we detect corrupted pages while we search, traversing down
 181 the tree. That check will notice if a parent node is set to too high a value.
 182 In both cases, the upper nodes on the page are immediately rebuilt, fixing
 183 the corruption so far as that page is concerned.
 184
 185 VACUUM updates all the bottom-level FSM pages with the correct amount of free
 186 space on corresponding heap pages, as it proceeds through the heap.  This
 187 goes through fsm_set_avail(), so that the upper nodes on those pages are
 188 immediately updated.  Periodically, VACUUM calls FreeSpaceMapVacuum[Range]
 189 to propagate the new free-space info into the upper pages of the FSM tree.
 190
 191 TODO
 192 ----
 193
 194 - fastroot to avoid traversing upper nodes with just 1 child
 195 - use a different system for tables that fit into one FSM page, with a
 196   mechanism to switch to the real thing as it grows.