
Условие
Если каждый узел считает свой топ-100 и результаты складываются, ответ может оказаться неверным при безупречных логах. Задача про условия, при которых частичные результаты складываются.
Спроектируйте выдачу топ-100 по числу событий.
Продукт показывает сто самых популярных элементов за последнюю минуту, час, сутки и за всё время. Отдельно — топ по стране и по категории. Список обновляется не реже раза в минуту.
Считайте, что:
- распределение крайне неравномерное: несколько элементов собирают заметную долю событий, а подавляющее большинство встречается один-два раза; сотое место за любое окно набирает не меньше 0,01 % всех событий окна;
- страна — откуда пришло событие, категория — свойство элемента;
- небольшая ошибка допустима: счёт в списке может отличаться от истинного до 5 % от счёта сотого места, порядок внутри сотни может слегка сдвигаться; пропуск настоящего лидера недопустим;
- события приходят с задержкой до 10 минут и иногда дважды;
- узлы перезапускают в обычном режиме эксплуатации.
Персонализация выдачи, ранжирование по сложной формуле вместо счёта, борьба с накруткой и отчёты за произвольный период в задачу не входят.
Требования
Функциональные 5
- Топ-100 элементов по числу событий за окно
- Окна: минута, час, сутки, всё время
- Отдельный топ по стране и по категории
- Обновление списка не реже раза в минуту
- Опоздавшее до 10 минут событие попадает в окно своего времени
Нефункциональные 5
- Не пропускается элемент, чей счёт за окно превышает счёт сотого места более чем на 5 %
- Погрешность счёта в списке: не более 5 % от счёта сотого места
- Задержка появления события в списке: не более 90 с
- Чтение топа: 99-й процентиль задержки (p99) < 100 мс
- Перезапуск узла: список снова актуален не позже чем через 10 минут
Задачи того же уровня
СложнаяЦифровой кошелёкмиллион переводов в секунду между разделамиВнутренний кошелёк, в котором перевод связывает два произвольных счёта, а в пик их миллион в секунду. Нерв задачи — перевести деньги между счетами на разных узлах так, чтобы они не появились из ниоткуда и не пропали.
СложнаяCoinKeeperучёт личных финансов с импортом из банкаСервис личных финансов: ручные доходы и расходы плюс импорт операций из банка. Нерв задачи — узкое место вне вашей системы, лимит банка, и две разные цены ошибки: ручная запись не должна потеряться, а импортированная — продублироваться.
СложнаяDistributed Job Schedulerзадания по расписаниюМиллионы заданий, и каждую секунду надо знать, у каких подошло время. Плюс честный ответ на главный вопрос: «ровно один раз» недостижимо, достижимы аренда против одновременности и идемпотентность против повторов.
Решите задачу у доски
Интервьюер задаст вопросы по вашей схеме, проверка разберёт её по семи осям




