Scaling to 1B Memories: Index Tiers

Memory infrastructure decisions are different from "vector database" decisions. The access pattern is per-user namespaced; the typical user store is small; the global store is enormous. The right architecture depends on which dimension dominates your scale, and the answer changes as you grow.

Tier 1 — a single shard

Up to 100K memories per user-store. One Brain shard — a single thread-per-core Glommio executor holding its HNSW index in RAM, backed by its own memory-mapped arena, WAL, and redb metadata store. Read latency is sub-millisecond on the retrieval path.

• When to use: single-tenant agents, prototypes, low-traffic services.
• When to leave: multi-tenancy, >100K per user, or throughput that saturates a single core.
• Failure mode: one shard is one core. Once its write path and index maintenance saturate that core, p99 rises and there's no headroom left to absorb bursts.

Tier 2 — multiple thread-per-core shards, one node

Up to ~10M memories. One Brain server process running N shards — one Glommio executor pinned per core, each shard owning its own arena, WAL, redb, HNSW, and tantivy indexes end to end. Requests hash to a shard by namespace and the shards run fully in parallel with no shared locks.

• When to use: SaaS at any reasonable scale on a single well-provisioned box.
• When to leave: p99 query latency rises above your SLO; the node's RAM can't hold all shards' HNSW indexes; or you need failure isolation across machines.
• Failure mode: you run out of cores or RAM on one machine; adding shards past the core count over-subscribes the CPU.

Tier 3 — multiple nodes

Up to ~100M memories. Several Brain nodes, each running its full complement of thread-per-core shards, with a routing layer that picks the node+shard by namespace hash. Each shard still owns its own indexes end to end.

• When to use: you've hit the single-node ceiling; you want failure isolation and independent scaling per node.
• When to leave: rebalance orchestration becomes a bottleneck; cross-namespace queries become common.
• Failure mode: coordinated rebalancing when adding nodes; consistency-during-migration; tail-latency outliers from straggler shards.

Tier 4 — a multi-node sharded cluster

100M+ memories. Many Brain nodes under a coordinator, with rebalancing, replication, and per-namespace placement. The unit of scale is still the shard — you simply run a great many of them across the fleet.

• When to use: billion-scale; recall vs cost is a real constraint.
• When to leave: you start questioning whether you actually need a billion memories — usually you don't, and aggressive consolidation is cheaper than infra growth.
• Failure mode: operational complexity; rebalancing coordination; keeping the fleet's tail latency in budget.

Vector store ≠ memory store

The vector index is one component. A real memory store also holds:

• Lexical index (BM25, via tantivy).
• Entity graph (typed edges, hop traversal).
• Temporal index (B-tree on event timestamps).
• Audit ledger (supersession chains, access counts).
• Metadata (confidence, type, freshness). Brain bundles all of these into every shard. Teams that instead bolt a bare vector DB onto their stack find it manages none of them — a specialized vector DB handles only the ANN index, so they end up running a separate relational store (typically Postgres) for the graph, temporal, audit, and metadata layers, with a coordinator fanning out across the two. The memory store is the whole set, not the vector index alone.

Reality check

Most teams that imagine they need 1B memories don't. A typical memory system at 1M users and ~200 retained memories per user is 200M memories — comfortably tier 3. Above that, consolidation usually beats further scale-out: aggressive supersession + decay reduces memory counts faster than user growth grows them. Before reaching for tier 4, audit your store. What's your dedup rate? Your supersession rate? Your decay floor? An aggressive cleanup pass often shrinks the store enough to stay in tier 3 for another year.

HNSW parameter math

Understanding HNSW parameters makes tier transitions easier to reason about.

Memory cost:

bytes_per_vector ≈ dims × 4 + m × 8 × log₂(N)

For N = 1M vectors, dims = 1536, m = 16:

bytes_per_vector ≈ 6,144 + 128 × 20 ≈ 8,700 bytes
Total index ≈ 8.3 GB in RAM

At N = 10M, the log₂ term grows by ~3 bits: index grows to ~85 GB. This is where tier 2 becomes uncomfortable on typical 64GB server RAM — you start fighting the OS page cache.

Build time:

T_build ≈ N × log(N) × m × ef_construction / parallelism

Empirically: 1M vectors on 8 cores → 20–40 minutes at ef_construction = 200. 10M vectors → 4–8 hours. At 10M, you care about incremental insertion latency (amortized log(N) per insert) rather than cold rebuild time.

Query time:

T_query ≈ log(N) × ef_search × vector_distance_cost

