Storage: compact schema-referenced document encoding with lazy, crash-safe format upgrades

Summary

LiteDB currently stores collection documents as BSON bytes directly in DataPage/DataBlock payloads. This is simple and self-describing, but it repeatedly stores the same field names in every document and even stores array indexes as BSON CString keys ("0", "1", "2", ...).

For regular POCO-shaped collections this can waste a substantial amount of disk space, WAL bandwidth, page-cache capacity, and I/O.

Proposal: introduce a LiteDB-internal compact document codec where repeated document shape is stored once in a per-collection schema catalog and documents reference that schema. The engine reconstructs the normal BsonDocument on read, so users, queries, indexes, LINQ, SQL, BsonMapper, and the public BSON serializer continue to see exactly the same document model.

The important part is that this must not require rebuilding a database just because the LiteDB package was upgraded.

Existing BSON documents should remain readable in place. Compact documents and legacy BSON documents may coexist indefinitely. A full Rebuild is an optional compaction operation, not a mandatory migration step.

Why this is worth doing

Today the storage path is effectively:

BsonDocument
    -> GetBytesCount(true)
    -> BufferWriter.WriteDocument()
    -> BSON bytes
    -> DataBlock(s)

Every document element stores:

type byte + UTF-8 field name + NUL + value

Nested documents repeat their field names again. BSON arrays also encode every array index as a CString.

For a collection with 15 fields averaging 10 UTF-8 bytes per name, field metadata alone is roughly:

15 * (1 type + 10 name + 1 NUL) ~= 180 bytes/document

At 1,000,000 documents that is ~180 MB before considering nested object field names or array index strings.

Reducing physical document size also has second-order benefits:

• more documents per 8 KiB data page
• fewer DataBlocks and page chains
• less WAL traffic
• less page-cache pressure
• fewer disk reads for scans
• smaller backups/rebuild output
• potentially faster scans simply because less data is moved

Related user reports include #2037, #1825, #157 and #298.

This intentionally revisits the assumption in #2832 that the physical storage format must remain BSON. The public BsonDocument/BsonSerializer contract should remain BSON; the physical storage format does not need to be BSON.

Non-negotiable safety / compatibility invariants

1. Opening a database must never rewrite every document.
2. Updating the LiteDB library must not by itself require Rebuild().
3. Existing v8/v9 documents remain readable exactly where they are.
4. Legacy BSON and compact documents can coexist in the same collection/file.
5. A document is converted only when it is newly inserted/updated, or by an explicit Rebuild.
6. Schema metadata and any document referencing it become visible atomically in the same transaction.
7. A compact document must never be durable while the file header still claims an older format.
8. File-format promotion is monotonic during normal operation. Checkpoint/WAL replay must never downgrade it.
9. A rollback may leave the file-format version promoted, but must never leave a committed document pointing at uncommitted/missing schema metadata.
10. Schema IDs/definitions that have been committed are immutable and never reused for another shape.
11. Corrupt or missing schema metadata must fail loudly. Never guess, silently reinterpret values, or fall back to another schema.
12. Public BsonSerializer must remain a real BSON serializer. Internal compact encoding must be a separate component.
13. Existing query/index semantics must not change merely because the document is stored compactly.
14. Read-only open must never promote or mutate the file.
15. Full conversion and downgrade are done by the existing temp-file/backup Rebuild model, never by an in-place whole-file migration.

Current code paths affected

The current coupling is fairly localized:

• LiteDB/Engine/Services/DataService.cs
  • sizes documents with BsonDocument.GetBytesCount(true)
  • writes them with BufferWriter.WriteDocument()
• LiteDB/Engine/Query/Lookup/DatafileLookup.cs
  • reads DataBlocks with BufferReader.ReadDocument()
• LiteDB/Engine/Engine/Index.cs
  • has direct BufferReader.ReadDocument() paths while building normal/vector indexes
• LiteDB/Engine/FileReader/FileReaderV8.cs
  • rebuild/recovery path needs to understand whatever document payload format is on disk
• LiteDB/Document/Bson/BsonSerializer.cs
  • currently shares BufferReader/BufferWriter with the engine, but should remain standards-compatible BSON
