14 октября 2012 г.

StampedLock

На днях в concurrency-interest Даг Ли объявил о выходе альфа-версии StampedLock-a. Это довольно интересный вариант ReadWriteLock-а, с возможностью ультра-оптимистичных чтений практически без contention. Он дает ограниченную функциональность обычного ReadWriteLock (в частности, нет reentrancy), но добавляет методы tryOptimisticRead()/validate(stamp), и tryConvertToWriteLock(stamp). По-сути, это попытка сделать версионную структуру данных: каждый захват блокировки возвращает уникальный (ну, почти — это все-таки обычный long, который через пару лет непрерывного использования может начать повторяться) идентификатор. Этот идентификатор можно рассматривать как номер текущей версии данных, защищаемых данной блокировкой. И, используя этот идентификатор можно делать очень дешевое спекулятивное чтение:

private long x, y;
...
double distanceFromOriginV1() { // A read-only method
     long stamp;
     if ((stamp = sl.tryOptimisticRead()) != 0L) { // optimistic
       double currentX = x;
       double currentY = y;
       if (sl.validate(stamp))
         return Math.sqrt(currentX * currentX + currentY * currentY);
     }
     stamp = sl.readLock(); // fall back to read lock
     try {
       double currentX = x;
       double currentY = y;
         return Math.sqrt(currentX * currentX + currentY * currentY);
     } finally {
       sl.unlockRead(stamp);
     }
}

(Пример из javadoc). Как можно видеть, такое спекулятивное чтение довольно громоздко с точки зрения кода. Кроме того, код этот нужно писать очень аккуратно: в частности, все необходимые вам чтения должны быть выполнены между tryOptimisticLock()/validate(stamp). Это не кажется большим ограничением, пока не заметишь, что "все" означает "прямо совсем все, вплоть до примитивных типов". В примере выше все поля и так примитивны, и эта тонкость не бросается в глаза. Сложность возникает если поля -- это ссылки на объекты (например, на массив). Так вот, в этом случае вы не можете прочитать, скажем, ссылку на объект, и после validate(stamp) прочитать поля этого объекта, и как-то их использовать! Вы должны добраться до реально необходимых вам в дальнейшем примитивных полей (или ссылок — но только в том случае, если вы дальше ссылки используете только для сравнения, но не для разыменования с целью доступа к полям объекта по ссылке). Более того, вы не можете внутри блока tryOptimisticLock()/validate(stamp) делать ничего, что не сможете откатить, если validate(stamp) не пройдет. Собственно, лучше там вообще ничего кроме чтений не делать. Блок tryOptimisticLock()/validate(stamp) — это способ получить непротиворечивое представление данных, а все операции с этими данными лучше делать после, когда успешный validate(stamp) даст вам право считать, что полученные данные действительно не противоречивы (==нет шанса, что кто-то вклинился, и изменил часть их, пока вы дочитывали другую часть).

Собственно, что здесь самое интересное. Дело в том, что, если опустить детали, то весь этот tryOptimisticLock()/validate(stamp) реализуется очень просто:
class StampedLock{
   private volatile long stamp;
   public long tryOptimisticRead(){
       return stamp;
   }
   public boolean validate(final long stamp){
       return this.stamp == stamp;
   }
}
Как можно видеть, основная особенность этого кода, по сравнению с обычным ReadWriteLock в том, что здесь нет ни одной записи. Это и есть та самая killing feature StampedLock-а, из-за которой весь сыр-бор. Она дает самое идеальное масштабирование чтений в многопроцессорном окружении, которое только возможно, ибо чистые чтения скалируются так хорошо, как это только возможно.

Казалось бы, если все так круто, почему это 100 лет назад еще не реализовано? Ответ очень простой: вот прямо так это работать не будет. Точнее, JMM не гарантирует, что это будет работать. Тонкость в деталях: чтобы чтения, выполненные между tryOptimisticLock() и validate(stamp) гарантировали непротиворечивое представление данных, нужно чтобы эти чтения нельзя было вынести из блока tryOptimisticLock()/validate(stamp). Так вот, волатильное чтение в tryOptimisticLock() гарантирует, что идущие после него обычные чтения не могут быть вынесены до него — тут все хорошо. Но волатильное чтение с проверкой в validate(stamp) не гарантирует, что обычные чтения, идущие до него в program order не будут переставлены после него! JMM не запрещает рантайму преобразовать вот этот код
private long x, y;
...
double distanceFromOriginV1() {
     long stamp;
     if ((stamp = sl.tryOptimisticRead()) != 0L) { // optimistic
       double currentX = x;
       double currentY = y;
       if (sl.validate(stamp))
         return Math.sqrt(currentX * currentX + currentY * currentY);
     }
}
Вот в такой:
private long x, y;
...
double distanceFromOriginV1() { // A read-only method
     long stamp;
     if ((stamp = sl.tryOptimisticRead()) != 0L) { // optimistic
       if (sl.validate(stamp)){
         //чтения вынесены из защищенного блока!
         double currentX = x;
         double currentY = y;
         return Math.sqrt(currentX * currentX + currentY * currentY);
       }
     }
}
И это и есть та причина, по которой StampedLock до сих пор не был реализован в JDK, а все попытки его реализовывать самостоятельно либо были некорректными, либо таки-использовали запись в своих версиях validate(). (Еще одной причиной, наверняка, является ультра-консервативность авторов j.u.c: они стараются не включать в стандартную библиотеку код со сложными сценариями использования. Хотя последнее время им приходится)

Собственно, как раз недавно я читал статью Hans Boehm-а, где он анализировал этот самый StampedLock, и пришел к выводу, что нет способа реализовать его без записей используя примитивы, задаваемые JMM. Просто в JMM нет операций, которые бы имели семантику чтения, и при этом давали бы двусторонний барьер памяти. В рамках JMM нужно как минимум что-то вроде CAS(stamp, stamp), чтобы одновременно проверить значение, и эмулировать double-sided membar — но это-таки будет запись (да плюс еще #lock на шине), и это гробит всю идею write-less read locking.

Тогда вопрос, как же это сделал Даг Ли? Ответ простой: Даг читер :) Он воспользовался тем, что, хотя JMM этого и не требует, и не гарантирует, но фактически Unsafe.getLongVolatile() таки имеет семантику двустороннего барьера. Разумеется, чтобы это знать, и чтобы быть уверенным, что в дальнейшем семантика не поменяется — надо быть на короткой ноге с авторами JVM. И это именно то, чем Даг может похвастаться :) Что позволено Юпитеру...

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

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

  1. > Разумеется, чтобы это знать, и чтобы быть уверенным, что в дальнейшем семантика не поменяется — надо быть на короткой ноге с авторами JVM.

    Коротконогий DL уже предложил добавить эксплицитные барьеры в Unsafe, и тогда StampedLock получит нормальный двухсторонний барьер, а не этот костыль.

    ОтветитьУдалить
  2. Unsafe is a new Fences, я гарантирую это! //JMM

    Меня что грустит -- что со всеми этими барьерами нужно будет JMM аццки переделывать. А вот это никто делать не торопится. Добавить что-то в Unsafe это внутреннее дело оракла, в общем-то, и потому дело нехитрое, а вот JMM переделать даже в малом -- ой, будем мы этого ждать до второго пришествия.

    ОтветитьУдалить
  3. > Добавить что-то в Unsafe это внутреннее дело оракла

    Нифига подобного. В поддержке этого "нестандартного" класса участвуют минимум три больших вендора.

    > "Со всеми этими барьерами нужно будет JMM аццки переделывать"

    Надо будет. Только вот задача мало кому по зубам. Я вот каждый раз попадаю в тёмный угол JMM'а, бьюсь там головой, плачу и убегаю.

    ОтветитьУдалить
  4. Ну все равно, это внутреннее дело, пусть и трех больших вендоров. А не миллионов джава-разработчиков.

    Разве проблема с коррекцией JMM теоретическая? Я думал, там основной вопрос про обратную совместимость.

    ОтветитьУдалить
  5. А если мы вставим между первым чтением штампа и валидацией запись координат в final-поля промежуточного объекта?
    То есть:

    private long x, y;
    static class Distance{
    final long x,y;
    .....
    }
    ...
    double distanceFromOriginV1() {
    long stamp;
    if ((stamp = sl.tryOptimisticRead()) != 0L) { // optimistic
    Distance d = new Distance(x,y);
    if (sl.validate(stamp))
    return Math.sqrt(d.x* d.x+ d.y* d.y);
    }
    }


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

    ОтветитьУдалить
  6. Я не понял, причем здесь final-поля. Если ты так хочешь обеспечить двусторонний барьер, то я не вижу, как они тебе помогут. Упрощенно говоря, freeze не позволит переставить "d=" до присвоения полей в конструкторе Distance. Но никто по-прежнему не мешает компилятору перенести d = new Distance(x,y) вниз, после validate().

    immutability спасает тебя от публикации ссылки через data race. Здесь же у тебя вообще публикации нет (объект используется только в создающем потоке), но зато сами параметры конструктора (x,y) получены через data race.

    ОтветитьУдалить
  7. Просто я пытался придумать способ как можно было бы сделать код рабочим не прибегая к помощи этого нового StampedLock-а, то есть если бы его реализация была такой как ты написал - просто чтение volatile-поля.
    "Но никто по-прежнему не мешает компилятору перенести d = new Distance(x,y) вниз, после validate() ..." - вот это мне казалось не очевидным.

    ОтветитьУдалить
  8. Руслан, спасибо за интересный блог! Разбираюсь с concurrency, прочел вот интересную статью на Хабре, но не могу там комментировать :) Если есть время ответьте хотя бы коротко, пожалуйста:

    1) Обычный Double-Checked Locking без volatile. Какая из проблем может случиться:
    - ссылка физически заполнена быстрее, чем занесены все поля. такое вообще бывает в Jave?
    - ссылка заполнена и объект корректно создан, но снаружи не видно полей объекта из-за проблемы c visibility
    - ссылка заполнена, а ее не видно, потоки будут входить в synchronized когда этого уже не надо

    2) 4 правила безопасной публикации - static, volatile, final и synchronized - безопасно публикуют не только объект, но и все вложенные объекты внутри него?

    3) Если объект immutable, но поля не final (нет сеттеров, init в конструкторе) - нам придется публиковать его безопасным способом, так? То есть безопасно публиковать immutables только если они содержат final поля, да и сама публикуемая ссылка все равно должна быть например volatile, что делает final attributes необязательными. Так?

    ОтветитьУдалить
  9. Ну прежде всего вот и вот -- в качестве основы. Там разобрано большинство вопросов.

    1.1 Что значит "заполнены поля"? Никто в яве не может увидеть значения полей до того, как они заполнены значениями по умолчанию. Но значения, которые вы присваиваете в конструкторе это другое дело. Вы можете увидеть ссылку на объект до того, как выполнится конструктор.
    1.2 Что значит "не видно полей"? Не видно может быть каких-то конкретных _значений_ полей.
    1.3 Вы можете не увидеть ссылку и при безопасной публикации -- volatile/synchronized не дают вам каких-либо временнЫх гарантий "через сколько ns значение может увидеть другой поток"

    2. Да, как правило

    3. Непонятно, почему вы считаете что immutable объект обязательно публиковать через volatile. Это как раз не обязательно

    ОтветитьУдалить
    Ответы
    1. Руслан, по поводу пункта 2 - "как правило" означает, что в случае volatile поля то, что находится по ссылке, уже volatile-не будет, так ? final должно же аналогично отрабатывать ?

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

      Удалить
  10. Спасибо,
    1) получается, есть две причины выдачи неполностью инициализированного объекта DCL-фабрикой: 1. конструктор физически не успел записать значения в поля объекта 2. значения в конструкторе записались, но другой поток их пока не видит.
    3) Я имел ввиду, что лучше immutable публиковать тоже через volatile, тогда другой поток вероятно быстрее увидит свежезаполненную ссылку, а не предыдущее ее значение, если я правильно понял ваш другой пост.

    ОтветитьУдалить
  11. 1) По-сути, это одна и та же причина: присвоение ссылки стало видимым раньше, чем присвоения значений полям. Если же вопрос как это физически получилось, то вариантов больше, чем 2. Запись могла "застрять" на полудюжине уровней.

    2) Вообще, если верить Дагу Ли, то специальная семантика final-полей была придумана просто чтобы _была возможность_ создавать совершенно безопасные объекты для некоторых критичных частей classlib. String, который используется в качестве ключей в уйме security-sensetive мест -- тому пример. То есть то, что получившуюся семантику можно использовать где-то для улучшения производительности -- это не планировалось, это побочный эффект. И потому Даг рекомендует придерживаться "обычных" правил безопасной публикации, не особо напирая на immutability.

    Но мне лично кажется, что это перебор. Особенно учитывая, что в яве и так сейчас сильно не хватает "слабых" примитивов синхронизации, наличие freeze просто редкий подарок.

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

    ОтветитьУдалить
  12. Этот комментарий был удален автором.

    ОтветитьУдалить
  13. Вы говорите: volatile не дает временнЫх гарантий, однако happens-before для volatile утверждает что любой последующий read должен увидеть результаты write. Как я понял из другого поста проблема в понятии "последующий" т.к. время на разных процессорах может как-то не совпадать. Могу ли я сделать выводы:
    1) volatile read может не увидить volatile write только если потоки выполняются разными процессорами?
    2) наличие volatile или другой правильной публикации просто существенно повышает вероятность последующим read увидеть результат предыдущего write?

    ps:
    а не знаете что можно почитать по основам устройства процессоров?

    ОтветитьУдалить
  14. Да, дело именно в значении термина "последующий". В JMM нет понятия времени, поэтому там "последующий" значит именно последующий в смысле "произошел после". Поэтому дело вовсе не в том, что время на разных процессорах может не совпадать -- этот аргумент я приводил чтобы показать _почему_ JMM формулируется без понятия физического времени -- дело именно в том, что времени в JMM вообще нет.

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

    2) Да, вероятность повышается. Текущая известная мне реализация vstore/vload на x86 старается обойти все возможные буфера чтения/записи. Так что запись окажется в общей памяти так быстро, как это позволяет контроллер, и прочитается оттуда так быстро, как это возможно. Но это, конечно, вовсе не из JMM следует -- это детали конкретных реализаций, которые мне известны.

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

    ОтветитьУдалить
  15. В следующем году Intel выпускает новый процессор на базе архитектуры Haswell с поддержкой транзакционной памяти - это по сути и есть супер-оптимистичная блокировка с железной реализацией. Подобные шаманства по идее станут не нужны

    ОтветитьУдалить
  16. Да, я читал про это. Но сколько времени пройдет, прежде чем эту транзакционность "протащат" в языки типа явы? Сомневаюсь, что кто-то будет разрабатывать апи только под одну-единственную модель процессоров, пусть и самого крупного вендора.

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

    ОтветитьУдалить
  17. Я думаю AMD тоже подтянется со временем. Имплементить это в джаве видно нужно будет с fall-back'ом на софтовую версию.

    Хотя конечно времени до внедрения много пройдёт

    ОтветитьУдалить
  18. Я что имею в виду: вот есть у нас getAndIncrement, который реализован в яве через CAS, который интринсик. Несмотря на то, что есть прямая инструкция lock xadd. Казалось бы, если сделать getAndInc интринсиком -- можно наверняка огрести кучу бенефита. И вот Мартин Томпсон как-то попробовал (в дизрапторе getAndInc активно юзается) -- и очень удивился, что прирост составил всего лишь какие-то 15%. И, насколько я знаю, getAndInc до сих пор все еще не интринсик.

    А все потому, что основная стоимость CAS -- это кэш-когерентность. И с точки зрения нагрузки на КК сценарии lock xadd и CAS-loop практически идентичны.

    Мне кажется, здесь так же будет. То есть оптимистичная блокировка -- это практически то же самое, с точки зрения КК, что и транзакционная память в версии интела. А значит разница может оказаться не очень велика, и на нее забьют, как забили на lock xadd.

    ОтветитьУдалить
  19. Руслан, не пробывали реализовать при помощи такого лока обычный multithread-counter без CAS и synchronized ?

    ОтветитьУдалить
  20. Не очень понятен смысл -- для счетчика не нужен лок на чтение, достаточно его просто прочитать :)

    ОтветитьУдалить
  21. Этот комментарий был удален автором.

    ОтветитьУдалить
  22. А что инкремент? Для записи StampedLock ничем принципиально не лучше обычного. Тут фокус именно на том, что если у вас есть одно примитивное значение, то достаточно сделать его volatile. Вот если у вас связанных полей несколько -- тут нужно как-то обеспечить согласованное чтение их всех в одном снэпшоте.

    Посмотрите архивы concurrency-interest, там Dr. Kibuz делал бенчи. У него выходило что на чтение чуть ли не в 10000 быстрее. Это, конечно, оптимистично (т.е. в специфичном бенчмарке такое вполне возможно, но в реальных кейсах на такой прирост рассчитывать не стоит), но зато наглядно показывает, ради чего весь сыр-бор

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