It is also possible to encode JSON documents directly as a serialized B-tree. Then you can construct iterators on it directly, and query internal fields at indexed speeds. It is still a serialized document (possible to send over a network), though now you don't need to do any parsing, since the document itself is already indexed. It is called the Lite³ format.

Disclaimer: I am working on this.

https://github.com/fastserial/lite3

▲

conradev 5 days ago | parent | next [-]

This is super cool! I've always liked Rkyv (https://rkyv.org) but it requires Rust which can be a big lift for a small project. I see this supports binary data (`lite3_val_bytes`) which is great!

▲

eliasdejong 5 days ago | parent [-]

Thank you. Having a native bytes type is non-negotiable for any performance intensive application that cannot afford the overhead of base64 encoding. And yes, Rkyv also implements this idea of indexing serialized data. The main differences are:

1) Rkyv uses a binary tree vs Lite³ B-tree (B-trees are more cache and space efficient).

2) Rkyv is immutable once serialized. Lite³ allows for arbitrary mutations on serialized data.

3) Rkyv is Rust only. Lite³ is a 9.3 kB C library free of dependencies.

4) Rkyv as a custom binary format is not directly compatible with other formats. Lite³ can be directly converted to/from JSON.

I have not benchmarked Lite³ against Rust libraries, though it would be an interesting experiment.

▲

conradev 5 days ago | parent | next [-]

That second point is huge – Rkyv does have limited support for in-place mutation, but it is quite limited!

If you added support for running jq natively, that would be very cool. Lite³ brings the B-trees, jq brings the query parser and bytecode, combined, you get SQLite :P

▲

eliasdejong 5 days ago | parent [-]

Yes, in fact the name Lite³ was chosen because it is lighter than SQLite.

I thought about implementing something like jq or JSON query, and this is very possible. It is like sending a mini-database that can be queried at speeds thousands of times faster than any JSON library is able to parse.

One interesting effect of being a zero-copy format is that the 'parsing speed' can exceed the memory bandwidth of the CPU, since to fulfill a query you do not actually need to parse the entire dataset. You only walk the branches of the tree that are actually required.

I've talked to some other people that have also shown interest in this idea. There doesn't really seem to exist a good schemaless single-file format that supports advanced queries. There is only SQLite and maybe HDF5.

▲

conradev 4 days ago | parent | next [-]

I would very much love that. I like `jq` itself as a standard, even though I don't know how well it maps. Areas where I'd want to use Lite³:

- Microcontrollers. I find myself reaching for https://github.com/siara-cc/sqlite_micro_logger_c/tree/maste... because SQLite is just too big

- Shared memory regions/mapped files. Use it to share state between processes. Could you make mutations across processes/threads lock-free?

- Caching GPU-friendly data (i.e. image cache). I'm not sure if the current API surface/structure is page alignment friendly

	▲	eliasdejong 4 days ago \| parent [-]
		In general jq maps very well to any hierarchical datastructure. One of the maintainers has made 'fq' which supports BSON, MsgPack, Protobuf, CBOR and even media files png, jpg, mp4 etc. SQLite when compiled for size is 590 kB. But I think a full jq database implementation based on Lite³ would be possible under 100 kB. Lock-free shared state relies on algorithms that can make clever use of atomic instructions. But you should not have threads write to the same memory regions, because the hardware only allows for 1 core to have a cacheline in a writeable state. If another core attempts a write to the same line, this will immediately invalidate all the other copies. Under high contention the coherency penalty becomes so large that throughput falls through the floor. So basically the algorithms need to do most of the work in separate memory regions, then occasionally coordinate by 'committing' their work via a spinlock or similar. Lite³ implements some settings for node alignment, but not for user data. It would be possible to create a bytes type with extra alignment guarantees.

▲

cryptonector 5 days ago | parent | prev [-]

Building a jq around something like Lite^3 or JSONB is a very appealing thought.

▲

namibj 5 days ago | parent | prev [-]

1) when did they downgrade? I've stared for hours at that particular code...

2) no you just don't get to move data freely.

3) I don't believe JSON has any place in a system that needs C because it can't handle Rust.

4) JSON can't handle non-tree structures, it's further very limited in expressivity. Rkyv is more of a code gen akin to ASN.1

Happy benchmarking, feel free to use the rkyv benchmark tooling and ensure you have enough link time optimization going on.

	▲	taintegral a day ago \| parent [-]
		(I made rkyv) I took a look at lite3/tron because I was interested in seeing how it approached some of the issues I ran into with rkyv. I ended up with some additional information related to points 1 and 2 I figured I'd write down: 1) You're correct, rkyv uses a B-tree with a default branching factor of 6 [1]. I don't think I've ever implemented a binary tree in any version of rkyv - maybe one of the earliest versions used a sorted vec instead of a B-tree? I hate the B-tree map implementation because it is so complicated, even though it actually used to be even worse in 0.7 when it was implemented as a B+ tree. Sorry for making you read any of it! 2) Arbitrary mutations would definitely be an improvement on rkyv, and I was most interested to see what kind of approach lite3/tron took! Unfortunately growing the buffer is not supported [2] and freed memory isn't reclaimed [3]. These are the two actually difficult problems standing in the way of rkyv getting more comprehensive mutation support, so unfortunately I think there's nothing valuable to take away here. The issue with growing the buffer is that you invalidate any pointers into the buffer and have to manually fix them up (e.g. by re-crawling the buffer). There's not a decent approach I'm aware of which manages these pointer fixups in a way that limits complexity and avoids really nasty API surfaces. The issue with memory reclamation is that you effectively have to add an allocator to your buffer, and that allocator has to also be persistable. I actually got this part working in rel while that was still a project worth hacking on [4]. I just ran out of steam and willingness to play the type-tac-toe required to get a safe API out of it. The main problem I ran into there was related to value branding, since you shouldn't be allowed to make references to objects which cross between contiguous buffers. This project is neat, but it does basically just look like an rkyv-converted `BTreeMap<String, JsonValue>`. [1]: https://github.com/rkyv/rkyv/blob/main/rkyv/src/collections/... [2]: https://github.com/fastserial/lite3/blob/main/src/lite3.c#L5... [3]: https://lite3.io/design_and_limitations.html#autotoc_md29 (see note at end of section) [4]: https://github.com/rkyv/rel/blob/main/rel_example/src/main.r...

