2 сентября 2011 г.

LMAX Disruptor #1: Идеи

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

Для начала исходные данные. Сам проект -- open-source, хостится на google-code, вот здесь http://code.google.com/p/disruptor/. На вики проекта есть страничка, где аггрегируются ссылки на все статьи его разработчиков, где проясняются многие моменты его дизайна и использования. Если вы хотите сами поразбираться -- добро пожаловать. Между прочим один из основных разработчиков, и популяризаторов -- Триша -- женского пола А-а-а, крокодил в ванной женщины в программировании!!! :)

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

Я буду стараться следовать логике разработчиков, комментируя места, которые мне не очевидны. Поехали:

Disruptor -- фреймворк для создания многопоточных конвейеров обработки событий. Из схожих вещей -- Акторы, или просто граф (ориентированный) Producers-Consumers. Классический способ организовать такой граф -- запустить код поставщиков-потребителей в различных потоках, и использовать bounded concurrent/thread-safe queue для создания ребер (неклассический вариант -- упоминавшийся мной фреймворк JetLang) . Именно этот подход и тестировали разработчики disruptor прежде, чем начать изобретать свой собственный велосипед. Производительность этого варианта их не устроила. Почему производительность системы очередей может быть неудовлетворительной (точнее -- значительно ниже теоретического предела), и что мы с этим можем сделать?

Общие принципы


Мы априори принимаем, что любая очередь используемая в production должна быть ограниченной емкости (bounded). В самом деле, если мы допускаем неограниченный рост -- мы допускаем, что наше приложение может в любой момент упасть с OutOfMemory. Если этот вариант нас не устраивает -- нужно задавать явные ограничения.

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

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

В-третьих, желательно, чтобы текущие положения головы и хвоста очереди перемещались по памяти предсказуемым образом. Имеется в виду, что современные процессоры пытаются угадывать паттерн обращений к памяти, которые делает программа, и упреждающе загружать соответствующие данные в кэш. В частности, на данный момент процессоры умеют распознавать паттерн доступа с фиксированным шагом (fixed strides) размером <2Kb. То есть, если наша программа обращается к ячейкам памяти с постоянным шагом, скажем, 128 байт, то через несколько таких обращений процессор начнет понимать, чего мы от него хотим, и заранее запрашивать загрузку очередной такой ячейки (точнее -- строки, ее содержащей) в кэш. Если же наша программа бежит по памяти каким-то более хитрым образом -- процессор уже не осилит его угадать, и мы будем регулярно получать кэш-промахи со всеми вытекающими последствиями для производительности. Мы опять же приходим к выводу, что организация очереди на основе связанных списков менее предпочтительна, чем на основе массива. Это несколько спорные утверждения. Далеко не каждое приложение имеет настолько низкую "фоновую" нагрузку на GC, чтобы дополнительная нагрузка в виде узлов очереди стала заметна -- раз. Можно организовать быстрый пул узлов (тем более раз очередь ограниченного размера -- можно этот пул заранее наполнить) -- два. Можно даже постараться организовать выдачу узлов из пула в некотором определенном порядке, согласованном с их порядком в памяти -- три. С другой стороны все эти обходные пути, конечно, усложняют дело -- трудно судить, насколько они эффективны. Очевидно, имеет смысл рассматривать сначала более простые решения (массив с преаллоцированными ячейками), и только если они не дают нужного результата -- рыть глубже.

Далее -- нам надо стараться минимизировать трафик на межядерной шине interconnect. Для этого нужно стараться избегать параллельной записи в одну ячейку памяти. Более того, в силу существования эффекта false sharing нужно избегать параллельной записи даже просто в близкие ячейки памяти. Кроме того, нужно минимизировать число содаваемых мембаров.
Я еще об этом буду писать подробнее, но предварительно могу сказать, что большая часть хитростей, примененных разработчиками посвящена именно этому пункту -- игре вокруг уменьшения трафика на шине. По-видимому, это один из ключевых моментов в том, как disruptor зарабатывает свою рекордную производительность.

Архитектурные идеи


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

