Fwd: New Version Notification for draft-toomim-httpbis-versions-00.txt

[Michael Toomim]

Hi everyone in HTTP!

Last fall we solicited feedback on the Braid State Synchronization proposal [draft, slides], which I'd summarize as:

"We're enthusiastic about the general work, but the proposal is too high-level. Break the spec up into multiple independent specs, and work bottom-up. Focus on concrete 'bits-on-the-wire'."

So I'm breaking the spec up, and have drafted up the first chunk for you. I would very much like your review on:

Versioning of HTTP Resources
draft-toomim-httpbis-versions
https://datatracker.ietf.org/doc/html/draft-toomim-httpbis-versions-00

Versioning is necessary for state synchronization—and occurs in a range of HTTP systems:

• Caching
• Archiving
  
• Version Control
  
• Collaborative Editing
  

Today, HTTP has resource versions in the Last-Modified and ETag headers, and sometimes embeds versions in URLs, like with WebDAV. Each of these options serves some needs, but also has specific limitations. An improved general approach is proposed, which provides new features, that could enable cool new applications, such as incrementally-updated RSS feeds, and could simplify existing specifications, such as resumeable uploads, and history compression in OT/CRDT algorithms.

I would love to know if people find this work interesting. I think we could improve performance, interoperability, and be one step closer to having Google Docs power within HTTP URLs.

Michael

-------- Forwarded Message --------

Subject:	New Version Notification for draft-toomim-httpbis-versions-00.txt
Date:	Mon, 08 Jul 2024 11:02:11 -0700
From:	interne...@ietf.org
To:	Michael Toomim <too...@gmail.com>

A new version of Internet-Draft draft-toomim-httpbis-versions-00.txt has been
successfully submitted by Michael Toomim and posted to the
IETF repository.

Name: draft-toomim-httpbis-versions
Revision: 00
Title: HTTP Resource Versioning
Date: 2024-07-08
Group: Individual Submission
Pages: 19
URL: https://www.ietf.org/archive/id/draft-toomim-httpbis-versions-00.txt
Status: https://datatracker.ietf.org/doc/draft-toomim-httpbis-versions/
HTMLized: https://datatracker.ietf.org/doc/html/draft-toomim-httpbis-versions


Abstract:

HTTP resources change over time. Each change to a resource creates a
new "version" of its state. HTTP systems often need a way to
identify, read, write, navigate, and/or merge these versions, in
order to implement cache consistency, create history archives, settle
race conditions, request incremental updates to resources, interpret
incremental updates to versions, or implement distributed
collaborative editing algorithms.

This document analyzes existing methods of versioning in HTTP,
highlights limitations, and sketches a more general versioning
approach that can enable new use-cases for HTTP.



The IETF Secretariat

[Rory Hewitt]

Hey Michael,

A few thoughts...

First, I agree that the concept of versioning hasn't been thought about enough, and this is definitely a 'good idea (TM)'.

However, I have a few concerns:

1.1.2 Versioning with ETag

Because ETags are, by definition, unformatted, while it's true to say that you often can't rely on them to establish a version, that's entirely dependent on the format chosen by the user. An ETag *could* validly be specified as a date: 

    ETag: "Sat, 6 Jul 2024 07:28:00 GMT"

or as a version number:

    ETag: "v1.0.2"

or as a random string:

    ETag: "Michael is cool"

IOW, it's totally possible for a site that cares about versioning to use a format that specifies a version number. I recognize this isn't *necessarily* the case, but it helps to be clear here. It should be noted that many web servers that include the creation of ETags natively (e.g. Apache) include an effective version as part of the ETag.

Likewise ETags don't *have* to be sensitive to encoding - there's nothing to stop a server from sending the exact same ETag for two differently-encoded copies of the same underlying resource. It's just that they typically do.

None of this is to say that ETags are better or worse than you describe - just to say that they *can* be better than they are.

2.3 Version and Parents headers

You state that the Parents header can include multiple parents (parents, grandparents, great-grandparents?) and provide an example:

    Parents: "ajtva12kid", "cmdpvkpll2"

and then say "Any version can be recreated by first merging its parents, and then applying the its update onto that merger." (Nit: additional "the" in this sentence). However, you also say that the order of the values in a Parents header makes no difference.

