tgk/quilt_proposal.edn

It's great that you've worked through how one might use something like CRDTs to represent and coordinate computation. :-D

You have the basic idea right. As you might expect, the details are very important.

I don't think explicitly representing wholesale views of the database is a worthwhile or practical approach, as I think you're implying here (or perhaps you don't mean to imply that each progression of state shown at each 'tick' of time is materialized). You want your data model to support very fine-grained changes, so that incremental replication can be efficient. The other side of that coin is that the same mechanisms that would allow such fine-grained changes will allow for fine-grained query mechanisms (as opposed to pushing decomposition of larger states into "application-level" manipulations of query results).

Keep in mind the commutative and associative constraints. The removal of element 0 in the integer-indexed sequence at tick 3 would not satisfy either condition. You can characterize sequences such that removals are commutative and associative, but the underlying data model has to be amenable to that; one approach in this area is treedoc, which you can read about here and here. (Quilt's approach is very similar, but different. :-P)

You have a good intuition of how one could use a shared replicated medium to coordinate computations. The query/results example is a fine sketch of a (probably) request/response interaction among different actors. Note that the ideal is that computations performed by actors are themselves idempotent, so it would hopefully be safe for multiple query processors to run the requested query and deliver results into the replicated state, with no ill effects (outside of resources involved). There are interesting questions about how one coordinates work (e.g. using constrained or weak consensus mechanisms to minimize or guarantee that a given computation is performed only once by one actor). I often refer people to tuple spaces as an interesting characterization of a work coordination mechanism; reconciling its semantics with CRDTs (using the latter as largely just a conveyance for the necessary consensus mechanism(s)) will be very interesting IMO.

You're absolutely right that there needs to be a stable, monotonically-increasing notion of time within the system, ideally that also captures causal relationships between different operations, "versions", etc (as you allude to w.r.t. vector clocks or similar). At the moment, splice (Quilt's CRDT impl) identifies "writes" (a unit of atomically-applied changes) with a tuple of [actor-id, monotonically-increasing-value]. This gives a total order over all writes on a per-actor basis, and a partial order over all writes globally. Essentially, naive vector clocks. (Optimizations TBD.) There are lots of other ways you could skin this, including not explicitly including such causal information in the user-visible data model at all; it's exposed in splice so that you can obtain a consistent snapshot of any point in "time" of the CRDT, as identified by a write id (this is analogous to e.g. obtaining a version of a Datomic database as of a particular transaction number/id, with the big caveat that Datomic's linearization guarantee means that transaction numbers are totally ordered, globally).

I hope the above helps. Again, thanks for taking the time to think about these things. I'm putting some final bits into the first three projects in Quilt now (license, publicly-reasonable READMEs, etc); hopefully what I have in mind will be even more clear once I push those. And, just P.S.: Quilt is being build using CRDTs, but they are strictly a means to an end, and hardly its fundamental objective. :-)

Thanks for all the feedback. It is extremely informative.

The explicit model of the entire database in my example is a bit misleading. Possibly an ordered list of available database transactions would make more sense (think Datomic). The important bit is that there is a shared knowledge of the data available. Actually responding to queries marked with a given transaction (or "version" of the database) does not need to look in the shared state. I'm pretty sure that's what you are suggesting in your response(?). Adding transactions is an add-only operation. For even more fine-grained queries, the version (sha or other) of the service intended to answer the query can be added to the request, along with the transaction. This should also help in defining idempotent operations.

I'll definitely look into the "only-once" aspect, but I don't really see it as a major problem for query-only services. Of course, you don't want it for other types of interaction with the world (fire missiles etc) but that part of the system could possibly be handled by some slower co-ordination service outside the core.

Once again, thanks for all the feedback. It's very refreshing to see a different take on co-ordination between processes. I'm very excited to see what shape splice will have.

Yup, pairing CRDTs with various sorts of consensus mechanisms with different guarantees is a thing, and is a must for enabling general-purpose distributed computation (including interacting with the "real world").

One quibble (sorry, can't help it :-P):

Local reads — including all sorts of possible query mechanisms — are a core part of the construction of CRDTs. They're entirely orthogonal to any update or write paths/mechanisms, and so are readily scalable and tolerant of e.g. isolation from peers to which you might otherwise replicate writes. There may very well be query services that you might interact with via a CRDT (especially if you characterize any transformation of the shared data as a query!), but queries over the CRDT's actual state (e.g. the sum example) should always be available locally.

Alright, thanks for clearing that up for me. I shan't disturb your quest further :-)

Not a disturbance at all. :-)