Act on the latest version of the resource state

[michielbdejong]

Just had a chat about this with @acoburn, I think there are a number of points where a Solid server should support concurrency of http requests. A naive but valid way of dealing with this is to queue up all http requests in a single queue at the gate, and only ever execute one at a time, to completion, before starting the next one. But of course that would be a bottleneck and most server implementations will probably want to do better than that. So another model is to have one such queue per resource, instead of a single queue for the whole server. Or maybe one queue for each pod / user.

One restriction we should probably specify is that the server should only report success if the authoritative state of a resource was deterministically updated. It doesn't mean that all cached copies have to be updated before the write request is completed, but they do need to update to the new authoritative state eventually.

Reads are pretty easy, they don't necessarily need to report the latest state of the server, as long as they report a state that is consistent with itself. So for instance if I PUT /foo, then PUT /bar, then GET /, then <> ldp:contains </foo> is ok even though it's outdated, but <> ldp:contains </bar> is incorrect.

There needs to be a single queue of operations that affect a given container, they can be:

• add/remove a subcontainer
• add/remove a non-container

There are also requests that affect more than one resource. I think with the deprecation of globbing and the rejection of recursive deletes, the remaining ones will be:

• a PUT or DELETE affects both the resource itself and the container that contains it
• a POST affects both the container itself and the resource that is created.
• a PUT or POST to a non-existing resource will create all containers up to whatever parent does exist (mkdir-p)
• a container DELETE which may conflict with a concurrent POST or a PUT

Note that mkdir-p might also conflict with PUT of a non-container.

For the same non-container resource, if PUT, PATCH, and DELETE requests can be handled concurrently, instead of having to handle those one-by-one from a single-file queue, that could greatly increase performance.

I think it's inevitable to introduce some concept of subtree locking to support all of this including mkdir-p. If we drop the requirement for server-side mkdir-p (move it to the client, basically), then concurrency becomes easier, and except for container delete (see below) you only ever have to lock either one resource, or two: a resource and the containment triple for it, in the container that directly contains it. Note that you don't have to lock the whole container, just the triple that pertains to the contained resource in question.

This leads to an attractive property: if two requests affect a different URL, then they can be handled concurrently without coordination.

For container deletion, we could say:
If the DELETE of a container starts at a where that container is not empty, then the server may refuse the request.

If the DELETE of a container starts at a where that container is empty, then if any concurrent requests create resource that make it non-empty, then the delete should overrule those new creations, and in that sense act as a recursive delete for those resources, without taking into account any ACL restrictions. So basically if a POST and a DELETE happen concurrently, both may report success to the client, but the DELETE will prevail.

Or if we don't make those two changes to the spec (removing the mkdir-p feature and relaxing the situation around container-deletion) then we need to state in the implementation guide that all POST, PUT and DELETE requests should lock not only the resource but also the containment triples they affect.

@acoburn I think that covers all the points of concurrency in the current spec, did I miss anything?

[acoburn]

I would just add that concurrency over a distributed system leads to a lot of complexity, and one should be very careful about mandating certain specific behaviors in normative text. For example:

Reads are pretty easy, they don't necessarily need to report the latest state of the server, as long as they report a state that is consistent with itself. So for instance if I PUT /foo, then PUT /bar, then GET /, then <> ldp:contains is ok even though it's outdated, but <> ldp:contains is incorrect.

I would not agree with that assertion. A server could implement the propagation of containment triples asynchronously and in an async system, strict ordering is not guaranteed (I wrote such a system a while ago). So it would be entirely possible to see <> ldp:contains </bar> in the container before <> ldp:contains </foo> appears.

I think it's inevitable to introduce some concept of subtree locking to support all of this including mkdir-p

Mandating locking at the specification level would be highly problematic for any sort of distributed/high-performance system.

[kjetilk]

This sounds like a good topic for a master's or a ph.d. paper to me...

[michielbdejong]

Mandating locking at the specification level would be highly problematic for any sort of distributed/high-performance system.

