Когда математика встречает бэкенд, или Как рассчитать RPS на поллинговую ручку / Хабр

Загадка: во сколько раз увеличится RPS на ручку поллинга, если уменьшить интервал поллинга с 5 минут до 2?

Ответ: в 2,5 раза!

Привет! Меня зовут Стёпа, и я разработчик в Яндекс Go. Я хочу поделиться тем, как математика может встречаться в самых неожиданных местах — даже в такой рутинной задаче, как настройка интервала поллинга. В статье я рассмотрю модельный пример, который встречался каждому разработчику, и просчитаю его с математической точки зрения, использовав базовые факты из теории вероятностей и статистики.

Постановка задачи

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

Для примера возьмём интервал в 5 минут. Таких клиентов могут быть миллионы (MAU Яндекс Go — 58,4 млн пользователей), то есть на ручке обновления постоянно держится заметный показатель RPS (Requests per Second — число, которое показывает, сколько запросов приходит на сервер в секунду). Возникает вопрос: а как изменится RPS на ручке, если поставить интервал поллинга 2 минуты?

Можно подумать, что ответ тривиален: раньше клиенты ходили раз в 5 минут, а потом стали ходить в 2,5 раза чаще. Значит, количество запросов возросло в 2,5 раза, поэтому количество запросов на сервере увеличится в 2,5 раза. Всё, казалось бы, просто. Так же подумал и я, планируя ресурсы для раскатки проекта. Но на масштабе в миллионы пользователей это сыграло со мной злую шутку, ведь ответ оказался значительно сложнее и приводил к совсем другому результату, который в несколько раз отличался от ожидаемого!

Спойлер: правильный ответ зависит от параметров и выглядит так:

$RPS(\tau) = r_0 \cdot \frac{exp(\lambda \tau)}{exp(\lambda \tau) - 1}$

Э-э-э-эксперименты

В приложениях которые обеспечивают работу сервиса такси (это приложение Яндекс Go, через которое заказывают такси пассажиры, и приложение Яндекс Про, через которое водители принимают заказы) работает механизм фоновой сетевой диагностики. Приложения раз в 5 минут отправляют технические данные на бэкенд, чтобы удостовериться в доступности сети. Суммарная нагрузка на эту ручку в пике может достигать 5 000 RPS. Далее на примере этих условий и рассмотрим нашу задачу.

Моей целью было ускорить сетевую диагностику, поэтому я хотел уменьшить интервал поллинга до 30 секунд. Надо было посчитать, сколько ресурсов стоит докинуть сервису, чтобы выдерживать повышенный RPS. Посчитав, что суммарно будет приходить в 10 раз больше запросов (5 минут: 30 секунд = 10), я заложил ресурсов на 50 000 RPS, добавив сверху ещё 25 000 RPS на отказоустойчивость и потерю части подов (микросервисы Такси живут в трёх дата‑центрах, при этом инфраструктура полностью выдерживает отказ одного из них). Сказано — сделано, ~~протестировано~~ и задеплоено в прод.

Переключаем рубильник и видим, что после изменения интервала поллинга RPS вырос на ручке не до 50 000, а до 25 000. Масштаб довольно заметный: потерялось почти 25 000 запросов в секунду! Естественно, при таких потерях всё откатывается и создаётся инцидент. Но каково было наше удивление, когда после проверки всех балансеров мы не заметили ни деградации, ни технической потери запросов ни на одном из них. Кажется, что клиенты просто перестали ходить в наш бэкенд, но по бизнес‑метрикам количество клиентов на линии осталось прежним.

Хотя задача не требовала срочного решения, аномальное изменение трафика вызывало у меня огромный интерес. Где‑то после недели раздумий и попыток найти ответ я наконец сдался и решил попробовать поменять интервал снова, но в этот раз менее радикально — до 2 минут. Ожидал получить 5: 2 × 5 000 = 12 500 RPS, но на практике после переключения осталось лишь 8 500 RPS. Благо, ручка не критичная — экспериментируем дальше и получаем такую таблицу:

И тут начинается самое интересное — математика!

Построение математической модели

Понятно, что в тривиальной модели рассуждений (интервал в X раз меньше, значит, трафика в X раз больше) зависимость между интервалом поллинга и RPS линейная. Однако если визуализировать результаты наших экспериментов, то результат будет совсем не похож на линию:

