Aufhören, alles zu synchronisieren

• Graft ist eine Open-Source-Transactional-Storage-Engine, die die Einfachheit physischer Replikation mit der Effizienz logischer Replikation verbinden will, statt den vollständigen Änderungslog an alle Clients zu senden
• Es behandelt Volumes, die aus Pages fester Größe bestehen, auf Snapshot-Basis; der Server liefert nicht die eigentlichen Daten aus, sondern einen komprimierten Bitset geänderter Seitenindizes namens graft
• Der Client wertet graft aus und lädt nur die benötigten Pages; dabei kann er zwischen Leap-basiertem Prefetching, domänenspezifischem Prefetching und proaktivem Abruf aller Änderungen wählen
• Durch die Nutzung von Object Storage und Edge-Servern zielt es auf partielle Replikation auch in ressourcenbeschränkten Umgebungen wie Browsern, mobilen Apps, serverlosen Funktionen und Embedded-Systemen
• Das Konsistenzmodell ist Serializable Snapshot Isolation; Commits auf Basis veralteter Snapshots werden abgelehnt, und der Client verarbeitet das per Reset/Replay, Merge oder Volume-Fork

---

Das Replikationsproblem, das Graft lösen will

• Partielle Replikation wirkt einfach, wenn man nur die benötigten Daten synchronisieren muss, aber im tatsächlichen Design hat jede Replikationsmethode klare Kosten
  • Logische Replikation verfolgt alle Änderungen präzise, macht starke Konsistenz aber komplex
  • Physische Replikation vermeidet diese Komplexität, muss dafür aber auch Änderungen synchronisieren, die später verworfen werden
• Graft ist eine Open-Source-Transactional-Storage-Engine mit den Zielen verzögerte Synchronisierung, partielle Replikation, starke Konsistenz, horizontale Skalierung und die Dauerhaftigkeit von Object Storage
• Ausgangspunkt waren Erfahrungen mit SQLSync
  • SQLSync ist ein frontend-optimierter Datenbank-Stack auf Basis von SQLite und nutzt Ideen aus Git und verteilten Systemen für seine Synchronisierungs-Engine
  • SQLSync repliziert den vollständigen Änderungslog an alle Clients; das funktioniert auf Servern, passt aber nicht gut zu Edge- und Browser-Umgebungen
• Graft soll es Clients ermöglichen, in ihrem eigenen Tempo zu synchronisieren, nur das Benötigte zu laden und beliebige Daten auch auf Edge- und Offline-Geräten mit starker Konsistenz zu replizieren

Das Design zwischen vollständiger Replikation und schemabewussten Diffs

• Bestehende Lösungen teilen sich grob in zwei Richtungen
  • Vollständige Replikation: Der gesamte Datensatz wird auf jeden Client synchronisiert und ist daher in eingeschränkten Umgebungen wie serverlosen Funktionen oder Web-Apps nicht praktikabel
  • Schemabewusste Diffs: Verfolgen logische Änderungen auf Zeilen- oder Feldebene wie CDC oder CRDTs, erfordern aber eine tiefe Integration in die Anwendung und lassen sich schwer auf beliebige Daten verallgemeinern
• Graft ist wie vollständige Replikation schemaunabhängig
  • Es muss weder wissen noch berücksichtigen, welche Art von Daten gespeichert wird, sondern repliziert Pages mit Bytes
• Gleichzeitig liefert es dem Client wie bei logischer Replikation eine komprimierte Beschreibung dessen, was sich seit der letzten Synchronisierung geändert hat
• Die zentrale Abstraktion ist das Volume
  • Ein Volume ist eine spärliche, geordnete Sammlung von Pages fester Größe
  • Clients lesen und schreiben ein Volume an einem bestimmten Snapshot über eine transaktionale API
  • Intern speichert und repliziert Graft nur das Nötige und nutzt Object Storage als langlebiges und skalierbares Backend

Verzögerte Synchronisierung: Clients holen auf, wenn sie es wollen

