Как работает шаблон прерывания LMAX?

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

Похоже, что есть один или несколько атомных целых чисел, которые отслеживают позиции. Кажется, что каждое «событие» получает уникальный идентификатор, и его положение в кольце определяется путем нахождения его модуля по размеру кольца и т. Д. И т. Д.

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

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

Есть ли хорошие рекомендации для лучшего объяснения?

5 Solutions collect form web for “Как работает шаблон прерывания LMAX?”

Проект Google Code ссылается на технический документ о внедрении кольцевого буфера, однако он немного сух, академичен и жестко подходит для тех, кто хочет узнать, как это работает. Однако есть некоторые сообщения в блогах, которые начали объяснять внутренности более читаемым образом. Существует пояснение кольцевого буфера, который является kernelм шаблона разрушителя, описание потребительских барьеров (часть, относящаяся к чтению от разрушителя) и некоторая информация о работе с несколькими производителями .

Простейшим описанием Disruptor является: Это способ отправки сообщений между streamами наиболее эффективным способом. Он может использоваться как альтернатива очереди, но также имеет ряд функций с SEDA и Actors.

По сравнению с очередями:

Disruptor предоставляет возможность передавать сообщение на другие streamи, пробуждая его, если требуется (аналогично BlockingQueue). Тем не менее, есть 3 различных отличия.

  1. Пользователь Disruptor определяет, как хранятся сообщения, расширяя class Entry и предоставляя фабрику для преалоляции. Это позволяет использовать либо повторное использование памяти (копирование), либо запись может содержать ссылку на другой объект.
  2. Посылка сообщений в Disruptor является двухфазным процессом, сначала в кольцевом буфере заявлен слот, который предоставляет пользователю запись, которая может быть заполнена соответствующими данными. Затем запись должна быть выполнена, этот двухфазный подход необходим, чтобы обеспечить гибкое использование памяти, упомянутой выше. Это фиксация делает сообщение видимым для потребительских streamов.
  3. Пользователь несет ответственность за отслеживание сообщений, которые были изложены в кольцевом буфере. Перенос этой ответственности из кольцевого буфера помог уменьшить количество конфликтов записи, так как каждый stream поддерживает собственный счетчик.

По сравнению с актерами

Модель Actor ближе Disruptor, чем большинство других моделей программирования, особенно если вы используете classы BatchConsumer / BatchHandler, которые предоставляются. Эти classы скрывают все сложности, связанные с сохранением номеров потребляемых последовательностей и обеспечивают набор простых обратных вызовов, когда происходят важные события. Однако есть несколько тонких различий.

  1. Disruptor использует 1 потребительскую модель с 1 streamом – 1, где актеры используют модель N: M, то есть у вас может быть столько игроков, сколько вам нравится, и они будут распределены по фиксированному количеству streamов (обычно 1 на kernel).
  2. Интерфейс BatchHandler обеспечивает дополнительный (и очень важный) обратный вызов onEndOfBatch() . Это позволяет медленным потребителям, например, делать операции ввода-вывода для пакетных событий вместе, чтобы повысить пропускную способность. Можно выполнить доработку в других структурах Actor, однако, поскольку почти все другие структуры не обеспечивают обратного вызова в конце пакета, вам нужно использовать таймаут для определения конца партии, что приводит к плохой задержке.

По сравнению с SEDA

LMAX построил шаблон Disruptor для замены подхода на основе SEDA.

  1. Главным улучшением, которое он предоставил над SEDA, была способность параллельно выполнять работу. Для этого Disruptor поддерживает многолитирование одних и тех же сообщений (в том же порядке) нескольким потребителям. Это позволяет избежать необходимости в этапах вилки в трубопроводе.
  2. Мы также разрешаем потребителям ждать результатов других потребителей, не ставя перед ними очередную стадию очередей. Потребитель может просто наблюдать за порядковым номером потребителя, от которого он зависит. Это позволяет избежать необходимости в этапах соединения в трубопроводе.

По сравнению с препятствиями памяти

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

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

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

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

