Перейти к содержанию

Сложная

Топ-K по потоку событий

Условие

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

Спроектируйте выдачу топ-100 по числу событий.

Продукт показывает сто самых популярных элементов за последнюю минуту, час, сутки и за всё время. Отдельно — топ по стране и по категории. Список обновляется не реже раза в минуту.

Считайте, что:

  • распределение крайне неравномерное: несколько элементов собирают заметную долю событий, а подавляющее большинство встречается один-два раза; сотое место за любое окно набирает не меньше 0,01 % всех событий окна;
  • страна — откуда пришло событие, категория — свойство элемента;
  • небольшая ошибка допустима: счёт в списке может отличаться от истинного до 5 % от счёта сотого места, порядок внутри сотни может слегка сдвигаться; пропуск настоящего лидера недопустим;
  • события приходят с задержкой до 10 минут и иногда дважды;
  • узлы перезапускают в обычном режиме эксплуатации.

Персонализация выдачи, ранжирование по сложной формуле вместо счёта, борьба с накруткой и отчёты за произвольный период в задачу не входят.

Требования

Функциональные 5

  • Топ-100 элементов по числу событий за окно
  • Окна: минута, час, сутки, всё время
  • Отдельный топ по стране и по категории
  • Обновление списка не реже раза в минуту
  • Опоздавшее до 10 минут событие попадает в окно своего времени

Нефункциональные 5

  • Не пропускается элемент, чей счёт за окно превышает счёт сотого места более чем на 5 %
  • Погрешность счёта в списке: не более 5 % от счёта сотого места
  • Задержка появления события в списке: не более 90 с
  • Чтение топа: 99-й процентиль задержки (p99) < 100 мс
  • Перезапуск узла: список снова актуален не позже чем через 10 минут

Задачи того же уровня

Решите задачу у доски

Интервьюер задаст вопросы по вашей схеме, проверка разберёт её по семи осям