-
Notifications
You must be signed in to change notification settings - Fork 16
/
draft-toomim-httpbis-merge-types-00.txt
367 lines (267 loc) · 14.4 KB
/
draft-toomim-httpbis-merge-types-00.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
Internet-Draft M. Toomim
Expires: Mar 8, 2020 Invisible College
Intended status: Proposed Standard M. Milutinovic
UC Berkeley
B. Bellomy
Invisible College
Nov 18, 2019
Merge Types
draft-toomim-httpbis-merge-types-00
Abstract
Merge Types specify how to merge multiple simultaneous edits to a
resource. This happens when two computers edit the same state over a
network with latency. A Merge Type specifies how to merge
conflicting changes. If the computers implement and agree upon the
same Merge Type, then they can guarantee to reach a consistent state,
after arbitrary edits, eventually.
You can define new Merge Types. This document defines Merge Types,
the structure of the Merge Type system, and IANA registration
procedures for Merge Types.
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), its areas, and its working groups. Note that
other groups may also distribute working documents as
Internet-Drafts. The list of current Internet-Drafts is at
http://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."
The list of current Internet-Drafts can be accessed at
https://www.ietf.org/1id-abstracts.html
The list of Internet-Draft Shadow Directories can be accessed at
https://www.ietf.org/shadow.html
Table of Contents
1. Introduction ...................................................4
1.1. Merge Types vary across applications .......................4
1.2. A Merge Type is specified as a function ....................5
2. Definitions .....................................................5
3. Merge Type Naming ...............................................5
4. IANA Considerations .............................................6
4.1. Merge Type Registry ........................................6
4.1.1. Procedure ...........................................6
4.1.2. Registrations .......................................6
4.1.3. Comments on Merge Type Registrations ................6
4.1.4. Change Procedures ...................................6
5. Security Considerations .........................................7
6. Conventions .....................................................8
7. Copyright Notice ................................................8
8. References ......................................................8
8.1. Normative References .......................................8
8.2. Informative References .....................................8
1. Introduction
In a version history, a merge type defines the output of a version
that is derived from two or more parent versions:
_
Time: | birds
| / \
| dogs cats
| \ /
V dogcats <-- merged version
This can be ambiguous if two or more edits overlap, and edit the same
thing in different ways. It is desireable if all computers resolve
ambiguities in the same way, because then they will achieve
consistent results. In the example above, one person replaced "bird"
with "dog", while the other replaced it with "cat", creating an
ambiguity, which the Merge Type resolved by merging these edits
together into "dogcats". Some other Merge Type might resolve this
ambiguity differently.
Currently popular approaches are using conflict-free replicated data
types [CRDT] or operational transformation [OT]. Different
algorithms that merge in different ways. Different applications need
different parts of their data to merge in different ways. The Merge
Type specifies the outcome of a merge. Different algorithms can
implement the same Merge Type to interoperate.
If a Merge Type is specified for a region of data, and all computers
implement that Merge Type, then they can guarantee to obtain the same
resulting state, no matter the order that events arrive over the
network, or the algorithms they use to implement the Merge Types.
This document defines how to specify a Merge Type within a
standardized naming scheme.
1.1. Merge Types vary across applications
Different resources merge in different ways, and can use different
merge types. For example, if a string represents a collaborative
text document, then parallel edits should be merged together. But if
a string represents a database entry ID and it is modified by two
requests simultaneously, the appropriate behavior is to choose one or
the other.
Similarly, if the resource is a number that represents a bank account
balance, then it should merge multiple simultaneous debits by adding
the amounts of the debits together.
Thus, it is nice to re-use a Merge Type across multiple types of
data; and each application has different needs for how its data
should merge.
1.2. A Merge Type is specified as a function
A Merge Type is a function that produces a merged state when provided
with any set of parent versions:
Merge Type
(parent, parent, ..) -> merged state
A Merge Type must be a deterministic function. Given the same set of
parents that descend from the same version history, it should always
return the same resulting merged state. This guarantees eventual
consistency.
To compute the result, a Merge Type has access to the entire version
history that preceded each of the parents, but the function cannot
depend on state outside that version history or its specification.
A Merge Type might only work on a particular Content-Type. For
instance, a "counter" Merge Type only works on numbers. A Merge Type
SHOULD state any limitations in the set of states that it is capable
of operating upon, and any assumptions it makes about the data.
But given that it has data that meets those assumptions, a Merge Type
MUST return a result when merging any set of versions. A Merge Type
cannot perform any validation on new versions.
2. Definitions
For the purpose of this document we define "synchronization" as the
resolution of conflicts. There are multiple approaches to resolving
conflicts and we define "Merge Type" an identifier that corresponds
to an approach of resolving conflicts.
3. Merge Type Naming
Naming of Merge Type follows naming requirements of media types as
described in Section 4.2. of [RFC6838] with the following exception:
Merge Type names consist only of a type-name without a sub-type.
Similarly, Merge Type parameters follow Section 4.3. of [RFC6838].
Example:
automerge-counter
sharedb-json; variant=1
biggest-wins; sortby=versionid
4. IANA Considerations
4.1. 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
<http://www.iana.org/assignments/merge-types>.
4.1.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
Values to be added to this namespace require IETF Review (see
[RFC5226], Section 4.1).
4.1.2. Registrations
4.1.3. Comments on Merge Type Registrations
Comments on registered Merge Types may be submitted by members of the
community to the IANA at [email protected]. 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.
4.1.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.
5. 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 4.1.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 user's privacy
in some way.
o A Merge Type should be considered in concert with a Validator.
For instance, it is possible for two transactions A and B to both
be valid individually, but when merged, the result is not valid.
For instance, if a bank account has $1, then two simultaneous
debits of $1 are both valid individually, but the resulting
merger, yielding -$2, drains the bank account balance below $0.
This is the double-spend problem. A system using Merge Types
SHOULD be aware of how its Merge Types interact with its
Validators.
6. Conventions
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in [RFC2119].
7. Copyright Notice
Copyright (c) 2019 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
(http://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 Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License.
8. References
8.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.
[RFC5226] Narten, T. and H. Alvestrand, "Guidelines for Writing an
IANA Considerations Section in RFCs", BCP 26, RFC 5226,
May 2008.
8.2. Informative References
[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.
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: [email protected]
Web: https://invisible.college/@toomim
Mitar Milutinovic
UC Berkeley, EECS Department
775 Soda Hall #1776
Berkeley, CA 94720-1776
EMail: [email protected]
Web: https://mitar.tnode.com/
Bryn Bellomy
Invisible College, Berkeley
2053 Berkeley Way
Berkeley, CA 94704
EMail: [email protected]
Web: https://invisible.college/@bryn