Module image 

The index image: what a checkpoint points at so an index does not have to be rebuilt from the records it was built from.

CheckpointEntry::index_image_addr has been in the superblock since the format was first written down and nothing has pointed at anything yet. This is the first thing it points at, and it is the vector index, because the vector index is the one that costs real money to rebuild: a million vectors is a million quantisations and a few thousand partitions that arrived at their shape through a long sequence of splits, merges and sweeps. Replaying the records gives back the vectors. It does not give back the shape, and rebuilding the shape on open is the outage the whole update protocol exists to avoid.

It is chunks, not a record kind

06 fixes the record kinds and there is no kind for an index, which is deliberate: an index is derived, so a reader that has never heard of it must be able to walk straight past it. So an image is written as CollectionChunk records through the chain in yo-kv, exactly the way a demoted collection is, and the only thing that knows the chunks mean an index is the checkpoint entry that points at them. A reader that ignores the checkpoint sees a run of chunks nobody claims and compaction drops them.

10 section 2 is where the shape comes from: a partition is a natural chunk. At the default posting size and 768 dimensions a partition is about 32 KiB, which is half of one chunk, so a partition is one chunk and one read almost always, and a partition that has grown past a chunk is a chain of its own rather than a special case.

  root                        one per partition
+------------------+        +---------------------------+
| header, 100 bytes |        | count | code_bytes | stuck |
+------------------+        +---------------------------+
| centroid chain   |        | ids      count * 8        |
| key chain        |        | tags     count * 8        |
+------------------+        | codes    count * width    |
| partition 0      | -----> | meta     count * 16       |
| partition 1      |        +---------------------------+
| ...              |
+------------------+

The four arrays inside a partition are separate runs rather than one run of structures, and that is the same reason the posting itself is laid out that way in memory: a scan that only wants the tags reads only the tags. A cold partition can be brought in one array at a time for the same reason.

What is not in here

The vectors. They are records of kind 3 already (crate::vector), at addresses the log resolves, and G8’s budget is 96 bytes of index for a 768 dimensional vector with the raw copy in the log. An image that carried them as well would write every vector twice and spend the whole gate to save a walk. So loading an image is two halves: the image gives the shape and the codes, and the log gives the vectors back under the keys the image names.

No checksum either, and that is not an omission. Every chunk of an image is a record, every record carries a CRC32C over its own bytes, and the chain’s directory is a record too, so a second checksum inside the image would cover bytes that are already covered. What a checksum cannot catch is an image that is intact and stale, and that is what the checkpoint’s log addresses are for.

The freeze

This layout is frozen with the rest of the format at the end of M6. After that the only lever is min_reader_version (07 section 9), so the fields that exist to be changed later exist now: ImageHeader::kind so that a document or graph index can have an image beside this one, flags in both headers so that a section can be added to an image a version one reader then refuses one image at a time, and bits and metric as their own bytes rather than as something a reader has to infer.

An image is a cache in the end, which is the safety net under all of it: a reader that does not like an image can throw it away and rebuild from the records, slowly and correctly.

Modules

image_kind

What kind of index an image holds.

metric

How a vector is compared, as the byte the image stores.

Structs

Chain

Where a section went and how long it is.

ImageHeader

The root of an image: everything the index is, apart from the members.

Keys

The key table, one entry at a time.

PostingHeader

The fixed part at the front of one partition’s image.

Constants

IMAGE_HEADER_LEN

The fixed part at the front of an image root.

IMAGE_TAG

The four bytes an image starts with, so that a stray chunk is not read as one.

META_LEN

What a code needs beside it: norm, scale, lo and delta, four f32.

PARTITION_ENTRY_LEN

One line of the partition table that follows the root header.

POSTING_HEADER_LEN

The fixed part at the front of one partition’s image.

Functions

get_floats

Reads floats back out of bytes into out, which says how many.

get_partition

Reads partition i’s chain back out of an encoded root.

image_len

How long an image root with this many partitions is.

key_entry_len

How many bytes a key of klen takes in the key table.

posting_len

How long one partition’s image is.

put_floats

Writes floats into into end to end and says how many bytes that took.

put_key

Writes one key table entry and says how long it was.

put_partition

Writes partition i’s chain into an encoded root.