Maybe I'm missing something, but in this scenario, how could that work? Using your example above, here are two possible scenarios:

* Version "ajtva12kid" is earlier. Version "cmdpvkpll2" is later and contains an additional section of HTML

* Version "ajtva12kid" is earlier and contains a section of HTML which is removed in the later "cmdpvkpll2" version

If you merge the two parent versions, then does the outcome (onto which you will apply the update) include that section of HTML?

I guess it just makes sense to me to have the order in the Parents have some meaning - whether oldest first or last. Or you could specify that both Version and Parent values must be integers.

2.4.3 PUT a new version

This seems like it could lead to either race conditions or some other issue with duplicate Version values. Surely it's better to have the client submit a new version of a resource (passing the Parents header but *not* passing the Version header) and have the server, which is presumably the prime source of versioning truth, calculate a version (perhaps after retrieving other PUT requests from other clients) and return that value in the Version response header?

I see you discuss this later with the Current-Version header, so perhaps you covered this and my old eyes missed it.

Rory

[Michael Toomim]

We've got divergent discussion threads that I'm merging together.

First, Peter Van Hardenberg (of Ink & Switch, Local-First, and Automerge) wrote this initial review of the draft. He's cc'd, and we can respond in this thread.

------------------------
-- Peter Van Hardenberg: --
------------------------

Hi Michael,

I had a quick look at the spec and gave some thought to whether we'd want to adopt it. I think right now it has quite a lot of per-version overhead, and viewing this through a local-first lens, one can imagine having to publish a large number of versions each as separate PUT calls. You might want to consider supporting ranges for PUT in a single message.

Overall, our goals appear to differ from what you're proposing here so this feedback may not be particularly important. My sense is that the expected granularity of changes for Braid is relatively large and that the frequency is relatively long -- on par with a changed HTML form submission, perhaps. We spend quite a lot of our time thinking about optimizing updates for potentially thousands of edits and trying to minimize the number of round trips required to synchronize state in both directions. You mention that the design intends to be optimizable but I didn't see much in the text that clarified how. 

One other observation is that this spec does not appear to prioritize retention of history: 

>      - If the Parents header is absent, the server SHOULD return a

>      single response, containing the requested version of the resource
>      in its body, with the Version response header set to the same
>      version.

This design may centralize the system, as clients default to receiving "flattened" versions of resources and thus may not be able to merge changes from other sources.

Last, have you considered specifying some kind of signature / validation feature? If clients are applying patches iteratively, it might help for them to be able to validate that they're in the expected state either before or after applying a patch.

All the best,

-p

[Michael Toomim]

I'm also merging Pierre Chapuis' comments into this thread. Pierre is cc'd, and we can respond here.

------------------
-- Pierre Chapuis: --
------------------

Hello everyone,

this email got me interested. I have been silently following the progress on Braid for a while. I have worked with various data replication and synchronization techniques (including CRDTs and others) and a HTTP standard for resumable feeds is something I have wanted for a long time, to support use cases similar to HTTP Feeds.

Here is a small observation I have from reading the draft. In "4. Version-Type Header", regarding the vector-clock type, did you consider the alternative of just using parents instead of the complex dedicated version format, where each Parent would be of the form "agentidX: counterX"? If the data is modified, the Version response header could potentially be used for the current "server" node.

For instance, considering a CRDT implementation, if the "client" Bob is at {alice: 2, bob: 2, charlie: 3} and the "server" Alice is at {alice: 3, bob: 2, charlie: 4}, and Bob submits a new version, the request headers could be:

Version: "bob: 3"
Parents: "alice: 2", "bob: 2", "charlie: 3"

and the response headers could would be:

Parents: "alice: 3", "bob: 3" , "charlie: 4"

Best,

-- 

Pierre Chapuis

On 7/15/24 6:26 PM, Michael Toomim wrote:

[Michael Toomim]

Peter, thank you for your interest! I'm excited that you are bringing up performance for discussion! There's a lot to say on that, and I give an overview below:

== Compression & Performance ==

First, let me correct a big misinterpretation— this work absolutely prioritizes high-performance, realtime data synchronization. It should support thousands of mutations per second. Our implementations are higher-performance than Automerge, for instance. I regularly work today with a doc composed of 110,000 edits. It loads instantly, thanks to some great Version-Types we've designed.

