Инфраструктура и распределённое обслуживание

[kirill_ir]

Часть IV · ~12 ч · Сложность: (продвинутый) · Пререквизиты: Модуль 4, Модуль 12

Обзор модуля

К этому моменту в сквозном конвейере «обход → индекс → факторы → ранжирование → выдача → постобработка → измерение» мы уже умеем строить обратный индекс и раскладывать его по сегментам, ярусам и шардам (Модуль 4), а также оценивать кандидатов каскадом ранжирования L0–L3 за бюджет латентности (Модуль 12). Но один важный вопрос мы до сих пор обходили: корпус не помещается на одну машину, а одна машина не отвечает за приемлемое время и не работает вечно. Этот модуль — про то, как из тысяч ненадёжных машин собрать поисковую систему, которая отвечает за сотни миллисекунд, переживает отказы отдельных узлов и обновляет индекс без остановки обслуживания.

Инфраструктура — это онлайн-сторона шва между офлайн и онлайн, но взятая не на уровне одной реплики (как в Модуле 12), а на уровне всего флота. Здесь мы перестаём говорить «индекс» в единственном числе и начинаем говорить про шарды (горизонтальные куски корпуса) и реплики (копии шарда ради пропускной способности и надёжности). Запрос больше не «исполняется» — он разветвляется (fan-out) на десятки и сотни узлов, ответы которых нужно собрать, слить и вернуть, причём в условиях, когда часть узлов медленная или мёртвая. Центральная величина всего модуля — не средняя латентность, а хвостовая латентность (tail latency), то есть p99/p999: именно она определяет, что почувствует пользователь, и именно она взрывается при разветвлении.

Ещё одна сквозная тема — жизненный цикл индекса в проде: индекс не статичен, его пересобирают и подменяют, и эта подмена должна быть консистентной, горячей (без простоя) и обратимой (с возможностью отката). Мы свяжем это с реалтайм-контуром из Модуля 4 и покажем, как версии индекса, реплей и атомарное переключение позволяют менять то, по чему ищут миллионы запросов в секунду, не уронив выдачу.

После модуля вы будете понимать, как шардировать и реплицировать индекс и маршрутизировать по нему запросы; почему p99 агрегата хуже p99 одного узла и как с этим борются hedged-запросы; как проектировать грациозную деградацию и частичные ответы под жёсткий дедлайн; и как выкатывать новую версию индекса горячо, консистентно и с возможностью отката.

Как читать по трекам

• Студент CS. Главы 13.1 и 13.2 — обязательно и подробно: это фундамент распределённых систем (партиционирование, репликация, scatter-gather, математика хвоста). Глава 13.3 — обязательно концептуально (дедлайны, деградация). Глава 13.4 — обзорно (версионирование как частный случай атомарной подмены). Лабу по симуляции хвоста (13.2) сделайте обязательно — она переворачивает интуицию про среднее.
• Инженер поиска/ML. Весь модуль — ваш «домашний» материал. Особое внимание: инженерные заметки про балансировку и горячие шарды (13.1), бюджет hedged-запросов и взаимоблокировки хвоста (13.2), дедлайн-бюджеты и идемпотентность ретраев (13.3), консистентность версий и реплей (13.4). Лабы делайте с реальными распределениями латентности.
• SEO-специалист. Обзорно весь модуль, но обязательно SEO-врезки: почему один и тот же запрос может давать слегка разную выдачу (реплики/версии расходятся), почему «новое» появляется не мгновенно (горячая подмена и лаг репликации) и почему частичный ответ под нагрузкой может «потерять» ваш документ. Математику хвоста — по диагонали.
• Смешанный/руководитель. Прочитайте Обзор, конспект 13.2 (про хвост и p99 — это главный бизнес-риск надёжности) и 13.3 (деградация вместо отказа). Это объясняет, почему «добавить ещё реплик» не всегда ускоряет, а иногда замедляет, и почему SLO формулируют в перцентилях, а не в среднем.

Карта модуля

• 13.1. Шардирование и репликация индекса; маршрутизация запросов. (продвинутый)
• 13.2. Scatter-gather и проблема хвостовых латентностей (tail latency), hedged requests. (продвинутый)
• 13.3. Отказоустойчивость, грациозная деградация, таймауты, частичные ответы. (продвинутый)
• 13.4. Обновление индекса: версии, консистентность, горячая подмена, реплей. (продвинутый)

Глава 13.1. Шардирование и репликация индекса; маршрутизация запросов (продвинутый)

Цели обучения

После главы студент сможет:

• объяснить разницу между шардированием (sharding/partitioning) и репликацией (replication) и зачем нужны обе оси;
• сравнить документное (document-partitioning) и термовое (term-partitioning) шардирование и обосновать, почему в вебе побеждает документное;
• спроектировать схему распределения docID → shard (хеш, диапазон, по ярусам) и объяснить компромисс «равномерность ↔ перемещение при ребалансе»;
• описать роль корня (root/broker) и листьев (leaf) в дереве обслуживания и роль балансировщика реплик;
• оценить требуемое число шардов и реплик под заданный объём корпуса, QPS и бюджет латентности.

Конспект

Две независимые оси: шард и реплика

Корпус слишком велик для одной машины, а поток запросов (QPS, queries per second) слишком велик для одной копии. Это две разные проблемы, и решаются они двумя ортогональными осями.

• Шардирование (горизонтальное партиционирование): корпус режут на S непересекающихся кусков-шардов, каждый шард держит свою долю документов. Решает проблему объёма и латентности одного запроса (каждый шард обрабатывает меньше данных параллельно).
• Репликация: каждый шард копируют в R экземпляров-реплик с идентичным содержимым. Решает проблему пропускной способности (QPS делится между репликами) и надёжности (смерть одной реплики не теряет данные шарда).

Интуиция. Представьте библиотеку. Шардирование — это «разнести книги по S залам, чтобы один зал можно было обойти быстро». Репликация — это «сделать R одинаковых филиалов библиотеки, чтобы очередь читателей делилась и чтобы пожар в одном филиале не уничтожил книги». Объём лечит шард, нагрузку и отказ — реплика.

