4.1 Cohérence à propos de Brewera
Pour commencer, Eric Brewer n'est pas, et n'a jamais prétendu être, un expert en bases de données. Il appartient à la communauté des systèmes distribués, et son célèbre exposé, dans lequel apparaît le "théorème" CAP, a été donné lors de la conférence "Principles of Distributed Computing". (Au fait, dix ans plus tard, en 2010, il a de nouveau donné une conférence invitée à la même conférence, et dans cette conférence, il a notamment donné un certain nombre d'exemples de systèmes distribués, dont le développement a pris en compte le " théorème" de CAP.) Dans ce domaine a sa propre interprétation des termes utilisés dans le domaine des bases de données.
En particulier, le terme "cohérence immédiate" signifie qu'après que l'utilisateur a reçu une notification du système concernant la réussite d'une opération de mise à jour de données, le résultat de cette opération devient instantanément visible pour tous les observateurs.
La cohérence éventuelle signifie que si aucune nouvelle opération de mise à jour des données n'entre dans le système pendant une période suffisamment longue, on peut s'attendre à ce que les résultats de toutes les opérations de mise à jour des données précédentes finissent par se propager à tous les nœuds du système, et toutes les répliques de données sont cohérent (apparemment, cela devrait être compris comme "toutes les répliques auront le même état".
Avec ce sens de la cohérence à l'esprit, le "théorème" de Brewer peut être considéré comme tout à fait compréhensible et évident : dans tout système distribué avec des données partagées, seules deux propriétés quelconques de cohérence, de disponibilité et de tolérance de partition du réseau peuvent être assurées simultanément. À cet égard, Brewer oppose même l'ensemble des propriétés ACID à son ensemble proposé de propriétés BASE (basiquement disponible, état souple, cohérence éventuelle - disponibilité dans la plupart des cas ; état instable ; cohérence finale). Mais cette opposition, à mon avis, est injustifiée, car dans le premier cas, nous parlons des caractéristiques logiques des transactions, et dans le second - des propriétés physiques des systèmes distribués.
4.2 Preuve du "théorème"
Beaucoup pensent que le "théorème" de Brewer a été formellement prouvé. En effet, l'article de Seth Gilbert et Nancy Lynch introduit quelques définitions (presque) formelles dans lesquelles le "théorème" devient réellement un théorème et est prouvé. Cependant, voyons comment ces trois propriétés d'un système distribué sont déterminées, dont, selon le "théorème de Brewer", seules deux propriétés peuvent être prises en charge simultanément.
La cohérence est appelée cohérence atomique ou linéarisable (cohérence atomique ou linéarisable), qui est une propriété du système, dont tous les objets de données individuels sont atomiques (linéarisables). À son tour, un objet atomique est un objet avec plusieurs opérations, de sorte que l'appel de l'opération et la réception des données de réponse se produisent comme s'ils étaient instantanés, c'est-à-dire l'objet n'accepte pas l'appel de l'opération suivante tant que l'opération précédente n'est pas complètement terminée. L'ordre dans lequel les opérations sont reçues doit être tel que si une opération de type lecture arrive après qu'une opération de type écriture a été effectuée, alors l'opération de lecture doit renvoyer la valeur écrite par cette opération d'écriture ou une opération d'écriture ultérieure.
Un système distribué est toujours disponible si chaque demande reçue par un nœud non défaillant doit recevoir une réponse. La résilience du système à la partition du réseau est modélisée comme la préservation de la viabilité du système en cas de perte d'un nombre arbitraire de messages envoyés d'un nœud à un autre.
Sur la base de ces définitions, Hilbert et Lynch formulent le théorème suivant (il n'y a pas d'horloge dans le modèle de réseau asynchrone, et les nœuds doivent prendre des décisions uniquement sur la base des messages reçus et des calculs locaux) :
Dans un modèle de réseau asynchrone, il n'est pas possible d'implémenter un objet de données en lecture/écriture qui garantit les propriétés de disponibilité et de cohérence atomique pour toutes les exécutions valides (y compris celles qui perdent des messages).
Ce théorème est en réalité tout simplement prouvé formellement par la méthode "par contradiction". L'article poursuit en concluant que :
Dans un modèle de réseau asynchrone, il n'est pas possible d'implémenter un objet de données en lecture/écriture qui garantit les propriétés d'accessibilité pour toutes les exécutions valides et la cohérence atomique pour les exécutions valides dans lesquelles les messages ne sont pas perdus.
De plus, la vérité du théorème principal est prouvée pour un modèle de réseau partiellement synchrone, dans lequel chaque nœud a une horloge, dont le temps indiqué augmente au même rythme, mais qui ne sont pas synchronisés, c'est-à-dire peut montrer des moments différents au même moment réel. Il est montré que pour ce cas, une conséquence similaire n'est pas dérivée et, par conséquent, pour les réseaux partiellement synchrones, il existe plus de possibilités d'organiser des systèmes distribués avec de "bonnes" propriétés.
Oui, dans un sens (pas nécessairement le même que celui de Brewer), Gilbert et Lynch peuvent être considérés comme ayant prouvé qu'il est impossible d'assurer simultanément les propriétés de cohérence atomique, de disponibilité et de tolérance de partition d'un réseau dans un seul système distribué. Mais qu'est-ce que cela a à voir avec les transactions de base de données en général et les transactions ACID en particulier ?
4.3 Transactions ACID
Voici ce qu'écrit Julian Browne à ce sujet dans sa note sur la discussion du "théorème" de CAP :
Dans leur preuve, Hilbert et Lynch utilisent le terme d'atomicité au lieu de cohérence, ce qui est plus logique d'un point de vue technique car, à proprement parler, la cohérence au sens d'ACID fait référence aux propriétés idéales des transactions de base de données et signifie qu'aucune donnée ne sera deviennent persistants s'ils violent certaines restrictions préétablies. Mais si nous supposons qu'une limitation préétablie des systèmes distribués est l'interdiction de la présence de plusieurs valeurs différentes pour le même élément de données, alors, à mon avis, cette faille dans l'abstraction de cohérence peut être considérée insignifiant (de plus, si Brewer utilisait le terme d'atomicité, alors le théorème AAP apparaîtrait, dont le nom serait extrêmement gênant à prononcer).
Ceci est écrit pas très sérieusement, mais honnêtement. Et, de fait, l'exigence de cohérence atomique ne doit pas être confondue avec les exigences de cohérence transactionnelle au sens d'ACID. Les contraintes d'intégrité de la base de données sont logiques, si vous voulez, les exigences de l'entreprise. Ils proviennent de la logique du domaine d'application. L'exigence de cohérence atomique est d'une tout autre nature. Il s'agit d'une exigence de mise en œuvre qui entre dans la catégorie traditionnellement désignée dans l'industrie des bases de données sous le nom de cohérence physique (par exemple, lors de l'exécution de toute opération de changement d'index, tous les blocs de l'arbre B+ correspondant doivent contenir des valeurs valides et être liés par des références valides ).
Et voici ce que les représentants de la communauté des bases de données Daniel Abadi et Alexander Thomson écrivent assez sérieusement dans leur note :
... l'exigence de disponibilité de systèmes transactionnels évolutifs devient de plus en plus critique, et cela est généralement satisfait par la réplication et la redirection automatique des requêtes en cas de défaillance de l'un des nœuds. Par conséquent, les développeurs d'applications s'attendent à ce que les garanties de cohérence des systèmes ACID (constituées à l'origine d'un support local pour les invariants définis par l'utilisateur) soient étendues pour assurer une cohérence forte (que toutes les répliques des mêmes données à un moment donné soient des copies identiques, c'est-à-dire dans cette cohérence de cas est implicite au sens du CAP/PACELC.
En d'autres termes, la cohérence de Brewer n'a rien à voir avec la cohérence au sens d'ACID, mais c'est dans les systèmes axés sur la fourniture d'une haute disponibilité via la réplication des données qu'il est souhaitable de maintenir une forte cohérence des répliques. Il ne s'agit pas d'une propriété ACID, mais d'une caractéristique technique (physique) du SGBD massivement parallèle qui facilite le développement d'applications.
Selon Michael Stonebreaker, la clé de la construction d'un SGBD moderne de haute qualité est le bon choix de compromis techniques. Lors du choix d'une solution d'ingénierie spécifique, de nombreux facteurs doivent être pris en compte - les exigences des futurs utilisateurs, la probabilité de diverses situations de défaillance, etc., et ne pas être guidé dogmatiquement par des directives théoriques générales (y compris le "théorème" CAP).
Stonebreaker estime que dans le domaine des systèmes de bases de données parallèles transactionnelles, abandonner la cohérence de Brewer au profit de la prise en charge de la haute disponibilité et de la tolérance aux partitions réseau est un mauvais compromis car (a) la cohérence des répliques est une fonctionnalité très utile du système ; (b) les SGBD transactionnels massivement parallèles n'ont pas besoin de clusters avec un très grand nombre de nœuds, de sorte que les situations de division du réseau sont peu probables ; (c) le système peut facilement devenir indisponible, non pas à cause d'une partition du réseau, mais, par exemple, à cause de la présence d'erreurs logicielles récurrentes.
Ainsi, la forte activité des représentants du camp NoSQL (lire NoACID), qui se réfèrent souvent au "théorème" de Brewer, n'est pas liée à l'impossibilité théorique de construire des SGBD transactionnels massivement parallèles supportant les transactions ACID, mais au fait que des systèmes simplifiés qui ne prennent pas uniquement en charge les transactions ACID, mais également la cohérence des répliques, sont créés plus facilement et plus rapidement. En raison de leur organisation simpliste, ils sont capables d'un traitement de données très rapide, et pour certaines applications, cela est plus important que toutes les commodités inhérentes à la technologie des bases de données.
Voyons comment la communauté des bases de données répond à ce défi.