0,0
рейтинг
12 октября 2011 в 17:21

Разработка → Disruptor — новая парадигма многопоточного программирования

На прошлой неделе компания LMAX, где я работаю, получила приз Java Duke's Choice Award 2011 за фреймворк Disruptor. Ранее об этой технологии писал Martin Fowler, известный многим читателям публикациями об объектном программировании.

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

LMAX предоставляет трейдинговую платформу по CFD и Forex, отличающуюся очень низкой латентностью и высокой пропускной способностью.

Чтобы добиться скорости исполнения более 10 тысяч операций в секунду, LMAX разработали паттерн Disruptor. Это – совершенно новый и очень нетрадиционный подход к решению задач параллельного программирования. Disruptor – это многопоточный параллельный фреймворк для обработки транзакций отличающийся высокой пропускной способностью и очень низкой латентностью. Disruptor LMAX заменяет java.util.concurrent.ArrayBlockingQueue и превосходит её по производительности вплоть до 80 раз.

Проблема многопоточного программирования


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

Таблица иллюстрирует затраты на увеличение 64-битного счётчика 500 миллионов раз используя разные техники на процессоре 2.4Ghz Nehalem(стырено с блога коллеги).
Метод
Время (мс)
Один поток
300
Один поток с Memory Barrier
4,700
Один поток с CAS
5,700
Два потока с CAS
30,000
Один поток с Lock
10,000
Два потока с Lock
224,000


Подход LMAX


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

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

Disruptor – это очень высокоскоростной, низколатентный способ обмена сообщениями между потоками. Это как очередь на стероидах(на больших количествах стероидов!) и он является одной из главных инноваций биржи LMAX. Disruptor включает в себя производителя, потребителя и круговой буфер. Каждый производитель и потребитель знает порядковый номер – ячейка в буфере, которую он сейчас обрабатывает. Каждый производитель и потребитель записывает свой номер в счётчик, и может считывать другие счётчики. Таким образом, потребитель может считать счётчик производителя чтобы убедиться что ячейка, в которую он хочет записать доступна. Так же потребитель может проверить что он обрабатывает сообщение только после того, как другой потребитель закончил обработку.

Disruptor в LMAX

Преимущество Disruptor состоит в том, что потребители могут быстро догнать остальных, если они отстали. Если преобразователь сообщения (un-marshaller) столкнулся с проблемой на ячейке 15, и понял это когда получатель на ячейке 31, он может считать данные из ячеек 16-30 в один заход и быстро догнать. Возможность считывать большие блоки помогает отстающим потребителям быстро нагнать других, таким образом снижая латентность.

Процессор бизнес-логики управляет всей бизнес-логикой c помощью однопоточной Java-программы, которая реагирует на вызовы методов и производит события вывода. Он работает полностью в оперативной памяти, без базы данных или другого постоянного хранилища.

Хотя бизнес-логика осуществляется в одном потоке, целый ряд задач следует осуществить перед вызовом бизнес-объекта. Входящее сообщение из сети нужно unmarshall в формат удобный для бизнес логики, нужно сохранить на надёжный накопитель чтобы иметь возможность восстановить данные в случае аварии.

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

image

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

Выводы и ресурсы


Disruptor не является универсальным решением для каждой разработки, однако при правильном применении может показать заметное повышение скорости программных систем.
Часто финансовые компании не распространяются о своих технологиях. LMAX не только открыто говорит о своих разработках(см. блоги), но так же выпустил код Disruptor в Open Source.

См. так же — официальный сайт LMAX и партнёрский сайт LMAX на русском.

