The Tail at Scale: как побороть медленный хвост (Рубрика #DistributedSystems)

В моих заметках к whitepaper 2013 года "The Tail at Scale" у меня сошлись Monarch, Cassandra, QoS и Harvest/Yield & CAP теорема. Статья хорошо связывает эти темы через один вопрос: как быстро отвечать пользователю, если для ответа нужны сотни серверов, а кто-нибудь из них нет-нет да и тормозит?

Jeffrey Dean и Luiz André Barroso, оба на тот момент Google Fellows, опубликовали её в Communications of the ACM в феврале 2013 года. Они обобщают опыт инфраструктуры Google: интерактивный поиск и чтение распределённых данных, где редкая задержка одного узла становится проблемой всего сервиса.

Если каждый сервер отвечает дольше секунды в 1% случаев, то при запросе к 100 серверам и ожидании всех ответов медленным окажется уже примерно 63% запросов. Здесь обычная теория вероятностей: 1 − 0,99¹⁰⁰. При условии независимости задержек! В моём разборе Monarch, всепланетной системы для телеметрии в Google, уже встречалась другая сторона этой задачи: заранее исключать ненужные узлы из запроса.

Авторы предлагают строить tail-tolerant системы: предсказуемо быстрый сервис из компонентов с непредсказуемым временем ответа. Часть нужных ресурсов уже есть — реплики, созданные для отказоустойчивости. Осталось научиться использовать их и против задержек.

Что для этого делают:

🔸 Hedged requests
Если первая реплика долго молчит, отправляем копию запроса другой; получив ответ, отменяем остальные. В тесте Google чтение 1000 ключей BigTable со 100 серверов с дубликатом после 10 мс сократило p99.9 всей операции с 1800 до 74 мс при +2% запросов. Это результат конкретного теста; число запросов ещё не равно расходу CPU или диска.

🔸Tied requests
Ставим копии в две очереди, и та, где выполнение началось раньше, отменяет вторую. Напоминает занятие нескольких очередей в аэропорту с освобождением остальных, как только тебя позвали. Помогает, когда основная задержка возникает до начала работы. Если медленно само вычисление, отменённая альтернатива могла бы пригодиться.

🔸 Мелкие партиции и выборочная репликация
Делим работу на большее число частей, чем машин, переносим части между ними, популярные данные дополнительно реплицируем. Здесь вспоминаются виртуальные узлы Cassandra. Но микропартиционирование шире consistent hashing, а равномерно разложенные данные ещё не означают равномерную нагрузку.

Есть и знакомые QoS-приёмы: приоритет интерактивным запросам, короткие очереди нижнего уровня, дробление тяжёлых операций. Более неожиданное предложение — иногда синхронизировать фоновое обслуживание. При большом числе участников одна общая короткая пауза может затронуть меньше запросов, чем постоянно занятые разные машины. Правда, общая пауза способна перегрузить общие ресурсы и накопить очередь.

Ещё две рифмы из заметок: временное исключение медленного узла напоминает circuit breaker, а проверка опасного запроса на паре серверов перед массовой рассылкой — canary release на уровне запроса.

А обязательно ждать всех?
Для поиска авторы допускают иногда вернуть немного неполный результат. Это прямо связывается с Harvest/Yield у Armando Fox и Eric Brewer: полнота ответа и вероятность его получить. В их статье 1999 года уже сформулирован CAP principle. Тему гарантий я разбирал в лекции о CAP/PACELC и Cassandra в Центральном Университете. Здесь важно различать полноту и консистентность: пропустить часть поискового индекса и прочитать несовместимые версии данных — разные проблемы.

У дублирования тоже есть граница: другая реплика должна иметь шанс ответить быстрее. Общий перегруженный ресурс или одинаково дорогой запрос могут съесть выигрыш. Поэтому перед внедрением я бы проверял, где именно теряется время, насколько независимы альтернативные пути и какую потерю качества ответа продукт вообще готов принять.

#DistributedSystems #Architecture #SystemDesign #SRE #Research