Полный флот листьев — это сетка S × R: S шардов, у каждого R реплик. Чтобы ответить на запрос полностью, нужно опросить по одной реплике каждого из S шардов (см. scatter-gather, 13.2).

Код: Выделить всё

                     корень (root / broker)
                            │
        ┌───────────────────┼───────────────────┐
     шард 0              шард 1   ...          шард S-1
   ┌───┬───┬───┐      ┌───┬───┬───┐         ┌───┬───┬───┐
   r0  r1  r2         r0  r1  r2            r0  r1  r2     ← R реплик каждого шарда

Документное vs термовое шардирование

Есть два способа разрезать обратный индекс.

• Документное партиционирование (document-partitioning, локальный индекс): каждый шард строит полный обратный индекс по своему подмножеству документов. Терм кот имеет постинг-лист в каждом шарде, но только по своим документам.
• Термовое партиционирование (term-partitioning, глобальный индекс): обратный индекс режут по словарю — шард владеет полным постинг-листом для своего набора термов. Весь постинг-лист терма кот лежит на одном шарде целиком.

Код: Выделить всё

Критерий                       |  Документное                                   |  Термовое
-------------------------------+------------------------------------------------+-----------------------------------------------------
Где живёт запрос из k слов     |  на всех шардах параллельно                    |  только на k шардах (по числу термов)
Объём fan-out                  |  широкий (S узлов)                             |  узкий (k узлов)
Дисбаланс нагрузки             |  равномерный (любой запрос грузит всех)        |  перекошенный (частые термы → горячие шарды)
Стоимость пересечения списков  |  локально в шарде, дёшево                      |  пересылка длинных постинг-листов по сети
Добавление документа           |  пишем в один шард                             |  трогаем много шардов (по числу термов в документе)
Отказ шарда                    |  теряем долю документов (можно деградировать)  |  теряем целые термы (катастрофа для запросов с ними)

Интуиция. Документное — «каждый библиотекарь знает всё про свою полку». Термовое — «один библиотекарь знает всё про слово кот по всей библиотеке». Первое легко балансируется и деградирует, второе экономит fan-out, но создаёт горячие точки и хрупкость.

В вебпоиске почти всегда побеждает документное шардирование: оно равномерно по нагрузке, устойчиво к отказу (потеря шарда — это потеря доли корпуса, а не доли языка), тривиально для записи и хорошо ложится на ярусы из Модуля 4 (высокий ярус = маленький шард по «лучшим» документам). Цена — широкий fan-out, и весь Модуль 13.2 про то, как с ним жить.

Инженерная заметка. Термовое партиционирование иногда применяют точечно для очень длинных постинг-листов или для специальных подсистем (например, отдельный сервис по одному измерению). Но как основная схема веб-индекса оно проигрывает: пересылка постинг-листов на десятки миллионов документов по сети убивает латентность, а распределение частот термов по закону Ципфа гарантирует горячие шарды.

Как назначать документ шарду

Схема docID → shard определяет равномерность и стоимость ребаланса.

• Хеш-партиционирование: shard = hash(docID) mod S. Идеально равномерно по объёму и нагрузке, но при изменении S переезжает почти весь корпус. Лечится консистентным хешированием (consistent hashing) или рандеву-хешированием (rendezvous/HRW), где добавление шарда двигает лишь ~1/S документов.
• Диапазонное партиционирование: режем по диапазонам docID или по какому-то ключу (хост, язык, регион). Удобно для локальности (документы одного сайта рядом), но провоцирует перекосы (крупный хост = горячий диапазон).
• По ярусам/важности: документ кладут в шард яруса в зависимости от его статической ценности (Модуль 4). Высокий ярус — мало документов, много реплик; низкий — наоборот.

Внимание. Любая схема, где shard зависит от S напрямую (mod S), означает, что масштабирование флота — это полная переиндексация и переезд. Если вы планируете расти, закладывайте консистентное/рандеву-хеширование или фиксированное большое число логических шардов, которые потом группируются на физические машины (виртуальные шарды).

Пример. Корпус 10 млрд документов, по 50 млн документов на шард → S = 200 шардов. Целевой QPS 200 000, одна реплика тянет 2 000 QPS → нужно R = 100 реплик на шард. Итого S × R = 20 000 листьев. Если бюджет латентности требует, чтобы один шард обрабатывал запрос за ≤ 30 мс, и 50 млн документов в этот бюджет не укладываются — увеличиваем S (мельче шарды → быстрее каждый, но шире fan-out → хуже хвост; см. 13.2).

Маршрутизация запросов: дерево обслуживания

Запрос проходит дерево обслуживания (serving tree). В простейшем виде — два яруса:

1. Корень / брокер (root, broker, aggregator): принимает запрос, рассылает его по всем шардам (по одной реплике каждого), собирает ответы, сливает и возвращает. При больших S корней делают многоуровневыми (промежуточные агрегаторы), чтобы fan-out одного узла не превышал сотни-другой.
2. Листья (leaf): реплики шардов, которые реально ищут по своему куску индекса.

Внутри шарда балансировщик реплик выбирает, какую из R реплик опросить. Стратегии:

• Round-robin / случайно — просто, но не учитывает загрузку.
• Least-outstanding-requests (наименьшее число незавершённых запросов) — отправляем туда, где меньше всего «висящих» запросов; хорошо ловит временно перегруженную реплику.
• Power-of-two-choices: выбрать две случайные реплики и отправить в менее загруженную — почти оптимально при копеечной стоимости.
• Локальность/прогрев кэша: «прилипание» (affinity) запроса к реплике, у которой нужный кусок индекса уже в кэше (Модуль 12).

