TrueTime est une horloge distribuée hautement disponible fournie aux applications sur tous les serveurs Google1. TrueTime permet aux applications de générer des horodatages monotones croissants, c'est-à-dire qu'il est garanti qu'un horodatage T calculé par une application est ultérieur à un horodatage T' dans la mesure où la génération de T' est terminée avant que celle de T ne commence. Cette garantie s'exerce pour tous les serveurs et tous les horodatages.
Cette fonctionnalité de TrueTime est utilisée par Spanner pour attribuer des horodatages aux transactions. Plus précisément, chaque transaction se voit attribuer un horodatage qui reflète l'instant où Spanner considère qu'elle s'est produite. Étant donné que Spanner utilise un contrôle de simultanéité multiversion, la garantie de classement des horodatages permet aux clients de Spanner d'effectuer des lectures cohérentes sur l'ensemble d'une base de données (même dans plusieurs régions du cloud) sans bloquer les écritures.
Cohérence externe
Spanner fournit aux clients les garanties de contrôle de simultanéité les plus strictes pour les transactions. Ce processus est appelé cohérence externe2. Sous la cohérence externe, le système se comporte comme si toutes les transactions étaient exécutées de manière séquentielle, même si Spanner les exécute sur plusieurs serveurs (et éventuellement dans plusieurs centres de données) pour améliorer les performances et la disponibilité. De plus, si une transaction est terminée avant qu'une autre transaction ne commence, le système garantit que les clients ne peuvent jamais voir un état qui inclut l'effet de la seconde transaction mais pas de la première. Intuitivement, Spanner est sémantiquement impossible à distinguer d'une base de données à machine unique. Bien qu'il offre des garanties aussi solides, Spanner permet aux applications d'atteindre des performances comparables à celles des bases de données offrant des garanties plus faibles (en échange de performances supérieures). Par exemple, comme les bases de données compatibles avec l'isolation d'instantané, Spanner permet aux écritures de se poursuivre sans être bloquées par des transactions en lecture seule, mais sans présenter les anomalies permises par l'isolation d'instantané.
La cohérence externe simplifie grandement le développement d'applications. Par exemple, supposons que vous ayez créé une application bancaire sur Spanner et que l'un de vos clients commence avec 50 $sur son compte courant et 50 $sur son compte d'épargne. Votre application commence alors un flux de travail dans lequel elle enregistre d'abord une transaction T1 pour déposer 200 $ sur le compte d'épargne, puis une seconde transaction T2 pour débiter 150 $ du compte courant. Supposons également qu'à la fin de la journée, les bilans négatifs d'un compte soient automatiquement couverts par d'autres comptes et que le client encoure une pénalité si le solde total de tous ses comptes est négatif à tout moment de la journée. La cohérence externe garantit que, étant donné que T2 commence après la fin de T1, tous les lecteurs de la base de données constatent que le dépôt T1 a eu lieu avant le débit T2. En d'autres termes, la cohérence externe garantit que personne ne voit jamais un état où T2 se produit avant T1. Le débit n'entraîne donc jamais de pénalité pour cause de fonds insuffisants.
Une base de données traditionnelle utilisant le stockage d'une seule version et le verrouillage strict à deux phases fournit une cohérence externe. Malheureusement, dans un tel système, chaque fois que votre application souhaite lire les données les plus récentes (ce qu'on appelle une "lecture forte"), le système acquiert un verrou en lecture sur les données, ce qui bloque les écritures sur les données en cours de lecture.
Horodatage et contrôle de simultanéité multiversion (MVCC, multi-version concurrency control)
Pour lire sans bloquer les écritures, Spanner et de nombreux autres systèmes de base de données conservent plusieurs versions immuables des données (souvent appelée contrôle de simultanéité multiversion). Une écriture crée une nouvelle version immuable dont l'horodatage est celui de la transaction d'écriture. Une "lecture instantanée" à un horodatage renvoie la valeur de la version la plus récente antérieure à cet horodatage, sans qu'il soit nécessaire de bloquer les écritures. Il est donc important que les horodatages affectés aux versions soient cohérents avec l'ordre dans lequel la validation des transactions se produit. Cette propriété est appelée "horodatage correct". Notez que l'existence d'un horodatage correct équivaut à une cohérence externe.
Pour comprendre l'importance d'un horodatage correct, considérons l'exemple bancaire de la section précédente. Sans horodatage correct, T2 pourrait se voir attribuer un horodatage antérieur à celui attribué à T1 (par exemple, dans le cas où un système hypothétique utiliserait des horloges locales plutôt que TrueTime, et où l'horloge du serveur qui traite T2 serait légèrement décalée). Une lecture d'instantané pourrait alors refléter le débit T2, mais pas le dépôt T1, même si le client a vu l'arrivée du dépôt avant de commencer le débit.
Obtenir un horodatage correct est simple pour une base de données fonctionnant sur une seule machine (vous pouvez, par exemple, simplement attribuer des horodatages à partir d'un compteur global à augmentation monotone). Il est beaucoup plus difficile de le faire efficacement dans un système largement distribué tel que Spanner, dans lequel des serveurs du monde entier doivent attribuer des horodatages.
Spanner dépend de TrueTime pour générer des horodatages monotones croissants. Spanner utilise ces horodatages de deux manières. Tout d'abord, il les utilise comme horodatages corrects pour les transactions d'écriture ne nécessitant pas une communication globale. Il les utilise ensuite comme horodatages pour les lectures fortes, ce qui permet à ces dernières de s'exécuter dans un cycle de communication, même pour celles concernant plusieurs serveurs.
Questions fréquentes
Quelles garanties de cohérence offre Spanner ?
Spanner fournit une cohérence externe, qui est la propriété de cohérence la plus stricte pour les systèmes de traitement des transactions. Toutes les transactions dans Spanner respectent cette propriété de cohérence, pas seulement celles d'une partition. La cohérence externe indique que Spanner exécute les transactions d'une manière qu'il est impossible de distinguer par rapport à un système dans lequel les transactions sont exécutées en série, et que l'ordre en série est cohérent avec l'ordre dans lequel les transactions peuvent être observées pour le commit. Étant donné que les horodatages générés pour les transactions correspondent à un ordre sérialisé, si un client voit une transaction T2 commencer après la fin d'une autre transaction T1, le système attribue un horodatage à T2 ultérieur à celui de T1.
Spanner permet-il la linéarisation ?
Oui. En fait, Spanner fournit une cohérence externe, qui est une propriété plus forte que la linéarisation, car celle-ci ne dit rien sur le comportement des transactions. La linéarisation est une propriété des objets simultanés qui acceptent les opérations de lecture et d'écriture atomiques. Dans une base de données, un "objet" représenterait typiquement une ligne ou même une cellule unique. La cohérence externe est une propriété des systèmes de traitement des transactions, dans lesquels les clients synthétisent de manière dynamique des transactions contenant plusieurs opérations de lecture et d'écriture sur des objets arbitraires. La linéarisation peut être considérée comme un cas particulier de cohérence externe, dans lequel une transaction ne peut contenir qu'une seule opération de lecture ou d'écriture sur un seul objet.
Spanner offre-t-il une sérialisabilité ?
Oui. En fait, Spanner fournit une cohérence externe, qui est une propriété plus stricte que la sérialisabilité. Un système de traitement des transactions est sérialisable s’il exécute des transactions d'une manière qui ne peut pas être distinguée d'un système dans lequel les transactions sont exécutées en série. Spanner garantit également que l'ordre de la série est cohérent avec l'ordre dans lequel les transactions peuvent être validées.
Considérons à nouveau l'exemple bancaire utilisé précédemment. Dans un système offrant la sérialisabilité mais pas de cohérence externe, même si le client exécutait T1 puis T2 de manière séquentielle, le système serait autorisé à les réorganiser, ce qui pourrait entraîner une pénalité pour le débit en raison de fonds insuffisants.
Spanner offre-t-il une cohérence forte ?
Oui. En fait, Spanner fournit une cohérence externe, qui est une propriété plus forte qu'une cohérence forte. Le mode de lecture par défaut dans Spanner est "strong", ce qui garantit qu'elles observent les effets de toutes les transactions validées avant le début de l'opération, indépendamment de l'instance répliquée qui reçoit la lecture.
Quelle est la différence entre une consistance forte et une consistance externe ?
Un protocole de réplication présente une "cohérence forte" si les objets répliqués sont linéarisables. Comme la linéarisation, la "cohérence forte" est plus faible que la "cohérence externe", car elle ne donne aucune information sur le comportement des transactions.
Spanner fournit-il une cohérence à terme (ou différée) ?
Spanner fournit une cohérence externe, qui est une propriété beaucoup plus forte que la cohérence à terme. La cohérence à terme concède des garanties plus faibles au profit de performances plus élevées. La cohérence à terme est problématique car cela signifie que les lecteurs peuvent observer la base de données dans un état dans lequel elle n'a jamais été réellement (par exemple, une lecture peut montrer un état dans lequel la transaction B est validée mais la transaction A ne l'est pas, même si A a eu lieu avant B). Spanner fournit des lectures non actualisées qui offrent des avantages semblables à ceux d'une cohérence à terme, mais avec des garanties de cohérence beaucoup plus solides. Une lecture non actualisée renvoie les données d'un "ancien" horodatage, qui ne peut pas bloquer les écritures, car les versions précédentes des données sont immuables.