Hi! Diamond types author here.

UPDATE tbl SET doc = text_crdt_update(text, position) WHERE id = 123;

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?

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?

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 #[no_mangle] and friends. And it shouldn't take more than an hour or two to get something simple working. This is the WASM API at the moment, which I'd base the API on. Here's some documentation on how to make a rust project into a C library. And there's even projects like cbindgen which can automatically generate C headers. Probably take me a couple hours to get something like that working if I do it, but if someone else wants to take a stab at it go for it!

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.

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?

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:

$ dt log benchmark_data/node_nodecc.dt --json
...
{"kind":"Ins","start":2360,"end":2361,"fwd":true,"content":"="}
{"kind":"Ins","start":2362,"end":2371,"fwd":true,"content":"args[0];\n"}
{"kind":"Ins","start":2373,"end":2376,"fwd":true,"content":"Str"}
{"kind":"Ins","start":2377,"end":2383,"fwd":true,"content":"ng::Ut"}
{"kind":"Ins","start":2384,"end":2390,"fwd":true,"content":"8Value"}
{"kind":"Ins","start":2391,"end":2396,"fwd":true,"content":"value"}
{"kind":"Ins","start":2397,"end":2406,"fwd":true,"content":"arg);\n\n  "}
{"kind":"Del","start":2411,"end":2413,"fwd":true}
{"kind":"Ins","start":2411,"end":2426,"fwd":true,"content":"f(\"%s\\n\", *valu"}
{"kind":"Ins","start":2427,"end":2436,"fwd":true,"content":");\n  fflu"}
{"kind":"Ins","start":2437,"end":2443,"fwd":true,"content":"h(stdo"}
{"kind":"Del","start":2444,"end":2445,"fwd":true}
{"kind":"Ins","start":2445,"end":2449,"fwd":true,"content":");\n\n"}
{"kind":"Del","start":2450,"end":2452,"fwd":true}
{"kind":"Del","start":2451,"end":2452,"fwd":true}
{"kind":"Del","start":2453,"end":2454,"fwd":true}

kind = Delete or Insert
start/end describe where in the document the characters were inserted / deleted. Half open range.
fwd is an optimization trick. If the user backspaces a run of characters, we mark those changes as fwd: false and we can still RLE the edits. Don't worry about it.
content is the inserted content. (Deleted content can also be saved if you want to)

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:

$ dt log benchmark_data/node_nodecc.dt --json --history
{"span":[0,63597],"parents":[]}
{"span":[63597,68772],"parents":[63276]}
{"span":[68772,68916],"parents":[63596,68771]}
{"span":[68916,79737],"parents":[68771]}
{"span":[79737,79868],"parents":[68915,79736]}
{"span":[79868,79999],"parents":[79736]}
{"span":[79999,80299],"parents":[79867,79998]}
...

(span here is the missing ID column from above).

Parents work the same as the parents of a git commit. The only difference is that I'm just using (local) autoincrementing integers instead of git SHAs to name each change, so I can run-length encode better. You can turn this sort of data into a DAG and for super complex data sets you can end up with something like this.

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 (agentId, sequence number) pair. Eg (seph,0). The last piece of data associates local versions with agent+seq pairs. Its used when peers communicate they can figure out what changes they need to send. And to deduplicate received changes. And its used for tie breaking when users concurrently insert at the same place in the document, at the same time.

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.

Uh oh!

investigate sequence / text crdts #65

Description

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions