Интерактивный разбор объясняет reservoir sampling, или резервуарную выборку. Алгоритм держит
k элементов. Для элемента с номером n шанс попасть в массив равен k/n; при выборе он заменяет один из сохранённых случайным образом. Поэтому каждый элемент потока имеет равный шанс остаться в результате.Механизм показан на картах, а затем на сервисе сбора логов. При
k=5 сервис хранит не больше пяти сообщений и раз в секунду отправляет выборку: при потоке до пяти сообщений сохраняет все, а во время всплеска выбирает пять без преимущества у первых событий. Цена предсказуемой памяти: логи поступают пачками, а не непрерывно.Разбор с интерактивными схемами стоит прочитать разработчикам потоковых систем. Он выводит математику без сложных обозначений и даёт простую реализацию. Для логов разной ценности есть взвешенный вариант алгоритма.