Перейти к основному содержимому

Введение в чередование замков

· 5 мин. чтения

1. Введение

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

2. Проблема

HashMap не является потокобезопасной структурой данных из-за своей несинхронизированной природы. Это означает, что команды из многопоточной среды могут привести к несогласованности данных.

Чтобы решить эту проблему, мы можем либо преобразовать исходную карту с помощью метода Collections#synchronizedMap , либо использовать структуру данных HashTable . Оба вернут потокобезопасную реализацию интерфейса Map , но за счет производительности.

Подход к определению монопольного доступа к структурам данных с помощью одного объекта блокировки называется крупнозернистой синхронизацией .

В крупномодульной реализации синхронизации каждый доступ к объекту должен выполняться одновременно одним потоком. В итоге мы имеем последовательный доступ.

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

3. Блокировка чередования

Чтобы достичь нашей цели, мы будем использовать шаблон Lock Striping. Чередование блокировок — это метод, при котором блокировка происходит на нескольких сегментах или полосах, что означает, что доступ к сегменту блокирует только этот сегмент, а не всю структуру данных.

Есть несколько способов сделать это:

  • Во-первых, мы могли бы использовать блокировку для каждой задачи, тем самым максимизируя параллелизм между задачами — хотя это требует большего объема памяти.
  • Или мы могли бы использовать одну блокировку для каждой задачи, что требует меньше памяти, но также снижает производительность в параллелизме.

Чтобы помочь нам справиться с этим компромиссом между производительностью и памятью, Guava поставляется с классом Striped. Это похоже на логику ConcurrentHashMap , но класс Striped идет еще дальше, уменьшая синхронизацию отдельных задач с помощью семафоров или повторных блокировок.

4. Краткий пример

Давайте сделаем быстрый пример, который поможет нам понять преимущества этого шаблона.

Мы сравним HashMap и ConcurrentHashMap , а также одиночную блокировку и чередующуюся блокировку, что приведет к четырем экспериментам.

Для каждого эксперимента мы будем выполнять одновременные операции чтения и записи на базовом Map . Что будет отличаться, так это то, как мы получаем доступ к каждому сегменту.

И для этого мы создадим два класса — SingleLock и StripedLock. Это конкретные реализации абстрактного класса ConcurrentAccessExperiment , который выполняет всю работу.

4.1. Зависимости

Поскольку мы собираемся использовать класс Striped из Guava , мы добавим зависимость от guava :

<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>31.0.1-jre</version>
</dependency>

4.2. Основной процесс

Наш класс ConcurrentAccessExperiment реализует поведение, описанное ранее:

public abstract class ConcurrentAccessExperiment {

public final Map<String,String> doWork(Map<String,String> map, int threads, int slots) {
CompletableFuture<?>[] requests = new CompletableFuture<?>[threads * slots];

for (int i = 0; i < threads; i++) {
requests[slots * i + 0] = CompletableFuture.supplyAsync(putSupplier(map, i));
requests[slots * i + 1] = CompletableFuture.supplyAsync(getSupplier(map, i));
requests[slots * i + 2] = CompletableFuture.supplyAsync(getSupplier(map, i));
requests[slots * i + 3] = CompletableFuture.supplyAsync(getSupplier(map, i));
}
CompletableFuture.allOf(requests).join();

return map;
}

protected abstract Supplier<?> putSupplier(Map<String,String> map, int key);
protected abstract Supplier<?> getSupplier(Map<String,String> map, int key);
}

Важно отметить, что, поскольку наш тест привязан к ЦП, мы ограничили количество сегментов до некоторого числа, кратного доступным процессорам.

4.3. Параллельный доступ с ReentrantLock

Теперь мы реализуем методы для наших асинхронных задач.

Наш класс SingleLock определяет единую блокировку для всей структуры данных с помощью ReentrantLock :

public class SingleLock extends ConcurrentAccessExperiment {
ReentrantLock lock;

public SingleLock() {
lock = new ReentrantLock();
}

protected Supplier<?> putSupplier(Map<String,String> map, int key) {
return (()-> {
lock.lock();
try {
return map.put("key" + key, "value" + key);
} finally {
lock.unlock();
}
});
}

protected Supplier<?> getSupplier(Map<String,String> map, int key) {
return (()-> {
lock.lock();
try {
return map.get("key" + key);
} finally {
lock.unlock();
}
});
}
}

4.4. Параллельный доступ с чередованием

Затем класс StripedLock определяет полосатый замок для каждого сегмента:

public class StripedLock extends ConcurrentAccessExperiment {
Striped lock;

public StripedLock(int buckets) {
lock = Striped.lock(buckets);
}

protected Supplier<?> putSupplier(Map<String,String> map, int key) {
return (()-> {
int bucket = key % stripedLock.size();
Lock lock = stripedLock.get(bucket);
lock.lock();
try {
return map.put("key" + key, "value" + key);
} finally {
lock.unlock();
}
});
}

protected Supplier<?> getSupplier(Map<String,String> map, int key) {
return (()-> {
int bucket = key % stripedLock.size();
Lock lock = stripedLock.get(bucket);
lock.lock();
try {
return map.get("key" + key);
} finally {
lock.unlock();
}
});
}
}

Итак, какая стратегия работает лучше?

5. Результаты

Давайте воспользуемся JMH (Java Microbenchmark Harness), чтобы выяснить это. Тесты можно найти по ссылке на исходный код в конце руководства.

Запустив наш тест, мы можем увидеть что-то похожее на следующее (обратите внимание, чем выше пропускная способность, тем лучше):

Benchmark                                                Mode  Cnt  Score   Error   Units
ConcurrentAccessBenchmark.singleLockConcurrentHashMap thrpt 10 0,059 ± 0,006 ops/ms
ConcurrentAccessBenchmark.singleLockHashMap thrpt 10 0,061 ± 0,005 ops/ms
ConcurrentAccessBenchmark.stripedLockConcurrentHashMap thrpt 10 0,065 ± 0,009 ops/ms
ConcurrentAccessBenchmark.stripedLockHashMap thrpt 10 0,068 ± 0,008 ops/ms

6. Выводы

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

Из наших результатов тестов мы можем понять, как различные параллельные стратегии могут значительно повлиять на общий процесс. Паттерн Striped Lock обеспечивает существенное улучшение, поскольку он набирает примерно 10% больше как с HashMap , так и с ConcurrentHashMap .

Как обычно, исходный код этого руководства доступен на GitHub .