ef_search = 80: ~5–15ms for 1M vectors, ~15–30ms for 10M. Raising ef_search increases recall@k but costs linearly. At 10M memories with ef_search = 120, you start bumping against p99 SLOs if your SLO is 100ms end-to-end.

When HNSW starts breaking down

HNSW becomes problematic above ~50M vectors on a single node:

• Index build time exceeds maintenance windows. A nightly rebuild of a 50M-vector index takes 8+ hours on a 16-core machine. You can't afford nightly rebuilds.
• RAM footprint exceeds available memory. At 50M vectors with m=16, the index is ~4GB. Combined with the data tables and OS page cache, this pushes you to 128GB+ servers.
• Partial indexes become necessary for multi-tenancy: a global HNSW at 50M must post-filter by namespace, which reduces effective ef_search headroom and hurts recall.

Tier 3 solutions: time-partitioned HNSW per namespace (smaller indexes, faster rebuilds, cold tiering for old partitions). Tier 4: consider DiskANN (disk-resident approximate NN for memory-constrained environments) or IVF-PQ (product quantization reduces index size by 10–30× at modest recall cost).

Four-layer cache system

Independent of scale tier, Brain stacks four caches:

L2 (entity attribute) is what makes entity resolution fast — looking up "Priya" and getting ent_priya_XYZ with attributes hits the shard-local cache in under 2ms rather than reading from the redb metadata store. L4 is Brain's defining choice: each shard keeps its HNSW graph resident in RAM rather than paging it from disk, so queries never stall waiting for index pages to load.

Re-embedding at scale: the shadow strategy

When you change embedding models, you can't just swap the model and rebuild — old embeddings in the index are incompatible with new query embeddings. The shadow strategy runs the two models in parallel:

1. Dual-write: new memories embed with both old (v1) and new (v2) models.
2. Backfill: background job re-embeds historical memories with v2. Rate-limited to avoid provider throttling. Checkpointed for resumption.
3. Shadow query: reads compute results with both v1 and v2, comparing top-K overlap via Jaccard divergence. Alert if divergence > 0.5.
4. Validation: run LongMemEval-style probes against both versions.
5. Cutover: queries switch to v2. v1 retained for N days as rollback.
6. Cleanup: drop v1 column and index.

Cost to re-embed 10M memories at OpenAI text-embedding-3-small rates: ~$4 and ~1 week at 3,000 RPM. Most of the "cost" is time, not dollars — plan accordingly.

Scaling lexical and graph indexes alongside vectors

The vector index gets the most attention in scaling discussions, but it is only one of five indexes in a memory store. Scaling to 100M+ memories requires planning all five in parallel — the vector index rarely becomes the bottleneck first.

BM25 / GIN index

PostgreSQL's GIN index for full-text search scales differently from HNSW. At 10M memories, a GIN index on to_tsvector(content) is approximately 2–4 GB. Build time for a fresh GIN at 10M records: 10–15 minutes. Unlike HNSW, GIN supports parallel index builds natively in PostgreSQL 11+, so the cold-build story is friendlier.

The bottleneck at 100M records is not build time but write-time maintenance: every INSERT updates the GIN index, which involves updating potentially thousands of posting lists. At high write rates (1,000+ turns/second), GIN writes become a measurable bottleneck. The mitigation is gin_pending_list_limit, which batches GIN updates into a pending list and flushes them asynchronously during vacuums rather than on every write. This can cut write-time GIN overhead by 60–80% at the cost of slightly stale full-text index state (typically seconds, not minutes).

At 100M memories, the GIN index is 20–40 GB. This is large but manageable on a dedicated Postgres instance. The GIN does not need to live on the same machine as the HNSW — at tier 3, BM25 traffic can route to a read-replica while ANN traffic routes to the primary or dedicated vector DB.

Entity graph (edge table)

The entity graph scales by node and edge count, not by memory count. A namespace with 10M memories might have 500K entities and 2M edges. A Postgres table with 2M rows is trivial — the entity graph scales easily to 100M edges before requiring specialized infrastructure.

Edge traversal (multi-hop queries) uses recursive CTEs or WITH RECURSIVE in PostgreSQL. Performance characteristics:

• 2-hop traversal at 2M edges: under 5ms
• 3-hop traversal at 2M edges: 15–50ms depending on fan-out
• 4-hop traversal: exponential growth in intermediate results, frequently timing out

Cap hop depth at 3 in production. Beyond 3 hops, the signal-to-noise ratio falls below retrieval usefulness on real conversational graphs — and the query time cost is significant. The practical answer to "why limit at 3 hops?" is that measured LongMemEval scores do not improve past 3 hops while query latency rises sharply.

Temporal BTREE index

The event_at BTREE index is the cheapest to maintain of all five. BTREE is update-friendly and scales linearly with row count. At 10M event memories, a range scan for a 7-day window returns fewer than 1,000 results in 2–5ms. The temporal index does not require sharding until 500M+ events. If you are sharding before that threshold, shard by namespace_id first, which collocates each user's temporal data on one shard and keeps range scans local.

Metadata indexes

Confidence, status, schema_version, and namespace — composite indexes cover these. A composite index on (namespace_id, status, confidence) enables the most common filter pattern (all active memories for a user above a confidence threshold). At 100M memories, this index is approximately 3–4 GB. Unlike GIN, composite BTREE indexes have minimal write-time overhead — they add roughly 10–20% to INSERT cost rather than the potentially large posting-list updates GIN requires.

The key insight across all five indexes: GIN is the write-time bottleneck at high write rates, HNSW is the RAM bottleneck at high memory counts, and the graph and temporal indexes scale without drama until you are well into tier 3. Plan your scaling headroom for GIN and HNSW first; the others will not surprise you.

Multi-tenant scaling patterns

A memory system serving 1M users has different scaling constraints than one serving 1K users. The unit of isolation is the namespace (one per user, typically); the challenge is that all namespaces share infrastructure while having wildly different usage profiles.

Per-user namespace isolation

Row-level security in PostgreSQL enforces that queries with WHERE namespace_id = $user_namespace only see their namespace's rows. This is correct and necessary, but adds a predicate to every query. At 10M total memories across 100K users (average 100 memories/user), the namespace predicate is cheap — most indexes include namespace_id as a leading column, so the predicate prunes at index traversal time rather than requiring a heap scan.

The index design that makes this work: all five indexes should use namespace_id as the leftmost column in composite indexes, or — for HNSW — pair the vector index with a namespace_id filter that applies during approximate neighbor search rather than post-hoc. pgvector supports filtering via WHERE predicates on top of HNSW, but with degraded recall if the filter is highly selective. The workaround is per-namespace HNSW indexes for large namespaces (discussed below).

Hot namespace problem

Some users have vastly more memories than others: power users with long conversation histories, or organizations sharing a single namespace. A namespace with 500K memories uses more resources than 5,000 namespaces with 100 memories each — not just in storage, but in HNSW recall degradation (post-filter selectivity), BM25 query time (more posting list entries), and graph traversal fan-out (more edges per hop).

Identify hot namespaces by memory count with a simple query run weekly:

SELECT namespace_id, COUNT(*) AS memory_count
FROM memories
GROUP BY namespace_id
ORDER BY memory_count DESC
LIMIT 20;

Namespaces above a threshold (100K memories is a reasonable trigger) are candidates for dedicated Postgres schemas with per-namespace HNSW indexes. A per-namespace HNSW at 100K vectors is tiny — under 1 GB RAM — and gives near-perfect recall without post-filter degradation. Route hot namespaces to their dedicated schema; cold namespaces remain in the shared table.

Write rate spikes

A user who pastes 1,000 conversation turns at once (backfilling history, importing a chat log) can saturate the write pipeline and affect other users' write latency. Rate limiting per namespace at the API layer prevents this. Default: 100 turns/minute per namespace with a burst allowance of 200 turns. For deliberate backfill operations, use the batch import endpoint, which places work in the background worker queue rather than the synchronous write path. The background worker drains at a rate that does not impact real-time write latency for other namespaces.

The write rate spike also affects GIN index maintenance at high aggregate rates. If 100 users simultaneously backfill at 100 turns/minute each, that is 10,000 writes/minute — high enough to stress GIN pending list flushing. Monitor pg_stat_user_tables.n_live_tup and pgstattuple on the GIN index to detect bloat accumulation during sustained high-write periods.

Shard transition planning

Moving from tier 2 (one multi-shard node) to tier 3 (multiple nodes) or tier 4 (a full cluster) requires careful planning because the transition must be zero-downtime. Users cannot experience degraded retrieval quality during migration.

Tier 2 to Tier 3 (adding nodes)

A four-week migration timeline:

Day 1:    Provision node 2 (a new Brain server running its own shards)
Day 2:    Add routing layer (consistent hash by namespace_id)
Day 3–7:  Backfill existing namespaces to their target shard
          (dual-write to both shards during backfill window)
Day 7:    Cut over write path — new namespaces route to target shard
          via hash(namespace_id) % num_shards