Обычно читатели могут читать одновременно и независимо. Однако мы можем заявлять зависимости между читателями. Зависимости Reader могут быть произвольными ациклическими графами. Если читатель В зависит от читателя А, читатель В не может читать читателя А.

Зависимость читателя возникает потому, что читатель А может аннотировать запись, а читатель В зависит от этой annotations. Например, A выполняет некоторые вычисления в записи и сохраняет результат в поле a в записи. A затем перейдите, и теперь B может прочитать запись и сохранить значение A. Если читатель C не зависит от A, C не должен пытаться читать a .

Это действительно интересная модель программирования. Независимо от производительности, модель сама по себе может принести пользу многим приложениям.

Конечно, главной целью LMAX является производительность. Он использует предварительно выделенное кольцо записей. Кольцо достаточно большое, но оно ограничено, так что система не будет загружена за пределы проектной емкости. Если кольцо заполнено, писатель (ы) будет ждать, пока самые медленные читатели не продвинутся и не освободят место.

Объекты ввода предварительно распределены и живут вечно, чтобы уменьшить стоимость сбора мусора. Мы не вставляем новые объекты ввода или удаляем старые объекты записи, вместо этого автор запрашивает ранее существовавшую запись, заполняет ее поля и уведомляет читателей. Это кажущееся 2-фазное действие действительно просто атомное действие

 setNewEntry(EntryPopulator); interface EntryPopulator{ void populate(Entry existingEntry); } 

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

И много усилий, чтобы избежать блокировки, CAS, даже барьера памяти (например, используйте переменную переменной нестабильной последовательности, если есть только одна запись)

Для разработчиков читателей: разные аннотирующие читатели должны писать в разные поля, чтобы избежать конкуренции. (На самом деле они должны писать в разные строки кэша.) Аннотирующий читатель не должен касаться ничего, что могут читать другие не зависящие от читателя читатели. Вот почему я говорю, что эти читатели аннотируют записи, а не изменяют записи.

Мартин Фаулер написал статью о LMAX и шаблоне disruptor , LMAX Architecture , которая может прояснить его дальше.

Я действительно потратил время, чтобы изучить реальный источник, из чистого любопытства, и идея, стоящая за этим, довольно проста. Самая последняя версия на момент написания этого сообщения – 3.2.1.

Существует буфер, в котором хранятся предварительно выделенные события, которые будут хранить данные для чтения потребителями.

Буфер поддерживается массивом флагов (целочисленный массив) его длины, который описывает доступность слотов буфера (подробнее см. Подробности). Массив получает доступ как java # AtomicIntegerArray, поэтому для этого объяснения вы можете также предположить, что он один.

