1 of 17

Live Local-First RDF Graph Sharing

Application Independence in the Age of CRDTs

2 of 17

[Go to js.m-ld.org. The screenshot is the top sandbox, popped-out to a window]

Here we are in a super-simple demo app using m-ld, in a Javascript browser sandbox environment. The first thing to note is that m-ld is a just an embedded library, in this case simply imported into the app code. Its purpose is to allow the app code to operate on a dataset, called a 'domain'—in client app-development parlance, it's the Model out of MVC—and to have that domain 'shared' between multiple remote instances of the app.

There is no server code for this demo, except for dumb app-independent message-passing (because that's not a standard part of the Web yet, we've created a service for this called the m-ld Gateway). Just as an aside, we may already note a parallel with Solid, which also has an app-independent service. But here, the data itself is not stored anywhere other than the client. The Gateway does not store any data unless you want it to.

This 'app' does almost nothing other than establish a new domain, by calling the m-ld clone function and passing the genesis flag. The word 'clone' deliberately suggests that the domain will be replicated to other 'clones' which are local to the other app instances.

Then, the app listens to changes in the domain via the follow method. Again, this suggests the fundamental reactive pattern for interaction with a m-ld domain. Note that this pattern is common to most modern MVC frameworks and libraries like React; with the exception that m-ld domains stay in sync automatically, with no client-server synchronization to be coded by the application developer.

3 of 17

[The screenshot is the second sandbox on js.m-ld.org, also popped-out]

Once we have copied the unique domain name, we can shift our attention to another app which is going to share the domain information. Immediately we can see that this a different app. In this case that difference is trivially motivated by the needs of the demo; but we're already getting a hint at application independence.

You can see from the code that this app again uses clone to replicate the domain, this time without the genesis flag. In contrast to the previous app, here we provide some interaction by allowing users to add their name to the domain. When we do so, we note that the reactive code in the first app sees the change and welcomes us.

So far, what we're looking at is a simple local-first application. This is an emerging pattern, in which apps are developed and deployed with the emphasis on utilising client compute, while still providing a collaborative 'multiplayer' experience. The advantages of this approach can also include the ability to work offline, and to maintain ownership of data even when services fail or become untenable. It has arisen enabled by a new category of replicated data types with the property of convergence: all replicas of the data are guaranteed to end up with the same data if everyone stops typing.

A m-ld domain is one of these; a Conflict-free Replicated Data Type (CRDT). As we'll see though, CRDTs may always converge, but they don't always converge on what we intuitively expect.

So let's drive towards how m-ld is different. You may have noticed some strange keywords arising in the code, starting with @; a pattern you may recognise from JSON-LD. This is indicative of m-ld's JSON-LD-based API. We can look more closely at that API using a generic tool called the m-ld Playground.

[Click Playground link]

4 of 17

We can connect the playground to an existing domain that uses the m-ld Gateway (in this case, we're using a public account; user authorisation is something you can add for private domains).

The Data box on the left shows what's inside the domain. You may have noticed in the app code the entered name was added as a Javascript object with a name property, and we can see that here, along with a generated identity for the object. This is JSON-LD, which is itself a serialisation format of RDF. A m-ld domain contains an RDF Graph.

With the Transact box on the right we can add another name to the domain. Let's add Elf. Note again that the playground is generic; it has no idea what the expected data schema might be (the box was pre-populated by the URL). OK, so now we have both George and Elf, and you can see again that Elf's object has been given a generated identity.

5 of 17

Let's try and change Elf's name. So instead of adding a new named object, what we want to do is change the name property of the existing object. Intuitively, we might do something like this: provide the identity of the object in the Transact box, so that m-ld knows we're talking about something that already exists.

Oh. Perhaps this is unexpected. What's happened is that "Pavlik" has been added to the name property, which is now an array. If you're familiar with JSON-LD, this might not be too surprising. What we've done is added a new edge to the graph, from the identity, through the name property, and to the new literal value; and this is how JSON-LD canonically represents that.

However, non-RDF folks might not like this behaviour. Fields in objects unexpectedly turning into arrays is going to complicate our app code.

6 of 17

So let's see how to get what we really wanted: to replace the name. Here m-ld adopts a new syntax, which is heavily inspired by JSON-LD (it's almost a superset), but is actually more like a JSON representation of SPARQL (RDF's query language).

We use these keywords @delete and @insert to express that we want to remove the previous value and replace it with a new one. You'll see that we don't actually have to specify the value to replace; we can use a placeholder variable, in this case a plain ? (we can also name the variable, like SPARQL, if we want to re-use the captured value in the update). This is helpful in our demo here because we're actually replacing both of the previous values arising from the last step.

We now have our wanted effect. Great. We can code our application using these deletes and inserts such that no ugly arrays arise that we have to worry about. Right?

Nope. Actually, arrays can still arise. The reason is that other clones of this domain exist, and can be operated on concurrently with our update. Someone else might be replacing Elf's name—say, to "Pavlik, Elf"—at exactly the same time as we are, and we don't know whose update should 'win'. In that case, m-ld will still, by default, expand the property to an array of both "Elf Pavlik" and "Pavlik, Elf".

This scenario is commonly referred to as a conflict. In a database-backed system, the two updates will get serialised one after the other; or, using locks, it could be that the conflict couldn't arise in the first place. In m-ld, like many local-first technologies, we actually 'commit' all local updates immediately. We call this live-by-default.

7 of 17

Live-by-default means that app developers get a choice over how they want concurrency to manifest. In this case, exposing a conflict through an array is a way to signal it, which might be exactly what you want: the application can show the conflict to the user. But this is a double-edged sword: as we already noted, it's kind of awkward. And there are other cases in which this awkwardness is actually very hard to code around. An example is RDF collections. While the CRDT in m-ld ensures everyone always gets the same data, concurrent writing of RDF Lists results in a hilarious range of incoherent results: lists with loops, branches, and orphan list items.

So, how do we ensure not only that data converges, but that is converges to something coherent according to the rules of the application?

One approach could be to add some logic in the app to handle unexpected data. In our case, we could have something that looks at the property, and when it sees an array, it picks one of the values—say, the first one in a lexical ordering—to display to the user.

But this creates a big problem with application independence. Apps could choose differently! such that what gets displayed to one user is different to what is displayed to another user, even after all the clones have converged.

Alternatively, we could have the choice be somehow embedded in the data type. So far I've said that a m-ld domain is one CRDT: a single data type, a graph. This is true, but CRDTs can be compositional: you can often embed one CRDT in another. In m-ld, this is supported, and we'll see an example in a minute. But I want to take one step even further.

Another part of the RDF ecosystem is Shapes; a way to declare constraints on RDF graphs. In m-ld, we've adopted Shapes not only as a way of validating a graph, but also as a way to declare concurrency behaviour. I'll use a template to declare a shape in our domain here. Don't worry about all the details, but you can see that we're using the SHACL vocabulary to declare that the name property should only have one value. And most importantly, we're not doing this using some configuration side-channel, but we're doing directly in the data itself, using the Transact box.

8 of 17

9 of 17

If we use the delete/insert syntax like before, m-ld is okay with the update. This difference here is that the data will now never contain an array, even if there's a 'conflict'. By declaring the shape constraint, the extension has made the name property into a register CRDT. (As it happens, the current implementation will pick the highest lexical value; but importantly, it will pick the same value on all clones.)

So this is the approach that m-ld takes: you declare the constraints on the data in the data itself. Thus, any app that loads up this domain will get the same behaviour out of m-ld; and application independence is preserved. The declaration can also be queried by the app and used to drive user interface behaviour. For example, a number of folks are using SHACL to build forms dynamically.

Another key principle of RDF, shred with with Web in general, is the concept of decentralized extensibility: no-one has authority to say which extensions are allowed and which are not. You can completely recreate a m-ld domain, including its concurrency behaviour, from looking at the data in it. So if the code for m-ld disappears, or any of its extensions, or if someone comes up with a much better way to implement its behaviour, there is no lock-in.

10 of 17

Let's look at a another example of an embedded CRDT in m-ld, this time, for collaborative text. The pick-one algorithm used for our name property would not be suitable for a document; every time two users made a concurrent change, one of them would have their change disappear entirely.

In the code on the left, we can see another way to declare a data constraint, which is much less verbose than the SHACL constraint we saw before. This is just sugar, made available by the extension. Here, we're declaring that the text property should behave like a text CRDT, which is to say, it should allow concurrent text editing without losing anyone's intended character changes. Note that even though we're importing the extension code directly here, other apps can load the extension based on the declared data type.

11 of 17

12 of 17

13 of 17

application independence

works when a standard exists

markdown, iCalendar, GeoJSON, most program code
differentiation with extensions
most apps don't care. They want lock-in

RDF allows decentralised extensibility with vocabularies

apps can change behaviour based on what they understand
works for CRDTs too
… but security, fault tolerance…

So, let's zoom out to think about application independence. Experience over the history of software suggests that it has arisen before, when its cost has been outweighed by its value, but that condition has been far from universal. The use of standards primarily helps with interoperability, so that apps can communicate; but very rarely is it possible for users to choose their own tools and and still be able to collaborate. Strangely enough, one place is which this has been achieved is in coding itself: it's often true that programmers on a project can use different IDEs running on different operating systems. However even this doesn't extend to live multiplayer collaboration, yet.

RDF and its ecosystem has always had at its heart the use of "vocabularies of known IRIs, given meanings by specifications or conventions". This is a way to provide decentralised extensibility to not only the meaning of the data but also the expected behaviour of apps that interact with it. The "open-world" model, however, complicates or even precludes apps that are hard-coded to certain structures in the data (that being the most common kind of app!). Shapes constraint languages are intended to bridge that gap, and today we've seen a m-ld extension that makes use of SHACL to constrain concurrent behaviours.

14 of 17

m-ld and Solid

application independence in principle

application & constraint agnostic service

data metamodel: RDF

Solid is adopting the RDF approach too, and is therefore complementary; but it's also seeing some of the same challenges. In particular, how to ensure that apps actually obey the contract explicit or implicit in the data?

In m-ld, every clone is a peer, and the onus is therefore on a local clone engine to audit the contributions of others (and we've looked deeply into how this applies to security constraints, for example); but this approach means a lot of duplicated effort, and indeed may not even be computationally feasible in the general case.

In Solid, the server is intentionally agnostic to the data rules—it will accept anything that an authorised client gives it, even if it makes no sense. I'm looking forward to continuing to explore this topic in collaboration with my friends in the Solid community.

15 of 17

m-ld and Solid

16 of 17

m-ld internals

Baseline concurrency is by graph CRDT (SU-Set)

tombstone-free

Journaling for peer recovery

fuses sequential edits from the same peer

Supports embedded CRDT extensions

as graph overlays or as atomic leaf nodes

Supports coordinated transactions

for e.g. schema changes & security

17 of 17

m-ld status

make it work

make it right

make it fast