investigate sequence / text crdts #65
Comments
|
Perhaps with column wrapper functions like we discussed a while back for counter crdts? UPDATE tbl SET doc = text_crdt_update(text, position) WHERE id = 123; |
|
I like it. That should work well -- diamond types can operate without modification and the two functions act as the bridge between worlds. cc @josephg in case he's interested in the above proposed interface for diamond types over SQL. Note that the |
|
Yeah, I suspect the actual doc would be multiple text columns spread across multiple rows in its own table? My excitement is through the roof to see text-crdts in sqlite! |
|
If we don't target WASM I think adding diamond types will be easy. Targeting WASM makes everything harder since WASM binaries currently can not load other binaries (AFAIK) so we have to compile Rust code with C code. Maybe I'm worried about nothing and that is actually an easy thing to do? |
I have no idea at the moment. I know diamond types handles its own persistence. Maybe in some future iteration that persistence layer would be exposed as a virtual table or vfs? |
|
Hi! Diamond types author here. You'd need to specify whether your change is an insert or delete. And for deletes, storing the deleted content is optional. You'll probably also need some methods to sync changes with other peers. How does this work at the moment? Is there a set of methods for querying changes since some version? Is it table-specific?
Compiling rust code to a C library (either static or dynamic) is really easy. We just need to write a simple C wrapper API around diamond types with Adding this stuff will also mean you need a rust compiler to be able to compile the library. Thats one nice advantage about wasm - you can ship a compiled wasm file and it works everywhere.
Right now (v1.x) diamond types has its own encode function which packs the operations into a highly compact byte array. (And corresponding decode methods). Re-saving the entire oplog with each change isn't very efficient, and its something I'm fixing for diamond types 2.0. You can also encode partial subsections of the oplog into chunks on disk and join them back together again later if you want. But the changes are internally incredibly table-like either way. You could absolutely store them in a SQL table if you wanted - though size on disk would probably increase a bit. Or use diamond types but expose them via a virtual table. The log of text operations is one big append-only table with a handful of columns. A lot of the performance of diamond types comes from run-length encoding those changes everywhere, including in memory while we're working on things. On disk every column gets individually run-length encoded based on what will let us store it with the fewest bytes. This description got longer than I expected, but I just kept typing anyway because I'm in a documenting mood, and in case its interesting to people. I should put this write-up somewhere. But if you're interested, the operations look like this:
You can see the run-length encoding in the example above. Without it, every inserted or deleted character would need its own row in the table. On disk this is way more compact, but thats another story. There's not shown but implied autoindexing row ID in the above data. That counts from 0 at the first locally known change and goes up by 1 for each inserted or deleted character. (This ID is called a "local version" internally in diamond types). There's 2 more columns missing from the data above: Parents and Agent Assignment. Parents information describes when each change happened relative to other changes. Eg: (
And then the third piece of data is agent assignments. Each user agent generates for itself a unique agent ID (a string). Over the network, each change is identified by a unique So anyway, if you want to actually store all this stuff in a SQL table (or a couple of tables) or expose it via a virtual table let me know. There's probably some missing API methods to query all this stuff back out of diamond types. |
Super interesting. With it being structured data already I'm really fond of this idea. I'm not sure if a full vtab is needed for it, or just a set of functions at the column level (behind the functions operations on the underlying tables would be executed). I guess a full vtab could allow the user greater control of the underlying type... There is already a vtab for changesets on the LWW-registers, so (perhaps) ideally the diamond types (and other future CRDTs) changesets should be accessible and appliable through the same interface. What do you think @tantaman? |
|
We've (iver & myself) been discussing this a bunch offline and here is a summary of where we're at so far:
CREATE TABLE ytext (
doc_alias,
clock, client_alias, -- id
origin_clock, origin_alias, -- origin
right_origin_clock, right_origin_alias, -- rightOrigin
content,
length,
tail_clock AS (clock + length - 1),
PRIMARY KEY (client_alias, tail_clock)
);
CREATE UNIQUE INDEX ytext_tailclock ON ytext (client_alias, tail_clock);
CREATE INDEX ytext_origin ON ytext (origin_alias, origin_clock);
In the above table:
Given all the state updates are rows in a table, incremental updates to and merging of the doc becomes pretty efficient. Just an insert with an Next tricks are to:
I have some ideas on these but I need to iterate a bit more. |
|
Of course the other option for a yjs integration is to just save raw update blobs as the indexeddb integration does. Downsides of that are:
Although we could timestamp the received updates with the db's clock and integrate that. The only missing piece then is reconstructing the doc as a string in the db. This latter approach looks to be the route taken by the leveldb integration -- https://github.com/yjs/y-leveldb
We don't need |
|
Another interesting thing -- sqlite support incremental I/O against blob columns: https://www.sqlite.org/capi3ref.html#sqlite3_blob_open |
|
If you're interested, one alternative is to use a "CRDT-quality" version of fractional indices. Specifically, strings such that:
These will never be as storage-efficient as a dedicated list CRDT, but you can generate the strings in <100 LOC and put them in a "position" column that you ORDER BY. More info, log-growth prototype PS: Nice talk at lfw.dev! |
|
@mweidner037 I still haven't seen any fractional indexing string which didn't have interleaving problems.. Has that been solved? |
|
Yeah, it was also my impression that you couldn't fix the interleaving problem with fractional indexing. btw -- we have implemented fractional indexing in cr-sqlite. An overview of the feature here: https://www.youtube.com/watch?v=BghFgK6VJIE I'll take a look at the links you provided to see if there's a significant difference between the approaches. |
It should be non-interleaving in both directions. The total order is equivalent to a tree walk over a binary-ish tree; concurrently-inserted sequences end up in different subtrees, which don't interleave. You do pay for this with longer strings, though: "averaging" two neighboring strings adds a UID (~13 chars) instead of a single bit, except when the in-order optimization kicks in. |
We've found that you could use a RECURSIVE ORDER BY (https://www.sqlite.org/lang_with.html#hierarchical_query_examples) so each index only needs a reference to its parent instead of containing the full traversal of the tree. So length of the index becomes deterministic and not dependent on the depth of the tree. Basically what's going on here #65 (comment) |
|
@mweidner037 - reading through https://mattweidner.com/2022/10/21/basic-list-crdt.html#semantics
Any idea how long these strings end up getting in practice?
We could do something for client-server setups that give out short IDs for clients. E.g., some auto-increment number assigned to clients by the server. Another optimization may be to assign replicas short ids to use for that specific document when they join the document.
I really like this property. It makes it easy to represent a rich text doc to other parts of a system and also make integrations with rich text editors (e.g., lexical, prosemirror) easier. |
Stats for the long text trace used in crdt-benchmarks are here (edit: see newer numbers below). The average position length is 423 chars, which is awkwardly long :( For the first 1,000 ops, the average is 97 chars. Prefix compression would help a lot, but I don't think SQLite does that. For sending positions over the network, normal compression does help - the average compressed length is 148 bytes. Short IDs would indeed help too - currently, IDs are 8 random chars, and you pay that cost once per "node" (an average position has 29 nodes). I'll see if I can optimize these further.
One alternative would be to have database-internal positions that use RECURSIVE ORDER BY like above, plus functions to map those positions to lexicographically-sorted strings. The function would basically find the position's path in the underlying tree, then make a string out of the node IDs on that path. That way you don't pay the length cost for positions that are "at rest". |
I added some optimizations that make this much better (details):
If you assign short replica IDs as @tantaman suggested, the "rotating" stats should improve noticeably. Otherwise, I don't think I can improve this much more; does it seem good enough? |
|
I'll have a chance to get back to this at the end of the week. Will let you know then. btw, @mweidner037 - I got the impression during one reading that tombstones were not required in this approach but then, on another reading, that they are required. Can you help clear that up for me? Is there an approach with fractional indices that does not require tombstones for character removals? |
You don't need tombstones - just the positions of present characters. It's okay to call Each Fractional indexing in general also shouldn't need tombstones, except for the usual uniqueness issues. |
|
Makes sense and matches what I originally thought. The slide that confused me: https://docs.google.com/presentation/d/1u8bcvfEcJ2wseH3u4P8QAMabq5VZrPR-FX8VaIIkbFQ/edit#slide=id.g11737e0938d_0_338 I probably just didn't read the entire deck carefully enough. |
Ah yes, that's describing a different version of Plain Tree that does have tombstones. position-strings is more like this slide, except it does have the LtR optimizations (in a new way that avoids interleaving). The slides are a bit older than the blog post, so they omit the string implementation that I meant to link to. Sorry for the confusion! In general, for any tree-based list CRDT, you can choose if you want "no-tombstone mode" with longer positions (= whole paths in the tree), or "tombstone mode" with shorter positions (= pointers to nodes in the tree). The former lets you compare two positions directly, without consulting some external tree state; so position-strings (and fractional indexing) uses this mode. But tombstone mode is usually more memory-efficient, so that's what the slides recommend, and what libraries like Yjs do. |
|
I wonder if its possible to store an entire string of characters per position instead of just a single one @mweidner037? So inserting something within an existing node, would split that into two nodes, and insert a new text node between them. Split nodes would have to be sorted at the same position as they were before the split, while it still being possible to insert before, after or between them. This would also require extra CRDT logic at merge for concurrent splits, as well as some functionality a substring within a node. The advantage is a lot less metadata per character. |
My first impression is that it would be simpler to wrap a CRDT that does so internally, like the beginning of this thread discusses for diamond-types. I think it would be possible to re-implement that optimization within a database table (e.g. columns "position" and "substring", instead of "position" and "char"), but it could be hard to query. |
|
This is an interesting integration of yjs + sqlite -- https://github.com/samwillis/yjs-sqlite-test by @samwillis There look like a few issues with the linked project, however:
exciting though. |
|
I think I'll either go with:
or
unless @mweidner037 has come up with something else in the meantime. |
|
Elaborating on #65 (comment) , I think we can implement a variant of Fugue [1] that stores multiple chars per row. (Untested) Terminology
We store one sub-item per row: CREATE TABLE fugue(
itemId TEXT,
index INT,
content TEXT,
parentItemId TEXT,
parentIndex INT,
PRIMARY KEY(itemId, index),
FOREIGN KEY(parentItemId, parentIndex) REFERENCES fugue
);Tree OrderThe In other words, you sort items arbitrarily by their To create parents, you often need to "split" a sub-item into two sub-items. E.g., starting from the tree if someone types "you " between "Hey " and "there", then we split the "Hey there" sub-item into "Hey " and "there", and we use "Hey " as the new parent: Selecting the sub-items in sorted order should look something like this (cf.): WITH_RECURSIVE under_node(content,level,itemId,index) AS (
VALUES('Root',0,?,?)
UNION ALL
SELECT fugue.content, under_node.level+1, fugue.itemId, fugue.index
FROM fugue JOIN under_node ON fugue.parentItemId=under_node.itemId AND fugue.parentIndex = under_node.index
ORDER BY 2 DESC, fugue.itemID, fugue.index
)
SELECT content,itemId,index FROM under_node WHERE index != -1; -- index -1 explained belowInsertionsTo insert a new character, assume you know the There are a few cases:
MergingTo merge two tables (or process an update), you mostly need to take the union of their rows. However, you also need to "clean up" sub-items that got split. E.g., to process the "you " update above, a remote user needs to:
DeletionsThese should involve tombstones; otherwise I haven't thought it through. [1] https://arxiv.org/abs/2305.00583 . The alg described here is more similar to Braid's Sync9 list CRDT, which is apparently order-equivalent to Fugue. |
|
@mweidner037 - The rules for extending an item make sense to me. I'm a bit unsure about item splitting. Wouldn't splitting an item require re-parenting its children? If we have the string |
|
@tantaman If we start with sub-item Then Here we used the facts that:
|
|
@mweidner037 - Got it. The last case I'm still fuzzy on is an item being split concurrently by many peers. Is this an accurate description of the cleanup algorithm? Peer 1: Peer 2: Peer 3: On merge we union: Then "clean up" would be:
Example: Pass 1 of cleanup: Pass 2 of cleanup: etc. I'm excited for this approach. Seems like it could work well & without crazy storage requirements. |
|
@tantaman Yes, that looks correct. When you do the union, I believe it is okay to skip duplicate primary keys |
|
On a separate topic, @mweidner037, are you aware of the work on Portals in Sync9? It is a new concept to support the notion of replacing text. The really awesome thing is that it seems to solve the rich text problem as rich text edits become replace operations. E.g., The idea is that a portal represents a view into a document at a prior version so you can get the exact text the user intended to move or replace. It is presented in more detail here: https://braid.org/meeting-62 |
Thanks, I had not seen these before. Portals look interesting, though they might be hard to implement efficiently - you may need to track versions/concurrency with vector clocks, which get large quickly. |
|
What do you think about deletes? Seems like there's two ways:
The latter seems nice given previously inserted characters can fully be scrubbed out of the document. |
|
Yes, I think you can make deletes work using "tombstone sub-items", represented as rows with content=NULL (or similar).
|
|
Thanks @mweidner037. This has been super helpful. |
|
Closing this as I think enough research has been done and I'm ready to start implementing -- #323 |
Is it possible to stream patches (keystrokes even) to a column behind which is the sequence crdt? https://docs.rs/diamond-types/latest/diamond_types/
The text was updated successfully, but these errors were encountered: