Quels algorithmes / éléments de lecture recommanderiez-vous pour résoudre les transactions / verrous en lecture-écriture?

Une transaction de base de données classique simplifiée peut être considérée comme:

• lecture de M éléments
• effectuer un calcul basé sur ces lectures
• écrire quelques résultats N basés sur ces calculs, qui peuvent inclure les éléments lus à l'origine.

Lors de l'exécution de ces transactions (simultanément), les propriétés ACID doivent être conservées.

Exactement les mêmes exigences (N mises à jour basées sur M lectures de manière transactionnelle) existent dans d'autres systèmes concurrents non SGBD.

Je suis intéressé à découvrir quels algorithmes existent pour effectuer / résoudre ces transactions, et quelles sont les forces et les faiblesses relatives de ces algorithmes. Pourriez-vous recommander une lecture? Il peut s'agir de livres ou de références / tutoriels en ligne.

Clarification:

Ainsi, par exemple, un algorithme naïf peut faire en sorte que chaque transaction prenne un seul verrou global, forçant en fait le thread unique et supprimant la concurrence. Un algorithme un peu plus compliqué serait les verrous de lecture / écriture des éléments individuels, avec un ordre pour éviter le blocage). Etc, etc. Existe-t-il une bonne source documentant divers algorithmes pour résoudre ce problème. Même une réponse qui n'indiquerait qu'un seul algorithme avec ses forces et ses faiblesses serait utile.

Le livre Transactional Information Systems de Weikum et Vossen couvre une grande partie du domaine, à la fois en termes théoriques et pratiques, à partir de perspectives différentes, pas seulement des transactions. Il fait environ 1 000 pages et vous occupera donc pendant un week-end ou deux. En revanche, il a presque 10 ans, il pourrait donc y avoir quelque chose de plus à jour disponible. D'autres livres dans la ligne incluent le contrôle de la concurrence et la récupération dans les systèmes de bases de données par Bernstein, P., Hadzilacos, V., et Goodman, N, Addison-Wesley, 1987, Transaction Processing: Concepts and Techniques par Jim Gray et Andreas Reuter, et Principles du traitement des transactionspar Philip A. Bernstein et Eric Newcomer, 2009. Je n'ai pas vu ce dernier, mais étant le plus récent, il pourrait être un bon point de départ, bien que votre solution puisse très bien être trouvée dans des textes plus anciens. Un voyage à la bibliothèque peut valoir la peine.

Un texte monumental dans ce domaine est Atomic Transactions de Nancy Lynch et al. Il présente un compte rendu formel et des preuves d'un certain nombre d'algorithmes qui vous intéressent. Il est plutôt formel et fastidieux, donc peut-être pas à votre goût.

De nombreux travaux récents sont consacrés à la mémoire transactionnelle logicielle , qui applique les idées de transaction à des applications multithreads. Il existe des dizaines de publications sur ce sujet chaque année: la page wikipedia propose de nombreuses références.