.grafeo Container Format Specification¶

The .grafeo file is the single-file persistence format for Grafeo databases. This page describes container format v3, written since 0.6.0. A file holds images: an image is the state of one checkpoint, made of the chunks of its typed sections and a chained directory that lists them. Every header, directory block and chunk is checksummed, and checkpoints are copy-on-write: a new image never overwrites a page the active one uses.

Files written by 0.5.x (container v1 and v2) are described under Files Written by 0.5.x.

File Layout¶

Offset    Size     Contents
────────────────────────────────────────────────────
0x0000    4 KiB    File header (magic, format version 3, flags, database id)
0x1000    4 KiB    Database header, slot 0
0x2000    4 KiB    Database header, slot 1
0x3000+   pages    Chunks and directory blocks of the images

The page size is 4 KiB. The headers take the first three pages (12 KiB); data starts at page 3 (0x3000). Every chunk and directory block starts on a page boundary, except that a chunk without bytes is stored with offset 0 and length 0 and takes no pages. All integers are little-endian.

File Header (0x0000, 4 KiB)¶

Written once when the database is created, never modified afterwards.

Flags: bits 0 to 15 are incompatible features, which change how the file must be read: a reader refuses a file that sets one it does not know. Bits 16 to 31 are compatible features, which a reader that does not know them ignores. The only feature today is incompatible bit 0: the file is encrypted.

Validation on open, in this order: the magic, the CRC, the format version (must be 3), the page size (must be 4096) and the incompatible flags.

Database Headers (0x1000 and 0x2000, 4 KiB each)¶

Two alternating slots provide crash safety. A checkpoint writes its header into the inactive slot, so the active one stays intact until the new header is on disk.

Active header selection: a slot whose bytes are all zero was never written. Any other slot without the magic and a matching CRC is damaged (a torn or corrupted write). The valid slot with the higher iteration is active (slot 0 on a tie). If no slot is valid and one is damaged, the open fails instead of treating the file as empty: the image the damaged slot pointed at may still be in the file. A new database gets a valid iteration-0 header in slot 0 that points at an image without sections.

Format revision: the active header's format_revision says which additions to container v3 its image may use. 0.6.0 writes and reads revision 1. A reader refuses a revision above the highest it knows ("written by a newer version of Grafeo") and revision 0 (a 0.6.0 development build from before revisions, which no release reads), before it reads the directory, and leaves the file as it is. A checkpoint writes the revision of the header it replaces, so a file keeps its revision: a 0.6.x release that adds a revision gives it to a file only through an explicit upgrade, and new files keep revision 1 throughout 0.6.x.

Directory¶

The directory of an image lists every chunk in fixed 48-byte entries. It is stored in blocks of at most 64 KiB (up to 1,364 entries each); each block names the next one, so the number of chunks is not limited. The active database header points at the first block.

Directory Block¶

The CRC of a block is kept by whoever points at it: the database header for the first block, the previous block for the others. An open checks that every block pointer is page-aligned and lies in the data area, that the length fits the entries, the CRC and the magic, and that the chain never visits a block twice.

Directory Entry (48 bytes)¶

Unknown entries. A newer version may add section types and chunk kinds. The flags of each entry tell an older reader what to do with one it does not know:

• Bit 0 (0x01, section optional): a reader that does not know the section type skips the entry.
• Bit 1 (0x02, chunk optional): a reader that knows the section type but not the chunk kind skips the entry. Bit 0 never covers an unknown kind of a known section, so an optional section can still add a required chunk kind.
• An entry of an unknown section type or chunk kind without its bit is refused: the error names the type or kind and says it is required.
• Bits 0 to 3 change how an entry is read, so a reader refuses an entry that sets one of them it does not know. Bits 4 to 7 do not, and a reader ignores them (the same split as the feature flags of the file header).

Every section type and chunk kind of this release is required: its entries have flags 0.

A skipped chunk is never read, decrypted or handed to a section. Its place is checked as a known chunk's, and its pages stay in use while its image is active, so no checkpoint writes over them. A checkpoint writes only the section types and chunk kinds it knows, so the next one drops the skipped chunks, and their pages become free once its image is active.

An open also checks that every chunk, a skipped one included, is page-aligned, lies within the file, and shares no page with another chunk or directory block.

Section Types¶

Type ranges:

• 1-9: Data sections (authoritative, cannot be rebuilt)
• 10-19: Index sections (derived, can be rebuilt from data)
• 20+: Acceleration structures

