Теория и практика Java: Построение лучшей HashMap

Как ConcurrentHashMap предоставляет более высокий уровень параллелизма без ущерба для безопасности потоков

ConcurrentHashMap - часть пакета util.concurrent Дага Ли (Doug Lea) - предлагает более высокий уровень параллелизма, чем Hashtable или synchronizedMap. Вдобавок, ей удаётся полностью избегать блокировок для большинства успешных операций get(), что даёт в итоге отличную пропускную способность в параллельных приложениях. В этом месяце Брайан Гетц проникает в код ConcurrentHashMap и рассматривает, как достигается этот впечатляющий эффект без ущерба для безопасности потоков.

Брайан Гетц, главный консультант, Quiotix

Брайан Гетц (Brian Goetz) - консультант по ПО и последние 15 лет работал профессиональными разработчиком ПО. Сейчас он является главным консультантом в фирме Quiotix, занимающейся разработкой ПО и консалтингом и находящейся в Лос-Альтос, Калифорния. Следите за публикациями Брайана в популярных промышленных изданиях. Вы можете связаться с Брайаном по адресу brian@quiotix.com



26.02.2007

В июльском выпуске Теории и практики Java ("Классы параллельных коллекций" (Concurrent collections classes)), мы рассматривали узкие места масштабируемости и обсуждали, как достичь более высокого параллелизма и пропускной способности в разделяемых структурах данных. Иногда лучший способ изучения чего-либо - это исследование работы экспертов, так в этом месяце мы собираемся взглянуть на реализацию ConcurrentHashMap из пакета util.concurrent Дага Ли. Версия ConcurrentHashMap, оптимизированная для новой Модели Памяти Java (JMM), которая определяется JSR 133, будет включена в пакет java.util.concurrent в JDK 1.5; версия в util.concurrent была проверена на потокобезопасность в условиях старой и новой моделей памяти.

Оптимизация пропускной способности

ConcurrentHashMap использует несколько оригинальных приёмов для достижения более высокого уровня параллелизма и избежания блокировок, в их числе использование множественных блокировок записи для различных хэш-бакетов и эксплуатация неопределенностей в JMM для минимизации времени блокировок или полного ухода от привлечения блокировок. Она оптимизирована для самого распространённого использования - извлечения значения, которое должно уже существовать в map-таблице. Фактически, большинство успешных операций get() будут работать вообще без блокирования. (Предупреждение: не пытайтесь повторить это дома! Попытка перехитрить JMM гораздо опаснее, чем может показаться, и не должна предприниматься бездумно. Классы util.concurrent были написаны экспертами по параллелизму и подвергнуты независимой экспертизе на предмет безопасности для JMM.)

Множественные блокировки записи

Вспомните, что основным препятствием для масштабируемости Hashtable (или Collections.synchronizedMap) является то, что они используют единственную на всю map-таблицу блокировку, которая должна поддерживаться для целостности операций вставки, удаления или извлечения, а иногда даже для целостности обхода итератором. Это полностью предотвращает доступ других потоков к Map на время удержания блокировки, даже при наличии простаивающих процессоров, что значительно ограничивает параллелизм.

ConcurrentHashMap обходится без единственной на всю map-таблицу блокировки, используя вместо этого набор из 32 блокировок, каждая из которых защищает подмножество хэш-бакетов. Блокировки, прежде всего, используются изменчивыми операциями (put() и remove()). Наличие 32 отдельных блокировок означает, что максимум 32 потока могут одновременно модифицировать map-таблицу. Это вовсе не обязательно означает, что если менее 32 потоков в данный момент пишет в map-таблицу, очередная операция записи не заблокируется - 32 является теоретическим пределом для параллельной записи, но этот показатель не всегда может быть достигнут на практике. И всё же, 32 гораздо лучше, чем один, и этого более чем достаточно для большинства приложений, работающих на сегодняшнем поколении компьютерных систем.

Операции над всей map-таблицей

Наличие 32 отдельных блокировок, каждая из которых предохраняет подмножество хэш-бакетов, означает, что операции, требующие монопольного доступа к map-таблице, должны захватить все 32 блокировки. Некоторые операции над всей map-таблицей, такие как size() и isEmpty(), могут устраниться без блокирования всей map-таблицы (путём правильного задания семантики этих операций), но некоторые операции, такие как пересчёт хэшей map-таблицы (увеличивающих количество хэш-бакетов и перераспределяющих элементы по мере роста map-таблицы), должны гарантировать монопольный доступ. Язык Java не предоставляет простого способа для получения переменного набора блокировок; в редких случаях, когда это необходимо сделать, это осуществляется путём рекурсии.


Обзор JMM

Прежде, чем мы перейдем к реализации put(), get() и remove(), давайте сделаем краткий обзор JMM, которая управляет тем, как операции с памятью (чтение и запись) одного потока влияют на операции с памятью других потоков. Ввиду выигрыша в производительности, получаемого при использовании регистров процессора и кэш-памяти процессоров для ускорения доступа к памяти, Спецификация Языка Java (Java Language Specification - JLS) допускает, что некоторые операции с памятью не будут сразу же видны всем другим потокам. Существуют два языковых механизма, гарантирующих связность операций с памятью относительно потоков - synchronized и volatile.

В соответствии с JLS, "В отсутствие синхронизации в явном виде реализация может свободно обновлять оперативную память в неожиданном порядке." Это значит, что без синхронизации операции записи, появляющиеся в данном потоке в одном порядке, могут появиться в ином порядке для другого потока, и эти обновления переменных памяти могут занимать неопределенное время на распространение из одного потока в другой.

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

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

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


Реализация ConcurrentHashMap

Как предполагалось ранее, структура данных, используемая ConcurrentHashMap является сходной по реализации с Hashtable или HashMap, с допускающим изменение размера массивом данных мусоросборников, каждый из которых состоит из последовательности элементов Map.Entry, как показано в Листинге 1. Вместо одной блокировки массива, ConcurrentHashMap использует фиксированный пул блокировок, которые формируют секторы в массиве участков памяти.

Листинг 1. Элементы Map.Entry, используемые ConcurrentHashMap
protected static class Entry implements Map.Entry {
    protected final Object key;
    protected volatile Object value;
    protected final int hash;
    protected final Entry next;
    ...
}

Обход структур данных без блокирования

В отличие от Hashtable или типичной реализации Map с пулом блокировок, операции ConcurrentHashMap.get() не обязательно влекут за собой получение блокировки, ассоциированной с соответствующим бакетом. В отсутствие блокировки, реализация должна быть готова иметь дело с устаревшими или противоречивыми значениями любых используемых переменных, таких как указатель начала списка и поля элементов Map.Entry (в том числе указатели на связи, включающие связанный список элементов для каждого бакета).

Большинство параллельных классов использует синхронизацию для обеспечения монопольного доступа к структуре данных (и непротиворечивого её представления). Вместо того, чтобы предполагать монопольность и непротиворечивость, связанный список, используемый ConcurrentHashMap, тщательно спроектирован так, что реализация может выявлять, что её представление списка является противоречивым или устаревшим. Если она обнаруживает, что её представление является противоречивым или устаревшим или просто не обнаруживает искомую запись, она затем синхронизируется с соответствующей блокировкой бакета и снова ищет в цепочке. Это оптимизирует поиск для общего случая, где большинство извлечений являются успешными, а количество извлечений превосходит вставки и удаления.

Эксплуатация неизменности

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

Хотя новая JMM обеспечивает безопасность при инициализации для финальных переменных, старая JMM этого не делает, а значит, для другого потока есть возможность увидеть значение по умолчанию для финального поля, вместо значения, помещенного туда конструктором объекта. Реализация должна быть также готова распознать это, что она делает, обеспечивая, чтобы значение по умолчанию для каждого поля Entry не являлось подходящим. Список сконструирован таким образом, что если какое-либо из полей Entry имеет значение по умолчанию (ноль или null), поиск не даст результатов, сообщая реализации get() о необходимости синхронизации и повторного обхода цепочки.

Операции извлечения

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

