10 августа 2015 г.

Left-Right

Пару лет назад ребята из concurrency freaks опубликовали в c-i описание интересного алгоритма управления конкурентным доступом к произвольной структуре данных. Они назвали этот алгоритм Left-Right, и утверждали, что он позволяет реализовать blocking writes, но зато аж wait-free (population oblivios) reads. При этом писатели не блокируют читателей, хотя читатели блокируют писателей (но не блокируют друг друга). Это довольно-таки неплохой набор свойств, особенно учитывая, что защищаемя структура данных может быть любой. Сценарий с редко обновляемой, зато часто читаемой структурой данных очень типичен, и обычно в нем используется что-то вроде CopyOnWrite — очень простой и надежный алгоритм, но требующий аллокации. Здесь же аллокаций после инициализации нет вообще (в самом алгоритме — если защищаемая структура данных нуждается в аллокациях при выполнении над ней каких-то операций, то эти аллокации, конечно, никуда не исчезнут). Тогда у меня не дошли руки описать их алгоритм, зато дошли сейчас :)

Идея алгоритма (статья в pdf) довольно простая: мы заводим две копии (left & right) нужной нам структуры данных. Одна из копий всегда открыта для чтения, вторая, соответственно, спрятана от читателей. Поток, желающий выполнить операцию чтения должен просто определить, какая из копий открыта, и читать ее. Пишущий же поток захватывает глобальный монитор, и сначала модифицирует скрытую копию. Выполнив запись над скрытой копией писатель делает ее открытой для чтения, а бывшую открытую — скрывает, и повторяет свою запись теперь уже над ней. В итоге одна копия всегда свободна от записей, и ее можно безопасно читать, и одна копия всегда свобода от чтения, и ее можно безопасно модифицировать (под блокировкой, конечно — чтобы не конфликтовать с другими писателями), и после каждой операции записи копии меняются ролями.

Идея простая, но в реализации есть тонкости. Одномоментно сменить открытую копию просто — достаточно обычной volatile ссылки/индекса (и даже не нужно CAS-а, потому что запись и так происходит под блокировкой, и обновлять этот указатель может только один поток в каждый момент времени). Но после того, как мы перенаправили эту ссылку, и бывшая открытая копия стала закрытой — мы пока еще не можем утверждать, что нынешнюю закрытую копию никто не читает, ведь это только новые читатели пойдут по обновленной ссылке, а старые, которые начали чтение до смены ролей, все еще читают копию, которая сейчас уже закрыта. Значит, нам нужен какой-то механизм, позволяющий дождаться, пока все эти старички закончат читать. То есть нужно, чтобы потоки-читатели где-то отмечались “я сейчас читаю копию номер 1”, и чтобы писатель мог спросить “а есть ли хоть кто-то, кто читает копию номер 1?"

Реализация этого механизма регистрации читателей — это ключевая вещь в Left-Right, потому что от его эффективности и progress conditions прямо зависит эффективность и progress condition операций чтения — а неждущие чтения это, пожалуй, основная заявка всего алгоритма. В самом простейшем случае можно просто завести readersCount:AtomicInteger на каждую копию, и каждый читатель будет делать readersCount.incrementAndGet() перед началом чтения, и .decrementAndGet() после окончания, и если readersCount.get() == 0 значит активных читателей не осталось. Этот способ регистрации читателей самый простой, и самый компактный по памяти — но он мягко говоря не очень хорошо масштабируется с увеличением количества читателей, ведь все читатели будут конкурировать за обновление одного участка памяти (true sharing).

Ситуацию можно улучшить, если начать дробить единый счетчик на несколько более мелких: каждый поток-читатель приписан к какому-то суб-счетчику (не обязательно навсегда к одному и тому же, кстати), и инкрементит/декрементит его, а поток-писатель должен тогда будет обойти все суб-счетчики, и просуммировать их значения, чтобы получить итоговую сумму (отдельные суб-счетчики, конечно, нужно хорошенько изолировать друг от друга padding-ом, чтобы не налететь сходу теперь уже на false sharing). В пределе, если на каждый поток-читатель выделить свой собственный суб-счетчик, мы получим полное отсутствие конкуренции за запись (технически нужно еще обеспокоиться еще отсутствием false sharing) — по-сути записи будут чисто локальными для каждого из потоков, и тогда даже CAS/atomicAdd нам не нужно, мы можем обновлять волатильный локальный счетчик обычным инкрементом/декрементом (очень изящную реализацию на базе односвязного списка, слабых ссылок, и thread local-ов можно посмотреть здесь). И значит мы получим-таки заявленное свойство wait-free population oblivios. По цене ~64+ байт на каждый читающий поток (padding + сам счетчик + дополнительные поля — и не забываем, что пишущий поток еще будет обязан все эти локальные счетчики обойти и просуммировать)

