UUIDs

RON relies heavily on UUIDs to globally and unambigously identify its every construct: operations, objects, patches, versions, branches, snapshots etc. The RON UUID is one of several building blocks that lead to the immutable op.

Because RON employs UUIDs so heavily, it benefits greatly from using its own variant of UUID. The RON UUID bit layout is backwards-compatible with RFC 4122 (128 bits, RFC4122-reserved flag values). But unlike RFC 4122, time-based RON UUIDs can function as Lamport/logical/hybrid timestamps – this nuance is critical for RON and CRDTs in general.

Additionally, the textual RON UUID serialization has some nice features too.

  1. RON UUIDs are compact, thanks to Base64 and abbreviations. RON UUIDs are 23 chars max, typically less. RFC4122 is 36 chars of hex. MS GUIDs are 38 chars. Compare: 1fLDV+biQFvtGV and {f81d4fae-7dec-11d0-a765-00a0c91e6bf6}.
  2. RON UUIDs are meaningfully sorted lexicographically, thanks to the sortable variant of Base64.
  3. Very much like RFC4122 UUIDs, RON UUIDs come in different versions: time-based event ids, time-based derived ids, hashes/numbers, and human-friendly string constants (names). For example, referencing a type of RON RDT can be done with a perfectly human-readable identifier: lww, rga, etc. The same applies to error identifiers (e.g. NOTFOUND$~~~~~~~~~~) and other global/transcendent constants.

To minimize the confusion, RON UUID bit layout is defined in terms of two 64-bit words. The most significant word is value while the least-significant is origin. Each word’s most-significant four bits are flags, the rest is payload. In accordance with RFC4122 (as much as it is possible), two most-significant bits of the origin are set to zero. That corresponds to RFC4122 variant bits 00, thus overriding the RFC4122-reserved value “NCS backward compatibility”. We assume there are no Apollo NCS UUIDs left in circulation. The following two bits of the origin denote the RON UUID version. Flag bits of the most-significant word denote the variety, see below. Interpretation of the payload depends on the flag bits. Most often, value is the actual value (e.g. a timestamp), while origin is a replica id.

value:   vvvv.... ........ ........ ........  ........ ........ ........ ........ 
origin:  00VV.... ........ ........ ........  ........ ........ ........ ........ 

flag bits:
  00    RFC4122 variant
  VV    version bits
  vvvv  variety bits

Flag bit coding

In the textual form, two version bits are encoded as a middle separator e.g. @1hTDE6+test or NOTFOUND$~~~~~~~~~~.

Four variety bits are encoded using single hex digit 0..F followed by a slash /. Variety of zero 0 can be omitted.

Interpretation of varieties depends on the version.

Varieties for version $ (names) are:

Varieties for version % (numbers and hashes) are:

Varieties for versions + and - (events) are a combination of timestamp variety (m.s.bits) and origin variety:

Timestamp varieties are:

Origin varieties are:

UUID compression

Most of RON UUIDs can be efficiently compressed by only encoding highest significant bits.

Base 64×64 tailing zeroes can be omitted:

A/LED0000000+0000000000 = A/LED+0
A/LED0000000$123 = A/LED$123

If version is $ and second component is zero, it can be fully omitted:

A/LED0000000$0000000000 = A/LED$0 = A/LED

If variety is 0, it can be omitted as well:

0/lww0000000$0000000000 = lww0000000$0000000000 = lww$0 = lww

See also

Integer encoding scheme: Base 64×64.

Replica assignments rules.

Calendar-aware timestamp encoding.