Version syntax (from merge-type and patch types thread)

[Michael Toomim]

I'm starting a new thread for this Version syntax discussion.

Seph:

You've raised some interesting problems here which are worth addressing (And I've changed the title to hopefully bump this into a separate thread).

- Does the version field in a patch specify the "operation version" or "resultant version" after the client has applied a change? These can be different - eg, with vector clocks the document version might be {a:1, b:2, c:3}. My operation version is {c:4}. Should the patch say {a:1, b:2, c:4} or just {c:4} ?

The Braid specification is fine either way. It only requires that each version uniquely references a particular state of the resource, at a unique point in time, and that when you follow versions back through their parents, you get a DAG that says which versions were known to occur before other versions:

   Each version string must be unique, to differentiate any two
   points in time.

   ...<snip>...

   The full graph of parents forms a Directed Acyclic Graph (DAG),
   representing the known partial order of all versions.  A version A is
   known to have occurred before a version B if and only if A is an
   ancestor of B in the partial order.

So that's all that's required for the Braid spec, and all that is needed to synchronize perfectly. But you might be asking more about the tradeoffs in a particular implementation, so let's look at those.

First, rather than calling these "Operation Version" and "Resultant Version", I'd propose we use the conventional academic terms for these things:

- {c:4} is a "Lamport Timestamp"
- {a:1, b:2, c:4} is a "Vector Clock"

Reference: https://www.cs.rutgers.edu/~pxk/417/notes/logical-clocks.html

The typical advantage of a Vector Clock is that you can compare any two versions' partial order just by checking each entry in the clock. You don't need to look at the DAG! The clocks themselves carry enough info to imply a time DAG.

This means that the information in a Vector Clock is redundant with the "Parents:" field. You could recompute the parents for every version in time if you know that every version is a vector clock.

However, the Vector Clock itself takes up space proportional to O(num_peers). This kinda sucks, because a Lamport Timestamp only takes up O(1) space. And you can encode the same information using Lamport Timestamps by just including the preceding versions in the Parents: field. Then you get the whole DAG.

So if you know for a fact that you have a small number of peers, then you might find it handy to use Vector Clocks, and have a unified representation to compare any two versions. However, if you are interested in scaling your network to a large number of editing peers, then it behooves you to use just Lamport Timestamps for each version ID, and encode the DAG directly using the Parents: field.

The Academic work discussing this tradeoff is called Hash Histories:

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.124.9074

ByungHoon Kang, Robert Wilensky, and John Kubiatowicz. The Hash History Approach for Reconciling Mutual Inconsistency. ICDCS, pp. 670-677, IEEE Computer Society, 2003.

...because it applies not just to Lamport Timestamps, but also Hashes, and in fact any unique identifier.

This availability of improved performance (in situations of many peers) is a big reason that the Braid spec allows changes to be expressed as a Time DAG instead of just Vector Clocks.

If we're sending operation versions (which was my understanding from our conversation earlier on discord):

- How does a client compare {c:4} with the "up to date version" field named at the start of the subscription stream, in the spec? Surely that up to date version must say {a:1, b:2, c:4} - but in that case, how will a client know that they're up to date? (They can't directly compare {c:4} with {a:1,b:2,c:4} if those strings are supposed to be opaque)

Can you clarify what you mean by "up to date version"? Are you referring to this? https://github.com/braid-work/braid-spec/pull/79/files

Or are you referring to the information provided in the "Parents:" field for a GET?

- Actually how does the client even recieve a snapshot at {a:1,b:2,c:3} ? What does the version header in the first message in the subscription stream say? I'd love to see a worked example of this!

Are you using Lamport Timestamps in this example, or Vector Clocks?

If Lamport Timestamps, you'd do:

          GET /foo
          Version: "{a: 1}"

...or whatever the timestamp is for the editor who created that version.

If Vector Clock, you'd do:

          GET /foo
          Version: "{a:1,b:2,c:3}"

- This might be resolved in the content-ranges draft, but lets say I have versions like this:

 {a:0,b:0}

  /    \

{a:1}  {b:1}

What content-ranges draft are you referring to? The range-patch draft?