(Небезызвестный LongAdder из последних версий jdk использует похожий подход, но он всего лишь lock-free. Почему? Потому что пытается балансировать между скоростью и потреблением памяти — если на каждый поток сразу по 64+ байт выделять — никакого кэша не хватит. Так что LongAdder подстраивает количество счетчиков под реальную нагрузку — он начинает с одного счетчика (общего для всех потоков), который обновляется через CAS. Если неудачных CAS-ов становится много — это значит, что за счетчик идет слишком большая конкуренция, и LongAdder увеличивает количество суб-счетчиков, стараясь равномерно распределять потоки между ними. Покуда неудачных CAS-ов все еще много — количество счетчиков еще увеличивается, пока их не окажется столько, чтобы за каждый конкретный счетчик конкуренция была ниже некого предела. Очень изящное, эффективное, и гораздо более универсальное решение — но вся эта машинерия динамической перестройки, увы, уже не вписывается в wait-free)

(Любопытная деталь: чтобы получить конкурентный алгоритм с наиболее “хорошими” свойствами для читателей, в ущерб писателям, нам оказывается нужен, в качестве строительного блока, алгоритм счетчика с наиболее “хорошими” свойствами для писателей, в ущерб читателям)

Довольно очевидно, что алгоритм близок идейно к CopyOnWrite, только в CoW количество копий не ограничено, а за количеством читателей следит GC — пока на какую-то из копий хоть из одного потока есть ссылка, эта копия считается занятой, как только ни одной ссылки не остается — копию подбирает GC, и ее память заново можно использовать для аллокации. За эту простоту приходится платить — алгоритмы определения достижимости у GC обходятся гораздо дороже по CPU, чем смена читаемой копии в LR, да к тому же теряется детерминированность. Плюс вместо дублирования одной конкретной записи мы вынуждены при реаллокации копировать все содержимое структуры данных целиком.

Что в алгоритме LR еще интересного? Интересно то, что его основной недостаток — блокировка для писателей — не актуален, если писатель у нас один. Поскольку блокировка нужна только для разруливания конфликтов между писателями, то в случае одного писателя ее можно просто выкинуть. И мы получаем алгоритм с wait-free писателем, и wait-free (или lock-free если мы пожадничаем на память для счетчиков) читателями. Хотя стоп, писателю же все равно придется ждать завершения всех чтений? Да, никакого wait-free не получится, писатель все равно остается блокирующимся, просто монитор захватывать в этом случае не нужно.

Второй интересный аспект это пакетная запись. Если нам не принципиально предоставлять читателям свежую версию максимально быстро — мы можем переключать копии между открытой на закрытой не после каждой записи, а, скажем, после какого-то их числа, или по явной команде, типа commit/flush. И тогда высокая стоимость записей может быть амортизирована на всю пачку. В том числе и блокировку можно брать лишь однажды и на всю пачку (или вообще не брать — если писатель один-единственный). От необходимости выполнять каждую запись дважды это нас не избавит, но все остальные накладные расходы можно сильно размазать.

Третья идея — а что, если копий сделать больше одной? В пределе неограниченного количества копий мы приходим к классическому CopyOnWrite + GC, но что если копий все-таки ограниченное количество? В оригинальной статье этот вариант не рассматривается, но насколько я вижу, это вполне можно реализовать. Здесь есть интересный вариант: мы можем, как и в оригинальном LR применять каждую запись N раз, к каждой копии. А можем вместо этого при модификации копировать все содержимое самой свежей копии (текущей читаемой) в самую старую (будущую читаемую), и применять текущую запись уже поверх. (Очевидно, что при большом N этот способ рано или поздно станет более эффективным).

То, что у нас здесь получится — это натуральный CopyOnWrite, только без аллокации и GC, и с ограниченным набором копий. В чем его потенциальные преимущества? По сравнению с обычным CoW нет постоянной реаллокации (но все же есть копирование). А вот по сравнению с LR преимущество в том, что для выполнения записи нам не нужно дожидаться завершения всех чтений над только-что-переставшей-быть-открытой копией — потому что сейчас нам в нее ничего писать не нужно. Пишем (копируем свежее состояние + применяем текущую запись) мы в самую последнюю (самую дальнюю от текущей) копию, и именно она должна быть свободна от читателей. Но поскольку эта дальняя копия была открытой для чтения уже довольно давно, то вероятность, что ее все еще кто-то читает (т.е. есть кого ждать) довольно мала, и ее можно уменьшать далее увеличивая количество копий.

