Немного тервера, или зачем нужны хартбиты

Вот допустим у меня есть система А, которая потребляет данные из системы Б. И тут с системой Б что-то произошло — свет отключили, метеорит упал, староверы вырезали кусок транссибирского кабеля на цветной лом, старший разработчик ушел в запой, предварительно выключив главный секретный рубильник — и данные поступать перестали. Допустим, у меня даже есть План Б на этот случай — ну там, накрыться простыней и медленно ползти в сторону кладбища, например. Или скучно и банально переключиться на резервного поставщика данных. Так вот вопрос: как бы мне пораньше-то узнать, что все плохо, и пора приводить в действие План Б?

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

Такое гадание на кофейной гуще заставляет меня немного кривить лицо, так что в какой-то момент я решил призвать на помощь математику, и прояснить для себя, можно ли сделать оценки не с потолка, и какие. Сколько времени достаточно ждать, чтобы сделать вывод о потере доступности удаленной системы с такой-то степенью достоверности?

Начал я с самой простой (==легко формализуемой) ситуации — когда данные отправляются источником через равные (и известные) интервалы времени. Это соответствует сценарию отправки пульса (heartbeats). Самая первая статистическая модель, которая приходит в голову, выглядит так: с интервалом времени $$T_h$$ к нам в систему отправляют хартбиты. Как всегда, на длинном пути от теории к практике находится большое число разных помех, каждая из которых норовит отклонить реальный период получения от идеального платоновского T. Поэтому приход хартбита мы можем моделировать как случайное событие. Если в момент T=0 мы наблюдали это случайное событие (==получили хартбит), то время возникновения следующего такого события — случайная величина. Как она распределена мы точно не знаем, но в качестве гипотезы первого порядка мы можем принять, что интервал интервал между хартбитами распределен по Гауссу, со средним значением равным $$T_h$$, и какой-то там дисперсией $$\sigma_h$$

Но иногда в системе отправки и доставки хартбитов происходят неисправности. Неисправность — это когда что-то случилось с отправляющей системой, или с сетью, или с нашим сетевым стеком, или еще где — но очередного хартбита нет, и не будет. Неисправности тоже случайные события. Как они распределены во времени нам тоже априори не известно, но в качестве гипотезы первого порядка мы можем принять, что они возникают случайно, независимо и равномерно, в среднем раз в $$T_f$$ — то есть вероятность события неисправности на малом интервале $$[t..t+dt]$$ равна просто $${dt \over T_f}$$.

Тогда, если на принимающей стороне с момента получения последнего хартбита прошло уже время T, а очередного хартбита мы все еще не наблюдаем, то это могло произойти по двум (предположительно, независимым) причинам:

1. или хартбит еще не пришел (нам просто в этот раз так повезло, и из случайного распределения интервалов между хартбитами нам в этот раз выпало какое-то значение, бОльшее чем T)
2. или отправляющая система уже сдохла (на отрезке [0..T] произошла неисправность)

Нам нужно как раз понять, с какой вероятностью истинным объяснением задержки будет №2. Несложно видеть, что это будет условная вероятность неисправности при отсутствии хартбита к моменту T: P(неисправность где-то на [0..T] | хартбит не получен в течении T)

$$ = \frac{P(failure \in [0..T])}{P(T_{hb} > T)+P(failure \in [0..T])} = \frac{P(2)}{P(1)+P(2)}$$

То есть нам нужно посчитать две вероятности: вероятность того, что очередной интервал между хартбитами будет >T “сам по себе” (т.е. только из-за случайных задержек), и вероятность того, что на отрезке [0..T] произошла неисправность.

Какова вероятность того, что неисправность случилась на отрезке [0..T]? Проще считать от обратного: вероятность того, что неисправность случилась на отрезке длиной dt равна $$\frac{dt}{T_f}$$. Вероятность того, что неисправность там не случилась $$1 - \frac{dt}{T_f}$$. Вероятность того, что неисправность не случилась нигде на отрезке [0..T] $$ = \left(1-\frac{dt}{T_f}\right)^\frac{T}{dt} \rightarrow e^{-\frac{T}{T_f}}$$, вероятность того, что неисправность случилась хоть где-то на отрезке [0..T] хоть раз $$1 - e^{-\frac{T}{T_f}}$$ (узнавшие пуассоновский процесс эту формулу могли просто вспомнитьподсмотреть в википедии, но я люблю повыпендриваться)

Какова вероятность того, что интервал между хартбитами (нормально распределенная случайная величина $$N_{T_h,\sigma}$$) случайно окажется > T сам по себе? Эта вероятность равна