Versions. The version is the one 0.6.0 writes, in the section_version byte of every directory entry of the section. A reader accepts its section's version and refuses any other, naming the section and both versions (for a derived section that means building it from the data, see below). The one exception is a section stored as one raw chunk (see Chunks), which holds 0.5.x bytes and is read by the 0.5.x reader of its section, whatever its version byte.

Derived sections (VECTOR_STORE, TEXT_INDEX and RDF_RING) only mirror the data. A reader that cannot decode one, because it has another section version or a stream that does not decode, builds its indexes from the data instead, with a warning, and the database opens; a derived section whose chunks cannot be read (a checksum, I/O or decryption failure) fails the open, as any section's does. So a later 0.6 release can change a derived layout without making its files unreadable to this one: it writes the new layout under a new section version, or as a new section type with the optional bit set, which this release skips (see unknown entries) and builds from the data. Derived data a later 0.6 release adds, such as persisted statistics, comes as such optional sections as well.

PROPERTY_INDEX is reserved: no checkpoint writes it. Property indexes are built from the data when a database opens, from their definitions in the catalog.

Sections without data (indexes, RDF data, overlay deletions) are left out of the image: if no RDF data exists, there is no RDF_STORE chunk. The CATALOG and LPG_STORE sections are always written.

Chunks¶

A section is written as a stream of chunks, which the reader gathers back by section type. The chunk fields (graph, column, rows, codec) let a section split its data into many independently addressable chunks. Every section of a checkpoint writes a metadata chunk (chunk_kind 1), first (in LPG_STORE last), and its data in chunks of their own. A file written by 0.5.x holds every section as one raw chunk (chunk_kind 0) of its serialized bytes, which the section's 0.5.x reader reads.

A raw or metadata chunk has every other field of its directory entry set to 0. All chunks of a section carry the same section_version, and no two of them have the same kind, namespace, graph, column and first row (the chunk's identity): a reader refuses a section that breaks either rule.

Namespaces¶

A chunk's column_id is a number within its namespace, so ids repeat across namespaces: a node property and an edge property column can have the same id. The namespace bytes come in groups with room to grow:

Reserved and not written yet: 18 node deletes, 19 node label bitmaps, 20 node versions, 34 edge deletes, 36 edge versions, 48 outgoing adjacency and 49 incoming adjacency; the other bytes are unassigned. Every namespace a file of a known revision can hold is known to its reader, so an entry with a namespace byte the reader does not know is refused as damage, whatever its flags.

Caps¶

A chunk holds at most 65,536 rows and 1 MiB (the caps). A row whose values pass the byte cap gets a chunk of its own, and every piece of a stream but the last holds exactly 1 MiB. A section's metadata chunk records the caps it was written with, and its reader checks the chunks against those. The row cap is also the format's: a reader refuses caps of more than 65,536 rows and a column chunk of more rows, so what a chunk decodes into stays bounded. The metadata chunks are not cut: they hold as many names and graphs as the database has. The catalog's records are a stream, cut wherever the byte cap falls, so a record can span pieces.

No 4 GiB limit (#392). Chunk offsets, chunk lengths and first rows are 64-bit, and the 32-bit counts and lengths inside a chunk count only within that chunk. So a database, a section, a graph and a table can pass 4 GiB and 2^32 rows, and a node can have any number of labels. What stays limited is a single value (lengths and counts of at most 2^32 - 1, nesting of at most 128 levels, see Value Encoding), and the RDF ring index, which holds at most 2^32 - 1 terms and triples (see Stream Sections). Each schema entry is one catalog record of at most 2 MiB, whose property types nest at most 32,768 LIST<...> levels in all (see Catalog Records). A checkpoint that meets a value or an entry past these limits fails, names it and keeps the WAL.

Column Chunks¶

A Column or History chunk holds the values of one column for a range of rows of a table: only the rows that have a value, in row order, behind a presence bitmap, so a row without a value costs one bit. Its directory entry names the graph (graph_id), the column (column_id), the first row (row_start), the rows from the first to the last it covers (row_count, at most the row cap) and the codec (codec). The chunk repeats the codec and the row count, and a reader refuses a chunk that disagrees with its entry. Layout, little-endian:

A writer picks a typed codec (1 to 6, or 8) only when every value of the chunk has its kind, and Values otherwise, so every value reads back exactly as it was written: an Int64 next to a Float64 stays an Int64, and decimals of several scales go into a Values chunk, each keeping its own scale (1.50 stays 1.50).

Zone maps. A chunk of the codecs BitPacked, RawI64, Float64, Bitmap and Decimal64 carries the minimum and the maximum of its values, two values in the value encoding; NaN is left out (a chunk of NaN only has no zone map). Every Dict chunk carries a string zone map, by the strings' UTF-8 bytes:

A cut maximum is raised so it stays an upper bound: every string that starts with its first 16 bytes is below it (UTF-8 holds no 0xFF byte, so the 16^th byte can always be raised; the result need not be UTF-8). So no string of the chunk is below the minimum or above the maximum (or at or above it when it was cut), and each is from the shortest to the longest length. Float32Vector and Values chunks have none. A reader refuses a zone map other than the one the values give, so it can be trusted. See Zone Maps.

Epochs. In a section of version 3 written by a build with the temporal feature, each property value carries the epoch it was set at, in its Column chunk's epochs. A chunk whose epochs are all 0 carries none, and a reader refuses epochs that are all 0. The fixed columns and the History chunks never carry epochs: a history value holds the epochs of its versions itself.

Value Encoding¶

The Values codec, the zone maps and the history values store each value as a tag byte followed by its fields, little-endian. Every kind reads back exactly: floats by their bits (NaN payloads and -0.0 included), times and zoned datetimes with their offsets, counters with every replica.

A reader checks every length and count against the bytes left before it allocates, and refuses an unknown tag, a field the kind does not accept (such as a bool other than 0 or 1, or a time of a full day or more), map keys or counter replicas that are not strictly increasing, and lists, maps and paths nested more than 130 levels deep, so each value has exactly one encoding. Property values nest at most 128 levels: a write of a deeper value fails (GRAFEO-V001), and the two levels above it hold the lists of a history value.

Table Sections¶

LPG_STORE and RDF_STORE hold their data as tables of Column (and History) chunks. A table is cut into row groups of max_rows rows: group k holds rows [k * max_rows, (k + 1) * max_rows). Only the groups that hold a row are written, and the chunks of one group come together. Every order is defined (ids, names, keys and terms sorted), so the same data gives the same bytes.

LPG_STORE (version 3)¶

Version 3 is the layout 0.6.0-beta.1 wrote. This release reads it to migrate such a file into the layout it writes, version 4, and no longer writes it.

Per graph in id order, the section holds its node table and then its edge table, and it ends with its metadata chunk. Graph 0 is the default graph; a named graph gets the next graph id when it is created. A row is a node or edge id. The columns:

Ids are permanent. A graph's id, and each graph's label, edge type and property key ids, are given once and never reassigned or reused, so one checkpoint and the next name the same things by the same ids. Each graph has three dictionaries: its labels and edge types (an id given when a name is first used), and its property keys (an id given when a checkpoint first writes the key's column), one dictionary of keys for the node and the edge table, the namespace telling their columns apart. A name nothing uses any more keeps its id; an id that names nothing is a gap. A dropped graph's id is never given again: a graph created later under its name gets a new one. A load restores every id as written. Within a row group, a column's Column chunks, and its History chunks, each come in row order without overlapping; a property column has chunks only where it has values; and the edge columns 1, 2 and 3 come as three chunks of one range in a row. Only the nodes and edges visible at the checkpoint are written, with their properties. A property whose value is null does not exist and is not written.

A build with the temporal feature wrote, in a Column chunk of a property, its current values with their epochs, and its older versions in a History chunk written right before it: a history value is a list of [epoch, value] lists, with Int64 epochs, ascending. A property removed last (its latest version null) has no current value: its history holds every version. A History chunk and the Column chunk after it cover the same rows, and either can come alone. Versions of transactions that did not commit are not written. This release checks the History chunks and does not apply them: the history of a migrated file starts at its epoch.

The metadata chunk, little-endian:

The layout has no size limit of its own: a reader checks every count and length against the bytes left, so the chunk holds as many names as the store has. It comes last because it lists every name the chunks use, read after the rows: commits wait while a checkpoint writes, but a transaction still open can create a label, an edge type or a property key meanwhile, and as the dictionaries only grow, the ones read after the rows hold every id the rows name. A graph's next node and edge ids are at least one past its last row, so no id is given out twice across a reopen; the next graph id and each dictionary's next id do the same for graphs and names. A reader fetches the metadata chunk first, restores every graph and its dictionaries, then reads the other chunks in order.

A reader refuses, naming the graph, the column and the rows: a last chunk that is not the section's only metadata chunk; a chunk of another kind than Column or History (History only for property columns), of an unknown graph, outside the node and edge namespaces, of a fixed column its namespace does not have or a property key its graph does not have, holding no rows or more than max_rows, crossing its row group or reaching past its table's next id; groups out of order (by graph, then table, then row group), or overlapping chunks of one column; edge columns that do not come as three chunks of one range; a property value of a row whose node or edge is not in its group; labels that are not ascending ids of the graph's labels, negative endpoints, and edge type ids the graph does not have; epochs on a fixed column or a History chunk; a null property value; history epochs that go back; and in the metadata, a first graph other than the default graph, graph ids that do not ascend or reach the next graph id, two named graphs of one name, and per dictionary ids that do not ascend or reach its next id, or a name listed twice.

RDF_STORE (version 4)¶

The section starts with its metadata chunk, little-endian:

Graph 0 is the default graph, then come the named graphs in name order; a graph's id is its position, and a named graph with an empty name stays apart from the default graph.

Then the term table, the chunks of graph id 0xFFFFFFFF (no graph has it): one row per term, from row 0, with columns 3 (the kind, an Int64: 0 IRI, 1 blank node, 2 simple literal, 3 typed literal, 4 tagged literal), 4 (the IRI, the blank node's label or the literal's lexical form, a String) and 5 (a typed literal's datatype IRI or a tagged literal's tag, a String, empty for the other kinds). A term's row is its file index. The writer numbers the terms by their first use in the order the triples are written, so the same triples give the same bytes, and a term no triple uses is not written.

Then, per graph in id order, its triple table: one row per triple, from row 0, in a fixed order (by subject, predicate and object). Its columns are 0 (subject), 1 (predicate) and 2 (object), and each value is a term id, the 64 bits of the id in an Int64: a 4-bit tag and a 60-bit payload.

A literal is inlined (tags 1 to 6) only in the canonical form of its value, so its id gives the term back exactly ("019"^^xsd:integer is a row of the term table); every term has one id. Tag 15 is the id of a term only a query made, which a file never holds; tags 7 to 14 are unused.

The term table's three columns and each triple table's three columns share their chunk boundaries: their chunks come as three in a row with one range, and every row has a value. A graph without triples writes no chunk; the metadata lists it, so an open creates it.

A reader refuses, naming the table and the rows: a first chunk other than the metadata chunk, or a second metadata chunk; a chunk of another kind than Column; a term table that does not come first, or whose rows stop short of the metadata's count; a row of the term table of an unknown kind, or with a datatype or tag for a kind that has none; a graph the metadata does not list, or whose chunks come after those of a later graph; a range that does not start where the table's rows before it end, holds more than max_rows rows, crosses a row group or reaches past the table's rows; a first chunk not followed by the other two of its range; epochs or a row without a value; a cell that is no term id, an id of an unused tag or of a query's own term, or a row past the term table; and a graph whose rows stop short of its number of triples.

Version 3 (0.6.0-beta.1) has no term table: metadata layout 1 without the term count, and each triple table cell is the term in N-Triples syntax, as a String. A read-write open of a file with an RDF or ring section of version 3 keeps a copy of the file and of its sidecar WAL as <file>.pre-0.6.0 (and <file>.pre-0.6.0.wal), each copied to a .partial name, synced and renamed, then writes both sections in version 4 with a checkpoint as soon as the database is open; a copy that exists is never replaced, so a crash at any point is finished by the next read-write open. A read-only open reads version 3 as it is.

Stream Sections¶

The index sections (VECTOR_STORE, TEXT_INDEX, RDF_RING) and CATALOG hold their data as byte streams. Such a section is its metadata chunk, then the pieces of its streams, stream after stream:

• The metadata chunk (chunk_kind 1, every other field 0) is the bincode encoding (bincode 2, standard configuration: variable-length little-endian integers) of the section's metadata, which starts with a layout byte (1; a reader refuses another layout) and the byte cap the streams were cut with.
• A stream piece (chunk_kind 4) belongs to graph 0; its column_id is the stream, its row_start the piece's byte offset in the stream, and its row_count and codec are 0. Every piece but the last of a stream holds exactly the byte cap (1 MiB by default), and an empty stream has no piece.
• A reader refuses a section whose first chunk is not its metadata chunk, a chunk of another kind or graph after it, a piece of a stream the metadata does not list, a piece that does not start where the pieces before it end, a stream that ends before its contents do, and bytes after them. A reader that joins a stream into one buffer first checks, from the directory alone, that each piece starts after the one before it, by at most the first piece's length and the bytes the piece before it is stored in, so the buffer it allocates is bounded by the file.

All numbers inside the streams are little-endian.

VECTOR_STORE (version 3). The metadata lists the HNSW indexes in strictly increasing key order (Label:property), each with its dimensions, its metric (0 cosine, 1 Euclidean, 2 dot product, 3 Manhattan), m and ef_construction. Stream i holds the topology of index i: [has_entry_point u8][entry_point u64][max_level u32][node_count u64], then node_count records [id u64][level_count u32], each level followed by [neighbor_count u32] and that many [neighbor u64], ids strictly increasing. There is an entry point exactly when there are nodes; it has max_level + 1 levels, and every node has 1 to max_level + 1. Every neighbor listed at a level is a node of the stream with that level, and no node lists itself. Quantized indexes are not written: an open builds them from the data. A topology is restored only into an index with the same dimensions and metric.

TEXT_INDEX (version 2). The metadata lists the index keys in strictly increasing order. Stream i holds the index of key i: [k1 f64][b f64][total_length u64][doc_count u64][term_count u64], then doc_count document lengths [node u64][length u32], then term_count posting lists [term_length u32][term][count u64], each followed by count postings [node u64][term_frequency u32]. The stream is canonical: node ids strictly increase among the document lengths and within each list, terms (UTF-8) strictly increase, every length, count and term frequency is at least 1, every posting's node has a document length, the document lengths add up to total_length, and each document's term frequencies add up to its length. The index's options (k1, b, tokenizer, stop words) are those of its catalog record: an open restores a stream into an index with the record's tokenizer and stop words, and builds the index from the data instead when the stream's k1 or b are not the record's.

RDF_RING (version 4). The metadata holds the number of triples. Stream 0 holds the ring's terms in ring id order as term ids: a count u64, then an id u64 per term, little-endian, a dictionary term's id naming its row of the RDF_STORE term table (which an open reads just before), an inlined literal's id itself. Streams 1 to 5 hold the other parts of the ring, each in its packed format: the wavelet trees of the subjects, predicates and objects, and the permutations from SPO to POS and to OSP order. A store without a ring writes no RDF_RING section. In version 3 (0.6.0-beta.1) stream 0 holds the packed term dictionary of N-Triples strings, read as it is and rewritten in version 4 (see RDF_STORE above).

CATALOG (version 2). The metadata holds the byte cap. Stream 0 holds the catalog records. A catalog without entries is its metadata chunk alone.

An index section that can be read but does not decode is no error: a warning is logged and the index is built from the data. A chunk that cannot be read (a checksum mismatch, an I/O error) fails the open, as in any other section. A CATALOG section that does not decode fails the open.

Catalog Records¶

The CATALOG section holds the schema as a stream of records, one per entry: the schemas, the node and edge types, the graph types and the graphs bound to them, the named constraints, the definitions of every graph's indexes and the names CREATE INDEX gave them, and the stored procedures. Each record is framed, little-endian:

A property of a node or edge type is its name, its type, whether it may be null, and its default value (none, or a byte string holding the value in the value encoding, so it reads back exactly). A type constraint is 0 a primary key or 1 a unique constraint (each a list of properties), 2 a not-null property, or 3 a check (an optional name and the expression). An edge type's endpoints are pairs of a source and a target node type, either of them none for any node type: the cross product of the types CONNECTING (...) TO (...) lists, and no pairs for an edge type that connects any nodes. A property type is two u32: the number of LIST<...> levels around it (at most 128, and at most 32,768 over all the property types of one record, so 256 properties of the deepest type) and the code of the type inside them:

Code 16 is DECIMAL, any decimal with its own scale. DECIMAL(p, s) is 0x0100_0000 | p << 8 | s, with a precision p from 1 to 38 and a scale s from 0 to p; any other code with bit 24 set is refused.

The records come in the order of their kinds, and the records of one kind in increasing order of their key, so the same catalog is written to the same bytes: schemas, types and procedures by name, bindings by graph, constraints by name, index definitions by graph (the default graph first), then property, vector and text indexes, each by key or by label and property, and index names by name, label, property and kind. A binding to a graph type that was dropped binds nothing and is left out.

Newer records. A later version can add kinds. Its writer clears the required flag of a record an older reader may skip, and an older reader skips a record of a kind it does not know when the flag is clear and refuses the catalog when it is set. Every kind of this release is written required. A kind's fields do not change: a version that needs other fields adds a kind.

A reader refuses, naming the chunk or the record (by its entry, or by its position and the byte it starts at): a first chunk other than the metadata chunk, another layout, bytes after the metadata, a chunk other than a piece of stream 0 of graph 0; kind 0, a flag among bits 0 to 3 other than bit 0, or an unknown kind with the required flag; a length over 2 MiB (before it reads the payload, which it reads into a buffer that grows with the bytes present); a stream that ends inside a record; a payload that does not decode as its kind's record or has bytes left over, a property type nested more than 128 levels or of an unknown code, property types that nest more than 32,768 levels in all (each type's levels are counted before they are built); a record that repeats or comes before the record of its kind before it (only an index name may repeat); endpoint pairs that are not a cross product; and a record the catalog refuses, such as a binding to a graph type no record defines. A schema record also creates the schema's default graph.

A payload of n bytes decodes into at most 120 n bytes of memory plus 1 MiB for its LIST<...> levels, while it decodes and the database converts it, before the allocator's own overhead: so at most 241 MiB for a payload of 2 MiB. Every list element, and each null of a default value's list, takes at most 120 bytes per payload byte (three times its size while its list grows or is copied: a property, 5 bytes at its smallest, takes three times 88). A level takes no payload byte of its own, as a type's levels are one count, but 32 bytes of memory (a 16-byte box in the record and another in the database's type), so its memory is bounded per record instead: the cap of 32,768 levels holds the levels of a record to 1 MiB, as much as a damaged list length may allocate ahead of its elements in any record. A damaged length inside a payload allocates no more than that: a string's length counts against a decode limit of 16 MiB before the string is allocated (which no payload of 2 MiB reaches), a list allocates at most 1 MiB ahead of its elements, and a default value's counts are checked against the bytes left. A checkpoint that meets a type past the cap of levels fails, naming it, and CREATE NODE TYPE, CREATE EDGE TYPE, ALTER ... ADD and inline graph types refuse one.

Memory¶

A checkpoint writes one section at a time and holds, besides the database, about one chunk per column of a table's row group, or one piece of a stream, plus the 48-byte directory entries of the chunks written so far. An open chunk holds its rows as decoded values until it is cut, so a column of small values (such as node labels) fills at the 65,536-row cap rather than the 1 MiB byte cap: at the default caps a checkpoint of a large store holds about 14 MiB above the database, bounded by the caps, not by the database. An open reads one chunk at a time (the three chunks of one range for the columns that come together), holds what it builds from them, and reads the same 48-byte directory entries. These sections hold more, in proportion to their data:

Locks. A checkpoint holds commits off while it takes its snapshot and writes the catalog, the RDF sections and the time index, and so does a copy (see Copies and Full Backups). It then holds a graph store's read lock while it gathers the values of one file row group, never while it encodes them or writes to the file: a write to that store waits for one row group's values to be read at most.

Encryption¶

In an encrypted file (flag bit 0), every chunk and every directory block is encrypted with AES-256-GCM under a key derived for the database's id, with a random nonce each. The associated data binds a chunk to its section type, chunk kind, namespace, graph, column and first row (grafeo-chunk:{section}:{kind}:{namespace}:{graph}:{column}:{first row}, in decimal), and a directory block to its offset, so a chunk cannot pass for another part of a section (a node property chunk for an edge property chunk of the same column id, say), nor a directory block for one at another offset. A stored block is the nonce, the ciphertext and the tag: 28 bytes longer than its plaintext. A chunk's length and crc cover the stored bytes; a directory block's pointer holds the plaintext length and CRC. The file header and the database headers are not encrypted. See Encryption at Rest.

Checkpoint Flow¶

Every checkpoint writes a complete new image, which shares the chunks that did not change with the active image:

Checkpoint:
  1. (Engine) Hold commits off and take the snapshot: the epoch E of the last
     commit, a read pinned at E (at the start of the history window for a
     database that keeps history), and what changed in each row group since
     the active image
  2. (Engine) Start a new WAL segment at the end of the log: every commit so
     far is in the segments before its first log position, the checkpoint
     LSN, and is at or before E
  3. Stream each section's chunks, one section at a time, into free pages as
     the section writes them (CRC-32, encrypted if enabled): first the
     sections without versions (the catalog, the RDF sections, the time
     index) while commits are still held off, then, with commits going on,
     the `LPG_STORE` section as of E; a chunk the active image holds
     unchanged is not written: the new directory entry points at its pages
     (see below)
  4. Write the directory blocks into free pages
  5. fsync
  6. Write the new database header (iteration + 1, the new root, the
     checkpoint LSN) into the inactive slot
  7. fsync
  8. Shorten the file to end at the last page of the new image
  9. (Engine) Delete the WAL segments before the checkpoint LSN, unless an
     incremental backup still needs them; a reopen replays the WAL from the
     checkpoint LSN the active header records

Commits during a checkpoint: commits wait for steps 1 and 2 and for the sections without versions. While the LPG_STORE section is written, they go on: it is written as a reader at E sees the store, a file row group at a time, its values gathered under the store's read lock and encoded and written once the lock is released, and the pinned read keeps every version it reads. So the image holds the committed state at E exactly, and the commits after E are in the WAL after the checkpoint LSN.

Incremental checkpoints: a write marks what it changes in its row group as it takes effect (at its commit, or at once for a write outside a transaction): rows created or deleted, the property keys and labels it changed (per vector of 2,048 rows), the nodes' outgoing and incoming adjacency. The snapshot takes the marks, and per file row group of the LPG_STORE section the checkpoint:

• reuses every chunk of a row group without marks, its row count from the active image's metadata;
• for a row group whose rows did not change (and with no history kept), writes the changed columns again within the chunk boundaries of the active image, the chunks of the vectors that changed, and the adjacency of a direction that changed, reusing every other chunk;
• writes any other row group anew.

The sections encoded in step 1 reuse every chunk the active image holds with the same description and bytes, so a catalog that did not change is not written again. Chunks are reused only from the image a store's data was last written to or read from: a store loaded from another file, a copy, or one whose last checkpoint failed writes every chunk at its next checkpoint, the same path with nothing to reuse. A reused chunk keeps its directory entry (offset, length, CRC, codec): its associated data names its section and place, not its offset, so an encrypted chunk decrypts in the new image too.

Free space: the pages free for a checkpoint are derived from the pages the active image uses, which an open reads from its directory: every page from page 3 up to the end of the last used page that the active image does not use. No free list is stored. Allocation is first fit and appends at the end of the file when no gap is large enough, so a checkpoint reuses the pages of the image before the active one. While a checkpoint runs, the file can hold the active image and the new one; the chunks they share take their pages once, and become free only when no image uses them any more. A reused chunk stays where it is, unless at least half of the pages the active image spans are free: then each chunk the checkpoint reuses that fits a free run before it is copied there as stored (its CRC, and for an encrypted file its nonce and tag, stay valid), so the image packs toward the start of the file and the file shrinks after its data did.

Crash safety: steps 3 to 5 write only pages the active image does not use, so a crash before the new header is on disk opens the previous image, intact. A torn header write fails its CRC, so the other slot stays active. A crash after step 7 opens the new image. If a checkpoint fails at or after its header write, the new header may or may not have reached the disk: the next checkpoint spares the pages of both images, and the WAL is kept until a later checkpoint succeeds.

Copies and Full Backups¶

A full backup, save() and to_memory() write a complete image of the database at an epoch through the same path, with commits going on:

Copy:
  1. (Engine) Hold commits off and take the snapshot as a checkpoint does
     (the epoch E, a read pinned at E), without taking the row groups' marks
  2. (Engine) For a full backup, start a new WAL segment: its first log
     position is where the incremental backups after it begin
  3. Write every section into a new file `<target>.partial` (into memory for
     `to_memory()`): the sections without versions while commits are still
     held off, then the `LPG_STORE` section as of E with commits going on;
     every chunk is written, as nothing is shared with another file
  4. Write the directory, fsync, the database header, fsync
  5. Rename `<target>.partial` to the target and sync its directory

The image holds the committed state at E exactly. The copy leaves the marks and the baselines of the database alone, so its next checkpoint reuses what it would have without the copy. A crash before step 5 leaves the database and the target as they were, and at most a <target>.partial that the next copy to the same target removes. A full backup enters the backup manifest only after its rename, so a restore never reads an image a crash cut off, and the next full backup replaces an image the manifest does not list. The incremental backups after a full backup hold the WAL from the segment it started, so a restore to an epoch is the full image and the commits after E up to that epoch. A read-only database starts no WAL segment: its image records the end of the sidecar WAL its open replayed, and as it cannot move the WAL's backup cursor, the writer's next incremental backup starts before that image's epoch. A restore therefore replays every incremental backup taken after the full backup it starts from, from the image's log position on, which skips what the image holds. export_snapshot() reads the graphs' rows at E the same way: commits are held off while it takes the catalog's records and the RDF triples.

Spilled Sections¶

The .grafeo file is read with positional reads and is not memory-mapped. When memory pressure spills a section (or a ForceDisk tier override asks for it), the engine writes the section to a spill file in the spill directory (<file>.spill/ by default) and memory-maps that file. An encrypted database spills nothing, as spill files are not encrypted. See Storage Tiers.

Recovery¶

Open database:
  1. Read the file header at 0x0000 and validate it (a file written by 0.5.x
     takes the migration path instead, see below)
  2. Read both database header slots, select the active one, and check its
     format revision
  3. Read the directory chain from the active header's root, checking every
     block (and decrypting it in an encrypted file); set optional entries of
     an unknown section type or chunk kind apart, and refuse required ones
  4. Check that every chunk (a skipped one included) lies within the file and
     that no pages overlap
  5. Read each section's chunks, verify their CRC-32 (and decrypt them), and
     load the section into RAM
  6. If a sidecar WAL exists: replay the commits logged after the active
     header's checkpoint LSN, each complete group at the epoch it names (a
     group without its last frame was never committed and is skipped); a
     WAL written by 0.5.x or 0.6.0-beta.1 is replayed once, checkpointed
     into the file and removed
  7. Database is ready