Мы получаем такую версионную структуру данных, которая одновременно содержит черты CoW, кольцевого буфера (ну, потому что копии организованы натурально в виде кольцевого буфера), и LR. Без аллокаций, с wait-free чтением (если не жалко по 64+ байт кэша на каждый читающий поток потратить), и с блокирующейся записью — но при этом вероятность ожидания на записи можно регулировать увеличивая количество копий. Интересная штука, правда, очень сложно поверить, что эту структуру данных еще никто не придумал :)

22 комментария:

  1. Есть вопросы по реализации EnterExitWait. Возможно, если сделать достаточно жирный striping, как в LongAdder, но статический (допустим, зависящий от кол-ва CPU в системе, или конфигурируемый), амортизированные затраты на редкий sharing будут меньше, чем цена хождения в ThreadLocal при _каждом_ чтении.

    Еще, я бы не делал Thread.yield() сразу

    ОтветитьУдалить
    Ответы
    1. Если мы подходим с формальной точки зрения, то пока у нас есть CAS+retry у нас только lock-free, но не wait-free. Обойтись без CAS можно только гарантировав single writer -- то есть гарантировав принадлежность счетчика одному-единственному потоку.

      С технической точки зрения, конечно, вся эта иерархия progress conditions это лишь полезная абстракция, со своими границами применимости. Хорошо написанный блокирующийся алгоритм легко может уделывать по производительности плохо написанный wait-free. Поэтому Даг Ли предпочитает почти lock-free LongAdder чистому wait-free.

      Про ThreadLocal я не понял тебя -- где-то же надо хранить id текущего потока, по которому ты будешь определять, какой счетчик ему обновлять? Самое эффективное хранить на стеке, но это не вариант для универсального алгоритма, реализованного как хорошо инкапсулированный библиотечный примитив, не требующий ничего особого от клиентов (как RWLock, например). Так что ThreadLocal...

      (Пару лет назад Натан приходил в c-i с идеей (сомневаюсь, что сильно свежей) про ProcessorLocal как альтернативу ThreadLocal (точнее было бы сказать HardwareThreadLocal как альтернативу нынешнему SoftwareThreadLocal). Если бы была возможность быстро и дешево получать в яве hardware thread id, то те же самые счетчики можно было бы создавать не под каждый программный поток, а только под каждый аппаратный, потому как реальная конкуренция за выполнение модифицирующих память инструкций может быть только между аппаратными потоками. Но не сложилось -- точно уже не помню почему, но инструкции такой в яве нет, да и, кажется, на машинном уровне аналогичная инструкция не такая уж дешевая. В любом случае, с ростом количества аппаратных потоков эта идея становится все менее привлекательной)

      Мне кажется, что если уж говорить про недостатки, то главный недостаток здесь это то, что чтение все-таки требует для своей организации _записи_. Если вспомнить StampedLock, то вот он уникален как раз тем, что там, в оптимистичном варианте, удается прочитать ничего не записав.

      >Еще, я бы не делал Thread.yield() сразу

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

      Удалить
    2. > Если мы подходим с формальной точки зрения, то пока у нас есть CAS+retry у нас только lock-free, но не wait-free. Обойтись без CAS можно только гарантировав single writer -- то есть гарантировав принадлежность счетчика одному-единственному потоку.

      Moжно использовать getAndAdd[Int, Long] => xadd, в этом упрощенном striped счетчике, и будет даже wait-free. Кстати мне не вполне понятно, почему LongAdder не использует getAndAddLong().

      > Про ThreadLocal я не понял тебя -- где-то же надо хранить id текущего потока, по которому ты будешь определять, какой счетчик ему обновлять? Самое эффективное хранить на стеке, но это не вариант для универсального алгоритма, реализованного как хорошо инкапсулированный библиотечный примитив, не требующий ничего особого от клиентов (как RWLock, например). Так что ThreadLocal...

      1) Хех, а какая разница, какой счетчик обновлять?) Плюсанули один, минусанули другой, а поток-писатель пусть суммирует и ждет, пока сумма станет ноль :)
      2) Чем не подходит Thread.currentThread().getId()?

      Удалить
    3. >Кстати мне не вполне понятно, почему LongAdder не использует getAndAddLong().

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

      >ех, а какая разница, какой счетчик обновлять?)

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

      >Чем не подходит Thread.currentThread().getId()?

      Подходит. Только чем это принципиально отличается от ThreadLocal? Тебе нужно будет взять этот ID из поля Thread (на каждом чтении:), и отобразить его в индекс в массиве счетчиков. А в случае threadLocal ты берешь словарь из поля Thread, по аналогичному хэшу ищешь в нем нужную ячейку -- и вот у тебя уже счетчик. Преимущество, возможно, в одно-два чтения, но ты теряешь простую возможность раздувать/сдувать свой массив счетчиков, как у него сделано со связным списком. Если затачивать под конкретный сценарий, где тебе примерно известно количество читателей, то массив будет получше. Если целиться в создание общеупотребимого компонента, достаточно хорошо работающего out of box, то ThreadLocal выглядит лучше.

      Удалить
  2. Руслан а как ты собираешься разруливать проблему
    консистентности в случае большого числа копий ?

    Ну вот скажем пришел писатель и начал писать в

    Copy1 - done
    Copy2 - done
    ....
    Copy_i - done
    Тут приходит читатель и хочет прочитать и вот незадача взял и прочитал Copy_i+1 -
    в то время как писатель туда еще недописал - а другой читатель из другого треда
    взял и прочитал из Copy_1.

    Можешь тут пояснить ? Может я чего не догоняю ?



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

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

      Удалить
  3. Так я и не говорю что мы пишем и читаем в одну копию одновременно.
    Я о том что один читатель может прочитать одну копию (с одной версией) -
    а другой другую.

    ОтветитьУдалить
    Ответы
    1. Да, все верно. Это и есть "версионность". Этим страдает (или наслаждается) и CoW, и оригинальный Left-Right -- каждый читатель начиная чтение получает в свое распоряжение версию структуры данных на момент начала чтения, и эта версия не изменяется пока читатель сам не решит ее "отпустить" и перезапросить свежую. Напоминает ограниченный serializable, в терминах баз данных.

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

      Удалить
    3. Но ведь мы под локом пока пишем только в одну копию ?
      Или лок держим пока не записали во все копии ?

      Удалить
    4. Writers-lock защищает всю записи процедуру целиком -- в том числе все записи во все копии.

      Удалить
  4. Очень похоже на trade-off'ы CAP теоремы. По сути вопрос - кто и как будет распространять изменения внесенные одними писателями в одни копии на те копии, в которые никто не пишет и никто не читает... Логично было бы для начала определиться с тем, что важнее - целостность или доступность. Если 2ое - то можно хоть под глобал локом потихонечку распространить теми же писателями, если 1ое, то надо быть готовым к устаревшим данным.

    Интересно, что Руслан скажет

    ОтветитьУдалить
  5. Я думаю это ответ на твой вопрос - почему никто не догадался

    Видимо все хотят консистентности.

    Конечно - если у тебя цены и в принципе пофигу на то что разные читатели получает разные версии - лишь бы как говорится лошадка бежала - то можно и забить )

    ОтветитьУдалить
    Ответы
    1. Так как раз ты консистентность-то и получишь -- наоборот, если бы ты позволял читателю видеть полузаписанное состояние, то это было бы неконсистентно. Вон, Гил-то со своим WriterReaderPhaser-ом -- у него уже была полностью конкурентная, неблокирующая даже для писателей структура данных. И он поверх нее навенул еще свой фазер чтобы как раз дать возможность читателям читать консистентный снапшот, а не мешанину из разных записей

      Удалить
    2. Да верно - я просто подумал что лок на запись берется только для одной из копий.

      Удалить
  6. Кстати, похожую конструкцию, только с wait-free writing в свое время описывал Gil Tene: http://stuff-gil-says.blogspot.ru/2014/11/writerreaderphaser-story-about-new.html

    ОтветитьУдалить
    Ответы
    1. О, кстати да! Спасибо за ссылку -- я помню, чо когда-то читал этот его пост, но тогда меня интересовали другие вещи, поэтому даже не отложилось в памяти. Там в коментах можно найти длинный диалог Гила с Педро на тему что первично -- LeftRight или ReaderWriterPhaser :)

      Удалить
    2. Я перечитал, и вспомнил, почему не отложилось -- потому что у Гила очень узкий сценарий использования. У него уже есть конкурентная структура данных с неблокирующимися _писателями_ (и читателями, конечно). Но он хочет иметь возможность читать не мутирующую прямо на глазах версию, а консистентный снапшот. Вот чтобы такой снапшот снимать он и придумал свой фазер.

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

      Удалить
  7. >>
    не можем утверждать, что нынешнюю закрытую копию никто не читает, ведь это только новые читатели пойдут по обновленной ссылке, а старые, которые начали чтение до смены ролей, все еще читают копию, которая сейчас уже закрыта. Значит, нам нужен какой-то механизм, позволяющий дождаться, пока все эти старички закончат читать
    >>
    напомнило RCU (read-copy-update)

    ОтветитьУдалить
    Ответы
    1. Да, авторы тоже про него упоминают.

      Удалить