| 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. |