27 сентября 2015 г.

Joker 2015

Еду в Питер 16-17 октября, на Джокер. Будет Шипилев, Паньгин, будет Мартин Томпсон (это который автор дизраптора и Aeron) — аж с двумя докладами (правда, про Аэрон не будет рассказывать, а жаль). А 18 числа будет University day — тот же Джокер, но для студентов, как я это понял. Но я уже не останусь, годы не те...

20 сентября 2015 г.

Немного тервера


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

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

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

Начал я с самой простой (==легко формализуемой) ситуации — когда данные отправляются источником через равные (и известные) интервалы времени. Это соответствует сценарию отправки пульса (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} }$$
Как видно, общий вид зависимости похож (убывающий хвост), но числа здесь уже совсем других порядков: вместо единиц при характерных значениях параметров получаются десятки тысяч (в единицах стандартных отклонений). Ну, неравенство Чебышева это самая общая оценка, которая только возможна в тервере, так что ничего удивительного в его расплывчатости нет. Но, увы, это означает, что хорошую, удобную оценку мы получаем лишь для более-менее периодических сигналов. Если вместо хартбитов мы возьмем какие-то обновления данных, то распределение их по времени легко может оказаться совсем не гауссовским, и иметь тяжелый хвост, и большую дисперсию. И тогда таймаут придется брать весьма не маленьким. Собственно, как я понимаю, это и есть математическое обоснование тому, зачем добавлять в потоки данных еще и хартбиты.

10 августа 2015 г.

Left-Right

Пару лет назад ребята из concurrency freaks опубликовали в c-i описание интересного алгоритма управления конкурентным доступом к произвольной структуре данных. Они назвали этот алгоритм Left-Right, и утверждали, что он позволяет реализовать blocking writes, но зато аж wait-free (population oblivios) reads. При этом писатели не блокируют читателей, хотя читатели блокируют писателей (но не блокируют друг друга). Это довольно-таки неплохой набор свойств, особенно учитывая, что защищаемя структура данных может быть любой. Сценарий с редко обновляемой, зато часто читаемой структурой данных очень типичен, и обычно в нем используется что-то вроде CopyOnWrite — очень простой и надежный алгоритм, но требующий аллокации. Здесь же аллокаций после инициализации нет вообще (в самом алгоритме — если защищаемая структура данных нуждается в аллокациях при выполнении над ней каких-то операций, то эти аллокации, конечно, никуда не исчезнут). Тогда у меня не дошли руки описать их алгоритм, зато дошли сейчас :)

Идея алгоритма (статья в pdf) довольно простая: мы заводим две копии (left & right) нужной нам структуры данных. Одна из копий всегда открыта для чтения, вторая, соответственно, спрятана от читателей. Поток, желающий выполнить операцию чтения должен просто определить, какая из копий открыта, и читать ее. Пишущий же поток захватывает глобальный монитор, и сначала модифицирует скрытую копию. Выполнив запись над скрытой копией писатель делает ее открытой для чтения, а бывшую открытую — скрывает, и повторяет свою запись теперь уже над ней. В итоге одна копия всегда свободна от записей, и ее можно безопасно читать, и одна копия всегда свобода от чтения, и ее можно безопасно модифицировать (под блокировкой, конечно — чтобы не конфликтовать с другими писателями), и после каждой операции записи копии меняются ролями.

Идея простая, но в реализации есть тонкости. Одномоментно сменить открытую копию просто — достаточно обычной volatile ссылки/индекса (и даже не нужно CAS-а, потому что запись и так происходит под блокировкой, и обновлять этот указатель может только один поток в каждый момент времени). Но после того, как мы перенаправили эту ссылку, и бывшая открытая копия стала закрытой — мы пока еще не можем утверждать, что нынешнюю закрытую копию никто не читает, ведь это только новые читатели пойдут по обновленной ссылке, а старые, которые начали чтение до смены ролей, все еще читают копию, которая сейчас уже закрыта. Значит, нам нужен какой-то механизм, позволяющий дождаться, пока все эти старички закончат читать. То есть нужно, чтобы потоки-читатели где-то отмечались “я сейчас читаю копию номер 1”, и чтобы писатель мог спросить “а есть ли хоть кто-то, кто читает копию номер 1?"

Реализация этого механизма регистрации читателей — это ключевая вещь в Left-Right, потому что от его эффективности и progress conditions прямо зависит эффективность и progress condition операций чтения — а неждущие чтения это, пожалуй, основная заявка всего алгоритма. В самом простейшем случае можно просто завести readersCount:AtomicInteger на каждую копию, и каждый читатель будет делать readersCount.incrementAndGet() перед началом чтения, и .decrementAndGet() после окончания, и если readersCount.get() == 0 значит активных читателей не осталось. Этот способ регистрации читателей самый простой, и самый компактный по памяти — но он мягко говоря не очень хорошо масштабируется с увеличением количества читателей, ведь все читатели будут конкурировать за обновление одного участка памяти (true sharing).

