7 ms·

Braid: Synchronization for HTTP

196 points by tobr 7y ago

deleted 7y ago
[deleted]
chrisweekly 7y ago
"Braid is an effort to incorporate new distributed technologies into the existing World-Wide Web. We find consensus on extensions to today's web standards that support distributed web technologies. We work in the IETF's HTTP Working Group. You can join the effort. The Braid Protocol is a set of extensions to HTTP, which transform it from a state transfer protocol into a state synchronization protocol. When a resource is changed by one client or server, all other clients and servers update. Braid supports Operational Transform and CRDTs at web URLs, enabling peer-to-peer, offline-capable web applications."
deleted 7y ago
[deleted]
ChrisRus 7y ago
This looks very interesting indeed. I am currently working on a system that allows hierarchical system modeling and evaluation of so-called "observable process models". I can easily understand leveraging something like this over HTTP to reduce implementation details of model and state transfers.
- heavenlyblue 7y ago
  What's an "observable process model"?
- toomim 7y ago
  Oh, thank you for sharing! I would love to see an example of where you are dealing with model and state transfers, so that we can make sure that the protocol we are building supports it. Is there anything more you can say about this?
svnpenn 7y ago
I wrote 2 implementations for ETag, one using plain text files and one using a database file: https://cup.github.io/autumn/talk-conditional-request https://cup.github.io/autumn/talk-conditional-request My implementations are in PHP, but they could easily be adapted to other languages. I was surprised when I found that cURL really doesnt have support for this. Yeah, you can do something like this: $ curl -I -H 'If-None-Match: "109-55035a2e5a100"' \ > speedtest.lax.hivelocity.net HTTP/1.1 304 Not Modified but its of limited usefulness. What you need is a cache storing all the requests youve made, so that the next time you make a request the cache can be checked. Without the cache its pointless. Also a problem is that some sites only return Last-Modified, not ETag: $ curl -I https://en.wikipedia.org/wiki/Main_Page last-modified: Sun, 03 Nov 2019 20:12:16 GMT and some dont return either: https://www.google.com https://www.google.com
codetrotter 7y ago
> Why "Braid"? > 1. It adds versioning—and time travel—to the web, just like the videogame Braid. That video game was the first thing I thought of when I read the name. Cool that it is one of the actual reasons they chose to name this that.
pm90 7y ago
Can someone with a mathematical background explain what the practical uses of this protocol are? It talks about time travel and state synchronization v/s state transfer. Is this an effort to create a protocol that e.g. allows for distributed systems over http instead of relying on "custom" implementations such as Paxos? (i'm pretty sure I'm misunderstanding this, please feel free to correct)
- toomim 7y ago
  Yes, the braid protocol could let you run a distributed system over HTTP. It lets you put a CRDT or OT behind any HTTP resource, which lets you distribute the resource, with multiple writers, and guarantee consistency after arbitrary edits. Each resource will still have a URL, with one particular hostname, but the actual state can live and be modified simultaneously on multiple hosts. The first thing you might use this for is collaborative editing. Braid can give you the power of Google Docs at any HTTP URL, without writing additional code. This also improves performance. Instead of using heuristics to determine when a cache needs to be reload (cache-control max-age, last-modified, etags), Braid will automatically push all updates to caches -- guaranteed. That means you never need to force-reload a page, or force-clear a cache. Also, updates are sent as minimal diffs, rather than re-sending the entire resource whenever it changes. This saves a lot of bandwidth and a lot of round-trip latency when loading a page. As a third practical example, Braid makes it very simple to read and write data from multiple web sites. By collapsing time, braid implementations let you write code that manipulates state at any URL as easily as a local variable. It doesn't matter whether state is located on your server, or someone else's server, or distributed on everyone's servers and clients. It's all equally easy to interact with. This also makes it easy to write a new UI for an existing site. As for Paxos, yes, CRDTs are an alternative to Paxos, and CRDTs can be used in Braid. CRDTs have some performance improvements over Paxos -- Paxos chooses a leader, and whenever the leader is unreachable, a new leader election takes place which requires a couple network round trips before any new edits can be broadcast. CRDTs are always editable, and edits can always be broadcast.
  - sagichmal 7y ago
    > Braid can give you the power of Google Docs at any HTTP URL, without writing additional code. What implements the OT or CRDT logic? The webserver itself?
