Балансировка нагрузки, прокси и сбалансированные структуры данных

Кратко о теме

Балансировка нагрузки — это распределение входящего потока запросов между несколькими равнозначными обработчиками так, чтобы (а) суммарная пропускная способность росла с числом инстансов, (б) отказ одного инстанса не ронял сервис, (в) latency оставалась предсказуемой. Ключевая предпосылка — взаимозаменяемость бэкендов: если инстансы не идентичны по функциональности или хранят локальное состояние сессии, «балансировка» превращается в шардирование, а это другая задача с другими алгоритмами. Поэтому первый вопрос на дизайне всегда один: сервис stateless или нет. Stateless-сервис можно балансировать чем угодно, stateful требует либо вынесения состояния наружу (Redis, БД), либо sticky-привязки клиента к инстансу, либо консистентного хеширования по ключу данных.

Балансировщики принято классифицировать по уровню модели OSI, на котором принимается решение. L4-балансировка работает с TCP/UDP: балансировщик видит только пятёрку (src ip, src port, dst ip, dst port, proto), выбирает бэкенд один раз на соединение и дальше просто гоняет байты — это дёшево (в пределе — на уровне ядра или сетевой карты: IPVS, eBPF/XDP, Maglev, Katran) и прозрачно для протокола, но не умеет ничего, что требует понимания содержимого. L7-балансировка терминирует HTTP/gRPC/HTTP2 и решает по каждому запросу: видит URL, заголовки, метод, может ретраить, переписывать, дробить трафик по канареечным правилам, но платит за это CPU на парсинг и TLS. Ниже L4 есть ещё сетевой уровень — anycast + BGP и DNS-балансировка, они распределяют трафик между дата-центрами и точками присутствия, а не между процессами.

Отдельная ось — где живёт решение. Классическая схема серверная (proxy-based): между клиентом и бэкендами стоит nginx/HAProxy/Envoy/облачный ALB, все знают только его адрес. Клиентская балансировка (client-side) переносит выбор бэкенда в саму клиентскую библиотеку: клиент через service discovery получает полный список адресов и сам решает, куда слать — так работают gRPC, Finagle, Ribbon. Промежуточный вариант — sidecar/service mesh (Envoy рядом с приложением): для приложения это выглядит как обычный localhost-прокси, а по факту это клиентская балансировка с вынесенной в отдельный процесс логикой.

Про алгоритмы важно понимать, что они делятся на три семейства с принципиально разной семантикой. Слепые (round-robin, weighted RR, random) не смотрят на состояние бэкендов, дёшевы и хороши при однородных быстрых запросах. Адаптивные (least connections, least time / peak-EWMA, power of two choices) смотрят на текущую загрузку и выигрывают при разбросе времени обработки — именно они защищают от «медленного» инстанса, который слепой RR продолжит тупо заваливать запросами. Детерминированные (hash по IP/URL/ключу, consistent hashing, rendezvous) нужны, когда важно, чтобы один и тот же ключ стабильно попадал на один и тот же бэкенд — кеш-локальность, sticky-сессии, шардирование.

Небольшая, но регулярная путаница на собеседованиях: русское слово «балансировка» одновременно означает и load balancing, и сбалансированность деревьев (AVL, красно-чёрное, B-tree). Часть вопросов в этой подтеме именно про структуры данных и индексы БД — там «сбалансированность» значит «высота дерева ограничена O(log n), все листья примерно на одной глубине», и никакого отношения к сетевому трафику это не имеет.

Вопросы и ответы

Балансировка нагрузки?

Коротко. Балансировка нагрузки — распределение запросов между несколькими одинаковыми инстансами сервиса ради горизонтального масштабирования, отказоустойчивости и равномерной утилизации. Реализуется прокси-балансировщиком (L4 или L7), клиентской библиотекой или на уровне DNS/anycast; конкретный бэкенд выбирается алгоритмом — от round-robin до consistent hashing.

