Какие есть инструменты и решения для экстремально быстрой online-аналитики потоковых данных?

Question

[Иван Мельников]

Хотелось бы узнать о таких инструментах, решениях и подходах разработки для экстремально быстрой online-аналитики потоковых данных для decision making.
Я понимаю, что ничего не может быть быстрее полной реализации необходимого функционала на C/C++, но это часто (если не всегда) слишком дорого, слишком долго и менее стабильно.
Какие "кирпичики" используют в таких задачах?

Уточнения:
- Под экстремально быстрой аналитикой я подразумеваю "чем быстрее, тем лучше". Например, 1 мс будет сильно лучше 10 мс.
- Под данными подразумеваются market data от множества различных независимых источников.
- Для меня важно стабильное экстремальное low lanency. В какой-то момент данных может поступать очень много (highload), а в какой-то очень мало (единицы записей в секунду). Но в обоих случаях важен экстремальный low lanency для decision making.

Comments

[Everything_is_not_so_bad]

Что за аналитика? Какого рода запросы?

[Иван Мельников]

Иерокопус Таманский, всевозможные статистики временных рядов в окне.

[Сергей Горностаев]

Я понимаю, что ничего не может быть быстрее полной реализации необходимого функционала на C/C++,

Это заблуждение. Среды с jit-компиляцией обычно показывают более хорошую пропускную способность после прогрева, чем aot-компилируемые выдавать в принципе способны.

Для меня важно стабильное экстремальное low lanency.

Очень редко можно встретить такое требование в подобном классе задач. За низкой латентностью гоняются обычно в системах реального времени. Зачем оно вам?

[Иван Мельников]

Зачем оно вам?

Принятое решение имеет ценность, если вы его успеваете быстро реализовать. Оно быстро "протухает". Это в контексте HFT. В противном случае, в моём понимании, есть риск реализовать "протухшее" решение.

[Иван Мельников]

Сергей Горностаев,

Это заблуждение. Среды с jit-компиляцией обычно показывают более хорошую пропускную способность после прогрева, чем aot-компилируемые выдавать в принципе способны.

А есть какая-то фактура на эту тему? Статьи, доклады.

[Василий Банников]

Сергей Горностаев,

чем aot-компилируемые выдавать в принципе способны.

