Shirakami: A Hybrid Concurrency Control Protocol for Tsurugi Relational Database System

Ce papier présente Shirakami, un nouveau protocole de contrôle de concurrence hybride intégré au système de base de données Tsurugi, conçu pour gérer simultanément des transactions courtes et longues avec des performances nettement supérieures à PostgreSQL.

L'essentiel

🌊 Le Problème : La Tempête dans le Port

Imaginez une base de données comme un port très fréquenté.

• Les petits bateaux (Transactions courtes) : Ce sont des clients qui veulent acheter un café, vérifier un solde ou mettre à jour un prix. Ils arrivent, font leur petite opération en une seconde et repartent. Ils sont rapides et nombreux.
• Les gros cargos (Transactions longues) : Ce sont des navires de marchandises qui doivent charger des milliers de conteneurs, faire des calculs complexes sur tout le chargement et réorganiser tout le quai. Cela prend des heures.

Le problème actuel :
Dans les systèmes de base de données classiques (comme PostgreSQL), si un gros cargo essaie de s'approcher du quai pendant que des centaines de petits bateaux font des allers-retours, il y a un embouteillage monstre.

• Soit le gros cargo est bloqué par les petits bateaux et ne peut jamais finir son travail (il doit recommencer tout le chargement).
• Soit le gros cargo bloque tout le port, et les petits bateaux attendent des heures pour un simple café.

C'est exactement ce qui arrive dans des secteurs comme la facturation téléphonique (calculer les factures de millions d'utilisateurs en temps réel) ou la gestion des stocks (recalculer le coût de millions de produits). Les systèmes actuels ne savent pas bien gérer ces deux mondes en même temps.

---

🏔️ La Solution : Le Protocole Shirakami

Les auteurs ont créé un nouveau système appelé Shirakami (nommé d'après une chaîne de montagnes au Japon, symbolisant la stabilité). C'est un système "hybride" qui utilise deux stratégies différentes selon la taille du bateau, mais qui les fait travailler ensemble sans se gêner.

Imaginez que Shirakami est un chef de port ultra-intelligent qui a deux règles d'or :

1. Le Protocole "OCC" (Pour les petits bateaux rapides)

C'est comme une file d'attente rapide pour les clients pressés.

• Comment ça marche ? Les petits bateaux naviguent sans demander la permission à tout le monde. Ils font leur travail, et au moment de partir, le chef vérifie : "Personne n'a bougé votre conteneur pendant que vous étiez là ?"
• Si tout est calme, ils partent. S'il y a eu un conflit, ils repartent immédiatement refaire leur tour. C'est très rapide pour les petites tâches.

2. Le Protocule "LTX" (Pour les gros cargos lents)

C'est la zone spéciale pour les gros navires.

• Le secret : La "Préservation d'Écriture" (Write Preservation). Avant même que le gros cargo ne commence à charger, il annonce : "Je vais manipuler les zones A, B et C du quai."
• Le chef de port affiche cette annonce sur un panneau géant.
• L'astuce géniale : Les petits bateaux voient l'annonce. Au lieu d'entrer en collision avec le cargo, ils voient le panneau, disent "Ah, cette zone est occupée plus tard !" et s'abstiennent d'y aller ou attendent patiemment.
• Cela évite que le gros cargo ne soit bloqué par des milliers de petits bateaux qui essaient de passer au mauvais endroit.

3. La Magie : "L'Avancement de l'Ordre" (Order Forwarding)

C'est l'ingrédient secret qui rend Shirakami unique.
Parfois, un gros cargo commence à charger une zone, mais un autre cargo (un peu moins prioritaire) a déjà commencé à lire cette zone. Dans les systèmes classiques, le premier cargo serait bloqué ou annulé.
Avec Shirakami, le chef de port dit : "Attends, on va inverser les rôles !" Il permet au petit cargo de finir son travail avant que le gros cargo ne l'écrase, en ajustant l'ordre des événements dans le temps. C'est comme si le chef de port pouvait faire un petit "saut dans le temps" pour que tout le monde puisse passer sans collision.

---

🚀 Les Résultats : Pourquoi c'est impressionnant ?

Les chercheurs ont testé ce système sur une base de données réelle appelée Tsurugi. Voici ce qu'ils ont découvert :

1. Vitesse des petits bateaux : Tsurugi est 19,7 fois plus rapide que PostgreSQL pour les tâches de facturation téléphonique. Les petits bateaux ne sont plus bloqués par les gros.
2. Efficacité des gros cargos : Le protocole spécial pour les longs calculs (Shirakami-LTX) est 680 fois plus efficace que le protocole classique quand il s'agit de traiter de gros volumes de données.
3. Pas de compromis : Le système n'a pas besoin de changer de mode (comme passer d'un système de jour à un système de nuit). Il gère tout en même temps, 24h/24.

