Бутстреп на миллионах пользователей
Вопрос
Платформа экспериментов должна считать бутстреп-интервалы для сотен метрик на десятках миллионов пользователей. Как сделать это быстро?
Попробуйте сами
Ответьте вслух за 2 минуты, как на собесе. Потом сверьтесь с тезисами: что прозвучало, а что нет.
Показать ответ и разбор
Коротко
Что должно прозвучать в ответе
Классический ресэмплинг дорог: B × n операций на метрику
Пуассоновский бутстреп: вес Poisson(1) на пользователя, считается за проход и параллельно
Бакетизация: пользователи в K бакетов по хешу, метрики по бакетам, бутстреп или t-тест по бакетам
Для средних и долей формулы и дельта-метод вместо бутстрепа
Ratio-метрики: суммы числителя и знаменателя по пользователю
Фиксированные seed для воспроизводимости
Что могут спросить следом
- Сколько бакетов брать и чем это рискует?
- Когда бутстреп всё-таки нужен?
Разбор
Сначала спрошу, где бутстреп действительно нужен: для средних, долей и ratio-метрик есть формулы и дельта-метод, они на порядки дешевле и дают тот же результат на больших выборках. Бутстреп оставляю для квантилей и сложных метрик. Чтобы он был дешёвым, есть два приёма. Пуассоновский бутстреп: каждому пользователю на каждой итерации даю вес из Пуассона(1), это приближает ресэмплинг с возвращением, генерируется независимо на каждой строке и хорошо параллелится в Spark или ClickHouse. Бакетизация: делю пользователей по хешу на, скажем, 100-1000 бакетов, считаю метрику по бакету и дальше работаю с бакетами как с наблюдениями. Предварительно агрегирую данные до пользователя: суммы числителя и знаменателя. И фиксирую seed, чтобы цифры не прыгали между пересчётами.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.