Debian Codegraph @

DESIGN

raw
1 requirements
2 ------------
3
4 Objective: key-value store (hash, in Perl terms), with keys and values
5 all being strings, in memory shared between user processes, with no
6 reliance on user processes not hanging/crashing.
7
8 Keys and values may be restricted to octet strings, but handling arbitrary
9 Unicode strings would be a bonus.
10
11 The shared hash must not require explicit initialisation.
12
13 If a user process crashes or hangs, other processes must continue to
14 operate correctly.
15
16 A user process that has write permission can be trusted to write correctly
17 (although not to complete its write operations).
18
19 Read and write operations must be atomic.
20
21 The shared hash must not occupy many times more memory than necessary
22 for the data stored.
23
24 Read operations must be fast.
25
26 The shared hash must be efficient when it contains a large number of
27 small items.
28
29 The shared hash must be capable of handling large values.
30
31 principles
32 ----------
33
34 A shared hash will be referred to as a "shash".
35
36 There should be no requirement to lock anything in order to read from
37 the shash. This implies that all data representations larger than
38 a word must be functionally immutable: data written and published is
39 never overwritten.
40
41 This implies that memory cannot be reclaimed by overwriting. Memory can
42 only be reclaimed by being unlinked from the filesystem and unmapped by
43 all user processes. The shash must periodically migrate from one file
44 to another, in the manner of copying gc.
45
46 Writes must be completed by means of atomically replacing a root pointer,
47 using a conditional-set instruction. Writers must be prepared to retry,
48 in case another writer got in first. This mode of writing makes it easy
49 to implement high-level conditional setting, with a write occurring only
50 if some subset of the shash (up to all of it) is in an expected state.
51
52 A snapshot of the root pointer acts as a snapshot of the entire shash,
53 permitting reading of a consistent state. ACI semantics are readily
54 achieved.
55
56 For nice behaviour on SMP systems, data that will be frequently read
57 should where possible be separated from physically-mutable data, in
58 order to go in a separate cache line. (Physically-mutable data can
59 occur within functionally-immutable data structures.)
60
61 design
62 ------
63
64 The whole shash should be encapsulated as a single file. Since it can't
65 actually be just a single file (see below), it should be encapsulated
66 as a directory, which contains all the constituent files.
67
68 Encapsulation as a directory means that the shash can be referenced as
69 a single filesystem entity, can be renamed as a whole, and generally
70 basic filesystem operations work as desired. Provided that users of
71 the shash keep a file handle open on the directory and use openat(2)
72 et al on the constituent files, rather than repeatedly using a pathname
73 referring to the directory, open handles on the shash will continue to
74 work across the shash being renamed.
75
76 By having only regular files within the directory, other aspects
77 of filesystem regularity are achieved. The entire shash can live
78 on essentially any kind of filesystem, and deletion of a shash can
79 be accomplished by a standard means (rm -r). However, by virtue of
80 being a directory, the shash cannot be directly unlinked, nor can it
81 be multiply linked, or at least doing either of these would result in
82 filesystem irregularities. Renaming a shash cannot atomically replace
83 either a regular file or another shash.
84
85 There should be a single master file. It can be a single page and
86 never grow. It must contain a reference to the current data file.
87
88 Normally there will be only one data file active. The shash's root
89 pointer is contained in the current data file. Periodically the shash
90 content will be migrated from one data file to another, and during the
91 transition two data files will be active. The root pointer in one data
92 file can take a special form to indicate that handoff is in progress.
93
94 Within each data file, any user (being a potential writer) must be able
95 to allocate lines, which can be easily arranged as atomic modification
96 of a next-line counter. Allocating a line doesn't imply that it is,
97 or will be, usefully filled: the writer might crash or need to abort the
98 write attempt. After an abort, an allocated line can be reused by the
99 same writer for a later write attempt. It is only when data is published,
100 by changing the root pointer to point (directly or indirectly) at it,
101 that it must be well-formed and becomes immutable.
102
103 Structures are designed for 64-bit systems, and rely on having a 64-bit
104 conditional-set instruction. All sizes are inherently limited by 64-bit
105 addressing. The size terms that matter are:
106
107 * byte = octet = 8 bits
108
109 * word = 8 bytes = 64 bits
110
111 * line is some power of two number of bytes, at least one word
112
113 * page is some power of two number of bytes, at least one line
114
115 The line size is meant to match the native cache line size, and the
116 page size is meant to match the native memory page size. These are
117 64 bytes and 4096 bytes on current amd64 machines. These sizes are
118 parameters to the design. All users of a particular shash must agree
119 on these parameters.
120
121 All word quantities are in native byte order, and must be word-aligned.
122 They are to be treated as unsigned integers unless otherwise specified.
123
124 A pointer to a data object is represented as a word quantity. A pointer
125 can only be stored in a data file, and points to a word-aligned object
126 in the same file. It is represented as a byte offset from the start of
127 the data file, and so necessarily has its lowest three bits all zero.
128
129 A string (key or value) is represented as a structure consisting of a word
130 count of bytes in the string, immediately followed by the string's bytes,
131 followed by a NUL byte. (The terminating NUL is not part of the string,
132 but included to satisfy Perl's requirements for an SV buffer, so that an
133 SV can be constructed to represent the string without needing to copy the
134 string.) The string can contain octets of any value, including NUL; the
135 explicit length is the canonical way to determine where the string ends.
136 A string in the data file cannot contain anything that's not an octet
137 (or, via Perl's aliasing, a Latin-1 character).
138
139 A collection of keys and values is represented as a btree (actually a
140 B+-tree), in which the keys are sorted lexicographically. The maximum
141 number of entries in a btree node is a parameter to the design, called
142 MAXFANOUT, on which all users of a shash must agree. It must be odd,
143 and between 3 and 255 inclusive. (Lower limit is inherent in btree
144 structure; upper limit is to fit in a byte.) A suggested value for
145 it is 15. Each btree node except for the root node contains between
146 (MAXFANOUT+1)/2 and MAXFANOUT (inclusive) entries. The root node
147 contains between 2 and MAXFANOUT (inclusive) entries if there is at
148 least one layer of btree nodes below it, or between 0 and MAXFANOUT
149 (inclusive) entries if its entries are individual key/value pairs.
150 A btree node begins with a word header, in which bits are allocated thus:
151
152 0-5 layer (0 = pointing directly to key/value pairs)
153 6-7 zero padding
154 8-15 fanout (range 0 to MAXFANOUT inclusive)
155 16-63 zero padding
156
157 (Note: six bits for the layer number is enough to accommodate the maximum
158 possible number of addressable nodes in a btree with the minimum possible
159 fanout. Trees in practice are unlikely to get anywhere near this height.)
160
161 The node header is immediately followed by an array of entries, as
162 many as indicated by the header. Each entry consists of two words.
163 The first word is a pointer to a string object representing the first
164 (lexicographically earliest) key in the collection represented by the
165 entry. The second word is a pointer to either a btree node of the next
166 layer down (if this node is not level zero) or a string representing a
167 value (if this node is level zero). The key to which the entry refers
168 is either the first key in the collection represented by the subnode,
169 or the key under which the value is stored, respectively.
170
171 String and btree node objects are permitted to be multiply referenced.
172 (The key arrangement implies that a btree node cannot appear more than
173 once in a single tree, but it is expected that nodes will appear in
174 multiple trees.) It is also permitted for their representations to
175 overlap, with each other or even with the file header, provided that
176 they do not use lines that contain mutable data. (Overlapping isn't
177 very useful, except that the empty btree node and empty string, whose
178 representations are all-bits-zero, can sensibly be aliased to padding
179 in the header.)
180
181 For compatibility checking purposes, the design parameters (other than
182 endianness) are encapsulated as a word quantity, in which bits are
183 allocated thus:
184
185 0-7 log2(line/byte)
186 8-15 log2(page/byte)
187 16-23 MAXFANOUT
188 24-63 zero padding
189
190 If, in the future, there is any change in the file formats, it should be
191 indicated by setting bits in what is currently zero padding. This might
192 be formulated as setting bit flags, or as changing a version number.
193 ext2's concept of readonly-compatible changes may be useful, but
194 comprehensibility of a shash to old code is not generally a priority.
195
196 A data file begins with this header:
197
198 * word: magic number 0xc693dac5ed5e47c2
199
200 * word: design parameters
201
202 * word: total file length in bytes (must be page-aligned, and
203 must match physical file length)
204
205 * zero pad to line alignment
206
207 * word: offset of next point in file that may be allocated (must
208 be line-aligned; if equal to total file length then the file
209 is full)
210
211 * zero pad to line alignment
212
213 * word: root pointer and handoff flag (see notes below)
214
215 * zero pad to line alignment
216
217 The earliest point at which the next-allocation word can point is the
218 end of the header.
219
220 A process wishing to write data into the file must allocate space for
221 it by (atomically) moving the next-allocation pointer. It owns the
222 lines located between the old and new positions of the pointer. It may
223 initially write arbitrarily to lines that it owns. However, once a line
224 has been made reachable from the root pointer (by containing (part of)
225 a reachable object), that line must not be written to again, even if it
226 later becomes unreachable from the root. (It remains reachable to anyone
227 who read the root pointer when it was reachable.) A process may give
228 back allocated lines, by moving the next-allocation pointer backwards.
229 Such lines must not have been made reachable (i.e., must still be legal
230 to write to), and (due to the single allocation pointer arrangement)
231 can only be given back when they immediately precede the current
232 next-allocation position.
233
234 There are no restrictions on the content of file space that is neither
235 part of the header nor has ever been part of a reachable object.
236 This includes parts of reachable lines that don't form objects, lines
237 owned by some process that have not been made reachable, and the unowned
238 lines following the next-allocation position.
239
240 A data file is identified, among the data files in a single shash, by a
241 word quantity. Identifier zero has special significance, and identifiers
242 are otherwise assigned sequentially by means described below. Data file
243 identifiers are permitted to wrap. This design does not protect against
244 race conditions that span a large fraction of a data file identifier
245 cycle.
246
247 The root pointer word contains both a pointer and a one-bit flag to
248 control handoff. The handoff flag is bit 0, and the rest of the word must
249 be a valid pointer (with bits 1 and 2 necessarily zero). The pointer is
250 read by masking off the handoff flag from the word. The shash's root is
251 pointed to by the pointer part of the root pointer word in the current
252 data file. The handoff flag governs how a root can be superseded.
253
254 When the handoff flag is clear, a process wishing to replace the shash
255 root does so by atomically modifying the root pointer word to point to
256 the new root node in the same data file. If a process finds that there
257 is insufficient space in the data file for the data it wants to write,
258 it must initiate handoff, by atomically setting the handoff flag (without
259 changing the root pointer). When the handoff flag has been set, the root
260 pointer word in this data file must not be changed again; the root can
261 then only be replaced by superseding the data file with a new data file.
262
263 The master file has this form:
264
265 * word: magic number 0xa58afd185cbf5af7
266
267 * word: design parameters
268
269 * zero pad to line alignment
270
271 * word: last-allocated data file identifier
272
273 * zero pad to line alignment
274
275 * word: identifier of current data file
276
277 * zero pad to page alignment
278
279 The data files and master file are arranged in a directory. The
280 directory provides the identity of the shash. The master file is named
281 "iNmv0,m\$%3". The data files are each named "&\"JBLMEgGm" followed by
282 their identifier as 16 lowercase hexadecimal digits. Temporary files
283 created during shash creation can exist in the directory with names
284 beginning "DNaM6okQi;". Files whose names begin with "." may also exist
285 in the directory, and are not part of shash operations: they may be
286 created by revision control systems and the like. No other filenames
287 may exist in the directory.
288
289 When the handoff flag in the current data file is clear, the choice
290 of current data file referenced by the master file cannot be changed.
291 The shash root can then only be changed by modifying the root pointer
292 word in the current data file. To supersede the current data file,
293 the handoff flag in its root pointer word must first be set. When the
294 handoff flag in the current data file is set, the choice of current data
295 file referenced by the master file may be atomically changed.
296
297 When the handoff flag in the current data file is set, a process wishing
298 to replace the shash root does so by creating a new data file with the
299 new data and atomically changing the master file to refer to it as the
300 current data file. The process that does this successfully is expected
301 to then unlink the old data file. A process that creates a new data
302 file and fails to install it is expected to unlink its failed data file.
303
304 The data file identifier zero has a special meaning. Rather than
305 referring to a real data file, if it is current it means that the
306 shash is empty. The zero data file can always be superseded by
307 atomically changing the current file identifier to refer to a real file.
308 Effectively, the zero data file is one in which the root pointer always
309 refers to an empty btree and the handoff flag is always set.
310
311 When a process wishes to create a new data file, as a prospective
312 replacement for the current data file, it must first assign an identifier
313 for it. This is done by atomically adding one to the "last-allocated data
314 file identifier" word in the master file. This word should initially
315 be zero in a new shash. After incrementing the word, the incremented
316 value is the assigned identifier owned by the incrementing process.
317 If the word reaches all-bits-one (2^63 - 1), the next process wanting
318 a data file identifier must `increment' it to 1, skipping the special
319 identifier 0. Allocating a data file identifier only grants permission
320 to create a file with the allocated identifier; it does not inherently
321 put the file into use, and does not mean that the file will necessarily
322 ever be the shash's current data file.
323
324 A new data file should be created directly with its proper data file name.
325 This means that it will initially not have the format of a complete data
326 file. This is permitted. A data file (file with data-style filename)
327 is required to be well-formed if and only if it is, or has previously
328 been, current. A process other than the data file's creator cannot
329 allocate space in the file, and must not write to it, unless it is,
330 or has been, current.
331
332 When superseding the current data file, the current file identifier
333 must only be increased, aside from when the file identifiers wrap.
334 The current file identifier does not have to increase only to the next
335 possible identifier; it is permitted to skip identifiers. It is normal
336 to skip identifiers where concurrent processes are each attempting to
337 switch data file, so that they have competing new files of which only
338 one will be installed. It is never permitted to switch to the special
339 data file identifier zero; that can only be current in a new shash to
340 which content has never been written.
341
342 Creation of a shash is unavoidably non-atomic, but by following a
343 protocol it can pretend to be atomic. A writer that wants to create
344 a shash must be willing not only to create from scratch, but also
345 to resume an incomplete creation, and to cooperate with simultaneous
346 creators. To create a shash, it is necessary to create the directory,
347 then the master file. The master file must be written as a temporary
348 file and then atomically moved into place (using link(2) semantics to
349 avoid replacing a file already in place). Any file in place with the
350 master filename must be a well-formed master file. The master file
351 must initially use the special data file identifier zero as the current
352 data file identifier. Creators must accept directory creation having
353 already happened. The creator that is credited with creating the shash
354 is the one that put the master file into place, which must be the last
355 step of creation. Data files must not be created until the master file
356 is in place to manage data file identifier allocation.
357
358 It follows from the above protocol that certain files in the shash
359 directory can be identified as obsolete. Specifically, any temporary
360 file is obsolete once the master file exists, and any data file whose
361 identifier (modulo wrapping) is below that of the current data file
362 is obsolete. Normally these files should be cleaned up by the process
363 that created them or (in the case of a formerly-current data file) the
364 process that superseded them. However, if a process gets interrupted,
365 an obsolete file might persist. Any writer may unlink any identifiably
366 obsolete file, and it is encouraged to periodically do this.
367
368 If a process wishes to allocate space for temporary data as part of
369 a shash, it can create a file in the shash directory and immediately
370 unlink it. It should be unlinked as soon as it no longer needs to have
371 a name. There are two options for the filename. Firstly, a data file
372 identifier can be allocated, and the resulting data filename used.
373 It is not necessary that the file at all resemble a shash data file
374 in its format or usage. Secondly, a temporary filename can be used,
375 at the risk of collision with other processes. A temporary filename
376 is always interpreted as obsolete in a fully-created shash, and so is
377 liable to be unlinked immediately by another process.
378
379 compatibility
380 -------------
381
382 The design inherently requires that the OS support mmap(2), and that the
383 CPU support atomic reading and conditional writing of 64-bit quantities.
384 When implementing in C, the compiler must provide a 64-bit data type,
385 and must support the atomic operations on it. The Intel-specified
386 built-in __sync_bool_compare_and_swap() suffices for conditional setting;
387 inline assembler and library functions are other possible approaches.
388 Clean filename resolution semantics for shared hashes requires that the
389 OS support openat(2) et al.