sansnomme 7y ago
Would it be correct to say that this is a CRDT protocol on the HTTP level, similar abstraction level to e.g. REST?
- toomim 7y ago
  Yes. One way to look at this is that HTTP is already very close to a CRDT or OT protocol -- it just needs a few new features. By adding those features into HTTP, we generalize HTTP and REST from being able to simply transfer state to being able to synchronize it, across arbitrary arbitrary edits, from multiple writers. HTTP: HyperText *Transfer* Protocol REST: REpresentational State *Transfer* HTSP: HyperText *Synchronization* Protocol RESS: REpresentational State *Synchronization*
  - sansnomme 7y ago
    So stuff like PouchDB, Gunjs will now be trivial?
    - toomim 7y ago
      These are databases that support synchronization. They have to design their own custom protocol, because HTTP (without Braid) does not support synchronization. We want to add Braid support to PouchDB and Gunjs. Then they can interoperate, with one another, and with the rest of the web. You'll be able to build a distributed app that stores some data in Gunjs, and some in PouchDB, on different servers, on different websites. The differences between different synchronizing databases are captured in "Merge Types": https://raw.githubusercontent.com/braid-work/braid-spec/master/draft-toomim-httpbis-merge-types-00.txt https://raw.githubusercontent.com/braid-work/braid-spec/mast... Over time, I imagine that these databases will add support for each other's merge types, and then -- yes -- their abilities will be "trivial", and baked into most URLs of the web.
BiteCode_dev 7y ago
Reading the RFC, this seems to make HTTP stateful: "A subscription is different from a GET connection (e.g. a TCP connection, or HTTP/2 stream). If a client requests "Subscribe: keep-alive", then the subscription will be remembered even after the GET connection closes." It also uses PUT to patch things, but then why not use PATCH ? You could say it's non standard, but at this point, everybody uses it. Plus their stuff apparently deviates from the HTTP standard as well by allowing headers after the first line of the payload and introducing the forGET command. Or am I missing something ? Interesting anyway, especially the way they create of graph of unique ID to solve the ordering problem. Feels like Git. The flow of patch reminds me of react-redux. Plus it's great to have more geeky technical things on HN. I'm missing it, among all the news and start up things. They also mention a really cool RFC on a JSON patch format: https://datatracker.ietf.org/doc/html/rfc6902 https://datatracker.ietf.org/doc/html/rfc6902 I'm reading RFC and getting excited about it. Damn, that must be what they call growing old.
- Karrot_Kream 7y ago
  I agree, this RFC seems to propose a great deal of different additions/changes to the HTTP protocol without a unifying reason why. But the committee/process is all in the open, through the IETF, so now is the time to voice your concerns! > Reading the RFC, this seems to make HTTP stateful The reasoning behind this seems to be that the alternatives right now are either polling or a homegrown websocket based protocol. The authors argue that rather than continuing to let different implementors make bespoke or otherwise non-standard polling/subscription based websocket implementations, to standardize on a RESTful way to subscribe to a stream of updates. > It also uses PUT to patch things, but then why not use PATCH ? You could say it's non standard, but at this point, everybody uses it. Plus their stuff is apparently deviate from the original standard as well by allowing headers after the first line of the payload and introducing the forGET command. I've personally seen both PUT and PATCH used for updates, so this didn't seem particularly odd to me, and seemed more like a nod to one particular method of updates. But yes, the overall RFC is proposing to modify HTTP from a state transfer protocol to a state synchronization protocol, so that clients and servers have to hold onto state and send diffs between their internal states, and then implement some reconciliation algorithm (e.g. OTs or CRDTs) to merge state. This seems like it is in response to a myriad of bespoke long-polling or websocket based update mechanisms. > They also mention a really cool RFC on a JSON patch format: https://datatracker.ietf.org/doc/html/rfc6902 https://datatracker.ietf.org/doc/html/rfc6902 Yup! Super cool right? > I'm reading RFC and getting excited about it. Damn, that must be what they call growing old. Well, you could do that, or you could read yet another article about startup financials, which is all that seems to trend on HN these days ;)
jkarneges 7y ago
> When a resource is changed by one client or server, all other clients and servers update. This reminds me a little bit of a project I started some years ago: http://liveresource.org/ http://liveresource.org/ It wasn't nearly as fancy as Braid. Just a way to get a URL's current content and then listen for changes. Kinda like Firebase, but for the web. Didn't get much traction though.
- Arathorn 7y ago
  The team behind matrix.org had one prior to Matrix very similar to this too (albeit longpolling) called Glow. It was basically simple & stupid pubsub on top of HTTP: you could GET an arbitrary url, and whenever anyone PUT stuff within that url tree your GET would return. It worked well enough to build a pretty massive instant messaging platform on top of it, but the lack of schema and lack of intelligent query language got a bit frustrating. Some of the ideas made it into Matrix though. Braid looks cool; we've hoped someone would layer OT or CRDT semantics on top of Matrix but it hasn't really happened yet (unless you count Matrix itself as a set of add-only monotonic DAG CRDTs, which I guess it is). Eitherway, perhaps going in at a lower level like Braid has legs; time will tell :)