• LiteDB/Engine/Pages/HeaderPage.cs and DiskService.FileVersion.cs
  • file-format capability/version gating
• LiteDB/Engine/Pages/CollectionPage.cs
  • natural place to point at per-collection schema metadata
• Snapshot / TransactionService / WAL
  • schema pages and data pages must have ordinary transaction visibility and recovery semantics

All engine-level reads of document DataBlocks need to go through one storage codec abstraction. Header/collection/index metadata that currently uses BSON internally does not have to change as part of this proposal.

Proposed architecture

Introduce a storage-specific abstraction, conceptually:

DocumentStorageCodec
    Read(...)
    PrepareWrite(...)
    Write(...)

with at least two decoders:

LegacyBsonDocumentCodec
CompactDocumentCodecV1

Public serialization remains:

BsonSerializer
    -> BSON BufferReader/BufferWriter

Database storage becomes:

DataService
    -> DocumentStorageCodec
    -> legacy BSON OR compact LiteDB encoding

The engine should no longer assume that bytes inside a DataBlock are public BSON bytes.

Important: prepare once, then write from the plan

DataService currently calculates a BSON size first and then writes the document. The compact encoder needs schema selection before exact size is known.

Use a write plan:

var plan = codec.PrepareWrite(document, schemaCatalog);
plan.EncodedLength
plan.RequiredCatalogChanges
codec.Write(plan, output);

The exact same plan must be used for allocation and writing so a schema-selection heuristic cannot make a different decision between the size pass and write pass.

Compact document format

The exact byte layout should be benchmarked before freezing it, but V1 should be deliberately conservative.

Root format discriminator

Legacy documents start with a positive Int32 BSON document length.

Compact documents should start with a magic value that cannot be a valid legacy BSON length, followed by a codec version/flags.

Example conceptually:

[invalid-as-BSON magic]
[codec version]
[flags]
[schema id]
[schema fingerprint]
[presence bitmap]
[typed values]
[optional extension fields]

Do not change DataBlock layout just to identify the codec. Keeping the discriminator inside the document payload avoids changing all DataBlocks.

The magic value must be chosen so legacy BSON can never legally collide with it.

Keep types in the document for V1

A schema should describe field identity/order, not enforce field types.

Each present value should still carry its BsonType.

That means this remains fully schemaless:

{ Age: 10 }
{ Age: "unknown" }

can use the same schema.

This also avoids generating schema versions just because a field changes type.

A later format version can explore type elision if measurements justify the extra complexity.

Presence bitmap

Missing and null must remain different:

{ A: null } != { }

A schema is an ordered list of known fields. Each document carries a presence bitmap indicating which schema slots are present.

That allows optional fields to share a schema instead of creating 2^N schema combinations.

Example:

Schema 12 = [_id, Name, Email, Birthday]

bitmap 1110:
    _id present
    Name present
    Email present
    Birthday missing

Null is represented by the bit being present plus a Null value type.

Nested documents

Nested documents use the same per-collection schema catalog.

A nested Document value can therefore contain:

schema id + bitmap + typed values

without repeating a top-level magic value when the parent BsonType already says "Document".

Arrays

Compact arrays should be:

[count]
[typed value]
[typed value]
...

There is no reason for the internal format to store BSON keys "0", "1", "2", etc.

This is an independent win even when array contents are highly dynamic.

Scalar representation

V1 should preserve current LiteDB/BSON semantics for scalar values rather than mixing a storage optimization with value-semantics changes.

In particular, round-trip behavior for:

• Int32 / Int64 / Double / Decimal
• String
• Binary / Guid
• ObjectId
• Boolean
• DateTime
• Null / MinValue / MaxValue
• Vector
• nested Documents / Arrays

must match the current engine.

Schema catalog design

Prefer per-collection metadata, not one normal hidden collection

A global hidden "_schemas" collection is tempting, but has several drawbacks:

• it creates a recursion/special-case problem: how is the schema collection itself encoded?
• every collection write may contend on one global collection lock
• schema lifecycle becomes disconnected from collection lifecycle
• transaction and drop/rebuild handling becomes more awkward