A read-only open takes a shared lock instead and goes through the same steps, the WAL replay included, but only into memory: it writes nothing, so a torn tail stays until the next read-write open. With the WAL enabled, that open cuts the tail before it logs anything new; with wal_enabled off, it writes the replayed changes to the file and removes the WAL, the torn tail with it. A build without the wal feature cannot replay: it refuses to open a database whose sidecar WAL holds commits (a log file with more than a segment header), read-only or not, and leaves the WAL as it is. Likewise a build refuses a file that holds data only a feature it lacks reads, which it would load without and its next checkpoint drop: without triple-store RDF triples (an RdfStore or RdfRing section, or RDF records in the sidecar WAL), without vector-index or text-index the definition of such an index in the catalog; a 0.5.x database (also a WAL directory or a container v1 snapshot) the same way. A compacted base of a 0.5.x file is read by every build that opens files. It refuses them read-only or not, and changes nothing: it looks at the sections of the image and at the catalog before it loads any other section, and at the records of a WAL as it replays them into memory.

Periodic Checkpoints¶

When Config::checkpoint_interval is set, a background thread periodically checkpoints the database to the container. This bounds the size of the WAL, and so the time a reopen spends replaying it.

The timer polls a shutdown flag every 100 ms. On database close, the timer is stopped before the final checkpoint to prevent races.

