La classe ConcurrentDictionary en .NET est une implémentation thread-safe d’une hashtable ; au vu de son nom il est facile de l’imaginer comme l’alternative sûre et “standard” du classique Dictionary. En pratique c’est un peu plus compliqué que ça …
Objectif
On cherche à partager une hashtable entre plusieurs threads d’un même processus, qui peuvent simultanément la lire et/ou la modifier.
Comme toutes les structures pouvant être modifiées par plusieurs threads à la fois, il est impératif de synchroniser les accès, sous peine de s’exposer à un comportement indéterminé (et fréquemment catastrophique).
Prenons l’exemple d’un Dictionary classique, si deux threads A et B essaient d’ajouter une clé en même temps, et en l’absence de synchronisation :
- le thread A commence à ajouter sa clé,
- le thread B essaie d’ajouter sa clé et peut voir le dictionnaire dans au moins trois états différents :
- soit il est complètement à jour : le thread B peut ajouter sa clé, tout se passe bien.
- soit il n’est pas du tout à jour : le thread B ajoute sa clé avant le thread A, mais tout se passe bien
- soit il est partiellement à jour : le thread A est en train d’ajouter sa clé. Le comportement du thread B sera alors indéterminé*
(* tirer un dé 20 sur la table des désastres, qui contient : exceptions aléatoires, boucle infinie, corruption des données, deadlocks …)
Le comportement devient aléatoire : plus le nombre de threads tentant de modifier le dictionnaire en parallèle sont importants, plus la probabilité que le programme explose en flammes augmente. Pire encore, cela dépend également du nombre de cores CPU de la machine : plus le système peut exécuter de threads simultanément, plus le problème a de chance d’arriver.
Pour illustrer le cas :
Dictionary<int, string> dictionary = new Dictionary<int, string>();
Parallel.For(0, 100000, i =>
{
dictionary.Add(i, "foo");
// exception quasi systématique avec 100000 itérations ou plus
});
Cette situation n’est évidemment pas tenable et constitue un bug particulièrement vicieux à détecter, puisque les “symptômes” sont variables. Il faut donc trouver un moyen de synchroniser les modifications.
Le ConcurrentDictionary
Le ConcurrentDictionary est une implémentation alternative de Dictionary (et pas une “surcouche thread safe”), qui permet de synchroniser les accès en implémentant une stratégie de verrouillage dite optimiste :
- on part du principe que la majorité des opérations seront des lectures,
- on assume que les écritures (ajouts/modifications/suppressions) des différents threads se feront la plupart du temps sur des clés différentes.
- dans le cas rare où deux threads (ou plus) essaient de créer ou modifier la même clé, on peut se permettre de perdre des modifications.
En gros on assume le meilleur des mondes, dans lequel la synchronisation n’est presque pas nécessaire.
A cette fin, la classe effectue deux choix majeurs :
- elle ne verrouille pas les accès en lecture, elle travaille sur une copie partielle des données à la place (aussi appelé un snapshot, ou instantané) ;
- elle synchronise toutes les écritures par des verrous, et elle essaie de minimiser au maximum le temps passé dans ces verrous.
Concernant les verrous, plutôt que de n’avoir qu’un verrou global n’autorisant qu’une modification à la fois, la classe utilise une petite liste de verrous protégeant chacun une portion des données : cela permet ainsi d’écrire potentiellement plusieurs clés en parallèle.
Implémentation
Les classes Dictionary et ConcurrentDictionary en .NET stockent leurs données de la façon suivante :
Lorsqu’une clé doit être ajoutée, on en calcule son hash, qui est exprimé sous la forme d’un int en C# (c’est le retour de la “fameuse” méthode GetHashCode(), implémentée par tous les descendants de object en .NET).
Le dictionnaire contient un tableau de buckets qui sont eux-même des listes chaînées de valeur. Lorsque l’on souhaite ajouter une valeur, on choisit un bucket en calculant le modulo de son hash sur le nombre de buckets disponible.
On stocke ensuite la valeur à la fin de la liste chaînée de ce bucket. Si la fonction de hash utilisée est de bonne qualité, chaque bucket va recevoir approximativement autant de valeurs que les autres.
Par exemple si l’on stocke 1000 valeurs dans 4 buckets, chacun de ces buckets devrait contenir plus ou moins 250 valeurs, garantissant ainsi un temps d’accès quasiment constant.
Enfin, la classe va elle-même réorganiser le nombre de buckets au fur et à mesure des ajouts, pour conserver des temps d’accès raisonnables.
Voyons quelques unes des opérations principales du ConcurrentDictionary :
TryGetValue()
Essaie de lire une valeur à partir de sa clé, et renvoie false si la clé n’a pas été trouvée. C’est l’équivalent “atomique” d’un ContainsKey() suivi d’une lecture de clé sur un Dictionary classique.
Il serait faux d’appeller une hypothétique méthode ContainsKey() (qui ne verrouille pas) pour savoir si la clé existe avant d’en lire la valeur, car un autre thread peut tout à fait supprimer la clé après l’appel à ContainsKey() mais avant la lecture du premier thread.
if (dictionary.ContainsKey(foo))
{
// <- un autre thread peut supprimer la clé à ce moment-là
var value = dictionary[foo];
// indéterminé : la clé n'existe peut-être plus !
}
Le code ne verrouille pas le dictionnaire pendant la lecture, il récupère simplement le bucket correspondant à la clé en paramètre, puis lit la liste chaînée correspondante via une méthode Volatile.Read(), thread-safe, dont le fonctionnement dépasse l’objet de cet article.
TryAdd()
Essaie d’ajouter une clé et sa valeur ; si la clé existe déjà la méthode n’a aucun effet et renvoie false :
dictionary.TryAdd("foo", "bar"); // la clé "foo" contient "bar"
dictionary.TryAdd("foo", "baz"); // la clé "foo" contient TOUJOURS "bar" !
Dans un scénario où plusieurs threads essaient d’ajouter la même clé simultanément, la valeur associée à une clé sera celle écrite lors du premier appel à TryAdd(), elle ne sera pas mise à jour par les appels suivants et ne lèvera aucune erreur.
Si tous les threads essaient d’insérer la même valeur, tout va bien. Si cela n’est pas le cas cela peut créer quelques surprises …
Il peut donc être utile de vérifier le code de retour de TryAdd(), qui indiquera si oui ou non la clé a été créée par ce thread.
Lors de l’appel à cette méthode, et uniquement si la clé n’existe pas déjà, le ConcurrentDictionary verrouille le bucket qui va accueillir la clé, et quelques autres buckets adjacents, selon son algorithme interne.
GetOrAdd()
Essaie d’ajouter une nouvelle clé/valeur si elle n’existe pas, ou renvoie la valeur existante si elle existe déjà.
Très utile pour implémenter un cache, mais ne permet pas de mettre à jour la valeur associée à une clé existante. C’est en fait le cas idéal d’utilisation d’un ConcurrentDictionary.
AddOrUpdate()
La plus intéressante, et la plus complexe.
Essaie d’ajouter une clé et sa valeur ; et si la clé existe déjà, appelle une fonction fournie en paramètre pour mettre à jour la valeur déjà présente.
ConcurrentDictionary<string, int> cd = new ConcurrentDictionary<string, int>();
Parallel.For(0, 10000, i =>
{
cd.AddOrUpdate("foo", 1, (key, oldValue) => oldValue + 1);
// ici on passe une fonction anonyme (ou lambda),
// prenant en paramètre la clé et la valeur existante,
// et qui doit renvoyer la nouvelle valeur à enregister
// "foo" vaut 1, puis 2, puis 3, et ainsi de suite.
});
// la clé "foo" contient 10000.
La subtilité vient de la fonction de mise à jour fournie : comme c’est le développeur qui la fournit, .NET ne peut savoir si elle est rapide ou lente, si elle peut lever des exceptions ou non, ou même si elle se termine bien à tous les coups.
Le ConcurrentDictionary fait donc le choix de ne pas exécuter cette fonction sous son verrou d’écriture habituel, pour essayer de limiter les comportements indéterminés.
Par conséquent cette fonction de mise à jour s’effectue sans verrou ; le contenu du ConcurrentDictionary peut donc être modifié pendant que cette fonction s’exécute ; la clé pourrait même avoir disparue.
Par exemple, si l’on essaie de supprimer la clé pendant qu’elle est mise à jour :
Parallel.For(0, 10000, i =>
{
if (i % 4 == 0) // une itération sur 4 essaie de supprimer la clé
{
int val;
cd.TryRemove("foo", out val);
}
else // trois itérations sur 4 essaient de créer puis d'incrémenter la clé
{
cd.AddOrUpdate("foo", 1, (key, oldValue) => oldValue + 1);
}
});
// la clé "foo" peut contenir 1, 2, 3 ... ou plus, ou ne plus exister du tout
// le résultat sera aléatoire car Parallel.For ne garantit pas l'ordre des itérations.
Opérateur []
L’opérateur [] du ConcurrentDictionary appelle simplement TryGetValue ou TryAddInternal (équivalent à TryAdd) (source) :
public TValue this[TKey key]
{
get
{
TValue value;
if (!TryGetValue(key, out value))
{
throw new KeyNotFoundException();
}
return value;
}
set
{
if (key == null) throw new ArgumentNullException("key");
TValue dummy;
TryAddInternal(key, value, true, true, out dummy);
}
}
En résumé
La classe ConcurrentDictionary est donc à double tranchant : bien qu’elle permette en effet d’être utilisée de manière thread-safe, il est possible d’avoir quelques surprises lors de son utilisation, particulièrement lorsque les valeurs de retour des différentes méthodes ne sont pas vérifiées.
Elle reste complexe à manipuler, il convient donc de bien comprendre les cas d’usage dans lesquels elle se justifie.
Alternatives
D’autres alternatives existent pour obtenir une hashtable thread-safe, sans passer par le ConcurrentDictionary :
Verrou global
Consiste tout simplement à utiliser le mot-clé lock dans un bloc using autour de tous les accès en lecture et écriture à un Dictionary classique :
object globalLock = new object();
// crée un object dont la référence va servir de verrou global
// doit être être visible de tous les threads qui accèderont au dictionnaire,
// mais ne doit jamais être modifiée par aucun thread
lock (globalLock)
{
// un seul thread à la fois peut être dans cette section du code
if (!dictionary.ContainsKey("foo"))
{
dictionary["foo"] = "bar";
}
// l'instruction lock garantit qu'une exception relâchera immédiatement le verrou
}
Cela a pour effet d’empêcher complètement la moindre lecture ou écriture concurrente au dictionnaire, dans sa totalité.
On parle de concurrence dite pessimiste :
- on part du principe qu’il y aura autant de lectures que d’écritures, voire une majorité d’écritures.
- on assume que les écritures des différents threads se feront potentiellement souvent sur les même clés,
- on n’accepte de “perdre” aucune opération.
C’est un bon compromis à utiliser par défaut, lorsque l’on n’est pas encore sûr de la concurrence réelle :
- la classe est plus simple à manipuler qu’un ConcurrentDictionary,
- le code est plus lisible et plus simple à comprendre : plus d’accès simultanés à la hashtable
C’est également indispensable si par exemple :
- une modification a besoin de voir l’ensemble des données dans la hashtable pour s’exécuter.
- on souhaite modifier la hashtable et en même temps modifier une autre variable synchronisée
- etc.
La perte de performance due à la contention plus élevée ne sera verra réellement que si les lectures sont largement majoritaires, et que les opérations sont très nombreuses ; il est toujours temps à ce moment-là de basculer sur un ConcurrentDictionary.
Pas de verrous
Comme toujours en programmation multi-thread, le meilleur verrouillage est l’absence pure et simple de verrouillage.
Si l’algorithme utilisé peut être écrit de façon à ce que :
- le dictionnaire soit initialisé (écrit) en une seule fois, idéalement par un seul thread,
- le dictionnaire soit ensuite uniquement lu, mais jamais modifié
Il est devient alors possible de se passer complètement de synchronisation et de lire un Dictionary classique à partir de multiples threads en parallèle, avec une performance encore supérieure au ConcurrentDictionary.
Implémentation spécialisée
Bien que plus complexe, il est toujours possible d’implémenter sa propre hashtable, ce qui permettra de faire des compromis différents dans la synchronisation des accès, par exemple :
- en verrouillant plus finement, par exemple clé par clé
- en effectuant les mises à jour entièrement sous un verrou, sans passer par une fonction lambda comme AddOrUpdate()
- en spécialisant la structure interne à un type de clé/valeurs particulières pour gagner en performance
- etc.