Prefer a per-collection schema catalog owned by the CollectionPage.

CollectionPage already has reserved bytes

CollectionPage currently starts indexes at offset 96.

From the page header at offset 32 it currently stores 5 free-list UInt32 values (20 bytes) and skips the remainder up to offset 96.

That leaves ~44 bytes of reserved space.

Use part of this area for compact-storage metadata, for example:

collection storage metadata magic/version
schema root page id
reserved flags / future fields

Do not blindly interpret old reserved bytes.

Existing v8/v9 CollectionPages must be treated as having no compact metadata until an explicit collection-storage marker is present. New-format collections write the marker. Lazily promoted old collections initialize it on first compact write.

SchemaPage

Add a dedicated engine page type, e.g. PageType.Schema.

Why a dedicated page instead of BSON documents:

• no recursive dependency on the document codec
• page ownership naturally belongs to the collection
• WAL/snapshot behavior is inherited from normal engine pages
• dropping a collection can reclaim its schema pages
• no global lock
• catalog structure can be purpose-built and bounded

A schema catalog can initially be a simple page chain. Optimize only if profiling shows lookup/append cost matters.

The root should maintain enough metadata for efficient append, such as:

catalog format version
next schema id
tail page id
schema count

Schema entries are append-only/immutable after commit.

V1 schema entry

Start simple:

schema id
ordered field count
ordered UTF-8 field names
fingerprint/checksum

Do not require a separate field-name dictionary in V1.

A second dictionary level (FieldId -> field name) can reduce duplication between many schema versions, but it adds another indirection and corruption surface. Add it later only if schema-catalog size is measurable.

The big win already comes from field names existing once per schema instead of once per document.

Schema fingerprint

A wrong schema mapping is more dangerous than an obvious read failure because values could be assigned to the wrong field names.

Store a deterministic fingerprint/checksum of the exact ordered schema definition.

Compact document references should carry enough verification information to detect a stale/wrong schema reference (for example SchemaId + a compact fingerprint).

The exact width is a storage/robustness trade-off to benchmark, but the goal is:

schema mismatch => deterministic corruption exception, never silently wrong BsonDocument.

Catalog loading should also validate its stored fingerprint against the schema definition.

Schema lifecycle / avoiding schema explosion

LiteDB is schemaless, so this cannot assume POCO-like data.

Pathological examples include:

• documents with random field names
• telemetry/maps where keys are data
• constantly changing shape
• same fields inserted in many different orders
• one-off nested objects

Therefore compact encoding must always have a fallback.

Proposed behavior

1. Reuse an existing schema when it can reconstruct the document exactly.
2. Presence bitmap handles missing optional fields.
3. Type changes do not create a new schema.
4. Repeated shape evolution may create a new immutable schema.
5. Rare/dynamic fields may be encoded as inline extension fields when that preserves exact semantics.
6. If schema encoding would not be beneficial or cannot preserve behavior cleanly, store the document as legacy BSON.

Do not force every document into a schema.

Hard limits

Add defensive limits for:

• schemas per collection
• fields per schema
• total schema-catalog bytes
• schema name lengths
• nested depth / bitmap size

Once a collection exceeds the useful schema budget, fall back to inline/legacy representation rather than allowing metadata to grow without bound.

Unused schemas do not need online garbage collection in V1.

A full Rebuild naturally recreates the catalog from live documents and drops dead schema definitions.

Field order

Current BSON writing uses BsonDocument.GetElements(), including the special _id-first behavior.

Do not silently reorder user-visible documents.

V1 should use a schema only when the reader can reconstruct the same element order. If a shape/order cannot be represented without changing observable enumeration/JSON order, create another schema if worthwhile or fall back to legacy BSON.

Do not add complicated per-document permutations until benchmarks demonstrate they are worth it.

Field names from different documents that differ only by casing also must not accidentally be normalized by a shared schema if that would change the stored casing.

File version / library upgrade strategy

Use a new file-format capability/version (v10 is the obvious next number, but the number is just a placeholder until merged).

Current state:

• v8 = ordinary current format
• v9 = vector-capable format
• current vector work already demonstrates lazy, monotonic promotion

