← Back to branch summary

~ubuntu-branches/ubuntu/hardy/postgresql-8.4/hardy-backports

« back to all changes in this revision

Viewing changes to src/backend/storage/freespace/README

  • Committer: Bazaar Package Importer
  • Author(s): Martin Pitt
  • Date: 2009-03-20 12:00:13 UTC
  • Revision ID: james.westby@ubuntu.com-20090320120013-hogj7egc5mjncc5g
Tags: upstream-8.4~0cvs20090328
Import upstream version 8.4~0cvs20090328

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/backend/storage/freespace/README
 
1
$PostgreSQL$
 
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 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.
 
182
 
 
183
Vacuum updates all the bottom level pages with correct amount of free space
 
184
on the heap pages, fixing any outdated values there. After the heap and
 
185
index passes are done, FreeSpaceMapVacuum is called, and the FSM tree is
 
186
scanned in depth-first order. This fixes any discrepancies between upper
 
187
and lower level FSM pages.
 
188
 
 
189
TODO
 
190
----
 
191
 
 
192
- fastroot to avoid traversing upper nodes with just 1 child
 
193
- use a different system for tables that fit into one FSM page, with a
 
194
  mechanism to switch to the real thing as it grows.
 
195