• Graft ist für Edge-Clients entworfen, die nur gelegentlich aufwachen, instabile Netzwerke haben und in Umgebungen mit kurzer Laufzeit laufen
• Statt auf kontinuierliche Replikation zu setzen, entscheidet der Client selbst, wann synchronisiert wird
• Die Synchronisierung beginnt mit der Frage: „Was hat sich seit dem letzten Snapshot geändert?“
• Der Server sendet keine eigentlichen Daten, sondern graft, einen komprimierten Bitset geänderter Seitenindizes
  • graft dient als Anleitung, um neue Änderungen an einen bestehenden Snapshot anzuhängen
  • Der Client erkennt, welche Pages weiterverwendet werden können und welche bei Bedarf nachgeladen werden müssen
• Da graft keine Daten, sondern Änderungsmetadaten enthält, bleibt die Kontrolle darüber, was wann geladen wird, beim Client

Partielle Replikation und Prefetching

• In Browser-Tabs, mobilen Apps oder serverlosen Funktionen ist es schwer, den gesamten Datensatz herunterzuladen, nur um einige Abfragen zu bearbeiten
• Nach Erhalt von graft bestimmt der Client, welche Pages noch gültig sind und welche geholt werden müssen
• Da nur benötigte Pages selektiv geladen werden, können tatsächlich nur die Daten repliziert werden, die später verwendet werden
• Graft unterstützt mehrere Prefetching-Methoden, um die Latenz beim Seitenzugriff zu verringern
  • Allzweck-Prefetching: Ein eingebauter Prefetcher auf Basis des Leap-Algorithmus erkennt Zugriffsmuster und sagt künftige Seitenzugriffe voraus
  • Domänenspezifisches Prefetching: Die Anwendung kann Wissen über häufig abgefragte Daten wie Benutzerprofile nutzen, um relevante Pages vorab zu laden
  • Proaktiver Abruf: Falls nötig, lassen sich alle Änderungen laden, was faktisch zu vollständiger Replikation zurückführt und besonders für serverseitige Graft-Workloads nützlich ist
• Die Pages werden direkt im Object Storage gehostet und dienen so als replikationsbasierte Grundlage mit Dauerhaftigkeit und Skalierbarkeit

Edge-Bereitstellung und Embedded-Clients

• Grafts Edge-Replikation zielt nicht nur darauf, welche Daten synchronisiert werden, sondern auch darauf, die Daten dorthin zu bringen, wo sie benötigt werden
• Pages werden aus dem Object Storage über eine globale Flotte von Edge-Servern ausgeliefert
  • Häufig genutzte hot pages können in Client-Nähe gecacht werden
  • Ziel sind geringe Latenz und hohe Reaktionsfähigkeit unabhängig vom Standort der Nutzer weltweit
• Der Graft-Client ist leichtgewichtig und für Embedding ausgelegt
  • Wenige Abhängigkeiten und kleine Runtime
  • Integration in Browser, Geräte, mobile Apps und serverlose Funktionen möglich
• Weil Edge-Caching Fragen zu Konsistenz und Konfliktbehandlung aufwirft, liefert Graft dazu auch ein starkes Konsistenzmodell

Konsistenzmodell und Konfliktbehandlung

• Graft verwendet Serializable Snapshot Isolation als Konsistenzmodell
• Clients erhalten an einem bestimmten Snapshot eine isolierte und konsistente Sicht auf die Daten; Lesevorgänge können parallel ablaufen, ohne sich gegenseitig zu stören
• Schreibvorgänge werden strikt serialisiert, sodass für alle Transaktionen eine global konsistente Reihenfolge entsteht
• Wegen des Offline-first- und verzögerten Replikationsmodells können Clients versuchen, auf Basis eines veralteten Snapshots zu committen
  • Würde man solche Commits immer akzeptieren, würde strict serializability verletzt
  • Graft lehnt solche Commits sicher ab und lässt den Client die Behandlungsstrategie wählen
• Typischerweise hat der Client drei Optionen
  • Reset and replay: Den neuesten Snapshot laden, lokale Transaktionen erneut anwenden und dann erneut versuchen
    • Die globalen Daten bleiben strict serializable
    • Lokal erlebt man Optimistic Snapshot Isolation; Lesevorgänge sehen intern einen konsistenten Snapshot, der bei Commit-Ablehnung aber verworfen werden kann
  • Merge: Den lokalen Zustand mit dem neuesten Snapshot des Servers zusammenführen
    • Dabei kann das globale Konsistenzmodell auf snapshot isolation abgesenkt werden
  • Volume fork: Dauerhaft ein neues Volume erstellen und abspalten
    • Die globale Serialisierbarkeit bleibt erhalten