Ситуацию можно улучшить, если начать дробить единый счетчик на несколько более мелких: каждый поток-читатель приписан к какому-то суб-счетчику (не обязательно навсегда к одному и тому же, кстати), и инкрементит/декрементит его, а поток-писатель должен тогда будет обойти все суб-счетчики, и просуммировать их значения, чтобы получить итоговую сумму (отдельные суб-счетчики, конечно, нужно хорошенько изолировать друг от друга padding-ом, чтобы не налететь сходу теперь уже на false sharing). В пределе, если на каждый поток-читатель выделить свой собственный суб-счетчик, мы получим полное отсутствие конкуренции за запись (технически нужно еще обеспокоиться еще отсутствием false sharing) — по-сути записи будут чисто локальными для каждого из потоков, и тогда даже CAS/atomicAdd нам не нужно, мы можем обновлять волатильный локальный счетчик обычным инкрементом/декрементом (очень изящную реализацию на базе односвязного списка, слабых ссылок, и thread local-ов можно посмотреть здесь). И значит мы получим-таки заявленное свойство wait-free population oblivios. По цене ~64+ байт на каждый читающий поток (padding + сам счетчик + дополнительные поля — и не забываем, что пишущий поток еще будет обязан все эти локальные счетчики обойти и просуммировать)

(Небезызвестный LongAdder из последних версий jdk использует похожий подход, но он всего лишь lock-free. Почему? Потому что пытается балансировать между скоростью и потреблением памяти — если на каждый поток сразу по 64+ байт выделять — никакого кэша не хватит. Так что LongAdder подстраивает количество счетчиков под реальную нагрузку — он начинает с одного счетчика (общего для всех потоков), который обновляется через CAS. Если неудачных CAS-ов становится много — это значит, что за счетчик идет слишком большая конкуренция, и LongAdder увеличивает количество суб-счетчиков, стараясь равномерно распределять потоки между ними. Покуда неудачных CAS-ов все еще много — количество счетчиков еще увеличивается, пока их не окажется столько, чтобы за каждый конкретный счетчик конкуренция была ниже некого предела. Очень изящное, эффективное, и гораздо более универсальное решение — но вся эта машинерия динамической перестройки, увы, уже не вписывается в wait-free)

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

Довольно очевидно, что алгоритм близок идейно к CopyOnWrite, только в CoW количество копий не ограничено, а за количеством читателей следит GC — пока на какую-то из копий хоть из одного потока есть ссылка, эта копия считается занятой, как только ни одной ссылки не остается — копию подбирает GC, и ее память заново можно использовать для аллокации. За эту простоту приходится платить — алгоритмы определения достижимости у GC обходятся гораздо дороже по CPU, чем смена читаемой копии в LR, да к тому же теряется детерминированность. Плюс вместо дублирования одной конкретной записи мы вынуждены при реаллокации копировать все содержимое структуры данных целиком.

Что в алгоритме LR еще интересного? Интересно то, что его основной недостаток — блокировка для писателей — не актуален, если писатель у нас один. Поскольку блокировка нужна только для разруливания конфликтов между писателями, то в случае одного писателя ее можно просто выкинуть. И мы получаем алгоритм с wait-free писателем, и wait-free (или lock-free если мы пожадничаем на память для счетчиков) читателями. Хотя стоп, писателю же все равно придется ждать завершения всех чтений? Да, никакого wait-free не получится, писатель все равно остается блокирующимся, просто монитор захватывать в этом случае не нужно.

Второй интересный аспект это пакетная запись. Если нам не принципиально предоставлять читателям свежую версию максимально быстро — мы можем переключать копии между открытой на закрытой не после каждой записи, а, скажем, после какого-то их числа, или по явной команде, типа commit/flush. И тогда высокая стоимость записей может быть амортизирована на всю пачку. В том числе и блокировку можно брать лишь однажды и на всю пачку (или вообще не брать — если писатель один-единственный). От необходимости выполнять каждую запись дважды это нас не избавит, но все остальные накладные расходы можно сильно размазать.

Третья идея — а что, если копий сделать больше одной? В пределе неограниченного количества копий мы приходим к классическому CopyOnWrite + GC, но что если копий все-таки ограниченное количество? В оригинальной статье этот вариант не рассматривается, но насколько я вижу, это вполне можно реализовать. Здесь есть интересный вариант: мы можем, как и в оригинальном LR применять каждую запись N раз, к каждой копии. А можем вместо этого при модификации копировать все содержимое самой свежей копии (текущей читаемой) в самую старую (будущую читаемую), и применять текущую запись уже поверх. (Очевидно, что при большом N этот способ рано или поздно станет более эффективным).

То, что у нас здесь получится — это натуральный CopyOnWrite, только без аллокации и GC, и с ограниченным набором копий. В чем его потенциальные преимущества? По сравнению с обычным CoW нет постоянной реаллокации (но все же есть копирование). А вот по сравнению с LR преимущество в том, что для выполнения записи нам не нужно дожидаться завершения всех чтений над только-что-переставшей-быть-открытой копией — потому что сейчас нам в нее ничего писать не нужно. Пишем (копируем свежее состояние + применяем текущую запись) мы в самую последнюю (самую дальнюю от текущей) копию, и именно она должна быть свободна от читателей. Но поскольку эта дальняя копия была открытой для чтения уже довольно давно, то вероятность, что ее все еще кто-то читает (т.е. есть кого ждать) довольно мала, и ее можно уменьшать далее увеличивая количество копий.

Мы получаем такую версионную структуру данных, которая одновременно содержит черты CoW, кольцевого буфера (ну, потому что копии организованы натурально в виде кольцевого буфера), и LR. Без аллокаций, с wait-free чтением (если не жалко по 64+ байт кэша на каждый читающий поток потратить), и с блокирующейся записью — но при этом вероятность ожидания на записи можно регулировать увеличивая количество копий. Интересная штука, правда, очень сложно поверить, что эту структуру данных еще никто не придумал :)