Arrêtez de tout synchroniser

• Graft est un moteur de stockage transactionnel open source qui cherche à combiner la simplicité de la réplication physique avec l’efficacité de la réplication logique, plutôt que d’envoyer l’intégralité du journal des changements à tous les clients
• Il traite un volume composé de pages de taille fixe au niveau des snapshots, et le serveur ne renvoie pas les données réelles, mais un graft, un bitmap compressé des index de pages modifiées
• Le client examine le graft et ne récupère que les pages nécessaires ; il peut choisir entre le préchargement basé sur Leap, le préchargement propre au domaine, ou une récupération proactive de l’ensemble des changements
• En s’appuyant sur le stockage objet et des serveurs edge, il vise la réplication partielle même dans des environnements contraints comme les navigateurs, les apps mobiles, les fonctions serverless ou les environnements embarqués
• Le modèle de cohérence est Serializable Snapshot Isolation ; les commits basés sur d’anciens snapshots sont rejetés, et le client les traite via reset/replay, merge ou fork de volume

---

Le problème de réplication que Graft veut résoudre

• La réplication partielle semble simple si l’on ne synchronise que les données nécessaires, mais en pratique chaque approche de réplication a un coût bien identifié
  • La réplication logique suit précisément tous les changements, mais rend la cohérence forte complexe
  • La réplication physique évite cette complexité, mais oblige à synchroniser aussi des changements qui seront jetés plus tard
• Graft est un moteur de stockage transactionnel open source conçu pour la synchronisation différée, la réplication partielle, la cohérence forte, le passage à l’échelle horizontal et la durabilité du stockage objet
• Son point de départ est l’expérience acquise avec SQLSync
  • SQLSync est une pile de base de données optimisée pour le frontend, construite au-dessus de SQLite, qui applique des idées issues de Git et des systèmes distribués à son moteur de synchronisation
  • SQLSync réplique l’intégralité du journal des changements vers tous les clients ; cela convient côté serveur, mais pas aux environnements edge et navigateur
• L’objectif de Graft est de permettre aux clients de se synchroniser à leur propre rythme, de ne récupérer que ce dont ils ont besoin, et de répliquer des données arbitraires avec une cohérence forte, y compris sur l’edge et sur des appareils hors ligne

Une conception entre réplication complète et diff conscient du schéma

• Les solutions existantes se répartissent globalement en deux catégories
  • Réplication complète : tout le jeu de données est synchronisé vers chaque client, ce qui n’est pas pratique dans des environnements contraints comme les fonctions serverless ou les webapps
  • Diff conscient du schéma : comme CDC ou les CRDT, suit les changements logiques au niveau des lignes ou des champs, mais nécessite une intégration profonde avec l’application et se généralise difficilement à des données arbitraires
• Comme la réplication complète, Graft est indépendant du schéma
  • Il ne connaît pas et ne se soucie pas du type de données stockées ; il réplique des pages contenant des octets
• En même temps, comme la réplication logique, il transmet au client une description compressée de ce qui a changé depuis la dernière synchronisation
• L’abstraction centrale est le volume
  • Un volume est une collection clairsemée et triée de pages de taille fixe
  • Les clients lisent et écrivent un volume via une API transactionnelle à partir d’un snapshot donné
  • En interne, Graft ne stocke et ne réplique que le nécessaire, et utilise le stockage objet comme backend durable et scalable

Synchronisation différée : laisser le client rattraper son retard quand il le souhaite

• Graft est conçu pour des clients edge qui se réveillent de temps en temps, avec un réseau instable et des temps d’exécution courts
• Il ne dépend pas d’une réplication continue : le client choisit lui-même quand se synchroniser
• La synchronisation commence par la question : « qu’est-ce qui a changé depuis le dernier snapshot ? »
• Le serveur ne renvoie pas les données réelles, mais un graft, un bitmap compressé des index de pages modifiées
  • Le graft sert de guide pour ajouter les nouveaux changements au snapshot existant
  • Le client peut savoir quelles pages il peut réutiliser et quelles pages il devra récupérer à la demande
• Comme le graft est une métadonnée de changement et non une donnée, le client garde le contrôle sur ce qu’il récupère et à quel moment

Réplication partielle et préchargement

• Dans un onglet de navigateur, une app mobile ou une fonction serverless, il est difficile de télécharger tout le jeu de données pour traiter quelques requêtes
• Après avoir reçu le graft, le client détermine quelles pages restent valides et quelles pages doivent être récupérées
• Comme seules les pages nécessaires sont récupérées de manière sélective, seules les données réellement utilisées peuvent être répliquées
• Graft prend en charge plusieurs méthodes de préchargement pour réduire la latence d’accès aux pages
  • Préchargement généraliste : le préchargeur intégré basé sur l’algorithme Leap identifie les schémas d’accès et prédit les futurs accès aux pages
  • Préchargement propre au domaine : l’application peut exploiter sa connaissance de données fréquemment consultées, comme les profils utilisateur, pour récupérer à l’avance les pages associées
  • Récupération proactive : si nécessaire, elle peut récupérer tous les changements et revenir de fait à une réplication complète, ce qui est particulièrement utile pour les charges de travail Graft côté serveur
