Hvordan forespørger du 10B records under 100ms?

Question

IT Interview Practice · Accepted Answer

Design for **access pattern først**, vælg derefter partitionering + den rette index/PK, så enhver enkelt forespørgsel rører en lille, afgrænset skive — aldrig scanner 10B rows. Sub-100ms over 10 milliarder records handler ikke om en hurtigere disk; det handler om at gøre working set'et lille.

```text
Query ─▶ Router ──▶ Partition (by tenant/time) ──▶ Index/PK lookup ─▶ ~thousands of rows
   │                    (prune 99.9% of data)         (B-tree / sort key)
   └─▶ Cache (Redis) ─▶ hit? return in <5ms
                        miss ▼
                   Columnar store (ClickHouse) for aggregates / scans
```

## Access patterns styrer alt

Før du vælger teknologi, spørg: **point lookup eller range/aggregate?** "Hent bruger X's sidste 20 ordrer" er en point/range-forespørgsel — du vil have partition- og sort key til at matche den nøjagtigt. "Summér omsætning pr. region denne måned" er en analytisk scan — en row store er det forkerte værktøj. At modellere forespørgslen først er det, der adskiller et design der virker, fra et der ser rimeligt ud men full-scanner.

## Partitionering beskærer søgerummet

Split tabellen efter en nøgle, der optræder i hver forespørgsel — som regel **tenant_id + time**. Med tidspartitioner læser en forespørgsel for "sidste 7 dage" 7 partitioner og ignorerer de andre 3 år. Dette er *partition pruning*: routeren eliminerer 99,9% af data, før noget index konsulteres.

## Rigtig index / PK-design

Inden for en partition **skal primærnøglen front-loade forespørgslens filter-kolonner**. I DynamoDB: partition key = `tenant`, sort key = `timestamp` → range-forespørgsler er O(log n) + sekventiel read. I en columnar store som **ClickHouse** lader sorting key'en (`ORDER BY (tenant, ts)`) engine'en springe granules over og kun læse matchende blokke. Et covering index undgår den ekstra row-fetch helt.

## Store-valg

- **Point lookups, høj write:** NoSQL key-value (DynamoDB, Cassandra) — O(1)-agtig efter nøgle, skalerer horisontalt.
- **Analytics/aggregates:** columnar (ClickHouse, BigQuery) — læser kun nødvendige kolonner, vektoriseret.
- **Cache de hotte 1%:** Redis foran absorberer gentagne reads under 5ms; 10B rows men få millioner hot keys.

## Interview-perspektiv

Intervieweren vil se dig sige **"hvad er forespørgslerne?" før "hvilken database?"**. Gode kandidater griber efter indexes; fremragende bemærker, at et index på 10B rows selv er enormt — så du *partitionerer først for at formindske det, index'et dækker*. At navngive row-vs-columnar-splittet og cache-tier'en signalerer ægte skalaerfaring.

**Almindelig fælde:** at foreslå ét gigantisk B-tree index som svaret. Det hjælper point lookups men gør intet for de analytiske scans, og dets writes flaskehalser ingestion.

## Trade-offs & fejlmåder

- **Forkert partition key** = cross-partition scatter-gather, latency eksploderer. Vælg en nøgle til stede i forespørgsler.
- **Hot partition:** en kendis-tenant overvælder én shard — tilføj et salting-suffiks.
- **Cache-forældelse:** invalidér ved write eller accepter TTL-sakke.
- **Denormaliserings-omkostning:** du duplikerer ofte data pr. access pattern; storage er billigt, en 10-sekunders forespørgsel er ikke.

Access patterns styrer alt

Partitionering beskærer søgerummet

Rigtig index / PK-design

Store-valg

Interview-perspektiv

Trade-offs & fejlmåder

Relaterede spørgsmål