- toomim 7y ago
  This is very interesting! Thank you for posting it. You have clearly thought the problem through, and we'd love to get you more involved in the consensus process.
skybrian 7y ago
What happens when you have OT and CRDT interoperating? They are different algorithms, so wouldn't they see different results?
- toomim 7y ago
  The trick is that they only need to agree on how multiple simultaneous edits merge. Each URL specifies a Merge-Type. If the algorithms implement it, they can merge conistently.
  - skybrian 7y ago
    It seems like that's saying each client has to implement all the algorithms in use? So, no magic here, but a choice among standardized algorithms?
    - toomim 7y ago
      Almost -- you can actually have different algorithms that still merge the same way. See our interoperability demo here: https://braid.news/demo/interoperate https://braid.news/demo/interoperate This demo shows a CRDT and OT system interoperating. They use different algorithms, but merge (almost) the same way! (I say "almost" because we aren't using the same sorting function to break ties when two people edit in the same location. But this could be fixed.) In practice, you can certainly specify a merge-type in terms of an algorithm, by saying "this resource merges in the way that the Automerge algorithm merges." But you can also state it abstractly -- for instance, as we do here: https://braid.news/demo/interact#a-merge-type-defines-how-to-flatten-bubbles-in-space https://braid.news/demo/interact#a-merge-type-defines-how-to...
User23 7y ago
Looks interesting, but where is the proof? Distributed consensus is HARD. Without a formal proof why should I trust this? TLA+ would be great, but I'd be happy with anything that demonstrated formal correctness.
- toomim 7y ago
  Braid itself is just a neutral protocol— the proof you want applies to the particular CRDT or OT algorithm that you use with it. For instance, you can use it with ShareDB, or Automerge. Both of these synchronizers are quite robust, and prove correctness with fuzz testing. Links: https://github.com/automerge/automerge https://github.com/automerge/automerge https://github.com/share/sharedb https://github.com/share/sharedb
devj 7y ago
How does it compare with CouchDB Replication protocol - https://docs.couchdb.org/en/stable/replication/protocol.html https://docs.couchdb.org/en/stable/replication/protocol.html?

196 points by tobr 7y ago

deleted 7y ago

[deleted]

"Braid is an effort to incorporate new distributed technologies into the existing World-Wide Web. We find consensus on extensions to today's web standards that support distributed web technologies. We work in the IETF's HTTP Working Group. You can join the effort. The Braid Protocol is a set of extensions to HTTP, which transform it from a state transfer protocol into a state synchronization protocol. When a resource is changed by one client or server, all other clients and servers update. Braid supports Operational Transform and CRDTs at web URLs, enabling peer-to-peer, offline-capable web applications."

deleted 7y ago

[deleted]

ChrisRus 7y ago

This looks very interesting indeed. I am currently working on a system that allows hierarchical system modeling and evaluation of so-called "observable process models". I can easily understand leveraging something like this over HTTP to reduce implementation details of model and state transfers.

heavenlyblue 7y ago
What's an "observable process model"?
toomim 7y ago
Oh, thank you for sharing! I would love to see an example of where you are dealing with model and state transfers, so that we can make sure that the protocol we are building supports it. Is there anything more you can say about this?

svnpenn 7y ago

I wrote 2 implementations for ETag, one using plain text files and one using a database file: https://cup.github.io/autumn/talk-conditional-request https://cup.github.io/autumn/talk-conditional-request My implementations are in PHP, but they could easily be adapted to other languages. I was surprised when I found that cURL really doesnt have support for this. Yeah, you can do something like this: $ curl -I -H 'If-None-Match: "109-55035a2e5a100"' \ > speedtest.lax.hivelocity.net HTTP/1.1 304 Not Modified but its of limited usefulness. What you need is a cache storing all the requests youve made, so that the next time you make a request the cache can be checked. Without the cache its pointless. Also a problem is that some sites only return Last-Modified, not ETag: $ curl -I https://en.wikipedia.org/wiki/Main_Page last-modified: Sun, 03 Nov 2019 20:12:16 GMT and some dont return either: https://www.google.com https://www.google.com

codetrotter 7y ago

> Why "Braid"? > 1. It adds versioning—and time travel—to the web, just like the videogame Braid. That video game was the first thing I thought of when I read the name. Cool that it is one of the actual reasons they chose to name this that.

pm90 7y ago