Может быть любое количество производителей. Когда производитель хочет записать в буфер, генерируется длинное число (как при вызове AtomicLong # getAndIncrement, Disruptor фактически использует свою собственную реализацию, но работает так же). Назовем это сгенерированным longproducCallId. Аналогичным образом, consumerCallId генерируется, когда потребительская ENDS считывает слот из буфера. Доступен самый последний доступ к потребителю.

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

Затем эти идентификаторы сравниваются, и если разница между ними меньше, чем буферная сторона, производителю разрешено писать.

(Если производительCallId больше, чем недавний queryCallId + bufferSize, это означает, что буфер заполнен, и продюсер вынужден ждать по шине, пока не станет доступно место.)

Затем производителю присваивается слот в буфере на основе его callId (который является prducerCallId по модулю bufferSize, но так как bufferSize всегда имеет мощность 2 (ограничение, установленное при создании буфера), используемая операция активации – производительCallId & (bufferSize – 1 )). Затем можно изменить событие в этом слоте.

(Фактический алгоритм немного сложнее, включая кэширование недавнего consumerId в отдельной атомной ссылке для целей оптимизации.)

Когда событие было изменено, изменение «опубликовано». При публикации соответствующего слота в массиве флагов заполняется обновленный флаг. Значение флага – это номер цикла (производительCallId, деленный на bufferSize (опять же, поскольку bufferSize имеет мощность 2, фактическая операция – это сдвиг вправо).

Аналогичным образом может быть любое количество потребителей. Каждый раз, когда потребитель хочет получить доступ к буферу, генерируется consumerCallId (в зависимости от того, как потребители были добавлены в разрушитель, атом, используемый в генерации id, может быть разделен или разделен для каждого из них). Этот consumerCallId затем сравнивается с последним producentCallId, и если он меньше из двух, читателю разрешено продвигаться вперед.

(Точно так же, если производительCallId является даже для customerCallId, это означает, что буфер является empety, и потребитель вынужден ждать. Способ ожидания определяется WaitStrategy во время создания сбоя.)

Для отдельных потребителей (те, у которых есть собственный генератор идентификаторов), следующая вещь проверяется – это возможность потреблять партии. Слоты в буфере проверяются по порядку от единицы, соответствующей customerCallId (индекс определяется таким же образом, как и для производителей), который соответствует последнему производителюCallId.

Они проверяются в цикле путем сравнения значения флага, записанного в массиве флагов, со значением флага, генерируемым для customerCallId. Если флаги совпадают, это означает, что производители, заполняющие слоты, совершили свои изменения. Если нет, цикл прерывается, и возвращается самая высокая переменная changeId. Слоты из ConsumerCallId, полученные в changeId, могут быть использованы в пакетном режиме.

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

Из этой статьи :

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

Память-барьеры трудно объяснить, и блог Trisha сделал наилучшую попытку, на мой взгляд, с этой должности: http://mechanitis.blogspot.com/2011/08/dissecting-disruptor-why-its-so-fast. HTML

Но если вы не хотите погружаться в детали низкого уровня, вы можете просто знать, что барьеры памяти в Java реализованы с помощью ключевого слова volatile или через java.util.concurrent.AtomicLong . Последовательности шаблонов разрушителей являются AtomicLong s и передаются назад и вперед среди производителей и потребителей через барьеры памяти вместо блокировок.

Мне легче понять концепцию с помощью кода, поэтому приведенный ниже код – это простой helloworld из CoralQueue , который представляет собой реализацию шаблона прерывания, выполненную CoralBlocks, с которой я связан. В приведенном ниже коде вы можете увидеть, как шаблон disruptor реализует пакетную обработку и как кольцевой буфер (например, круговой массив) позволяет без мусора обмениваться данными между двумя streamами:

 package com.coralblocks.coralqueue.sample.queue; import com.coralblocks.coralqueue.AtomicQueue; import com.coralblocks.coralqueue.Queue; import com.coralblocks.coralqueue.util.MutableLong; public class Sample { public static void main(String[] args) throws InterruptedException { final Queue queue = new AtomicQueue(1024, MutableLong.class); Thread consumer = new Thread() { @Override public void run() { boolean running = true; while(running) { long avail; while((avail = queue.availableToPoll()) == 0); // busy spin for(int i = 0; i < avail; i++) { MutableLong ml = queue.poll(); if (ml.get() == -1) { running = false; } else { System.out.println(ml.get()); } } queue.donePolling(); } } }; consumer.start(); MutableLong ml; for(int i = 0; i < 10; i++) { while((ml = queue.nextToDispatch()) == null); // busy spin ml.set(System.nanoTime()); queue.flush(); } // send a message to stop consumer... while((ml = queue.nextToDispatch()) == null); // busy spin ml.set(-1); queue.flush(); consumer.join(); // wait for the consumer thread to die... } } 
Interesting Posts

C # использовать System.Type как общий параметр

Печать шестнадцатеричных цифр со сборкой

Создайте загрузочный RedHat iso из папки

Как определить, какой тип слота определен для конкретной PC-карты?

Принудительное видео HTML5 youtube

Есть ли простой способ управления большим количеством условных правил форматирования?

Как получить доступ к имени / значению объекта JSON?

Почему и когда нам нужно связывать функции и eventHandlers в React?

как установить fragment карты google внутри прокрутки

Использовать stream в программировании в vb6

Windows 7 показывает красный значок «X» в сети, но я подключен

Установка обновления Windows 8.1 на учетную запись без администратора?

Возможно ли скорректировать местоположение GeoIP

Получить каталог приложений

Мне нужно заменить мой процессор или материнскую плату, ПК не включается

Давайте будем гением компьютера.