JSOG: Encode complex object graphs in JSON

May 31, 2013

I keep having this problem over and over. I have a complex, interlinked object graph on my server and I need to transfer a representation to my (usually Javascript) client. This is a long-solved problem in RPC protocols from the 90s, but like the cure for scurvy, we seem to have forgotten something in progress towards JSON-based protocols.

Consider this example graph of people and their secret santas:

[
    {
        "name": "Sally",
        "secretSanta": <link to Bob>
    },{
        "name": "Bob",
        "secretSanta": <link to Fred>
    },{
        "name": "Fred",
        "secretSanta": <link to Sally>
    }
]

Notice that it has cycles. Even if somehow it didn't, there's still likely going to be a lot of duplicated data both on the wire and in memory. Typically this is where programmers tediously add id fields and write code to cross-link the entries manually - but wouldn't we rather just transfer the object graph as-is?

Yes we would! So Jon and I created JSOG, a laughably simple convention that lets us represent an interlinked, cyclic object graph in JSON:

• JSOG is 100% JSON and uses standard platform JSON parsing tools.
• JSOG is human readable; graphs without cycles look like regular JSON.
• JSOG does not require or interact with pre-existing id fields.
• JSOG is fully self-describing; no external metadata or IDL is required.
• JSOG is easy to implement in any language or platform.
• JSOG-decoding a simple JSON structure leaves the JSON unchanged.

This is the JSOG representation of the aforementioned graph:

[
    {
        "@id": "1",
        "name": "Sally",
        "secretSanta": {
            "@id": "2",
            "name": "Bob",
            "secretSanta": {
                "@id": "3",
                "name": "Fred",
                "secretSanta": { "@ref": "1" }
            }
        }
    },
    { "@ref": "2" },
    { "@ref": "3" }
]

To encode an object graph: Each time a new object is encountered, give it a unique string @id. Each time a repeated object is encountered, serialize as a @ref to the existing @id.

To decode an object graph: Track the @id of every object deserialized. When a @ref is encountered, replace it with the object referenced.

The "catch" is that you cannot have real keys @id or @ref in your structure. When the graph is serialized, @id and @ref are added; when the graph is deserialized, @id and @ref are removed.

JSOG is designed to be trivial to implement on any platform with a JSON parser. @ids are arbitrary strings unique only within the context of a single graph serialization. To facilitate implementation on platforms with ordered dictionary structures, @id definitions must come before @ref references.

We have provided four production-ready implementations:

• Javascript, available in NPM
• Java, available in Maven
• Python, available in PyPI
• Ruby, available in Rubygems

The logic of JSOG encoding and decoding is simple; these implementations are a couple dozen lines of code each. The license is MIT. We are striving for ubiquity.

Care to contribute an implementation for your platform-of-choice? Email me.

Discuss this at Hacker News

original