Replicated Object Notation

Replicated Object Notation (RON) is a format for distributed live data. It guarantees continuous bitwise convergence of replicated data structures in a network of arbitrary topology. That makes it a good fit for collaborative software, data synchronization on mobile devices, and broadly defined decentralized apps. RON was specifically designed for CRDTs (Conflict-Free Replicated Data Types). For example, this page is a versioned/collaborative CRDT object containing some CommonMark wikitext. RON can express non-CRDT data too.

RON is op-based, so it expresses objects, patches and separate ops with equal ease. It can work in real-time, it can work offline. Still, it tries very hard to look like your regular notation of the day. Here is a simple JSON object:

    {   "_id":      "0-2dE-Wares",
        "type":     "apples",
        "quantity": 4,
        "color":    "red"           }

This is how it may look in RON:

    @0-2dE-Wares :struct,
        type        apples,
        quantity    4,
        color       red;

This does not seem like a big difference. Looks like RON is yet another notation, like YAML or something, right? Key differences are three:

  1. RON is op-based, so every line here is an op.
  2. Every op has a globally unique ID, like 0-2dE-Wares; we may skip those IDs when they go in incremental sequence.
  3. RON is typed, e.g. this particular object is a struct.

Note that RON ops, objects and versions are all addressable. Every new op gets a unique logical timestamp ID. That ID also serves as the ID of the version that op created (in the context of our subjective order of events). The op that created the object gives its ID to the object itself, e.g. 0-2dE-Wares.

Now suppose you ate one apple. How do you convey that? RFC6902 JSON patch may look like this:

 [ { "op":"replace", "path":"/quantity", "value":3 } ]

With RON, you add a new op that references the object.

    @4-2dI-Wares :3-2dH-Wares quantity 3;

In this case, the new op has an ID 4-2dI-Wares. Also, it references the version of the object it amends: 3-2dH-Wares. That was the id of the last op; the one that set color to red.

If you can point to a particular version of the object, why not request a patch?

    @patch :3-2dH-Wares? 
    @4-2dI-Wares :3-2dH-Wares quantity 3;

So far so good.

RON supports arbitrary data structures. RON Struct is a simple and cheap one, it does not support nesting or complex values. Although, values of a struct can be IDs referencing other objects, so that way you can nest other data structures in it. Still, RON Trie is the best one to represent arbitrary JSON. Suppose, I list the contents of my shelf in JSON:

{
    "shelf": {
        "jarA": {
            "content": "candies",
            "count": 20
        },
        "jarB": {
            "content": "vitamins",
            "count": 100
        }
    }
}

A RON Trie is like a regular trie, except it consists of tuples of RON atoms, not strings of chars. For our shelf JSON, a trie looks like this:

@0-3d-Wares :trie,
    shelf   jarA    content candies,
    ~       ~       count   20,
    ~       jarB    content vitamins,
    ~       ~       count   100;

Here, RON shows its tabular nature. Still, you may also see the trie, defined as a set of tuples/paths.

The directory/file structure of this wiki is stored as a trie. You may see the resulting RON trie or the original RON trie with all the history and metadata. You may also see it as JSON.

Now, let's take a look at the crown jewel of the system: a type for collaboratively edited text. Like the one you may find in Google Docs or a similar system. Those need a lot of rocket science under the hood! In a real-time collaboratively edited text, every letter is added or removed by a separate op. That may produce a lot of overheads, so every serialization of RON (RONt, RONv, RONp) optimizes that case in some way. RONt uses spreads: consecutively numbered single-char ops merge into a string. Here you see six formally-identical ways to render "Hello world!":

@0-jG-test :text, ('Hello world!');
@0-jG-test :text, ('Hello world'), '!';
@0-jG-test :text, ('Hello world'), :B-jR-test '!';
@0-jG-test :text, 'H', ('ello world'), 
                            @C-jS-test :B-jR-test '!';
@0-jG-test :text, 'H', 'e', 'l', 'l', 'o', ' ', 
                        'w', 'o', 'r', 'l', 'd', '!';

The underlying CRDT data type is named a Causal Tree. All pages of this wiki are stored as causal tries. See the source RON of this page for an extensive example of a RONt coded versioned text.

The last but not the least, let's consider such a boring but essential topic as tabular data. For your average CSV data-dump cases, RON supports a simple tabular type RON Tab. For a CSV like this:

Jar;Content;Count
jarA;candies;20
jarB;vitamins;100

A tab object would look like this:

   @0-dK2-data :tab  jar    content     count,
                     jarA   candies     20,
                     jarB   vitamins    100;

tab is a cheap and simple type. It can not change the format of a record; it can only append or remove whole records.

But suppose you need something more like Excel, a lot of action around your data. Then, you may resort to the most general key-value RON type named Dict. It maps any RON tuple to another tuple. For example:

    @0-X3n-data :dict,
        jarA   content   ~   candies,
        jarA   count     ~   20,
        jarB   content   ~   vitamins,
        jarB   count     ~   100;

A dict can store sparse or multidimensional tables, as it can update, insert or delete columns, rows or separate cells. Actually, dict can express a broad range of data structures, including relational tables.

Now, it is probably the right time to introduce the formal rules of RON.

This is what RON is.