Это от того что в среднем aot компилируется под среднестатистическую машину и без PGO.
Если заранее знать особенности целевой машины (семейство процессоров, поддерживаемые наборы инструкций, и закинуть данные профайлинга, то результат в принципе не будет уступать JIT-ованным языкам.

Другое дело что прогрев JIT-а занимает неизвестное время, требует определённых ресурсов.
Да и про GC не забываем. Лично я не видел таких языков, у которых был бы хороший JIT, но при этом не было GC, либо без него можно было очень легко обойтись.

[Василий Банников]

Иван Мельников,

А есть какая-то фактура на эту тему? Статьи, доклады.

Бенчмарки и листинг кода, который тебе генерирует JIT, и который генерирует AOT-компилятор.

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

[Сергей Горностаев]

Василий Банников,

Да и про GC не забываем.

Современные GC работают без STW и способны обрабатывать терабайтные кучи.

Если заранее знать особенности целевой машины (семейство процессоров, поддерживаемые наборы инструкций, и закинуть данные профайлинга, то результат в принципе не будет уступать JIT-ованным языкам.

Профиль выполнения может меняться и если JIT на ходу перекомпилирует код, то для AOT придётся каждый раз собирать новый профиль и новый билд с ним. Не видел ещё ни один проект, который мог бы адаптироваться например под рекламные компании так же хорошо, как проекты на JVM. При этом плюсы AOT с Граалем уже доступны для java-мира.

[Иван Мельников]

Сергей Горностаев, речь про Oracle GraalVM ?

[Василий Банников]

Сергей Горностаев,
1. STW вроде как концептуально необходим, хоть и можно, например, привязать их к процессорным ядрам, чтобы останавливать не всё, а только часть.
2. Можно конкретный пример?

Профиль выполнения может меняться и если JIT на ходу перекомпилирует код

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

Да и то что чисто в теории JIT так может - не значит, что разработчики рантайма так станут делать.
В том же .NET, емнип, профиль собирается 1 раз и после этого статистика больше не собирается.

[Сергей Горностаев]

Василий Банников,

STW вроде как концептуально необходим

неа, shenandoah и zgc работают без остановок.

Да и то что чисто в теории JIT так может - не значит, что разработчики рантайма так станут делать.

Как классические C1 и C2, так и новый граалевский jit'ы постоянно перегенерируют машинный код под текущий профиль. Если сценарий нагрузки меняется, ресурсы потратятся на новый прогрев, но оно того стоит.

[Сергей Горностаев]

Иван Мельников, он уже не оракловый, в прошлом году они его передали в опенсорс.

[Василий Банников]

Сергей Горностаев,

неа, shenandoah и zgc работают без остановок.

Спс, почитаю.

[Василий Банников]

Сергей Горностаев,

Если сценарий нагрузки меняется, ресурсы потратятся на новый прогрев, но оно того стоит.

Тут сценарий выглядит как раз так, будто профиль вообще не будет меняться

[Сергей Горностаев]

Василий Банников, я бы тогда на Rust посмотрел, как дрочер на функциональщину )

Answer 1

[Сергей Соловьев]

Ответ: Для экстремально быстрой online-аналитики нужны экстремально быстрые инструменты

Если серьезно, то когда речь заходит о хайлоаде, то нет готовых решений. Все приходится писать самим и тюнить весь софт под свои нужды.
Чтобы помочь надо знать контекст, а "чем быстрее, тем лучше" - у всех так.

Все что могу предложить:
- Горизонтально масштабировать софт, который эти данные от источников читает
- Использовать ClickHouse для хранения данных

Почему ClickHouse:
- Создан для OLAP задач
- Имеет поддержку шардирования причем шарды независимы - не нужно тратиться на синхронизацию

P.S. если это задача по трейдингу, то советую копать в сторону HFT

Comments

[Иван Мельников]

Уточню, что для меня важно стабильное экстремальное low lanency. В какой-то момент данных может поступать очень много (highload), а в какой-то очень мало (единицы записей в секунду). Но в обоих случаях важен экстремальный low lanency для decision making.

[Иван Мельников]

Использовать ClickHouse для хранения данных

Многие советуют. Но вроде как KDB+ сильно быстрее для расчёта статистик в окне.

[Сергей Соловьев]

Иван Мельников, инструментов куча, а контекст задачи неясен. все хотят низкую задержку, мало потреблять ресурсов, масштабироваться бесконечно и т.д.
задачу поконкретнее надо описать

[Иван Мельников]

Это обычная задача из HFT.
С нескольких фондовых и криптобирж по всем инструментам поступают рыночные данные: поток ордеров и поток сделок.
Имеется какая-то модель для принятия решений (ML, нейросеть, вероятностный вывод или просто какие-то правила вида if ... else ..., в которые мы верим).
Собственно, всё. Нам нужно экстремально быстро принимать решения о выставлении ордеров (на покупку или продажу) по мере получения новой информации.

[Василий Банников]

Иван Мельников,

очень много

Это сколько? В штуках или байтах/с

[Иван Мельников]

Василий Банников,
очень много – ~ 100 тыс. записей в секунду;
очень мало – единицы записей в секунду.
Одна запись – это что-то вида

ticker: SBER
type order: buy limit
size: 100
price: 150.015

[Василий Банников]

Иван Мельников. Если упороться и постараться уместить в минимальное количество байт, то можно попробовать уместить в 64 байта с учётом выравнивания)

Ну получается меньше 50мбит в секунду, что уже выглядит как вполне адекватное количество данных, которое может переварить одна машина.

[Сергей Соловьев]

Иван Мельников, если хочешь побольше об этом узнать, то у подлодки выходил выпуск про HFT -
https://music.yandex.ru/album/7570122/track/87571524

Answer 2

[Василий Банников]

"экстремально" - это имеет какое-то численное значение?

- Под экстремально быстрой аналитикой я подразумеваю "чем быстрее, тем лучше". Например, 1 мс будет сильно лучше 10 мс.

Тут лучше сказать, какой вариант будет точно неприемлимым и на сколько сложные вычисления нужно успеть выполнить.

- Под данными подразумеваются market data от множества различных независимых источников.

А этот самый market data вам уже приходить с экстремально низкой задержкой?

low latency

Отсекаем все языки со сборкой мусора, тк у них будет происходить вполне очевидная пауза.
Отсекаем все незрелые.
И вот у нас остаётся небольшой выбор: C, C++, Rust, Zig - компилируемые императивные языки без сборки мусора.

В целом выглядит как HFT, а значит и решения нужно брать те, которые активно в HFT используют.
Без конкретики - ничего конкретного посоветовать нельзя.

Comments

[Иван Мельников]

Тут лучше сказать, какой вариант будет точно неприемлимым и на сколько сложные вычисления нужно успеть выполнить.

