Introduction à Lock Striping

1. Introduction

Dans ce didacticiel, nous allons apprendre à réaliser une synchronisation fine, également connue sous le nom de Lock Striping, un modèle pour gérer l'accès simultané aux structures de données tout en conservant de bonnes performances.

2. Le problème

HashMap n'est pas une structure de données thread-safe en raison de sa nature non synchronisée. Cela signifie que les commandes d'un environnement multi-thread peuvent entraîner une incohérence des données.

Pour résoudre ce problème, nous pouvons soit convertir la carte d'origine avec la méthode Collections # synchronizedMap , soit utiliser la structure de données HashTable . Les deux renverront une implémentation thread-safe de l' interface Map , mais ils se font au détriment des performances.

L'approche consistant à définir un accès exclusif sur des structures de données avec un seul objet de verrouillage est appelée synchronisation grossière .

Dans une implémentation de synchronisation grossière, chaque accès à l'objet doit être effectué à la fois par un thread. Nous finissons par avoir des accès séquentiels.

Notre objectif est de permettre aux threads concurrents de travailler sur la structure de données tout en garantissant la sécurité des threads.

3. Verrouiller la bande

Pour atteindre notre objectif, nous utiliserons le motif Lock Striping. L'entrelacement de verrouillage est une technique où le verrouillage se produit sur plusieurs compartiments ou bandes, ce qui signifie que l'accès à un compartiment verrouille uniquement ce compartiment et non la structure de données entière.

Il y a plusieurs façons de faire ça:

  • Premièrement, nous pourrions utiliser un verrou par tâche, maximisant ainsi la concurrence entre les tâches - cela a une empreinte mémoire plus élevée, bien que
  • Ou, nous pourrions utiliser un seul verrou pour chaque tâche, ce qui utilise moins de mémoire mais compromet également les performances de la concurrence

Pour nous aider à gérer ce compromis performances-mémoire, Guava est livré avec une classe appelée Striped. C'est similaire à la logique trouvée dans ConcurrentHashMap , mais la classe Striped va encore plus loin en réduisant la synchronisation de tâches distinctes à l'aide de sémaphores ou de verrous réentrants.

4. Un exemple rapide

Faisons un exemple rapide pour nous aider à comprendre les avantages de ce modèle.

Nous comparerons HashMap vs ConcurrentHashMap et un seul verrou vs un verrou rayé résultant en quatre expériences.

Pour chaque expérience, nous effectuerons des lectures et des écritures simultanées sur la carte sous-jacente . Ce qui variera, c'est la façon dont nous accédons à chaque compartiment.

Et pour cela, nous allons créer deux classes - SingleLock et StripedLock. Ce sont des implémentations concrètes d'une classe abstraite ConcurrentAccessExperiment qui fait le travail.

4.1. Dépendances

Puisque nous allons utiliser la classe Striped de Guava , nous ajouterons la dépendance goyave :

 com.google.guava guava 28.2-jre 

4.2. Processus principal

Notre classe ConcurrentAccessExperiment implémente le comportement décrit précédemment:

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); }

Il est important de noter que, comme notre test est lié au processeur, nous avons limité le nombre de buckets à un multiple des processeurs disponibles.

4.3. Accès simultané avec ReentrantLock

Nous allons maintenant implémenter les méthodes pour nos tâches asynchrones.

Notre classe SingleLock définit un verrou unique pour toute la structure de données à l'aide d'un 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. Accès simultané avec rayé

Ensuite, la classe StripedLock définit un verrou par bandes pour chaque compartiment:

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(); } }); } }

Alors, quelle stratégie est la plus performante?

5. Résultats

Utilisons JMH (le Java Microbenchmark Harness) pour le découvrir. Les benchmarks peuvent être trouvés via le lien du code source à la fin du tutoriel.

En exécutant notre benchmark, nous sommes en mesure de voir quelque chose de similaire à ce qui suit (notez qu'un débit plus élevé est préférable):

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. Conclusions

Dans ce didacticiel, nous avons exploré différentes manières d'obtenir de meilleures performances en utilisant le verrouillage par bandes dans des structures de type Map . Nous avons créé un benchmark pour comparer les résultats avec plusieurs implémentations.

À partir de nos résultats de référence, nous pouvons comprendre comment différentes stratégies simultanées pourraient affecter de manière significative le processus global. Le motif Striped Lock offre une amélioration considérable car il obtient environ 10% de plus avec HashMap et ConcurrentHashMap .

Comme d'habitude, le code source de ce tutoriel est disponible à l'adresse over sur GitHub.