$$\int\limits_{T}^{\infty}{N_{T_h,\sigma}(t) \, dt = 1-\int\limits_{-\infty}^{T}{ \frac{1}{\sqrt{2\pi}\sigma}e^{-\frac{(t-T_h)^2}{2\sigma^2}} \, dt} = \frac{1}{2}erfc\left( \frac{T_h-T}{\sqrt{2}\sigma} \right) = Q\left( \frac{T-T_h}{\sigma} \right)$$

($$Q(x)$$ это объем хвоста нормального распределения от x и до беспредельности. В русских источниках я такое обозначение не встречал, но здесь мне оно оказалось очень к месту, поэтому дальше буду им пользоваться) Дальше все просто: формулы подставляем в формулы, и получаем уравнение, в котором P(2) выступает в роли задаваемого параметра (какую степень достоверности определения сбоев желаете: 90%, 95%, 99.99%?), а T — тем самым таймаутом, который позволит обеспечить нужную степень достоверности.

Вот что получается в итоге ($$x = \frac{T-T_h}{\sigma}$$, другими словами — сколько стандартных отклонений от среднего):

$$\frac{1 - \frac{1}{2} erfc\left(-\frac{x}{\sqrt{2}}\right)}{1 - e^{\frac{- (T_h+\sigma\,x)}{T_f}}} = \left(\frac{1}{P}-1\right)$$

На этом месте я несколько застопорился: в элементарных функциях это уравнение не решается, и даже после пары упрощений-приближений не решается все равно. В числах легко решается любой системой компьютерной математики, но хочется же понять сам вид зависимости $$T = f(T_h, T_f, \sigma, P)$$, хотя бы в приближенном, асимптотическом виде. Поигравшись с неделю с численными решениями и графиками я нашел, что с этим можно сделать.

Идея выглядит так: если мы преобразуем это уравнение к виду $$x = f(x)$$, подходящему для метода итераций, то легко показать, что $$f(x)$$ здесь будет иметь очень маленькую производную (при тех значениях параметров, которые нам интересны — $$ T_h, \sigma << T_f$$). А метод простых итераций сходится (если сходится) примерно со скоростью $$|x_n-x| \leq |f(\xi)'|^k|x_0-x| $$. То есть, имея достаточно малую производную $$f(\xi)' < 10^{-3}-10^{-6}$$ можно сделать вообще одну-единственную итерацию, и получить вполне пристойное приближение вида $$x = f(x_0=1)$$. По-сути это формализация примитивного метода последовательных приближений: какова вероятность возникновения неисправности на одном периоде между хартбитами? А насколько должен задержаться хартбит, чтобы вероятность его случайной задержки стала меньше, чем эта вероятность неисправности? — мы могли бы повторить эту процедуру несколько раз, но оказывается, что уже на первом же шаге мы уже почти сойдемся, потому что хвост нормального распределения убывает очень быстро, а распределение Пуассона "набирает вес" гораздо медленнее. Этого все еще недостаточно, потому что $$f(x)$$ здесь все равно получается невыразимая в элементарных функциях, поэтому придется использовать известные асимптотические ограничения на объем хвоста нормального распределения $$Q(x) < e^{-x^2/2}$$. В конечном счете, получается такое приближенное решение:

$$x \simeq \sqrt{ 2\,ln\left( 2\left(\frac{P}{1-P}\right)\frac{T_f}{T_h+\sigma} \right) }$$

Здесь уже достаточно ясно видно, что x зависит от параметров очень слабо — изменение аргументов в пределах 6 порядков изменяет результат в пределах 20-25 процентов (ну еще бы, корень, да из логарифма) При разумных значениях параметров получим x = 4-8. То есть в первом приближении можно просто брать таймаут $$T = T_h + 6..8\sigma$$, и не заморачиваться.

...Еще раз, что у нас получилось: в числителе у нас стоит вес (вероятность) хвоста распределения вероятности последовательных времен прихода данных $$P_{data}(t > T)$$. В знаменателе же "голова" (ну, что у нас с другой стороны от хвоста?) распределения вероятностей времен возникновения неисправностей $$P_f(t < T)$$.

По мере того, как мы двигаем T вправо, голова у нас тяжелеет (вероятность возникновения неисправности на интервале растет по мере роста интервала), и стремится к 1, а хвост тает, и стремится к 0 — поэтому в какой-то момент голова обязательно станет тяжелее хвоста в любое заданное число раз. То есть это уравнение всегда имеет решение. Можно подставлять сюда разные распределения, и смотреть что получится — но вряд ли это будет проще, чем с нормальным распределением.

А вот можем ли мы сказать что-то про решение без предположений о конкретном виде распределения интервалов между данными? Ну, для большого класса распределений с легкими хвостами верна оценка $$P([x-|x|] \geq k*\sigma) \leq exp(-x^2/2)$$ — та самая, которую мы уже использовали для нормального распределения, так что полученный ответ можно считать подходящим и для распределений похожих на нормальное.

С другой стороны, самая общая оценка, верная вообще для любого распределения с конечным средним и дисперсией — это неравенство Чебышева $$P\Big(\frac{x-|x|}{\sigma} \geq k\Big) \leq \frac{1}{k^2}$$

Используя его можно получить такую оценку
$$\frac{1}{x^2} \geq \Big(\frac{1}{P}-1\Big)\frac{T_h + \sigma x}{T_f} \rightarrow x \leq \sqrt{ \frac{P}{1-P} \frac{T_f}{T_h+\sigma x} } \rightarrow x \leq \sqrt{ \frac{P}{1-P} \frac{T_f}{T_h} }$$
Как видно, общий вид зависимости похож (убывающий хвост), но числа здесь уже совсем других порядков: вместо единиц при характерных значениях параметров получаются десятки тысяч (в единицах стандартных отклонений). Ну, неравенство Чебышева это самая общая оценка, которая только возможна в тервере, так что ничего удивительного в его расплывчатости нет. Но, увы, это означает, что хорошую, удобную оценку мы получаем лишь для более-менее периодических сигналов. Если вместо хартбитов мы возьмем какие-то обновления данных, то распределение их по времени легко может оказаться совсем не гауссовским, и иметь тяжелый хвост, и большую дисперсию. И тогда таймаут придется брать весьма не маленьким. Собственно, как я понимаю, это и есть математическое обоснование тому, зачем добавлять в потоки данных еще и хартбиты.