С таким характером зависимости становится ясно: зависимость точно не линейная.

К тому же на этом этапе становится понятно, что краевым случаям модель не соответствует: если мы выкрутим интервал поллинга в бесконечность, то RPS на ручке будет ненулевым — останется стабильный фон от клиентов, которые заходят в приложение и делают первый поллинговый запрос (а только потом начинают ждать «бесконечность»).

Как же можно количественно описать наблюдаемую нами зависимость? Ответ на этот вопрос неочевидный, и выбор модели, пожалуй, самая нетривиальная часть этой статьи. Если вы хотите догадаться самостоятельно, то попробуйте не подсматривать в решение ниже — все данные у вас уже есть!

Решение

Заметим, что поведение пользователей в приложении можно считать независимым: действия одного пользователя в среднем не влияют на то, как будет пользоваться приложением другой человек. Каждый из них использует приложения для своих нужд: заказать такси, взять заряд или получить доставку еды. Поэтому на больших данных количество RPS линейно растёт с количеством пользователей: если пользователи удваиваются, то и RPS тоже (в этом мы также убедились на этапе раскатки проекта). Поэтому, чтобы найти ответ, имеет смысл посмотреть внимательнее на паттерн использования одним пользователем. Для количественного анализа будем отвечать на вопрос «Какова „вероятность“ того, что пользователь вышел из приложения в момент времени t?». Интуитивно ясно, что:

основная «вероятность» должна быть сосредоточена в первом часу: пользователь заказал такси, встретился с водителем и вышел из приложения;
на бесконечности «вероятность» должна стремиться к нулю: никто не сидит в приложении бесконечно долго;
«вероятность» того, что пользователь выйдет из приложения, больше нуля только при t > 0;
после первых 5–10 минут «вероятность» должна убывать: короткие поездки встречаются чаще длинных.

Этим четырём свойствам соответствует широко применяемое в математике экспоненциальное распределение. Оно немного не подходит нам, когда время пребывания пользователя в приложении только начинает свой отсчет и почти равно нулю, ведь там «вероятность» уменьшается, однако для построения MVP нам этого будет вполне достаточно, а более точную модель мы рассмотрим ниже.

Технически, само распределение описывается плотностью вероятности:

$\rho(x) = \lambda \cdot e^{-\lambda x}, \quad x \geq 0$

где $\lambda > 0$ — параметр распределения (интенсивность). Ответ на вопрос «Какова „вероятность“ того, что пользователь вышел из приложения до момента времени T?» определяется функцией распределения.

$F(T) = \int_0^T \rho(x) dx = \int_0^T \lambda \cdot e^{-\lambda x} dx = 1 - e^{-\lambda T}, \quad T \geq 0$

Поэтому будем считать, что время жизни сессии пользователя распределено экспоненциально с параметром $\lambda$ , то есть:

$P(\xi \leq T) = F(T) = 1 - e^{-\lambda T}$

Этого будет более чем достаточно, чтобы описать наблюдаемую зависимость.

Для понимания приведу два графика:

Научимся находить RPS на ручке поллинга в зависимости от параметра распределения, а потом, зная ��езультаты наблюдений, найдём параметр для нашего случая.

Чтобы оценить количество клиентов, которые приходят в ручку без повторного поллинга, я сделал отдельное упражнение — поставил интервал поллинга этой ручки 2 часа. В процессе эксперимента получил, что RPS на ручке поллинга со временем стал равен 3200. Отсюда делаем вывод, что количество уникальных клиентов, которые ходили в ручку хотя бы раз со старта приложения, — 2 000 клиентов/сек. Любопытно, что это в точности повторяет RPS ручки входа пользователей в приложение.

Зафиксируем этот параметр как =3200.

То есть за каждое временное окно поллинга мы работаем в среднем с 3200 пользователями. Будем считать, что время, проведённое пользователем в приложении, — случайная величина, распределённая экспоненциально со свободным параметром.

Таким образом, мы имеем выборку $\xi_1$ , $\xi_2$ ,..., $\xi_r$ из случайных величин, распределённых экспоненциально. Как тогда оценить RPS на ручке, зная параметры распределения? Очень просто: посчитать, сколько в среднем ходит каждый клиент, то есть посчитать математическое ожидание случайной величины, равной

