CS
Задачник Базовый курс EN

Задача

Лавина повторов

ациклический граф динамика граф распределённые системы в проде

Сайт устроен как набор сервисов, которые вызывают друг друга. Пользователь нажал кнопку — запрос пришёл в сервис 1, тот вызвал свои зависимости, они — свои, и так дальше. Вызовы не образуют циклов. На каждой связи «u вызывает v» настроены повторы: если вызов закончился ошибкой, u повторяет его ещё r раз, всего не больше r + 1 попыток.

Часть сервисов сломана: на любой запрос сломанный сервис сразу отвечает ошибкой и никуда дальше не обращается. Исправный сервис на каждый пришедший запрос вызывает все свои зависимости и отвечает ошибкой, если хоть одна из них в итоге ответила ошибкой — уже после всех повторов. Ответ сервиса не зависит от попытки: что сломано, то сломано, а исправное отвечает одинаково. Значит, вызов исправного и здорового снизу сервиса удаётся с первой попытки, а вызов сервиса, который отвечает ошибкой, делается все r + 1 раз.

Сколько запросов получит каждый сервис от одного нажатия кнопки? Выведите общее число запросов ко всем сервисам и сервис, которому досталось больше всех.

Вход

В первой строке — число сервисов n, число связей m и число сломанных k (1 ≤ n ≤ 105, 0 ≤ m ≤ 2·105, 0 ≤ k ≤ n). Дальше m строк «u v r»: u вызывает v и повторяет упавший вызов ещё r раз (1 ≤ u, v ≤ n, 0 ≤ r ≤ 10). Каждая пара u, v встречается не больше одного раза, циклов нет. В последней строке — номера сломанных сервисов (пустая строка, если k = 0). Запрос пользователя приходит в сервис 1. Гарантируется, что общее число запросов не больше 1018.

Выход

Три числа: сколько всего запросов получили все сервисы вместе с первым, номер сервиса, получившего больше всех (из равных — с меньшим номером), и сколько он получил.

Первый пример — из книги Google о надёжности сайтов: три слоя над базой данных, каждый делает четыре попытки, и база получает 43 = 64 запроса от одного действия пользователя. Во втором сломан кэш (сервис 5): каталог (3) зовёт его четырежды на каждую из трёх своих попыток, итого 12 запросов к кэшу, а здоровые авторизация (2) и база (4) получают по одному запросу на каждый вызов.

Примеры

Пример 1

Вход
4 3 1
1 2 3
2 3 3
3 4 3
4
Выход
85 4 64

Пример 2

Вход
6 6 1
1 2 2
1 3 2
3 4 1
3 5 3
2 6 0
5 6 1
5
Выход
21 5 12

Ограничения

Время · Python
4000 мс
Время · Go
1000 мс
Память
256 МБ
Проверка
9 тестов

Разбор

Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.

1Подсказка 1

Чтобы знать, сколько попыток стоит вызов v, нужно сначала знать, ответит ли v ошибкой. А это зависит только от того, что ниже v.

2Подсказка 2

Если сервис получил x запросов, а его вызов к v делается по t попыток, то v получает от него x·t. Нужно ли знать, какими путями эти x запросов пришли?

3Идея

Две волны по топологическому порядку. Снизу вверх: сервис отвечает ошибкой, если сломан сам или если ошибкой отвечает хоть одна его зависимость — повторы ответ не меняют, поэтому «упавшая» зависимость остаётся упавшей. Сверху вниз: число запросов к сервису — сумма по его вызывающим: запросы вызывающего, умноженные на число попыток (r + 1, если v падает, иначе 1). Сломанный сервис никого не вызывает. Это динамика по ациклическому графу: путей может быть экспоненциально много, а значение каждой вершины считается один раз.

4Разбор

Порядок даёт алгоритм Кана: вершины с нулём входящих связей, снятие связей, новые нули. Потом проход в обратном порядке для ошибок и в прямом — для числа запросов. Числа большие, но условие держит их ниже 1018, и в Go хватает int64.

Что это значит для живых систем, видно по ответам. В первом примере повторы на каждом слое умножаются: три слоя по четыре попытки — 64 запроса к базе, которая и так лежит. В тесте с цепочкой из 10 000 сервисов повторы включены только на нижних 34 связях, по три попытки, и последний сервис получает 334 ≈ 1,7·1016 запросов. Поэтому повторять советуют на одном слое, обычно на самом верхнем, а на остальных — сразу передавать ошибку наверх; и ограничивать долю повторов от всех запросов.

4+Решение
5Сложность

O(n + m): топологическая сортировка и два прохода по связям.

6Типичные ошибки
  • Обход всех путей. Рекурсия «спуститься по каждой связи, умножив на попытки» даёт верные числа, но посещает каждый путь отдельно; в графе из 28 слоёв по два сервиса их 227.
  • Повторы на здоровых вызовах. Повторяют только упавший вызов: если v ответил без ошибки, попытка одна.
  • Сломанный сервис зовёт зависимости. Он отвечает ошибкой сразу, его связи в этот раз не работают.
  • Ошибка, но не повтор. Сервис падает, если упала хоть одна зависимость, — даже если на этой связи r = 0.

Алгоритмы задачи

SYS Приём Повтор с джиттером Пауза перед повтором растёт вдвое и выбирается случайно: клиенты расходятся во времени и не бьют по серверу волнами. O(1) на решение о паузе 2 задачи GRA Алгоритм Топологическая сортировка Выстраивает вершины графа без циклов так, чтобы все рёбра смотрели вперёд, за O(V + E). O(V + E) 2 задачи
Каталог алгоритмов