Инженерная заметка. Балансировщик должен видеть локальную оценку загрузки реплики (длина очереди, незавершённые запросы), а не только «жив/мёртв». Балансировка по живости пропускает реплику, которая жива, но захлёбывается из-за сборки мусора, холодного кэша или фоновой подмены индекса (13.4) — а именно такие реплики делают хвост (13.2).

SEO-врезка. Документное шардирование + случайная реплика означают, что два одинаковых запроса могут попасть на разные реплики с чуть разными версиями индекса (13.4) или разным состоянием кэша, и дать слегка разную выдачу или порядок. Это не «персонализация» и не баг ранжирования — это распределённая природа обслуживания. Поэтому замеры позиций надо усреднять по многим прогонам, а не делать выводов по одному снимку.

Частые заблуждения

Заблуждение. «Шардирование и репликация — это одно и то же, просто копии данных.» Нет: шард делит разные данные (лечит объём и латентность), реплика дублирует одни и те же данные (лечит QPS и отказ). Это ортогональные оси, и масштабировать их нужно по разным причинам.

Заблуждение. «Чем больше шардов, тем быстрее.» Мельче шарды → быстрее каждый лист, но шире fan-out, а хвостовая латентность агрегата растёт с числом опрашиваемых узлов (13.2). Существует оптимум: слишком много шардов делает p99 хуже, а не лучше.

Заблуждение. «Термовое шардирование экономит сеть, значит лучше.» Оно экономит число опрошенных узлов, но платит пересылкой длинных постинг-листов и горячими шардами на частых термах. В вебе это проигрышный размен.

Лаба / практика

Спроектируйте топологию флота. Дано: корпус N = 8·10⁹ документов, целевой QPS = 150 000, одна реплика держит ≤ 40 млн документов и ≤ 2 500 QPS, бюджет латентности на лист ≤ 35 мс.
Шаги: (1) посчитайте минимальное S по объёму и по бюджету латентности, возьмите максимум; (2) посчитайте R по QPS, добавьте запас на отказы (+30 %) и на хвост; (3) посчитайте суммарное число листьев S × R и прикиньте, нужен ли промежуточный ярус агрегаторов при ограничении fan-out корня ≤ 60; (4) выберите схему docID → shard и обоснуйте поведение при росте S на 25 %.
Время ~50 мин. Критерий «сделано»: числа сходятся, выбор документного шардирования и консистентного хеширования аргументирован, объяснено, как S влияет на хвост.

Контрольные вопросы

1. Какую проблему решает увеличение S, а какую — увеличение R? Можно ли увеличением R ускорить один запрос?
2. Почему в вебпоиске документное партиционирование почти всегда предпочтительнее термового? Назовите минимум три причины.
3. Что произойдёт с выдачей при отказе одного шарда в документной и в термовой схеме соответственно?
4. Почему shard = hash(docID) mod S плохо масштабируется и чем это лечат?
5. Зачем нужен промежуточный ярус агрегаторов, если можно опрашивать листья прямо из корня?
6. Почему балансировка «по живости» хуже, чем «по числу незавершённых запросов»?
7. Как ярусы индекса (Модуль 4) отображаются на число шардов и реплик?

Глава 13.2. Scatter-gather и проблема хвостовых латентностей (tail latency), hedged requests (продвинутый)

Цели обучения

После главы студент сможет:

• описать паттерн scatter-gather (разослать → собрать) и его латентностный профиль;
• объяснить, почему p99 агрегата хуже p99 любого отдельного узла, и вывести это математически;
• оценить вероятность «попасть в медленный хвост» как функцию ширины fan-out;
• применить hedged requests (подстраховочные/дублирующие запросы) и tied requests, оценить их стоимость;
• перечислить источники хвоста (variability) и инженерные приёмы их подавления.

Конспект

Паттерн scatter-gather

Чтобы ответить на запрос, корень рассылает (scatter) его на S шардов и собирает (gather) их ответы. Ключевое свойство: ответ корня готов не раньше самого медленного из S ответов. Латентность агрегата — это максимум по латентностям листьев, а не их среднее.

Код: Выделить всё

scatter →   ┌→ лист 0 ──[ 8 мс]─┐
            ├→ лист 1 ──[12 мс]─┤
            ├→ лист 2 ──[ 9 мс]─┤   gather: ждём ВСЕХ
            ├→ ...             ─┤   итог = max = 47 мс
            └→ лист S-1 [47 мс]─┘   (один медленный портит всё)

Интуиция. Колонна идёт со скоростью самого медленного. Неважно, что 99 листьев ответили за 10 мс — если сотый думал 200 мс, пользователь ждёт 200 мс. Чем больше листьев в колонне, тем выше шанс, что хоть один окажется медленным.

Почему хвост агрегата хуже хвоста узла (математика)

Пусть у одного листа вероятность ответить медленнее порога T равна q (например, q = 0.01, то есть T = p99 одного листа). Запрос ждёт всех S независимых листьев. Вероятность, что все уложились в T:

P(все ≤ T) = (1 − q)^S

Значит вероятность, что агрегат превысит T (хотя бы один медленный):

P(агрегат > T) = 1 − (1 − q)^S

Пример. q = 0.01 (p99 листа = T), S = 100. Тогда P(агрегат > T) = 1 − 0.99¹⁰⁰ ≈ 1 − 0.366 = 0.634. То есть 63 % запросов превысят порог, который для одного листа был p99. Иначе: то, что для листа было событием «1 раз из 100», для агрегата из 100 листьев становится типичным. При S = 200 это уже 1 − 0.99²⁰⁰ ≈ 0.87.

Вывод, который надо усвоить навсегда: fan-out превращает редкий хвост одного узла в обычное поведение системы. Поэтому в распределённом поиске нельзя оптимизировать среднее — надо давить хвост каждого листа, потому что он мультиплицируется.

Инженерная заметка. Если хотите, чтобы агрегат держал p99 ≤ T при S листьях, то каждый лист должен держать перцентиль порядка (1 − T_target)^{1/S}. Грубо: для p99 агрегата при S = 100 каждому листу нужен примерно p99.99 ≤ T. Поэтому в распределённых системах целятся в p999/p9999 отдельного узла, а не в p99.