Можно заметить, что если использовать очереди для соединения узлов графа, то в каждом узле мы вынуждены делать столько операций dequeue/enqueue, сколько выходящих/выходящих ребер у этого узла. Каждая операция enq/deq на конкурентной очереди -- это операция изменения разделяемого состояния -- а это барьеры памяти и трафик на межпроцессорной шине. Однако enc/deq редко когда бывают в самом деле нужны -- обычно очередной обработчик вовсе не "забирает" очередное событие себе, а лишь "берет попользоваться" и вскоре "отдает назад" (иногда -- модифицировав его как-то). И вся топология графа обработчиков состоит в том, что одни обработчики должны отработать гарантированно прежде других -- т.е. должен соблюдаться какой-то порядок вызова обработчиков.

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

Эта идея не кажется чем-то особенным, пока мы не заметим одну тонкость. Предположим пока, что производитель у нас один-единственный. У нас есть набор курсоров, по одному на каждого участника конвейера. Эти курсоры по сути, и составляют разделяемое состояние конвейера. Любой шаг -- что производителя, что обработчика -- изменяет один из курсоров. Но каждый участник меняет только свой курсор -- чужие курсоры он только читает! То есть у нас получается лучший возможный паттерн работы с разделяемым состоянием -- полное состояние конвейера распадается на несколько частей, и у каждой части один писатель и много читателей.

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

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

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