Can someone with a mathematical background explain what the practical uses of this protocol are? It talks about time travel and state synchronization v/s state transfer. Is this an effort to create a protocol that e.g. allows for distributed systems over http instead of relying on "custom" implementations such as Paxos? (i'm pretty sure I'm misunderstanding this, please feel free to correct)

toomim 7y ago
Yes, the braid protocol could let you run a distributed system over HTTP. It lets you put a CRDT or OT behind any HTTP resource, which lets you distribute the resource, with multiple writers, and guarantee consistency after arbitrary edits. Each resource will still have a URL, with one particular hostname, but the actual state can live and be modified simultaneously on multiple hosts. The first thing you might use this for is collaborative editing. Braid can give you the power of Google Docs at any HTTP URL, without writing additional code. This also improves performance. Instead of using heuristics to determine when a cache needs to be reload (cache-control max-age, last-modified, etags), Braid will automatically push all updates to caches -- guaranteed. That means you never need to force-reload a page, or force-clear a cache. Also, updates are sent as minimal diffs, rather than re-sending the entire resource whenever it changes. This saves a lot of bandwidth and a lot of round-trip latency when loading a page. As a third practical example, Braid makes it very simple to read and write data from multiple web sites. By collapsing time, braid implementations let you write code that manipulates state at any URL as easily as a local variable. It doesn't matter whether state is located on your server, or someone else's server, or distributed on everyone's servers and clients. It's all equally easy to interact with. This also makes it easy to write a new UI for an existing site. As for Paxos, yes, CRDTs are an alternative to Paxos, and CRDTs can be used in Braid. CRDTs have some performance improvements over Paxos -- Paxos chooses a leader, and whenever the leader is unreachable, a new leader election takes place which requires a couple network round trips before any new edits can be broadcast. CRDTs are always editable, and edits can always be broadcast.
- sagichmal 7y ago
  > Braid can give you the power of Google Docs at any HTTP URL, without writing additional code. What implements the OT or CRDT logic? The webserver itself?

sansnomme 7y ago

Would it be correct to say that this is a CRDT protocol on the HTTP level, similar abstraction level to e.g. REST?

toomim 7y ago
Yes. One way to look at this is that HTTP is already very close to a CRDT or OT protocol -- it just needs a few new features. By adding those features into HTTP, we generalize HTTP and REST from being able to simply transfer state to being able to synchronize it, across arbitrary arbitrary edits, from multiple writers. HTTP: HyperText *Transfer* Protocol REST: REpresentational State *Transfer* HTSP: HyperText *Synchronization* Protocol RESS: REpresentational State *Synchronization*
- sansnomme 7y ago
  So stuff like PouchDB, Gunjs will now be trivial?
  - toomim 7y ago
    These are databases that support synchronization. They have to design their own custom protocol, because HTTP (without Braid) does not support synchronization. We want to add Braid support to PouchDB and Gunjs. Then they can interoperate, with one another, and with the rest of the web. You'll be able to build a distributed app that stores some data in Gunjs, and some in PouchDB, on different servers, on different websites. The differences between different synchronizing databases are captured in "Merge Types": https://raw.githubusercontent.com/braid-work/braid-spec/master/draft-toomim-httpbis-merge-types-00.txt https://raw.githubusercontent.com/braid-work/braid-spec/mast... Over time, I imagine that these databases will add support for each other's merge types, and then -- yes -- their abilities will be "trivial", and baked into most URLs of the web.

BiteCode_dev 7y ago

Reading the RFC, this seems to make HTTP stateful: "A subscription is different from a GET connection (e.g. a TCP connection, or HTTP/2 stream). If a client requests "Subscribe: keep-alive", then the subscription will be remembered even after the GET connection closes." It also uses PUT to patch things, but then why not use PATCH ? You could say it's non standard, but at this point, everybody uses it. Plus their stuff apparently deviates from the HTTP standard as well by allowing headers after the first line of the payload and introducing the forGET command. Or am I missing something ? Interesting anyway, especially the way they create of graph of unique ID to solve the ordering problem. Feels like Git. The flow of patch reminds me of react-redux. Plus it's great to have more geeky technical things on HN. I'm missing it, among all the news and start up things. They also mention a really cool RFC on a JSON patch format: https://datatracker.ietf.org/doc/html/rfc6902 https://datatracker.ietf.org/doc/html/rfc6902 I'm reading RFC and getting excited about it. Damn, that must be what they call growing old.