Глубже. Балансировщик почти всегда несёт два дополнительных обязательства помимо выбора бэкенда. Первое — health checks: активные (сам периодически дёргает /healthz) и пассивные (outlier detection — вывел бэкенд из ротации, потому что он начал отдавать 5xx или таймауты). Без health checks балансировка не даёт отказоустойчивости, она просто равномерно шлёт часть трафика в мёртвый инстанс. Второе — сам балансировщик становится единой точкой отказа, поэтому его дублируют: пара нод с общим VIP через VRRP/keepalived, либо ECMP/anycast на маршрутизаторе, либо managed-сервис облака. Практически полезно помнить, что балансировка не создаёт мощность из воздуха: если узкое место — общая БД, добавление инстансов приложения только ускорит её деградацию.

Алгоритмы балансировки?

Коротко. Основные: round-robin и weighted round-robin, random (и его сильная версия — power of two choices), least connections / weighted least connections, least response time (peak EWMA), hash по ключу (source IP, URL, заголовок) и consistent hashing / rendezvous hashing. Выбор диктуется однородностью запросов и нужна ли привязка клиента к бэкенду.

Глубже. Round-robin оптимален только при примерно равной стоимости запросов и равных бэкендах — иначе один тяжёлый эндпоинт «залипает» на конкретной ноде. Least connections адаптивен: перегруженный или подтормаживающий инстанс естественным образом накапливает открытые соединения и перестаёт получать новые; это дефолт по умолчанию хорош для длинных и разнородных запросов. Power of two choices (P2C) — практически лучший компромисс в распределённых системах: выбираем два случайных бэкенда и отдаём запрос менее загруженному; это даёт почти качество least-connections без глобального состояния и без «стадного эффекта», когда все балансировщики одновременно выбирают один и тот же «самый свободный» инстанс. Хеш-алгоритмы (ip_hash, hash $request_uri consistent в nginx; source, uri в HAProxy) нужны для кеш-локальности и sticky; обычный модульный хеш при изменении числа бэкендов переразбрасывает почти все ключи, поэтому для кешей берут consistent hashing (кольцо с виртуальными нодами) или rendezvous/HRW — там переезжает лишь доля 1/N ключей. Отдельно стоит упомянуть, что EWMA-варианты (Envoy, linkerd2-proxy) учитывают не число соединений, а сглаженную latency, что лучше ловит «медленного соседа».

Клиентская балансировка?

Коротко. Клиентская балансировка — когда список адресов бэкендов известен самому клиенту (через service discovery), и клиентская библиотека сама выбирает, куда отправить каждый запрос. Плюсы: минус один сетевой хоп и минус одна точка отказа, полный контроль над политикой; минусы: логика дублируется в каждом клиенте и на каждом языке, а обновление политики требует релиза клиентов.

Глубже. Канонический пример — gRPC: resolver (например, dns:///users.svc:8080) отдаёт список адресов, balancer держит по подсоединению к каждому и на каждый RPC выбирает готовое. Это принципиально важно именно для gRPC, потому что он ходит по HTTP/2 с мультиплексированием: одно долгоживущее TCP-соединение несёт все RPC, поэтому L4-балансировка «размажет» соединения, но не запросы, и нагрузка окажется неравномерной. Включается политика через service config:

import (
    "log"

    "google.golang.org/grpc"
    "google.golang.org/grpc/credentials/insecure"
    _ "google.golang.org/grpc/balancer/roundrobin" // регистрирует политику round_robin
)

conn, err := grpc.NewClient(
    "dns:///users.default.svc.cluster.local:8080",
    grpc.WithTransportCredentials(insecure.NewCredentials()),
    grpc.WithDefaultServiceConfig(`{"loadBalancingConfig":[{"round_robin":{}}]}`),
)
if err != nil {
    log.Fatal(err)
}
defer conn.Close()

По умолчанию grpc-go использует pick_first (одно соединение с первым доступным адресом) — это как раз то, что нужно явно менять на round_robin, иначе весь трафик уедет в один инстанс. Нюанс DNS-резолвера: он перечитывает записи не мгновенно (в grpc-go есть минимальный интервал ресолвинга), поэтому при частом пересоздании подов нужен либо более быстрый discovery (xDS, Consul, etcd), либо серверный MAX_CONNECTION_AGE, чтобы соединения периодически переустанавливались и перераспределялись. Промежуточная форма — sidecar-прокси (Envoy в service mesh): политику балансировки задаёт control plane через xDS, а приложение просто ходит в localhost.

Есть три юзер-сервиса. Перед ними стоит прокси. Как распределить нагрузку на эти три сервиса?

Коротко. Если сервисы идентичны и stateless — round-robin (или least_conn при разнородных по времени запросах) с активными health-check’ами, чтобы упавший инстанс выбывал из ротации. Если инстансы разной мощности — weighted round-robin с весами пропорционально ресурсам. Если нужна кеш-локальность или sticky-сессия — consistent hash по user_id/сессионному ключу.

Глубже. На собеседовании тут ждут не столько название алгоритма, сколько последовательность рассуждений: (1) stateless ли сервис — если сессия хранится в памяти инстанса, надо либо вынести её в Redis, либо делать sticky, и тогда при падении инстанса часть пользователей разлогинится; (2) какие health-check’и и какой outlier detection — иначе отказ третьего инстанса означает, что треть запросов падает; (3) какой протокол — для HTTP/1.1 достаточно L4 или nginx, для gRPC/HTTP2 нужен L7-прокси (или клиентская балансировка), иначе одно соединение = один бэкенд; (4) ретраи и таймауты — ретрай на другой бэкенд спасает от единичных сбоев, но без бюджета ретраев легко устроить лавину; (5) сам прокси не должен быть SPOF. Минимальный конфиг nginx выглядит так:

upstream users {
    least_conn;
    server 10.0.0.11:8080 max_fails=3 fail_timeout=10s;
    server 10.0.0.12:8080 max_fails=3 fail_timeout=10s;
    server 10.0.0.13:8080 max_fails=3 fail_timeout=10s;
    keepalive 64;
}
server {
    location / {
        proxy_pass http://users;
        proxy_http_version 1.1;
        proxy_set_header Connection "";
        proxy_next_upstream error timeout http_502 http_503;
    }
}

keepalive + proxy_http_version 1.1 тут не косметика: без них nginx открывает новое TCP-соединение к бэкенду на каждый запрос.

Когда разумнее использовать сбалансированное дерево, а когда - хэш? Чем вы будете руководствоваться при решении задачи из нескольких матриц?

Коротко. Хеш-таблица — когда нужен только доступ по точному ключу: O(1) в среднем, но порядок ключей теряется. Сбалансированное дерево — когда нужны упорядоченные операции: диапазонные запросы, поиск ближайшего/следующего, обход по порядку, min/max; цена — O(log n) на операцию и худшая константа из-за переходов по указателям. Вторая часть вопроса («задача из нескольких матриц») — обрывок исходника, вопрос не восстанавливается.

Глубже. Практический чек-лист выбора. Хеш: равенство по ключу, отсутствие требований к порядку, известен приличный размер (можно преаллоцировать), ключ хешируется дёшево. Дерево: WHERE created_at BETWEEN ..., ORDER BY, префиксный поиск, персистентность на диске (тогда B-tree/B+tree, а не бинарное — см. ниже), а также предсказуемая worst-case сложность — у хеша при плохом распределении или адверсарных ключах деградация до O(n), у сбалансированного дерева гарантированно O(log n). В Go это разница между map[K]V (открытая адресация на Swiss Tables начиная с Go 1.24; итерация в случайном порядке — намеренно) и отсортированным слайсом с sort.Search / внешней реализацией дерева: стандартной библиотеки сбалансированных деревьев в Go нет, что само по себе часто и подразумевает ответ «в Go по умолчанию берём map, а порядок делаем сортировкой ключей». В БД та же дихотомия: hash-индекс поддерживает только =, B-tree — =, <, >, BETWEEN, ORDER BY и префиксы LIKE 'abc%'.

Какие есть виды балансировки?

Коротко. По уровню — DNS/глобальная, сетевая (anycast/BGP, ECMP), транспортная L4 и прикладная L7. По месту принятия решения — серверная (прокси), клиентская (в библиотеке клиента) и sidecar/mesh. По направлению — внешняя (ingress, трафик из интернета) и внутренняя (east-west, между микросервисами).

Глубже. Уровни не альтернативны, а складываются в стек: DNS/GSLB разводит пользователей по регионам, anycast — по ближайшим точкам присутствия, L4 внутри ДЦ раскидывает соединения по пулу L7-прокси, а L7-прокси уже по конкретным подам. Ещё одно полезное деление — по способу возврата ответа: proxy mode (ответ идёт обратно через балансировщик — просто, но балансировщик пропускает через себя весь исходящий трафик), NAT mode и DSR/Direct Server Return (бэкенд отвечает клиенту напрямую, минуя балансировщик — так работают L4-решения вроде Maglev и Katran, что критично при отдаче тяжёлого контента, где исходящий трафик в разы больше входящего). Отдельно упоминают active-active (все инстансы обслуживают трафик) и active-passive (резерв включается при отказе, типично для самих балансировщиков через VRRP/keepalived).

Какие есть алгоритмы балансировки?

Коротко. См. выше «Алгоритмы балансировки?» — набор тот же: RR/WRR, random и P2C, least connections, least response time (EWMA), хеш-алгоритмы и consistent hashing. Отличие формулировки лишь в том, что здесь уместно назвать конкретные реализации в популярных балансировщиках.

Глубже. В nginx это round-robin (по умолчанию), least_conn, ip_hash, hash <key> [consistent], random two [least_conn]; в коммерческом nginx plus дополнительно least_time. В HAProxy: roundrobin, static-rr, leastconn, first, source, uri, url_param, hdr(<name>), random. В Envoy: ROUND_ROBIN, LEAST_REQUEST (реализован как P2C), RANDOM, RING_HASH, MAGLEV. В grpc-go — pick_first, round_robin и политики, приходящие через xDS. Полезно помнить, что «least connections» в мульти-прокси-развёртывании считается локально по каждому прокси, поэтому глобально оптимальным он не является — это ещё один аргумент в пользу P2C.

Какие уровни балансировки знаешь?

Коротко. L7 (прикладной: HTTP/gRPC — решение по каждому запросу, видит URL/заголовки, умеет ретраи и канарейки), L4 (транспортный: TCP/UDP — решение один раз на соединение, дёшево и быстро), L3/сетевой (anycast + BGP, ECMP — распределение между площадками) и DNS (несколько A/AAAA-записей, GSLB, geo-DNS — распределение между дата-центрами).

Глубже. Практические различия. L4 не терминирует TLS, значит не видит SNI-содержимое запроса и не может ретраить на прикладном уровне, зато держит миллионы соединений на скромном железе и поддерживает DSR. L7 умеет всё, что требует понимания протокола: маршрутизацию по пути, работу с HTTP/2 и gRPC на уровне отдельных стримов, sticky по cookie, circuit breaking, rate limiting, mTLS. DNS-балансировка самая дешёвая и единственная, работающая до установки соединения, но у неё нет health-check’ов в базовом виде и она заложница TTL и кеширования у резолверов и клиентов — снять мёртвый адрес из ротации мгновенно не получится, поэтому её используют для грубого разведения по регионам, а не для отказоустойчивости внутри ДЦ. Anycast решает проблему «до какого ДЦ доехать» на уровне маршрутизации, но перестроение BGP рвёт TCP-соединения, поэтому его любят для UDP/QUIC и коротких HTTP-запросов.

Может ли клиент балансировать нагрузку?

Коротко. Да — это и есть client-side load balancing: клиент получает список адресов бэкендов из service discovery и сам выбирает получателя. Так работает gRPC по умолчанию в кластерных сценариях, а также Finagle, Ribbon и любой код, читающий DNS SRV/Consul/etcd и делающий выбор сам.

Глубже. См. выше подробнее в вопросе «Клиентская балансировка?». Что важно добавить именно к формулировке «может ли»: клиент балансирует и в вырожденном виде тоже — например, когда DNS отдаёт несколько A-записей, а библиотека/ОС выбирает одну из них (обычно первую, что и делает «round robin DNS» бесполезным без явной поддержки в клиенте). Ограничения клиентской балансировки: клиент должен доверять списку адресов (в публичном интернете это неприемлемо — там только прокси), должен уметь health-check и outlier detection сам, и его нельзя быстро перенастроить централизованно, если только не используется xDS/mesh. Поэтому типичное деление: north-south (внешний) трафик — серверная балансировка, east-west (внутренний) — клиентская или sidecar.

Чем сбалансированное дерево лучше бинарного?

Коротко. «Сбалансированное дерево» — это и есть бинарное дерево поиска, но с инвариантом на высоту. Обычное несбалансированное BST при вставке уже отсортированных данных вырождается в связанный список с O(n) на операцию; сбалансированное (AVL, красно-чёрное, B-дерево) поддерживает высоту O(log n) поворотами/перестроениями и потому гарантирует O(log n) в худшем случае.

Глубже. Разница именно в worst case, а не в среднем: у случайно построенного BST ожидаемая высота ~1.39·log₂n, то есть «в среднем» он неплох — проблема в том, что реальные данные редко случайны (автоинкрементные id, отсортированные импорты, временные метки — все дают вырожденное дерево). AVL держит разницу высот поддеревьев ≤ 1: поиск быстрее, но перебалансировок при вставке/удалении больше. Красно-чёрное дерево слабее ограничивает высоту (не более 2·log₂(n+1)), зато делает меньше поворотов — поэтому его берут для изменяемых структур (например, std::map в C++, планировщик CFS в Linux исторически). B-дерево — не бинарное: у него высокий фанаут (сотни ключей в узле), что минимизирует число обращений к диску; именно поэтому индексы в БД — B/B+-деревья, а не AVL. Цена балансировки — дополнительные записи при модификации и метаданные в узле (цвет/фактор баланса), что для read-mostly-нагрузки почти всегда окупается.

Что такое reverse proxy, для чего используется и как работает?

Коротко. Reverse proxy — прокси, стоящий на стороне сервера: клиент обращается к нему как к «самому сервису», а он от своего имени проксирует запрос на один из бэкендов и возвращает ответ. В отличие от forward proxy (который представляет клиента и настраивается у клиента), reverse proxy прозрачен для клиента и служит единой точкой входа: балансировка, TLS-терминация, кеширование, сжатие, rate limiting, WAF, маршрутизация по путям.

Глубже. Механика: reverse proxy принимает TCP-соединение и HTTP-запрос, по конфигурации (host, path, заголовки) выбирает upstream-пул, применяет алгоритм балансировки, открывает или переиспользует keep-alive соединение к бэкенду, проксирует запрос и стримит ответ обратно. По пути он обычно добавляет X-Forwarded-For/X-Forwarded-Proto/X-Real-IP (или RFC 7239 Forwarded), поэтому приложение за прокси должно брать IP клиента оттуда, а не из адреса соединения — и доверять этим заголовкам только от собственного прокси. Типичные представители: nginx, HAProxy, Envoy, Traefik, Caddy; в облаках — ALB/Application Gateway. В Go reverse proxy пишется в несколько строк на стандартной библиотеке:

package main

import (
    "log"
    "net/http"
    "net/http/httputil"
    "net/url"
)

func main() {
    target, _ := url.Parse("http://10.0.0.11:8080")
    proxy := httputil.NewSingleHostReverseProxy(target)
    log.Fatal(http.ListenAndServe(":80", proxy))
}

Для собственной балансировки используют httputil.ReverseProxy с кастомным Rewrite (или устаревшим Director), выбирающим цель из пула, и ErrorHandler для обработки недоступного бэкенда. Отдельно стоит понимать разницу между reverse proxy и API Gateway: второй — это тот же reverse proxy плюс прикладные функции (аутентификация, агрегация вызовов, квоты, версионирование API).

Какого типа балансировка у индекса b-tree?

Коротко. У B-дерева балансировка структурная и «по высоте»: все листья находятся строго на одной глубине, а каждый узел (кроме корня) заполнен не менее чем наполовину — от ⌈m/2⌉−1 до m−1 ключей при порядке m. Достигается это не поворотами, как в AVL/RB-деревьях, а расщеплением переполненного узла (split) при вставке и слиянием/перераспределением (merge/redistribute) при удалении; дерево растёт и убывает только через корень.

Глубже. В БД используется вариант B+-дерева: все реальные данные (в PostgreSQL — TID-ссылки на кортежи) лежат в листьях, внутренние узлы содержат только разделяющие ключи, а листья связаны в двусвязный список — это то, что делает диапазонные сканы и ORDER BY дешёвыми. Балансировка тут преследует не «красоту», а конкретную цель: гарантировать, что путь от корня до любого листа — одинаковое и малое число чтений страниц. При странице 8 КБ в PostgreSQL и фанауте в сотни ключей дерево на десятки миллионов строк имеет высоту 3–4, то есть поиск — 3–4 обращения к страницам, из которых верхние почти всегда в кеше. Реализация в PostgreSQL — вариант Lehman & Yao с right-links, позволяющий конкурентный доступ без блокировки всего пути. Практическое следствие «заполненности не менее половины»: при монотонно возрастающем ключе (bigserial, timestamp) вставки идут всегда в правый край, PostgreSQL применяет оптимизацию rightmost-page split (заполняя страницы почти целиком, а не 50/50), а вот массовые удаления старых значений оставляют разреженные страницы — отсюда bloat индекса и польза от REINDEX CONCURRENTLY.

Если мы записываем историю действий пользователя, и я хочу агрегировать балансировку отправки событий на кафку. Каким образом мне лучше организовать балансировку отправки событий на кафку?

Коротко. Ключ партиционирования — user_id, партиционер — хеш по ключу. Это даёт две нужные вещи сразу: гарантированный порядок событий в пределах одного пользователя (Kafka гарантирует порядок только внутри партиции) и равномерное распределение по партициям, потому что пользователей много. Число партиций выбирается по целевому параллелизму консьюмеров, а батчинг (linger.ms + batch.size) даёт «агрегацию» отправки.

Глубже. Разбор альтернатив. Round-robin/random по партициям (пустой ключ) даёт идеальную равномерность, но полностью теряет порядок действий пользователя — для истории действий это обычно неприемлемо. Ключ user_id — стандартный выбор; риск — «горячий» пользователь (бот, интеграция), который перекашивает одну партицию; лечится составным ключом user_id + bucket там, где строгий порядок не нужен, или отдельным топиком для тяжёлых источников. Важный подвох: при увеличении числа партиций хеш hash(key) % numPartitions переразбрасывает ключи, и порядок «старые события в партиции A, новые в партиции B» ломается — поэтому число партиций закладывают с запасом и стараются не менять.

Про «агрегацию отправки»: продюсер и так батчит — записи копятся в аккумуляторе по партициям и уходят одним запросом; linger.ms > 0 увеличивает батч и throughput ценой latency, compression.type=lz4/zstd резко снижает трафик на однотипных JSON-событиях. Обязательно включать acks=all + enable.idempotence=true (идемпотентный продюсер, защита от дублей при ретраях). Если событие должно быть согласовано с записью в БД — не отправлять напрямую из обработчика, а использовать transactional outbox: событие пишется в таблицу той же транзакцией, а релей (poller с FOR UPDATE SKIP LOCKED или CDC через Debezium) публикует его в Kafka.

В Go выбор балансировщика зависит от библиотеки. В segmentio/kafka-go это поле Balancer у Writer:

import (
    "time"

    "github.com/segmentio/kafka-go"
)

w := &kafka.Writer{
    Addr:     kafka.TCP("kafka:9092"),
    Topic:    "user.activity",
    Balancer: &kafka.Hash{}, // партиция = hash(Key) % len(partitions)
    BatchSize:    1000,
    BatchTimeout: 50 * time.Millisecond,
    Compression:  kafka.Lz4,
    RequiredAcks: kafka.RequireAll,
}
err := w.WriteMessages(ctx, kafka.Message{
    Key:   []byte(userID),
    Value: payload,
})

Если топик читают ещё и Java-консьюмеры/пишут Java-продюсеры и важна одинаковая раскладка по партициям, берут &kafka.Murmur2Balancer{} (совместим с дефолтным партиционером Java-клиента) или &kafka.CRC32Balancer{} (совместим с librdkafka). В twmb/franz-go по умолчанию используется sticky-партиционер по ключу, в confluent-kafka-go — партиционер librdkafka.

Что такое индексы в базах данных? Какие типы индексов существуют и их особенности? Что такое B-Tree и в чем заключается его сбалансированность? Для каких операций какой тип индекса лучше применять?

Коротко. Индекс — вспомогательная структура данных, позволяющая находить строки по значению столбцов без полного сканирования таблицы, ценой места на диске и замедления записи. Основные типы в PostgreSQL: B-tree (универсальный, по умолчанию), Hash (только =), GiST и SP-GiST (геометрия, диапазоны, полнотекст, kNN), GIN (массивы, jsonb, полнотекстовый поиск), BRIN (огромные таблицы с естественной корреляцией по физическому порядку). B-tree сбалансировано в том смысле, что все листья лежат на одинаковой глубине, а узлы заполнены минимум наполовину — это гарантирует одинаковое и малое число чтений страниц для любого ключа.

Глубже. По назначению индексы делят иначе: кластерный (определяет физический порядок строк; в InnoDB это первичный ключ, и все вторичные индексы ссылаются на него — отсюда двойной поиск и требование к короткому PK) и некластерный (в PostgreSQL все индексы такие, они хранят TID-указатели на кортежи в heap). Также: уникальные, составные (важен порядок столбцов — работает «левый префикс»), частичные (WHERE deleted_at IS NULL), покрывающие (INCLUDE (...), дают index-only scan), функциональные (ON t (lower(email))).

Что чем закрывать:

• B-tree: =, <, >, BETWEEN, IN, ORDER BY, LIKE 'prefix%', MIN/MAX, уникальность. В 95 % случаев это правильный ответ.
• Hash: только =; чуть компактнее и быстрее B-tree на точном равенстве длинных ключей, но не поддерживает сортировку, диапазоны и уникальные ограничения. В PostgreSQL стал WAL-логируемым и потому production-ready только с версии 10.
• GIN: «много значений в одном поле» — jsonb @>, tsvector @@, массивы @>/&&, триграммы pg_trgm для LIKE '%substr%'. Быстрый поиск, дорогая запись (частично лечится fastupdate).
• GiST/SP-GiST: пересечения диапазонов и геометрии (PostGIS, tsrange &&), поиск ближайших соседей (ORDER BY point <-> ...).
• BRIN: таблицы на сотни миллионов строк, где значение коррелирует с физическим порядком (логи по времени). Индекс крошечный (хранит min/max по зонам страниц), но и селективность грубая.

Про сбалансированность B-tree подробнее — см. ответ на «Какого типа балансировка у индекса b-tree?». Ключевая мысль для собеседования: балансировка нужна ради предсказуемого числа дисковых чтений, а высокий фанаут (сотни ключей на 8-килобайтную страницу) держит высоту дерева на уровне 3–4 даже для десятков миллионов строк. И обязательно упомянуть цену: каждый индекс — это дополнительная запись при каждом INSERT/UPDATE, дополнительное место и работа для VACUUM, поэтому неиспользуемые индексы (pg_stat_user_indexes.idx_scan = 0) надо удалять.

Есть сервис, который запущен на 1 ноде (1 сервере). Как бы ты его скэйлил? Считай что кубера нет ) Добавить второй сервер + балансировщик апи/днс