The Version-Type (in the proposed Version-Type header) is the way you get performance increases. The key to performance is managing history growth. You manage that by finding a pattern in history, and then compressing or ignoring history. You can express those patterns as a Version-Type spec. (There's a robust theory behind this called Time Machines.)

I apologize that this wasn't clear in the draft -00. I thought this would be an advanced feature that people wouldn't comment on for a bit — but am pleasantly surprised to hear your interest in it! I will be adding more clarity to the spec on Version-Types, and already have begun doing so in github:

https://github.com/braid-org/braid-spec/blob/master/draft-toomim-httpbis-versions-01.txt#L885

I'd also encourage you to check out this sketch of how to bake RLE into HTTP Header Compression:

https://braid.org/meeting-69/header-compression
https://braid.org/video/https://invisiblecollege.s3.us-west-1.amazonaws.com/braid-meeting-69.mp4#4166

In any case, keep in mind that at this stage, we need to know only whether there is interest in this area of work — not whether this particular spec meets your needs. If we adopt this work into the HTTP WG, we will get a chance to change or rewrite any part of the spec. This spec is just a starting point to get discussion going. So think of this as a problem statement rather than a solution statement.

== PUTs ==

As for PUTs, I suspect you might be thinking about HTTP/1.0 where each PUT might require a new TCP connection with its own TLS handshake. But keep in mind that with HTTP/2 and 3, all HTTP semantics are expressed in binary, and a PUT is usually just a single packet! This is just as efficient as any hand-rolled protocol you have, and it has the advantage of being interoperable with all of HTTP.

== History Retention ==

This versioning model supports Time Machines— the beauty of which is that peers become free to independently choose how much history to store. An archival peer can store the full history. A light client can store just the latest version (see the amazing Simpleton client, which needs zero history).

So each peer can choose how much history to store. If a peer doesn't have enough history to merge an edit, it can simply request that history from another peer. In this draft, you do so by requesting a GET with both Version and Parents headers specified.

== Signatures & Validation ==

This is out of scope for this proposal on versions. However, (a) there are some Version-Types that double as signatures. When this happens, it can be specified by authoring a Version-Type spec to articulate the new constraint. And (b) this is a generally important area of work that I encourage.

Cheers!

Michael

[Michael Toomim]

Rory, thanks for these excellent thoughts! It's exciting to see other people digging into the versioning problem with us. :)

Responses:

== Versioning with ETag ==

You make a good point that ETag headers, like the proposed Version header, are opaque strings that can be formatted to express additional information if we want to. This is true for both ETag and Version:

ETag: "Sat, 6 Jul 2024 07:28:00 GMT"

Version: "Sat, 6 Jul 2024 07:28:00 GMT"

ETag: "v1.0.2"
Version: "v1.0.2"

We propose articulating the structure of these version ids using a Version-Type header. You could, for instance, use "Version-Type: date" for the first example, and "Version-Type: semver" for the second.

The main problem with ETag, though, is that it marks *unique content* rather than *unique time*. If you mutate the state of the resource from "foo" to "bar" and then back to "foo", you'll revert to the same ETag, even though this is at a different point in time. This breaks collaborative editing algorithms.

Finally, I'll note that your claim that ETags don't have to be sensitive to content-encoding is only true for *weak* ETags. Strong ETags must change whenever the byte sequence of the response body changes. This means they should be sensitive to content-encoding. RFC9110 is also explicit that they depend on content-type:

> A strong validator might change for reasons other than a change to the representation data, such as when a semantically significant part of the representation metadata is changed (e.g., Content-Type)
https://datatracker.ietf.org/doc/html/rfc9110#section-8.8.1

Consider the case where a user edits a markdown resource:

PUT /foo
Content-Type: text/markdown
Version: "mike-99"

# This is a markdown file

Hello world!

And the server then shares this as HTML:

GET /foo
Accept: application/html


HTTP/1.1 200 OK
Content-Type: application/html
Version: "mike-99"

<html>
  <body>
    <h1>This is a markdown file</h1>
    <p>Hello world!</p>
  </body>
</html>

Using the Version header, we're able to express that these are two representations of the resource at the same point in time. You can't do this with a strong ETag.

== Version and Parents headers ==

I think there's been a miscommunication here. The reason there are multiple version IDs in the Parents header is for edits that happen *in parallel*, not for edits that happen in sequence. This is to represent a version DAG:

                  a  <-- oldest version
                 / \
                b   c
                 \ /
                  d  <-- current version

In this example, the current version "d" would have:

Parents: "b", "c"

This is not allowed:

Parents: "d", "b"

Because of this language in the spec:

For any two version IDs A and B that are specified in a Version or
Parents header, A cannot be a descendent of B or vice versa.  The
ordering of version IDs within the header carries no meaning.

Good question!

== Client-generated Version IDs on PUT ==

Yes, there would be a problem if two clients generate the same version IDs for two different PUTs. Then the versions would not be unique!

However, requiring the server to generate versions is only one possible solution— and is a solution that requires a server. We also want to support distributed p2p systems, which don't have servers.

In these systems, it's quite common for clients to generate version IDs. There are two common ways to solve this problem:

1. Use a large random hash space so that collisions are extremely unlikely. This works well enough for git, for instance.
2. Each client gets a unique ID, possibly by coordinating with a server, and then versions are constructed by concatenating "<client-id>:<counter>" for each client.

Does this all make sense?

Again, good questions, and I am glad to see this interest in the topic! I think we can do a lot with it!

Michael

[Michael Toomim]

Peter, I just wrote up an explicit example of how to compress four PUTs into 7 bytes. Check out the new section 5.1 here:

https://github.com/braid-org/braid-spec/blob/master/draft-toomim-httpbis-versions-01.txt#L945

These four puts compress down to 0.0146% of their original size, at least in theory. Note that said compression scheme isn't fully specified in this draft — the focus of this draft is just to gather interest in working on a versioning system that makes such compression possible. The actual compression schemes would be future work.

[Pierre Chapuis]

Hello Michael,

regarding the "version and parents headers" ordering issue Rory mentioned, I don't think he was talking about the case where one version descends the other one.

The fact that you say this has very strong implications:

> Any version can be recreated by first merging its parents, and then applying the its update onto that merger. 

It either means there cannot be conflicts between parents - or in other words that conflict resolution is deterministic, commutative *and* associative (like CRDTs), or that updates must always contain the conflict resolution of their parents like Git.

That last solution also means updates can be rejected by the server if its history is incoherent, and comes with its own issues. The way Git works is that conflict resolution is always performed with human intervention on pull, not on push.

I know Braid has answers to this (Merge Types) and you are trying to break up the spec here, but it is not surprising that if you have a spec that says "versions can have several parents and you can merge them" people are going to wonder how.

-- 

Pierre Chapuis

--

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/d713500c-c4db-4bf8-8096-edb0b5ff1751%40gmail.com.

[Pierre Chapuis]

I sent this too fast, I should have edited out the part where I said this is what Rory meant. I think he did talk about the case (that is prohibited) where one version descends the other one.

But I think the rest of my comment still holds: specifying multiple concurrent parents without specifying merges and conflict resolution is a bit weird.

-- 

Pierre Chapuis

To view this discussion on the web visit https://groups.google.com/d/msgid/braid-http/fdce4502-6888-4c27-bb14-c239e19e8771%40app.fastmail.com.

[Rory Hewitt]

Hey Pierre, 

Actually, I kinda WAS talking about my (mis)understanding that the Parents header could contain both parents and grandparents... 

That being said, if the Parents header can ONLY contain direct parents, that seems like a (possibly significant) limitation.

Would it not be an improvement to allow the header to contain a list of ancestors back to whatever level the server feels is appropriate or retains information, complete with level information (ancestor level): 

Parents: "parent1","parent 2":1; "grandparent":2;"greatgrandparent1","greatgrandparent2","greatgrandparent3";3

This indicates two parents (level 1), a single grandparent (level 2) and 3 great grandparents (level 3).

This could be compared with a similar Parents header for another object to determine where differences may be found, and how far back.

Maybe this is getting too far into the weeds - this was, as I noted, based on my misunderstanding, which Pierre obviously understands is a possibility. 

I guess my primary point is that in finding a balance between brevity and flexibility, a design that is able to specify detailed information is better, even if that detailed information is often elided or ignored. 

With these fairly 'generic' header names like Version and Parents, the ability to use them to (in theory) 'build' a history of a file and compare with a later, earlier or 'sibling' file send very useful...

But I defer to the smarter minds here - I am a mere tinkerer and may well have gotten too deep too early.

Rory

[Marius Kleidl]

Hi Michael,

talking about performance, I am curious how it would perform in a real-time, collaborative editing process (similar to Google Docs or the note taker tool during the IETF meeting). To facilitate the real-time aspects of the editing experience, would the client have to send a PUT request after every few keystrokes, so that the changes appear quickly on the peers' screens? Sending these requests is comparatively cheap for the client, especially with HTTP/2 and HTTP/3, but potentially more costly for the server, which has to perform authentication checks for each request and then load the resource's state from some storage. If many requests are sent in short succession, this can induce a higher load on the server. A stateful connection, like with WebSockets, in contrast to stateless HTTP requests could reuse the loaded and checked state - although such a method likely has other caveats attached.

Overall my question is whether you think this draft is suitable to deliver such real-time experiences in an efficient manner? 

Best regards

Marius Kleidl

[Michael Toomim]

Yes, it works great for collaborative editing. I use it every day in production. It's very fast. We send a PUT per keystroke. I should show you a demo. It's real. :)

