Въведение в Lock Striping

1. Въведение

В този урок ще научим как да постигнем фина синхронизация, известна още като Lock Striping, модел за обработка на едновременен достъп до структури от данни, като същевременно поддържаме добра производителност.

2. Проблемът

HashMap не е нишкобезопасна структура от данни поради несинхронизирания си характер. Това означава, че командите от многонишкова среда могат да доведат до несъответствие на данните.

За да преодолеем този проблем, можем или да конвертираме оригиналната карта с метода Collections # synchronizedMap , или да използваме структурата от данни на HashTable . И двете ще върнат безопасно изпълнение на интерфейса на Map , но те са с цената на производителността.

Подходът за дефиниране на изключителен достъп до структури от данни с един обект на заключване се нарича грубозърнеста синхронизация .

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

Нашата цел е да позволим на едновременните нишки да работят върху структурата на данните, като същевременно гарантираме безопасност на нишките.

3. Заключване на ивици

За да постигнем целта си, ще използваме шаблона Lock Striping. Заключването на ивици е техника, при която заключването се случва на няколко групи или ивици, което означава, че достъпът до групата заключва само тази група, а не цялата структура на данните.

Има няколко начина да направите това:

  • Първо, бихме могли да използваме заключване за задача, като по този начин максимизираме едновременността между задачите - това обаче има по-голям отпечатък от паметта
  • Или можем да използваме едно заключване за всяка задача, което използва по-малко памет, но също така компрометира производителността в паралелност

За да ни помогне да управляваме този компромис между производителността и паметта, Guava се доставя с клас, наречен Striped. Подобно е на логиката, открита в ConcurrentHashMap , но класът Striped отива още по-далеч, като намалява синхронизацията на отделни задачи, използвайки семафори или реентрантни брави.

4. Бърз пример

Нека направим бърз пример, който да ни помогне да разберем ползите от този модел.

Ще сравним HashMap спрямо ConcurrentHashMap и единична ключалка срещу раирана ключалка, което ще доведе до четири експеримента.

За всеки експеримент ще изпълняваме едновременно четене и запис на основната карта . Това, което ще варира, е как получаваме достъп до всяка група.

И за това ще създадем два класа - SingleLock и StripedLock. Това са конкретни реализации на абстрактния клас ConcurrentAccessExperiment, който върши работата.

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

Тъй като ще използваме Striped класа на Guava , ще добавим зависимостта на guava :

 com.google.guava guava 28.2-jre 

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

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

public abstract class ConcurrentAccessExperiment { public final Map doWork(Map 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 map, int key); protected abstract Supplier getSupplier(Map map, int key); }

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

4.3. Едновременен достъп с ReentrantLock

Сега ще приложим методите за нашите асинхронни задачи.

Нашият клас SingleLock дефинира едно заключване за цялата структура от данни, използвайки ReentrantLock :

public class SingleLock extends ConcurrentAccessExperiment { ReentrantLock lock; public SingleLock() { lock = new ReentrantLock(); } protected Supplier putSupplier(Map map, int key) { return (()-> { lock.lock(); try { return map.put("key" + key, "value" + key); } finally { lock.unlock(); } }); } protected Supplier getSupplier(Map 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 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 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.