• Les pages étant hébergées directement dans le stockage objet, celui-ci sert de base de réplication durable et scalable

Déploiement edge et clients embarqués

• La réplication edge de Graft vise non seulement à déterminer quelles données synchroniser, mais aussi à placer les données là où elles sont nécessaires
• Les pages sont servies depuis le stockage objet via une flotte mondiale de serveurs edge
  • Les pages chaudes fréquemment consultées peuvent être mises en cache près des clients
  • L’objectif est une faible latence et une forte réactivité, quelle que soit la localisation des utilisateurs dans le monde
• Le client Graft est conçu pour être léger et embarquable
  • Peu de dépendances et un runtime réduit
  • Il peut être intégré à des environnements comme les navigateurs, les appareils, les apps mobiles ou les fonctions serverless
• Comme le cache edge crée des problèmes de cohérence et de gestion des conflits, Graft fournit aussi un modèle de cohérence forte

Modèle de cohérence et gestion des conflits

• Graft utilise Serializable Snapshot Isolation comme modèle de cohérence
• Les clients obtiennent une vue isolée et cohérente des données à partir d’un snapshot donné, et les lectures peuvent s’exécuter simultanément sans se gêner
• Les écritures sont strictement sérialisées, ce qui donne à toutes les transactions un ordre globalement cohérent
• En raison de l’approche offline-first et de la réplication différée, un client peut tenter de committer à partir d’un ancien snapshot
  • Accepter systématiquement de tels commits casserait la strict serializability
  • Graft rejette ces commits de façon sûre et laisse le client choisir comment les traiter
• Les options courantes côté client sont au nombre de trois
  • Reset and replay : récupérer le dernier snapshot, réappliquer les transactions locales, puis réessayer
    • Les données globales restent strict serializable
    • Localement, le client observe une Optimistic Snapshot Isolation : les lectures voient un snapshot cohérent en interne, mais ce snapshot peut être abandonné si le commit est rejeté
  • Merge : fusionner l’état local avec le dernier snapshot du serveur
    • Dans ce cas, le modèle de cohérence global peut être abaissé à snapshot isolation
  • Volume fork : créer définitivement un nouveau volume séparé
    • La serializability globale est préservée

Applications possibles

• Applications offline-first : dans des apps qui fonctionnent partiellement hors ligne, comme les notes, la gestion de tâches ou les apps CRUD, Graft peut prendre en charge la synchronisation
  • Associé à des gestionnaires de conflits, il peut aussi permettre des fonctionnalités multijoueurs sur des données arbitraires
• Données multiplateformes : partager des données entre plateformes mobiles, appareils et web, tout en réduisant la dépendance à un fournisseur
• Réplicas de lecture sans état : lancer un réplica de base de données sans état local, récupérer les métadonnées du dernier snapshot, puis exécuter immédiatement des requêtes
  • Pas besoin de télécharger toutes les données ni de rejouer un journal
• Réplication de données arbitraires : Graft se concentre sur la réplication de pages et ne s’occupe pas du format des données à l’intérieur des pages
  • Il peut cibler des données comme des bases SQLite, des modèles d’IA, des fichiers Parquet, Lance ou des tilesets géospatiaux

L’extension SQLite libgraft

• Aujourd’hui, le moyen le plus simple d’utiliser Graft est libgraft, une extension SQLite native
• libgraft fonctionne partout où SQLite fonctionne et ne réplique que la partie de la base de données réellement utilisée par le client
• Il implémente le VFS de SQLite pour intercepter les lectures et écritures de la base de données
• Il fournit une sémantique de transaction et de concurrence semblable à celle offerte par SQLite en mode WAL
• Les fonctionnalités proposées sont les suivantes
  • Réplication asynchrone avec le stockage objet
  • Réplication partielle différée sur l’edge et les appareils
  • Serializable Snapshot Isolation
  • Restauration à un instant donné
• La documentation est disponible dans la documentation SQLite sur GitHub

Participation et projet de service managé

• Graft est développé publiquement sur GitHub
• Les issues, discussions et Pull Requests sont bienvenues, et un guide de contribution est fourni
• Discord et l’e-mail sont proposés comme canaux de discussion
• Le lancement de Graft Managed Service est également prévu, avec un lien d’inscription à la liste d’attente

Feuille de route