It's not true that an HTTP PUT induces more load on the server than a WebSocket message. They are equivalent. Consider that both H2 and WebSocket are TCP streams that stay persistently open. The only difference between these two streams is how the data is formatted. They don't impact how/when the server loads the resource from disk into ram. It's true that HTTP requests often contain a session ID in a cookie on each request, whereas a WebSocket might only send that when the user logs in/out, but that header gets compressed down with H2 header compression and isn't a significant performance problem.

Perhaps you're thinking about old-style threaded web servers? Those have a lot of overhead per request, because a 4mb OS thread has to be allocated to each request. But those don't support persistent connections (like WebSockets) at all. That's why everyone's moved to evented servers, like nodejs, which make persistent connections cheap, whether formatted as a WebSocket message stream or a H2 message stream.

[Ben Schwartz]

HTTP requests tend to run through a lot more middleware than application-layer messages like WebSocket.  Every request is likely to be checked for compliance with various Web Application Firewall policies, passed through various caching gateways, logged to various request logs, etc.

I would recommend thinking carefully about whether the using individual HTTP requests, instead of an application-layer stream of some kind, is semantically correct and useful.

--Ben

---

From: Michael Toomim <too...@gmail.com>
Sent: Tuesday, July 23, 2024 3:25 PM
To: Marius Kleidl <mar...@transloadit.com>
Cc: HTTP Working Group <ietf-h...@w3.org>; Braid <braid...@googlegroups.com>; Peter van Hardenberg <p...@pvh.ca>
Subject: Re: Review of draft-toomim-httpbis-versions-00

 

[Michael Toomim]

Ben Schwartz:

> I would recommend thinking carefully about whether the using
> individual HTTP requests, instead of an application-layer stream of
> some kind, is semantically correct and useful.

Yes, we have thought very much about the semantics, and are very excited
about the symmetry. The semantics of HTTP is State Transfer, and we are
extending them to State Synchronization. The messages fit very cleanly
and elegantly into HTTP requests and responses, which makes us quite
excited. =)

Thanks!

Michael

[Michael Toomim]

Pierre, thanks for these juicy thoughts!

First, your work on HTTP Feeds looks very relevant to 104 Multiresponse idea (Section 2.4.4) that is slated for a future spec. I'd love to hear your thoughts!

As for vector clocks, what you have just suggested is very interesting— that is a way to express the same History, with a different Version-Type! (Albeit, one that bends the constraint that parents' cannot be ancestors of each other that we've been discussing elsewhere.)

Although this contains the same history as the Vector-Clock example, I would not call these version IDs themselves Vector-Clocks. One cool thing about a Vector-Clock is that you can compare any two vector clocks in O(peers) time, without doing any O(n) traversals of the historical time DAG! If you have a small set of peers, this lets you compare order in O(1) time. This means you don't need to specify any parents at all in your messages. All ordering can be deduced from the Version header alone. That's kinda cool, for the systems that need that.

Michael