Желательно, от поступления новых данных на сетевой порт моего сервера до выставления заявки по api биржи должно пройти не более 100 мс. Хотя бы так. В идеале, конечно, 10 мс.
Вычисления: от стандартных статистик (среднее (усечённое) арифметическое, квантили, сумма, дисперсия, корреляции, волатильность) до чего-то посложнее (FFT, какие-то приближённые комбинаторные расчёты, по потокам ордеров и сделок строится стакан для каждого инструмента, а уже на стакане считаются метрики, например, спрэд и форма стакана). Этот этап видится самым долгим. Отработка модели должна происходить гораздо быстрее.

А этот самый market data вам уже приходить с экстремально низкой задержкой?

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

И вот у нас остаётся небольшой выбор: C, C++, Rust, Zig - компилируемые императивные языки без сборки мусора.

С выбором языков всё примерно понятно.
Но вот какое хранилище использовать для горячих данных? Можно ли использовать брокер сообщений, например, Kafka?

[Василий Банников]

Иван Мельников,

до выставления заявки по api биржи должно пройти не более 100 мс

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

В этой зоне лаг на передачу данных вроде не превышает 1 мс.

Ладно

Но вот какое хранилище использовать для горячих данных?

Непосредственно в оперативной памяти процесса я бы и хранил.
Сколько вообще этих данных физически?

Можно ли использовать брокер сообщений, например, Kafka?

1. Кафка не брокер сообщений.
2. Я бы не назвал кафку системой для горячих данных, так как все данные в кафке идут через диск.
Для онлайн аналитики она в принципе подходит, но точно не для HFT.

[Иван Мельников]

Василий Банников,

До выставления заявки на бирже или до формирования заявки на твоей стороне?

На моей стороне.

Непосредственно в оперативной памяти процесса я бы и хранил.
Сколько вообще этих данных физически?

Ну, если сделать оценку сверху. Пускай поступает 100 тыс. записей в секунду каждую секунду. По-хорошему данные в быстром доступе должны быть с начала торгового дня. Пусть торговый день длится 15 часов. Итого, 100 000 * 15 * 3600 = 5 400 000 000 записей.
Пусть информационная ёмкость одной записи 20 байт.
Итого, к концу дня сырых данных накопится 5 400 000 000 * 20 ≈ 100 ГБ.
Плюс нужно хранить рассчитанные метрики.
Выглядит так, что 256 ГБ в виде RAM должно хватить.
То есть, все хранить в оперативной памяти в принципе возможно.

[Василий Банников]

Иван Мельников, ну это сырые данные, а ведь их ещё нужно как-то индексировать, чтобы доступ таки был быстрым. Так что да, действительно нужно ещё сверху гигов 100.

Answer 3

[mayton2019]

При расчете аналитики (min/max/avg) и прочих оконных функций сам алгоритм имеет лаг.
Тоесть ты должен понимать что за 1 мс ты можешь анализировать данные в прошлом за окно
размером к примеру в 100мс.

Нельзя выводить точную аналитику на основе мгновенного значения.

Comments

[Иван Мельников]

Разумеется, на первом этапе рассчитываются статистики в каком-то временном окне.
На втором – результаты рассчитанных статистик передаются на вход модели.
На третьем – если модель приняла решение о каком-то действии, то выставляется order на продажу или покупку, снимается/изменяется order или что-нибудь ещё.

[mayton2019]

Иван Мельников, у этих этапов есть технические лаги. Стоит ли тебе упарываться 1 милисекундой?

[Иван Мельников]

mayton2019, пока не понятно. Может быть и 10 мс или даже 100 мс будет достаточно. Тут только методом тыка удастся нащупать баланс между сложностью модели принятия решений (с набором рассчитываемых метрик) и скоростью принятия решений.

[mayton2019]

У тебя очень перегретое ТЗ. Лучше из него убрать такие поэтические метафоры экстремально
или "чем быстрее, тем лучше". Потому что под них невозможно написать никаких SLA, AC.
Лучше нарисовать картинкой диаграмму из кубиков где слева течет информация
и описать роли и отвественности кубиков.

Разуместся главный кубик - это язык С++ и использование AsyncIO API. В Linux оно называется
multiplexing IO. Там кажется всего три функции select, poll, epoll.

В современных C++ фреймворках эти функции могут быть просто завернуты в какое-то громкий API.
Какой - я к сожалению не знаю т.к. давно уже не писал ничего на С++.

Да. Если будешь подписываться на какие-то SLA, то никогда не указывай максимумы минимумы и средние.
Пиши про 95 процентиль например. Типа 95 % всех сигналов будут обработаны за 1мс.

[Иван Мельников]

mayton2019, спасибо за советы!