Как выполнять запросы по 10 млрд записей быстрее 100 мс?

Question

IT Interview Practice · Accepted Answer

Проектируйте от **паттерна доступа**, затем выбирайте партиционирование + правильный индекс/PK, чтобы любой одиночный запрос касался малого ограниченного среза — никогда не сканировал 10 млрд строк. Sub-100ms по 10 миллиардам записей — это не про более быстрый диск; это про то, чтобы сделать рабочее множество крошечным.

```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
```

## Паттерны доступа определяют всё

Прежде чем выбирать технологию, спросите: **точечный lookup или диапазон/агрегат?** «Получить последние 20 заказов пользователя X» — это точечный/диапазонный запрос: partition key и sort key должны точно ему соответствовать. «Суммировать выручку по регионам за месяц» — это аналитический скан, а row store здесь неправильный инструмент. Моделирование запроса первым — вот что отличает работающий дизайн от того, что выглядит разумно, но делает full scan.

## Партиционирование сокращает пространство поиска

Разбейте таблицу по ключу, который появляется в каждом запросе — обычно **tenant_id + время**. С временными партициями запрос за «последние 7 дней» читает 7 партиций и игнорирует остальные 3 года. Это *partition pruning*: роутер отбрасывает 99.9% данных ещё до обращения к индексу.

## Правильный дизайн индекса / PK

Внутри партиции **первичный ключ должен выносить вперёд колонки фильтрации запроса**. В DynamoDB: partition key = `tenant`, sort key = `timestamp` → диапазонные запросы — это O(log n) + последовательное чтение. В колоночном хранилище вроде **ClickHouse** ключ сортировки (`ORDER BY (tenant, ts)`) позволяет движку пропускать гранулы и читать только подходящие блоки. Покрывающий индекс полностью устраняет лишнее чтение строки.

## Выбор хранилища

- **Точечные lookup, высокая запись:** NoSQL key-value (DynamoDB, Cassandra) — почти O(1) по ключу, масштабируется горизонтально.
- **Аналитика/агрегаты:** колоночные (ClickHouse, BigQuery) — читают только нужные колонки, векторизованно.
- **Кэшируйте горячий 1%:** Redis впереди поглощает повторные чтения за <5 мс; 10 млрд строк, но несколько миллионов горячих ключей.

## Взгляд с точки зрения интервью

Интервьюер хочет услышать **«какие запросы?» до «какая база?»**. Хорошие кандидаты тянутся к индексам; отличные замечают, что индекс на 10 млрд строк сам огромен — поэтому вы *сначала партиционируете, чтобы уменьшить область, которую покрывает индекс*. Назвать разделение row-vs-columnar и слой кэша — сигнал реального опыта масштаба.

**Частая ловушка:** предлагать один гигантский B-tree индекс как ответ. Он помогает точечным lookup, но ничего не даёт аналитическим сканам, а его записи становятся узким местом приёма.

## Компромиссы и режимы отказа

- **Неправильный partition key** = кросс-партиционный scatter-gather, latency раздувается. Выбирайте ключ, присутствующий в запросах.
- **Горячая партиция:** tenant-«знаменитость» перегружает один шард — добавьте salting-суффикс.
- **Устаревание кэша:** инвалидируйте при записи или принимайте отставание по TTL.
- **Стоимость денормализации:** вы часто дублируете данные под каждый паттерн доступа; хранилище дёшево, а 10-секундный запрос — нет.

Паттерны доступа определяют всё

Партиционирование сокращает пространство поиска

Правильный дизайн индекса / PK

Выбор хранилища

Взгляд с точки зрения интервью

Компромиссы и режимы отказа

Похожие вопросы