RX – a new random-access JSON alternative
github.com
github.com
My one eyebrow raise is - is there no binary format specification? https://github.com/creationix/rx/blob/main/rx.ts#L1109 is pretty well commented, but you can't call it a JSON alternative without having some kind of equivalent to https://www.json.org/ in all its flowchart glory!
One old version that is meant to be more human readable/writable is jsonito
https://github.com/creationix/jsonito
I'll add similar diagrams and docs for the format itself here.
https://github.com/creationix/rx/blob/main/docs/rx-format.md
Railroad diagrams will come later when I have more time.
I am curious why it’s parsed right to left. Is this so that you could add new data to a top-level JSONL-esque list, solely by rewriting the end of the data structure, and not needing to change the beginning (or worst-case shift every single byte of data, if you need a longer count)?
It’s an interesting design tradeoff, because you can’t show a partial parse if you’re streaming the content naively beginning to end, which is a bit odd in a world where streams that begin to render token-by-token are all the rage.
But if you have an ability to do range queries, it’s quite effective, and it does allow for those incremental updates!
But it does open up a future direction I want to make with mutable datasets using append-only persistent data structures. The chain primitive is currently only used for strings, but it will be used to do the equivalent of `{...oldObj, ...newObj}` as a single chain `(pointerToOldObj, newObj)`.
With chains and pointers, you can write new versions of a dataset and reuse all the existing values that are unchanged. This, combined with random-access reads and fixed-block caching makes for a fairly complete MVCC database.
(Or to avoid using cat to read, whatever2json file.whatever | jq)
What might be interesting is to have a tool that processes full JSON data and creates a b-tree index on specified keys. Then you could run searches against the index that return byte offsets you can use for actual random access on the original JSON.
OTOH, this is basically just recreating a database, just using raw JSON as its storage format.
Maybe a query over the random-access file then converted into JSON would work?
I did build that once. But keeping track of the index is a pain. Sometimes I was able to generate the index on-demand and cache it in some ephemeral storage, but overall it didn't work out so well.
This system with RX will work better because I get the indexes built-in to the data file and can always convert it back to JSON if needed.
Being able to copy/paste a serialization format is not really a feature i think i would care about.
> None of the space savings/efficiency of binary
For string heavy datasets, it's nearly the same encoding size as binary. I get 18x smaller sizes compared to JSON for my production datasets. This was originally designed as a binary format years ago (https://github.com/creationix/nibs) and then later after several iterations, converted to text.
> Being able to copy/paste a serialization format is not really a feature i think i would care about
Imagine being paged at 3am because some cache in some remote server got poisoned with a bad value (unrelated to the format itself). You load the value in dashboard, but it's encoded as CBOR or some binary format and so you have to download it in a binary safe way, upload that binary file to some tooling or install a cbor reader to your CLI. But then you realize that you don't have exec access to the k8s pods for security reasons, but do have access to a web-based terminal. Again, to extract a binary value you would need to create a shell, hexdump the file and somehow copy-paste that huge hexdump from the web-based terminal to your local machine, un-hex dump it, and finally load it into some CBOR reader.
A text format, however is as simple as copy-paste the value from the dashboard and paste into some online tool like https://rx.run/ to view the contents.
Unless, to read that correctly, it only has a text encoding as long as you can guarantee you don't have any unicode?
I did add some small examples to the repo.
https://github.com/creationix/rx/blob/main/samples/quest-log...
The older, slightly outdated, design spec is in the older rex repo (this format was spun out of the rex project when I realized it's actually a good standalone format)
https://github.com/creationix/rex/blob/main/rexc-bytecode.md
Oof.
The format is technically a binary format in that length prefixes are counts of bytes. But in practice it is a textual format since you can almost always copy-paste RX values from logs to chat messages to web forms without breaking it.
unciode doesn't break anything since strings are encoded as raw unicode with utf-8 byte length prefixes. It supports unicode perfectly.
If your data only contains 7-bit ASCII strings, the entire encoding is ASCII. If your data contains unicode, RX won't escape it, so the final encoding will contain unicode as UTF-8.
No human is reading much data regardless of the format.
What is the benefit over using for example BSON?
If all your workflows allow copying as binary files, more power to you! But there are a lot of workflows where that is not possible. This was inspired by years of hands-on operational incident handling in production systems. Every time we use a binary format, it's extra painful.
This particular format would be slightly more compact as binary, but not enough to justify closing the door on all the use cases that would preclude.
I'll probably add a binary variant for people who prefer that (or for people who want to be able to embed binary values in the data without base64 encoding it)
another thing, I put in a 400KB json and the REXC is 250KB, cool, but ideally the viewer should also tell me the compressed sizes, because that same json is 65kb after zstd, no idea how well your REXC will compress
edit: I think I figured out you can right click "copy as REXC" on the top object in the viewer to get an output, and compressed it, same document as my json compressed to 110kb, so this is not great... 2x the size of json after compression.
The primary use case is not compression, it's just a nice side effect of the deduplication. This will never beat something like zstd, brotli, or even gzip.
My production use cases are unique in that I can't afford the CPU to decompress to JSON and then parse to native objects. But with this format, I can use the text as-is with zero preprocessing and as a bonus my datasets are 18x smaller.
Right and that makes sense. There is more information in here. The entire thing is length prefixed and even indexed for O(1) array lookups and O(log2 N) object lookups.
If you don't care about random access and you don't mind the overhead of decompression, don't use RX.
Let me know what you think
https://github.com/creationix/rx/blob/main/README.md#when-to...
Q^mSat,3^b:d+s+E,4Fri,3^u:h+k+u,6Thu,3^P:j+
If you are effectively going binary, do it. CBOR or Protobuf or any dozen other binary serializations that would be far more efficient.The author claims this is because of copy and pasting… cool, remind me what BASE64 is again?
Sure, you can encode as JSON, then compress with gzip and then base64 encode. You'll probably end up with something smaller than rx and be extremely safe to copy-paste. But your consumers are going to consume orders of magnitude more CPU reading data from this document.
RX is usable as-is, is compressed, and is copy-pasteable. It's the unique combination of properties that makes it interesting.
>Q^mSat,3^b:d+s+E,4Fri,3^u:h+k+u,6Thu,3^P:j+
My man… no. I have no doubt you could kind of figure out what that sample is hot off the heels of writing this, and likely not in six months. And to consider that anyone else would fill their brain with the rules to decipher that, Nah 2.0.
Even a trivial doc like this is challenging for me to read as a human.
- clipboards
- logs
- terminal output
- alerts
- yaml configs
- JSON configs
- hacker news comments
- markdown documentation
- etc...
I assure you, this is not a solution looking for a problem. I started out with binary encodings first, but then realized it limits so many workflows.
> Nah.com, fam.
Yes, serially. Which means no random-access across the transfer channel.
Yes, many formats are read start-to-end, but I don't think that's a requirement. The important thing is it can be stored and transmitted as a stream of bytes. The word describes how it is transported and stored, not how it is read.
Yes. That's precisely what "random access" means.
> The important thing is it can be stored and transmitted as a stream of bytes.
What isn't stored and transmitted as a stream of bytes? Memory itself is a sequential array of bytes. The criteria you're using here seem to be all-encompassing.
When we're talking about serial access to data, it means that we're sequentially parsing the stream of bytes from its starting point, rather than reading arbitrarily from any point in the stream that we desire.
Yes, by your definition, this is random and not serially read.
This did catch my eye, however: https://github.com/creationix/rx?tab=readme-ov-file#proxy-be...
While this is a neat feature, this means it is not in fact a drop in replacement for JSON.parse, as you will be breaking any code that relies on the that result being a mutable object.
This lib keeps the compact representation at runtime and lets you read it without putting all the entities on the heap.
Cool!
It falls down if you have e.g. an array of 1 million small items, because you still need to skip over 999999 items to get to the last one. It looks like RX adds some support for indexes to improve that.
I was in this situation where we needed to sparsely read huge JSON files. In the end we just switched to SQLite which handles all that perfectly. I'd probably still use it over RX, even though there's a somewhat awkward impedance mismatch between SQL and structs.
It's not like you can just tell them to move to protobuf.
If you are working with an end you don’t control, this “newer better” format isn’t in your cards either.
RX can represent any value JSON can represent. It doesn't even lose key order like some random-access formats do.
In fact, RX is closer to JSON than CBOR.
Take decimals as an example:
JSON numbers are arbitrary precision numbers written in decimal. This means it can technically represent any decimal number to full precision.
CBOR stores numbers as binary floats which are appriximations of decimal numbers. This is why they needed to add Decimal Fractions (Tag 4)
RX already stores as decimal base and decimal power of 10. So out of the box, it matches JSON
Think of it as a hybrid between JSON, SQLite, and generic compression. This format really excels for use cases where large read-only build artifacts are queried by worker nodes like an embedded database.
What's expensive is very relative to the use case.
rx works very well as a kind of embedded database like sqlite, but completely unstructured like JSON.
Also I'm working on an extension that makes it mutable using append-only persistent data structures with a fixed-block caching level that is actually a pretty good database.
Also note it stores decimal in a very compact encoding (two varints for base and power of 10)
That said, while this is a text format, it is also technically binary safe and could be extended with a new type tag to contain binary data if desired.
That would make parsing faster and there will be very little in terms on tree (json can't really contain full blow graphs) but it's rather complicated, and it will require hashing to allow navigation, though.
With RX and other truly random-access formats you could even optimize to the point of not even fetching the whole document. You could grab chunks from a remote server using HTTP range requests and cache locally in fixed-width blocks.
With JSON you must start at the front and read byte-by-byte till you find all the data you're looking for. Smart parsers can help a lot to reduce heap allocations, but you can't skip the state machine scan.
There are SAX-like JSON libraries out there, and several of them work with a preallocated buffer or similar streaming interface, so you could stream the file and pick out the two fields as they come along.
XML has EXI (Efficient XML Interchange) for precisely the reason of getting wins over the wire but keeping the nice human readable format at the ends.
EXI looks useful. Now I just wish there was a renderer in the pugjs format as I find that terse format much pure readable than verbose XML. I also find indentation based syntax easier to visually parse hierarchical structure.
Does this duplicate the name of keys? Say if you have a thousand plain objects in an array, each with a "version" key, would the string "version" be duplicated a thousand times?
Another project a lot of people aren't aware of even though they've benefitted from it indirectly is the binary format for OpenStreetMap. It allows reading the data without loading a lot of it into memory, and is a lot faster than using sqlite would be.
Edit: the rust library I remember may have been https://rkyv.org/
Yes, the format allows for objects to be stored with a pointer to a shared schema (either an array of keys or another object that has the desired keys)
The current implementation is pretty close to ideal when deciding to use this encoding.
Even a technically superior format struggles without that ecosystem.
JSON has `null` values with string keyds, but lua doesn't have `null`. It has `nil`, but you can't have a key with a nil value. Setting nil deletes the key
Lua tables are unordered. But JS and JSON are often ordered and order often matters.
RX, however matches Lua/LuaJIT extremely well and should out-perform the JS Proxy based decoder using metatables. Since it's using metatables anyway do to the lazy parsing, it's trivial to do things like preserve order when calling `pairs` and `ipairs` and even including keys with associated null values.
You can round trip safely in Lua, which is not easy with most JSON implementations.
Douglas Crockford didn't design it — he said he "discovered" it. It was already there in JavaScript's object literal syntax, which itself traces back to Brendan Eich's 10-day sprint in 1995.
A data format that conquered the internet was a side effect of a language built under absurd time pressure.
Every attempt to replace it has to overcome that kind of accidental ubiquity, which is much harder than overcoming a technical limitation.
Once you get the computational complexity advantage, then you can make it as much times faster as you want. In these cases small instances matter to judge constants, and to the average (mean?) user, mean instance sizes.
I'm not sure how to sell the advantage succinctly though. Maybe just focus on "real-world" scenarios, but there's no footnote with details on the comparison
The benchmark (or is supposed to) measures end-to-end parse + lookup.
JSON: 92 MB RX: 5.1 MB
Request-path lookup: ~47,000x faster
Time to decode a manifest and look up one URL path:
JSON: 69 ms REXC: 0.003 ms
Heap allocations: 2.6 million vs. 1
JSON: 2,598,384 REXC: 1 (the returned string)
Docs are super unclear.
Is it versioned? Or does it need to be..
Sample output:
'fdiscovered,aextreme,7danger,6+1A+16;6level_range,b:QThe Heap ,d'th
Human unreadable, ascii output. Line up and get yours today!
I find it obvious that your first attempt failed. Try again, you have not even remotely failed enough if you are making the argument that this is kinda readable. Yes, ascii words are easy to pick out, you didn’t do that, you did the part that makes it all harder.
sick is binary, rx is textual (this matters for tooling)
sick has size limits (65534 max keys for example. I have real-world rx datasets reaching this size already) rx uses arbitrary precision variable-length b64 integers. There are no size limits anywhere inherit in the format, just in implementations.
sick does not preserve object key order rx preserves object key order, but still implements O(log2 N) lookups for object keys.
etc.
Why is it called RX?
The viewer is cool, took me a while to find the link to it though, maybe add a link in the readme next to the screenshot.
At this point, probably, we have to think how to classify all the "JSON alternatives" cause it gets difficult to remember them all.
Is RX a subset, a superset or bijective to JSON?
I could technically add binary to the format, but then it would lose the nice copy-paste property. But with the byte-aware length prefixes, it would just work otherwise.
Maybe a better framing would be no-sql sqlite?