Источники хвоста (откуда берётся медленный лист)

Хвост — это не «случайность», у него есть конкретные причины (variability):

• Конкуренция за ресурсы: CPU/память/диск/сеть делятся с соседями (shared tenancy), фоновыми задачами, другими запросами.
• Сборка мусора (GC pause) и дефрагментация — «стоп-мир» на десятки-сотни мс.
• Холодный кэш: реплика после рестарта или подмены индекса (13.4) читает с диска, а не из памяти.
• Очереди: запрос ждёт в очереди перегруженной реплики (head-of-line blocking).
• Перекошенные шарды: «тяжёлый» запрос (частый терм, длинные постинг-листы) на конкретном шарде.
• Аппаратные деграданты: сбоящий диск/сетевая карта/перегретое ядро («серая» неисправность — узел жив, но медленный).
• Периодика: чекпойнты, ротация логов, мониторинг, cron — синхронные «икоты».

Hedged requests и tied requests

Если хвост неустраним на уровне узла, его обходят на уровне запроса — избыточностью во времени.

• Hedged requests (подстраховочные запросы): отправляем запрос одной реплике; если ответ не пришёл за порог (например, за p95 ожидаемого времени), отправляем тот же запрос второй реплике и берём тот, что вернётся первым. Остальные отменяем.

Интуиция. Вы заказали такси и, если оно не подъехало за 5 минут, вызываете второе и едете на том, что приедет раньше. Платите чуть больше, но почти никогда не ждёте «хвост».

Стоимость крошечная, если хеджировать только хвост: при пороге на p95 лишь ~5 % запросов дублируются → +5 % нагрузки, а p99/p999 падают в разы.

• Tied requests (связанные запросы): отправляем сразу двум репликам, но они «знают» друг о друге — первая, начавшая обработку, шлёт второй сигнал «отмена», чтобы не делать работу дважды. Срезает хвост ещё агрессивнее ценой небольшого сетевого оверхеда на отмену.

Внимание. Hedged-запросы обязаны быть идемпотентными и отменяемыми, иначе вы удваиваете нагрузку и можете дважды выполнить побочный эффект. И никогда не хеджируйте с самого начала (порог 0) — это удвоит флот; смысл именно в том, чтобы дублировать только хвост, поставив порог на высокий перцентиль.

Внимание (взаимоблокировка хвоста). Наивный ретрай «по таймауту всех подряд» в момент общей перегрузки порождает ретрай-шторм: система и так не справляется, а вы удваиваете нагрузку — и окончательно её топите (метастабильный отказ). Поэтому hedged-запросы ограничивают бюджетом ретраев (retry budget, например «не более 10 % дополнительных запросов глобально») и адаптивным порогом, который растёт при росте общей нагрузки.

Другие приёмы подавления хвоста

• Микропартиционирование: много мелких логических шардов на машину → «тяжёлый» шард можно быстро перекинуть на менее загруженную реплику.
• Selective replication: горячим/тяжёлым кускам — больше реплик.
• Изоляция фоновых задач: чекпойнты, GC, подмену индекса разносить по времени между репликами (не у всех сразу), троттлить.
• Завершение по «достаточному кворуму»: не ждать всех S, а вернуть, когда пришло, скажем, S − 2, признав остаток частичным ответом (мост к 13.3).

SEO-врезка. Hedged-запросы и завершение по кворуму означают, что под нагрузкой ваш документ может «не успеть» с медленного шарда и не попасть в выдачу именно в этот момент — при том, что он проиндексирован и релевантен. Это вероятностный эффект хвоста, а не «выпадение из индекса». Диагностируется тем, что при повторных/менее нагруженных запросах документ возвращается.

Частые заблуждения

Заблуждение. «Средняя латентность 10 мс — значит система быстрая.» Пользователь живёт в хвосте: при широком fan-out именно p99/p999 определяют опыт, и они могут быть в десятки раз хуже среднего. SLO формулируют в перцентилях.

Заблуждение. «Добавим реплик/шардов — станет быстрее.» Больше реплик помогает QPS, но не латентности одного запроса. Больше шардов ускоряет лист, но расширяет fan-out и ухудшает хвост агрегата. Скорость лечится подавлением хвоста и хеджированием, а не только железом.

Заблуждение. «Хеджирование удваивает нагрузку.» Только если хеджировать всё. При пороге на высоком перцентиле дублируется лишь хвост (единицы процентов), а выигрыш по p99 — кратный.

Лаба / практика

Симуляция хвоста. (1) Возьмите распределение латентности листа (например, логнормальное со средним 8 мс и редкими «икотами» до 200 мс с вероятностью 1 %). (2) Смоделируйте scatter-gather: для S ∈ {1, 10, 50, 100, 200} сгенерируйте по 100 000 запросов, латентность агрегата = max по S листьям; постройте p50/p99/p999 агрегата как функцию S. (3) Добавьте hedged-запросы: при превышении порога = p95 листа дублируйте запрос на вторую реплику, берите min двух; измерьте новый p99 агрегата и процент дополнительной нагрузки. (4) Постройте кривую «доля дублей ↔ выигрыш по p99».
Время ~70 мин. Критерий «сделано»: воспроизведён рост p99 агрегата с S (совпал с формулой 1 − (1−q)^S по порядку), показано, что хеджирование ~5 % нагрузки даёт кратное падение p99, найден разумный порог.

Контрольные вопросы

1. Выведите вероятность P(агрегат > T) для S независимых листьев с P(лист > T) = q. Посчитайте для q = 0.005, S = 150.
2. Почему для p99 агрегата при большом S каждому листу нужно целиться в p999/p9999?
3. Чем hedged-запросы отличаются от tied-запросов? Когда выбрать второе?
4. Почему наивный ретрай по таймауту опасен при общей перегрузке и что такое retry budget?
5. Назовите пять источников хвостовой латентности и приём подавления для каждого.
6. Почему увеличение числа шардов может ухудшить p99, хотя каждый лист стал быстрее?
7. Какой порог хеджирования вы бы поставили и почему именно высокий перцентиль, а не 0?
8. Как «завершение по кворуму S − k» связывает эту главу с грациозной деградацией (13.3)?

Глава 13.3. Отказоустойчивость, грациозная деградация, таймауты, частичные ответы (продвинутый)

Цели обучения

После главы студент сможет:

• спроектировать дедлайн-бюджет (deadline budget) запроса и распределить его по ярусам дерева обслуживания;
• отличить fail-fast от fail-soft и обосновать грациозную деградацию (graceful degradation) вместо полного отказа;
• сформировать корректный частичный ответ (partial result) и пометить его для последующих стадий и измерений;
• применить автоматические предохранители (circuit breaker), сброс нагрузки (load shedding) и отсечку хвоста в систему обслуживания;
• объяснить, почему ретраи должны быть идемпотентными и бюджетированными.

Конспект

Дедлайн вместо таймаута

Наивный таймаут — «жду ответа X мс на каждом вызове» — складывается по уровням дерева и легко превышает то, что готов ждать пользователь. Правильная модель — дедлайн (deadline / absolute budget): запрос несёт с собой абсолютное время, к которому он обязан завершиться (например, «350 мс от приёма»). Каждый узел вычитает уже потраченное и передаёт остаток вниз (deadline propagation). Если остаток меньше минимально осмысленного — узел даже не начинает работу (fail-fast), экономя ресурсы.

Код: Выделить всё

приём (t=0, дедлайн 350 мс)
  корень  ─ потратил 20 мс ─→ листьям уходит дедлайн «осталось 330 мс»
    лист   ─ видит «330 мс», но сам отвечает за ≤ 60 мс ─→ ставит свой под-дедлайн
       └─ под-вызов (например, к сервису сниппетов) получает «осталось 280 мс»

Интуиция. Дедлайн — это «поезд уходит в 18:00» для всех участников сразу, а таймаут — «каждый дал себе по 10 минут на свой кусок» (и сумма уехала за полночь). Дедлайн распространяется по дереву и не даёт суммарному времени разойтись.

Инженерная заметка. Дедлайн передаётся в метаданных запроса (контекст вызова) и проверяется перед каждой дорогой операцией, а не только по таймеру. Узел, у которого осталось 5 мс, не должен начинать чтение постинг-листа на 30 мс — он сразу возвращает «не успел», и корень соберёт частичный ответ.

Грациозная деградация: частичный ответ лучше отсутствия ответа

Принцип: fail-soft, а не fail-hard. Если к дедлайну ответили не все S шардов, корень не обязан проваливать весь запрос — он возвращает частичный ответ из тех шардов, что успели. Для веб-поиска «топ-10 по 198 шардам из 200» обычно почти неотличим от «топ-10 по 200» — потерянные 2 шарда вряд ли содержали лучшие результаты, а пользователь получил выдачу вовремя.

Формы деградации (по нарастанию):

1. Усечение fan-out по кворуму: вернуть результат по S − k шардам к дедлайну.
2. Срезание стадий ранжирования: под нехватку времени пропустить дорогой L3 (Модуль 12) и вернуть результат L2.
3. Отключение обогащений: убрать сниппеты/колдстарт-блоки/федеративные источники (Модуль 14), оставив «голубые ссылки».
4. Падение на резервный/кэшированный результат: если живой путь не успевает — отдать недавно закэшированную выдачу (Модуль 12).

Внимание. Частичный ответ обязан быть помечен флагом полноты (например, coverage = 198/200, degraded = true). Иначе: (а) метрики качества (Модуль 19) посчитают деградированную выдачу как штатную и исказят оценку ранжирования; (б) кэш может сохранить неполный ответ как «настоящий»; (в) метапоиск (Модуль 14) не узнает, что федеративный источник выпал. Полнота — это часть контракта ответа.

SEO-врезка. Под пиковой нагрузкой система может отдать частичный ответ или результат с урезанным L3. Поэтому ваш документ, который в обычных условиях стоит в топе после полного ранжирования, под нагрузкой может временно проседать или отсутствовать. Это не сигнал «потери качества» документа, а защита системы от перегрузки; эффект непостоянен и не воспроизводится в спокойное время.

Предохранители и сброс нагрузки

• Автоматический предохранитель (circuit breaker): если реплика/сервис стабильно отвечает ошибками или хвостом, корень временно перестаёт слать ей запросы (размыкает цепь), периодически «прощупывая» (half-open). Это не даёт мёртвому/больному узлу тянуть хвост и копить очередь.
• Сброс нагрузки (load shedding): при превышении ёмкости узел отбрасывает часть запросов на входе (быстрый отказ), вместо того чтобы принять все и захлебнуться, отвечая всем медленно. Лучше отказать 5 %, чем уронить p99 для 100 %.
• Адаптивные конкуренси-лимиты: ограничение числа одновременно обрабатываемых запросов на узле; при достижении лимита — отказ/очередь с дедлайном, а не безграничное накопление.

Интуиция (метастабильность). Перегруженная система без сброса нагрузки попадает в порочный круг: очереди растут → латентность растёт → клиенты ретраят → нагрузка растёт ещё → и так до коллапса, который не рассасывается даже после спада входного потока (метастабильный отказ). Сброс нагрузки и retry budget разрывают этот круг.

Идемпотентность и бюджет ретраев

Поисковый запрос на чтение естественно идемпотентен (повтор не меняет состояние), поэтому ретраи и hedged-запросы (13.2) безопасны. Но их всё равно ограничивают бюджетом ретраев (например, ретраи ≤ 10 % основного трафика), иначе при общей деградации ретраи добивают систему (см. ретрай-шторм, 13.2). Любые операции с побочными эффектами (логирование кликов, обновление счётчиков) делают идемпотентными по ключу запроса.

Частые заблуждения