• Graft a déjà connu un an de recherche, plusieurs itérations et un important changement de direction, mais il reste encore beaucoup à faire
• Les éléments prévus sont les suivants
  • Support WebAssembly : rendre Graft utilisable dans le navigateur, avec pour objectif la prise en charge du build Wasm officiel de SQLite, de wa-sqlite et de sql.js
  • Intégration de Graft et SQLSync : après le support Wasm, le plan consiste à séparer les couches de mutation, rebase et query subscription de SQLSync pour les placer au-dessus d’une base de données répliquée par Graft
  • Élargissement des bibliothèques clientes : des wrappers clients Graft natifs sont souhaités pour Python, JavaScript, Go et Java
  • Écritures à faible latence : actuellement, les opérations push restent bloquées jusqu’à ce qu’elles soient entièrement committées dans le stockage objet
    • Expérimentation avec S3 Express One Zone
    • Placement d’un groupe de consensus durable à faible latence devant le stockage objet
  • Garbage collection, checkpointing et compaction : nécessaires pour maximiser les performances des requêtes, minimiser l’espace gaspillé et permettre la suppression définitive
  • Authentification et autorisation : un chantier large, allant des comptes du service managé aux permissions fines de lecture/écriture sur les volumes
  • Fork de volume : le service peut effectuer un fork zero-copy en copiant des références de segments vers un nouveau volume, mais un fork local doit actuellement copier toutes les pages
  • Gestion des conflits : des stratégies intégrées de résolution de conflits et des points d’extension sont prévus ; la stratégie initiale consistera à fusionner automatiquement les transactions qui ne se chevauchent pas

Comparaison avec les solutions de réplication SQLite

• Les informations de comparaison proviennent de la documentation et de billets de blog, avec la réserve qu’elles peuvent ne pas être parfaitement exactes

• mvSQLite

  • mvSQLite implémente une couche VFS personnalisée qui stocke directement les pages SQLite dans FoundationDB
  • Graft et mvSQLite se ressemblent par leur versionnement au niveau des pages, qui permet le fetch différé et des vues partielles de la base de données
  • La différence tient à l’emplacement du stockage et à la façon de suivre les changements de pages
    • mvSQLite dépend de FoundationDB et tous les nœuds doivent accéder directement au cluster
    • Les changesets de Graft, basés sur Splinter, sont autonomes, donc plus faciles à distribuer, et il n’est pas nécessaire d’interroger directement FoundationDB pour connaître les versions des pages modifiées

• Litestream

  • Litestream est une solution de sauvegarde en streaming qui réplique en continu les frames WAL de SQLite vers le stockage objet
  • Graft s’intègre directement au processus de commit de SQLite via un VFS personnalisé, ce qui permet la réplication partielle différée et les écritures distribuées
  • Les deux répliquent les pages vers le stockage objet et prennent en charge la restauration à un instant donné

• cr-sqlite

  • cr-sqlite est une extension SQLite qui transforme les tables en CRDT pour permettre une réplication logique au niveau des lignes
  • Il fournit une résolution automatique des conflits, mais nécessite une connaissance du schéma et une intégration au niveau applicatif
  • Graft est indépendant du schéma et compatible avec des extensions SQLite arbitraires ainsi que des structures de données personnalisées, mais pour préserver la serializability globale, l’application doit gérer explicitement la résolution des conflits

• Cloudflare Durable Objects with SQLite Storage

  • Associer Durable Objects et SQLite permet de placer une base de données à forte cohérence et haute durabilité, encapsulée par la logique métier, sur le réseau edge de Cloudflare
  • En interne, cela ressemble à Litestream dans la mesure où le WAL SQLite est répliqué vers le stockage objet et checkpointé périodiquement
  • Graft expose la réplication comme une fonctionnalité de premier ordre et vise une réplication efficace avec l’edge

• Cloudflare D1

  • Cloudflare D1 est une base de données SQLite managée accessible via une API HTTP
  • Graft adopte un modèle distribué où les données sont embarquées dans l’application cliente et répliquées directement vers l’edge

• Turso & libSQL

  • Turso fournit, via libSQL, des bases de données SQLite managées et des réplicas embarqués
  • Graft se distingue par la réplication partielle et la prise en charge de structures de données arbitraires indépendantes du schéma
  • Le service backend de Graft fonctionne au niveau des pages et laisse au client l’ensemble du cycle de vie transactionnel

• rqlite & dqlite

  • rqlite et dqlite distribuent SQLite sur plusieurs serveurs au moyen d’un consensus basé sur Raft et d’un protocole réseau
  • Ils se concentrent sur la synchronisation d’un ensemble de nœuds avec état qui restent connectés entre eux
  • Graft est un système sans état construit sur le stockage objet, conçu pour échanger des données avec l’edge

• Verneuil

  • Verneuil réplique de façon asynchrone des snapshots SQLite vers des réplicas de lecture via le stockage objet, avec la fiabilité comme priorité
  • Il évite explicitement les mécanismes visant à minimiser le délai de réplication ou à maximiser la fraîcheur
  • Graft se comporte davantage comme une base de données distribuée multi-auteurs et met l’accent sur la réplication partielle sélective en temps réel