File Locking¶

• Exclusive lock on open (read-write mode): prevents concurrent writers on the same file.
• Shared lock on open (read-only mode): allows multiple concurrent readers. A read-write open and read-only opens exclude each other.
• Locks are released on close or drop.
• A new file is built and synced as <file>.creating and then renamed, so the database path never holds a partial file.
• A migration of a 0.5.x file holds <file>.migrate.lock (see below).

Size Estimates¶

Files Written by 0.5.x¶

0.5.x wrote container v1 (0.5.21 to 0.5.34: one bincode snapshot after the headers) and v2 (0.5.35 to 0.5.44: a section directory page at 0x3000 with 32-byte entries, section data from 0x4000). Both use bincode headers in the same three 4 KiB pages. Byte 4 tells the formats apart: in a 0.5.x file it is the varint 0x01 of the bincode format version, in a v3 file the version is 03 00 00 00.

0.6 reads these files only to migrate them, or to open them without changes:

• A read-write open migrates the file. Under <file>.migrate.lock, it reads the old database (its sidecar WAL replayed), writes it as a v3 image to <file>.migrating, renames the old files to <file>.pre-0.6, <file>.pre-0.6.wal, <file>.pre-0.6.checkpoint and <file>.pre-0.6.spill (the spill directory, which may hold embeddings a database closed while spilled has nowhere else), and renames the image to <file>. The old files are kept byte for byte, and a crash at any step is resolved from the files present at the next read-write open.
• A read-only open and open_in_memory() read the file in place, with its sidecar WAL, and change nothing.

A 0.5.x WAL directory (a directory holding wal/, which 0.5.x created by default for a path without the .grafeo extension) is handled the same way: a read-write open replays its WAL into a v3 image, keeps the whole directory as <path>.pre-0.6/ (and its spill directory <path>.spill/ as <path>.pre-0.6.spill/) and renames the image to <path>, so the database becomes a file at the same path; a read-only open replays it in place. 0.6 creates no WAL directories.

0.7.0 will no longer read v1 and v2 files or WAL directories. See Upgrading from 0.5 for what users need to do.

Version History¶