P.S. Добавлю, что этот фреймфорк лежит в основе трейдинговой платформы LMAX, запущенной год назад, и успешно обрабатывающей тысячи транзакций в секунду.
Наташка Барабашка @balbesko
карма
25,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (25)

  • +13
    Что-то не улавливаю, в чём новизна?
    Как понимаю, фреймворк на яве, тогда причём тут memory barriers? ведь от CAS2 до JVM целая толща кода!
    И потом, вроде всё сводится к тому, что есть классическая задача разделения доступа к ресурсу, ну кольцевой буфер вы привлекли для этого, очень хорошо, и что из того?
    Сначала думал что у вас там хитрая lock-free стратегия какая-то, но вроде её тоже нет.
    Вы недоговариваете про то как реализуется конкурентный доступ к тем же счётчикам.
    А как насчёт fault-tolerance? Ну скажем этот unmarshaller не просто вышел покурить, а укурился совсем и его увезли на скорой в больницу?
    Как-то неполно и нового ничего нет…
    Вы извините, но эта тема мне интересна, мне приходилось самому разрабатывать такие системы в реальности (>30tps 24/7) и мне трудно поверить что на яве можно сделать что-то работающее в этом контексте.
    • НЛО прилетело и опубликовало эту надпись здесь
      • +2
        У меня ощущение что очередную примитивную вещь прикрывают заумными рассуждениями про барьеры памяти и тп. Почему-то такое часто наблюдаю когда слышу про яву. И даже Фаулера сюда прикрепили…

        "… на java подобное неоднократно делалось, java для этого очень хорошо подходит"
        Поверьте мне, ява не лучший инструмент для таких задач.
        Вы просто не можете полагаться на какой-то jit когда речь идёт о вещах, которые должны быть вылизаны до блеска. Там же деньги крутятся, а ява со своей непредсказуемой сборкой мусора и капризами виртуальной машины быстро могут всё испортить.

        Масштабироваться до 10Ktps без наращивания числа рабочих процессов вы не сможете. Это если у вас там не совсем примитивная обработка конечно, но тогда уж и вся эта затея с кольцевыми буферами не нужна, можно попроще что-то придумать.
        А раз уж число процессов становится ощутимо большим, то тут и начинается главный challenge. Мы сравнивали однажды, ява гибла однозначно.
        К тому же исходные данные как-то должны попадать в систему, значит рабочий процесс должен общаться с внешним миром. Это ещё один challenge.
        Это всё будет работать, но на небольших нагрузках, для торгов не потянет…

        Продолжать спорить не хочу, увидел вашу аватарку и понял что это надолго (шутка (с) ) :)
        • НЛО прилетело и опубликовало эту надпись здесь
        • +1
          Возможно неясно из моего поста, но данная система не находится в стадии прототипа, а была запущена год назад(октябрь 2010), и успешно функционирует, обрабатывая тысячи транзакций в секунду.
          Сами буфферы весьма немаленькие — 20М слотов для входящего буффера и по 4М слотов для исходящих. Система буффера рестартуется ночью, во избежание дорогостоющего Garbage Collection.
      • 0
        Мне кажется мы говорит об обычной очереди сообщений или нескольких очередей. Чем очередь сообщений принципиально отличается от буфера?

        Подалуйста, посните подробнее, потому-что просто так Duke's Choice Award, и хочется понять, чтобы плодотворно использовать!
        • НЛО прилетело и опубликовало эту надпись здесь
      • 0
        «JIT все заоптимизДит»
        поручик, как тонко подмечено!
    • 0
      поправка, ">30000tps" конечно же, только сейчас заметил…
    • 0
      Полность согласен!
      Я меня самого такая система работает, причем очередь реализована rabbitMQ. У ява машин иногда течет память в режиме lon-run (3-4 года без остановки высоконограженного сервиса), а с помощью сторонней очереди — можно перегрузить сервис без потери данных. Конечно эта схема полностью нарушает парадигму java прложений, но ведь работает! ;-)
  • +1
    гиковский радио-т повлиял?
  • 0
    Перевод что ли?
    Язык какой-то корявый, плохо читается.
    • 0
      Сложновато у меня с техническим русским.
      И частично перевод, да.

      Правда, статья Фаулера и в оригинале плоховато читается.
  • 0
    А в чём смысл партнёрки? Где регестрироваться, на оффсайте или на ней?
    • 0
      Ну то есть я понимаю, что профит владельцу партнёрки (Вам? :-), просто хочу всё знать :)
    • 0
      Регистироваться можно только на сайте LMAX.
      Смысл партнёрки — это единственный ресурс на русском о LMAX
  • 0
    Это циклический буфер по которому гуляют несколько обработчиков не обгоняя друг друга?
    • +3
      То есть реализует параллелизм типа «конвейер». Единственное отличие от конвейера — механизм поставки данных через циклический буфер. Так?
      • 0
        Да, примерно так.
  • 0
    А в чем преимущество по отношению к пулу потоков? Там ведь то же самое, просишь выполнить вызов метода асинхронно, и он выполняется в произвольном рабочем потоке. Плюс там уже готовый балансировщик, и масштабируемость автоматическая.
    Я сам .NET-чик, но судя по тому, что я нагуглил за пару минут, в Java пул потоков примерно совпадает по функциональности с .NETным.
    И да, перевод кривоват, тавтологии много.
    • 0
      Я не .NETчик и не JAVAчик, поэтому точно ответить не смогу.
      Но у нас проблема в том, что некоторые операции должны происходить в чётком порядки FIFO — ведь система «играет» с настоящими деньгами. А если потоки начнут произвольно там что-то выполнять, клиенты от нас очень скоро смотаются.

      • 0
        Это понятно, что в рамках одной операции последовательность действий не должна нарушаться. Тут проблема я так понял, заключается в том, что есть набор комплексных операций, каждую из которых можно разбить на этапы, каждый этап можно выполнять параллельно с любым другим этапом любой другой операции, но последовательно в рамках одной операции, и нужно это дело сделать неблокирующим и масштабируемым.
        Для этого можно использовать пул потоков с цепочкой каллбеков завершения. Каждая операция выглядит примерно так:

        void AsyncOperation()
        {
        // Синхронное выполнение какого-то кода.
        DoSomething();
        // Асинхронное выполнение следующего этапа.
        new Action(DoStageTwo).BeginInvoke((IAsyncResult ar) =>
        {
        // После завершения этапа 2, произвольный поток. Еще что-то делаем.
        DoSomethingElse();
        // Планируем следующую часть.
        new Action(DoStageThree).BeginInvoke((IAsyncResult ar) =>
        {
        // После завершения этапа 3, произвольный поток.
        // и т.д.
        }
        }
        }

        Метод возвращает управление сразу же по завершении строчки «new Action(DoStageTwo)...»! Т.е. синхронна только часть, обращающаяся к пулу потоков. Дальше, если вызвать много таких операций, то их куски будут выполняться параллельно, но последовательно в рамках одной операции.
        В .NET 4.0 для сокращения кода есть синтаксический сахар — ключевые слова ASYNC и AWAIT, которые позволяют написать указанный код без явного вызова Delegate.BeginInvoke.
  • +2
    А парадигма, парадигма-то где?
    Да, любопытная либа хорошо работающая там для чего она создавалась.
    Но ИМХО на парадигму не тянет.
    • –1
      Этот фреймворк можно использовать не только для такой системы, а для любой другой где важна низкая латентость, высокая скорость и предсказуемое поведение.

      Disruptor — это новый подход к старым проблемам.
      • НЛО прилетело и опубликовало эту надпись здесь

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