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.
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].
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
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).
Some simple examples: https://www.caktusgroup.com/blog/2018/03/19/when-clean-merge...
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.
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.
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.
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. :)
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.
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 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)
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.
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.
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.
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.
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 :)
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.
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 :)
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"?
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.
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.
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.
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 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.
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?
The talk contains a lot more details on how the transactional and replication layers of Graft work.
Beta ETA?
> 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...
> 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.
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.
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.
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!
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
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".
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!
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! :)
Much appreciated, I'll keep you informed :)
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.
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!
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?
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.
That's basically what we're doing with Triplit (https://triplit.dev), be it, not with SQL--which is a plus for most developers.
const deliveredMessagesQuery = client
.query("messages")
.Where("conversationId", "=", convoId)
.Order("created_at", "DESC")So GraphQL?