Заблуждение. «Если шард не ответил — надо вернуть ошибку.» Для агрегирующего поиска полный отказ хуже, чем частичный ответ: «топ по 198/200 шардам вовремя» лучше, чем «ошибка через таймаут». Главное — пометить ответ как частичный.

Заблуждение. «Таймаут на каждом вызове защищает от зависаний.» Локальные таймауты складываются по дереву и не дают гарантии сверху. Гарантию даёт сквозной дедлайн, распространяемый по всем уровням.

Заблуждение. «Под перегрузкой надо принять все запросы и обработать как сможем.» Это путь к метастабильному коллапсу. Под перегрузкой надо сбрасывать часть нагрузки на входе, сохраняя приемлемую латентность для остальных.

Лаба / практика

Реализуйте дедлайн-бюджет и деградацию в симуляторе scatter-gather из 13.2. (1) Добавьте сквозной дедлайн 350 мс и его распространение: корень тратит время на сборку, листья — на поиск; узел, у которого остаток меньше его типичного времени, сразу возвращает «не успел». (2) Реализуйте частичный ответ: корень ждёт до дедлайна и возвращает то, что собрал, с полем coverage. (3) Добавьте circuit breaker: лист, давший > N хвостовых/ошибочных ответов подряд, на M секунд исключается из рассылки. (4) Под синтетическим всплеском нагрузки сравните три режима: «без защиты», «таймаут на вызов», «дедлайн + деградация + breaker» — по p99, доле ошибок и доле частичных ответов.
Время ~75 мин. Критерий «сделано»: режим с дедлайном и деградацией держит p99 и не уходит в метастабильный коллапс при всплеске; частичные ответы корректно помечены coverage.

Контрольные вопросы

1. Чем дедлайн принципиально лучше набора локальных таймаутов? Что такое deadline propagation?
2. Перечислите уровни грациозной деградации от мягкого к жёсткому. Какой пропустить первым под нехваткой времени?
3. Почему частичный ответ обязательно помечать флагом полноты? Что сломается без этой пометки в Модулях 14 и 19?
4. Как работает circuit breaker и зачем ему состояние half-open?
5. Что такое метастабильный отказ и какие два механизма его предотвращают?
6. Почему «отказать 5 % на входе» лучше «обработать 100 % медленно»?
7. Почему ретраи поискового чтения безопасны, но их всё равно бюджетируют?

Глава 13.4. Обновление индекса: версии, консистентность, горячая подмена, реплей (продвинутый)

Цели обучения

После главы студент сможет:

• описать версионирование индекса и инвариант «весь шард обслуживает одну согласованную версию»;
• спроектировать горячую подмену (hot swap, atomic switch) новой версии без простоя и с возможностью отката (rollback);
• объяснить уровни консистентности между репликами и шардами и эффект лага репликации (replication lag);
• встроить реалтайм-контур (Модуль 4) поверх версионированного базового индекса через наложение (overlay) и реплей (replay) журнала;
• спланировать выкатку версии (rolling update) так, чтобы не обрушить хвост и кэш одновременно у многих реплик.

Конспект

Зачем версии

Индекс не статичен: его пересобирают (batch, Модуль 4), добавляют свежие документы (realtime), меняют схему факторов. Если просто «писать поверх» работающего индекса, запрос может прочитать полусобранное состояние — часть постинг-листов от старой версии, часть от новой → неконсистентная и даже падающая выдача.

Решение — неизменяемые версии (immutable index versions). Каждая полная сборка получает монотонный идентификатор (v1742, v1743, …). Версия неизменяема: её строят в стороне, проверяют, и только потом публикуют. Реплика обслуживает запросы из одной версии целиком и переключается на новую атомарно.

Интуиция. Это как выкладка нового сайта: вы не редактируете «живые» файлы под трафиком, а собираете новую папку release-1743, проверяете её, и затем одним движением переставляете симлинк current → release-1743. Запрос, начавшийся «до», дочитает старую папку; новый пойдёт в новую. Никто не видит полусобранного.

Инвариант консистентности

Главный инвариант обслуживания:

Один запрос к одному шарду обслуживается целиком из одной согласованной версии индекса.

Между шардами и репликами допускается расхождение версий во времени (eventual consistency): пока идёт выкатка, реплика A уже на v1743, реплика B ещё на v1742. Это нормально и почти незаметно для топ-результата, но порождает наблюдаемые эффекты (см. SEO-врезку). Чего нельзя — это смешать версии внутри одного ответа одного шарда.

Код: Выделить всё

Что                                 |  Допустимая консистентность
------------------------------------+--------------------------------------
Внутри одного постинг-листа         |  строгая (одна версия, неизменяемая)
Внутри ответа одного шарда          |  строгая (одна версия)
Между репликами одного шарда        |  eventual (лаг репликации)
Между шардами в одном запросе       |  eventual (разные версии при выкатке)
Базовый индекс vs realtime-overlay  |  базовый строгий + наложение свежего

Горячая подмена (hot swap)

Алгоритм атомарного переключения реплики на новую версию:

1. Доставка новой версии на реплику рядом со старой (новая папка/сегменты), старая продолжает обслуживать.
2. Прогрев (warm-up): новую версию открывают «вхолостую», прогоняют через неё теневой трафик/набор запросов, чтобы поднять кэши и страничный кэш в память. Без прогрева переключение даст холодный кэш → всплеск хвоста (13.2).
3. Атомарное переключение: указатель «активная версия» атомарно переставляется на новую. Запросы «в полёте» дочитывают старую (она держится, пока есть ссылки), новые идут в новую.
4. Удержание старой версии ещё T секунд — на случай немедленного отката и для дочитывания зависших запросов.
5. Сборка мусора старой версии после слива ссылок.

Внимание (одновременная подмена = хвостовая буря). Если все реплики шарда переключаются и прогреваются одновременно, у всех одновременно холодный кэш и фоновая нагрузка прогрева → p99 шарда взлетает, а то и нет живых реплик. Подмену делают скользящей (rolling): по одной-двум репликам за раз, прогрев до переключения, и никогда не выводить из строя больше, чем позволяет запас по QPS и отказам (13.1).

