Swarm Replicated Object Notation is a format for distributed live data. RON's focus is on continuous data synchronization. Every RON object may naturally have an unlimited number of replicas that synchronize incrementally, mostly in real-time. RON data always merges correctly and deterministically.
RON is information-centric: it aims to liberate the data from its location, storage, application or transport. There is no "master" replica, no "source of truth". Every event has an origin, but every replica is as good as the other one. Every single object, event or data type is uniquely identified and globally referenceable. RON metadata makes objects completely independent of the context. A program may read RON object versions and/or updates from the network, filesystem, database, message bus and/or local cache, in any order, and merge them correctly.
Consider JSON. It expresses relations by element positioning:
{
"foo": {
"bar": 1
}
}
RON may express that state as:
*lww #1TUAQ+gritzko @` :bar = 1;
#(R @` :foo > (Q;
Those are two RON ops:
bar
set to 1
(on
2017-10-31 10:26:00 UTC, by gritzko),foo
pointing to the first object
(10:27:00, by gritzko).Each op is a tuple of four globally-unique UUIDs for its data type, object, event and location, plus some number of value atoms. You may not see any UUIDs in the above example, initially. The notation does a lot to compress that metadata away.
These are the key features of RON:
> 1TUAQ+gritzko
), thus RON can
express object graph structures beyond simple nesting. Overall, RON relates
pieces of data by their UUIDs. Thanks to that, RON data can be cached
locally, updated incrementally and edited while offline.lww(state,change) = new_state
. Reducers tolerate partial order of
updates. Hence, all ops are applied immediately, without any linearization by
a central server.gritzko
in 1TUAQ+gritzko
).Consider the above frame uncompressed:
*lww #1TUAQ+gritzko @1TUAQ+gritzko :bar = 1;
*lww #1TUAR+gritzko @1TUAR+gritzko :foo > 1TUAQ+gritzko;
One may say, what metadata solves is naming things and cache invalidation. What RON solves is compressing that metadata.
RON makes no strong assumptions about consistency guarantees: linearized, causal-order or gossip environments are all fine (certain restrictions apply, see below). Once all the object's ops are propagated to all the object's replicas, replicas converge to the same state. RON formal model makes this process correct. RON wire format makes this process efficient.
Swarm RON formal model has five key components:
An UUID is a globally unique 128-bit identifier. An UUID consists of two 60-bit parts: value and origin. 4+4 bits are reserved for flags. There are four UUID types:
1TUAQ+gritzko
, value
is a monotonous counter 1TUAQ
, origin is a a replica id gritzko
,
roughly corresponds to RFC4122 v1 UUIDs,1TUAQ-gritzko
),foo
, lww
, bar
(global), MyVariable$gritzko
(scoped),4Js8lam4LB%kj529sMEsl
, both parts are hash sum bits).An op is an immutable atomic unit of data change. An op is a tuple of four or more atoms. First four atoms of an op are UUIDs forming the op's key.
These UUIDs are:
lww
a last-write-wins object,1TUAQ+gritzko
,1TUAQ+gritzko
andbar
.Other atoms (any number, any type) form the op's value. Op atoms types are:
Importantly, an op goes under one of four terms:
A frame is an ordered collection of ops, a transactional unit of data
A reducer is a RON term for a "data type"; reducers define how object state is changed by new ops
a reducer is a pure function: f(state_frame, change_frame) -> new_state_frame
, where frames are either empty frames or single ops or
products of past reductions by the same reducer,
reducers are:
f( f(state, op1), op2 ) == f( state, patch )
where patch == f(op1,op2)
f(f(state,a),b) == f(f(state,b),a)
, assuming a
and b
originated concurrently at different replicas,f(state, op1) == f(f(state, op1), op1) == f(state, f(op1, op1))
, etc.optionally, reducers may have stronger guarantees, e.g. full commutativity (tolerates causality violations),
a frame could be an op, a patch or a complete state. Hence, a baseline reducer can "switch gears" from pure op-based CRDT mode to state-based CRDT to delta-based, e.g.
f(state, op)
is op-basedf(state1, state2)
is state-basedf(state, patch)
is delta-baseda mapper translates a replicated object's state frame into other formats
Single ops assume causally consistent delivery. RON implies causal consistency by default. Although, nothing prevents it from running in a linearized ACIDic or gossip environment. That only relaxes (or restricts) the choice of reducers.
Design goals for the RON wire format is to be reasonably readable and reasonably compact. No less human-readable than regular expressions. No less compact than (say) three times plain JSON (and at least three times more compact than JSON with comparable amounts of metadata).
The syntax outline:
1
3.1415
, 1.0e+6
строка\n线\t\u7ebf\n라인
,
except that '
(U+0027 APOSTROPHE) must be encoded as \u0027
or \'
1D4ICC-XU5eRJ
, 1TUAQ+gritzko
123e4567-e89b-12d3-a456-426655440000
and RON 1D4ICC-XU5eRJ
)0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz~
*lww #1D4ICC-XU5eRJ @1D4ICC2-XU5eRJ :keyA 'valueA'
*
starts a data type UUID#
starts an object UUID@
starts an op's own event UUID:
starts a location UUID=
starts an integer'
starts and ends a string;
may occur inside a string if prefixed by backslash — \'
^
starts a float (e-notation)>
starts an UUID!
ends a frame header op (a reduced chunk has one header op)?
ends a query header op (a subscription frame has a header),
ends a reduced op (optional);
ends a raw op.
ends a frame (required for streaming transports, e.g. TCP)1D4ICCE+XU5eRJ
gets compressed to {E
if preceded by 1D4ICC+XU5eRJ
(symbols ([{}])
corespond to 4,5,..9 symbols of shared prefix)Consider a simple JSON object:
{"keyA":"valueA", "keyB":"valueB"}
A RON frame for that object will have three ops: one frame header op and two key-value ops. In the tabular form, that frame may look like:
type object event location value
-----------------------------------------------------
*lww #1D4ICC+XU5eRJ @1D4ICCE+XU5eRJ :0 !
*lww #1D4ICC+XU5eRJ @1D4ICCE+XU5eRJ :keyA 'valueA'
*lww #1D4ICC+XU5eRJ @1D4ICC1+XU5eRJ :keyB 'valueB'
There are lots of repeating bits here. We may skip repeating UUIDs and prefix-compress close UUIDs. The compressed frame will be just a bit longer than bare JSON:
*lww#1D4ICC+XU5eRJ@`{E! :keyA'valueA' @{1:keyB'valueB'
The frame contains twelve UUIDs (6 distinct UUIDs, 3 distinct timestamps) and also the data. Despite the impressive amount of metadata, it takes less space than two RFC4122 UUIDs. The point becomes even clearer if we add the object UUID to JSON using the RFC4122 notation:
{"_id": "0651a600-2b49-11e6-8000-1696d3000000", "keyA":"valueA",
"keyB":"valueB"}
We may take this to the extreme if we consider the case of a CRDT-based collaborative real-time editor. Then, every letter in the text has its own UUID. With RFC4122 UUIDs and JSON, that is simply ridiculous. With RON, that is perfectly OK.
Consider "Hello world!" collaboratively written by two users, bart
and lisa
on 27 Nov 2017 around 9am GMT. A compressed RGA (Replicated Growable Array)
frame would look like:
*rga#1UQ8p+bart@1UQ8yk+lisa:0!
@(s+bart'H'@[r'e'@(t'l'@[T'l'@[i'o'
@(w+lisa' '@(x'w'@(y'o'@[1'r'@{a'l'@[2'd'@[k'!'
The txt
mapper may convert the RGA frame into text:
*txt #1UQ8p+bart @1UQ8yk+lisa 'Hello world!'
If nicely indented, the compressed frame is easier to read:
*rga #1UQ8p+bart @1UQ8yk+lisa :0 !
@(s+bart 'H'
@[r 'e'
@(t 'l'
@[T 'l'
@[i 'o'
@(w+lisa ' '
@(x 'w'
@(y 'o'
@[1 'r'
@{a 'l'
@[2 'd'
@[k '!'
If fully uncompressed, the frame takes more space:
*rga #1UQ8p+bart @1UQ8yk+lisa :0 !
*rga #1UQ8p+bart @1UQ8s+bart :0 'H'
*rga #1UQ8p+bart @1UQ8sr+bart :0 'e'
*rga #1UQ8p+bart @1UQ8t+bart :0 'l'
*rga #1UQ8p+bart @1UQ8tT+bart :0 'l'
*rga #1UQ8p+bart @1UQ8ti+bart :0 'o'
*rga #1UQ8p+bart @1UQ8w+lisa :0 ' '
*rga #1UQ8p+bart @1UQ8x+lisa :0 'w'
*rga #1UQ8p+bart @1UQ8y+lisa :0 'o'
*rga #1UQ8p+bart @1UQ8y1+lisa :0 'r'
*rga #1UQ8p+bart @1UQ8y1a+lisa :0 'l'
*rga #1UQ8p+bart @1UQ8y2+lisa :0 'd'
*rga #1UQ8p+bart @1UQ8yk+lisa :0 '!'
If rendered in JSON, the same document would probably start as
{
"_id": "3b127800-d350-11e7-8000-9a5db8000000",
"_version": "98f38f80-d351-11e7-8000-c2dde5000000",
...
...which is already 90% of the size of the entire compressed frame above. With idiomatic JSON, per-symbol metadata is both difficult and expensive.
So, let's be precise. Let's put UUIDs on everything. RON makes it possible.
The binary format is more efficient because of higher bit density; it is also simpler and safer to parse because of explicit field lengths. Obviously, it is not human-readable.
Like the text format, the binary one is only optimized for iteration. Because of compression, records are inevitably of variable length, so random access is not possible. Also, compression depends on iteration, as UUIDs get abbreviated relative to similar preceding UUIDs.
A binary RON frame starts with magic bytes RON2
and frame length. The rest
of the frame is a sequence of fields. Each field starts with a descriptor
specifying the type of the field and its length.
Frame length is serialized as a 32-bit big-endian integer. The maximum length of a frame is 2^31-1 bytes. If the length value has its most significant bit set to 1, then the frame is chunked. A chunked frame is followed by a continuation frame. A continuation frame has no magic bytes, just a 4-byte length field. The last continuation frame must have the m.s.b. of its length set to 0.
A descriptor's first byte spends four most significant (m.s.) bits to describe the type of the field, other four bits describe its length.
7 6 5 4 3 2 1 0
+----+----+----+----+----+----+----+----+
| major | minor | field |
| type | type | length |
+----+----+----+----+----+----+----+----+
128 64 32 16 8 4 2 1
80 40 20 10 8 4 2 1
Field descriptor major/minor type bits are set as follows:
00
RON op term,
0000
raw op,0001
reduced op,0010
header op,0011
query header op.01
UUID, uncompressed
0100
type (reducer) id,0101
object id,0110
event id,0111
ref/location id10
UUID, compressed (zipped)
1000
value UUID, zipped (note: not type id)1001
object id,1010
event id,1011
ref/location id11
Atom
1100
value UUID, uncompressed (lengths 1..16)1101
integer (big-endian, zigzag-coded, lengths 1, 2, 4, 8)1110
string (UTF-8, length 0..2^31-1)1111
float (IEEE 754-2008, binary 16, 32 or 64, lengths 2, 4, 8 resp)A descriptor's four least significant bits encode the length of the field in question. The length value given by a descriptor does not include the length of the descriptor itself.
If a field or a frame is 1 to 16 bytes long then it has its length coded
directly in the four l.s. bits of the descriptor. Zero stands for the length of
16 because most field types are limited to that length. Op terms specify no
length. With string atoms, zero denotes the presence of an extended length
field which is either 1 or 4 bytes long. The maximum allowed string length is
2Gb (31 bits). In case the descriptor byte is exactly 1110 0000
, the m.s.
bit of the next byte denotes the length of the extended length field (0
for
one, 1
for four bytes). The rest of the next byte (and possibly other three)
is a big-endian integer denoting the byte length of the string.
Consider a time value query frame: *now?.
0101 0010 0100 1111 0100 1110 0011 0010
)0000 0000 0000 0000 0000 0000 0000 0101
)0011 0000
)0100 0011
)now
RON UUID: 3 bytes (0000 1100 1011 0011 1110 1100
,
the "uncompressed" coding still trims a lot of zeroes, see below).As UUID length is up to 16 bytes, UUID fields never use a separate length number. UUID descriptors are always 1 byte long. The length of 0 stands for 16.
Length bits 0000
stand for:
An extended length record is used for strings cause those can be up to 2GB long. An extended length record is either 1 or four bytes. Four-byte record is a big-endian 32-bit int having its m.s. bit set to 1. Thus, strings of 127 bytes and shorter may use 1 byte long length record.
Op term fields may have cited length of 0000
or be skipped if they match the
previous op's term. Still, sometimes we want to introduce redundancy,
CRC/checksumming, hashing, etc. Exactly for this purpose we may use non-empty
terms. The checksumming method is specified by the field length (TODO).
Uncompressed UUIDs are not compressed relative to preceding UUIDs (not zipped). Still, zero bytes are skipped to optimize for some often-used cases. The skip pattern is determined based on the cited field length.
Namely, UUIDs 1..8 bytes long have the origin part set to zeros (all 8 bytes)
and the least significant bytes of the value also set to zeroes.
These are often-used "transcendent" name UUIDs (lww
, rga
, db
, now
, etc).
For example, lww
is the data type UUID for last-write-wins objects.
In the unabbreviated RON Base64 form, lww
is 0/lww0000000 00000000000
(see the UUID spec for the details).
UUIDs 9 to 15 bytes long have their l.s. value bytes set to zero. This case is optimized for arbitrary-precision timestamps.
UUIDs 16 bytes long are full 128-bit RON UUIDs.
Zipped UUIDs are serialized as deltas to similar past UUIDs. That provides significant savings when UUIDs come from the same source (same origin bytes) or have close timestamp values. Repeated UUIDs are simply skipped, same as in the Base64 notation.
The origin part is either reused in full or rewritten in full. That is decided by the field length (<9 reuse, >=9 rewrite). Implicitly, origin ids are considered uncompressible.
There are two zip modes: short and long. In the short mode, an UUID is compressed relative to the same kind of UUID in the previous op (e.g. event id relative to the previous event id). In the long mode, an UUID is compressed relative to a past uncompressed UUID. A decoder must remember 16 last uncompressed timestamp-based UUIDs (no names, no hashes), to perform uncompression. For encoders, that is optional.
A zipped UUID starts with a zip byte referencing the compression details.
Short zip byte:
7 6 5 4 3 2 1 0
+----+----+----+----+----+----+----+----+
| 0 | zero tail len| |
| | (half-bytes) | m.s. half-byte |
+----+----+----+----+----+----+----+----+
128 64 32 16 8 4 2 1
In this mode, the zip byte specifies how many l.s. half-bytes of the value are zeroes. Based on the field length, we decide how many "middle" half-bytes need to be changed, relative to the past UUID. M.s. half-bytes stay the same as in the past UUID.
Long zip byte:
7 6 5 4 3 2 1 0
+----+----+----+----+----+----+----+----+
| 1 |zero tail len | past uncompressed |
| | (half-bytes)| UUID index |
+----+----+----+----+----+----+----+----+
128 64 32 16 8 4 2 1
In this mode, the zip byte specifies the past uncompressed UUID we use as a reference. Index 0 points at the recentmost uncompressed UUID, 1 to the previous one, etc. Similarly to the short mode, we set a number of l.s. half-bytes to zeroes, replace middle half-bytes with new values and keep the m.s. half-bytes the same.
Strings are serialized as UTF-8.
Integers are serialized using the zig-zag coding (the l.s. bit conveys the sign).
Floats are serialized as IEEE 754 floats (4-byte and 8-byte support is required, other lengths are optional).
RON is log-structured: it stores data as a stream of changes first, everything else second. Algorithmically, RON is LSMT-friendly (think BigTable and friends). RON is information-centric: the data is addressed independently of its place of storage (think git). RON is CRDT-friendly; Conflict-free Replicated Data Types enable real-time data sync (think Google Docs).
Swarm RON employs a variety of well-studied computer science models. The general flow of RON data synchronization follows the state machine replication model. Offline writability, real-time sync and conflict resolution are all possible thanks to Commutative Replicated Data Types and partially ordered op logs. UUIDs are essentially Lamport logical timestamps, although they borrow a lot from RFC4122 UUIDs. RON wire format is a regular language. That makes it (formally) simpler than either JSON or XML.
The core contribution of the RON format is practicality. RON arranges primitives in a way to make metadata overhead acceptable. Metadata was a known hurdle in CRDT-based solutions, as compared to e.g. OT-family algorithms. Small overhead enables such real-time apps as collaborative text editors where one op is one keystroke. Hopefully, it will enable some yet-unknown applications as well.
Use Swarm RON!
Package | Build status |
---|---|
gritzko/ron |
|
gritzko/ron/rdt |