hckrnws
The consistency model doesn't seem to make sense.
https://github.com/orbitinghail/graft/blob/main/docs/design....
> Graft clients commit locally and then asynchronously attempt to commit remotely. Because Graft enforces Strict Serializability globally, when two clients concurrently commit based on the same snapshot, one commit will succeed and the other will fail.
OK, but, the API provides only a single commit operation:
> commit(VolumeId, ClientId, Snapshot LSN, page_count, segments) Commit changes to a Volume if it is safe to do so. The provided Snapshot LSN is the snapshot the commit was based on. Returns the newly committed Snapshot on success.
So if a client commits something, and it succeeds, presumably locally, then how should that client discover that the "async" propagation of that commit has failed, and therefore everything it's done on top of that successful local commit needs to be rolled-back?
This model is kind of conflating multiple, very different, notions of "commit" with each other. Usually "commit" means the committed transaction/state/whatever is guaranteed to be valid. But here it seems like a "local commit" can be invalidated at some arbitrary point in the future, and is something totally different than an "async-validated commit"?
You're right - it's a bit confusing! I took a crack at explaining it in the blog post under the Consistency section: https://sqlsync.dev/posts/stop-syncing-everything/#consisten...
The key idea is that if your system supports offline writes, then by definition the client making those writes can't have general purpose strict serializability. They have to exist under the assumption that when their transactions eventually sync, they are no longer valid. Graft attempts to provide a strong foundation (server side commits are strictly serialized), however let's the client choose how to handle local writes.
A client may choose any of these options:
1. If offline, reject all local writes - wait until we are online to commit
2. Rebase local writes on the latest snapshot when you come back online, resulting in the client experiencing "optimistic snapshot isolation"
3. Merge local changes with remote changes - this probably depends heavily on the datastructure you are storing in Graft. For example, storing a Conflict-Free Replicated Datatype (CRDT) would work nicely
4. Fork the Volume entirely and let the user figure out how to manually merge the branches back together
5. Throw away all local changes (probably not what you want, but it works!)
My goal is to build a building block on top of which edge native systems can be built. But I'm not too opinionated about what local write semantic you're application needs. :)
(edit: added newlines between list items)
What you've said here is totally different to what the repo docs claim.
The guarantees of Graft's "commit" operation are properties of the Graft system itself. If commit is e.g. strict-serializable when clients satisfy one set of requirements, and isn't strict-serializable if clients don't satisfy those requirements, then "commit" is not strict-serializable.
Just to make sure I understand correctly, would you agree that if clients always synchronously commit (i.e. wait until the MetaStore commit returns ok) before acknowledging any commit locally, the client will experience Strict Serializability?
Assuming you agree with that, what would be a more clear way to explain the tradeoffs and resulting consistency models in the event that a client desires to asynchronously commit?
I think I see the issue, but I'd love to hear your take on how to update the docs.
Firstly, it might be worth separating the concepts of read and write consistency. For example, in your system reads are eventually consistent (because syncing is not enforced) and the situation with writes is more complicated.
I think the key point of your design is flexibility, rather than any individual consistency properties. It might be better to emphasise this and try to explain, at the top-level, the concrete ways an application can interact with the storage and the different tradeoffs.
So you might have strong write consistency with forced global serialisation or weaker properties with less enforced sync policies. From the perspective of the application, the internal details shouldn’t matter, but the external properties and how to achieve them (eg. CRDT style merging etc as a way to get strong consistency with less syncing, for certain domains).
I think I'm probably operating with definitions of client and commit that are different than yours.
Specifically, I don't really see how a client can "commit locally" and "commit globally" as separate things. I understand a client to be something that interacts with your metastore API, which provides a single "commit" operation, that AFAICT will return success/failure based on local commit state, not global state.
Is that not correct?
Later on in the design.md you say
> The Client will be a Rust library ...
which might be the missing link in this discussion. Is the system model here assuming that clients are always gonna be Rust code in the same compilation unit as the Graft crate/library/etc.?
Graft's definition sounds more like a Git "commit" than one found in a SQL standard. Perhaps that's the source of this confusion?
That may be the case, but the Git notion of a "commit" is a domain concept that is unrelated to, and incompatible with, the distsys notion of a "commit". And terminology like "strict serialization" and "snapshot isolation" and so on -- which this system and its docs reference -- are distsys concepts, not Git concepts. So "commit" needs to abide distsys rules, not Git rules, as you can't really mix-and-match definitions across domains.
Git is a DVCS. The D stands for distributed, meaning (in old people language) masterless. Git doesn't have a "global."
The doc you linked and the author's response here do a good job of clarifying the conditions.
They're building an edge data store that has both local and global characteristics, with certain options meant for offline mode. It's reasonable to assume that the answer is more complicated when talking about the strict serializability of such a system.
It's basically single master asynchronous replication. And only works for sqlite's journal mode. The master saves all sqlite's journals as commit history and sends them to followers to replay them.
Hey friends! Author of Graft here. Just want to say, huge thanks for all the great comments, stars, and support. Feels really nice to finally be building in public again.
I'm going to force myself to sign off for the evening. Will be around first thing to answer any other questions that come up! I just arrived to Washington, DC to attend Antithesis BugBash[1] and if I don't get ahead of the jet lag I'm going to regret it.
If anyone happens to be around Washington this week (perhaps at the conference) and wants to meet up, please let me know! You can email me at hello [at] orbitinghail [dotdev].
Thanks for sharing this, it looks really cool. I also wanted to explicitly mention that the graphics are great. IDK if you made them, or got help, but they do a great job explaining your point. It can be hard to create graphics for technical concepts like pages and databases, but these work well.
Thank you! I made them myself using http://excalidraw.com/.
Exciting to see all the continued energy around Graft today! If you want to continue the conversation feel free to join the Discord [1] or post a discussion on GitHub [2].
I'll be at Antithesis BugBash [3] for the next few days talking about Deterministic Simulation Testing (DST) with fellow DST nerds. If you're around please reach out so we can meet in person!
Either way, have an excellent day! :)
[1]: https://discord.gg/etFk2N9nzC
Great work here! A bit of a silly question - but can I ask you what tool you used to build the beautiful diagrams on the page (eg: https://sqlsync.dev/_astro/pull_changes.DjOYfgBf_2biXxv.webp)
Thank you! I made all the diagrams in https://excalidraw.com/. Been using it for years and absolutely love it!
So, if I understand correctly, the consistency model is essentially git. I.e. you have a local copy, makes changes to it, and then when its time to "push" you can get a conflict where you can "rebase" or "merge".
The problem here is that there is no way to cleanly detect a conflict. The documentation talks about pages which have changed, but a page changing isnt a good indicator of conflict. A conflict can happen due to a read conflict. E.g.
Update Customer Id: "UPDATE Customers SET id='bar' WHERE id='foo'; UPDATE Orders SET customerId='bar' WHERE customerId='foo'"
Add Customer Purchase: "SELECT id FROM Customers WHERE email="blah"; INSERT INTO Orders(customerId, ...) VALUES("foo", ...);"
If the update task gets committed first and the pages for the Orders table are full (i.e. inserting causes a new page to allocated) these two operations dont have any page conflicts, but the result is incorrect.\
In order to fix this, you would need to track the pages read during the transaction in which the write occurred, but that could easily end up being the whole table if the update column isnt part of an index (and thus requiring a table scan).
In git the rebase of course isn't a sound operation either, the merge is heuristic and you're liable to get conflicts or silent mismerges.
Some simple examples: https://www.caktusgroup.com/blog/2018/03/19/when-clean-merge...
They address this later on.
If strict serializability is not possible, because your changes are based on a snapshot that is already invalid, you can either replay (your local transactions are not durable, but system-wide you regain serializability) or merge (degrading to snapshot isolation).
As long as local unsynchronized transactions retain the page read set, and look for conflicts there, this should be sound.
What I find hard to imagine is how the app should respond when synchronisation fails after locally committing a bunch of transactions.
Dropping them all is technically consistent but it may be unsafe depending on the circumstances. E.g. a doc records an urgent referral but then the tx fails because admin staff has concurrently updated the patient's phone number or whatever. Automatically replaying is unsafe because consistency cannot be guaranteed.
Manual merging may be the only safe option in many cases. But how can the app reconstitute the context of those failed transactions so that users can review and revise? At the very least it would need access to a transaction ID that can be linked back to a user level entity, task or workflow. I don't think SQLite surfaces transaction IDs. So this would have to be provided by the Graft API I guess.
What I find hard to imagine is how the app should respond when synchronisation fails after locally committing a bunch of transactions... Manual merging may be the only safe option in many cases.
Yeah, exactly right. This is why CRDTs are popular: they give you well-defined semantics for automatic conflict resolution, and save you from having to implement all that stuff from scratch yourself.
The author writes that CRDTs "don’t generalize to arbitrary data." This is true, and sometimes it may be easier to your own custom app-specific conflict resolution logic than massaging your data to fit within preexisting CRDTs, but doing that is extremely tricky to get right.
It seems like the implied tradeoff being made by Graft is "you can just keep using the same data formats you're already using, and everything just works!" But the real tradeoff is that you're going to have to write a lot of tricky, error-prone conflict resolution logic. There's no such thing as a free lunch, unfortunately.
The problem I have with CRDTs is that while being conflict-free in a technical sense they don't allow me to express application level constraints.
E.g, how do you make sure that a hotel room cannot be booked by more than one person at a time or at least flag this situation as a constraint violation that needs manual intervention?
It's really hard to get anywhere close to the universal usefulness and simplicity of centralised transactions.
"How do you make sure that a hotel room cannot be booked by more than one person at a time" Excellent question! You don't. Instead, assuming a globally consistent transaction ordering, eg Spanner's TrueTime, but any uuid scheme suffices, it becomes a tradeoff between reconciliation latency and perceived unreliability. A room may be booked by several persons at a time, but eventually only one of them will win the reconciliation process.
A: T.uuid3712[X] = reserve X
...
B: T.uuid6214[X] = reserve X // eventually loses to A because of uuid ordering
...
A<-T.uuid6214[X]: discard T.uuid6214[X]
...
B<-T.uuid3712[X]: discard T.uuid6214[X], B.notify(cancel T.uuid6214[X])
-----
A wins, B discards
Yeah, this is a limitation, but generally if you have hard constraints like that to maintain, then yeah you probably should be using some sort of centralized transactional system to avoid e.g. booking the same hotel room to multiple people in the first place. Even with perfect conflict resolution, you don't want to tell someone their booking is confirmed and then later have to say "oh, sorry, never mind, somebody else booked that room and we just didn't check to verify that at the time."
But this isn't a problem specific to CRDTs, it's a limitation with any database that favors availability over consistency. And there are use cases that don't require these kinds of constraints where these limitations are more manageable.
I agree, hotel booking is not a great example.
I think CRDTs would be applicable to a wider range of applications if it was possible to specify soft constraints.
So after merging your changes you can query the CRDT for a list of constraint violations that need to be resolved.
> your local transactions are not durable
This manifests itself to the user as just data loss, though. You do something, it looks like it worked, but then it goes away later.
From the description, you can reapply transactions. How the system handles it (how much of it is up to the application, how much is handled in graft) I have no idea.
What does that mean though? How can you possibly reapply a failed transaction later? The database itself can't possibly know how to reconcile that (if it did, it wouldn't have been a failure in the first place). So it has to be done by the application, and that isn't always possible. There is still always the possibility of unavoidable data loss.
"Consistency" is really easy, as it turns out, if you allow yourself to simply drop any inconvenient transactions at some arbitrary point in the future.
This! Solving merge conflicts in git is quite hard. Building an app such that it has a UI and use cases for merging every operation is just unrealistic. Perhaps if you limit yourself to certain domains like CRDTs or turn based games or data silos modified by only one customer it can be useful. I doubt it can work in general case.
The only situation I can think of where it's always safe is if the order that you apply changes to the state never matters:
- Each action increments or decrements a counter
- You have a log of timestamps of actions stored as a set
- etc.
If you can't model your changes to the data store as an unordered set of actions and have that materialize into state, you will have data loss.
Consider a scenario with three clients which each dispatch an action. If action 1 sets value X to true, action 2 sets it to true, and action 3 sets it to false, you have no way to know whether X should be true or false. Even with timestamps, unless you have a centralized writer you can't possibly know whether some/none/all of the timestamps that the clients used are accurate.
Truly a hard problem!
> After a client pulls a graft, it knows exactly what’s changed. It can use that information to determine precisely which pages are still valid and which pages need to be fetched
Curious how this compares to Cloud-Backed SQLite’s manifest: https://sqlite.org/cloudsqlite/doc/trunk/www/index.wiki
It’s similar to your design (sending changed pages), but doesn’t need any compute on the server, which I think is a huge win.
Thanks for bringing that up! Cloud-Backed SQLite (CBS) is an awesome project and perhaps even more importantly a lot more mature than Graft. But here is my overview of what's different:
CBS uses manifests and blocks as you point out. This allows readers to pull a manifest and know which blocks can be reused and which need to be pulled. So from that perspective it's very similar.
The write layer is pretty different, mainly because CBS writes blocks directly from the client, while Graft leverages an intermediate PageStore to handle persistence.
The first benefit of using a middleman is that the PageStore is able to collate changes from many Volumes into larger segments in S3, and soon will compact and optimize those segments over time to improve query performance and eliminate tombstones.
The second benefit is fairly unique to Graft, and that is that the written pages are "floating" until they are pinned into a LSN by committing to the MetaStore. This matters when write concurrency increases. If a client's commit is rejected (it wasn't based on the last snapshot), it may attempt to rebase its local changes on the latest snapshot. When it does so, Graft's model allows it to reuse any subset of its previously attempted commit in the new commit, in the best case completely eliminating any additional page uploads. I'm excited to experiment with using this to dramatically improve concurrency for non-overlapping workloads.
The third benefit is permissions. When you roll out Graft, you are able to enforce granular write permissions in the PageStore and MetaStore. In comparison, CBS requires clients to have direct access to blob storage. This might work in a server side deployment, but isn't suited to edge and device use cases where you'd like to embed replicas in the application.
On the manifest side of the equation, while in CBS it's true that a client can simply pull the latest manifest, when you scale up to many clients and high change workload, Graft's compressed bitset approach dramatically reduces how much data clients need to pull. You can think of this as pulling a log vs a snapshot, except for metadata.
Hope that helps clarify the differences!
Oh, and one more petty detail: I really like Rust. :)
That makes total sense! Beyond the efficiency of no servers, the other aspect of CBS that is appealing to me is its simplicity.
Graft introduces a lot of new concepts, and while they might be necessary to achieve the more ambitious goals, it feels a like a lot. Running an HTTP API with Protobuf is a lot of API surface area to maintain and evolve going forward.
Write concurrency for CBS is "one writer per bucket", which is usable in a "one bucket per user" configuration. You can mediate a client's blob storage access with signed URLs. It's not great, though, and you have to roll your own conflict resolution.
The most interesting choice to me here is to handle conflict resolution (rebasing/forking/resetting) at the storage engine (page) level. For non-overlapping writes, I can see how rebasing is quite effective.
Fair! CBS is absolutely a killer solution to the same class of problems.
When you say “rebase” what do you mean exactly? Is it the application replaying the transaction including the interactive code, or is it the database writing the same rows/pages that were written last time?
Woah, hadn't seen this before but this is really cool!
I was recently looking for a way to do low scale serverless db in gcloud, this might be better than any of their actual offerings.
Cloud firestore seems like the obvious choice, but I couldn't figure out a way to make it work with existing gcloud credentials that are ubiquitous in our dev and CI environments. Maybe a skill issue.
I've always found these general solutions kind of confusing. All uses of distributed data are inherently flawed, and have specific limitations, so you have to pick a solution that closest matches your specific use case.
I like the idea behind graft, but it immediately runs into some complications. Like the fact that, as an edge device with unreliable networking, its client may not have availability to fetch the pages it needs when it needs them. If anything, what the client really needs is to fetch all the data whenever it can, so that when it does need to access it, it isn't waiting.
But if you have a lot of data, that could take forever! That's why the application needs to be more intelligent about what data it's requesting, and do things like create priorities and classes for its data so it can fetch what it needs the most first.
The fact that this is built for SQLite kind of reinforces the point. Distributed relational databases are usually a bad idea, because usually people want them to be ACID-like, but you can't enforce that in a distributed way. That's why things like CRDTs exist; you treat every "copy" as an independent thing, breaking the false narrative that you can really distribute the same thing in multiple places reliably. (And that shows you why relational databases just aren't good for replicating; to replicate an entire relational database with CRDTs, you need one CRDT per cell, which multiplies your data)
in case anyone finds this useful, here's the slowly growing collection of links to similar tools:
https://collabs.readthedocs.io/en/latest/
https://rxdb.info/offline-first.html
https://github.com/siriusastrebe/jsynchronous
I hope one day to try them all :-) Or read a summary from someone who does.
I wonder why there are so many, just people reinventing stuff that no one really needs?
For me personally I have 4 of those as visited, pouchdb, automerge, loro and sqlsync of course. I was trying to fit such a tool into existing architectures that I deal with at work but nothing really makes sense.
My guess is those solutions are in totally wrong abstraction layer, creators think that would be best thing since sliced bread - but in reality having rest API and some persistence on client is like 99% good enough. With service workers in browser and mobile apps no problem of just having data stores.
Sending out specific partial updates, just reloading full state from the server is just easy to explain to the users and easy to implement. Last write wins with some auditing log is also good for something like 99.9% of applications and is super easy to explain to people - what's not easy to explain and not easy to implement is merging conflicts on database data. It is not easy to make audit logs server side so they are not tampered with if you just sync full database instead of doing REST requests.
This approach with "sync databases" feels for me exactly like someone proposing use of LateX because it is great to people who need to write 10 page essays.
It's about the multiplayer application case, think Google Write/Sheets/etc. Applications with data that can change by multiple users and you can both see it live and the application (that keeps state in memory/localdb) is also resilient to disconnects.
The reason people descend into this madness is because visible replication code is tricky and the general feeling is that it'll infect parts that shouldn't be infected (or at least not without a general framework).
So at a somewhat trivial level you have:
A: A bare log replication system (where the application needs awareness for most object types multiplying object complexity).
B: A object replication system where the framework handles all object types coherently and the application "only" needs to be aware of how to fetch objects, think a KV store that stores fairly basic objects with some addressing support.
C: Since recent crowd "wisdom" dictates that most KV stores will likely re-implement SQL functionality badly, people go straight to doing the SQL case (maybe they've had a curiosity about SQL databases already that they're scratching)
I've recently built A (basic replication and LWW) and building the application I'm definitively feeling an itch to just start over or adjust to support B (a simple replicated KV store) to separate the concerns more, I can see how I would also feel the SQL itch of C (but having done SQL like systems before it's not as bad for me).
For this first application A will suffice (since the offline needs are relatively trivial) but having a more complicated application in mind I'm strongly considering B for that project (along with designs or third party libs to make it happen).
I think a big gap in the space is that most seem focused on "documents" (esp the CRDT based tools), ie a document being the atomic piece that is synchronized but imo it leaves a big gap in that now all regular application management tools like SQL query tools are useless since essentially you only have a bunch of "blobs" or worse. If you want the regular enterprise SQL backend these tools don't seem to have a focus on synchronizing to those regular backend storage systems.
This gap is filled by the likes of Couchbase where a single org controls the majority of the stack (spoiler/disclaimer alert: I've been working on Couchbase's Sync for 8 years)
You get local the document-level atomicity for sync. Multi-document transaction support on server side, KV access, SQL inside JSON docs or even across multiple documents, Full Text Search, and fine-grained/RBAC for document-level synchronization - but the cost is as much lock-in as it is financial. You can't mix and match storage, query or sync without pretty big tradeoffs.
I don’t see it you missed the context or I miss something.
Multiplayer documents are real time synchronized and since they are documents that’s totally not use case for DB synchronization.
All the tools are for offline to online data synchronization. Different use case than document.
Not really, the fundamental problem shared for all the tools mentioned by GP is the same of concurrent edits. We as an industry typically ignore it in regular CRUD settings due to low conflicting operation frequency, but it gets problematic in offline and multiplayer settings since those cause it to become more common/visible.
As for documents vs DB, technically you can often compose documents into a number of tables. And having it decomposed into a regular DB simplifies a lot of visibility tasks since you don't need to built an extra layer to manage that and/or you might want to implement partial permissions into something that feels "document like" but really pertains to a larger system.
> I wonder why there are so many, just people reinventing stuff that no one really needs? Or were you being rhetorical?
What do people really need? Who defines and polices that?
> just reloading full state from the server is just easy to explain to the users and easy to implement
Is the green light on? If not, press the "power" button. Never underestimate the difficulty of explaining the simple to the uninterested.
The audience in this case is geeks like us, so it's probably ok to have wonky process until someone forks the project and fixes those problems.
"nearly every problem these days is a synchronisation problem"
Wrote a very-related blog post here:
thanks for the link! just in time for me.
This is a really interesting project, and a great read. I learned a lot. I'm falling down the rabbit hole pretty hard reading about the "Leap" algorithm (https://www.usenix.org/system/files/atc20-maruf.pdf) it uses to predict remote memory prefetches.
It's easy to focus on libgraft's SQLite integration (comparing to turso, etc), but I appreciate that the author approached this as a more general and lower-level distributed storage problem. If it proves robust in practice, I could see this being used for a lot more than just sqlite.
At the same time, I think "low level general solutions" are often unhinged when they're not guided by concrete experience. The author's experience with sqlsync, and applying graft to sqlite on day one, feels like it gives them standing to take a stab at a general solution. I like the approach they came up with, particularly shifting responsibility for reconciliation to the application/client layer. Because reconciliation lives heavily in tradeoff space, it feels right to require the application to think closely about how they want to do it.
A lot of the questions here are requesting comparison's to existing SQLite replication systems, the article actually has a great section on this topic at the bottom: https://sqlsync.dev/posts/stop-syncing-everything/#compariso...
Thank you! I'm extremely excited and interested to explore applying Graft to solutions outside of SQLlite/SQLSync. That was a driving factor behind why I decided to make it more general. But you're absolutely right, I'm glad I spent time developing use cases first and then worked backwards to a general solution. I made a lot of mistakes in the process that I wouldn't have seen if I had gone the other way.
And yea, I fell pretty far down the "Leap" rabbit hole. It's a fun one :)
I didn't go into the implementation details so I won't comment on that, but I will say that this is a really important problem to solve. I've long wanted/needed an agnostic sync layer that apps could use to sync my changes across clients and servers, and it would be great if app developers didn't have to put any work into it, they'd just point their database to a URL and the database would take care of all the syncing.
This means that the app developer could support private syncing without any effort, and I wouldn't have to pay a subscription just for sync, I could just run a sync server on my NAS and all apps would know to sync their data with it. Of course, app developers don't want this because subscriptions are a reliable income stream, but hopefully users would push for it.
~10 years ago, CouchDB was the answer to this problem. I don't know what the status of that is in 2025, but at the time it was used to e.g. sync airplane sales tablets with a central database once they were back on the ground and online.
Yeah, what happened to CouchDB? I thought it would be much more popular, but I haven't heard of it in years. Maybe this problem isn't actually important, or maybe people don't know they can solve it in this way?
This space is very much alive and well and I'm really glad there's more competition cropping up from smaller projects like OP.
Disclaimer: I have worked on a sync backend for a company in this space for the last 8 years. You can probably find out where if you look, but this comment won't be a sales pitch.
Competition like this has incredible value for communities with poor internet access but reasonable development capabilities. Think about travelling doctors in the lesser developed countries and areas of Africa for instance. Quite often entire villages get medical checkups done, with data being recorded on a tablet. This can be synced once the doctor gets to a town with internet access for follow-up. Of course, projects like the above do not have big budgets. Unfortunately they are priced out of using a lot of tech to solve these problems (my company included in this statement)
On the more enterprise-y side, which is where I mostly sit, a lot of airlines, cruise ships, retail and field-based industry use these technologies, since they are prone to periods of being completely offline or in a P2P mesh only. Cloud databases or even regular replicated databases running in-situ are a non-starter, since there won't be anybody around to administer it. Replication is a difficult problem at the best of times, let alone in periods of comms downtime.
Not an expert on CouchDB, but used it recently in a project and loved the syncing with the corresponding pouchdb at the frontend. My main problem, what was missing imho was security: Interactions with couchdb where directly with the database, ie no intermediate API available. Maybe that was a good idea when couchDB was designed, but it made me feel uncomfortable in 2024. If anyone knows of an intermediate API-Layer for couchdb, please post.
Interesting that you're seeing the lack of intermediate server/API as a drawback. InstantDB sees it as progress, see their essay on it:
Thank you! Glad we see the world the same way! I've also always wanted a general purpose sync layer that provided a simple consistency model to build on top of.
And I made Graft open source to enable exactly that! Deploy it anywhere! Just let me know so I can better support your use case :)
Thanks for building SQLSync! You might like Klepmann's "local-first" talks, though I'm sure you're already familiar.
You're welcome! And yea, I'm a huge fan of Klepmann and his local first content :) Thanks for the reminder!
Looks impressive! Using the VFS is such a fun "hack" :)
We developed our own sync engine for an offline-first IDE for notes/tasks [1] we're building, where the data structure is a tree (or graph actually) to support outlining operations. Conflict resolution is always the challenge, and especially with trees multiple offline players can optimistically commit local changes which would result in an invalid tree state once globally merged.
The way we handle this is by rolling back tree inserts when a client comes online and receives other tree insert deltas. From what I understand from the description of SQLSync, the best way to handle this would be to pull in a latest snapshot and then replay. Pulling in a full snapshot sounds rather expensive though. We have some sort of heuristic where we can do this if the number of incoming deltas would be very large, but for most offline syncing we never need it. Just curious how SQLSync defines these snapshots? Sticking with the note-taking example, in our case we can't really have a snapshot of a single "note" because of graph features like transclusions. Does SQLSync have some clever way to avoid having to send all state in order to "reset and replay"?
Thank you! And I agree haha. I love writing SQLite VFS's.
In SQLSync, the major issue was precisely what you describe: pulling in the full snapshot to replay. This is the main driver behind the "partial" aspect of the Graft design. It means that clients only need to pull the portion of the incoming snapshot that they don't already have and that overlap with the read/write set of their transactions. So yes, to answer your question once SQLSync is powered by Graft, it will frequently be able to avoid downloading all state in order to reset and replay.
Note that if a client is ok with relaxing to snapshot isolation (in particular this means clients may experience Write Skew[1]), and the r/w set of their local transaction does not intersect the snapshot changeset, Graft is able to perform an automatic merge.
Seems interesting. A very challenging problem to wrap your head around. Anyone working on this is exactly pushing the field forward.
I'm thinking to give it a try in one of my React Native apps that face very uncertain connectivity.
> I'm thinking to give it a try in one of my React Native apps that face very uncertain connectivity.
Some similar stuff you may want to investigate (no real opinion, just sharing since I've investigated this space a bit):
https://localfirstweb.dev is a good link too.
It's been a fun project to work on, and I'm excited to see how deep this rabbit hole goes. :)
I'd love to hear how that goes! I haven't tried getting the SQLite extension running on mobile yet, so any help there would be very appreciated! I'm hoping it "just works" module maybe having to compile against a different architecture.
Another relevant project: https://zero.rocicorp.dev/
For a deep dive on Graft, a talk I did two weeks ago at Vancouver Systems just went live! You can watch it here: https://www.youtube.com/watch?v=P_OacKS2h5g
The talk contains a lot more details on how the transactional and replication layers of Graft work.
This approach has a problem when the mobile client is on the end of a very slow connection, yet the diff that needs to be synced is gigabytes, perhaps because it's an initial sync or the database got bloated for whatever reason.
A hybrid approach is to detect slow syncing (for example when sync hasn't completed after 5 seconds), and instead send queries directly to the server because there is a good chance the task the user wants to complete doesn't depend on the bloated records.
This is a great point. Solutions like Graft which involve syncing data to the edge work poorly when the dataset size is too large and not partitioned enough to be consistency partial.
This is why Graft isn't just focused on client sync. By expanding the focus to serverless functions and the edge, Graft is able to run the exact same workload on the exact same snapshot (which it can validate trivially due to its consistency guarantees) anywhere. This means that a client's workload can be trivially moved to the edge where there may be more resources, a better network connection, or existing cached state.
Maybe it's just me, since people here in the comments apparently understand what this is, but even after skimming the comments, I don't. Some simplified API example would be useful either in the "marketing post" or (actually, and) in the github readme.
I mean, it's obviously about syncing stuff (despite the title), ok. It "simplifies the development", "shares data smoothly" and all the other nice things that everything else does (or claims to do). And I can use it to implement everything where replication of data might be useful (so, everything). Cool, but... sorry, what does it, exactly?
The biggest problem with syncing is, obviously, conflict resolution. Graft "doesn’t care about what’s inside those pages", so, obviously, it cannot solve conflicts. So if I'm using it in a note-taking app, as suggested, every unsynced change to a plain text file will result in a conflict. So, I suppose, it isn't what it's for at all, it's just a mechanism to handle replication between 2 SQLite files, when there are no conflicts between statements (so, what MySQL or Postgres do out of the box). Right? So, it will replace the standard SQLite driver in my app code to route all requests via some Graft-DB that will send my statements to external Graft instance as well as to my SQLite storage? Or what?
If they can’t successfully communicate the problem that they’re solving, chances are, they don’t know it themselves.
Reading their readme:
> Licensed under either of
> Apache License, Version 2.0 (LICENSE-APACHE or https://www.apache.org/licenses/LICENSE-2.0)
> MIT license (LICENSE-MIT or https://opensource.org/licenses/MIT)
> at your option.
I see this now and then, but it makes me wonder, why would I pick in this case Apache over MIT? Or is this software actually Apache licensed, but the developer is giving you greenlight to use it under the terms of the MIT? But at that point I don't get why not just license it all under MIT to begin with...
Per the Rust FAQ [1]:
> The Apache license includes important protection against patent aggression, but it is not compatible with the GPL, version 2. To avoid problems using Rust with GPL2, it is alternately MIT licensed.
The Rust API guidelines also recommend the same: https://rust-lang.github.io/api-guidelines/necessities.html#...
[1]: https://github.com/dtolnay/rust-faq#why-a-dual-mitasl2-licen...
From my perspective (as the author of Graft) my goal was to be open source and as compatible as possible with the Rust ecosystem. Hence the choice to dual license.
Thank you! That is helpful, and understandable from that context. I to try to follow the best standards surrounding the language I use for a given project.
One thing I can think of is that Apache gives you a patent grant and MIT doesn't
Very interesting! I've been hacking on a somewhat related idea. I'm prototyping a sync system based on pglite and the concept of replicating "intentions" rather than data. By that I mean replicating actions -- a tag and a set of arguments to a business logic function along with a hybrid logical clock and a set of forward & reverse patches describing data modified by the action.
As long as actions are immutable and any non-deterministic inputs are captured in the arguments they can be (re)executed in total clock order from a known common state in the client database to arrive at a consistent state regardless of when clients sync. The benefit of this I realized is that it works perfectly with authentication/authorization using postgres row level security. It's also efficient, letting clients sync the minimal amount of information and handle conflicts while still having full server authority over what clients can write.
There's a lot more detail involved in actually making it work. Triggers to capture row level patches and reverse patches in a transaction while executing an action. Client local rollback mechanism to resolve conflicts by rolling back local db state and replaying actions in total causal order. State patch actions that reconcile the differences between expected and actual outcomes of replaying actions (for example due to private data and conditionals). And so on.
The big benefits of this technique is that it isn't just merging data, it's actually executing business logic to move state forward. That means it captures user intentions where a system based purely on merging data cannot. Traditional crdt that merges data will end up at a consistent state but can provide zero guarantees about the semantic validity of that state to the end user. By replaying business logic functions I'm seeking to guarantee that the state is not only consistent but maximally preserves the intentions of the user when reconciling interleaved writes.
This is still a WIP and I don't have anything useful to share yet but I think the core of the idea is sound. Exciting to see so much innovation in the space of data sync! It's a tough problem and no solution (yet) handles the use cases of many different types of apps.
Glad you enjoyed Graft! The system your describing sounds very cool! It's actually quite similar to SQLSync. The best description of how SQLSync represents and replays intentions (SQLSync calls them mutations) is this talk I did at WasmCon 2023: https://www.youtube.com/watch?v=oLYda9jmNpk
Cool! That's an interesting approach putting the actions in wasm. I'm going for something more tightly integrated into an application rather than entirely in the database layer.
The actions in my prototype are just TS functions (actually Effects https://effect.website/ but same idea) that can arbitrarily read and write to the client local database. This does put some restrictions on the app -- it has to define all mutations inside of actions and capture any non-deterministic things other than database access (random number, time, network calls, etc) as part of the arguments. Beyond that what an app does inside of the actions can be entirely arbitrary.
I think that hits the sweet spot between flexibility, simplicity, and consistency. The action functions can always handle divergence in whatever way makes sense for the application. Clients will always converge to the same semantically valid state because state is always advanced by business logic, not patches.
Patches are recorded but only for application to the server's database state and for checking divergence from expected results when replaying incoming actions on a client. It should create very little load on the backend server because it does not need to execute action functions, it can just apply patches with the confidence that the clients have resolved any conflicts in a way that makes the most sense.
It's fun and interesting stuff to work on! I'll have to take a closer look at SQLSync for some inspiration.
Woah that's awesome. Using Effect to represent mutations is brilliant!
Any chance your project is public? I'd love to dig into the details. Alternatively would you be willing to nerd out on this over a call sometime? You can reach me at hello [at] orbitinghail [dotdev]
As promised, here's the code. I decided to call it Synchrotron. Not ready for use yet but there is design/planning in the readme and a suite of passing tests showing that the approach can work. https://github.com/evelant/synchrotron
Sweet!! Will check it out shortly. Thanks for sharing :)
I haven't put it up in a github repo yet, it's not finished enough, but I will after spending a little more time hacking on it. I'll try to remember to come back here to comment when I do =)
Using effect really doesn't introduce anything special -- plain async typescript functions would work fine too. My approach is certainly a lot less sophisticated than yours with Graft or SQLSync! I just like using Effect. It makes working with typescript a lot more pleasant.
> Graft should be considered Alpha quality software. Thus, don't use it for production workloads yet.
Beta ETA?
ASAP :)
I looked at using turso embedded replicas for a realtime collaboration project and one downside was that each sync operation was fairly expensive. The minimum payload size is 4KB IIRC because it needs to sync the sqlite frame. Then they charge based on the number of sync operations so it wasn't a good fit for this particular use case.
I'm curious if the graft solution helps with this. The idea of just being able to ship a sqlite db to a mobile client that you can also mutate from a server is really powerful. I ended up basically building my own syncing engine to sync changes between clients and servers.
For now, Graft suffers from the same minimum payload size of 4KB. However, there are ways to eliminate that. I've filed an issue to resolve this in Graft (https://github.com/orbitinghail/graft/issues/35), thanks for the reminder!
As for the more general question though, by shipping pages you will often ship more data than the equivalent logical replication approach. This is a tradeoff you make for a much simpler approach to strong consistency on top of arbitrary data models.
I'd love to learn more about the approach you took with your sync engine! It's so fun how much energy is in the replication space right now!
This is a very interesting approach. Using pages as the basic sync unit seems to simplify a lot. It also makes the sync of arbitrary bytes possible. But it does seem that if your sync is this coarse-grained that there would be lots of conflicting writes in applications with a lot of concurrent users (even if they are updating semantically unrelated data). Seems like OT or CRDT would be better in such a use-case. I'd be interested to see some real-world benchmarks to see how contention scales with the number of users.
Thank you! You're 1000% correct, Graft's approach is not a good fit for high write contention on a single Volume. Graft instead is designed for architectures that can either partition writes[^1] or can represent writes as bundled mutations and apply them in a single location that can enforce order (the SQLSync model).
Basically, Graft is not the full story, but as you point out - because it's so simple it's easy to build different solutions on top of it.
[^1]: either across Volumes or across pages, Graft can handle automatically merging non-overlapping page sets
> [rqlite and dqlite] are focused on increasing SQLite’s durability and availability through consensus and traditional replication. They are designed to scale across a set of stateful nodes that maintain connectivity to one another.
Little nitpick there, consensus anti-scales. You add more nodes and it gets slower. The rest of the section on rqlite and dqlite makes sense though, just not about "scale".
Hey Phil! Also you're 100% right. I should use a different word than scale. I was meaning scale in the sense that they "scale" durability and availability. But obviously it sounds like I say they are scaling performance.
I've changed the wording to "They are designed to keep a set of stateful nodes that maintain connectivity to one another in sync.". Thank you!
Thank you!
I’ll nitpick you back: if done correctly, consensus can have quite positive scaling consensus groups can have quite a positive impact on tail latency. As the membership size gets bigger, the expectation on the tail latency of the committing quorum goes down assuming independence and any sort of fat tailed distribution for individual participants.
In the post or the comments here nobody mentions end-to-end encryption. Obsidian Sync offers multi-user sync withe2e encryption. An open source general tools solving the same problem would be great.
Man this looks super awesome. I will be extremely excited to ditch CouchDB for this (even tho I'm an Erlang fan). I'll certainly be keeping an eye on the project and I'll pitch in where I can!
Thank you!!
From an extremely brief scan, it appears that Erlang wrappers around SQLite should be able to use the Graft SQLite extension just fine.
Alternatively, it would be reasonably straight forward to wrap Graft Client (Rust library) directly in an Erlang NIF using something like https://github.com/rusterlium/rustler
Let's make it happen! :)
Oh, I don't use anything about CouchDB except the REST API. sorry to send you on a wild goose chase >.<
Much appreciated, I'll keep you informed :)
How are permissions supposed to work? Suppose a page has data that I need to see and also has data I can’t see. Does this mean I need to demoralize my entire data model?
There is simply so much to talk about here! Thanks for such an excellent question.
First, a caveat: Graft currently has no permissions. Anyone with access to the Graft PageStore and MetaStore can read/write to any volume. This is obviously going to change - so I'll talk about what's planned rather than what exists. :)
For writes, Graft can support fairly granular permission models. This is an advantage of handling writes in the PageStore. Depending on the data being stored in a Volume, a future PageStore version could reject writes based on inspecting the uploaded pages. This would increase the load on the PageStore, but since it's designed to run on the edge and horizontally scale like crazy (stateless) it seems like it would work.
Reads, on the other hand, are a lot more tricky. The simplest approach is to partition data across Volumes such that you can enforce read permissions at the Volume level. This isn't a great solution and will certainly limit the kinds of workloads that are well aligned with Graft. A more complex approach is to layer Volumes. Effectively virtualizing a single database that internally writes rows to different layers depending on access permissions. This second approach offers a slightly nicer user experience, at the cost of complexity and query performance.
For now though, Graft is best suited to workloads that can partition data and permissions across Volumes.
Separate Volume per user makes sense... but to build an application where users can collaborate, I would need some way of fanning out writes to other users' databases. Any thoughts on how to do that in the context of Graft?
If you're doing volume per user, but also want to do cross-user collab you might want to change the model slightly. Rather than one volume per user, consider one volume per "access unit". For example a document or group could be a volume.
As an example, let's say your building something like Google Sheets on top of Graft. Each document would be an independent Volume. This matches how Sharing works in Google Sheets, as each user added to the Volume could either be granted read or write permissions to the entire sheet.
I don’t believe SQLite has that kind of permissions system.
You probably want a db-per-user architecture with this kind of thing
Really like the look of this. Any thoughts on how it could be extended to work with duckdb?
Thanks! And great idea. I haven't deep dived into DuckDB's storage format yet, however I know that they split up the data into row groups which internally are columnar. I'm not sure how that maps to the pages in the file. If it doesn't align well, or they do a lot of shifting style writes (writes that cause all subsequent data to shift forward or backward) it may not be a great fit for Graft.
Either way, it's 100% a great idea that I'd like to explore. If any DuckDB contributors are reading I'd love to know if it would work!
"What are you syncing about?" https://youtu.be/0MUsVcYhERY?si=8gEMOo3nkd7SRX-Q
Finally got a chance to watch this. LMAO so good!
Congratulations, amazing job and documentation, I will deep on it.
Thank you!
Comment was deleted :(
How does this compare with Turso? I know it's mentioned in the article (mainly better support for partial replication and arbitrary schemas), but is there also a deeper architectural departure between the two projects?
Looks really good, great work!
Thank you! Generally Turso has focused on operating more like a traditional network attached backend. Although that has changed recently with libsql and embedded replicas. I think at this point the main delta is they use traditional wal based physical replication while Graft is something new that permits trivial partial replication. Also, Graft is not exclusive to SQLite. It’s just transactional page addressed object storage with built in replication. I’m excited to see what people build on it.
Thanks! That's a good distinction
Could you theoretically use it for e.g. DuckDB? (maybe not now, but with some work further down the line) What about a graph db like KuzuDB? or is it SQL only?
I think you could! Graft just provides transactions over sets of pages. As long as you can model your data in a compatible way it should work with Graft. A better question is how easy the system allows extensions to intercept filesystem operations. I'd prefer to avoid building a Fuse/NBD layer.
I've filed an issue for both:
Interesting approach. I've built my own thing and then rebuilt it last year for our use case. I'm using kotlin-js instead of regular js/typescript. It makes some of this stuff a bit easier to deal with.
Our system is map based; so we are dealing with a lot of map content that is updating often (e.g. location tracking).
v0 of our system was a failed attempt at using mongo realm before I joined. One of my first projects as the CTO of this company was shaking my head at that attempt and unceremoniously deleting it. It was moving GB of data around for no good reason (we only had a few hundred records at that point), was super flaky/buggy at that point, and I never liked mongo to begin with and this was just a mess that was never going to work. We actually triggered a few crash bugs in mongo cloud that caused data loss at some point. Probably because we were doing it wrong (somehow) but it made it clear to me that this was just wrong at many levels. The key problem of realm was that it was a product aimed at junior mobile developers with zero clue about databases. Not a great basis to start engineering a scalable, multi user system that needs to store a world full of data (literally, because geospatial).
We transitioned to a system that used a elasticsearch based system to query for objects to show on a map. Doing that all the time gets expensive so we quickly started thinking about caching objects locally. v1 one of that system served us for about two years and was based on a wasm build of sql lite together with some experimental sqldelight (a kotlin multiplatform framework). This worked surprisingly well given the alpha state of the ecosystem and libraries. But there are some unrelated gotchas when you want to package things up as a PWA, which requires being a bit strict on security model in the browser and conflicting requirements for OPFS (one of the options for local storage). Particularly Safari/IOS is a bit picky on this front. We got it working but it wasn't nice.
At some point I decided to try indexeddb and just get rid of a lot of complexity. IndexedDB is an absolutely horrible Javascript API piece of sh*. But with some kotlin coroutine wrappers, I got it to do what I wanted and unlike OPFS it just works pretty much in all browsers. Also it has similarly relaxed storage quota so you should be able to cram tens/hundreds of MB of data in there without issues (any more might work but is probably not a great idea for sync performance reasons). It's querying is much more limited. But it works for our mostly simple access pattern of getting and storing stuff by id only and maybe doing some things with timestamps, keyword columns, etc.
If somebody is interested, I put a gist here with the kotlin file that does all the interaction with indexed db: https://gist.github.com/jillesvangurp/c6923ac3c6f17fa36dd023...
This is part of another project that I'm working on that will be OSS (MIT license) at some point that I parked half a year ago. I built that first and then decided to lift the implementation and use it on my map product (closed source). Has some limitations. Transactional callback hell is a thing that I need to tackle at some point. Mostly you use it like a glorified Map<String, T> where T is anything that you can convert to/from json via kotlinx serialization.
We're currently working on adding geospatial filtering so we can prioritize the areas the user is using and delete area they are not using. We have millions of things world wide (too much to fetch) but typical usage focuses on a handful of local areas. So we don't need to fetch everything all the time and can get away with only fetching a few tens/hundreds of things. But we do want caching, personalization, and real time updates from others to be reflected. And possibly offline support later. So, the requirements around this are complicated.
We're actually deprioritizing local storage because after putting our API on a diet we don't actually fetch that much data without caching. A few KB on map reposition, typically; the map tiles are larger.
Offline is something that generates a lot of interest from customers but that's mostly because mobile networks suck in Germany.
[flagged]
[flagged]
In otherwords, "why are you a kid?"
Because of when they were born.
First link is x.com. Left.
My ideal version of this is simple: just define the queries you want (no matter how complex) and the you'll get exactly the data you need to fulfill those queries, no more, no less. And the cherry on top would be to have your queries update automatically with changes both locally and remote in close to real-time.
That's basically what we're doing with Triplit (https://triplit.dev), be it, not with SQL--which is a plus for most developers.
I heavily disagree with the notion that most developers would rather query with something that isn't SQL.
Funny, as Triplit front page shows a query much like SQL:
const deliveredMessagesQuery = client
.query("messages")
.Where("conversationId", "=", convoId)
.Order("created_at", "DESC")Comment was deleted :(
Exactly. Hard to improve on something so great.
We love a
``` select {what} from {where} left join {where} on {how} where {why} ```
A simple query, concisely answering every relevant question, while hiding all of the details of how any of it works. Beautiful.
Well yeah choosing what to query, a filter and an order is at the heart of all query-like things. Buy SQL specifically is a text language not a fluent api.
Probably the biggest upgrade SQL could have is putting the SELECT after the FROM, so autocomplete would work nicely.
> just define the queries you want (no matter how complex) and the you'll get exactly the data you need to fulfill those queries, no more, no less
So GraphQL?
Crafted by Rajat
Source Code