Существуют десятки достойных реализаций хеш-таблиц без блокировок. Обычно эти структуры данных вместо использования простых блокировок используют операции на основе CAS, чтобы быть свободными от блокировки. с этим повествованием может показаться, что я собираюсь использовать этот пост, чтобы создать аргумент для структур данных без блокировки. это не так, довольно удивительно. напротив, здесь мы будем говорить о старых простых замках.
Теперь, когда все готовы, давайте реализуем параллельную версию Mapс этим простым контрактом:
public interface ConcurrentMap<K, V> {
boolean put(K key, V value);
V get(K key);
boolean remove(K key);
}
Поскольку это будет поточно-ориентированная структура данных, мы должны получить некоторые блокировки и впоследствии снять их при установке, получении или удалении элементов:
xxxxxxxxxx
1
public abstract class AbstractConcurrentMap<K, V> implements ConcurrentMap<K, V> {
2
// constructor, fields and other methods
4
protected abstract void acquire(Entry<K, V> entry);
5
protected abstract void release(Entry<K, V> entry);
6
}
Также мы должны инициализировать реализацию с заранее определенным количеством сегментов:
Джава
xxxxxxxxxx
1
public abstract class AbstractConcurrentMap<K, V> implements ConcurrentMap<K, V> {
2
protected static final int INITIAL_CAPACITY = 100;
4
protected List<Entry<K, V>>[] table;
5
protected int size = 0;
6
public AbstractConcurrentMap() {
8
table = (List<Entry<K, V>>[]) new List[INITIAL_CAPACITY];
9
for (var i = 0; i < INITIAL_CAPACITY; i++) {
10
table[i] = new ArrayList<>();
11
}
12
}
13
// omitted
15
}
Один размер подходит всем?
Что происходит, когда количество хранимых элементов намного больше, чем количество сегментов? Даже при наличии самых универсальных хеш-функций производительность нашей хеш-таблицы значительно снизится. Чтобы предотвратить это, нам нужно добавить больше сегментов при необходимости:
Джава
xxxxxxxxxx
1
protected abstract boolean shouldResize();
2
protected abstract void resize();
С помощью этих абстрактных методов шаблона, вот как мы можем поместить новую пару ключ-значение в нашу карту:
Джава
xxxxxxxxxx
1
2
public boolean put(K key, V value) {
3
if (key == null) return false;
4
var entry = new Entry<>(key, value);
6
acquire(entry);
7
try {
8
var bucketNumber = findBucket(entry);
9
var currentPosition = table[bucketNumber].indexOf(entry);
10
if (currentPosition == -1) {
11
table[bucketNumber].add(entry);
12
size++;
13
} else {
14
table[bucketNumber].add(currentPosition, entry);
15
}
16
} finally {
17
release(entry);
18
}
19
if (shouldResize()) resize();
21
return true;
22
}
23
protected int findBucket(Entry<K, V> entry) {
25
return abs(entry.hashCode()) % table.length;
26
}
Чтобы найти корзину для нового элемента, мы полагаемся на hashcodeключ. Также мы должны рассчитать hashcodeмодуль количества сегментов, чтобы избежать выхода за пределы!
Остальные части довольно просты: мы получаем блокировку для новой записи и добавляем запись только в том случае, если она еще не существует. В противном случае мы бы обновили текущую запись. В конце операции, если мы пришли к такому выводу, что нам нужно добавить больше блоков, то мы сделаем это, чтобы сохранить баланс хеш-таблицы. getИ removeметоды могут быть реализованы как легко.
Давайте заполним пробелы, реализовав все эти абстрактные методы!
Один замок, чтобы управлять ими всеми
Самый простой способ реализовать поточно-ориентированную версию этой структуры данных - это использовать только одну блокировку для всех своих операций:
Джава
xxxxxxxxxx
1
public final class CoarseGrainedConcurrentMap<K, V> extends AbstractConcurrentMap<K, V> {
2
private final ReentrantLock lock;
4
public CoarseGrainedConcurrentMap() {
6
super();
7
lock = new ReentrantLock();
8
}
9
11
protected void acquire(Entry<K, V> entry) {
12
lock.lock();
13
}
14
16
protected void release(Entry<K, V> entry) {
17
lock.unlock();
18
}
19
// omitted
21
}
Текущие реализации получения и выпуска полностью независимы от записи карты. Как и было обещано, мы используем только один ReentrantLockдля синхронизации. Этот подход известен как грубая синхронизация, поскольку мы используем только одну блокировку для обеспечения эксклюзивного доступа ко всей хеш-таблице.
Кроме того, мы должны изменить размер хеш-таблицы, чтобы поддерживать ее постоянный доступ и время модификации. Для этого мы можем использовать разные эвристики. Например, когда средний размер корзины превышает определенное число:
Джава
xxxxxxxxxx
1
2
protected boolean shouldResize() {
3
return size / table.length >= 5;
4
}
Чтобы добавить больше сегментов, мы должны скопировать текущую хеш-таблицу и создать новую таблицу, скажем, в два раза больше. Затем добавьте все записи из старой таблицы в новую:
Джава
xxxxxxxxxx
1
2
protected void resize() {
3
lock.lock();
4
try {
5
var oldTable = table;
6
var doubledCapacity = oldTable.length * 2;
7
table = (List<Entry<K, V>>[]) new List[doubledCapacity];
9
for (var i = 0; i < doubledCapacity; i++) {
10
table[i] = new ArrayList<>();
11
}
12
for (var entries : oldTable) {
14
for (var entry : entries) {
15
var newBucketNumber = abs(entry.hashCode()) % doubledCapacity;
16
table[newBucketNumber].add(entry);
17
}
18
}
19
} finally {
20
lock.unlock();
21
}
22
}
Обратите внимание, что мы также должны получить и снять ту же блокировку для операции изменения размера.
Последовательное узкое место
Предположим, есть три одновременных запроса для помещения чего-либо в первый сегмент, получения чего-либо из третьего набора и удаления чего-либо из шестого набора:
В идеале мы ожидаем, что параллельная структура данных с высокой степенью масштабируемости будет обслуживать такие запросы с минимально возможной координацией. Однако вот что происходит в реальном мире:
Поскольку мы используем только одну блокировку для синхронизации, параллельные запросы будут заблокированы позади первой, которая получила блокировку. Когда первый снимает блокировку, второй получает ее и через некоторое время снимает ее.
Это явление известно как «Последовательное узкое место» (что-то вроде главы блокирования линий), и мы должны смягчить этот эффект в параллельных средах.
Соединенные полосы замков
Одним из способов улучшить нашу текущую грубую реализацию является использование набора блокировок вместо одной блокировки. Таким образом, каждая блокировка будет отвечать за синхронизацию одного или нескольких сегментов. Это более точная синхронизация по сравнению с нашим текущим подходом:
Здесь мы разделяем хеш-таблицу на несколько частей и синхронизируем каждую часть независимо. Таким образом мы уменьшаем конкуренцию за каждую блокировку и, следовательно, улучшаем пропускную способность. Эта идея также называется Lock Striping, потому что мы синхронизируем разные части (т.е. полосы) независимо:
Джава
xxxxxxxxxx
1
public final class LockStripedConcurrentMap<K, V> extends AbstractConcurrentMap<K, V> {
2
private final ReentrantLock[] locks;
4
public LockStripedConcurrentMap() {
6
super();
7
locks = new ReentrantLock[INITIAL_CAPACITY];
8
for (int i = 0; i < INITIAL_CAPACITY; i++) {
9
locks[i] = new ReentrantLock();
10
}
11
}
12
// omitted
14
}
Нам нужен метод, чтобы найти соответствующую блокировку для каждой записи (т. Е. Корзины):
Джава
xxxxxxxxxx
1
private ReentrantLock lockFor(Entry<K, V> entry) {
2
return locks[abs(entry.hashCode()) % locks.length];
3
}
Затем мы можем получить и снять блокировку для операции с определенной записью следующим образом:
Джава
xxxxxxxxxx
1
2
protected void acquire(Entry<K, V> entry) {
3
lockFor(entry).lock();
4
}
5
7
protected void release(Entry<K, V> entry) {
8
lockFor(entry).unlock();
9
}
Процедура изменения размера почти такая же, как и раньше. Единственное отличие состоит в том, что мы должны получить все блокировки до изменения размера и освободить их после изменения размера.
Мы ожидаем, что мелкозернистый подход превзойдет крупнозернистый, давайте измерим его!
Момент истины
Чтобы сравнить эти два подхода, мы собираемся использовать следующую рабочую нагрузку в обеих реализациях:
Джава
xxxxxxxxxx
1
final int NUMBER_OF_ITERATIONS = 100;
2
final List<String> KEYS = IntStream.rangeClosed(1, 100)
3
.mapToObj(i -> "key" + i).collect(toList());
4
void workload(ConcurrentMap<String, String> map) {
6
var requests = new CompletableFuture<?>[NUMBER_OF_ITERATIONS * 3];
7
for (var i = 0; i < NUMBER_OF_ITERATIONS; i++) {
8
requests[3 * i] = CompletableFuture.supplyAsync(
9
() -> map.put(randomKey(), "value")
10
);
11
requests[3 * i + 1] = CompletableFuture.supplyAsync(
12
() -> map.get(randomKey())
13
);
14
requests[3 * i + 2] = CompletableFuture.supplyAsync(
15
() -> map.remove(randomKey())
16
);
17
}
18
CompletableFuture.allOf(requests).join();
20
}
21
String randomKey() {
23
return KEYS.get(ThreadLocalRandom.current().nextInt(100));
24
}
Каждый раз мы ставим случайный ключ, получаем случайный ключ и удаляем случайный ключ. Каждая рабочая нагрузка будет выполнять эти три операции 100 раз. При добавлении JMH в смесь каждая рабочая нагрузка будет выполняться тысячи раз:
Джава
xxxxxxxxxx
1
2
(Throughput)
3
public void forCoarseGrainedLocking() {
4
workload(new CoarseGrainedConcurrentMap<>());
5
}
6
8
(Throughput)
9
public void forStripedLocking() {
10
workload(new LockStripedConcurrentMap<>());
11
}
В целом реализация может обрабатывать в среднем 8547 операций в секунду:
Джава
xxxxxxxxxx
1
8547.430 ±(99.9%) 58.803 ops/s [Average]
3
(min, avg, max) = (8350.369, 8547.430, 8676.476), stdev = 104.523
4
CI (99.9%): [8488.627, 8606.234] (assumes normal distribution)
С другой стороны, мелкозернистая реализация может обрабатывать в среднем до 13 855 операций в секунду.
Джава
xxxxxxxxxx
1
13855.946 ±(99.9%) 119.109 ops/s [Average]
2
(min, avg, max) = (13524.367, 13855.946, 14319.174), stdev = 211.716
3
CI (99.9%): [13736.837, 13975.055] (assumes normal distribution)
Рекурсивные сплит-упорядоченные списки
В своем документе Ори Шалев и Нир Шавит предложили способ реализации хеш-таблицы без блокировки. Они использовали способ упорядочения элементов в связанном списке, чтобы их можно было несколько раз «разделить» с помощью одной операции сравнения и замены. В любом случае, они использовали совершенно другой подход для реализации этой параллельной структуры данных. Настоятельно рекомендуется проверить и прочитать эту статью.
Также исходные коды этой статьи доступны на Github .