🎯 En Résumé

Imaginez un restaurant où vous pouvez commander un café (transaction courte) et en même temps, un chef prépare un banquet pour 1000 personnes (transaction longue).

• Les anciens systèmes : Le chef bloque la cuisine, personne ne peut commander de café. Ou alors, les clients commandent trop de café, et le chef doit tout recommencer.
• Le système Shirakami : Le chef met un panneau "Zone de travail en cours" sur les tables qu'il utilise. Les clients voient le panneau, évitent ces tables, et peuvent commander leur café sur les autres tables. Le chef travaille tranquillement sur son banquet. Tout le monde est content, tout est rapide, et rien n'est gaspillé.

C'est une révolution pour les entreprises qui doivent faire des calculs massifs en temps réel sans ralentir leurs services quotidiens.

Résumé technique

1. Problématique

Les applications modernes, telles que la gestion de nomenclatures (Bill of Materials - BoM) dans l'industrie manufacturière ou la facturation dans les télécommunications, nécessitent de traiter simultanément deux types de charges de travail contradictoires :

• Transactions courtes (Short Transactions) : Des opérations rapides et fréquentes (ex: mises à jour de coûts de matières premières, enregistrement d'appels en temps réel).
• Transactions longues (Long Read-Write Transactions) : Des opérations analytiques ou de batch qui scannent de vastes ensembles de données, effectuent des calculs complexes et écrivent les résultats (ex: calcul de coûts de production, facturation mensuelle).

Le défi : Les protocoles de contrôle de concurrence (CC) conventionnels échouent à gérer efficacement cette coexistence.

• Les protocoles basés sur l'OCC (Optimistic Concurrency Control) modernes (comme Silo) sont excellents pour les transactions courtes mais provoquent un taux d'annulation (abort) massif des transactions longues en raison de conflits fréquents.
• Les protocoles pour transactions longues (comme Oze ou les approches déterministes) sont souvent inefficaces pour les transactions courtes ou ne supportent pas les sous-requêtes SQL dynamiques.
• Les bases de données cloud natives actuelles (comme RedShift ou HiEngine) sont souvent incapables de gérer les transactions de batch longues sans les exécuter séparément la nuit, ce qui nuit à la réactivité des systèmes.

L'objectif est de concevoir un protocole capable de maintenir la cohérence (sérilabilité) tout en permettant l'exécution concurrente de ces deux types de charges sans dégradation de performance.

2. Méthodologie : Le Protocole Shirakami

Les auteurs proposent Shirakami, un protocole de contrôle de concurrence hybride intégré au système de base de données relationnelle Tsurugi. Shirakami combine deux sous-protocoles distincts mais interconnectés :

A. Les Deux Sous-Protocoles

1. Shirakami-OCC (S-OCC) : Basé sur le protocole Silo, optimisé pour les transactions courtes. Il utilise une lecture invisible et une validation optimiste.
2. Shirakami-LTX (S-LTX) : Un nouveau protocole conçu spécifiquement pour les transactions longues, basé sur la sérilabilité de vue multiversion (MVSR) plutôt que sur la simple sérilabilité par conflit (CSR). Cela offre un espace de planification (scheduling space) beaucoup plus large, réduisant les faux positifs d'annulation.

B. Mécanismes Clés d'Intégration

Pour faire coexister ces deux mondes sans basculement dynamique de protocole, Shirakami utilise trois mécanismes fondamentaux :

1. Préservation d'Écriture (Write Preservation - WP) :

   • Avant de commencer, une transaction longue (S-LTX) déclare l'ensemble des tables ou zones qu'elle va écrire.
   • Les transactions courtes (S-OCC) lisent ces métadonnées. Si une transaction courte détecte un conflit potentiel avec une écriture future d'une transaction longue, elle peut s'annuler immédiatement (ou attendre) plutôt que de procéder à une lecture qui serait invalide. Cela évite les conflits de lecture-écriture coûteux.

2. Avancement d'Ordre (Order Forwarding) :

   • C'est le cœur de la flexibilité de S-LTX. Si une transaction de haute priorité (débutée plus tôt) écrit une donnée lue par une transaction de basse priorité (débutée plus tard), la transaction de basse priorité peut changer dynamiquement son ordre de sérialisation pour se placer avant la transaction de haute priorité.
   • Cela permet de maintenir la cohérence sans annuler la transaction de basse priorité, élargissant ainsi l'espace de planification au-delà des limites du CSR.

3. Synchronisation par Époques (Epoch-based Synchronization) :

   • Le système gère des époques fixes. Les transactions S-LTX sont assignées à une époque de début spécifique (pour garantir qu'elles lisent un état cohérent), tandis que les S-OCC utilisent l'époque de clôture.
   • Les transactions S-LTX ont une priorité de commit supérieure aux S-OCC. Si un conflit survient, la transaction longue est préservée.

C. Architecture Tsurugi

Shirakami est le moteur de transaction de Tsurugi, une base de données relationnelle en mémoire (in-memory) conçue pour les architectures multi-cœurs. Tsurugi intègre également :

• Yakushima : Un index parallèle basé sur Masstree pour des performances élevées en lecture/écriture.
• Jogasaki : Un moteur SQL exécutant des flux de données (DAG) de manière asynchrone.
• Limestone : Un système de stockage de logs et de snapshots pour la persistance et la tolérance aux pannes.

3. Contributions Clés

• Première implémentation de production d'un espace MVSR large : Contrairement aux travaux théoriques ou aux systèmes graphiques (Tuskflow), Shirakami implémente la sérilabilité de vue multiversion (MVSR) dans un système relationnel généraliste capable de gérer des sous-requêtes SQL dynamiques.
• Coexistence sans basculement : Le système ne nécessite pas de changer de protocole en fonction du type de transaction ; les deux protocoles fonctionnent simultanément et de manière transparente.
• Support des sous-requêtes : Contrairement aux approches déterministes pures qui échouent souvent avec des requêtes SQL complexes dont l'ensemble de données n'est connu qu'à l'exécution, Shirakami gère nativement les sous-requêtes grâce à son approche hybride.
• Optimisation de la Préservation d'Écriture : Utilisation de verrous optimistes au niveau de la table (et non de l'enregistrement) pour minimiser les défauts de cache et les blocages, tout en permettant aux transactions courtes de détecter les conflits potentiels tôt.

4. Résultats Expérimentaux

Les auteurs ont évalué Tsurugi et Shirakami sur plusieurs benchmarks comparés à PostgreSQL et à des implémentations pures de S-OCC.

• Benchmark de Facturation Télécom (Phone Billing) :

  • Dans un scénario de mélange de transactions courtes et longues, Tsurugi a été 19,7 fois plus rapide (latence réduite) que PostgreSQL.
  • PostgreSQL n'a pas pu terminer le benchmark dans le délai imparti (1800s) avec 64 threads concurrents, tandis que Tsurugi l'a complété.

• Benchmark de Nomenclature (Bill of Materials - BoM) :

  • Tsurugi a été 5,6 fois plus rapide que PostgreSQL.
  • Lorsque PostgreSQL a été configuré en mode READ COMMITTED pour être plus rapide, il a généré des anomalies de cohérence inacceptables pour ce type de charge.

• Comparaison S-LTX vs S-OCC (YCSB-E avec transactions longues) :

  • L'expérience a montré que S-LTX offre un débit 680 fois supérieur à S-OCC pour les transactions longues dans un environnement mixte.
  • S-OCC voit son débit de transactions longues chuter à zéro dès que la longueur de la transaction dépasse un certain seuil (à cause des annulations), tandis que S-LTX maintient un débit stable même pour des transactions très longues (jusqu'à 8000 opérations).

• TPC-C :

  • Tsurugi montre une scalabilité linéaire jusqu'à 128 threads, alors que PostgreSQL sature autour de 16 threads (sous le mode SERIALIZABLE).

5. Signification et Impact

Ce travail est significatif car il résout un problème fondamental de l'industrie des bases de données : la séparation traditionnelle entre le traitement transactionnel (OLTP) et le traitement analytique (OLAP).

• Unification des charges de travail : Shirakami permet d'exécuter des analyses en temps réel (batch) et des transactions opérationnelles sur la même base de données sans sacrifier la cohérence ni la performance.
• Viabilité industrielle : Contrairement à des solutions antérieures (comme Oze) qui restaient théoriques ou limitées aux graphes, Shirakami est intégré dans un système de production (Tsurugi) prêt à l'emploi.
• Évolutivité : La capacité à gérer des milliers de transactions courtes tout en laissant passer des transactions longues lourdes sans les annuler ouvre la voie à de nouvelles architectures de bases de données pour les systèmes critiques (télécoms, finance, logistique) où la latence et la disponibilité sont critiques.

En conclusion, Shirakami démontre qu'il est possible de concevoir un protocole de contrôle de concurrence hybride qui surpasse les solutions monolithiques traditionnelles dans des environnements de travail réels et complexes.