Lab LD3: HNSW Vector Files on Disk

Background

Vectors are written by a KnnVectorsFormat into three files — .vec (the raw or quantized vectors), .vex (the HNSW graph adjacency), and .vem (metadata: dimension, similarity, the graph entry node, offsets, and quantization params). The HNSW chapter explained the algorithm and these files at a concept level; the masterclass index nailed the layout. In this lab you produce those files with KnnFloatVectorField + Lucene99HnswVectorsFormat, then:

1. Locate and size the .vec/.vex/.vem files with find/du.
2. Read their headers with xxd to confirm the CodecUtil magic and the codec name written into each file.
3. Reason about the on-disk layout: the .vec is vectors back-to-back (offset = ord × dims × 4); the .vex is per-level neighbour lists; the .vem names the entry node.
4. Compare raw vs scalar-quantized storage by building the same index with Lucene99HnswScalarQuantizedVectorsFormat and diffing .vec sizes.

Finally you map all of it to OpenSearch's k-NN lucene engine (engines chapter).

Why This Matters for Contributors

Vector indices are where disk and RAM pressure show up first: a float32 768-dim vector is 3 KB, and the graph plus vectors must sit in page cache for fast search. A contributor who can find the .vec/.vex/.vem, read their headers, and compare quantized vs raw sizes can diagnose "k-NN search is slow / OOM on merge / disk blew up" issues and reason about the recall/memory trade-off of quantization. Because the lucene engine is Lucene HNSW, this is the exact storage OpenSearch ships.

Prerequisites

• JDK 17+ and a lucene-core-*.jar (the HNSW format is in core). Set export LUCENE_CP=... as in Lab LD1.
• find, du, xxd on PATH.
• Read index.md (the HNSW section) and hnsw-vector-search.md.

export LUCENE_CP="/path/to/lucene-core-9.x.x.jar"
export LUCENE_SRC="/path/to/lucene/lucene/core/src/java/org/apache/lucene"

Note: Format class names carry a version (Lucene99..., Lucene104...). If a class below doesn't resolve, grep for the current one: grep -rln "HnswVectorsFormat" "$LUCENE_SRC/codecs/".

Step-by-Step Tasks

Step 1 — Index float vectors (raw float32)

Vectors.java indexes 5000 random 64-dim vectors with the default HNSW format and a cosine similarity, then runs a k-NN query. We keep dims small (64) so the files are readable but the structure is identical to 768-dim.

import org.apache.lucene.codecs.Codec;
import org.apache.lucene.codecs.KnnVectorsFormat;
import org.apache.lucene.codecs.lucene99.Lucene99HnswVectorsFormat;
import org.apache.lucene.codecs.perfield.PerFieldKnnVectorsFormat;
import org.apache.lucene.document.*;
import org.apache.lucene.index.*;
import org.apache.lucene.search.*;
import org.apache.lucene.store.*;
import java.nio.file.*;
import java.util.Random;

public class Vectors {
  static final int DIMS = 64, N = 5000;

  static float[] randomVec(Random rnd) {
    float[] v = new float[DIMS];
    for (int i = 0; i < DIMS; i++) v[i] = rnd.nextFloat();
    return v;   // cosine normalizes internally
  }

  public static void main(String[] args) throws Exception {
    Path dir = Paths.get("ld3-vec-raw");
    Random rnd = new Random(42);
    try (Directory d = FSDirectory.open(dir)) {
      IndexWriterConfig cfg = new IndexWriterConfig();
      cfg.setUseCompoundFile(false);
      // Default HNSW: float32 vectors + graph. M=16, beamWidth=100 by default.
      cfg.setCodec(new org.apache.lucene.codecs.lucene99.Lucene99Codec() {
        @Override public KnnVectorsFormat getKnnVectorsFormatForField(String field) {
          return new Lucene99HnswVectorsFormat(16, 100);   // (maxConn=M, beamWidth=efConstruction)
        }
      });
      try (IndexWriter w = new IndexWriter(d, cfg)) {
        for (int i = 0; i < N; i++) {
          Document doc = new Document();
          doc.add(new KnnFloatVectorField("embedding", randomVec(rnd),
              VectorSimilarityFunction.COSINE));
          doc.add(new StoredField("id", i));
          w.addDocument(doc);
        }
        w.forceMerge(1);   // one segment -> one .vec/.vex/.vem, easiest to inspect
        w.commit();
      }

      try (DirectoryReader r = DirectoryReader.open(d)) {
        IndexSearcher s = new IndexSearcher(r);
        float[] q = randomVec(new Random(7));
        TopDocs hits = s.search(new KnnFloatVectorQuery("embedding", q, 10), 10);
        System.out.println("kNN top-10 totalHits=" + hits.totalHits);

        for (LeafReaderContext ctx : r.leaves()) {
          FloatVectorValues fvv = ctx.reader().getFloatVectorValues("embedding");
          if (fvv == null) continue;
          System.out.println("FloatVectorValues: dims=" + fvv.dimension()
              + " size=" + fvv.size());   // 64 and 5000
        }
      }
    }
  }
}

