21 апреля 2012 г.

...расследования

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

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

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

Так вот, если это среднее расстояние таково, что записываемые издателем сообщения находятся на другом кэш-лайне, чем читаемые подписчиком -- то все шоколадно, контроллер памяти работает в приемлемом режиме. А вот если расстояние окажется слишком маленьким -- издатель и подписчик будут работать в пределах одного кэш-лайна. А значит -- контроллер памяти будет играть в пинг-понг: издатель будет для записи требовать кэшлайн в в своем кэше в состоянии M, а читатель -- в своем, в состоянии S. Да, это типичный пример false sharing.

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

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

Интересная штука -- когда курсоры идут плотно друг к другу пропускная способность падает. А вот время ответа (latency) -- скорее всего тоже будет падать. Я его не измерял, но кажется очевидным, что чем меньше расстояние между первым и последним курсором в цепочке -- тем быстрее конкретное сообщение будет полностью обработано. А это значит, что бэтчинг здесь это такой размен throughput<->latency. Можно чуть поднять throughput, но ценой увеличения времени обработки одного сообщения. Можно чуть уменьшить время ответа -- но ценой падения и пропускной способности (==менее эффективного использования шины interconnect-а).


И смотрите, как любопытно выходит (дальше мои довольно умозрительные рассуждения): почти наверняка замедление работы в subscriber-batching будет проявляться только в ненагруженном режиме. В нагруженном режиме скорость движения курсоров определяется не их механикой, а нагрузкой -- курсоры двигаются настолько быстро, насколько обработчик успевает делать свою работу. А это значит, что система будет самоподстраивающейся: если нагрузки немного, и обработчики успевают все перемолоть быстро -- они догонят издателя, и будут идти за ним ноздря в ноздрю, уменьшая время ответа. Как только нагрузка вырастает, обработчики начинают не справляться с работой так быстро -- и отстают от издателя. А это сразу дает им чуть-чуть продохнуть за счет более эффективного бэтчинга (больше сообщений за раз) и за счет большего КПД использования interconnect-а. Все это, разумеется, в некоторых, небольших, пределах -- серьезное изменение нагрузки так не скомпенсируешь. Можно даже примерно прикинуть, насколько небольших: худший режим с бэтчингом у нас 15 000 пакетов/мс (~70 нс/пакет), лучший без бэтчинга 35 000 (~30нс/пакет). Разница в 40 нс -- это и есть оценка того, сколько может нам сэкономить сам Disruptor за счет автоматического перехода между режимами.

UPD: Как мне тонко намекнули в комментариях, я забыл важную часть -- гипотеза-то ценна не сама по себе, а тем, что она имеет экспериментальные подтверждения! А именно: если причина ухудшения пропускной способности при включении бэтчинга и нестабильности работы -- действительно такая, как я предположил, то должна быть корреляция между средним расстоянием между курсорами (а схеме это обозначено как gap), и пропускной способностью в конкретном эксперименте. Это можно проверить, и я это проверил. Результат -- вот он (по X -- gap, по Y -- throughput):


По-моему, все очень наглядно. Скачок производительности происходит как раз в области gap=2.5-3.0 Это отлично коррелирует с тем фактом, что размер сообщений у меня примерно 24 байта, т.е. их на 64-байтный кэшлайн умещается как раз чуть меньше 3 штук.

UPD#2: По многочисленным просьбам трудящихся числом 2 -- бенчмарки с пэддингом сообщений. Без batching 19 789 (+/- 483), с batching 20 488 (+/- 1 277).

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

  1. чего я не понял - где возникает пинг-понг - на элементах D. или на твоём экспериментальном Queue ?
    если на D то как же padding ?

    ОтветитьУдалить
  2. false sharing возникает на объектах сообщений в D. Пэддинг в D присутствует только для _курсоров_ -- сами сообщения оставляются на откуп пользователям фреймворка. На форумах Д вроде обсуждалась тема про пэддинг самих сообщений, но в большинстве случаев это не нужно -- в продакшене редко когда удастся осмысленное сообщение впихнуть менее чем в 64 байта.

    Т.е. такое поведение -- это артефат ненагруженного бенчмарка с ультралегкими сообщениями. В реальной жизни и сообщения сами будут больше кэшлайна, и скорость курсоров будет определяться нагрузкой. И тогда бэтчинг _скорее всего_ будет, как ему и положено, оптимизацией.

    ОтветитьУдалить
  3. может стоит попробовать добавить padding в твои entries и проверить гипотезу ?

    ОтветитьУдалить
  4. Так это не гипотеза -- у нее и так есть экспериментальные подтверждения, я ж в докладе об этом говорил.

    И потом -- код я выложил, попробуй ;)

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

    ОтветитьУдалить
  5. Будет ли такой же эффект возникать в ArrayBlockingQueue? При расстоянии между хвостом и головой в 2-3 элемента должен сработать тот же самый false sharing? Тогда получается, что LinkedBlockingQueue быстреедолжна быть?

    ОтветитьУдалить
  6. Будет ли -- я не знаю. Но здесь есть еще хороший вопрос -- будет ли заметен этот эффект для ABQ. false sharing присутствует в огромном количестве кода, как в JDK так и third-party. Но это огромное количество кода от false sharing не страдает -- оно им наслаждается :)

    Просто пока у вас код работает на уровне КПД использования подсистемы памяти в 5% -- вам и на false sharing, и на single writer положить с пробором. Можно -- и нужно -- просто не париться. Преждевременная оптимизация -- корень всех бед, и все такое. А вот когда вы уже подходите к КПД процентов в 30-40 хотя бы, и хотите идти дальше -- у вас возникают вопросы типа "а кем же, вашу мать, заняты остальные 60% шины памяти". И вот тогда ответом на эти вопросы может являться "а у вас здесь вот false sharing, и 60% шины занято обслуживанием вашей непредусмотрительности"

    Возвращаясь к ABQ -- не забывайте, что ABQ синхронизируется единым ReentrantLock-ом. И он сам уже является источником большого memory contention -- это, в данном случае, будет true sharing, потому что так и задумано разработчиком -- но легче контроллеру памяти от этого не станет. Но важнее здесь то, что если очередь становится почти пуста -- с заметной вероятностью потоки начнут парковаться, выбывая из игры и снижая тем самым contention. Другими словами -- с ABQ вы просто не сможете достигнуть того уровня нагрузки (memory contention) на котором эффекты false sharing начнут сказываться.

    А LBQ действительно может в определенных случаях быть быстрее ABQ -- совсем недавно я писал о конкретном примере. Но дело здесь, кмк, просто в том, что в LBQ два лока, на хвост и на голову отдельно. Ну и не надо забывать, что LBQ плодит мусор, что под высокой нагрузкой может оказаться существенным

    ОтветитьУдалить
  7. небольшой доклад о дизрупторе от авторов http://www.infoq.com/presentations/Lock-free-Algorithms

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