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+ байт кэша на каждый читающий поток потратить), и с блокирующейся записью — но при этом вероятность ожидания на записи можно регулировать увеличивая количество копий. Интересная штука, правда, очень сложно поверить, что эту структуру данных еще никто не придумал :)