javac -cp "$LUCENE_CP" Vectors.java
java  -cp "$LUCENE_CP:." Vectors

Expected:

kNN top-10 totalHits=10
FloatVectorValues: dims=64 size=5000

Step 2 — Find and size the vector files

find ld3-vec-raw -name "*.vec" -o -name "*.vex" -o -name "*.vem"
# ld3-vec-raw/_X.vec   ld3-vec-raw/_X.vex   ld3-vec-raw/_X.vem

du -h ld3-vec-raw/_*.vec ld3-vec-raw/_*.vex ld3-vec-raw/_*.vem

Sanity-check the .vec size against the layout size = N × dims × 4 + header/footer:

5000 vectors × 64 dims × 4 bytes = 1,280,000 bytes ≈ 1.3 MB   <- ~ your .vec size

The .vec is just the vectors back to back — that is why du matches the arithmetic so closely (only the small CodecUtil envelope is overhead). The .vex (graph) is much smaller and its size tracks M (16 here): roughly N × ~M × neighbour-bytes plus per-level lists. The .vem is tiny — fixed metadata.

Step 3 — Read the headers with xxd

# Every Lucene file starts with CODEC_MAGIC 0x3FD76C17, then the codec/format name.
xxd -l 48 ld3-vec-raw/_*.vec
xxd -l 48 ld3-vec-raw/_*.vex
xxd -l 48 ld3-vec-raw/_*.vem

You should see, on each:

00000000: 3fd7 6c17 ....  4c75 6365 6e65 3939 ...   ?.l.....Lucene99...
          ^^^^^^^^^ CODEC_MAGIC          ^^^^^^^^^^^^ "Lucene99..." format name

The four bytes 3F D7 6C 17 are CodecUtil.CODEC_MAGIC; the string after the version/length is the format name written by CodecUtil.writeIndexHeader. Confirm in source:

grep -rn "CODEC_MAGIC\|writeIndexHeader" "$LUCENE_SRC/codecs/CodecUtil.java"
grep -rn "META_CODEC_NAME\|VECTOR_DATA_CODEC_NAME\|VECTOR_INDEX_CODEC_NAME\|entryNode\|writeGraph\|writeMeta" \
  "$LUCENE_SRC/codecs/lucene99/Lucene99HnswVectorsFormat.java" \
  "$LUCENE_SRC/codecs/lucene99/Lucene99HnswVectorsWriter.java" 2>/dev/null | head

Step 4 — Reason about the on-disk graph layout

You can't pretty-print the .vex adjacency without the reader, but you can verify the shape by reading the writer/reader source and the metadata:

# The metadata file records the entry node and per-level offsets:
grep -n "entryNode\|writeMeta\|numLevels\|nodesByLevel\|writeField" \
  "$LUCENE_SRC/codecs/lucene99/Lucene99HnswVectorsWriter.java" | head

# The reader's neighbour iteration (this is the graph walk at query time):
grep -rn "class .*HnswGraph\b\|nextNeighbor\|seek\|class OffHeapHnswGraph" \
  "$LUCENE_SRC/codecs/lucene99/" | head

The structure, from the masterclass index:

flowchart TD
    Vem[".vem (metadata)"] -->|dims, similarity| Cfg["64 dims, COSINE"]
    Vem -->|entry node| Entry["entryNode ordinal (top layer)"]
    Vem -->|per-level offsets| Vex[".vex graph"]
    Vex -->|"layer L: neighbour ord lists"| Adj["adjacency per node per level"]
    Vem -->|offset into .vec| Vec[".vec raw float32, ord-contiguous"]
    Vec -->|"offset = ord*dims*4"| V0["vector for ordinal 0, 1, 2 ..."]

Key facts to internalize:

• .vec random access: vector for ordinal ord lives at byte ord × dims × bytesPerComponent (+ header). Float32 ⇒ 4 bytes; that contiguity is what the SIMD distance loops exploit.
• .vex holds, per node and per level, the list of neighbour ordinals (bounded by M, or 2·M on layer 0 in some impls). Higher levels have fewer nodes (the "express lanes").
• .vem names the single entry node the greedy search starts from, plus the per-level node counts and the offsets that tie .vec/.vex together.

Step 5 — Build the same index scalar-quantized, compare sizes

Now switch the format to Lucene99HnswScalarQuantizedVectorsFormat (int8) and diff .vec sizes. Copy Vectors.java to VectorsQuant.java, change the directory to ld3-vec-q and the format line:

import org.apache.lucene.codecs.lucene99.Lucene99HnswScalarQuantizedVectorsFormat;
// ...
cfg.setCodec(new org.apache.lucene.codecs.lucene99.Lucene99Codec() {
  @Override public KnnVectorsFormat getKnnVectorsFormatForField(String field) {
    // int8 scalar-quantized HNSW: ~1/4 the .vec bytes of float32.
    return new Lucene99HnswScalarQuantizedVectorsFormat(16, 100);
  }
});

javac -cp "$LUCENE_CP" VectorsQuant.java
java  -cp "$LUCENE_CP:." VectorsQuant

# Compare the vector data files:
echo "RAW  float32:"; du -b ld3-vec-raw/_*.vec
echo "QUANT int8  :"; du -b ld3-vec-q/_*.vec

Expected: the quantized .vec is roughly ¼ the raw size (1 byte/component vs 4), plus a small per-vector/per-segment quantile stored in metadata. For 5000 × 64:

RAW  float32: ~1,280,000 bytes
QUANT int8  :   ~320,000 bytes (+ quantiles)   -> ~4x smaller

Note: Scalar quantization is lossy. The standard production pattern is search the quantized graph for candidates, then rescore against full-precision vectors. OpenSearch's disk-based ANN does exactly this — see quantization and disk-ANN. The Lucene104* formats generalize the bit width (1/2/4/7/8 bits) to dial memory vs recall finer.

Step 6 — Validate with CheckIndex

cp -r ld3-vec-raw ld3-vec-copy
java -cp "$LUCENE_CP" org.apache.lucene.index.CheckIndex ld3-vec-copy -verbose 2>&1 \
  | grep -iA3 "test: vectors\|knn\|vector"

The vectors test reads back every vector and walks the graph, validating the .vec/.vex/.vem checksums — proof the files you sized are internally consistent.

Step 7 — Map to OpenSearch k-NN lucene engine

The OpenSearch field config that produces exactly these files:

PUT /products
{
  "settings": { "index.knn": true },
  "mappings": { "properties": { "embedding": {
    "type": "knn_vector",
    "dimension": 64,
    "space_type": "cosinesimil",
    "method": { "name": "hnsw", "engine": "lucene",
      "parameters": { "m": 16, "ef_construction": 100 } }
  }}}
}

So a find …/<shard>/index -name '*.vec' on a real k-NN-with-engine:lucene index shows the same three files you just produced. The native faiss engine writes its own graph file instead — see k-NN engines.

Deliverables

• Vectors.java — indexes float32 vectors, runs a k-NN query, prints FloatVectorValues dims/size.
• A find/du capture of .vec/.vex/.vem with the .vec size checked against N × dims × 4.
• An xxd capture of each file's CODEC_MAGIC + format name.
• VectorsQuant.java + a du -b diff showing the int8 .vec ≈ ¼ the float32 .vec.
• A CheckIndex vectors-test capture.

Troubleshooting

Expected Output

Three vector files whose sizes match the byte arithmetic, a CODEC_MAGIC-confirmed header on each, a ~4× shrink from float32→int8 quantization, and a clear mapping from these files to an OpenSearch knn_vector field with engine: lucene.

Stretch Goals

• Vary M. Rebuild with M = 8, 16, 32; chart .vex size — it grows with M, confirming the graph (not the vectors) is what M controls.
• 768 dims. Bump DIMS to 768 and N to 10k; the .vec is now ~30 MB — observe how quickly raw float32 vectors dominate disk, motivating quantization.
• Read a vector by ordinal. Use FloatVectorValues random access to fetch the vector at ordinal 0 and confirm it equals what you indexed (seed-reproducible).
• Real OpenSearch shard. Create the products index above, index a few vectors, find the shard, and confirm the same three extensions appear.
• faiss contrast. Switch engine to faiss on a second field and observe the different on-disk file (native graph) — see k-NN engines.

Coding Exercises

These exercises turn "size and reason about the files" into graded code. Each is a standalone Java program or JUnit test against the Lucene jars on $LUCENE_CP — no Gradle. Build on Vectors.java and VectorsQuant.java.

1. (warm-up) Assert random access by ordinal. Extend Vectors.java into a JUnit test VecByOrdTest that, after indexing with a fixed Random(42) seed, uses FloatVectorValues random access to fetch the vector at ordinal 0 and asserts it equals the first vector you generated (regenerate from the same seed). This proves the .vec layout offset = ord × dims × bytesPerComponent gives O(1) lookup.

2. (warm-up) Verify the .vec byte arithmetic in code. Write VecSizeCheck that reads the on-disk .vec length with Files.size(...) and asserts it equals N × dims × 4 plus the CodecUtil header+footer (header = indexHeader length + footer = 16 bytes; locate the constants with grep -n "footerLength\|CODEC_MAGIC\|writeIndexHeader" "$LUCENE_SRC/codecs/CodecUtil.java"). Print the residual and confirm it is exactly the envelope, not data.

