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].
> 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"?
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. :)
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.
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.?
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.
> 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
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. :)
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 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!
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?
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.
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 :)
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.
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?
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.
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?
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'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].
[1]: https://bugbash.antithesis.com/
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"?
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)
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.
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.
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.?
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.
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.
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. :)
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'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.
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!
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...
And yea, I fell pretty far down the "Leap" rabbit hole. It's a fun one :)
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://rxdb.info
- https://www.powersync.com
- https://electric-sql.com
- https://dexie.org
https://localfirstweb.dev is a good link too.
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.
Beta ETA?
Looks really good, great work!
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?
That's basically what we're doing with Triplit (https://triplit.dev), be it, not with SQL--which is a plus for most developers.