Что такое нестабильность latency (jitter), и как с нею бороться

При написании low-latency приложения мы боремся не только за low-latency, но и за стабильность этой low-latency.

Предсказуемость latency

Запустим наше приложение и сделаем замер latency какой-то операции. Замер сделаем, скажем, в течение десяти минут. За это время будет сделано, предположим, миллион вызовов данной операции. Так мы получим миллион значений. Отобразим их на графике. График нам покажет, что большей частью значение latency колеблется в диапазоне 40 мсек +/-10 мсек. Предположим, что для нашего конкретного случая это значение latency приемлемо.

Но на графике мы также видим отрезки времени, когда latency подскакивает до 1000 мсек, держится так некоторое время, а потом снова снижается до приемлемых 40 мсек. Если бы таких всплесков на графике не было, мы могли бы говорить о предсказуемости latency, т.е. о том, что исполнение данной операции с большой долей вероятности займет 40 мсек с небольшой погрешностью.

Или например вот такой график, где в среднем значение latency колеблется вокруг 40 мсек, но постоянно появляются случайные всплески до 1000 мсек, а то и до 3000 мсек.

Это так называемый «дребезг» (jitter). Данный график наглядно показывает нам, что latency в нашем приложении хоть и низкая, но нестабильная. Более того, она нестабильна непредсказуемо! Это та самая ситуация, когда мы не можем с уверенностью предсказать, сколько времени займет выполнение определенной операции: 40 мсек или все же 3000 мсек. Чем больше таких всплесков, тем непредсказуемее, нестабильнее latency. Причем нестабильность эта может выражаться и в обратную сторону: latency может неожиданно снижаться, а потом возвращаться к среднему значению, а потом увеличиваться, снова возвращаясь к среднему значению.

Хуже всего, когда latency настолько непредсказуемая, что каждый вызов одной и той же операции даёт разное, нестабильное время выполнения. На графике ниже представлен как раз такой случай. По графику невозможно с уверенностью предсказать, то ли вызов функции будет завешен через 3 миллисекунды, то ли через 1000 миллисекунд.

Поэтому при написании low-latency приложения мы в первую очередь боремся за low-latency, и во-вторую очередь — за стабильность этой latency, за ее предсказуемость, за удаление «дребезга».

Что же может быть причиной такого дребезга в Java-приложении? Вот несколько возможных причин:

Сборщик мусора

Сборщик мусора является в Java-приложениях главной причиной задержки и непредсказуемых дребезгов. Так как сборка мусора осуществляется автоматически и напрямую управлять сборкой мусора в JVM у нас нет возможности, мы можем хотя бы попытаться снизить издержки работы сборщика мусора: например,

• сделать так, чтоб он реже вызывался, чтобы было меньше мусора для уборки, и т.д. В отдельной статье я перечисляю несколько таких приёмов.
• выбрать сборщик мусора, который «заточен» под low-latency. JVM представляет несколько сборщиков мусора на выбор, из которых можно выбрать тот, что больше всего подходит для вашего конкретного случая. А с помощью разных параметров, точно настроить его.
• выбрать другую JVM (коммерческую реализацию), которая специально предназначена для low-latency приложений

Компилятор кода

JIT-компилятор оказывает нам неоценимую помощь. Но за эту помощь надо платить. На компиляцию кода и подмену «на лету» старого кода на новый требуется время и ресурсы. JIT-компилятор сам определяет, какие участки кода он будет компилировать и когда он будет их подменять. Мы лишь можем помочь ему в его работе с помощью тонких настроек. Лучше всего, конечно, иметь полностью прогретый на старте код, чтобы уже во время реальной работы приложения компиляция не производилась или производилась как можно реже.

Внутренние сервисы JVM

Сервисы JVM не прекращают свою работу после старта приложения. В определенные промежутки времени эти сервисы должны выполнить свою работу (поиск «мусора», финализация объектов, сброс внутренних кэшей ). JVM может приостановить свою работу только в определенные моменты времени. Это так называемые точки safepoints. По достижении такой точки JVM определяет, что можно безопасно приостановить работу приложения и даёт сервисам сделать своё дело. Такие короткие приостановки тоже являются причиной задержек и «дребезга». Например, вы получили критически важные рыночные данные, начали их обрабатывать, а JVM определила, что именно в этот момент наступил safepoint, остановила ваше приложение и дала поработать какому-то своему сервисному потоку. Когда ваше приложение снова продолжит свою обработку рыночных данных и наконец обработает их, будет уже поздно как-то на них реагировать, время будет упущено.

Интервалы точек safepoint можно настраивать с помощью стартовых параметров. Если интервалы сделать очень большими, работа сервисных потоков будет все время откладываться, в результате в JVM будет накапливаться мусор, который все равно придется убрать с остановкой JVM. Но если ваше приложение, например,  работает только 8 часов во время торгового дня, а потом перезапускается, то работу сервисных потоков можно откладывать с помощью стартовых параметров на неопределенное время, и таким образом избегать еще одной причины «дребезга».

Блокировки

Java поддерживает многопоточность «из коробки». Для обмена данными между потоками Java предлагает различные механизмы синхронизации и блокировки: от классического synchornized / wait / notify / notifyAll, до классов синхронизации в пакете java.util.concurrent.*, появившихся в Java 5. Механизмы синхронизации позволяют упорядочить доступ потоков к общему объекту (shared object) путем предоставления доступа к нему только одному потоку и блокировки всех других. Пока первый поток не закончит свою работу в критической секции (critical section), все остальные потоки находятся в очереди, т.е. находятся в заблокированном/нерабочем состоянии. Это значит, что вам не гарантируется время, затраченное на вызов какого-то метода, если метод обращается к общим данным. При в каком-то случае он может быть заблокирован, из-за того, что с данными в это время работает другой поток, и это может быть одной из причин «дребезга».