Karrot_Kream 7y ago
I agree, this RFC seems to propose a great deal of different additions/changes to the HTTP protocol without a unifying reason why. But the committee/process is all in the open, through the IETF, so now is the time to voice your concerns! > Reading the RFC, this seems to make HTTP stateful The reasoning behind this seems to be that the alternatives right now are either polling or a homegrown websocket based protocol. The authors argue that rather than continuing to let different implementors make bespoke or otherwise non-standard polling/subscription based websocket implementations, to standardize on a RESTful way to subscribe to a stream of updates. > It also uses PUT to patch things, but then why not use PATCH ? You could say it's non standard, but at this point, everybody uses it. Plus their stuff is apparently deviate from the original standard as well by allowing headers after the first line of the payload and introducing the forGET command. I've personally seen both PUT and PATCH used for updates, so this didn't seem particularly odd to me, and seemed more like a nod to one particular method of updates. But yes, the overall RFC is proposing to modify HTTP from a state transfer protocol to a state synchronization protocol, so that clients and servers have to hold onto state and send diffs between their internal states, and then implement some reconciliation algorithm (e.g. OTs or CRDTs) to merge state. This seems like it is in response to a myriad of bespoke long-polling or websocket based update mechanisms. > They also mention a really cool RFC on a JSON patch format: https://datatracker.ietf.org/doc/html/rfc6902 https://datatracker.ietf.org/doc/html/rfc6902 Yup! Super cool right? > I'm reading RFC and getting excited about it. Damn, that must be what they call growing old. Well, you could do that, or you could read yet another article about startup financials, which is all that seems to trend on HN these days ;)

jkarneges 7y ago

> When a resource is changed by one client or server, all other clients and servers update. This reminds me a little bit of a project I started some years ago: http://liveresource.org/ http://liveresource.org/ It wasn't nearly as fancy as Braid. Just a way to get a URL's current content and then listen for changes. Kinda like Firebase, but for the web. Didn't get much traction though.

Arathorn 7y ago
The team behind matrix.org had one prior to Matrix very similar to this too (albeit longpolling) called Glow. It was basically simple & stupid pubsub on top of HTTP: you could GET an arbitrary url, and whenever anyone PUT stuff within that url tree your GET would return. It worked well enough to build a pretty massive instant messaging platform on top of it, but the lack of schema and lack of intelligent query language got a bit frustrating. Some of the ideas made it into Matrix though. Braid looks cool; we've hoped someone would layer OT or CRDT semantics on top of Matrix but it hasn't really happened yet (unless you count Matrix itself as a set of add-only monotonic DAG CRDTs, which I guess it is). Eitherway, perhaps going in at a lower level like Braid has legs; time will tell :)
toomim 7y ago
This is very interesting! Thank you for posting it. You have clearly thought the problem through, and we'd love to get you more involved in the consensus process.

skybrian 7y ago

What happens when you have OT and CRDT interoperating? They are different algorithms, so wouldn't they see different results?

toomim 7y ago
The trick is that they only need to agree on how multiple simultaneous edits merge. Each URL specifies a Merge-Type. If the algorithms implement it, they can merge conistently.
- skybrian 7y ago
  It seems like that's saying each client has to implement all the algorithms in use? So, no magic here, but a choice among standardized algorithms?
  - toomim 7y ago
    Almost -- you can actually have different algorithms that still merge the same way. See our interoperability demo here: https://braid.news/demo/interoperate https://braid.news/demo/interoperate This demo shows a CRDT and OT system interoperating. They use different algorithms, but merge (almost) the same way! (I say "almost" because we aren't using the same sorting function to break ties when two people edit in the same location. But this could be fixed.) In practice, you can certainly specify a merge-type in terms of an algorithm, by saying "this resource merges in the way that the Automerge algorithm merges." But you can also state it abstractly -- for instance, as we do here: https://braid.news/demo/interact#a-merge-type-defines-how-to-flatten-bubbles-in-space https://braid.news/demo/interact#a-merge-type-defines-how-to...

User23 7y ago

Looks interesting, but where is the proof? Distributed consensus is HARD. Without a formal proof why should I trust this? TLA+ would be great, but I'd be happy with anything that demonstrated formal correctness.

toomim 7y ago
Braid itself is just a neutral protocol— the proof you want applies to the particular CRDT or OT algorithm that you use with it. For instance, you can use it with ShareDB, or Automerge. Both of these synchronizers are quite robust, and prove correctness with fuzz testing. Links: https://github.com/automerge/automerge https://github.com/automerge/automerge https://github.com/share/sharedb https://github.com/share/sharedb

devj 7y ago

How does it compare with CouchDB Replication protocol - https://docs.couchdb.org/en/stable/replication/protocol.html https://docs.couchdb.org/en/stable/replication/protocol.html?