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. Даг обещает сделать это когда-нибудь, но пока, как он пишет "вы можете ожидать, что он работает так, как вы ожидаете". Звучит обнадеживающе, что тут сказать.