Merkle/Causal structure

[gritzko]

RON ops certainly have some redundancy. The op specifier consists of four UUIDs: type, object, event and location ids, which may be derived from each other in many cases.

Indeed, having the object id, we may learn the type; having the location id we may learn the object (as location ids are globally unique). This redundancy may lead to contradictions. Indeed, we may specify a wrong type for the object or a wrong object for the location (or vice versa).

While a detailed four-component specifier makes it easy to process an op, it also makes it difficult to handle a RON database as a Merkle structure.

My solution is to continue the Causal Tree line of thinking all the way forward. Namely, make object and type ids 100% derived. Use two versions of the protocol: Open RON (two-UUID specifier, event and ref) and Closed RON (four-UUID specifier for client's convenience). Having the full history of events, a peer/server may transitively close ops, deriving the closed form for the clients (who don't have the full history).

This way, the protocol is much less vulnerable to data inconsistencies. Also, the Merkle structure of the event graph becomes self- evident. Last but not least, a RON log gets a simpler key-value structure which is much easier to store and navigate.

Formally, the new rules are:

• a RON op has two UUIDs (own id and a reference) and zero or more value atoms (ints, UUIDs, strings and floats)
• both UUIDs are RON event UUIDs, essentially Lamport timestamps
• the reference points to some past op of the same object, thus describing the new op's place of application;
• an op with a null reference is an object creation op; its value must mention the object's type (i.e. RDT UUID)
• an op with an empty value is an ack op, which is only significant in the context of the Causal/Merkle graph; it modifies no object.

This way, ops form an orderly tree. The existing types and algorithms need to be corrected in two cases (at least):

• lww could no longer mention the field name in the reference UUID
• rga remove op has to work differently (at the very least, it cannot have is value empty)

Otherwise, the overall structure of the protocol stays the same; all the reducer/RDT logic stays the same as reducers did not read type/object ids anyway. The existing grammar stays valid.

In a follow up, I'll describe how the Merkle tree is defined and used in this context.

[gritzko]

If it clarifies anything...

[abalandin]

@gritzko , seeing into the picture, not understand, why reference of 4+b operation points to 1+a (not 3+b) ?

[gritzko]

@abalandin For 4+b, blue arrow (same-origin implicit causality) goes to 3+b, while green arrow (reference UUID, explicit causality) goes to 1+a.

[gritzko]

@abalandin Ah, I see. One object's ops form a tree. That tree conveys the structure of the object and the causality of operations. For lww, both 1+a and 3+b may work.

[cblp]

having the object id, we may learn the type;

May, or may not. Learning the type involves need of some lookup. Instead, we can build a system where object ids are namespaced by type ids. I. e. objects

*lww #42
*rga #42

may be considered as two distinct valid objects. Then de facto the full object id will be a pair (type, object-id). This is possible in all cases since when we work with an object, we always know its type.

having the location id we may learn the object (as location ids are globally unique).

This is false for name-based UUIDs in *lww location.

This redundancy may lead to contradictions. Indeed, we may specify a wrong type for the object or a wrong object for the location (or vice versa).

No, if we account parts of an object as local to their object. So, if distinct objects have parts with the same local id, they are still located inside different objects. Hence, the global id of a specific part must simply include its object’s id. Incorporating type, as said above, the global is of an object part is a triple (type, object-id, location).

On the other hand, if we consider location-ids global and try to calculate object-ids from them, we have to build enormous tables of all parent-child UUID relations. But what problems does it solve?

What do you mean by vice versa in this case?

While a detailed four-component specifier makes it easy to process an op, it also makes it difficult to handle a RON database as a Merkle structure.

Why?

My solution...

But you haven’t described the problem.

[gritzko]

may be considered as two distinct valid objects. Then de facto the full object id will be a pair (type, object-id). This is possible in all cases since when we work with an object, we always know its type.

Two issues here: (1) keys become twice bigger (2) that contradicts the idea of a globally-unique identifier (even inside a database, it is scoped by the type). The open-RON version is mathematically more attractive: an UUID identifies the object, the event and the version of the object.

Given that I want to add hashes, UUID(type)+UUID(object)+UUID(version)+hash becomes way too heavy.

[gritzko]

This is false for name-based UUIDs in *lww location.

True. As is, lww can't work with open-RON. Need something like: *lww2 #obj @event :prev_event 'arbitrary field name' =42

[gritzko]

On the other hand, if we consider location-ids global and try to calculate object-ids from them, we have to build enormous tables of all parent-child UUID relations. But what problems does it solve?

True. My goal is to have a nice Merkle structure. For revision control and for decentralized Web, Merkle DAG is a must-have.

[cblp]

@gritzko

Need something like: *lww2 #obj @event :prev_event 'arbitrary field name' =42

In example, there are 2 different formats for lww ops. I see them as create-field and update-field. It is too complex. They may be converged into one

event	ref	value	comment
1+a	0	>lww	create object
2+a	1+a	'x' =1	update field 'x' of the object; will be dropped after reduce
3+b	1+a	'x' =2	update field 'x' of the object

This comment is a bit aside of the issue topic, but it is written as a proof that the idea may work.

[gritzko]

About a year ago, I had to introduce the formal grammar cause the thing had to work inside a database. Now, I am introducing a Merkle tree, so it becomes even more strict. Like, bitwise strict.

So, I am struggling with immutability right now. RON 2.0 is logically-immutable, but in fact ops change. Two key issues are:

1. chunk headers (these are quite random),
2. the ingenious rga optimization (collapsing rm ids into removed ops).

I think I mostly solved (1), not sure about (2)...

[gritzko]

How to deal with headers: equate an object-create operation and a state frame header. We can't discard that operation anyway. So, object creation is @time+author :lww ! and a state frame is

@time+author :lww !
@time1+author :time+author 'field' 'value'

Then, any header-less chunk counts as a patch. Separate ops go in chunks of their own. This way, we discard the chunk metadata (event id range), but it was not that useful anyway.

Now, we only use immutable ops as-is, no "synthesized" headers.

[gritzko]

Then, any header-less chunk counts as a patch.

A patch:

@time-author :lww !
@time2+author :time+author 'field' 'value'

This open-RON notation is mostly backwards-compatible (Except 2.0 uses 0 for the ref, here we use RDT id. Also we use a derived UUID for the patch header. From what I see, this breaks nothing.)

I think, I also have a solution for rga.

To summarize that, ref UUIDs are more strictly defined now, so we can build on them more easily. Ops are strictly immutable, form an orderly tree.

So far, I like 2.1.

[cblp]

The notation is backwards-compatible (except 2.0 uses 0 for the ref, here we use RDT id).

The notation is backwards-compatible, the RDT encoding is not.