Skip to main content

Manifests, not indexes — routing a query with no map

· 3 min read
The Gnarl team
The Gnarl team
Lucenia

Ask a distributed search engine where a document lives and it consults something that knows: a routing table, a shard map, a coordinator. Take that away and the obvious question is how anything gets found at all.

Elimination beats lookup​

Gnarl never asks "who has this document?" It asks "who can I rule out?"

Every node publishes a manifest: a compact, signed statement of what it can answer. A few kilobytes, whether the node holds fifty thousand documents or fifty million.

{
  "index": "imagery",
  "doc_count": 48219,
  "fields": ["title", "captured_at", "sensor"],
  "summary": {
    "time_range": ["2019-03-01T00:00:00Z", "2026-07-28T00:00:00Z"],
    "bbox": [-124.7, 24.5, -66.9, 49.4],
    "terms": "bloom:8kb:base64…"
  },
  "signature": "ed25519:9c41…2f7e"
}

Given a query, the planner walks its cached manifests and discards every node it can prove cannot contribute:

Query saysManifest saysResult
captured_at > 2024newest doc is 2021eliminated
within(puget sound)bbox is over Europeeliminated
match("glacier")Bloom filter says noeliminated
sensor = "landsat-8"never seen that sensoreliminated

Whatever survives gets asked.

Why this is safe​

Every summary is conservative by construction. A Bloom filter can say "maybe" when the answer is no, but it can never say "no" when the answer is yes. A bbox is always the enclosing box, never a tighter one. A time range always spans the extremes.

So the failure mode is asking a node that turns out to have nothing — one wasted round trip. The failure mode that would actually hurt, silently skipping a node that had the answer, is structurally impossible.

The cost of being wrong is bounded​

False positives are not free, so queries carry a budget:

{"scope": {"max_nodes": 64, "deadline_ms": 750, "min_coverage": 0.9}}

When more nodes survive elimination than the budget allows, the planner ranks survivors by expected contribution — how strongly the manifest matched, how fast that node has been answering lately, how often it has answered at all — and asks the best ones first.

The response reports exactly what happened, so "we asked 64 of 300 eligible nodes" is a fact the caller gets to see rather than a detail buried in the runtime.

Propagation​

Manifests gossip. A node pushes a new version to a random subset of peers, which forward it on until the network converges — seconds, on networks of hundreds of nodes.

Versions are monotonic and signed. A stale manifest cannot overwrite a fresh one, and a peer cannot publish a manifest on somebody else's behalf.

What this buys​

Adding a node is starting a process. It indexes what it can already read, gossips a manifest, and starts receiving the queries it can answer. Nothing rebalances. No map is updated. Nobody is told to make room.

More detail in Routing and manifests.