Откат (rollback). Поскольку версии неизменяемы и старая держится T секунд, откат — это просто атомарно переставить указатель обратно. Поэтому новую версию выкатывают постепенно (canary: сначала 1 % флота), смотрят на метрики качества (Модуль 19) и латентности, и только потом раскатывают на весь флот.

Реалтайм-контур поверх версий (overlay + replay)

Batch-версия публикуется, скажем, раз в часы — этого мало для «свежего». Поверх неизменяемого базового индекса держат realtime-наложение (overlay, Модуль 4): небольшой, часто обновляемый индекс свежих/изменённых документов, плюс карта удалений/перекрытий (delete/tombstone map), чтобы скрыть устаревшие версии документа из базы. Ответ шарда = база (версия) ⊕ overlay.

Реплей (replay) — механизм восстановления и согласования: все изменения (новые документы, обновления, удаления) пишутся в упорядоченный журнал (write-ahead log) с монотонными смещениями. Реплика, отставшая или перезапущенная, проигрывает журнал с последнего подтверждённого смещения и догоняет актуальное состояние. Тот же журнал используется, чтобы перестроить overlay поверх новой batch-версии: после публикации v1743 overlay-изменения, уже вошедшие в v1743, отсекаются по смещению, а более свежие — реплеятся поверх.

Инженерная заметка. Журнал даёт две вещи разом: (1) долговечность — overlay в памяти можно восстановить реплеем после сбоя; (2) точку согласования — смещение журнала служит «версией свежести», по которой реплики сверяют, насколько они отстали (replication lag). Лаг измеряют именно в терминах «отставание по смещению/времени журнала».

SEO-врезка. Из версий и лага напрямую следуют наблюдаемые эффекты: (1) только что проиндексированный документ виден не мгновенно и не везде одновременно — он сначала попадает в realtime-overlay одних реплик, потом расходится; (2) во время выкатки batch-версии часть реплик отвечает по старой версии — поэтому позиции «дрожат» и зависят от того, на какую реплику попал запрос; (3) удаление/изменение документа отражается через tombstone и догоняет с лагом. Вывод: не делайте выводов о ранжировании по единичному свежему замеру — дайте изменению устаканиться по флоту.

Частые заблуждения

Заблуждение. «Обновить индекс — значит дописать в работающий файл.» Запись поверх живого индекса под трафиком ведёт к чтению полусобранного состояния. Версии неизменяемы; меняется лишь атомарный указатель на активную версию.

Заблуждение. «Все реплики всегда видят одно и то же.» Между репликами и шардами консистентность eventual: во время выкатки и из-за лага репликации они расходятся. Строгая консистентность гарантируется только внутри одного ответа одного шарда.

Заблуждение. «Горячую подмену можно делать на всех репликах сразу — так быстрее.» Так вы получите одновременный холодный кэш и хвостовую бурю, а в худшем случае — отсутствие живых реплик шарда. Подмена строго скользящая, с прогревом до переключения.

Заблуждение. «Realtime-индекс заменяет batch.» Они дополняют друг друга: batch даёт компактный оптимизированный базовый индекс, overlay — свежесть; реплей сшивает их по смещению журнала. Overlay не растёт бесконечно — он периодически «впитывается» новой batch-версией.

Лаба / практика

Спроектируйте и просимулируйте горячую подмену версии шарда. Дано: шард с R = 6 репликами, целевой p99 ≤ 40 мс, прогрев новой версии добавляет реплике +50 % латентности на 30 с. (1) Опишите протокол: доставка → прогрев → атомарный свитч → удержание старой T → GC; укажите инвариант консистентности. (2) Сравните стратегии выкатки: «все сразу», «по 3», «по 1 (canary)» — по тому, удержится ли p99 ≤ 40 мс при текущем QPS и запасе реплик из 13.1. (3) Добавьте overlay + журнал: после публикации новой версии отсеките вошедшие изменения по смещению и реплейте остаток; покажите, что свежий документ не теряется при подмене. (4) Смоделируйте откат по плохой канареечной метрике.
Время ~70 мин. Критерий «сделано»: скользящая выкатка с прогревом держит p99, инвариант «одна версия на ответ шарда» соблюдён, свежесть из overlay переживает подмену, откат — атомарный.

Контрольные вопросы

1. Сформулируйте инвариант консистентности обслуживания. Что допустимо смешивать, а что нет?
2. Зачем версии делают неизменяемыми и почему это упрощает откат?
3. Что произойдёт с p99, если переключить и прогреть все реплики шарда одновременно? Как это лечит скользящая выкатка?
4. Зачем нужен прогрев новой версии перед переключением?
5. Как overlay и журнал реплея обеспечивают свежесть и долговечность? Как overlay согласуется с новой batch-версией по смещению?
6. Что такое лаг репликации и в каких единицах его измеряют?
7. Какие наблюдаемые SEO-эффекты порождают версии и лаг? Почему нельзя судить о ранжировании по единичному свежему замеру?
8. Как канареечная выкатка связана с метриками качества из Модуля 19?

Итоги модуля