Week 2-4: Migrate remaining existing namespaces at background priority
Day 30:   All existing namespaces migrated; remove dual-write path;
          decommission shared table

Routing is by hash(namespace_id) % num_shards. For N=4 shards: namespace_id mod 4 determines the shard. This is stable — a given namespace always routes to the same shard without a coordination table, which keeps the routing layer stateless and fast.

Cross-shard queries are rare in memory systems because nearly all queries are scoped to a single namespace. When cross-shard is required (administrative queries, analytics), fan-out to all shards and merge results at the routing layer. Design APIs to avoid cross-shard patterns in the hot path — they are linearly slower with shard count.

Tier 3 to Tier 4 (scaling the cluster)

Tier 4 is not a switch to a different storage engine — it is more of the same shard, coordinated at fleet scale. A coordinator tracks which node owns each namespace, rebalances shards as nodes are added or removed, and manages replication. Because each shard is self-contained (its own arena, WAL, redb, HNSW, and tantivy), moving a namespace means streaming that shard's state to a new node and cutting over the routing entry — there is no separate vector store to keep in sync.

The failure mode to design for is rebalance-induced tail latency: while a shard is being migrated, its namespace should keep serving from the source node until the destination is caught up and verified, then cut over atomically. Size the rebalance rate so in-flight migrations never starve live traffic on either node.

Cost optimization at scale

Memory infrastructure costs more than expected if you are not paying attention to the right cost drivers. At 100M+ memories, three items dominate the budget.

Embedding API cost

At OpenAI text-embedding-3-small pricing (~$0.02 per 1M tokens), embedding 100M memories at an average of 50 tokens each is 5B tokens, or$100. That is a one-time cost for the initial corpus. The ongoing cost for new memories at 1M new memories per day at 50 tokens each is 50M tokens per day, or $1 per day — essentially free.

The expensive event is model migration: re-embedding 100M memories when switching from text-embedding-3-small to text-embedding-3-large (or any model change) costs another $100 in API fees and approximately one week of background worker time at 3,000 RPM. Model selection decisions are consequential. The shadow strategy described above gives you the tooling to validate before committing; the cost model means you do not want to do this frequently. Plan embedding model selection as a 1–2 year commitment, not a quarterly optimization.

LLM extraction cost

At Claude Haiku pricing, 100M extraction calls (including input context and output JSON) costs approximately $1,000–2,000. This is the largest ongoing operational cost in the memory pipeline — larger than storage, larger than embedding API. The pre-filter gate (the classifier that rejects turns unlikely to contain memorable content) is the primary cost lever: rejecting 55$550–1,100 at 100M memory scale.

HyPE (hypothetical question generation at write time) adds approximately 30% to extraction cost because it generates additional LLM output per memory. It is opt-in and improves retrieval quality on direct question queries. At 100M scale, opting into HyPE adds $300–600 to extraction costs — justified if your workload includes frequent direct question retrieval patterns (e.g., "what is Alice's phone number?"), unjustified for workloads that are primarily conversational context retrieval.

Database storage cost

Brain stores on SSD: the memory-mapped arena holds the vectors, redb holds metadata and the audit ledger, and the WAL holds the durability log. At commodity SSD pricing, 1TB is approximately $100–115/month. At 5.5 KB per memory (text content, metadata, audit fields, and one embedding vector at 1536 dims × 4 bytes = 6,144 bytes), 100M memories consumes approximately 550 GB for vectors alone. Adding text content (average 200 bytes), metadata, and index overhead: approximately 1TB total at 100M memories. Budget$100–200/month for storage at this scale.

Retrieval infrastructure adds little beyond the nodes themselves: Brain's L1–L3 caches are shard-local (in-process) and the HNSW index is built into each shard, so there is no separate cache tier or vector-DB service to pay for. The cost at tier 3/tier 4 is simply the RAM and cores of the nodes.

The consolidation dividend

Aggressive deduplication reduces the effective memory count and therefore every cost that scales with memory count. A system with 10M raw stored memories and a 40% dedup rate (aggressive supersession + entity attribute consolidation) has 6M effective memories in active indexes. Each 10% reduction in effective memory count reduces:

• HNSW RAM footprint by 10%
• Embedding API re-embedding cost by 10%
• BM25 (tantivy) index size by 10%
• Storage cost by 10%

The consolidation dividend compounds: a system that aggressively consolidates from the start avoids the infrastructure scaling work that a system with poor dedup requires. Measure dedup rate monthly. If it is below 20% at 1M memories, the extraction and supersession pipeline has a problem — it is storing too many near-duplicate memories.