Коротко. Сначала вертикально (дешевле всего) и профилированием — убедиться, что упёрлись именно в CPU/RAM приложения, а не в БД или диск. Затем сделать приложение stateless (сессии и файлы — наружу, в Redis/S3), поднять второй сервер с тем же артефактом и поставить перед ними балансировщик (nginx/HAProxy), а сам балансировщик задублировать парой нод с общим VIP через keepalived/VRRP. DNS при этом указывает на VIP, а не на конкретные бэкенды.

Глубже. Порядок шагов, который ждут на систем-дизайне:

1. Измерить: где узкое место — приложение, БД, диск, сеть. Масштабировать приложение при упёртой БД бессмысленно.
2. Вертикальное масштабирование как первый шаг — оно не требует изменений архитектуры и часто выигрывает месяцы.
3. Убрать локальное состояние: сессии в Redis или stateless JWT, загруженные файлы в объектное хранилище, локальные крон-задачи — в одну выделенную роль или под распределённый лок, чтобы не выполнялись дважды.
4. Балансировщик: nginx/HAProxy с health-check’ами, least_conn или round-robin, proxy_next_upstream для ретраев. Для деплоя без даунтайма — вывод ноды из ротации (drain) перед рестартом и graceful shutdown в приложении (http.Server.Shutdown).
5. HA самого балансировщика: два узла, keepalived + VRRP, плавающий IP. Альтернатива без VIP — DNS round-robin на два балансировщика, но с оговоркой про TTL и отсутствие health-check’ов.
6. DNS: одна A-запись на VIP; несколько A-записей — это грубая балансировка «на будущее» и способ пережить отказ целого ДЦ, но переключение занимает время TTL, поэтому для быстрого failover TTL держат низким (30–60 с) и всё равно не полагаются на него как на основной механизм.
7. Затем — БД: сначала read-реплики и вынос тяжёлого чтения, потом кеш (Redis), и только потом шардирование. Плюс stateless-обвязка: централизованные логи и метрики, потому что «зайти на сервер и посмотреть лог» перестаёт работать с двух нод.

