23 августа 2011 г.

LMAX trading

Статья про архитектуру трейдинговой платформы LMAX. Кажется, про нее рассказывали на JavaOne, но я пропустил этот доклад. Читать здесь

Несколько любопытных вещей. Во-первых, они ухитряются обрабатывать 6 миллионов транзакций в секунду на обычных серверных Nehalem-ах, при том, что вся бизнес-логика у них в одном потоке. А, да, все это на java.

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

Вкратце: во-первых, у них три главных части в приложении -- входная "мультиочередь" (хитрая структура данных, которую они назвали Disruptor, по-сути -- циклическая конкурентная очередь-конвейер, она одна стоит разговора), в которую приходят все заявки, обработчик бизнес-логики (тот самый, однопоточный), который берет заявки из этой очереди, и выходная такая же мультиочередь.

Обработчик бизнес-логики -- это, по-сути, message-loop, однопоточный, написаный максимально оптимизированно. Все данные ("мир") он держит исключительно в оперативке, весь код очень простой и максимально короткий, чтобы JIT его наиболее удачно оптимизировал (JIT-friendly code). Это, в частности, и позволило им получить 6 миллионов транзакций в секунду. Но здесь возникает вопрос надежности (устойчивости к сбоям), и вопрос ввода-вывода -- он, по-любому, медленный, и традиционно в одном потоке не делается.

И тут на сцену выходят как раз мультиочереди-конвейеры. Идея состоит в том, что, прежде чем попасть на вход к обработчику бизнес-логики, сообщение проходит целый конвейер обработчиков. Конвейер этот, по сути, ориентированный граф с определенной топологией. На вход конвейеру сообщение подается чуть ли не в виде массива байт, как оно принято из сети -- причем делать это могут сразу несколько потоков (т.е. они могут слушать сразу несколько сетевых интерфейсов, в частности). Дальше, по мере продвижения по конвейеру, данные могут обрабатываться различными обработчиками.

Большая часть из обработчиков read-only -- и они вполне себе работают параллельно, загружая разные ядра процессора. В частности, какие-то обработчики дублируют данные на вторичные сервера -- реально в продакшене в каждый момент времени работают 3 территориально разнесенных сервера, с полностью идентичным состоянием -- это решает проблему устойчивости к сбоям. Другие обработчики сохраняют данные в персистентное хранилище -- так что состояние системы (которое, напомню, все в оперативке) в любой момент можно восстановить заново накатив весь лог событий (реально раз в сутки делается снапшот, так что накатывать приходится только за последние сутки). Третьи отправляют часть событий для какого-то анализа и последующей генерации отчетов. И так далее.

Часть обработчиков -- read-write, в частности, те, которые собственно парсят и раскодируют сообщение, превращая его из массива байт в джава-объекты, и в конечном счете, в набор команд для процессора бизнес-логики.

Причем команда разработчиков сумела реализовать этот конвейер обработчиков событий очень эффективно, с минимальными накладными расходами, при сохранении высокого уровня конкурентности. Их Disruptor по их бенчмаркам обеспечивает примерно в 4-8 раз большую пропускную способность, чем реализация аналогичного графа с помощью стандартных ArrayBlockingQueue, и на несколько порядков меньшие задержки. Плюс намного меньшую нагрузку на GC.

Что в итоге: в итоге main code path для обработки входящей транзакции включает в себя начальную предобработку (парсинг/проверка/конвертация в команды), которая делается конвейером параллельных обработчиков, работающих на разных ядрах, и передающих друг другу данные с минимальными накладными расходами (через Disruptor), потом отработку команд центральным процессором бизнес-логики -- который максимально короткий, и работает только с оперативкой, и выдачу результата в выходной Disruptor -- что опять же почти даром. Т.е. этот центральный путь -- максимально короткий, и максимально предсказуемый -- на нем нет ничего, что могло бы вызвать непредсказуемые задержки, ни аллокации больших объемов памяти (что приближает full stop-the-world GC), ни блокировок, ни сетевого ввода-вывода в базу данных. Практически, этот центральный путь не вполне real-time, но что-то очень близкое к тому. Все тяжелые вещи -- типа анализа, без которого все равно не обойтись -- можно вынести на отдельные машины, получающие данные с входного/выходного конвейера -- без малейшей задержки центральной части.

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

6 комментариев:

  1. 6 млн операций в секунду, хм... получается по 166 ns на операцию. Теперь если взять оценки с http://highscalability.com/blog/2011/1/26/google-pro-tip-use-back-of-the-envelope-calculations-to-choo.html, где сказано, что "Main memory reference 100 ns". А, ведь, взять из входной мультиочереди и положить в выходную, это будут как раз операции с основной памятью скорее всего. Т.е. у них прямо какие-то волшебные машины с совсем другими порядками времени выполнения простейших операций получаются.

    ОтветитьУдалить
  2. >это будут как раз операции с основной памятью скорее всего

    Вовсе не факт, что с основной памятью. Это скорее всего будут операции с кэш-памятью. Тут ведь вся фишка в том-то и есть -- благодаря грамотной архитектуре все данные максимально горячие в кэше. L2 кэш имеет латентность уже <10ns.

    ОтветитьУдалить
  3. Ну да это было просто предположение. Я честно говоря, не очень себе представляю когда данные идут через L1, L2 и т.д. Просто, думал, что раз разные потоки будут обращаться к одной и той же памяти (кто-то положил в мультиочередь, а мы потом берем его от туда), то есть вероятность, что нам придется синхронизироваться через основную память.

    ОтветитьУдалить
  4. Там у них все правда очень грамотно продумано -- я еще буду об этом писать. Насколько я могу видеть со стороны -- они и правда вполне способны выжать эти 6 миллионов трансзакций не напрягаясь.

    ОтветитьУдалить
  5. Погуглил немного про процессорные кэши. Пишут, что Intel имеет в том числе пошаренные кэши между ядрами, а AMD нет, поэтому вопрос все же остается.

    Я верю, что они очень грамотные ребята, и все у них реально летает. Вопрос остается в том, как они это сделали...

    ОтветитьУдалить
  6. Насколько я понимаю, массив элементов в disruptor у них в кэш не влезает -- там 2 млн элементов, это явно больше, чем L1. Но доступ к этому массиву абсолютно предсказуем -- поэтому процессор его легко угадывает, и префетчит данные в кэш заранее, что амортизирует латентность основной памяти или L2 -- где там этот массив лежит. После же того, как производитель спровоцировал загрузку в кэш очередной(ых) ячейки, эта ячейка (ее кэшлайн) передается между ядрами по интерконнекту. Так и получается, что начальная загрузка опережающая за счет предсказуемого паттерна обхода памяти, а дальше все через интерконнект.

    И да, они специально упоминают, что 6 миллионов трансзакций/с -- это именно на Nehalem-ах

    ОтветитьУдалить