Mögliche Anwendungen

• Offline-first-Apps: In Apps wie Notizen, Aufgabenverwaltung oder CRUD-Anwendungen, die teilweise offline laufen, kann Graft die Synchronisierung übernehmen
  • In Kombination mit Konflikt-Handlern sind auch Multiplayer-Funktionen auf beliebigen Daten möglich
• Plattformübergreifende Daten: Daten lassen sich zwischen mobilen Plattformen, Geräten und dem Web teilen und die Abhängigkeit von einzelnen Anbietern verringern
• Zustandslose Lesereplikate: Ein Datenbankreplikat kann ohne lokalen Zustand gestartet werden, sofort die neuesten Snapshot-Metadaten laden und direkt Abfragen ausführen
  • Weder der komplette Datensatz noch ein Log-Replay ist nötig
• Replikation beliebiger Daten: Graft konzentriert sich auf Seitenreplikation und kümmert sich nicht um das Datenformat innerhalb der Pages
  • Ziele können SQLite-Datenbanken, KI-Modelle, Parquet, Lance-Dateien oder Geospatial tilesets sein

SQLite-Erweiterung libgraft

• Aktuell ist libgraft, eine native SQLite-Erweiterung, der einfachste Weg, Graft zu nutzen
• libgraft kann überall eingesetzt werden, wo SQLite läuft, und repliziert nur den Teil der Datenbank, den der Client tatsächlich verwendet
• Es implementiert ein SQLite-VFS und fängt Datenbank-Lese- und Schreibzugriffe ab
• Es bietet dieselben Transaktions- und Nebenläufigkeitssemantiken wie SQLite im WAL mode
• Geboten werden unter anderem
  • Asynchrone Replikation mit Object Storage
  • Verzögerte partielle Replikation an der Edge und auf Geräten
  • Serializable Snapshot Isolation
  • Point-in-Time-Recovery
• Die Dokumentation findet sich in den SQLite-Dokumenten auf GitHub

Beteiligung und Pläne für einen Managed Service

• Graft wird offen auf GitHub entwickelt
• Issues, Diskussionen und Pull Requests sind willkommen; außerdem gibt es einen contribution guide
• Als Kommunikationskanäle stehen Discord und E-Mail bereit
• Geplant ist auch ein Graft Managed Service; ein Link zur Warteliste ist vorhanden

Roadmap

• Graft hat bereits ein Jahr Forschung, mehrere Iterationen und einen größeren Richtungswechsel hinter sich, aber es bleibt noch viel zu tun
• Geplant sind unter anderem
  • WebAssembly-Support: Damit Graft im Browser nutzbar wird; angestrebt wird Support für den offiziellen SQLite-Wasm-Build, wa-sqlite und sql.js
  • Integration von Graft und SQLSync: Nach dem Wasm-Support soll die Mutation-, Rebase- und Query-Subscription-Schicht von SQLSync getrennt und auf die von Graft replizierte Datenbank aufgesetzt werden
  • Mehr Client-Bibliotheken: Gewünscht sind native Graft-Client-Wrapper für Python, JavaScript, Go und Java
  • Schreibvorgänge mit geringer Latenz: Aktuell blockieren Push-Operationen, bis sie vollständig im Object Storage committed sind
    • Experimente mit S3 express zone
    • Ein Ansatz mit einer langlebigen Konsensgruppe mit geringer Latenz vor dem Object Storage
  • Garbage Collection, Checkpointing und Compaction: Notwendig für maximale Query-Performance, minimalen Speicherabfall und echtes Löschen
  • Authentifizierung und Autorisierung: Ein breites Aufgabenfeld von Managed-Service-Konten bis zu feingranularen Lese-/Schreibrechten pro Volume
  • Volume forking: Der Service kann per Kopie von Segment-Referenzen in ein neues Volume einen Zero-Copy-Fork erzeugen, lokal müssen derzeit aber noch alle Pages kopiert werden
  • Konfliktbehandlung: Geplant sind eingebaute Strategien zur Konfliktauflösung und Erweiterungspunkte; eine erste Strategie ist das automatische Mergen nicht überlappender Transaktionen

