creationix

I see. We have different definitions of serialized. The way I typically see it used is to describe how something is transmitted and stored, not how it is read.

Yes, by your definition, this is random and not serially read.

So you're saying that random access formats that are encoded to disk as a stream of bytes are not "serialized" because you don't alway read them in order?

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.

Just copy and paste files

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)

what sort of storage device does not allow your computers to use all 256 byte values

- 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.

And don't worry about railroad diagrams. I already intended to create them, I've just been extra busy this week with other things.

Tha main reason for the reverse encoding is it makes it easier on the writer. You simply do a depth-first traversal of the data graph and emit data on the way back up the stack. Zero buffering is needed since this naturally means you write contents before the length prefix.

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.

Also good luck parsing 10 MiB of JSON in a loop that can't tolerate blocking the CPU for more than 10ms.

What's expensive is very relative to the use case.

Very true. I had forgotten about bencode, I should read up on that again.

It makes sense they need a canonical form because they want same values to have same content hashes.

I meant computers can read it without any preprocessing. It's random access. You don't need to parse it, you don't need to decompress it. You just start at the end and follow pointers till you get to the desired value.

Even a trivial doc like this is challenging for me to read as a human.

yeah, LuaJIT is one of the use cases I had in mind working on this. JSON is pretty fast in modern JS engines, but in Lua land, JSON kinda sucks and doesn't really match the language without using virtual tables.

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.

it only has a text encoding as long as you can guarantee you don't have any unicode?

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.

How does CBOR retain JSON compatibility more than RX?

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

I've rewritten the framing in the README to first explain when you should use RX and when you should not. Most uses of JSON should probably stay JSON.

Let me know what you think

https://github.com/creationix/rx/blob/main/README.md#when-to...

Initial format docs are now here:

https://github.com/creationix/rx/blob/main/docs/rx-format.md

Railroad diagrams will come later when I have more time.

Thanks for the feedback. I've improved the framing to make the purpose/value more clear. What do you think about "RX is a read-only embedded store for JSON-shaped data"?

https://www.npmjs.com/package/@creationix/rx

That benchmark is a fair comparison for a real-world production workload and use case. Sadly I can't share the details. But suffice it to say that the dataset is a huge object with tens of thousands of paths as keys and moderately large objects as values (averaging around 3KB of JSON each) all with slightly different shapes. The use is reading just a few entries by path an then looking up some properties within those entries.

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)

the project framing needs some help perhaps. JSON is really good at a lot of use cases that this will never replace. But there are cases where JSON is currently used where this is much better. In particular large unstructured datasets where you only need to read a tiny subset of the data in a single request.

Maybe a better framing would be no-sql sqlite?

I'm happy to hear suggestions. This format was actually the internal .rexc bytecode for Rex (routing expressions), but when I realized it was actually a pretty good standalone format, I renamed it `.rx` for short. I am aware of RxJS, but I think that `rx-format` is different enough and `.rx` file extensions are unique enough, it's not too confusing.

You're right. Some important differences:

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.

Does this duplicate the name of keys?

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.

The current format version is the exact same feature set as JSON. I even encode numbers as arbitrary precision decimals (which JSON also does). This is quite different from CBOR which stores floats in binary as powers of 2.

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.

it's not really possible to stay human readable and get the compression levels and random access properties I was going for. But it is as human tooling friendly as possible given the constraints.

yes, this would work very well for any case where you have embedded databases of unstructured data that you want to query in a website or edge server

yep. I built custom JSON parsers as a first solution. The problem is you can't get away from scanning at least half the document bytes on average.

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.

I did seriously consider SQLite, but my existing datasets don't map easily to relational database tables. This is essentially no-sql for sqlite.

right, the jq query language is much more complex and featureful than the simple selector syntax I added to the rx-cli. But more could be added later as needed or it could just stream JSON output. It would be pretty trivial to hook up a streaming JSON encoder to rx-cli which could then pipe to jq for low-latency lookups. The problem is jq would need to JSON parse all that data which will be expensive.

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.

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.

2x the size of json after compression

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.

It is also a format that can be read as-is without any preprocessing. In some cases base64 can do that, and this format does make heavy use of base64 varints.

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.

yep, this is exactly the kind of use case that caused me to design this format.