Generalize the vector-specific promotion mechanism into something like:

RequireFileVersion(requiredVersion)

Opening old databases

New engine opening v8/v9:

• read-only open: no changes
• writable open with no writes: no changes
• no automatic rebuild
• no scan/rewrite of existing documents

First compact write

Before any compact-format bytes can enter the WAL, durably promote the file header to the compact-capable file version.

This should follow the same fundamental rule as vector promotion:

1. write/promote the persisted header first
2. flush it durably
3. only then allow compact/schema pages into WAL
4. never downgrade the in-memory or persisted version afterward

If promotion succeeds but the user transaction later rolls back, the file may remain v10 with only legacy documents. That is safe and preferable to ever having compact bytes in a file whose header claims v8/v9.

Mixed-format database

After promotion:

• old untouched documents remain raw BSON
• newly inserted documents may be compact
• updated legacy documents may become compact
• compact and legacy documents can live on the same DataPage
• deleting the last compact document does not downgrade the file header

No database-wide migration is necessary.

Old LiteDB versions

Once the header is promoted, older LiteDB binaries must reject the file as unsupported rather than trying to read compact bytes.

That is a safe failure mode.

During initial rollout, compact writes should be behind an explicit setting/feature flag so users do not accidentally lose downgrade compatibility merely by updating a minor package and performing an ordinary write.

Before making compact writes the default, decide/document the policy for:

• new databases
• existing v8/v9 databases
• major-version vs minor-version rollout
• explicit legacy-compatibility mode

Hard rule regardless of policy: open alone never promotes.

Vector interaction

A compact document containing vectors should require the maximum capability once, not perform separate promotions.

The version system should be generalized away from vector-specific code so:

required = max(document-format requirement, value-type requirement)

is promoted atomically/monotonically.

Transaction / WAL / crash safety

Schema metadata is part of document correctness, so it must obey normal transaction visibility.

Same transaction

If a write needs a new schema:

create/update schema page
write compact document referencing schema
commit both in the same transaction

The document must never reference catalog state from another uncommitted transaction.

Collection write locks already serialize writes to the same collection, which is another reason to keep the catalog per collection.

Safepoints

A large transaction can flush dirty pages to WAL before commit.

That is okay if schema pages and data pages are normal transaction pages:

• either may reach WAL first
• neither is visible as committed until transaction confirmation
• recovery sees the committed transaction atomically

Add an invariant before commit that every compact schema reference written by the transaction resolves to a committed or same-transaction catalog entry.

Rollback

Rollback must:

• discard uncommitted schema page changes
• discard uncommitted compact document changes
• discard transaction-local schema-cache additions
• never publish an uncommitted schema into a global cache

The file-format header may remain promoted.

Cache semantics

A global schema cache may contain committed append-only definitions only.

New schema definitions should first live in transaction-local state and be published after successful commit.

Because committed schema IDs are immutable and append-only, a cache being newer than an older read snapshot is safe: older documents only refer to older immutable IDs.

Crash matrix that needs explicit tests

• crash before format promotion
• failure during header page write
• failure during header flush
• promotion completed, crash before any schema/document WAL write
• schema page reaches WAL, document does not
• document page reaches WAL, schema page ordering differs
• crash before confirmation record/page
• crash immediately after confirmation
• crash during checkpoint
• rollback after schema allocation
• safepoint between schema creation and document write
• encrypted database versions of all relevant promotion/checkpoint failures
• caller-provided stream versions where possible

The vector-format failure tests around #2881 are a useful model and should be generalized.

Query / index implications

The initial implementation should not change index storage.

Index nodes already point at a document PageAddress and store index keys separately. The physical representation of the document behind that PageAddress can therefore change without rebuilding indexes.

Expected behavior:

index lookup
  -> PageAddress
  -> DocumentStorageCodec
  -> BsonDocument
  -> existing query/expression code

No index migration is needed just because a document switches from legacy BSON to compact encoding.

Index creation paths

LiteDB/Engine/Engine/Index.cs currently bypasses DatafileLookup and directly constructs BufferReader over DataService.Read() while building normal/vector indexes.

Those paths must be routed through DocumentStorageC