Листинг 2. Реализация ConcurrentHashMap.get()
  public Object get(Object key) {
    int hash = hash(key);     // throws null pointer exception if key is null

    // Try first without locking...
    Entry[] tab = table;
    int index = hash & (tab.length - 1);
    Entry first = tab[index];
    Entry e;

    for (e = first; e != null; e = e.next) {
      if (e.hash == hash && eq(key, e.key)) {
        Object value = e.value;
        // null values means that the element has been removed
        if (value != null) 
          return value;
        else
          break;
      }
    }

    // Recheck under synch if key apparently not there or interference
    Segment seg = segments[hash & SEGMENT_MASK];
    synchronized(seg) { 
      tab = table;
      index = hash & (tab.length - 1);
      Entry newFirst = tab[index];
      if (e != null || first != newFirst) {
        for (e = newFirst; e != null; e = e.next) {
          if (e.hash == hash && eq(key, e.key)) 
            return e.value;
        }
      }
      return null;
    }
  }

Операции удаления

Поскольку поток может видеть устаревшие значения для указателей на связи в цепочке хэшей, простого удаления элемента из цепочки будет недостаточно, чтобы убедиться в том, что другие потоки не будут продолжать видеть удаленное значение при выполнении поиска. Напротив, как показано в Листинге 3, удаление является двухступенчатым процессом - сначала отыскивается подходящий объект Entry и его поле значения устанавливается на null, а затем часть цепочки от начала до удалённого элемента клонируется и присоединяется к оставшейся части цепочки, следующей за удаленным элементом. Поскольку поле значения является изменчивым, если другой поток просматривает просроченную цепочку в поисках удалённого элемента, то он сразу же увидит поле с нулевым значением, и будет знать о необходимости повтора извлечения с синхронизацией. В конечном счёте, начальная часть цепочки хэшей, заканчивающаяся в удаленном элементе, будет утилизирована.

Листинг 3. Реализация ConcurrentHashMap.remove()
  protected Object remove(Object key, Object value) {
    /*
      Find the entry, then 
        1. Set value field to null, to force get() to retry
        2. Rebuild the list without this entry.
           All entries following removed node can stay in list, but
           all preceding ones need to be cloned.  Traversals rely
           on this strategy to ensure that elements will not be
          repeated during iteration.
    */

    int hash = hash(key);
    Segment seg = segments[hash & SEGMENT_MASK];

    synchronized(seg) {
      Entry[] tab = table;
      int index = hash & (tab.length-1);
      Entry first = tab[index];
      Entry e = first;

      for (;;) {
        if (e == null)
          return null;
        if (e.hash == hash && eq(key, e.key)) 
          break;
        e = e.next;
      }

      Object oldValue = e.value;
      if (value != null && !value.equals(oldValue))
        return null;
     
      e.value = null;

      Entry head = e.next;
      for (Entry p = first; p != e; p = p.next) 
        head = new Entry(p.hash, p.key, p.value, head);
      tab[index] = head;
      seg.count-;
      return oldValue;
    }
  }

На Рисунке 1 показана цепочка хэшей до удаления элемента:

Рисунок 1. Цепочка хэшей
Рисунок 1. Цепочка хэшей

На Рисунке 2 показана цепочка с удаленным элементом 3:

Рисунок 2. Удаление элемента
Рисунок 2. Удаление элемента

Операции вставки и обновления

Реализация put() является простой. Как и remove(), put() удерживает блокировку бакета на протяжении своего выполнения, но поскольку get() не всегда нуждается в блокировке, то это не обязательно блокирует выполнение читающих процессов (также не блокируются и другие записывающие процессы от доступа к другим бакетам). Сначала put() ищет желаемый ключ в соответствующей цепочке хэшей. Если он найден, то поле value (являющееся изменяемым) просто обновляется. Если же он не найден, то создается новый объект Entry для описания нового отображения и вставляется в начало списка для этого бакета.

Слабо связные итераторы

