Le multithreading zen

La mémoire transactionnelle (ou STM) est un mécanisme de concurrence alternatif au locking classique.

Ce mécanisme permet de réaliser en mémoire des transactions atomiques, cohérentes et isolées. Ces transactions ne sont évidemment pas durables.

Par nature, la STM ne connait ni deadlock ni race condition. Elle ouvre la porte au multithreading zen.

STM is to shared-memory concurrency

as

Garbage Collection is to memory management.

-- Dan Grossman

Usage

Le programmeur doit identifier et marquer les variables de nature transactionnelle. Voici un exemple d'école : un compte en banque.

class Account { Int accountType; STM Int amount; // variable transactionnelle! }

C'est la donnée qui possède un type spécial et informe le compilateur de sa nature transactionnelle. Grâce à cette qualité, le programmeur n'aura pas besoin de créer des locks ni de déclarer des sections critiques. Par contre, il devra déclarer des blocs transactionnels.

Les langages de programmation qui ont un bon support de la STM empêchent l'écriture d'une variable transactionnelle en dehors d'une transaction. Cette sécurité est surtout offerte chez des langages fonctionnels, grâce au typage de ces variables (explication plus bas). Le compilateur n'acceptera pas de sommer directement un Int à un STM Int.

Maintenant, créons une opération simple sur ce compte (pseudo-code) :

// Déposer de l'argent func deposit (account, amount) { atomically { account.amount += amount; } }

Cela ressemble à une section synchronized, mais ça ne l'est pas. Aucun lock pessimiste n'a été posé sur cette fonction, ni sur l'objet qui porte le compte en banque. Le bloc atomically qui délimite la transaction peut être écrit à n'importe quel endroit dans le code, car il n'est pas lié à une classe ou à un fichier. Disons le autrement: la programmation concurrente basée sur des locks impose des limitations sur l'architecture, alors que la STM n'en impose aucune.

En outre, cette fonction deposit est scalable. L'absence de section critique permet de l'exécuter sur N comptes en parallèle. Et si l'objet Account avait plusieurs variables transactionnelles, il serait possible de les modifier de manière concurrente.

En supposant que l'opération withdraw est déjà codée,  on pourra aussi écrire :

// Transférer sous réserve de fonds func transfer (account1, account2, amount) { atomically { if (account1.amount > amount)) { withdraw(account1, amount); deposit(account2, amount); return True; } return False; }

Voilà, c'est tout. Le bloc atomically va être exécuté dans une seule transaction, comme si le langage avait magiquement placé les locks appropriés autour de chaque variable et les avait locké dans l'ordre adéquat. La STM a réussi à composer deux transactions, ce qui est impossible avec l'approche traditionnelle.

Les implications sont enthousiasmantes. Comme la STM sait composer les opérations concurrentes, le programmeur peut écrire chaque opération concurrente indépendamment des autres. Le problème était complexe, donc difficile. Il est devenu simple, donc facile.

Adoption

La bonne nouvelle c'est que des implémentations de STM existent déjà dans beaucoup de langages de programmation (oui, même en Java). La mauvaise, c'est qu'elles marchent d'autant mieux que le langage est fonctionnellement pur.

Les implémentations les plus naturelles sont probablement celles de Haskell, Clojure et Scala, car elles séparent clairement les effets de bords transactionnels des autres I/O, ce qui leur permet d'être plus sûres et plus performantes.

Pour aller plus loin

Alors, comment ça marche? Cette connaissance n'est pas indispensable, sauf pour quelques cas limites de performance. Chaque langage porte une implémentation STM différente. Clojure fonctionne en MVCC, ici nous allons regarder l'implémentation de Haskell.

La STM est de nature optimiste. Elle commence son calcul sans demander permission, et déclenche un rollback à la fin du bloc si elle a provoqué un conflit en écriture. En contraste, les locks sont "pessimistes": ils demandent permission avant même de commencer un calcul.

Un log de transaction vide est créé pour le thread courant au moment de l'appel à atomically.

• Pour chaque écriture, la nouvelle valeur est placée dans le log
• Pour chaque lecture, la STM va chercher sa valeur dans le log (elle a peut-être été écrasée par le thread courant) puis dans la variable ordinaire. Grâce au log, la transaction est bien isolée des autres threads.

Après avoir terminé toutes les opérations, il faut encore valider l'ensemble pour pouvoir commiter (souvenez-vous: des conflits se sont peut-être produit!). La transaction est jugée valide si aucune des variables utilisées en lecture n'a été modifiée depuis la création du log. En pratique, on compare une à une les valeurs de ces variables dans le log et dans la RAM principale pour remarquer une éventuelle différence de valeur. Si tout va bien, le runtime écrase les variables en écriture. Sinon, il faut rollbacker la transaction, c'est à dire effacer le log sans réaliser les écritures prévues. Libre au runtime de relancer la transaction dans la foulée.

Attention: Le rollback ne peut fonctionner correctement que si le programmeur n'a pas introduit d'effet de bord supplémentaire dans la transaction. Il ne doit pas appeler lancerMissile au milieu d'une transaction, sous peine de lancer ses missiles deux fois... Voilà pourquoi les langages fonctionnels sont mieux adaptés à la STM: ils ont moins d'effets de bord. En pratique, certains langages fonctionnels interdisent carrément les actions à effet de bord dans un bloc atomically, via le système de types.

Zoom sur la performance

La STM ne bloquera jamais un accès en lecture. Par contre, un accès répété en écriture sur l'une des variables peut pénaliser la performance (la probabilité de conflit augmentant avec le nombre et la complexité des transactions qui essaient de la modifier).

Le cas le plus défavorable est peut-être celui d'une queue consommée en permanence par 10.000 threads: le nombre de rollbacks peut alors immobiliser la queue (starvation). Dans ce cas, utilisez plutôt une queue ordinaire, ou bien distribuez ces données sur plusieurs queues STM moins sollicitées. De même, évitez la STM si il faut absolument verrouiller une structure volumineuse dans sa totalité, ou si il faut modifier des centaines de variables dans une seule transaction.

La durée de transaction dépend largement de la qualité de la bibliothèque. Par exemple, en Haskell, le compilateur utilise le typage STM pour limiter l'usage du log de transaction au strict minimum. Toutes les lectures/écritures des variables non-STM sont ignorées par le log, ce qui améliore les performances.

La STM brille surtout dans le cas de transactions courtes et réparties sur un grand nombre de variables indépendantes. Dans le cas particulier des structures de données volumineuses (liste chainée, arbre,...), il devient trivial de modifier quelques éléments sans bloquer la structure dans son ensemble (fine-grained locking).

Les apports de la STM sont analogues à ceux d'un garbage collector: elle fiabilise et facilite les développements, tout en étant sensiblement moins performante que des locks posés avec soin par un expert.

Bibliographie

Software Transactional Memory (Wikipedia) Beautiful concurrency : Un parallèle complet et intriguant entre les concepts des GC et de la STM (Dan Grossman)