▲

c-cube 3 days ago | parent | prev | next [-]

It's a bit unfortunate that [1] doesn't seem to mention Fleece[2], since Fleece is an already existing, solid format with very similar properties (JSON-compatible data format, uses offsets for sharing, allows for cheap updates, and uses binary search on arrays to achieve O(ln n) lookups in large tables or arrays, etc.)

[1]: https://lite3.io/design_and_limitations.html#autotoc_md31 [2]: https://github.com/couchbase/fleece/

▲

cryptonector 5 days ago | parent | prev | next [-]

This is pretty cool.

How does Lite^3 compare to PG's JSONB? PG's JSONB is also a serialized, indexed data structure. One of the key things about JSONB is that for arrays (and so objects) it encodes first their lengths, then the values, but every so many elements (32 is the default IIRC) it encodes an offset, and the reason for this design is that when they encoded offsets only the result did not compress well (and if you think about it it will be obvious why). The price they pay for this design is that finding the offset to the nth element's value requires first finding the offset of the last entry before n that has an offset, then adding all the lengths of the entries in between. This way you get a tunable parameter for trading off speed for compressibility.

EDIT: Ok, I've looked at the format. Some comments:

- Updating in place is cool but you need to clear unused replaced data in case it's sensitive, and then unless you re-encode you will use up more and more space -- once in a while you need a "vacuum". Though vacuuming a Lite^3 document is quite simple: just traverse the data structure and write a new version, and naturally it will be vacuumed.

- On the whole I like Lite^3 quite a bit. Very clever.

- JSONB is also indexed as encoded, but IIUC it's not in-place updateable (unless the new items are the same length as the old) without re-encoding. Though I can imagine a way to tombstone old values and replace them with offsets into appended data, then the result would also need a "vacuum" once in a while.

- I'm curious about compressibility. I suspect not having long runs of pointers (offsets) helps, but still I suspect JSONB is more compressible.

I love the topic of serialization formats, and I've been thinking for some time about ASN.1 compilers (since I maintain one). I've wanted to implement a flatbuffers / JSONB style codec for ASN.1 borrowing ideas from OER. You've given me something to think about! When you have a schema (e.g., an ASN.1 module) you don't really need a B-tree -- the encoded data, if it's encoded in a convenient way, is the B-tree already, but accessing the encoded data by traversal path rather than decoding into nice in-memory structures sure would be a major improvement in codec performance!

▲

eliasdejong 5 days ago | parent | next [-]

The main difference between Lite³ and JSONB is that JSONB is not a standalone portable format, and therefore is not suitable for external interchange. Its purpose is to be an indexable representation of JSON inside a Postgres database. But sending it as standalone messages to arbitrary consumers does not really make sense. JSONB can only be interpreted in a Postgres context. This is different from for example BSON, which can be read and constructed as a standalone format without Mongo.

Another difference is that JSONB is immutable. Suppose you need to replace one specific value inside an object or array. With JSONB, you would rewrite the entire JSONB document as a result of this, even if it is several megabytes large. If you are performing frequent updates inside JSONB documents, this will cause severe write amplification. Despite the fact that offsets are grouped in chunks of 32, Postgres still rewrites the entire document. This is the case for all current Postgres versions.

On the other hand, Lite³ supports replacing of individual values where ONLY the changed value needs updating. For this to work, you need separate offsets. Postgres makes a tradeoff where they get some benefits in size, but as a result become completely read-only. This is the case in general for most types of compression.

Also JSONB is not suited to storing binary data. The user must use a separate bytea column. Lite³ directly implements a native bytes type.

JSONB was designed to sacrifice mutability in favor of read performance, but despite this, I still expect Lite³ to exceed it at read performance. Of course it is hard to back this up without benchmarks, but there are several reasons:

1) JSONB performs runtime string comparison loops to find keys. Lite³ uses fixed-size hash digests comparisons, where the hashes are computed at compile time.

2) JSONB must do 'walking back' because of the 32-grouped offset scheme.

3) Lite³ has none of the database overhead.

Again, the two formats serve a different purpose, but comparing just the raw byte layouts.

	▲	cryptonector 4 days ago \| parent \| next [-]
		Thank you for your thoughtful response. I agree that Lite³ is almost certainly better than JSONB on every score except compressibility, but when Lite³ is your database format then that doesn't matter (you can always compress large string/blob values if need be). Compressibility might matter for interchange however, but again, if your messages are huge chances are there are compressible strings in them, or if they're not huge then you probably don't care to compress.
	▲	nh2 4 days ago \| parent \| prev [-]
		Why not add this approach to postgres as a "JSONL3" type? It'd be nice to update postgres JSON values without the big write amplification.

▲

namibj 5 days ago | parent | prev [-]

Rkyv is basically the last thing you mentioned already? It's basically a code gen for deriving serialized structures that can be accessed for read with the exact same API and functionally almost identical (but not quite; in the differences lies much of the special sauce) ABI.

▲

the_duke 5 days ago | parent | prev | next [-]

Would love a Rust implementation of this.

▲

gritzko 5 days ago | parent | prev [-]

Sorry, but who are you? Your accounts have no history.