$\left\lfloor \frac{\xi_i}{\tau} \right\rfloor + 1$ где $\tau$ — интервал поллинга, $\left\lfloor a \right\rfloor$ — целая часть числа a.

Используя базовую формулу подсчёта математического ожидания через его плотность, получаем:

$\mathbb{E}\langle \left\lfloor \frac{\xi_i}{\tau} \right\rfloor + 1 \rangle = \int_0^\infty \left( \left\lfloor \frac{t}{\tau} \right\rfloor + 1 \right)\cdot \lambda \cdot exp(-\lambda \cdot t) dt$

То есть чтобы получить ответ на наш вопрос, нам достаточно посчитать интеграл с параметром и найти коэффициент $\lambda$ для нашего случая. Интеграл берётся не менее красиво, образуя «лестницу» из интегралов экспоненты:

$\mathbb{E}\langle \left\lfloor \frac{\xi_i}{\tau} \right\rfloor + 1 \rangle = \int_0^\infty \left( \left\lfloor \frac{t}{\tau} \right\rfloor + 1 \right)\cdot \lambda \cdot exp(-\lambda \cdot t) dt = \int_0^\tau \lambda exp(-\lambda t)dt + 2 \cdot \int_\tau^{2 \tau} \lambda exp(-\lambda t)dt + 3 \cdot \int_{2 \tau}^{3 \tau} \lambda exp(-\lambda t)dt + \cdots.$

Зная, что:

$\int_a^b exp(-\lambda \cdot t) dt = - \lambda^{-1} exp(-\lambda t)\Big|_a^b = \lambda^{-1} \cdot (exp(-\lambda a) - exp(-\lambda b))$

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

$\mathbb{E}\left( \left\lfloor \frac{\xi_i}{\tau} \right\rfloor + 1 \right) = \int_0^\infty \left( \left\lfloor \frac{t}{\tau} \right\rfloor + 1 \right)\cdot \lambda \cdot exp(-\lambda \cdot t) dt = \sum_{i=1}^{\infty} exp(-\lambda i \tau) = \frac{exp(\lambda \tau)}{exp(\lambda \tau) - 1}$

Поскольку всего пользователей, включающих приложение за единицу времени, равно , то RPS как функция от $(\lambda, \tau)$ представляется в виде:

$RPS(\lambda, \tau) = r_0 \cdot \frac{exp(\lambda \tau)}{exp(\lambda \tau) - 1}$

Ура, теперь у нас есть теоретически полученный результат для нашей модели!

Зная эту зависимость и экспериментальные данные, оценим параметр $\lambda$ . С помощью эмпирической зависимости RPS от интервала поллинга, подберём оптимальное значение параметра $\lambda$ . В этом месте можно углубиться в теорию сравнения оценок, но для упрощения будем считать, что оптимальная оценка параметра $\lambda$ равна

$min_{\lambda_0 \in \mathbb{R}} \sum_{i = 0}^{n}\frac{|RPS(\lambda_0, \tau_i) - RPS(\tau_i)|}{RPS(\lambda_0, \tau_i)},$

где n = 10 — количество точек в эксперименте (7200 не берём), $RPS(\tau_i)$ — результат эксперимента для фиксированного $(\tau_i)$ .

r_0 = 3200

def RPS_experimental(tau):
    return experiments[tau]
def RPS_theoretical(lambd, tau):
    return r_0 * (math.exp(lambd * tau) / (math.exp(lambd * tau) - 1))

best_lambd, best_difference = -1, 10 ** 10

for lambd in np.arange(0.0001, 0.01, 0.0001):
    current_difference = 0


    # calculating sum
    for experiment_tau in experiments.keys():
        v1 = RPS_experimental(experiment_tau)
        v2 = RPS_theoretical(lambd, experiment_tau)
        current_difference += abs(v1 - v2) / v2
    if current_difference < best_difference:
        best_lambd, best_difference = lambd, current_differenceprint(f'lambd={best_lambd}')

print(f'lambd={best_lambd}')

lambd=0.0043

Проверим, насколько хорошо наши теоретические результаты соответствуют модели, поместив их на график:

Видим, что полученная оценка довольно хорошо описывает распределение экспериментальных данных. Таким образом, значение RPS на ручке поллинга можно вычислить как:

$RPS(\tau) = r_0 \cdot \frac{exp(\lambda \tau)}{exp(\lambda \tau) - 1},$

где = 3200, $\lambda = 2,3\cdot 10^{-3}$ , $\tau$ — интервал поллинга в секундах.

Увеличиваем точность модели

В модели выше мы предполагали, что случайные величины распределены экспоненциально. В более общем виде это допущение можно обобщить, рассмотрев гамма‑распределение, которое включает экспоненциальное как частный случай. Таким образом, мы не ограничим общность и получим возможность более точно описать искомое распределение.

Проблема заключается в том, что в этом случае интегрирование будет проводиться сложнее, — придётся суммировать гамма‑функции. Поэтому здесь разумнее перейти от прямого суммирования к численным методам и использовать метод Монте‑Карло.

Идея простая: мы генерируем случайные величины с нужными параметрами, пропускаем их через тот же алгоритм (делим нацело на интервал поллинга и прибавляем единицу), а затем считаем среднее значение. Такой подход позволяет работать даже с довольно сложными распределениями независимо от их формы:

def RPS_theoretical(shape, scale, t):
    sample = np.random.gamma(shape=shape, scale=scale, size=100000)
    sample = (sample // t).astype(int) + 1
    return np.mean(sample) * r_0


best_shape, best_scale, best_difference = -1, -1, 10 ** 10


for shape in np.arange(3, 15, 1):
    for scale in np.arange(10, 40, 1):
        current_difference = 0
        for experiment in experiments.keys():
            v1 = RPS_experimental(experiment)
            v2 = RPS_theoretical(shape, scale, experiment)
            current_difference += (abs(v1 - v2) / v2) ** 2


        if current_difference < best_difference:
            best_shape, best_scale, best_difference = shape, scale, c


print(f'shape={best_shape}')
print(f'scale={best_scale}')

shape=7
scale=37

Интерпретация результатов

Зная итоговые параметры распределения, можно легко понять, сколько времени в среднем пользователь проводит в приложении. Для этого достаточно построить график плотности распределения с соответствующими параметрами.

Чем больше значение графика в определённой точке Х, тем больше «вероятность» того, что пользователь выйдет из приложения в этот момент времени.

Видно, что первые несколько минут пользователи почти не выходят из приложения Яндекс Go. Пик выхода приходится на 4–12 минут — скорее всего, пользователи за это время успевают заказать такси и закрыть приложение. Стоит отметить, что гамма‑распределение, как и экспоненциальное, имеет только один «горб» — то есть один пик вероятности.

В реальности же распределение времени использования приложения может быть более сложным: например, могут быть отдельные пики для коротких поездок (5–10 минут), средних (15–30 минут) и длинных (более часа).

Для более точного моделирования можно использовать смесь распределений или другие многомодальные модели, однако для практических целей оценки RPS на поллинговой ручке гамма‑распределение оказывается вполне достаточным.

Также достаточно интересно сравнить графики приложений Яндекс Go (для пассажиров) и Яндекс Про (для водителей). Если провести аналогичные расчёты для обоих приложений, то можно увидеть, что вероятность выхода из приложения у водителей «размазана» на весь период работы (единицы часов на линии) и представляет собой почти прямую линию, в то время как в приложении для клиентов есть ярко выраженный пик выхода через несколько минут. Это ещё раз подтверждает валидность модели и позволяет проводить полезную аналитику, используя самые неожиданные данные.

Заключение

Итак, мы увидели, что методы математического моделирования позволяют эффективно решать практические задачи на примере планирования ресурсов для модели поллинга.

Ключевые практические выводы:

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

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

Часто мы не замечаем математику, потому что она скрыта за абстракциями библиотек и рутинных инструментов. Но когда нужно оптимизировать производительность, спланировать ресурсы или понять поведение системы на масштабе — без математического моделирования не обойтись. Попробуйте задуматься — и вы увидите, что даже в вашем проекте есть много мест для применения математики!

Когда математика встречает бэкенд, или Как рассчитать RPS на поллинговую ручку