Internet-Draft M. Toomim Expires: 6 May 2027 Invisible College Intended status: Proposed Standard M. Milutinovic UC Berkeley B. Bellomy Invisible College 2 November 2026 Consistent Merge Types for HTTP draft-toomim-httpbis-braid-merge-types-00 Abstract Merge Types specify how to merge parallel edits to a resource. Parallel edits happen when two peers edit the same state over a network with latency. A Merge Type specifies how to merge conflicting changes. If the peers implement and agree upon the same Merge Type, then they will reach a consistent state eventually, whatever edits they make. This document defines Merge Types, the structure of the Merge Type system, the Merge-Type header, and IANA registration procedures for Merge Types. Other specifications can define more Merge Types, in the registry that this document creates. This document is one of the Braid-HTTP extensions, which work alone or together; together they make HTTP a state synchronization protocol. About This Document This note is to be removed before publishing as an RFC. Discussion of this document takes place on the HTTP Working Group mailing list (ietf-http-wg@w3.org). The source of this document, and an issue tracker, are at https://github.com/braid-org/braid-spec. Status of this Memo This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet-Drafts is at https://datatracker.ietf.org/drafts/current/. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." This Internet-Draft will expire on 6 May 2027. Copyright Notice Copyright (c) 2026 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Revised BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Revised BSD License. Table of Contents 1. Introduction ...................................................4 1.1. Merge Types vary across applications .........................5 1.2. A Merge Type is specified as a function ......................5 2. Definitions ....................................................6 3. Merge Type Naming ..............................................6 4. The Merge-Type Header ..........................................6 5. IANA Considerations ............................................7 5.1. Merge-Type Header Field Registration .........................7 5.2. Merge Type Registry ..........................................7 5.2.1. Procedure ..................................................7 5.2.2. Registrations ..............................................8 5.2.3. Comments on Merge Type Registrations .......................8 5.2.4. Change Procedures ..........................................8 6. Implementation Status ..........................................9 7. Security Considerations ........................................9 8. Conventions ...................................................10 9. References ....................................................10 9.1. Normative References ........................................10 9.2. Informative References ......................................11 1. Introduction Merge Types specify how peers merge parallel edits consistently. In a version history [VERSIONS], a Merge Type defines the state of a resource at a version derived from two or more parent versions: _ Time: | birds | / \ | dogs cats | \ / V dogcats <-- merged state The merged state can be ambiguous if two or more edits overlap, and edit the same thing in different ways. All peers should resolve ambiguities in the same way, so that they reach consistent results. In the example above, one person replaced "bird" with "dog", while the other replaced it with "cat". The Merge Type resolved this ambiguity by merging both edits into "dogcats". Some other Merge Type might resolve this ambiguity differently. Popular approaches to merging include conflict-free replicated data types [CRDT] and operational transformation [OT]. Different algorithms merge in different ways. Different applications need different parts of their data to merge in different ways. A Merge Type specifies the outcome of a merge. Different algorithms can implement the same Merge Type to interoperate. If all peers merge a history of updates with the same Merge Type, then they will be consistent, no matter the order in which the updates arrive over the network, or the algorithms that the peers use to implement that Merge Type. This document defines how to specify a Merge Type within a standardized naming scheme, and how a client or server says which Merge Type it uses, with the Merge-Type header. Merge Types are one of the Braid-HTTP extensions [BRAID-HTTP]. To merge, a peer needs two of the others: Versions [VERSIONS], to know which edits happened in parallel, and Updates [UPDATES], to know what each edit changed. 1.1. Merge Types vary across applications Different applications merge different resources in different ways, and can use different Merge Types. For example, if a string represents a collaborative text document, then the application should merge parallel edits together. But if a string represents a database entry ID, and two requests modify it in parallel, then the application should choose one or the other. Similarly, if a number represents a bank account balance, then the application should merge parallel debits by adding their amounts together. So each application has different needs for how its data should merge. And it is useful to reuse a Merge Type across multiple types of data. 1.2. A Merge Type is specified as a function A Merge Type is a function that takes an edit history, and returns a merged state: Merge Type (edit history) -> merged state A Merge Type MUST be a deterministic function. Given the same edit history, it always returns the same merged state. So peers that have received the same edits reach the same state. Along with a guarantee that every edit reaches every peer, this gives strong eventual consistency [CRDT]. The edit history holds every edit that led to the parent versions of the merge. In the example above, to merge "dogs" and "cats" into "dogcats", the Merge Type needs to know that each edit replaced "bird". The function MUST NOT depend on state outside that edit history or its specification. A Merge Type might only work on some media types, or some kinds of data. For instance, a "counter" Merge Type only works on numbers. A Merge Type's specification SHOULD state any limits on the states that the Merge Type can operate on, and any assumptions that it makes about the data. If the data meets those assumptions, a Merge Type MUST return a result when it merges any set of versions. A Merge Type cannot reject a new version. 2. Definitions For the purpose of this document we define a "merge" as computing the state at a version that has two or more parent versions. A merge works from the edit history that led to the parents, and resolves any conflicts between their edits. There are multiple approaches to resolving conflicts. We call each one a "Merge Type", and give each a name that identifies it. 3. Merge Type Naming Merge Type names follow the naming requirements for media types in Section 4.2 of [RFC6838], with two exceptions: Merge Type names consist only of a type-name without a sub-type, and they begin with a letter, so that each name is a Token [RFC9651]. Merge Type parameters are Parameters of that Token, as defined in [RFC9651]. Example: automerge-counter sharedb-json;variant=1 biggest-wins;sortby=versionid 4. The Merge-Type Header The Merge-Type header names the Merge Type that peers use to merge parallel versions. A client or server can send it with any update [UPDATES], in a request such as a PUT, or in a response: Request: PUT /chat Version: ("ej4lhb9z78") | Update Parents: ("oakwn5b8qh" "uc9zwhw7mf") | Content-Type: text/plain | Merge-Type: dt | Content-Length: 13 | | Hi, everyone! | | Snapshot Response: HTTP/1.1 200 OK Here the new version has two parents, and "dt" is the Merge Type that merges them. The value of Merge-Type is a Structured Field Item [RFC9651]: a Token that names the Merge Type, with any parameters, as in Section 3. A server can offer a resource's history in more than one Merge Type, as variants of that history. A client chooses one by sending Merge-Type in its request. For instance, under one Merge Type, the server can leave parallel versions for the client to merge, and under another, it can present the same versions as a single path. 5. IANA Considerations 5.1. Merge-Type Header Field Registration This document registers the following header field in the "Hypertext Transfer Protocol (HTTP) Field Name Registry", maintained at , as described in Section 16.3.1 of [RFC9110]: Field Name: Merge-Type Status: permanent Structured Type: Item Reference: Section 4 of this document 5.2. Merge Type Registry The "Merge Type Registry" defines the namespace for the Merge Type names and refers to their corresponding specifications. The registry will be created and maintained at . 5.2.1. Procedure Registration of a Merge Type MUST include the following fields: o Type name o Required parameters o Optional parameters o Description o Security considerations o Interoperability considerations o Obsolete/Non-obsolete status o Published specification o Person & email address to contact for further information IANA adds values to this namespace under the "Specification Required" policy (see [RFC8126], Section 4.6), so that anyone can register a Merge Type defined outside the IETF. 5.2.2. Registrations This document registers no Merge Types. 5.2.3. Comments on Merge Type Registrations Comments on registered Merge Types may be submitted by members of the community to the IANA at iana@iana.org. These comments will be reviewed by the Merge Types reviewer and then passed on to the "owner" of the Merge Type if possible. Submitters of comments may request that their comment be attached to the Merge Type registration itself; if the IANA, in consultation with the Merge Types reviewer, approves, the comment will be made accessible in conjunction with the type registration. 5.2.4. Change Procedures Once a Merge Type has been published by the IANA, the owner may request a change to its definition. The same procedure that would be appropriate for the original registration request is used to process a change request. Merge Type registrations may not be deleted; Merge Types that are no longer believed appropriate for use can be declared OBSOLETE; such Merge Types will be clearly marked in the list published by the IANA. Significant changes to a Merge Type's definition should be requested only when there are serious omissions or errors in the published specification. When review is required, a change request may be denied if it renders entities that were valid under the previous definition invalid under the new definition. The owner of a Merge Type may pass responsibility to another person or agency by informing the IANA; this can be done without discussion or review. The IESG may reassign responsibility for a Merge Type. The most common case of this will be to enable changes to be made to types where the author of the registration has died, moved out of contact, or is otherwise unable to make changes that are important to the community. 6. Implementation Status This section records the known implementations of this document, as [RFC7942] describes. It is to be removed before publishing as an RFC. - braid-text [BRAID-TEXT] implements three Merge Types for text: "simpleton" [SIMPLETON], for light clients, "dt", which merges with Diamond Types [DIAMOND-TYPES], and "yjs", which merges with Yjs [YJS]. - braid-blob [BRAID-BLOB] implements "aww", arbitrary writer wins [AWW], for binary files. - braidfs [BRAIDFS] synchronizes a folder of local files, merging text with "dt" and other files with "aww". - braid-chrome [BRAID-CHROME], a browser extension for Chrome and Firefox, merges text with "dt" and "simpleton", to edit pages collaboratively. - Editor plugins for Emacs [BRAID-EMACS], Neovim [BRAID-NEOVIM], and VS Code [BRAID-VSCODE] merge text with "simpleton", to edit any braid-text resource collaboratively. - antimatter [ANTIMATTER] and antimatter_wiki [ANTIMATTER-WIKI] implement "sync9" [SYNC9], a peer-to-peer CRDT for text and JSON. 7. Security Considerations An analysis of security issues SHOULD be done for all registered Merge Types. However, regardless of what security analysis has or has not been done, all descriptions of security issues MUST be as accurate as possible. In particular, the security considerations MUST NOT state that there are "no security issues associated with this Merge Type". Security considerations for Merge Types MAY state that "the security issues associated with this Merge Type have not been assessed". There is absolutely no requirement that Merge Types registered be secure or completely free from risks. Nevertheless, all known security risks MUST be identified in the registration of a Merge Type. The security considerations section of all registrations is subject to continuing evaluation and modification, and in particular MAY be extended by use of the "comments on Merge Types" mechanism described in Section 5.2.3 above. Some of the issues that need to be examined and described in a security analysis of a Merge Type are: o Merge Types might operate in a way that, while not directly harmful, may result in disclosure of information that either facilitates a subsequent attack or else violates a user's privacy in some way. o The analysis should consider the Merge Type together with the rules that an application uses to accept or reject updates. Two updates A and B can each be valid alone, and still merge into a result that is not valid. For instance, if a bank account holds $1, then two parallel debits of $1 are each valid alone, but together they debit $2, and drain the balance below $0. This is the double-spend problem. A system using Merge Types SHOULD be aware of how its Merge Types interact with the rules it uses to accept or reject updates. 8. Conventions The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here. 9. References 9.1. Normative References [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. [RFC6838] Freed, N., Klensin, J., and T. Hansen, "Media Type Specifications and Registration Procedures", BCP 13, RFC 6838, January 2013. [RFC8126] Cotton, M., Leiba, B., and T. Narten, "Guidelines for Writing an IANA Considerations Section in RFCs", BCP 26, RFC 8126, June 2017. [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, May 2017. [RFC9110] Fielding, R., Ed., Nottingham, M., Ed., and J. Reschke, Ed., "HTTP Semantics", STD 97, RFC 9110, June 2022. [RFC9651] Nottingham, M. and P-H. Kamp, "Structured Field Values for HTTP", RFC 9651, September 2024. [UPDATES] Toomim, M., "Replayable Updates for HTTP", draft-toomim-httpbis-braid-updates-00, work in progress, November 2026. [VERSIONS] Toomim, M., "Resource Versioning for HTTP", draft-toomim-httpbis-braid-versions-00, work in progress, November 2026. 9.2. Informative References [BRAID-HTTP] Toomim, M., "Braid-HTTP: State Synchronization for HTTP", draft-toomim-httpbis-braid-http-05, work in progress, November 2026. [CRDT] Shapiro, M., Preguica, N., Baquero, C., and M. Zawirski, "Conflict-free replicated data types", in SSS'11 Proceedings of the 13th international conference on Stabilization, safety, and security of distributed systems, October 2011. [OT] Ellis, C. A., and S. J. Gibbs, "Concurrency control in groupware systems", in SIGMOD '89 Proceedings of the 1989 ACM SIGMOD international conference on Management of data, June 1989. [RFC7942] Sheffer, Y. and A. Farrel, "Improving Awareness of Running Code: The Implementation Status Section", BCP 205, RFC 7942, July 2016. [AWW] braid.org, "Arbitrary Writer Wins", . [BRAID-BLOB] braid.org, "braid-blob", . [BRAID-TEXT] braid.org, "braid-text", . [BRAIDFS] braid.org, "braidfs", . [DIAMOND-TYPES] Gentle, J., "Diamond Types", . [SIMPLETON] braid.org, "Simpleton", . [SYNC9] braid.org, "Sync9: a Peer-to-Peer Synchronizer", . [BRAID-CHROME] braid.org, "braid-chrome", . [ANTIMATTER] braid.org, "antimatter", . [ANTIMATTER-WIKI] braid.org, "antimatter_wiki", . [BRAID-EMACS] braid.org, "braid-emacs", . [BRAID-NEOVIM] braid.org, "braid-neovim", . [BRAID-VSCODE] braid.org, "braid-vscode", . [YJS] Jahns, K., "Yjs", . Authors' Addresses For more information, the authors of this document are best contacted via Internet mail: Michael Toomim Invisible College, Berkeley 2053 Berkeley Way Berkeley, CA 94704 EMail: toomim@gmail.com Web: https://invisible.college/@toomim Mitar Milutinovic UC Berkeley, EECS Department 775 Soda Hall #1776 Berkeley, CA 94720-1776 EMail: mitar.ietf@tnode.com Web: https://mitar.tnode.com/ Bryn Bellomy Invisible College, Berkeley 2053 Berkeley Way Berkeley, CA 94704 EMail: bryn@signals.io Web: https://invisible.college/@bryn