[Michael Toomim]

Good point! I've clarified the spec on merging by adding a reference to [Merge-Types].

Thank you!

[Michael Toomim]

Peter and Martin,

I've hit "publish" on the explanation for how to compress history with Version-Types:

https://datatracker.ietf.org/doc/html/draft-toomim-httpbis-versions#section-5.1

You can simply review these sections (5.1 and 5.2) instead of the long list of links below. Does this address your concerns?

Thanks,

Michael

[Michael Toomim]

Well, the main reason for the Parents: header is to convey the shape of the historical time DAG.

The scheme you propose here does not give *quite* the full information on grandparents. Consider these two time DAGs:

DAG 1 has parents and grandparents:

    a1   a2
     |   |
     |   |
    b1   b2
      \ /
       c

DAG 2 has the grandparenting flipped:

    a1   a2
      \ /
      / \
    b1   b2
      \ /
       c

These are different DAGs, but they'd produce the same Parents: header in your scheme:

Parents: "b1", "b2":1; "a1", "a2":2

So I don't think this scheme is yet an improvement.

If your goal is to have a convenient way to request a span of history, might I suggest doing a HEAD request on the span:

HEAD /foo
Parents: "a1", "a2"
Version: "c"

The server will respond with an outline of the time DAG:

HTTP/1.1 104 Multiresponse

HTTP/1.1 200 OK
Parents: "a1"
Version: "b1"

HTTP/1.1 200 OK
Parents: "a2"
Version: "b2"

HTTP/1.1 200 OK
Parents: "b1", "b2"
Version: "c"

This lets you access the DAG without downloading any patches or resource contents.

Cheers!

Michael

[Pierre Chapuis]

Hello Michael,

to be clear I have not worked on HTTP Feeds myself, I have just used it, but your work on Braid made me think of it.

Regarding the Vector-Clock type I see your point, this would violate how parents are supposed to work so it is probably not a good idea.

-- 

Pierre Chapuis

[Mostafa Shahdadi]

Unsubscribe 

Sent from my iPhone

On Jul 25, 2024, at 13:57, Michael Toomim <too...@gmail.com> wrote:



[Martin Kleppmann]

Hi Michael,

Thanks for sharing your write-up! The approach you describe is quite different from the way we're thinking about syncing CRDT updates. If I understand correctly, you are proposing to use the HTTP-style structures of resource path, headers, and body to encode different parts of a CRDT update: the path identifies the object to be updated, the Content-Range header identifies the position within that object (e.g. text index), the Version and Parents headers provide causality, and in your example the body contains the actual text to be inserted.

In contrast, the way we're thinking about this in Automerge is that the CRDT library defines a serialisation format, and all the components above (the object to be updated, the position within that object, the causality information, and anything else) are packed opaquely inside that serialised format. The sync protocol would not need to care about that structure; it would only transfer those serialised blobs.

I have a couple of questions about your proposed approach:

- If you want to atomically update multiple objects, would your approach require multiple PUTs? Is there a risk of some of them being applied and some being dropped if the network drops at an inopportune moment? In our approach we simply encode multiple updates into a single blob. An example for wanting atomicity: say you want to attach a comment as an annotation to a span of text. In Automerge you would do that by attaching a comment ID as a mark to a range of characters, and then in a separate object you would map the comment ID to a JSON object with the details of the comment (author, text, timestamp, reply thread, etc).

- If you want to support end-to-end encryption, it looks like you would need to separately encrypt the request body and each of the header fields, which would add overhead and complexity. Similarly for cryptographic authentication, you would have to compute a signature over all those individual fields. With a blob-based sync protocol we can make the sync independent of the blob contents, and thus we can encrypt the blob without the sync protocol caring.

- How would the HTTP-style requests map to a p2p setting? The PUT … syntax seems to suggest an asymmetric, client-server style relationship between the communicating nodes. I know you said that Braid was p2p-compatible, but maybe the HTTP-style syntax just puts me so much in a client-server mindset that it's not obvious to me how it translates to communication between peers.