Семантика итераторов, возвращаемых ConcurrentHashMap, отличается от семантики коллекции java.util; вместо того чтобы быть быстро-сбойными (выбрасывая исключение, если лежащая в основе коллекция изменяется во время использования итератора), они являются слабо связными. Когда пользователь вызывает keySet().iterator(), чтобы извлечь итератор для набора хэш-ключей, реализация быстро выполняет синхронизацию, чтобы удостовериться, что указатели начала для каждой цепочки являются актуальными. Операции next() и hasNext() описаны понятным образом, просматривают каждую цепочку хэшей, а затем переходят к следующей цепочке до тех пор, пока не будут просмотрены все цепочки. Слабо связные итераторы могут отражать, а могут и не отражать вставки, сделанные во время итерации, но они, разумеется, будут отражать обновления или удаления для ключей, до которых ещё не добрался итератор, и не вернут ни одно значение больше одного раза. Итераторы, возвращаемые ConcurrentHashMap, не будут генерировать ConcurrentModificationException.

Динамическое изменение размеров

По мере увеличения числа элементов в map-таблице, цепочки хэшей будут удлиняться, а время извлечения увеличиваться. В определенный момент имеет смысл увеличить количество бакетов и перехэшировать значения. В таких классах, как Hashtable, это легко, потому что есть возможность удерживать монопольную блокировку всей map-таблицы. В ConcurrentHashMap каждый раз, когда вставляется запись, если длина этой цепочки превышает некоторый порог, цепочка помечается, как нуждающаяся в изменении размеров. Когда достаточное количество цепочек сообщают, что требуется изменение размеров, ConcurrentHashMap использует рекурсию для получения блокировки для каждого бакета и перехэширует элементы из каждого бакета в новую хэш-таблицу большего размера. В большинстве случаев это будет происходить автоматически и прозрачно для вызывающей стороны.

Без блокировок?

Утверждение, что успешные операции get() происходят без блокировок, будет некоторым преувеличением, поскольку поле value в Entry является изменяемым и это используется для обнаружения обновлений и удалений. На машинном уровне изменяемость и синхронизация часто заканчиваются преобразованием в те же самые примитивы когерентности кэша, поэтому здесь в действительности имеет место некоторое блокирование, хотя и при меньшем размере ячеек и без планирования или издержек JVM, связанных с получением и освобождением мониторов. Но, не учитывая семантики, параллелизм, достигаемый ConcurrentHashMap, во многих типичных ситуациях, когда число извлечений превосходит число вставок и удалений, является весьма впечатляющим.


Резюме

ConcurrentHashMap является как очень полезным классом для многих параллельных приложений, так и прекрасным примером класса, понимающего и эксплуатирующего тонкие особенности JMM для достижения более высокой производительности. ConcurrentHashMap является впечатляющим достижением кодирования, требующим глубокого понимания параллелизма и JMM. Используйте его, учитесь у него и наслаждайтесь, но если вы пока не являетесь экспертом по параллелизму в Java, то вам лучше воздержаться от самостоятельных действий.

Ресурсы

Комментарии

developerWorks: Войти

Обязательные поля отмечены звездочкой (*).


Нужен IBM ID?
Забыли Ваш IBM ID?


Забыли Ваш пароль?
Изменить пароль

Нажимая Отправить, Вы принимаете Условия использования developerWorks.

 


Профиль создается, когда вы первый раз заходите в developerWorks. Информация в вашем профиле (имя, страна / регион, название компании) отображается для всех пользователей и будет сопровождать любой опубликованный вами контент пока вы специально не укажите скрыть название вашей компании. Вы можете обновить ваш IBM аккаунт в любое время.

Вся введенная информация защищена.

Выберите имя, которое будет отображаться на экране



При первом входе в developerWorks для Вас будет создан профиль и Вам нужно будет выбрать Отображаемое имя. Оно будет выводиться рядом с контентом, опубликованным Вами в developerWorks.

Отображаемое имя должно иметь длину от 3 символов до 31 символа. Ваше Имя в системе должно быть уникальным. В качестве имени по соображениям приватности нельзя использовать контактный e-mail.

Обязательные поля отмечены звездочкой (*).

(Отображаемое имя должно иметь длину от 3 символов до 31 символа.)

Нажимая Отправить, Вы принимаете Условия использования developerWorks.

 


Вся введенная информация защищена.


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=40
Zone=Технология Java
ArticleID=197868
ArticleTitle=Теория и практика Java: Построение лучшей HashMap
publish-date=02262007