|
Everett
|
The README starts with the recommended named session API. The connection guide covers mutable commands, asynchronous tickets, snapshots and forks. This guide goes underneath that API to file construction, explicit updates and merges, then explains representation and tuning choices. We keep the same policy from input records to mapped queries.
For an ordinary byte-aligned string table on ARM, import everett.neon and everett.sqlite and use everett::multiverse<everett::neon_policy<>>. On x86, select the corresponding AVX2 module and policy. The baseline everett::multiverse<> uses the same encoding with scalar execution. The byte table guide covers its raw string framing, schema and measured tradeoffs.
For a bit table, select the policy explicitly:
This uses the bit registry and order-zero exponential-Golomb backspaces, with the same connection, snapshot and transaction operations. Choose its matching policy when reopening the store; a policy choice does not convert existing files. I use bytes as the starting point and measure the whole workload before choosing bit packing for space. Sorts with bit-oriented keys can declare that grammar directly.
For low-level encoded blobs, use a sort exposing using encoding = byte_encoding<> for byte strings, or bit_encoding<> for packed bits, then use storage_policy<tip<YourSort>>. The registry derives the storage units from its sorts. Both encodings default to variable values, 15:1 sampling and physical blocks of 15 records; bit backspaces use order-zero exponential-Golomb.
The persistent workflow has three parts: build immutable table files, publish a root in the catalog, and open that root through a multiverse. Naming another save of a registered root only retains it; it does not serialize the table again. The catalog keeps its small mutable records in SQLite, while queries read the key/value files through mmap.
Link this program with everett::sqlite. Run example create /path/to/store once, then example read /path/to/store in another process. The backing directory must already exist; the application establishes its durability before creating the catalog. The create mode expects a fresh store. Its fixed identities are for this example only: allocate fresh object, attempt and operation identities for new work in an application.
The reader acquires its pin before opening the files. Registration uses the normal metadata checks, trusting the contents produced by our encoders; pass catalog_admission::scan when admission should verify the complete contents. The two-entry table fits the default fifteen-entry search head. A larger table needs a prepared chain, including its routing prefix, before publication.
The catalog guide gives the reservation, sealing and registration calls. For more than fifteen entries, prepare a root with query_root<P>::build and persist every pair in its chain; see the mapped example. For incremental output, follow the streamed timeline example. The COLA store example adds two-route indexes and publishes a merge while the old saved states remain readable.
Each C++ example below is a complete program. Include the component you use and link the CMake interface target described under building.
Policies make representation choices visible in types. Arrays, blobs, indexes, and files that share a policy agree on the units used by their metadata.
variable_values selects independently framed values in a leaf encoding. For several sorts, use bin<L,R> or sort_list<S...> and reserve holes with sort_undefined; sort registries explains dispatch and extension. Existing files retain their own value widths when a new sort broadens the registry. bit_string owns a packed string; bit_view borrows one and can describe a range beginning inside a byte. Keep the owner alive while using its view.
Provide strictly increasing native keys and nondecreasing borrowed keys. This small example fits in one group, so its first key supplies the known boundary context for search_window.
search_window is the local navigation operation: its caller supplies a group and the known boundary context. Its projected native and borrowed intervals share one K-entry budget. For sequential access, use blob.native().view().cursor(); a cursor's peek() exposes its reconstructed key and an original-payload value view.
Sampling includes both streams. Here the two equal borrowed delta keys remain separate occurrences after the native delta.
Repeated peeks leave the cursor where it is. A sampled key view lasts until advance, move, or destruction; copy the key when retaining it beyond that point. The sampler's target() retains the exact pair independently of the caller's original handle.
The pipeline starts at an existing target and works outward through the supplied native stages. The final stage becomes the new head. This example also destroys the pipeline and its original input handles before checking the result's retained target.
The borrowed indexes are new; the native allocation at the head is the same one supplied for the final stage. Intermediate sampled catalogs are passed through the pipeline as bounded queues. Finalized pairs own their exact downstream relationships, allowing older and newer chains to coexist.
A query starts from a prepared root. If the head already fits in one group, preparation retains it as-is. Otherwise, I add empty-native routing catalogs above it until the new head fits. Those catalogs contain successively sparser samples and retain the existing chain. Preparation scans the original head; we do that once and reuse the root for subsequent queries.
query_root<policy>::build(head) is the eager preparation convenience. A cursor owns its query key and pins the unvisited chain, so it can outlive the original handles. step(budget) visits at most that many catalogs and stops when a match is ready. take_match() returns an owned value, native ordinal and exact source pair; a pending match pauses further traversal until it is taken.
Matches arrive from head toward target. That order describes the index chain; the caller supplies any replacement or arrow-composition semantics. A native match does not suppress routing to later matches. Query steps bound catalog visits, not reconstructed bytes or value-copy cost. The query contract describes preparation, trust and work bounds.
Use reference_world to exercise the update semantics with byte-string keys and unsigned 64-bit values. Each batch is prepared against the same base. Partition ownership determines which keys it may change; different workers may read that base while preparing their assigned writes.
Admission checks old values, partition ownership, overlap, and the advertised fingerprint contribution. Identical batch replay is recognized. Calls to a receiver's apply() are serialized; preparing disjoint batches can happen independently. snapshot() shares the existing immutable state; compaction preserves both the resolved entries and their fingerprint.
The reference model also has a .rc debug dump for inspecting or round-tripping all live entries. This is a debugging feature, not an intended access pattern; ordinary saves retain object roots through the catalog. See debug dumps.
profile_native_writer<P> accepts records one at a time. We choose a common value width before writing, or let each value carry its own length. Finishing produces an ordinary front-coded array with its sparse offset directory. profile_blob<P>::adopt_native turns it into a terminal pair without decoding or rewriting the native data.
The merge builder consumes two sorted native streams, older then newer. Its default equal-key operation takes the newer value:
A custom compose(key, older, newer) can combine encoded arrows instead. Its result may own its bits or borrow a view until the writer consumes it. With associative composition, we can change the merge parentheses while keeping each key's update order. One step unit resolves one distinct key; string work, composition and final EF construction have separate costs. The builder retains its source owners, and a failed step cannot publish a partial result. See native writing and merging for mapped inputs, value-width rules and the continuation's exact limits.
For output larger than memory, native_file_writer and native_file_merge stream their payload into a reserved private file and return a seal receipt at completion. They retain sparse offsets until final Elias–Fano construction. The streamed timeline example combines this path with mapped inputs, a new terminal index and persistent timeline publication.
The custom object kinds are .kv and .index. Physical identities use 32 lowercase hexadecimal digits, split into paths such as ab/cd/0123456789abcdef0123456789abcd.kv. The two directory prefixes are removed from the leaf name. Logical keys never become filesystem paths.
mapped_file provides read-only shared ownership of an opened regular file. Bounded slices retain the mapping after the original owner is released. file<P>::open(path) checks the 96-byte header and exact file extent, including magic, version, policy and header CRC32C, without reading the body. An explicit file<P>::scan() checks the whole body's CRC32C and bit padding when recovery or a scrub calls for it. Opening an object does not certify its payload. multiverse<P> opens these objects beneath an existing backing directory and exposes their associated policy-bound types.
encode_native_sections and encode_index_sections package the existing encoded arrays into portable file sections. They borrow the arrays while writing: we do not front-code the keys again or rebuild Elias–Fano. A prepared query chain can then be reopened with multiverse<P>::open_query(saved_head_identity). Its mapped_query_root retains the exact native/index mappings and uses the same bounded cursor operations as the in-memory root. Typed opening reads fixed metadata; mapped_blob::scan() explicitly verifies contents, navigation and exact downstream samples. See mapped blobs for the layout, lifetime and trust contracts.
We can also build a new index directly over a retained mapped_native<P>. index_builder<P, mapped_native<P>> leaves its FC bytes and sparse offsets in place; finish_index returns the new borrowed stream and navigation structures as a profile_index<P>. sample_cursor<P, mapped_blob<P>> supplies samples from an exact mapped target. For a terminal pair, profile_index<P>::native_only constructs the zero directories from the native count without reading its keys. See sampling for ownership and target-validation contracts.
file_index_builder<P, mapped_native<P>> sends the borrowed stream directly to a private .index attempt. file_index_pipeline<P> builds several links together, passing front-coded samples through bounded queues and sealing the results from target to head. The file-index example constructs and queries a complete mapped chain without collecting its borrowed payloads in memory.
multiverse<P>::seal_object writes a body under caller-reserved object and attempt identities. It accepts a contiguous span or borrowed chunks, including mmap-backed input. The writer computes CRC32C while streaming, seals a private file, installs its name without replacing an existing object, and flushes the directory chain. A failed operation retains surviving outputs and reports its identities and last acknowledged stage. The sealing protocol spells out Linux/macOS barriers and the caller's recovery obligations. Sealing an object produces the receipt that sqlite_catalog::record_sealed records before the pair is registered and saved.
object_stream<P> accepts body chunks across calls when the final extent is not yet known. It can reserve a directory prefix and fill it at completion; CRC combination accounts for that replacement without rereading the body. An unfinished stream retains a private attempt, and finish seals it using the same persistence protocol.
For already trusted objects, pass file_open_mode::trusted to open, from_slice, or multiverse<P>::open_object. This avoids reading even the header page. body() returns the physical bytes after the 96-byte envelope; requesting header() explicitly reads and validates the metadata, returning it by value. scan() still performs full validation. Trusted opening assumes the caller already knows the object's type, policy and format; checked opening is the default.
The optional sqlite_catalog<P> reserves objects before writing, records their seal receipts, registers exact query chains and retains named saves, timeline generations and reader pins. We can close it, reopen a save and query its mmap chain. Enable EVERETT_ENABLE_SQLITE and link everett::sqlite; the ordinary core target has no SQLite dependency. The working catalog guide gives a complete publication/reopen example and explains operation replay and failed commits. Timelines support conditional publication and forks from exact historical generations; a stale publication returns the observed head, and replay returns that same outcome. Generations currently retain their pins. The catalog design covers retirement and merge progress. This leaves two immutable object kinds for us to manage. The durability protocol orders verified output, durable publication, and old-pin release, with explicit recovery states after failed synchronization.
A native blob holds sorted key/value records. A fractional index holds selected keys borrowed from a particular target. Together they form a searchable pair. A world is one logical state, retaining a collection of objects. A timeline describes successive worlds; a branch point retains a place from which another timeline can grow. The multiverse holds the backing store. Uppercase COLA names the cache-oblivious lookahead-array organization behind the indexes. Worlds share immutable objects in a multiverse; a session follows the current world.
| Component | What it gives you |
|---|---|
storage_policy | A sort registry plus sampling, physical block size and backspace code; units and width hints come from its sorts. |
elias_fano, rank_groups | Monotone offsets and grouped origin counts, independent of the key representation. |
profile_array, profile_view, profile_cursor | Encoded records, borrowed views, and sequential decoding. |
profile_native_writer, native_merge_builder | Incremental native encoding and ordered per-key value composition. |
native_file_writer, native_file_merge | The same native framing and merge semantics with bounded payload buffering into private files. |
profile_blob, profile_index | A complete native/index pair, or an independently constructed index for existing native storage. |
sample_cursor, index_builder, index_pipeline | Sampling an existing pair and building new index links incrementally. |
file_index_builder, file_index_pipeline | Streaming those index links to files while retaining the original mapped native data. |
query_root, query_root_builder, query_cursor | Preparing a bounded search head and visiting matching native entries through an exact index chain. |
cola_index, cola_index_builder, cola_query_root | Two-route main/secondary catalogs, incremental construction and all matching native contributions. |
cola_local_merge_job | A native merge, its destination index and replacement routing, with explicit stage boundaries and retained inputs. |
mapped_file, file, multiverse | Retained read-only mappings and policy-checked object access. |
encode_native_sections, encode_index_sections, mapped_blob, mapped_query_root | Portable blob files and queries over exact pinned mmap chains. |
encode_cola_sections, mapped_cola_blob, mapped_cola_query_root | IX03 indexes over unchanged native files, with one recursive main route and one terminal secondary route. |
mapped_cola_index_builder | Constructing those two routes directly from pinned mappings, without rewriting native files. |
object_writer, object_stream, multiverse::seal_object | Immutable object construction with explicit persistence barriers and retained failure identities. |
sqlite_catalog | Durable reservations, exact file graphs, named saves, timeline generations and reader pins. |
reference_world, partition_round, pin_set | Executable snapshot, update, fingerprint, and ownership semantics. |
Immutability makes sharing straightforward. Two readers can retain the same native allocation while using different indexes. A saved world can retain old inputs after a newer world has compacted them. Reclamation follows ownership: an object stays alive while something still needs it.
Indexes make that last sentence precise. A borrowed key and its ordinal name an occurrence in an exact target pair. If another branch merges that target, the old ordinal still belongs to the old pair. We keep the old target pinned, build the new link, then adopt the replacement. This permits shared compaction work without forcing all branches to repair their dependencies simultaneously. The file lifecycle and catalog design describe that transition on disk.
Binary search gets us into one sorted run. Repeating it independently in every run costs another logarithm. Fractional cascading lets us carry the result of one search into the next: selected target keys bound a small interval in the following pair.
We don't have to store the merged keys to describe that interval. Grouped counts suffice to represent the virtual merge of native and borrowed keys. At a group boundary, rank tells us how many occurrences came from the borrowed stream; subtraction gives the native count. The projected ranges contain at most K occurrences in total. Native entries come first on equality, and borrowed duplicates remain distinct. A borrowed key also present natively gets a false-borrow flag, preserving both its lookup meaning and its position.
The group size is a policy choice of the form K = 2^r - 1:
K | Bits per group count | Sampling positions |
|---|---|---|
| 3 | 2 | 0, 3, 6, … |
| 7 | 3 | 0, 7, 14, … |
| 15 | 4 | 0, 15, 30, … |
| 31 | 5 | 0, 31, 62, … |
Fifteen is the default. A smaller group buys a narrower search window with more index space; a larger group spreads the metadata over more records. Group size and level growth are separate choices. The sampling analysis explains their interaction, including why sampling counts augmented occurrences rather than distinct keys.
For redundant COLA levels, a main catalog borrows from two targets. The main target continues the cascade; the secondary target ends at its native array. We keep two borrowed streams and two population directories over their shared three-way order. Native rank follows by subtracting both borrowed counts. This lets a query visit at most two arrays per level while shadow construction proceeds separately. The COLA guide includes a complete two-target example and the mapped file layout; the scheduling design explains visibility and work. The mapped save and merge example writes files, retains both input contributions, publishes their merge and reopens the saved states. The local merge example drives both main and secondary destination plans while retaining the old query root. The space report measures the resulting arrays. The construction benchmark measures the effect of carrying prefix comparisons through sampling and merging.
Sorted strings share prefixes, so we can encode a key by backspacing from its predecessor and appending a suffix. Each physical stream uses ordinary front coding. A search carries comparison state against its query: the known prefix agreement, comparison direction and the full key length when known. It compares the next literal without reconstructing the inherited prefix.
The borrowed predecessor before a window needs one extra scalar: its exact LCP with the incoming boundary. Because those two keys and the query are ordered, the smaller adjacent LCP gives its agreement with the query. This scalar belongs to the exact index view. Rebuilding an index recomputes it while retaining the native bytes. The comparison argument covers ties, endpoints and the separate roles of physical and virtual boundaries.
The byte profile counts lengths and offsets in bytes. The bit profile works with densely packed, most-significant-bit-first strings and counts in bits. Both use the same policy-bound interfaces. A fixed value width counts the chosen leaf encoding's units: byte_encoding<fixed_values<3>> means three bytes, and bit_encoding<fixed_values<3>> means three bits. A byte leaf nested in a bit registry still has a 24-bit value. Borrowed records carry zero value bits while retaining the same policy family.
Bit backspaces can use golomb<M> or exponential_golomb<Order>; the default is exponential_golomb<0>. The choice belongs to the policy and is checked in stream and file metadata. Absolute retained counts and suffix/value lengths use order-zero exponential-Golomb, while the byte profile uses unsigned varints. Golomb's unary quotient can be long for a large backspace, so its decoding cost includes the count's encoded length even when the resulting key is short.
We mark each physical stream's block starts and end sentinel, then encode those monotone offsets with elias_fano. Its select(i) returns the stored integer at ordinal i; sampling intervals and value strides belong to the profile. For consecutive positions, view.cursor().next() walks the high words forwards and retains the unconsumed bits. Native profile cursors use this traversal at block boundaries; random lookups still use select. Fixed-width values give us an additional saving: their contribution to an offset is predictable, so we subtract it before encoding and add it back on access. If width is w and record ordinal is i, the contribution is w * i in the same address units. The fixed payload stride consequently does not inflate the residual offset universe. The terminal sample uses the actual record count, including a short final block. Physical block width W is independent of cascade stride K; both are part of the policy. Each block starts with an absolute retained-prefix length, then uses relative backspaces. We can parse controls before the selected lane without reading the preceding block or reconstructing those earlier keys.
The native and borrowed streams each have a sparse offset directory. A single-route pair has two such directories and one grouped rank; a two-route COLA pair has three directories and two grouped ranks. Exact cut LCPs connect their physical byte/bit streams to one virtual order. See key policies for the framing and reconstruction contracts.
profile_cursor preserves one decoder context as it advances. sample_cursor keeps two such contexts, merges their current keys, and emits every Kth occurrence. It pins the source pair, reconstructs each source key once during a complete pass, and borrows value payloads without copying them.
An index_builder accepts these samples and merges them with a native stream. An index_pipeline connects builders so that newly produced samples flow straight into the next stage:
Handoffs are front-coded: a backspace count and suffix relative to the preceding sample from that producer, with a literal first key. Counts use policy bytes or bits. The receiving builder retains its decoder context and independently records the exact cut LCPs required by its final index.
Stages are supplied nearest the target first. Bounded queues let a downstream stage pause its producer. step(budget) advances the pipeline in work quanta; finish() assembles the completed directories and binds the resulting pairs to their targets. A quantum can include up to K source occurrences. Key reconstruction, comparisons, and final directory construction have their own costs, so an entry budget is not a byte or wall-clock deadline.
A replacement table represents deletion with an absent value. To count a deletion, though, we need to know that something was there. Updates therefore carry both the old and new binding, and admission checks the old one. Otherwise we could earn rebuilding credit by inventing tombstones for absent keys. The strong-deletion protocol uses that accounting to replace accumulated history with a smaller live table.
Now summarize the reference world's resolved contents with sum(h_key(key) * h_value(value)), taking the hash of an absent value as zero. An update subtracts the old binding's contribution and adds the new one. Compaction leaves this sum alone, and disjoint changesets can contribute their deltas in either order. A file's native contents and its contribution to a world are separate quantities; replacement deltas retain the information needed to subtract older bindings.
These fingerprints are useful for noticing disagreement. They are not cryptographic authentication or physical object identities. The default algebra uses wrapping unsigned 64-bit arithmetic; a supplied algebra can use a prime field, a binary extension field, or another suitable ring. No division is needed.
Replacement values are one useful instance of a broader idea. The categorical update design treats each key's update as an arrow between states. A list can describe prepends, appends and deletions as composable edits, while another key can choose a different vocabulary of changes. This keeps the storage mechanism useful beyond one interpretation of a map.
The compact representation also gives us useful units of parallel work. Packed rank classes can be summed together, byte prefixes can be compared sixteen bytes at a time, and bit streams can be copied or framed in word-sized chunks. The implementations keep loads within the supplied spans, including the last partial byte. Compiler targets select the available instructions; the package does not add runtime dispatch or impose ISA flags on consumers.
I measure dependent queries as well as independent throughput. The next step through a fractional index depends on the previous answer, and the fastest bulk kernel need not have the lowest latency for that chain. In particular, groups of three keep a scalar packed sum, while seven and thirty-one use NEON on little-endian AArch64. The dense select scan also stays scalar: its SIMD candidate was slower in the measured cases.
The blob and pipeline comparison measures complete in-memory builds, three-link index construction and searches within a known window. It checks the resulting bytes and answers against the same inputs and an independent catalog oracle. The component reports cover key and bit operations, Elias–Fano, grouped and bitmap rank, and rank15, with source, raw trials and reproduction commands. The whole-query comparison includes root preparation and traversal through every catalog, with owned results. Ordinary FC with exact cut comparisons uses 38–48% less median query time in its M2 Max fixtures, with counted backing arrays changing by less than 1%. Root preparation has mixed results. These are resident-memory measurements; disk faults remain a separate cost.
A count-decoding follow-up measures the common bit counts from one bounded field. It reduces complete bit-query time by another 26.0–26.9% against its ordinary-FC baseline, without changing the encoded arrays. The byte-profile timing ranges overlap. Each report gives its own exact baseline, fixtures and validation; these are separate measurements.
The incremental writers keep the previous key buffer and replace only its changed suffix after an append succeeds. Complete append/finalize measurements show 26–46% less time for borrowed keys and 18–44% less for native key/value records. These runs verify identical encoded sections and decoded contents. The retained buffer capacity can grow to the largest key seen; output bytes and format do not change.
The Lean model checks the algebra, ownership and fractional indexing rules behind the construction. Its theorems cover chronological composition, disjoint updates, endpoint contributions, snapshot adoption and retention of exact target dependencies. An adjacent-merge theorem connects the composition law to adoption of a new representation.
For fractional indexing, a search over sampled occurrences followed by a local window search agrees with a full predecessor search. Endpoint ranks project that window into native and borrowed ranges sharing one K-entry budget. False-borrow recovery finds an equal native key even when it lies before the window. Equal borrowed occurrences remain distinct, and indexes retain their exact targets across catalog extension and safe reclamation.
These are abstract sequence proofs. Compressed rank, Elias–Fano, front coding, complete cascade execution, scheduling and the filesystem protocol still need their own refinements. The proof project builds independently of C++ and records those boundaries explicitly.
The string-comparison modules also check the ordered-triple LCP identity and associative mismatch transfers used by the ordinary-FC design. An exact LCP at each cut can repair the preceding borrowed comparison state without repeating its prefix. Connecting those theorems to encoded metadata and the complete cursor is the next proof obligation. The complete query tests separately check the encoded implementation against independent native-array oracles.
Use upstream Clang 23, CMake 4.4 and Ninja. Install simd with SIMD_ENABLE_EXCEPTIONS=ON using the same compiler, standard library and runtime. Set CMAKE_PREFIX_PATH to that installation when configuring Everett. The module guide gives the dependency build, explicit execution profiles and macOS SDK setup. The mapping backend uses the platform's native read-only mapping API. I use one pinned fast-crc32 generator for portable, ARM and x86 CRC32C kernels. Generated kernels are compiled into Everett, so a consumer build needs no generator or separate CRC library. The compiler target selects eligible kernels; buffers too small to benefit from parallel folding use a scalar path. The checksum and file format stay the same.
The tests check decoded results against independent oracles, group boundaries, byte/bit policy combinations, exact ownership, partition permutations, and simulated publication and recovery failures. Run AddressSanitizer and UndefinedBehaviorSanitizer on supported compilers with:
EVERETT_SANITIZERS instruments test translation units. Instrument the compiled Everett and SIMD libraries in their own builds as well when checking code inside those archives. Enable EVERETT_ENABLE_SQLITE=ON to include the durable catalog, connection and SQLite package tests; the core-only configuration omits them.
Install the package:
Configure your consumer with both /path/to/everett-install and /path/to/simd in CMAKE_PREFIX_PATH, using the same toolchain, then link the compiled target:
An embedded checkout supports add_subdirectory(path/to/everett) and the same target. Tests default off when embedded. EVERETT_USE_CCACHE=ON enables a compiler cache for test builds when ccache is available. The baseline target and storage_policy<> use scalar execution. For a native policy, import and link its profile module and apply simd_target_profile to the consuming target.
With Doxygen and Python 3 installed, generate and check the API documentation:
The optional documentation check verifies file metadata, declaration ownership, overloads, and source locations. See Doxygen conventions and contributor instructions for the corresponding source conventions.
The functional Data.Vector.Map and its deamortized variant in structures supply the starting point. Everett's levels use the redundant COLA scheme from Cache-Oblivious Streaming B-trees. String locality and front-compression background come from Cache-Oblivious String B-trees, particularly Section 3.2. The sparse offset representation follows the Elias–Fano techniques discussed in Quasi-Succinct Indices.
The design's annotated references include fractional cascading, succinct rank, persistent streaming indexes, compressed string merging, and live-size rebuilding. For a particular concern:
1.9.8