Vergleich mit SQLite-Replikationslösungen

• Die Vergleichsinformationen stammen aus Dokumentation und Blogposts und sind laut Hinweis möglicherweise nicht vollständig korrekt

• mvSQLite

  • mvSQLite implementiert eine benutzerdefinierte VFS-Schicht, die SQLite-Pages direkt in FoundationDB speichert
  • Graft und mvSQLite ähneln sich darin, dass Versionsverwaltung auf Seitenebene verzögertes Fetching und partielle Datenbankansichten ermöglicht
  • Der Unterschied liegt im Speicherort und in der Art, wie Seitenänderungen verfolgt werden
    • mvSQLite hängt von FoundationDB ab, und alle Nodes müssen direkt auf den Cluster zugreifen können
    • Grafts auf Splinter basierende Changesets sind in sich geschlossen und daher einfacher zu verteilen; zudem muss FoundationDB nicht direkt abgefragt werden, um Versionen geänderter Pages zu kennen

• Litestream

  • Litestream ist eine Streaming-Backup-Lösung, die SQLite-WAL-Frames fortlaufend in Object Storage repliziert
  • Graft integriert sich über ein benutzerdefiniertes VFS direkt in den SQLite-Commit-Prozess und ermöglicht dadurch verzögerte partielle Replikation und verteilte Schreibvorgänge
  • Beide replizieren Pages in Object Storage und unterstützen Point-in-Time-Recovery

• cr-sqlite

  • cr-sqlite ist eine SQLite-Erweiterung, die Tabellen in CRDTs umwandelt und logische Replikation auf Zeilenebene ermöglicht
  • Sie bietet automatische Konfliktauflösung, erfordert aber Schemawissen und Integration auf Anwendungsebene
  • Graft ist schemaunabhängig und kompatibel mit beliebigen SQLite-Erweiterungen sowie benutzerdefinierten Datenstrukturen; für globale Serialisierbarkeit muss die Anwendung Konfliktauflösung aber explizit behandeln

• Cloudflare Durable Objects with SQLite Storage

  • Die Kombination aus Durable Objects und SQLite erlaubt eine Datenbank im Cloudflare-Edge-Netzwerk mit starker Konsistenz und hoher Dauerhaftigkeit, umhüllt von Business-Logik
  • Intern ähnelt das Litestream, da SQLite-WAL in Object Storage repliziert und periodisch checkpointed wird
  • Graft exponiert Replikation als First-Class-Funktion und zielt auf effiziente Replikation mit der Edge

• Cloudflare D1

  • Cloudflare D1 ist eine gemanagte SQLite-Datenbank mit Zugriff per HTTP API
  • Graft verfolgt ein verteiltes Modell, bei dem Daten in Client-Anwendungen eingebettet und direkt an die Edge repliziert werden

• Turso & libSQL

  • Turso bietet über libSQL gemanagte SQLite-Datenbanken und eingebettete Replikate
  • Graft unterscheidet sich durch partielle Replikation und Unterstützung für beliebige schemaunabhängige Datenstrukturen
  • Der Graft-Backend-Service arbeitet auf Seitenebene und überlässt den gesamten Lebenszyklus von Transaktionen dem Client

• rqlite & dqlite

  • rqlite und dqlite verteilen SQLite über Raft-basierte Konsensmechanismen und Netzwerkprotokolle auf mehrere Server
  • Ihr Fokus liegt auf der Synchronisierung zustandsbehafteter Nodes, die miteinander verbunden bleiben
  • Graft ist ein zustandsloses System auf Basis von Object Storage und für den Datenaustausch mit der Edge entworfen

• Verneuil

  • Verneuil repliziert SQLite-Snapshots asynchron über Object Storage an Lesereplikate und priorisiert Zuverlässigkeit
  • Mechanismen zur Minimierung von Replikationslatenz oder Aktualität werden ausdrücklich vermieden
  • Graft verhält sich stärker wie eine verteilte Datenbank mit mehreren Schreibern und betont selektive partielle Replikation in Echtzeit