1. Шард и реплика — ортогональные оси. Шардирование делит корпус (лечит объём и латентность одного запроса), репликация дублирует шард (лечит QPS и отказ). Масштабировать их нужно по разным причинам и независимо.
2. В вебе побеждает документное шардирование. Оно равномерно по нагрузке, устойчиво к отказу (теряется доля корпуса, а не доля языка), легко пишется и деградирует. Цена — широкий fan-out.
3. Хвост важнее среднего, и fan-out его мультиплицирует. P(агрегат > T) = 1 − (1 − q)^S: редкое для одного узла событие при большом S становится типичным. SLO формулируют в p99/p999, а узлы целят в p999/p9999.
4. Хвост давят избыточностью во времени. Hedged- и tied-запросы дублируют только хвост (порог на высоком перцентиле) и режут p99 в разы ценой единиц процентов нагрузки — но строго под retry budget, чтобы не вызвать ретрай-шторм.
5. Дедлайн, а не таймаут. Сквозной распространяемый дедлайн гарантирует время сверху по всему дереву; локальные таймауты складываются и такой гарантии не дают.
6. Грациозная деградация лучше отказа. Частичный ответ по S − k шардам, срезание L3, отключение обогащений, падение на кэш — но всё помечено флагом полноты, иначе врут метрики и кэш.
7. Под перегрузкой — сброс нагрузки и предохранители. Иначе система сваливается в метастабильный коллапс, который не рассасывается после спада входа.
8. Индекс обновляют версиями и горячей подменой. Неизменяемые версии, прогрев, атомарный свитч, скользящая выкатка с канарейкой и откатом; свежесть — через overlay и реплей журнала. Инвариант: одна согласованная версия на один ответ шарда.

Глоссарий модуля

• Шардирование (sharding/partitioning) — деление корпуса на непересекающиеся куски-шарды ради объёма и латентности.
• Реплика (replica) — идентичная копия шарда ради QPS и отказоустойчивости.
• Документное / термовое партиционирование — разрез индекса по документам (локальный индекс на шарде) или по словарю (постинг-лист терма целиком на одном шарде).
• Консистентное / рандеву-хеширование — схемы docID → shard, при которых добавление шарда двигает лишь ~1/S данных.
• Дерево обслуживания (serving tree) — корень/брокер → (промежуточные агрегаторы) → листья.
• Scatter-gather — разослать запрос по шардам и собрать ответы; латентность = max по листьям.
• Хвостовая латентность (tail latency) — высокие перцентили p99/p999/p9999, определяющие пользовательский опыт.
• Fan-out — ширина разветвления запроса (число опрашиваемых узлов).
• Hedged / tied requests — дублирование запроса на вторую реплику для срезания хвоста (с отменой проигравшего).
• Retry budget — глобальный лимит на долю дополнительных запросов, защита от ретрай-шторма.
• Метастабильный отказ — самоподдерживающийся коллапс под перегрузкой, не рассасывающийся после спада входа.
• Дедлайн (deadline) и его распространение (propagation) — абсолютный сквозной бюджет времени, передаваемый вниз по дереву.
• Грациозная деградация (graceful degradation) — частичный/упрощённый ответ вместо полного отказа.
• Частичный ответ (partial result), coverage — ответ по части шардов, помеченный долей полноты.
• Circuit breaker — временное исключение больного узла из рассылки с фазой half-open.
• Load shedding — сброс части входной нагрузки ради латентности остальных.
• Версия индекса (immutable version) — неизменяемая полная сборка с монотонным идентификатором.
• Горячая подмена (hot swap / atomic switch) — переключение активной версии без простоя; rolling-выкатка с прогревом, канарейкой и откатом.
• Прогрев (warm-up) — наполнение кэшей новой версии до переключения, чтобы избежать холодного хвоста.
• Overlay (realtime-наложение) — небольшой индекс свежих документов поверх базовой версии; tombstone скрывает устаревшие.
• Реплей (replay) журнала — проигрывание упорядоченного WAL по смещениям ради восстановления и согласования; лаг репликации измеряют по смещению/времени журнала.

Связи с другими модулями

• Опирается на Модуль 4 (индексирование): шарды, сегменты, ярусы, реалтайм-контур и overlay — отсюда; этот модуль распределяет их по флоту и подменяет версии.
• Опирается на Модуль 12 (serving / каскад ранжирования): бюджет латентности одной реплики, кэши, стадии L0–L3. Здесь мы поднимаемся с уровня реплики на уровень флота: scatter-gather, хвост агрегата, деградация (срезание L3, падение на кэш).
• Ведёт к Модулю 14 (метапоиск / федерация): движок федерации — это scatter-gather над разнородными источниками с теми же проблемами хвоста, дедлайнов и частичных ответов, но без гарантии однородности и контроля над листьями; флаг полноты ответа становится контрактом между источниками.
• Связан с Модулем 19 (Оценка и эксперименты): частичные/деградированные ответы и расхождение версий искажают метрики, если не помечены; канареечная выкатка опирается на онлайн-метрики качества.
• Связан с Модулем 17 (свежесть): realtime-overlay и реплей журнала — инфраструктурная основа того, как «новое» доезжает до выдачи и с каким лагом.

Материалы для углубления

• Классические работы по распределённым системам хранения и партиционированию (consistent hashing, rendezvous/HRW-хеширование).
• Обзорные работы по проблеме хвостовой латентности в крупных онлайн-сервисах и приёмам её подавления (hedged/tied requests, микропартиционирование).
• Литература по проектированию надёжности сервисов: дедлайны и их распространение, circuit breaker, load shedding, бюджеты ошибок/ретраев, метастабильные отказы.
• Материалы по архитектуре распределённых поисковых индексов: документное vs термовое партиционирование, деревья обслуживания, scatter-gather.
• Источники по управлению версиями данных под трафиком: неизменяемые сегменты, атомарная подмена, write-ahead log и реплей, eventual consistency и лаг репликации.

[simonelo]

по шардингу инвертированного индекса: вы режете по документам или по термам? мы пробовали term-partitioning и захлебнулись на хвостовых запросах, где один шард с популярным термом ложил всю выдачу. в итоге вернулись к document-partitioning со скаттер-гезером

[dra777]

история с прода: репликация ярусов спасла когда отвалилась стойка целиком. горячий ярус держали в трех репликах, холодный в одной, и при потере реплики деградировали в качестве а не падали. дешевле чем три копии всего индекса

[mrglass]

не совсем согласен что scatter-gather всегда упирается в самый медленный шард. если повесить tail-latency хедж и слать дубль-запрос на отстающий шард, p99 заметно проседает. да, лишний трафик, но для горячего яруса окупается