Well, not mandating it directly, but would you agree with the statements that

1. we're currently mandating mkdir-p (unless there has been a decision to deprecate that?) and
2. that probably requires some sort of semaphores or locking right?

[dmitrizagidulin]

@michielbdejong I'm probably missing something obvious - why does mkdir -p require locking?

[michielbdejong]

propagation of containment triples asynchronously

interesting, ok I can go with that. especially if all the containers exist, it's easy. The only difficulty then is probably container deletion. What if you simultaneously delete an empty container, and also add an item into it.

[dmitrizagidulin]

@michielbdejong

What if you simultaneously delete an empty container, and also add an item into it.

So that question often comes up in any sort of eventual consistency conflict resolution system (like CRDTs). And basically, the policy there is - your conflict resolution strategy explicitly states what happens. Like, "if a delete and an add conflict, the add wins". (which results in less information loss than the other way around, incidentally.)

[michielbdejong]

@dmitrizagidulin suppose on an empty domain, you simultaneously add /foo and /foo/bar.

• The server creates a resource /foo
• and a resource called /foo/bar,
• and then queues an asynchronous task to:
• 1. create a container /foo/ if none exists yet
• 2. add a containment triple saying /foo/ contains /foo/bar
• By the time that asynchronous task gets executed, it's already impossible, because /foo is already a non-container resource.
• 💥

[acoburn]

we're currently mandating mkdir-p

In the 0.8 solid spec document perhaps, but it is an open question whether such behavior would be required for the 1.0 document. See #68

that probably requires some sort of semaphores or locking right?

Not necessarily. The basic problem here is that mkdir -p is not RESTful (multiple resources are changed with a single operation), and so the question relates to atomicity. Some backend systems can guarantee that level of atomicity across multiple resources (e.g. a database transaction). Other systems simply do not have that feature, so then the issue becomes one of conflict resolution

Regarding #91 (comment), there are ways to handle that situation that does not lead to errors. E.g. if /foo is not an LDP-C, then ipso facto it cannot contain ldp:contains triples.

[michielbdejong]

"if a delete and an add conflict, the add wins"

OK but what if you do POST /foo/ and DELETE /foo/ simultaneously, and both requests had an If-Match header for the same ETag. Then you would be seen to execute the POST in violation of that condition. That's not the behaviour I would hope to see from a server.

[michielbdejong]

Wait, wow, so it sounds like you're both saying that we should allow servers to basically report success on all requests, even if some of them end up just not having been executed in the post-hoc view. I had always thought we wanted to be much stricter than that.

[acoburn]

Best case scenario: if the persistence layer handles conflict resolution (there are many potential mechanisms for this), then the first request would succeed and the second would fail.

Worst case scenario: you end up with a disconnected graph.

[michielbdejong]

Oh wow, that's definitely a much lower bar than the one I would like us to set. Good that we're having this discussion, we should at least make it explicit in the documentation whether clients can expect any kind of guarantee or whether it's all on a "best effort" basis.

To make it specific, let's imagine:

• server is empty except for one empty BasicContainer at /foo/, whose ETag is "1".
• Client 1 sends DELETE /foo/ with If-Match: "1"
• Client 2 sends POST /foo/ with If-Match: "1"

We could allow the server to create two contradicting universes, in which both requests succeed, and then later we silently destroy one of those universes. So both would get a 2xx response, but then when they check later, they may find out that actually maybe their operation didn't have the desired effect at all. So despite the 2xx response that was given at the time, the change was later deselected. I call that erasing things from the history books, and I think a Solid server should not be allowed to do it.

[michielbdejong]

the first request would succeed and the second would fail.

That scenario is fine, and I think it's what the spec should demand.

[dmitrizagidulin]

@michielbdejong This argument is essentially "do we require strong consistency" in our servers (which would dictate some very specific architectural choices), or do we allow eventual consistency.
(And I definitely think it should be the latter.)

[michielbdejong]

but at least leave the requests pending until we know whether they succeeded, right?