I prefer to think about the sync protocol as a reconciliation between two sets of blobs, where the two peers are figuring out which blobs they need to send to each other so that, at the end, they both have all the blobs. The content of those blobs is not important to the sync. In your model, more of the structure of CRDT updates is exposed to the sync protocol, and it's not clear to me that you gain much of an advantage from that – but it has the disadvantage of coupling the two layers more closely. Why prescribe the HTTP-style message format and not just let each CRDT implementation define its own serialisation format that is optimised for its features?

I guess one thing that your approach supports is that when in unencrypted mode, the server could generate a snapshot of the document rather than serving a log of the edit history. However, our blob approach allows that too: a server that is able to interpret the contents of the blobs can also compress them into a snapshot and serve it when required (we sometimes call this a "shallow clone" by analogy to the similar concept in Git). But that is an optional extension to the protocol; the core protocol can still work on uninterpreted blobs.

There is a lot more to be said on compression, encryption etc. but I'll leave it there for now, as I'd be interested to hear what you make of the different approaches.

Best wishes,

Martin

[Michael Toomim]

Martin, thank you for engaging! It's valuable getting input on data synchronization from the author of Designing Data-Intensive Applications.

I believe we are addressing complementary aspects of the state synchronization problem, rather than "different approaches." Specifically: you're focusing on how peers reconcile and route an E2EE history of blobs; whereas I'm working on the structure within those blobs.

Our work could integrate as follows:

Envelope            1: Your work (routing protocol)
  Routing Headers
  Message Type
  Message           2: My work (message structure)
    Headers
      Version       3: This versioning spec
      Parents       3: This versioning spec
      Range
    Body
      New Value

An Envelope is a structured container within a protocol that encapsulates opaque data across multiple hops. It's a feature of SMTP, for instance, that allows mail to go through relays, while GPG-encrypting the contents, and is also how BCC works. In my understanding, you are working on a routing & reconciliation protocol for envelopes that maintain content opacity.

In my view, your work could be expressed in an extension to HTTP that allows HTTP messages to route through multiple peers. Some HTTP extensions already implement this concept implicitly. For example, OHAI (Oblivious HTTP) uses an encapsulated request that functions like an envelope — it includes routing information (gateway and target URLs), encrypts contents, and has authenticity elements (like a nonce). This enables OHAI to separate client identity from request content, facilitating privacy-preserving routing.

The versioning spec discussed in this thread, on the other hand, addresses part 3 of the above diagram: event Versioning, which falls within part 2: Messages.

Our efforts complement each other. Any synchronization protocol requires both message routing and message contents. However, I've noticed you use "synchronization protocol" to refer to just the reconciliation part:

> I prefer to think about the sync protocol as a reconciliation between two sets of blobs, where the two peers are figuring out which blobs they need to send to each other so that, at the end, they both have all the blobs.

I propose using "synchronization" to encompass the entire problem, including the CRDT bits. CRDTs are crucial to synchronization as they define how peers merge parallel edits in synchrony.

I hope we can discuss both aspects. I would love to hear your thoughts on the versioning proposal, and I will now address your broader questions about P2P routing of HTTP messages:

Martin Kleppmann wrote:

- If you want to atomically update multiple objects, would your approach require multiple PUTs? Is there a risk of some of them being applied and some being dropped if the network drops at an inopportune moment? In our approach we simply encode multiple updates into a single blob. An example for wanting atomicity: say you want to attach a comment as an annotation to a span of text. In Automerge you would do that by attaching a comment ID as a mark to a range of characters, and then in a separate object you would map the comment ID to a JSON object with the details of the comment (author, text, timestamp, reply thread, etc).

Yes, we want to support atomic mutations (e.g. "transactions") across objects.

I'd like to pick a more difficult example, though, because annotations to spans of text do not intrinsically require two atomic writes to create. The annotation's "attachment" can just be a single field that points to a span of text at a version ID, such as {version: ["x72h"], range: "text 44:70"}. Then you don't need an intermediate object, don't mutate the text CRDT, and end up with just one object to mutate.

Perhaps a stronger example is a Bank Account transfer. Suppose Bob wants to send $10 to Alice. We will debit -$100 from Bob's account, and credit +$100 to Alice's. Bob and Alice sign their mutations from different computers, and send them over the network:

PUT /bob
Version: "transaction-9bx38"
Content-Range: json .account.balance
Content-Length: 3

110


PUT /alice
Version: "transaction-9bx38"
Content-Range: json .account.balance
Content-Length: 2

90

You propose enforcing atomicity by encoding both PUT messages within the same opaque envelope, which would eliminate scenarios where some peers have one message, but not the other. Unfortunately, this requires both mutations to be created atomically on the same computer. If Alice and Bob sign and send their transactions from separate peers, they will have separate envelopes, and we still have an atomicity problem to contend with.

A more general way to address atomicity is via Versioning + Validation. Atomicity is about time, Versioning specifies time, and Validation can mark a version invalid until all parts of the transaction are available. In our case, Bob and Alice:

• Choose a single Version ID (e.g. "transaction-9bx38") for both PUTs, to say that they happened atomically, at the same time.
  
• Implement a validation rule (aka "precondition" in CRDT parlance) that says the mutation is not valid/enabled until both sides of the transaction have been received, and are signed by the appropriate parties.

I believe Validated Versioning provides a more expressive framework for atomicity than Multi-Message Envelopes. We can do this with PUTs, if we extend them with a versioning spec (e.g. in this thread) and a validation spec (TBD).

- How would the HTTP-style requests map to a p2p setting? The PUT … syntax seems to suggest an asymmetric, client-server style relationship between the communicating nodes. I know you said that Braid was p2p-compatible, but maybe the HTTP-style syntax just puts me so much in a client-server mindset that it's not obvious to me how it translates to communication between peers.

This might be easier to understand visually, so I just recorded this video:

https://braid.org/protocol/visualizing-http2p

I hope that's helpful. It was my first time trying that. I'm happy to clarify anything that I hand-waved. The resources I used are here:

1. https://braid.org/antimatter#viz2
2. https://braid.org/antimatter#messages-summary

Why prescribe the HTTP-style message format and not just let each CRDT implementation define its own serialisation format that is optimised for its features?

The goal is interoperability. You cannot get decentralization without interoperability. If you build a decentralized protocol that doesn't interoperate, you just create a new walled garden on top of your "p2p" protocol. Look at IPFS.

My work makes CRDTs and OT interoperable. We now have a common protocol that any CRDT and OT algorithm can use, while independently optimizing their own features. (Yes, this is the Time Machine architecture that unifies OT and CRDT, which I am writing up, and your new paper cites a draft of.) Part of this is a general representation of time, specified in terms of Events and Versions, with a "version-type" that enables optimizations, without coupling implementations to each other's data structures. This versioning idea is in the spec for this thread, and is awaiting peer-review from experts like you.

This common protocol for any CRDT or OT algorithm has many benefits. (1) It allows us to build CRDT algorithms that support multiple merge-types. (See Seph's reference-crdts work.) (2) It allows implementations to implement optimizations independently, while still guaranteeing consistency. (Consider EG-Walker. Each peer can implement a walker and its internal format differently.) (3) It allows implementations to summarize or prune some ranges of history independently, while still guaranteeing full consistency for merges through other ranges of time (like with antimatter), and (4) to request various ranges of history from one another in a standard way if they have dropped information that they want back. (5) It allows these operations to be implemented by generic infrastructure, such as CDNs, caches, and backup devices, without requiring them to implement any specific CRDT or OT algorithm. (6) We can also build debugging and programming tools that are able to inspect and support this history without knowing about a particular CRDT or OT algorithm. See the braid-chrome devtools panel as an example.

The goal is interoperability. It results in better performance, tools, and infrastructure; along with more widespread usage. This gets even better when we interoperate with HTTP.

I guess one thing that your approach supports is that when in unencrypted mode, the server could generate a snapshot of the document rather than serving a log of the edit history. However, our blob approach allows that too: a server that is able to interpret the contents of the blobs can also compress them into a snapshot and serve it when required (we sometimes call this a "shallow clone" by analogy to the similar concept in Git). But that is an optional extension to the protocol; the core protocol can still work on uninterpreted blobs.

Yes, there are important use-cases for both needs. However, one man's "core" is another man's "optional." May I propose the neutral principle of *separation of concerns*? The serialization/envelope/routing/reconciliation can be a separate concern from the message formatting. We don't need to agree on which concern is more "core." It's up to implementations to choose which specs they want to implement.

Thank you, again. This discussion has been quite valuable to me. I hope you find value in it, as well!

Michael