P.S. Чтобы не казалось, что все вообще радужно -- не все, что можно реализовать очередями, можно реализовать эффективно с помощью Disruptor. Первый же попавшийся мне на глаза пример -- автоматическая балансировка нагрузки. Эту штуку элементарно сделать с помощью одной-единственной очереди -- в один конец сколько угодно поставщиков кладут некие задачи, с другого конца N потоков-обработчиков (где N = числу ядер в системе) их разбирают. Нагрузка балансируется по отдельным потокам автоматически -- если кому-то почему-то достаются более легкие задачи, этот кто-то просто быстрее возвращается за новыми. С помощью Disruptor такую штуку не реализуешь -- для каждого обработчика явно, при конструировании конвейера, задано, какие события он получит. Полученные им события никак не будут зависеть от относительной загрузки различных элементов конвейера -- отстающих просто будут ждать. Конечно, никто не помешает создать 10 одинаковых обработчиков, каждый из которых будет обрабатывать лишь одно событие из 10, и пропускать остальные -- но это не будет автоматическим балансированием нагрузки, это будет балансированием числа событий.

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

  1. Честно говоря, я не вижу, чем особенно восхищаться в disruptor'е: по-моему, это адский велосипед. Их перформансное сравнение [1] между disruptor и ArrayBlockingQueue меня повергло в тихий шок: в ABQ сидит один большой ReentrantLock, который охраняет доступ к очереди, а он как известно паркует поток после первого же неудавшегося CAS'а. Ясен пень, что тривиальный непаркующийся алгоритм порвёт ABQ как тузик грелку и по throughput, и по latency.

    А вот если в ABQ положить лок, который будет бесконечно спинниться без парковки, плюс сделать его не бешеными CAS'ами, а вариантом TTAS (Test-and-CAS), то получатся те же самые высокопроизводительные яйца. Сама мысль мысль про "давайте нотифицировать барьером" заложена в конструкции TTAS-a.

    О каком контеншене на head/tail очереди можно говорить, если в подавляющем большинстве сценариев у каждой очереди по одному клиенту на head и tail? Даже если принять, что это есть проблема, как отличается ожидание апдейта сиквенса producer'а от ожидания апдейта в TTAS-e на tail'e очереди? Всё равно придётся по шине этот апдейт пробить во все кеши на всех процах, и всё равно его придётся ждать.

    Я отдельно похихикал о том, что у них не получилась J-curve для зависимости latency от load'a. Конечно, когда все клиенты только и заняты тем, что обсцессивно ждут в локальных busy-loop-ах следующего элемента, и не делают вообще ничего другого, то никакой интерференции между ними нет, и они друг другу никогда не мешают. Это, понятно, тут же перестанет выполняться, как только в обработчиках появится мало-мальски полезный код. К великому сожалению, это большая проблема с любым спиннингом: понять, как долго спинниться. Может оказаться, что выгоднее как раз запарковаться, и не жечь зря циклы. Мерить производительность этих вариантов на пустых обработчиках глупо: ибо с ними бизнес-логика не конкурирует.

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

    Батчинг в disruptor'е работает из-за ослабленной consistency: может оказаться, что конкретный элемент вычитан вычитан несколькими consumer'ами сразу, и иди ты разбирайся как со этим всем жить -- балансировка идёт лесом. Эта задача проверки уникальности элемента, кстати, сводится к известной теореме Herlihy/Shavit'а: если есть произвольное количество потоков, которые должны получить одинаковый результат из одновременного вызова T makeConsensus(T myOwnBet), такой консенсус НЕЛЬЗЯ разрешить при помощи ТОЛЬКО атомарных чтений/записей (это слишком слабые примитивы)

    [1] http://code.google.com/p/disruptor/wiki/PerformanceResults

    P.S. Кстати, хотел с тобой поговорить насчёт Java performance, есть какой-нибудь живой голосовой контакт?

    ОтветитьУдалить
  2. Оффтоп: интерфейс комментариев в блоггере то уродство -- и как ты не поленился в нем столько текста набирать...

    >Их перформансное сравнение [1] между disruptor и ArrayBlockingQueue меня повергло в тихий шок:

    Это меня тоже немного удивило -- т.е. где-то в статьях у них есть какой-то посыл типа "а остальные очереди и еще хуже" -- но звучит это не впечатляюще. И да, я тоже заметил, что если смотреть disruptor в топологии A->B то ничего собо волшебного нет -- просто аккуратно реализованная circular array backed queue. Даже подумывал реализовать простейший вариант такой очереди, и подставить в бенчмарки вместо ABQ. Я понял эту часть так, что "обычным" разработчикам такая очередь недоступна -- в JDK-то ее нет (или я не заметил?), а самому писать со всеми этими тонкостями не каждый возьмется. Даже то, что TСAS эффективнее обычного CAS -- штука уже не самая очевидная, лично я до нее сам не допер, меня AMP наставил на путь истинный.

    >О каком контеншене на head/tail очереди можно говорить

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

    > предсказуемый батчинг работает тогда, когда есть единственный отстающий потребитель,

    Тут я уже тебя не понимаю. С бэтчингом вроде все честно -- за один volatile write курсора мы можем обработать столько записей, сколько их нам доступно до ближайшего курсора "спереди". Скажем, есть у нас один производитель и 4 обработчика в единую цепочку (каждый строго за предыдущим). Производитель сидит на сетевом интерфейсе и курит бамбук -- а потом ему раз -- и 50 сообщений в одном сетевом фрейме, как с куста. Он эти 50 сообщений опубликует за 1 volatile write всего. Следующий обработчик резко стартует из busy-wait, обнаруживает, что он отстал от батьки на 50 сообщений, обрабатывает их, и опять же в один volatile write обновляет свой курсор. И так по цепочке -- все 5 участников конвейера обработают эти 50 сообщений за 5 volatile write. Довольно экономно -- быстрее я не придумаю.

    Конечно, с очередью тоже так можно исхитриться -- ввести некий BatchEvent например -- но это будет не совсем то, потому что его постоянно придется переупаковывать -- разные обработчики могут ведь на разное количество событий отставать. Обычная же j.u.Queue методов типа takeAll() не содержит. Eсть BlockingQueue.drainTo() -- но тут я предвижу обвинения в создании дополнительной нагрузки на GC :), да и копирование, хоть и дешево, но не бесплатно.

    Если опустить промежуточные варианты -- нужно либо писать специальную single enqueuer-single dequeuer очередь, с нестандартным интерфейсом -- тогда можно и пакетную запись за один v-write реализовать, и пакетное чтение. Либо писать multy-enc-multy-dec очередь, но опять же с нестандартным интерфейсом с методом типа forEachAvailable(Function). То есть мы опять же упираемся в то, что "стандартных" методов получить такой результат -- нет.

    ОтветитьУдалить
  3. >Батчинг в disruptor'е работает из-за ослабленной consistency: может оказаться, что конкретный элемент вычитан вычитан несколькими consumer'ами сразу, и иди ты разбирайся как со этим всем жить -- балансировка идёт лесом

    Тут я тебя тоже не до конца понял. Если ты имеешь в виду, что нельзя использовать disruptor для балансировки нагрузки -- то да, я же про это в посткриптуме писал. А в остальном упорядочивание обработчиков по курсором вполне строгое, насколько я могу судить -- я не вижу как следующий обработчик может получить доступ к событию до того, как с ним закончит предыдущий. Предыдущий ведь обновляет свой курсор _после_ того, как закончит с очередным элементом, а последующий начинает работу только _после_ того, как увидит новое значение курсора -- порядок обеспечивается HB-ребром между v-write и v-read курсора.

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

    Кроме того лично для меня важно, что он достаточно простой. Т.е. когда я пытаюсь понять что-нибудь, написаное Daug Lea, то исходную его статью-то я еще худо-бедно понимаю, но вот когда я код начинаю читать -- у меня возникает кризис самооценки и я сбегаю пить, танцевать и клеить девок. Здесь же вроде бы все можно понять -- поэтому я ухватился за Disruptor в плане подробно разобрать и проанализировать.

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

    P.S. Честно говоря, с голосом я не очень дружу. Т.е. скайп-то у меня есть -- chereminruslan -- но я там без повода очень редко бываю, так что надо оговорить время заранее.

    ОтветитьУдалить
  4. > Оффтоп: интерфейс комментариев в блоггере то уродство -- и как ты не поленился в нем столько текста набирать...

    А меня ненадёжный интернет давно научил писать комменты в простых текстовых редакторах, а потом копипастить ;)

    > предсказуемый батчинг работает тогда, когда есть единственный отстающий потребитель,

    > Тут я уже тебя не понимаю. С бэтчингом вроде все честно -- за один volatile write курсора мы можем обработать столько записей, сколько их нам доступно до ближайшего курсора "спереди". Скажем, есть у нас один производитель и 4 обработчика в единую цепочку (каждый строго за предыдущим)

    А, прости. С моей точки зрения конвеер "производитель -> обработчик-1 -> обработчик-2 -> обработчик-3" это всё равно что "писатель1 -> читатель1+писатель2 -> читатель2+писатель3 -> читатель-3". Мой коммент не про конвеер из нескольких читателей-писателей, а про ситуацию один писатель/несколько читателей.

    Проблема в координации: если ты не синхронизируешься, то несколько читателей прочитают некоторые сообщения несколько раз. Поэтому у тебя есть три варианта:
    а. ты гарантируешь, что читатель единственный, и тогда не надо публиковать апдейт своего курсора каждый раз. В этом случае специализированная очередь, которая вычитывает всё, пока не упрётся в tail, а потом делает volatile write и локается, обеспечивает ту же семантику (это ты уже предложил)
    б. ты не можешь гарантировать, что читатель единственный, и не можешь разрешить читать дубликаты, тогда нужно синхронизироваться после сдвига локального курсора (опять замечу, что в связи с упомянутой выше теоремой просто барьеров для этого недостаточно, нужен CAS)
    в. ты не можешь гарантировать, что читатель единственный, но разрешаешь читать дубликаты. Это путь disruptor'а. При этом нет никаких условий и оценок, сколько таких "мульти-чтений" возникнет, и это главный геморрой с любым distruptor-like алгоритмом.

    Поэтому я говорю, что "предсказуемо" и быстро эта схема работает, когда есть только один читатель на одного писателя. По этому поводу, кстати, вообще сравнивать disruptor с очередями нельзя: очереди предоставляют гораздо более строгие гарантии (идут по плану "б").

    Поэтому мне довольно странны сравнения и восхищения по поводу distruptor'а: король-то голый :)

    ОтветитьУдалить
  5. > В общем, как я себе это вижу -- открытия Disruptor может и не сделал -- но это довольно удобный фреймворк для организации конвейеров произвольной топологии.

    Да понимаешь ли, я как раз спорю о том, что его применимость весьма ограничена. С busy-loop'ами он жрёт дофига throughput'а ради наносекундных латентностей (ну кому блин это нужно, кроме HFT'шников?), с обычными локами деградирует до дефолтовых JDK-овых очередей.

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

    Это потому что в JDK довольно консервативный код :) Мы с Дагом это уже триста раз перетирали, что пора бы элементарный спиннинг сделать в ReentrantLock'ах: это бы, кстати, сильно улучшило позицию ABQ против disruptor'а, но Даг протестует против изменений, которые колеблют предсказуемость производительности j.u.c.*. Есть одна отдушина: jsr166e, куда мы собираем новые примитивы для Java 8, там есть простор для творчества :) SequenceLock, например, наконец содержит в себе спиннинг.

    > Кроме того лично для меня важно, что он достаточно простой. Т.е. когда я пытаюсь понять что-нибудь, написаное Daug Lea, то исходную его статью-то я еще худо-бедно понимаю, но вот когда я код начинаю читать -- у меня возникает кризис самооценки и я сбегаю пить, танцевать и клеить девок.

    А ты знаешь, какой у меня охреневайтунг наступает, когда я с ним спорю? Тем не менее, при достаточном количестве алкоголя в крови тот код читается вполне себе нормально: и многие даговские решения имеют за собой хорошую историю. Например, повальное использование AtomicFieldUpdater'ов вместо AtomicX меня поначалу убивало.

    > Я тут с тобой вроде как спорю :) Но на самом деле за комментарий тебе большое спасибо, многое проясняет. Я бы сам даже если дошел -- долго сомневался бы.

    Мгм. А я тут не истина в последней инстанции, могу ошибаться. ;) Особенно, если умножить это на то, что я не люблю HFT'шные извращения, а также тонкий инжиниринг, рекламируемый как серебряный патронташ. Я бы, наверное, гораздо теплее относился к disruptor'у, если бы товарищи не превращали его в маркетинговый миф.

    > P.S. Честно говоря, с голосом я не очень дружу. Т.е. скайп-то у меня есть -- chereminruslan -- но я там без повода очень редко бываю, так что надо оговорить время заранее.

    Собственно, нужно минут 10-15. Пиши на aleksey[dot]shipilev[ну-тут-сам-знаешь]гуглопочта, либо в джаббер, либо письмом.

    ОтветитьУдалить
  6. > В общем, как я себе это вижу -- открытия Disruptor может и не сделал -- но это довольно удобный фреймворк для организации конвейеров произвольной топологии.

    Да, вот мне пришла мысль в голову: а какого чёрта вообще нужно устраивать конвеер, если это цепочка одиноких обработчиков? Зачем устраивать эту возню с передачей данных от одного потока к другому? Если стадии прекрасно сбалансированы, то почему бы их все не выполнить сразу в одном потоке? Если конкретная стадия оттормаживает, то пусть вместо бешено спинящихся потоков-"до"/"после" конкретные потоки-исполнители и тормозят на этой конкретной стадии.

    Максимум что можно придумать, это работа с DAG'ами конвееров, когда хочется сделать "A -> (B || C) -> D", зная, что B и C ужасно тормозные, но независимые. Но в этом случае банальный Fork/Join будет как раз в струю: оверхед от work stealing'а будет очень мал по сравнению с долгим (по определению) вычислением в B или C. Если же оказывается, что этот оверхед сравним с продолжительностью вычисления, значит, ты пытаешься выжать последние сотни наносекунд [irony on], и должен быть предан огню как и любой HFT'шник, ведущий нас к пропасти финансового Скайнета.[irony off]

    ОтветитьУдалить
  7. >в. ты не можешь гарантировать, что читатель единственный, но разрешаешь читать дубликаты. Это путь disruptor'а.

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

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

    >По этому поводу, кстати, вообще сравнивать disruptor с очередями нельзя

    Таки да. Но с чем его сравнивать? Они сравнивают с тем, что доступно обычному разработчику, из чего он, скорее всего, будет собирать подобную штуку, если она ему понадобится. Здесь есть много от маркетинга, да.

    >Да понимаешь ли, я как раз спорю о том, что его применимость весьма ограничена.

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

    >Это потому что в JDK довольно консервативный код :)

    На самом деле лично я это только приветствую. Стыдно признаться, но я до сих пор половину существующего j.u.c не изучил толком -- потому что без подробностей реализации я их использовать не готов, а подробности за минуту не изучишь.

    >Тем не менее, при достаточном количестве алкоголя в крови тот код читается вполне себе нормально: и многие даговские решения имеют за собой хорошую историю

    Вот это типичная штука -- не зная этой истории сложно понять почему здесь именно такое наслоение решений.

    >Да, вот мне пришла мысль в голову: а какого чёрта вообще нужно устраивать конвеер, если это цепочка одиноких обработчиков?

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

    >Собственно, нужно минут 10-15.

    Я с удовольствием, но уже завтра - засыпаю.

    ОтветитьУдалить
  8. >>Да, вот мне пришла мысль в голову: а какого чёрта вообще нужно устраивать конвеер, если это цепочка одиноких обработчиков?
    > Тут я тебя опять не понимаю. Есть у меня 8 ядер, и на каждом из них по обработчику (на одном -- производитель).

    А зачем? Допустим есть K задач, которые тебе надо обработать, каждая из этих задач может быть разбита на M последовательных подзадач. Обозначим m-тую подзадачу k-той задачи как P[k][m]. Теперь есть N свободных потоков, обозначим каждый поток T[n].

    Мой спич о том, что какого чёрта раскладывать на каждый T[n] подзадачи P[?][n], и в каждом потоке терять на ожидании результата P[?][n-1], когда можно на каждый T[n] положить все подзадачи P[k mod n][?] сразу? Если конвеер сбалансирован, то есть продолжительность P[?][m] примерно одинакова, то throughput будет такой же или даже лучше (тебе всё равно нужно каждую подзадачу посчитать, а сделать это в одном треде с лучшей cache locality куда круче, и т.п. к вопросу о лишних мембарах), latency будет как минимум той же (всё равно нужно будет потратить то же время, чтобы каждую подзадачу решить).

    Если конвеер не сбалансирован, и конкретная P[?][m] оттормаживает (это, кстати, самый частый вариант), в disruptor-like дизайне ты упираешься в производительность отдельного потока, и нет никого, кто мог бы ему помочь, все в сторонке в бизи-вейтах ждут, пока тот всё-таки что-нибудь родит. В сравнении со случаем, когда все N воркеров пришли и начали параллельно делать эту P[?][m] для многих P[?] одновременно: это патологический случай.

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

    ОтветитьУдалить
  9. >Мой спич о том, что какого чёрта раскладывать на каждый T[n] подзадачи P[?][n], и в каждом потоке терять на ожидании результата P[?][n-1], когда можно на каждый T[n] положить все подзадачи P[k mod n][?] сразу?

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

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

    Что касается кэш-локальности тут тоже не все однозначно. Да, приходящие данные будут более горячими в кэше если каждую команду обрабатывать отдельным потоком. А фоновые данные? Если для выполнения обработчика №3 нужно 25 байт самой команды и 1Мб "окружающей среды" в которую он вносит изменения?

    В самом LMAX же основной цикл бизнес-логики, как я понял, висит одним из обработчиков на этом самом disruptor-е. Все данные у них закэшированы в оперативке, и все изменения в них вносятся этим самым обработчиком. И благодаря тому, что обработчик однопоточный, им а) не приходится возиться с thread-safety б) данные "мира" всегда горячие в кэше этого конкретного потока. Они представляют дело так, что именно потому им удалось всю бизнес-логику реализовать в одном потоке и она не тормозит.

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

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

    Эта модель, конечно, не для всех подходит -- но для OLTP самое оно. Другое дело, конечно, что авторы-то особо не расписывают где и когда их систему имеет смысл применять -- ну так может еще дойдет время, не все сразу.

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