Cloud Spanner : TrueTime et cohérence externe

Avantages de TrueTime pour Cloud  Spanner

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.

Cloud Spanner utilise cette fonctionnalité pour attribuer des horodatages aux transactions. Plus précisément, chaque transaction se voit attribuer un horodatage qui reflète l'instant auquel Cloud Spanner considère qu'elle s'est produite. Étant donné que Cloud Spanner utilise un contrôle de simultanéité multiversion, cette garantie de classement des horodatages permet aux clients de Cloud 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

Cloud 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 Cloud 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, Cloud Spanner est sémantiquement impossible à distinguer d'une base de données utilisant une seule machine. Même s'il offre de solides garanties, Cloud Spanner permet aux applications de bénéficier de performances comparables à celles de bases de données proposant des garanties plus faibles (en contrepartie de performances supérieures). Par exemple, à l'instar des bases de données compatibles avec l'isolation d'instantané, Cloud Spanner permet de poursuivre les écritures sans être bloqué par des transactions en lecture seule, mais sans présenter les anomalies afférentes à 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 Cloud 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 soldes 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 un 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 pouvoir lire sans bloquer les écritures, Cloud Spanner et de nombreux autres systèmes de base de données conservent plusieurs versions de données immuables. Ce système est 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). Il est beaucoup plus difficile de le réaliser efficacement dans un système largement distribué tel que Cloud Spanner, dans lequel des serveurs du monde entier doivent attribuer des horodatages.

Cloud Spanner dépend de TrueTime pour générer des horodatages monotones croissants. Cloud 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.

FAQ

Quelles sont les garanties de cohérence fournies par Cloud Spanner ?

Cloud 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 Cloud Spanner satisfont à cette propriété de cohérence, pas seulement celles d'une partition. La cohérence externe établit que Cloud 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.

Cloud Spanner permet-il la linéarisation ?

Oui. Cloud Spanner fournit en fait 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.

Cloud Spanner permet-il la sérialisabilité ?

Oui. Cloud Spanner fournit en fait 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. Cloud 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.

Cloud Spanner offre-t-il une cohérence forte ?

Oui. Cloud Spanner fournit en fait 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 Cloud 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.

Cloud Spanner fournit-il une cohérence à terme (ou minimaliste) ?

Cloud 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). Cloud 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'un "ancien" horodatage, qui ne peut pas bloquer les écritures car les anciennes versions 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.