I subscribe. I get a copy of the document at version {a:1,b:0}. Then the server sends me the {b:1} operation with an insert. Is the insert location in the {b:1} patch specified with respect to {a:0,b:0} (as it was when the operation was created) or with respect to {a:1,b:0} (ie, transformed to meet the client's expected world)?

The former. Is the braid-http spec not clear about this?

If its with respect to {a:0,b:0}, how does the client interpret the contents and content-range locations, since presumably they're missing an explicit copy of the {b:1} patch?

They interpret them with respect to {a:0,b:0}. Its up to the client to merge that change with the {b:1} patch. It can use a CRDT or OT to do that.

Maybe, can you fill out this example so I can understand?

    HTTP/1.1 209 Subscription

    cache-control: no-cache

    connection: keep-alive

    content-type: application/automerge

    Transfer-Encoding: chunked

    version: "a:0,b:0"

    content-length: xxx

    version: "???" <-- What value does this contain?

    <<document at {a:1, b:0}>>

----(later)----

    content-length: xxx

    version: "b:0"

    parents: "a:0", "b:0" <-- How should the client interpret this? Its never seen "a:0" or "b:0"

    content-range: json=.messages[1:1] <-- What are these indexes relative to?

    <<patch content>> <-- Is this content not transformed by the server? Even when doing OT?

I'm not sure what you are trying to do, there. I see three ways of representing versions here:

• "a:0,b:0"
• "{a:0, b:0}"
• "a:0"

A resource needs to be consistent in how it represents versions. Each version is a unique string, that uniquely identifies a point in time in the Time DAG. When you reference a version in the Parents: field, that version needs to have been defined somewhere in a Version: field, so you need to use the same representation of versions throughout the resource.

[Seph Gentle]

I'm going to go through some points in more detail later; but I want to capture some thoughts right now. Mike and I just had a chat talking through some of this stuff - I'm going to imperfectly summarize some things from my perspective.

One of the differences in mental model is this (Sorry if I don't capture this accurately Mike - please correct!)

Seph:

There's two kinds of data - operations and documents. The idea of a 'version' means something slightly different in both cases:

- A "document version" always uniquely identifies a state that a document is in. The same document version implies identical document contents.

- There's some freedom in how an operation is applied. Eg the {z:1} operation could move document {a:0,z:0} to {a:0,z:1} or it could move {a:0,b:0,c:1000,z:0} to {a:0,b:0,c:1000,z:1}

- Yjs uses a (comparatively) very large document version which also embeds information about all the characters which have been deleted. But an operation/event is still named with just the (agentid,seq) pair (eg {b:1} in this example).

- So I see these as two different data types, which everybody tries to conflate together - to our ruin.

- The "up to date" header names a document version, not an operation version - and thats really confusing (its managed to confuse us, and we're experts in the field! Nobody else has a hope.)

Mike:

- When an operation specifies a version, that version field names the resulting document version after the operation has been applied

- This works everywhere *except for merges* which we have to think about using a different scheme. See demo: https://braid.news/demo/interact (sorry there was another link mike - I lost it). So in this demo the grey circles are like implicit, local only merge commits. They're never sent over the network, and their versions are the union of all the direct arrows going in.

I don't see merges as special like that (just follow the semantics of the underlying system to update the document and update the version). Mike doesn't see document versions as distinct from operation versions - but specialcases merges, because you have to carve that out if you do that.

Anyway, I'm still not sure we're on the same page. I'd love to see an example of what yjs could look like embedded into braid. I hear Greg is working on it here - https://braid.news/yjs - though I'd like to see a longer worked example at some point.

-Seph

--

You received this message because you are subscribed to the Google Groups "Braid" group.

To unsubscribe from this group and stop receiving emails from it, send an email to braid-http+...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/braid-http/e6ba81c5-0e28-ec5a-9b3e-3b41b78868bd%40gmail.com.

[Michael Toomim]

Seph:

I don't see merges as special like that (just follow the semantics of the underlying system to update the document and update the version). Mike doesn't see document versions as distinct from operation versions - but specialcases merges, because you have to carve that out if you do that.

I want to clarify that I do see your model, and you do see my model. In fact, it's our goal to see each other see, because it helps us with our greater goal: to make systems interoperate.

Let's focus this discussion on how to make our synchronizers interoperate. As long as they can talk together, we're fine, no matter the mental model of the language.

To do that here, we just need a mapping between the model you're thinking of and the current Braid spec. If we can do that, then we can interoperate.

Since the Braid spec is already written down, it would greatly help us if you could map your model of versioning into the Braid spec. That way we can understand your model. There are 5 authors on the Braid-HTTP and Range-Patch specs, and I think we would all appreciate seeing concretely what contributions you want to make to our shared work product.

[Michael Toomim]

Here, let me help map your model to the current Braid spec:

Seph:

- A "document version" always uniquely identifies a state that a document is in. The same document version implies identical document contents.

In Braid you can represent these things as:

• "Document Version" => the set of version IDs that are currently merged into the resource
• "Operation Version" => a version ID

Another way to distinguish these things is that the "Document Version" is the set of parents on a Braid version, and an "Operation Version" is the version ID and the set of patches.

- There's some freedom in how an operation is applied. Eg the {z:1} operation could move document {a:0,z:0} to {a:0,z:1} or it could move {a:0,b:0,c:1000,z:0} to {a:0,b:0,c:1000,z:1}

What you're thinking about as "applying an operation to a particular document version" can be expressed in Braid as "merging two versions together."

Do you see how that maps?

You have probably noticed that each peer can see different "document versions", depending on which subset of the of 2^N total operations it has received. In Braid language, these are the different ways edits can be combined in mergers. Here's an example with two possible mergers:

In general, there is a combinatorial explosion of possible ways to merge N leaf versions. This could be scary, but remember that our goal is to create interoperability, and interop doesn't depend on whether any two peers merge things in the same order. These intermediate merge versions don't need to be sent over the network. The only time a peer needs to send a version over the network is when it makes an edit.

So in Braid, the only "version" we need to specify is the one where an edit has occurred. In the cases where we explicitly want to talk about mergers of versions, like with the "parents" header, we specify that the peer should communicate a "set of versions." This way we only have one thing named "version," and it's quite straightforward to refer to a set of versions when we need to, by saying "set of versions."

[Michael Toomim]

In other words, we could simplify the mapping to this:

• "Operation Version" => a version ID

• "Document Version" => a set of version IDs

I think that captures the difference between your model and the current Braid spec.

[Seph Gentle]

> So in Braid, the only "version" we need to specify is the one where an edit has occurred. In the cases where we explicitly want to talk about mergers of versions, like with the "parents" header, we specify that the peer should communicate a "set of versions." This way we only have one thing named "version," and it's quite straightforward to refer to a set of versions when we need to, by saying "set of versions."

I think my term "document version" is better for this. "Set of versions" conflates syntax (a list of items) with semantics (identifying a document state). Not all versioning systems represent a document's version with a set of strings.

But maybe better terms would be something like:

"Operation identifier" - unique identifier for a single operation

"Version" / "document version" - Identifier that uniquely names the state a document is in. (Which is a set of operation identifiers in your synchronizer)

This terminology makes it obvious that an operation identifier doesn't always name a document version - they're only interchangable when there's no local merge. Ie, when the set of ancestors of the operation === the set of operations contained in the document.

Example usage:

"The up to date header names a document version"

"Every braid patch has a unique operation identifier" (Or maybe it should be patch identifier?)

-Seph

[Seph Gentle]

I'm going to reply to a few points here because I said I would; though I think they've been mostly better covered by our discussion.

On Fri, Feb 12, 2021, at 10:54 PM, Michael Toomim wrote:

- {c:4} is a "Lamport Timestamp"

- {a:1, b:2, c:4} is a "Vector Clock"

Reference: https://www.cs.rutgers.edu/~pxk/417/notes/logical-clocks.html

The typical advantage of a Vector Clock is that you can compare any two versions' partial order just by checking each entry in the clock. You don't need to look at the DAG! The clocks themselves carry enough info to imply a time DAG.

This means that the information in a Vector Clock is redundant with the "Parents:" field. You could recompute the parents for every version in time if you know that every version is a vector clock.

However, the Vector Clock itself takes up space proportional to O(num_peers). This kinda sucks, because a Lamport Timestamp only takes up O(1) space. And you can encode the same information using Lamport Timestamps by just including the preceding versions in the Parents: field. Then you get the whole DAG.

So if you know for a fact that you have a small number of peers, then you might find it handy to use Vector Clocks, and have a unified representation to compare any two versions. However, if you are interested in scaling your network to a large number of editing peers, then it behooves you to use just Lamport Timestamps for each version ID, and encode the DAG directly using the Parents: field.

The background is great but {c:4} in this example isn't a lamport timestamp. Its an operation identifier. This distinction shows up in many other pieces of work:

- Yjs makes a distinction between a delta (with its (agent,seq) pair) and a "full version" (used for snapshoting - which notably contains the RLE deleted range set).

- Interval tree clocks refer to an "event". The merger of many events is not a list of events - ITC's contribution is in having a much more compact form than you could get by simply naming the contributing parents. Ref: https://gsd.di.uminho.pt/members/cbm/ps/itc2008.pdf

- Dotted version vectors (DVV) extend vector clocks in a similar way...

Maybe, can you fill out this example so I can understand?

    HTTP/1.1 209 Subscription

    cache-control: no-cache

    connection: keep-alive

    content-type: application/automerge

    Transfer-Encoding: chunked

    version: "a:0,b:0"

    content-length: xxx

    version: "???" <-- What value does this contain?

    <<document at {a:1, b:0}>>

----(later)----

    content-length: xxx

    version: "b:0"

    parents: "a:0", "b:0" <-- How should the client interpret this? Its never seen "a:0" or "b:0"

    content-range: json=.messages[1:1] <-- What are these indexes relative to?

    <<patch content>> <-- Is this content not transformed by the server? Even when doing OT?

I'm not sure what you are trying to do, there. I see three ways of representing versions here:

• "a:0,b:0"
  
• "{a:0, b:0}"
  
• "a:0"
  

A resource needs to be consistent in how it represents versions. Each version is a unique string, that uniquely identifies a point in time in the Time DAG. When you reference a version in the Parents: field, that version needs to have been defined somewhere in a Version: field, so you need to use the same representation of versions throughout the resource.

• "a:0,b:0"
  
• "{a:0, b:0}"
  

Huh? How are these different? Are you using different syntax to imply different semantics, or just being a pedant?

---

In our extemporaneous discussion we talked about 2 different models that a system could use:

1. When a client subscribes, it can take the document state and blindly apply all the changes it gets to get caught up to date. Jupiter based OT systems use & extend this model.

2. When a client subscribes, it must build a local logical model of the DAG of operations. The client locally merges changes based on the merge type. CRDT systems typically use & extend this model.

To see the difference consider this history:

  {a:0}

  /   \

{a:1} |    <-- (start - 1)

    {b:0}  <-- (2)

The question I was asking is, if the client subscribes at (start) - ie {a:1}, then receives operation operation {b:1}, what data does the client receive? In ShareDB/ShareJS it would be:

1. document snapshot at {a:1}. The version would be named "1".

2: operation {b:0} *transformed by {a:1}*. This transformed operation would be renamed "2" by the server. (The client only needs to consider the causal history of itself and its server.)

In a CRDT (yjs or automerge):

1. document snapshot with complete document history at {a:0} - note this is much more data than just the document! This includes identifiers for every separable item in the document.

2: operation {b:0}. The client has enough context to be able to merge and update:

  - Its document state

  - Its internal mapping between document contents and IDs

  - Its version (Automerge's version would now be {a:1,b:0}. Yjs would be ({a:1,b:0}, deletes)

What I was asking was - in your mind what does braid do? Do you know? Does it do just one thing, or does it support either?

And I think your answer was it supports either method?

[Santiago Bazerque]

+1 to: operator identifier, document version (perhaps made up from a set of operators, perhaps otherwise - like with something resembling a Merkle tree, vector clocks, etc).

[coming from the pragmatic side of things, my understanding of the spec is not very deep - but in that way my own work seems to "click" with the spec]

--

You received this message because you are subscribed to the Google Groups "Braid" group.
To unsubscribe from this group and stop receiving emails from it, send an email to braid-http+...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/braid-http/41509506-c332-492a-ba46-6d43ff3e5b47%40www.fastmail.com.

[Santiago Bazerque]

I ment operation, not operator, sorry.

[Michael Toomim]

Hi— first can you confirm whether the mapping I proposed is technically accurate? I want to make sure that I'm understanding your model correctly.

Once we can confirm that our models map together, then it makes sense to move onto agreeing on terminology for the different parts.

Seph Gentle:

But maybe better terms would be something like:

"Operation identifier" - unique identifier for a single operation

"Version" / "document version" - Identifier that uniquely names the state a document is in. (Which is a set of operation identifiers in your synchronizer)

...

Example usage:

"The up to date header names a document version"

"Every braid patch has a unique operation identifier" (Or maybe it should be patch identifier?)

Yes, I would call this a Patch ID rather than an Operation ID.

HTTP calls these things patches (like in the PATCH method), and the Braid specs and docs also call them patches rather than operations. See e.g. section 2.3 of Braid-HTTP:

2.3.  PUT a new version as a patch

   Not only are patches smaller, and thus more efficient; they also
   provide useful information for merging two simultaneous edits, for
   instance in collaborative editing.

   One can send an update in a patch by setting the "Patches" header to
   a number, and then set the Message body to a sequence of that many
   patches, separated by blank lines:


      Request:

         PUT /chat
         Version: "g09ur8z74r"                                 | Version
         Parents: "ej4lhb9z78"                                 |
         Content-Type: application/json                        |
         Merge-Type: sync9                                     |
         Patches: 2                                            |
                                                               |
         Content-Length: 62                                    | | Patch
         Content-Range: json .messages[1:1]                    | |
                                                               | |
         [{text: "Yo!",                                        | |
           author: {type: "link", value: "/user/yobot"}]       | |
                                                               |
         Content-Length: 40                                    | | Patch
         Content-Range: json .latest_change                    | |
                                                               | |
         {"type": "date", "value": 1573952202370}              | |


      Response:

         HTTP/1.1 200 OK
         Patches: OK

To include the Patch ID, I'd suggest adding a Patch: header:

         PUT /chat
         Version: "g09ur8z74r"                                 | Version
         Patches: 1                                            |
                                                               |
         Patch: "eh872"                                        |
         Content-Length: 62                                    | | Patch
         Content-Range: json .messages[1:1]                    | |
                                                               | |
         [{text: "Yo!",                                        | |
           author: {type: "link", value: "/user/yobot"}]       | |
   

This patch ID isn't in the spec yet, but we could add it if it helps. However, we'd need to define if it has any particular properties. Is it unique? Or can you use a single patch in multiple different versions? If you do, does that mean that the contents of the patch have to be the same in those versions, or does the patch transform?

I also want to point out that if the Patch ID is unique, and a patch thus cannot be included in multiple versions, then you don't actually need a Patch ID in the protocol to get full consistency — you can re-derive a unique ID as e.g. "Patch 4 of Version 'g09ur8'" or "Offset 7 of Version 'g09ur8'" in every place where you'd need an ID. You'd do this using the wrapper technique where a wrapper translates internal representations into and out of "network representations", which use different unique IDs than the implementations themselves use. This translation can be done in O(1) time to write, and O(log(n)) time to read, for typical sequence CRDTs.

But you don't need to do that. You can include a Patch ID if you want. :)

[Michael Toomim]

Seph:

The background is great but {c:4} in this example isn't a lamport timestamp. Its an operation identifier.

In the name of finding consensus agreement rather than disagreement, let me take a page out of the book of "yes and", and say:

Actually both are true. It is a Lamport Timestamp. It is also a Patch ID. Specifically, your patches are "identified" by their "Lamport Timestamp".

This distinction shows up in many other pieces of work:

- Yjs makes a distinction between a delta (with its (agent,seq) pair) and a "full version" (used for snapshoting - which notably contains the RLE deleted range set).

- Interval tree clocks refer to an "event". The merger of many events is not a list of events - ITC's contribution is in having a much more compact form than you could get by simply naming the contributing parents. Ref: https://gsd.di.uminho.pt/members/cbm/ps/itc2008.pdf

- Dotted version vectors (DVV) extend vector clocks in a similar way...

Yes, you can distinguish a Patch ID from a Version ID. And you are certainly allowed to do so in the Braid-HTTP Spec.

However, the fact that existing systems distinguish Patch IDs from Version IDs is not an argument that you need to distinguish them in order to have full interoperating compatibility. Greg and I prove this by building Sync9, a CRDT that maintains Patch IDs internally, but does not expose them over the network— all communication is done in terms of Version IDs and ranges only.

Maybe, can you fill out this example so I can understand?

    HTTP/1.1 209 Subscription

    cache-control: no-cache

    connection: keep-alive

    content-type: application/automerge

    Transfer-Encoding: chunked

    version: "a:0,b:0"

    content-length: xxx

    version: "???" <-- What value does this contain?

    <<document at {a:1, b:0}>>

----(later)----

    content-length: xxx

    version: "b:0"

    parents: "a:0", "b:0" <-- How should the client interpret this? Its never seen "a:0" or "b:0"

    content-range: json=.messages[1:1] <-- What are these indexes relative to?

    <<patch content>> <-- Is this content not transformed by the server? Even when doing OT?

I'm not sure what you are trying to do, there. I see three ways of representing versions here:

• "a:0,b:0"
  
• "{a:0, b:0}"
  
• "a:0"
  

A resource needs to be consistent in how it represents versions. Each version is a unique string, that uniquely identifies a point in time in the Time DAG. When you reference a version in the Parents: field, that version needs to have been defined somewhere in a Version: field, so you need to use the same representation of versions throughout the resource.

• "a:0,b:0"
  
• "{a:0, b:0}"
  

Huh? How are these different? Are you using different syntax to imply different semantics, or just being a pedant?

I didn't use those syntaxes. You did. I was asking you if they meant anything semantically different, or were just accidents. That's why I said "I'm not sure what you are trying to do, there."

[Michael Toomim]

As for your question about the 2 different models:

Seph:

The question I was asking is, if the client subscribes at (start) - ie {a:1}, then receives operation operation {b:1}, what data does the client receive? In ShareDB/ShareJS it would be:

1. document snapshot at {a:1}. The version would be named "1".

2: operation {b:0} *transformed by {a:1}*. This transformed operation would be renamed "2" by the server. (The client only needs to consider the causal history of itself and its server.)

In a CRDT (yjs or automerge):

1. document snapshot with complete document history at {a:0} - note this is much more data than just the document! This includes identifiers for every separable item in the document.

2: operation {b:0}. The client has enough context to be able to merge and update:

  - Its document state

  - Its internal mapping between document contents and IDs

  - Its version (Automerge's version would now be {a:1,b:0}. Yjs would be ({a:1,b:0}, deletes)

What I was asking was - in your mind what does braid do? Do you know? Does it do just one thing, or does it support either?

And I think your answer was it supports either method?

Yes, Braid supports both of these methods. Do you need any explanation of how? It seems it might help you to see an example of the network messages.

To articulate a little bit:

(1) In the OT case, each client will be receiving different sequences of patches, with different version histories, in their subscription responses.

(2) In the CRDT case, all clients will see the same patches, and piece together identical version histories.

I also want to draw out a distinction that you might not be aware of. In (2) the CRDT case, the "initial snapshot" could be expressed in two different forms:

1. As an opaque blob of CRDT data (as you seem to suggest)
2. As the first N messages expressing the N versions and patches that recreate the blob.

The former will work, but the latter is more semantically meaningful, and requires peers to understand and agree upon one fewer file format. They have to learn how to read and write the patches anyway. Why force them to also read and write the same internal data structure blob?

The latter is also what the "all caught up" header is for: https://github.com/braid-work/braid-spec/pull/79/files

[Seph Gentle]

On Tue, Feb 16, 2021, at 9:23 AM, Michael Toomim wrote:

Hi— first can you confirm whether the mapping I proposed is technically accurate? I want to make sure that I'm understanding your model correctly.

Once we can confirm that our models map together, then it makes sense to move onto agreeing on terminology for the different parts.

Meta request: Please keep more context from the email thread. Its hard to remember your proposed mapping.

On Sat, Feb 13, 2021, at 4:53 AM, Michael Toomim wrote:

In other words, we could simplify the mapping to this:

• "Operation Version" => a version ID
  
• "Document Version" => a set of version IDs
  

I think that captures the difference between your model and the current Braid spec.

Its both technically accurate and semantically accurate for the case where versions are always represented as a DAG of opaque strings (like git).

I'm not sure its syntactically accurate in the case of other systems. And actually, I'm not sure how to represent some other versioning systems in general, in braid. I'm a little worried interval tree clocks won't quite fit - and I'd like to figure out if there's an expressiveness hole here and whether its worth patching.

I think the current system would work for:

- Lamport timestamps (eg sharedb)

- Git style version hashes (eg git, bitcoin)

- Automerge

I'm unsure about:

- Yjs

- Anything using interval tree clocks (its been too long since I read the paper).

- Dotted version-vectors (I think?)

In these latter two systems, a document version is not a set of version IDs. They have special specific representations for the version resulting from a merge.

Seph Gentle:

But maybe better terms would be something like:

"Operation identifier" - unique identifier for a single operation

"Version" / "document version" - Identifier that uniquely names the state a document is in. (Which is a set of operation identifiers in your synchronizer)

...

Example usage:

"The up to date header names a document version"

"Every braid patch has a unique operation identifier" (Or maybe it should be patch identifier?)

Yes, I would call this a Patch ID rather than an Operation ID.

HTTP calls these things patches (like in the PATCH method), and the Braid specs and docs also call them patches rather than operations. See e.g. section 2.3 of Braid-HTTP:

...

To include the Patch ID, I'd suggest adding a Patch: header:

         PUT /chat
         Version: "g09ur8z74r"                                 | Version
         Patches: 1                                            |

                                                               |
         Patch: "eh872"                                        |
         Content-Length: 62                                    | | Patch
         Content-Range: json .messages[1:1]                    | |
                                                               | |
         [{text: "Yo!",                                        | |
           author: {type: "link", value: "/user/yobot"}]       | |
   

This patch ID isn't in the spec yet, but we could add it if it helps. However, we'd need to define if it has any particular properties. Is it unique? Or can you use a single patch in multiple different versions? If you do, does that mean that the contents of the patch have to be the same in those versions, or does the patch transform?

I also want to point out that if the Patch ID is unique, and a patch thus cannot be included in multiple versions, then you don't actually need a Patch ID in the protocol to get full consistency — you can re-derive a unique ID as e.g. "Patch 4 of Version 'g09ur8'" or "Offset 7 of Version 'g09ur8'" in every place where you'd need an ID. You'd do this using the wrapper technique where a wrapper translates internal representations into and out of "network representations", which use different unique IDs than the implementations themselves use. This translation can be done in O(1) time to write, and O(log(n)) time to read, for typical sequence CRDTs.

But you don't need to do that. You can include a Patch ID if you want. :)

Sorry, I think you haven't understood my email. I was discussing semantics - like, what word we humans use to talk about document versions vs patch versions / ids. I wasn't proposing a change to the braid spec.

But now you've mentioned that proposed change, I think this might be a great idea. Maybe we can discuss it on a github issue?

- Seph

[Seph Gentle]

On Tue, Feb 16, 2021, at 9:51 AM, Michael Toomim wrote:

Seph:

The background is great but {c:4} in this example isn't a lamport timestamp. Its an operation identifier.

In the name of finding consensus agreement rather than disagreement, let me take a page out of the book of "yes and", and say:

Actually both are true. It is a Lamport Timestamp. It is also a Patch ID. Specifically, your patches are "identified" by their "Lamport Timestamp".

Uh, I'm not sure it is. I think (?) lamport timestamps just have a single number (1,2,3) and only version vectors support having a separate clock for each peer (eg a:1,b:2,c:0). From stackoverflow:

> Although similar they have different purposes: version vectors can distinguish whether two operations are concurrent or one is causally dependent on the other; Lamport timestamps enforces total ordering. Total ordering although more compact cannot tell whether two operations are concurrent or causally dependent.

I always get version vectors and lamport timestamps mixed up though, so I might be wrong.

This distinction shows up in many other pieces of work:

- Yjs makes a distinction between a delta (with its (agent,seq) pair) and a "full version" (used for snapshoting - which notably contains the RLE deleted range set).

- Interval tree clocks refer to an "event". The merger of many events is not a list of events - ITC's contribution is in having a much more compact form than you could get by simply naming the contributing parents. Ref: https://gsd.di.uminho.pt/members/cbm/ps/itc2008.pdf

- Dotted version vectors (DVV) extend vector clocks in a similar way...

Yes, you can distinguish a Patch ID from a Version ID. And you are certainly allowed to do so in the Braid-HTTP Spec.

However, the fact that existing systems distinguish Patch IDs from Version IDs is not an argument that you need to distinguish them in order to have full interoperating compatibility. Greg and I prove this by building Sync9, a CRDT that maintains Patch IDs internally, but does not expose them over the network— all communication is done in terms of Version IDs and ranges only.

So to be clear, the terminology you're using here is:

Patch ID: A unique identifier for the patch

Version ID: A unique identifier for the document at some point in time

?

Braid already has an example of patch IDs distinct from version IDs:

Inside a patch, the Version header acts as a patch ID (and a version ID)

The all-caught-up header (Current-Versions:) uniquely names a document version (version ID, but not a patch ID)

Braid's versioning system implies the following rules:

- When no merge has happened, version ID === patch ID

- When merges have happened, the version ID = the list of direct ancestor patch IDs

This is different from other systems that we want to contain (eg yjs).

If braid is a container format, should we:

a) Respect the versioning system of the synchronizer we contain

or

b) Make the systems we contain adapt to braid's versioning system

I don't have enough information to have a well formed opinion on this yet. I'd like to see some examples with yjs / automerge / ITC / ??? to know what the terrain here looks like. I'm looking forward to seeing some worked examples from Greg.

-Seph

[Seph Gentle]

On Tue, Feb 16, 2021, at 10:09 AM, Michael Toomim wrote:

As for your question about the 2 different models:

...

Yes, Braid supports both of these methods. Do you need any explanation of how? It seems it might help you to see an example of the network messages.

To articulate a little bit:

(1) In the OT case, each client will be receiving different sequences of patches, with different version histories, in their subscription responses.

(2) In the CRDT case, all clients will see the same patches, and piece together identical version histories.

Yeah I get it, and I think its neat! I added a github issue about potentially telling the client which model the server is working in, because it has some implications for what data the client needs to store. (And it has some implications for crypto - because cryptographic signatures won't survive a rebase)

https://github.com/braid-work/braid-spec/issues/92

I also want to draw out a distinction that you might not be aware of. In (2) the CRDT case, the "initial snapshot" could be expressed in two different forms:

1. As an opaque blob of CRDT data (as you seem to suggest)
   
2. As the first N messages expressing the N versions and patches that recreate the blob.
   

The former will work, but the latter is more semantically meaningful, and requires peers to understand and agree upon one fewer file format. They have to learn how to read and write the patches anyway. Why force them to also read and write the same internal data structure blob?

The latter is also what the "all caught up" header is for: https://github.com/braid-work/braid-spec/pull/79/files

Yep. I think they're semantically identical - In either case we get the complete set of changes. (Thats what automerge/yjs's blob contains). But both automerge and yjs have custom formats for this, becuase the set of all changes gets really large.

Braid doesn't yet have an equivalent form for sending a documents' complete history in a compact manner yet. It would be valuable to invent something like that for braid patches.

-Seph

[Michael Toomim]

> On Feb 16, 2021, at 2:50 AM, Seph Gentle <m...@josephg.com> wrote:
>
> Uh, I'm not sure it is.

It is.

> I think (?) lamport timestamps just have a single number (1,2,3) and only version vectors support having a separate clock for each peer (eg a:1,b:2,c:0).
>

> I always get version vectors and lamport timestamps mixed up though, so I might be wrong.

It looks like you didn't bother to read the link I sent (earlier in this thread) defining the distinction between these. Please read it before continuing.

[Seph Gentle]

On Tue, Feb 16, 2021, at 11:52 AM, Michael Toomim wrote:
> > I think (?) lamport timestamps just have a single number (1,2,3) and only version vectors support having a separate clock for each peer (eg a:1,b:2,c:0).
> >
> > I always get version vectors and lamport timestamps mixed up though, so I might be wrong.
>
> It looks like you didn't bother to read the link I sent (earlier in
> this thread) defining the distinction between these. Please read it
> before continuing.

My thats a lot of swagger to carry around while you're wrong mike. The article you linked[1] agrees with me.

> Each process maintains a single Lamport timestamp counter. Each event in the process is tagged with a value from this counter. The counter is incremented before the event timestamp is assigned. If a process has four events, a, b, c, d, the events would get Lamport timestamps of 1, 2, 3, 4, respectively.

The timestamps are 1, 2, 3, 4 no matter who made the events because the version isn't tagged with the name of the process involved. Those 1,2,3,4 timestamp numbers are global - like, there's one sort of shared global clock. If event A happened before event B, A<B. But its impossible to tell if two operations were concurrent or sequential.

In comparison, vector clocks:

> Instead of a single number, our timestamp is now a vector of numbers, with each element corresponding to a process.

Which is the basis for the clocks I was using in my example - {a:1,b:2,c:0} is a version that cannot be expressed using lamport timestamps. It can be expressed using vector clocks or dotted version vectors.

-Seph

[1] https://www.cs.rutgers.edu/~pxk/417/notes/logical-clocks.html