Во избежание подобных ситуаций при написании low-latency приложений стараются избегать блокировок и обращаются к неблокирующим структурам данных и неблокирующим алгоритмам. В этом случае время на вызов метода всегда гарантировано стабильное.

Операции внутри структур данных

При работе с определенными структурами данных «дребезг» может быть вызван внутренним поведением структуры в определенных условиях, например:

• ArrayList resizing: ArrayList по умолчанию выделяет внутри себя массив (array) определенного размера. Когда при добавлении элементов в ArrayList количество элементов достигает определенного порога, происходит операция «resizing», то есть метод ArrayList.add при вызове в такой ситуации сначала выделяет новый массив большего размера, копирует туда существующие данные и лишь потом добавляет новый элемент. Как вы понимаете в этом случае выполнение метода add замет чуть больше времени, чем обычно. Рекомендуется при создании ArrayList задавать размер массива, который по вашим предположениями или расчетам вам понадобится в конечном счете.
• HashSet / HashMap rehashing: Вспомните, как работают HashSet и HashMap. Внутри этих структур данных создается массив. При добавлении нового объекта, вычисляется hash этого обхекта, который служит для вычисления места (bucket/slot) в массиве, куда этот объект будет помещен. Если все места в массиве заняты, при добавлении нового объекта осуществляется аллокация нового массива, большего размера. Hash старых объектов перевычисляется и старые объекты перемещаются в новый массив. Только после этого новый объект добавляется в структуру данных и операция put заканчивает свое выполнение. Как и в случае в ArrayList рекомендуется задавать размер HashSet / HashMap заранее, чтобы время выполнения метода put всегда было предсказуемым
• HashSet / HashMap treefying. Если хэши разных объектов совпадают, в  Hash таблице они попадают в один и тот же слот (bucket). Для хранения всех неодинаковых объектов но с одним и тем же хешем принято использовать связанный список (linked list). При поиске объекта в Hash-таблице сначала по хэшу находится слот, а потом перебирается связанный список пока не находистя нужный объект. Как потом обнаружилось при умело созданной атаке (например, в web-приложении ) можно сделать так, что все объекты добавляемые объекты в hash-таблицу будут попадать в один и тот же слот и следовательно они все будут добавляться в один и тот же связанный список пока он не станет настолько большим, что перебор всех объектов в нем для поиска нужно не станет занимать ощутимое время. Во избежание подобной ситуации в новых реализация HashSet и HashMap в Java при достижении определенного количества объектов в заданном слоте связанный список преобразовывается в бинарное дерево. Это преобразование называется деревизация (treefying). Такое преобразование занимает время, поэтому добавление объекта в HashSet и в HashMap может занять больше времени, чем ожидалось, т.е. привести к дребезгу.

Задержки, вызванные операционной системой

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

В современных операционных системах каждому процессу выделяется определенное количество памяти. Но память эта — виртуальная. Неиспользуемые процессом участки памяти — не выделяются, либо сворачиваются на диск. Если процесс обратится к участку памяти, который находится на диске, происходит page fault, операционная система останавливает процесс, загружает участок памяти с диска в RAM, после чего снова запускает процесс. Если ваше приложение какое-то время не вызывало какой-то метод, а потом из-за стечения определенных условий сделало вызов, а он привел к page fault и остановке приложения, вы будете наблюдать «дребезг».

Задержки, вызванные железом

Современные процессоры оснащены множеством аппаратных средств для ускорения работы приложений. Это сделано с той целью, чтобы процессор как можно меньше простаивал и как можно больше времени проводил в обработке данных. Например, иерархия кэшей призвана уменьшить время простоя процессора, когда он ожидает поступления данных из RAM или с диска. Если данные оказываются в кэше (cache hit), ваше приложение тут же из получает с высокой скоростью. Если же данных нет ни в одном из уровней кэша (cache miss), процессор будет ждать данные из памяти. Это приводит к дребезгу, если ваша программа написана таким образом, что данные в кэше постоянно не те, которые нужны в данный момент. Есть еще много других нюансов работы с кэшем, которые требуют отдельной статьи.

Еще один пример, это функция branch prediction в процессоре, которая пытается предсказать, куда перейдет исполнение кода при вычислении условного перехода. Если ваш код на протяжение нескольких часов при определенном условии все время выдавал false, функция branch prediction считает что и в данном конкретном случае будет false, и уже подготавливает к исполнению кусок кода, который и до этого всегда исполнялся. Теперь представьте, что в какой-то момент ваше условие возвращает true. Летят к черту все предыдущие предположения в блоке branch prediction. Процессор теперь должен извлечь из памяти кусок когда, который соответствует переходу по ветке true, а это означает, что ваш процесс должен быть остановлен, данные (кода) должны быть извлечены из памяти, декодированы процессором. А это приводит к «дребезгу».

Выводы

В данной статье я перечислил лишь несколько причин, по которым может появляться «дребезг» в low-latency приложении. По каждой конкретной причине есть обширный материал в презентациях Алексея Шипилёва, Мартина Томпсона, Питера Лоури, в книгах по Java performance и в блогах многих программистов.