requirements ------------ Objective: key-value store (hash, in Perl terms), with keys and values all being strings, in memory shared between user processes, with no reliance on user processes not hanging/crashing. Keys and values may be restricted to octet strings, but handling arbitrary Unicode strings would be a bonus. The shared hash must not require explicit initialisation. If a user process crashes or hangs, other processes must continue to operate correctly. A user process that has write permission can be trusted to write correctly (although not to complete its write operations). Read and write operations must be atomic. The shared hash must not occupy many times more memory than necessary for the data stored. Read operations must be fast. The shared hash must be efficient when it contains a large number of small items. The shared hash must be capable of handling large values. principles ---------- A shared hash will be referred to as a "shash". There should be no requirement to lock anything in order to read from the shash. This implies that all data representations larger than a word must be functionally immutable: data written and published is never overwritten. This implies that memory cannot be reclaimed by overwriting. Memory can only be reclaimed by being unlinked from the filesystem and unmapped by all user processes. The shash must periodically migrate from one file to another, in the manner of copying gc. Writes must be completed by means of atomically replacing a root pointer, using a conditional-set instruction. Writers must be prepared to retry, in case another writer got in first. This mode of writing makes it easy to implement high-level conditional setting, with a write occurring only if some subset of the shash (up to all of it) is in an expected state. A snapshot of the root pointer acts as a snapshot of the entire shash, permitting reading of a consistent state. ACI semantics are readily achieved. For nice behaviour on SMP systems, data that will be frequently read should where possible be separated from physically-mutable data, in order to go in a separate cache line. (Physically-mutable data can occur within functionally-immutable data structures.) design ------ The whole shash should be encapsulated as a single file. Since it can't actually be just a single file (see below), it should be encapsulated as a directory, which contains all the constituent files. Encapsulation as a directory means that the shash can be referenced as a single filesystem entity, can be renamed as a whole, and generally basic filesystem operations work as desired. Provided that users of the shash keep a file handle open on the directory and use openat(2) et al on the constituent files, rather than repeatedly using a pathname referring to the directory, open handles on the shash will continue to work across the shash being renamed. By having only regular files within the directory, other aspects of filesystem regularity are achieved. The entire shash can live on essentially any kind of filesystem, and deletion of a shash can be accomplished by a standard means (rm -r). However, by virtue of being a directory, the shash cannot be directly unlinked, nor can it be multiply linked, or at least doing either of these would result in filesystem irregularities. Renaming a shash cannot atomically replace either a regular file or another shash. There should be a single master file. It can be a single page and never grow. It must contain a reference to the current data file. Normally there will be only one data file active. The shash's root pointer is contained in the current data file. Periodically the shash content will be migrated from one data file to another, and during the transition two data files will be active. The root pointer in one data file can take a special form to indicate that handoff is in progress. Within each data file, any user (being a potential writer) must be able to allocate lines, which can be easily arranged as atomic modification of a next-line counter. Allocating a line doesn't imply that it is, or will be, usefully filled: the writer might crash or need to abort the write attempt. After an abort, an allocated line can be reused by the same writer for a later write attempt. It is only when data is published, by changing the root pointer to point (directly or indirectly) at it, that it must be well-formed and becomes immutable. Structures are designed for 64-bit systems, and rely on having a 64-bit conditional-set instruction. All sizes are inherently limited by 64-bit addressing. The size terms that matter are: * byte = octet = 8 bits * word = 8 bytes = 64 bits * line is some power of two number of bytes, at least one word * page is some power of two number of bytes, at least one line The line size is meant to match the native cache line size, and the page size is meant to match the native memory page size. These are 64 bytes and 4096 bytes on current amd64 machines. These sizes are parameters to the design. All users of a particular shash must agree on these parameters. All word quantities are in native byte order, and must be word-aligned. They are to be treated as unsigned integers unless otherwise specified. A pointer to a data object is represented as a word quantity. A pointer can only be stored in a data file, and points to a word-aligned object in the same file. It is represented as a byte offset from the start of the data file, and so necessarily has its lowest three bits all zero. A string (key or value) is represented as a structure consisting of a word count of bytes in the string, immediately followed by the string's bytes, followed by a NUL byte. (The terminating NUL is not part of the string, but included to satisfy Perl's requirements for an SV buffer, so that an SV can be constructed to represent the string without needing to copy the string.) The string can contain octets of any value, including NUL; the explicit length is the canonical way to determine where the string ends. A string in the data file cannot contain anything that's not an octet (or, via Perl's aliasing, a Latin-1 character). A collection of keys and values is represented as a btree (actually a B+-tree), in which the keys are sorted lexicographically. The maximum number of entries in a btree node is a parameter to the design, called MAXFANOUT, on which all users of a shash must agree. It must be odd, and between 3 and 255 inclusive. (Lower limit is inherent in btree structure; upper limit is to fit in a byte.) A suggested value for it is 15. Each btree node except for the root node contains between (MAXFANOUT+1)/2 and MAXFANOUT (inclusive) entries. The root node contains between 2 and MAXFANOUT (inclusive) entries if there is at least one layer of btree nodes below it, or between 0 and MAXFANOUT (inclusive) entries if its entries are individual key/value pairs. A btree node begins with a word header, in which bits are allocated thus: 0-5 layer (0 = pointing directly to key/value pairs) 6-7 zero padding 8-15 fanout (range 0 to MAXFANOUT inclusive) 16-63 zero padding (Note: six bits for the layer number is enough to accommodate the maximum possible number of addressable nodes in a btree with the minimum possible fanout. Trees in practice are unlikely to get anywhere near this height.) The node header is immediately followed by an array of entries, as many as indicated by the header. Each entry consists of two words. The first word is a pointer to a string object representing the first (lexicographically earliest) key in the collection represented by the entry. The second word is a pointer to either a btree node of the next layer down (if this node is not level zero) or a string representing a value (if this node is level zero). The key to which the entry refers is either the first key in the collection represented by the subnode, or the key under which the value is stored, respectively. String and btree node objects are permitted to be multiply referenced. (The key arrangement implies that a btree node cannot appear more than once in a single tree, but it is expected that nodes will appear in multiple trees.) It is also permitted for their representations to overlap, with each other or even with the file header, provided that they do not use lines that contain mutable data. (Overlapping isn't very useful, except that the empty btree node and empty string, whose representations are all-bits-zero, can sensibly be aliased to padding in the header.) For compatibility checking purposes, the design parameters (other than endianness) are encapsulated as a word quantity, in which bits are allocated thus: 0-7 log2(line/byte) 8-15 log2(page/byte) 16-23 MAXFANOUT 24-63 zero padding If, in the future, there is any change in the file formats, it should be indicated by setting bits in what is currently zero padding. This might be formulated as setting bit flags, or as changing a version number. ext2's concept of readonly-compatible changes may be useful, but comprehensibility of a shash to old code is not generally a priority. A data file begins with this header: * word: magic number 0xc693dac5ed5e47c2 * word: design parameters * word: total file length in bytes (must be page-aligned, and must match physical file length) * zero pad to line alignment * word: offset of next point in file that may be allocated (must be line-aligned; if equal to total file length then the file is full) * zero pad to line alignment * word: root pointer and handoff flag (see notes below) * zero pad to line alignment The earliest point at which the next-allocation word can point is the end of the header. A process wishing to write data into the file must allocate space for it by (atomically) moving the next-allocation pointer. It owns the lines located between the old and new positions of the pointer. It may initially write arbitrarily to lines that it owns. However, once a line has been made reachable from the root pointer (by containing (part of) a reachable object), that line must not be written to again, even if it later becomes unreachable from the root. (It remains reachable to anyone who read the root pointer when it was reachable.) A process may give back allocated lines, by moving the next-allocation pointer backwards. Such lines must not have been made reachable (i.e., must still be legal to write to), and (due to the single allocation pointer arrangement) can only be given back when they immediately precede the current next-allocation position. There are no restrictions on the content of file space that is neither part of the header nor has ever been part of a reachable object. This includes parts of reachable lines that don't form objects, lines owned by some process that have not been made reachable, and the unowned lines following the next-allocation position. A data file is identified, among the data files in a single shash, by a word quantity. Identifier zero has special significance, and identifiers are otherwise assigned sequentially by means described below. Data file identifiers are permitted to wrap. This design does not protect against race conditions that span a large fraction of a data file identifier cycle. The root pointer word contains both a pointer and a one-bit flag to control handoff. The handoff flag is bit 0, and the rest of the word must be a valid pointer (with bits 1 and 2 necessarily zero). The pointer is read by masking off the handoff flag from the word. The shash's root is pointed to by the pointer part of the root pointer word in the current data file. The handoff flag governs how a root can be superseded. When the handoff flag is clear, a process wishing to replace the shash root does so by atomically modifying the root pointer word to point to the new root node in the same data file. If a process finds that there is insufficient space in the data file for the data it wants to write, it must initiate handoff, by atomically setting the handoff flag (without changing the root pointer). When the handoff flag has been set, the root pointer word in this data file must not be changed again; the root can then only be replaced by superseding the data file with a new data file. The master file has this form: * word: magic number 0xa58afd185cbf5af7 * word: design parameters * zero pad to line alignment * word: last-allocated data file identifier * zero pad to line alignment * word: identifier of current data file * zero pad to page alignment The data files and master file are arranged in a directory. The directory provides the identity of the shash. The master file is named "iNmv0,m\$%3". The data files are each named "&\"JBLMEgGm" followed by their identifier as 16 lowercase hexadecimal digits. Temporary files created during shash creation can exist in the directory with names beginning "DNaM6okQi;". Files whose names begin with "." may also exist in the directory, and are not part of shash operations: they may be created by revision control systems and the like. No other filenames may exist in the directory. When the handoff flag in the current data file is clear, the choice of current data file referenced by the master file cannot be changed. The shash root can then only be changed by modifying the root pointer word in the current data file. To supersede the current data file, the handoff flag in its root pointer word must first be set. When the handoff flag in the current data file is set, the choice of current data file referenced by the master file may be atomically changed. When the handoff flag in the current data file is set, a process wishing to replace the shash root does so by creating a new data file with the new data and atomically changing the master file to refer to it as the current data file. The process that does this successfully is expected to then unlink the old data file. A process that creates a new data file and fails to install it is expected to unlink its failed data file. The data file identifier zero has a special meaning. Rather than referring to a real data file, if it is current it means that the shash is empty. The zero data file can always be superseded by atomically changing the current file identifier to refer to a real file. Effectively, the zero data file is one in which the root pointer always refers to an empty btree and the handoff flag is always set. When a process wishes to create a new data file, as a prospective replacement for the current data file, it must first assign an identifier for it. This is done by atomically adding one to the "last-allocated data file identifier" word in the master file. This word should initially be zero in a new shash. After incrementing the word, the incremented value is the assigned identifier owned by the incrementing process. If the word reaches all-bits-one (2^63 - 1), the next process wanting a data file identifier must `increment' it to 1, skipping the special identifier 0. Allocating a data file identifier only grants permission to create a file with the allocated identifier; it does not inherently put the file into use, and does not mean that the file will necessarily ever be the shash's current data file. A new data file should be created directly with its proper data file name. This means that it will initially not have the format of a complete data file. This is permitted. A data file (file with data-style filename) is required to be well-formed if and only if it is, or has previously been, current. A process other than the data file's creator cannot allocate space in the file, and must not write to it, unless it is, or has been, current. When superseding the current data file, the current file identifier must only be increased, aside from when the file identifiers wrap. The current file identifier does not have to increase only to the next possible identifier; it is permitted to skip identifiers. It is normal to skip identifiers where concurrent processes are each attempting to switch data file, so that they have competing new files of which only one will be installed. It is never permitted to switch to the special data file identifier zero; that can only be current in a new shash to which content has never been written. Creation of a shash is unavoidably non-atomic, but by following a protocol it can pretend to be atomic. A writer that wants to create a shash must be willing not only to create from scratch, but also to resume an incomplete creation, and to cooperate with simultaneous creators. To create a shash, it is necessary to create the directory, then the master file. The master file must be written as a temporary file and then atomically moved into place (using link(2) semantics to avoid replacing a file already in place). Any file in place with the master filename must be a well-formed master file. The master file must initially use the special data file identifier zero as the current data file identifier. Creators must accept directory creation having already happened. The creator that is credited with creating the shash is the one that put the master file into place, which must be the last step of creation. Data files must not be created until the master file is in place to manage data file identifier allocation. It follows from the above protocol that certain files in the shash directory can be identified as obsolete. Specifically, any temporary file is obsolete once the master file exists, and any data file whose identifier (modulo wrapping) is below that of the current data file is obsolete. Normally these files should be cleaned up by the process that created them or (in the case of a formerly-current data file) the process that superseded them. However, if a process gets interrupted, an obsolete file might persist. Any writer may unlink any identifiably obsolete file, and it is encouraged to periodically do this. If a process wishes to allocate space for temporary data as part of a shash, it can create a file in the shash directory and immediately unlink it. It should be unlinked as soon as it no longer needs to have a name. There are two options for the filename. Firstly, a data file identifier can be allocated, and the resulting data filename used. It is not necessary that the file at all resemble a shash data file in its format or usage. Secondly, a temporary filename can be used, at the risk of collision with other processes. A temporary filename is always interpreted as obsolete in a fully-created shash, and so is liable to be unlinked immediately by another process. compatibility ------------- The design inherently requires that the OS support mmap(2), and that the CPU support atomic reading and conditional writing of 64-bit quantities. When implementing in C, the compiler must provide a 64-bit data type, and must support the atomic operations on it. The Intel-specified built-in __sync_bool_compare_and_swap() suffices for conditional setting; inline assembler and library functions are other possible approaches. Clean filename resolution semantics for shared hashes requires that the OS support openat(2) et al.