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.
Spanner utilise cette fonctionnalité pour attribuer des horodatages les transactions. Plus précisément, chaque transaction se voit attribuer un horodatage qui reflète l'instant auquel Spanner considère qu'elle s'est produite. Étant donné que Spanner utilise un contrôle de simultanéité multiversion, cette garantie de classement des horodatages permet aux clients de Spanner d'effectuer des lectures cohérentes sur l'ensemble de la base de données (même sur plusieurs régions du Cloud) sans bloquer les écritures.
Cohérence externe
Spanner fournit aux clients les garanties les plus strictes en matière de contrôle de simultanéité pour les transactions, appelée 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) à des fins de performances et de disponibilité accrues. 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 utilisant une seule machine. Même s'il offre des garanties si solides, Spanner permet aux applications d'atteindre de performances comparables à celles des bases de données qui offrent des garanties plus faibles (en retour pour de meilleures performances). Par exemple, les bases de données qui acceptent les instantanés l'isolation, Spanner autorise les écritures à s'exécuter sans être bloquée des transactions en lecture seule, sans pour autant présenter d'anomalies l'isolement le permet.
La cohérence externe simplifie grandement le développement d'applications. Par exemple : supposons que vous ayez créé une application bancaire sur Spanner et de vos clients commencent avec 50 USD sur leur compte courant et 50 USD sur leur 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 conserver plusieurs versions immuables des données (souvent appelée simultanéité multiversion de contrôle). 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 réaliser 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 codes temporels 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 de transactions. Toutes les transactions dans Spanner satisfont à cette propriété de cohérence, pas seulement celles d'une partition. La cohérence externe établit que Spanner exécute les transactions d'une manière qui ne peut être distinguée d'un système dans lequel les transactions sont exécutées en série, et que l'ordre de cette série est cohérent avec l'ordre dans lequel la validation des transactions se produit. É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 puissante que la linéarisation, car celle-ci ne donne aucune information 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 permet-il la 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 cette série est cohérent avec l'ordre dans lequel la validation des transactions se produit.
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 puissante qu'une cohérence forte. Le mode par défaut pour les lectures dans Spanner est "fort", ce qui garantit qu'elles observent les effets de toutes les transactions validées avant le début de l'opération, quel que soit l'instance dupliqué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 puissante qu'une 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 bien plus solides. Une lecture non actualisée renvoie les données d'une "ancienne" du code temporel, qui ne peut pas et de bloquer les écritures, car les versions précédentes des données sont immuables.