3. (core) Measure the float32→int8 ratio as a test. Combine Vectors and VectorsQuant into one test QuantRatioTest that builds both indices, reads both .vec sizes, and asserts the int8 .vec is between 0.2× and 0.3× the float32 .vec (≈¼ plus quantiles). Then assert k-NN recall@10 of the quantized index against the raw index's results is ≥ some threshold on your random data — quantifying the recall cost of the size win. (This is the rescore motivation; see quantization-and-disk-ann.md.)

4. (core) Chart .vex growth with M. Write MSweep that builds the index three times with M ∈ {8, 16, 32} (same N, DIMS, seed), records each .vex size, and asserts vex(8) < vex(16) < vex(32) while the .vec size is unchanged across all three. This isolates that M controls the graph file, not the vector file — the structural claim behind the lab.

5. (advanced) Advanced challenge — walk the off-heap HNSW graph and verify degree bounds. Locate the graph reader: grep -rln "OffHeapHnswGraph\|class HnswGraph\b\|nextNeighbor" "$LUCENE_SRC/codecs/lucene99/" "$LUCENE_SRC/util/hnsw/". Write GraphWalk that opens the index reader, obtains the HnswGraph for your field (you may need the codec reader / a small reflection or test-scoped accessor — note the access path you used), seeks the entry node, and for every node on level 0 counts neighbours via seek(level, node) + nextNeighbor(). Assert (a) the entry node is the one named in .vem, and (b) no level-0 node exceeds 2·M neighbours — the degree invariant HNSW maintains. Print the average degree. Deliverable: a JUnit test that fails loudly if any node violates the 2·M bound.

Issues to Practice On

The HNSW vector format lives in apache/lucene (KnnVectorsFormat, Lucene99HnswVectorsWriter, HnswGraphBuilder); the OpenSearch lucene engine just wires to it. Apache workflow: GitHub issues + PRs, a CHANGES.txt entry — no DCO. For OpenSearch-side k-NN wiring bugs, the repo is opensearch-project/k-NN. Find work with:

gh label list --repo apache/lucene | grep -iE "good first|core/|new feature"   # confirm taxonomy (labels move; check the tracker)
gh issue list --repo apache/lucene --label "good first issue" --state open
gh issue list --repo apache/lucene --search "HNSW OR KnnVectors OR vector in:title,body" --state open
# OpenSearch-side (lucene engine / knn_vector mapping):
gh issue list --repo opensearch-project/k-NN --label "good first issue" --state open
gh issue list --repo opensearch-project/k-NN --search "lucene engine OR quantization in:title,body" --state open

Representative issue patterns:

• Quantization / format size or recall. "Scalar-quantized .vec bigger than expected," "recall drop after merge." Approach: reproduce with a synthetic index, measure .vec/.vex sizes and recall@k as a test, locate the writer (rg "ScalarQuantizer\|Lucene99HnswScalarQuantizedVectorsWriter"), bisect.
• Graph build / merge correctness. "Entry node wrong after merge," "neighbour list exceeds M." Approach: write a degree-bound assertion (exercise 5), reproduce on a force-merge, locate HnswGraphBuilder/IncrementalHnswGraphMerger via rg.

Planted-bug drill. In a copy of Vectors.java, change the query vector's dimension from DIMS to DIMS + 1 and re-run: you should get IllegalArgumentException: vector's dimension differs. Now harden: add a JUnit test assertThrows(IllegalArgumentException.class, ...) that would have caught the mismatch — the same invariant that produces the #1 OpenSearch k-NN error ("dimension mismatch"). Then plant a subtler one in GraphWalk: assert < M instead of ≤ 2·M and watch a legitimate level-0 node fail the bound; revert and note the real invariant.

Etiquette: claim the issue first, reproduce before coding; Apache Lucene PRs need a test + CHANGES.txt (no DCO), OpenSearch k-NN PRs need a test + CHANGELOG entry + DCO Signed-off-by (git commit -s). See community-interaction.md.

Validation: prove you understand this

1. Map .vec/.vex/.vem to their contents and say which one grows with M and which names the entry node.
2. From your du, show the .vec size matches N × dims × 4 and explain why the layout makes random access by ordinal O(1).
3. Identify the CODEC_MAGIC bytes in your xxd and the format name that follows.
4. Explain the float32→int8 size ratio you measured and why quantization needs a rescore pass for top-quality recall.
5. Translate the OpenSearch knn_vector config (engine: lucene, m, ef_construction, space_type) into the Lucene format, M, beamWidth, and VectorSimilarityFunction it produces.
6. Explain why a force-merge of a vector index is expensive (the graph is rebuilt — see HNSW chapter) and what .vex churn you would observe.

When you can do all six, continue to Lab LD4: DocValues Encodings.