Spanner: TrueTime et cohérence externe

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é de TrueTime pour attribuer des horodatages aux 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, 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 sur plusieurs régions 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, ce que l'on appelle la cohérence externe2. Avec 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 des performances et une disponibilité plus élevées. 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. Bien qu'il offre des garanties aussi fortes, Spanner permet aux applications d'atteindre des performances comparables à celles des bases de données qui offrent des garanties plus faibles (en échange de performances supérieures). Par exemple, à l'instar des bases de données compatibles avec l'isolation d'instantanés, Spanner autorise le traitement des écritures sans être bloqués par des transactions en lecture seule, mais sans présenter les anomalies que permet 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é 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). Le réaliser dans un système largement distribué tel que Spanner, dans lequel des serveurs du monde entier doivent attribuer des horodatages, est beaucoup plus difficile à réaliser efficacement.

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 sont les garanties de cohérence fournies par 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 répondent à 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 qui ne peut pas être distinguée d'un système dans lequel les transactions sont exécutées en série. De plus, l'ordre en série est cohérent avec l'ordre dans lequel les transactions peuvent être validées. É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 offre-t-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 la linéarisation 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 offre-t-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 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 fournit-il une cohérence forte ?

Oui. En fait, Spanner fournit une cohérence externe, qui est une propriété plus solide 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, 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 puissante 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 en termes de performances 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.

Documentation complémentaire

Notes

  • 1J. C. Corbett, J. Dean, M. Epstein, A. Fikes, C. Frost, J. Furman, S. Ghemawat, A. Gubarev, C. Heiser, P. Hochschild, W. Hsieh, S. Kanthak, E. Kogan, H. Li, A. Lloyd, S. Melnik, D. Mwaura, D. Nagle, S. Quinlan, R. Rao, L. Rolig, Y. Saito, M. Szymaniak, C. Taylor, R. Wang, and D. Woodford. Spanner : la base de données de Google distribuée dans le monde entier. Dans le dixième symposium USENIX sur la conception et la mise en œuvre de systèmes d'exploitation (OSDI 12), p. 261 à 264, Hollywood, Californie, octobre 2012.
  • 2Gifford, D. K. Stockage d'informations dans un système informatique décentralisé. Thèse de doctorat, Université Stanford, 1981.