Отдельно стоит проговорить, что после появления второй ноды часть вещей ломается неочевидно: in-memory кеши расходятся, rate limiter «на инстанс» начинает пропускать вдвое больше, счётчики в памяти становятся неверными, а фоновые джобы дублируются. Это хороший показатель зрелости ответа.

Что такое балансировка?

Коротко. См. выше «Балансировка нагрузки?» — распределение запросов между несколькими равнозначными обработчиками ради масштабирования, отказоустойчивости и равномерной утилизации ресурсов.

Глубже. Единственное, что стоит добавить к общему ответу: если вопрос задан без уточнения, полезно самому развести два значения термина. В сетевом контексте «балансировка» — load balancing; в контексте структур данных и БД «сбалансированность» — свойство дерева (AVL, красно-чёрное, B-tree) держать высоту O(log n) и все листья на одном уровне. Уточняющий встречный вопрос «вы про балансировку нагрузки или про сбалансированные деревья?» здесь абсолютно уместен и обычно воспринимается положительно.

Частые ошибки на собесе

• Считать, что балансировщик сам по себе даёт отказоустойчивость. Без health-check’ов и outlier detection он просто равномерно шлёт часть трафика в мёртвый инстанс, а сам без резервирования (VRRP/anycast) остаётся единственной точкой отказа.
• Балансировать gRPC/HTTP2 на L4. Одно мультиплексированное соединение целиком уезжает на один бэкенд, и после нескольких коннектов нагрузка оказывается перекошенной. Нужен L7-прокси, клиентская балансировка или хотя бы MAX_CONNECTION_AGE на сервере.
• Называть round-robin универсальным ответом. При разбросе времени обработки запросов он гарантированно заваливает «медленный» инстанс; least_conn, least_time или P2C здесь принципиально лучше.
• Путать обычный модульный хеш и consistent hashing. hash(key) % N при добавлении бэкенда переразбрасывает почти все ключи и обнуляет кеши; consistent hashing/rendezvous переносят только ~1/N.
• Считать DNS-балансировку полноценным механизмом failover. TTL и агрессивное кеширование у резолверов и клиентов означают, что удалить упавший адрес из ротации мгновенно не выйдет.
• Говорить «B-tree — это бинарное дерево». B-дерево не бинарное: у него сотни ключей в узле, и весь смысл именно в высоком фанауте ради минимума дисковых чтений.
• Утверждать, что hash-индекс всегда быстрее B-tree. Он поддерживает только =, не даёт сортировки, диапазонов и уникальных ограничений, и на практике выигрыш у B-tree небольшой.
• Отправлять события в Kafka без ключа, когда нужен порядок. Порядок гарантируется только внутри партиции, и без ключа события одного пользователя разъезжаются по разным партициям.
• Забывать, что после второй ноды ломаются in-memory кеши, rate limiter «на инстанс», локальные счётчики и дублируются фоновые джобы.

Что почитать

• nginx, модуль ngx_http_upstream_module — все поддерживаемые методы балансировки: https://nginx.org/ru/docs/http/ngx_http_upstream_module.html
• gRPC Load Balancing (официальный блог и grpc/grpc design doc) — pick_first, round_robin, look-aside и client-side LB: https://grpc.io/blog/grpc-load-balancing/
• Envoy: Load Balancing — обзор алгоритмов, P2C, outlier detection, panic threshold: https://www.envoyproxy.io/docs/envoy/latest/intro/arch_overview/upstream/load_balancing/overview
• PostgreSQL Documentation: Index Types и Chapter 67 «B-Tree Indexes» (реализация Lehman & Yao): https://www.postgresql.org/docs/current/indexes-types.html и https://www.postgresql.org/docs/current/btree.html
• Maglev: A Fast and Reliable Software Network Load Balancer (Google, NSDI 2016) — L4-балансировка с consistent hashing и DSR: https://research.google/pubs/pub44824/
• «The Power of Two Choices in Randomized Load Balancing» (Mitzenmacher) — теоретическое обоснование P2C