Sick: Indexed deduplicated binary storage for JSON-like data structures

If you use varints for pointers you can have the best of both worlds, and achieve even better compaction for the smallest objects.

> I don't know what kind of data you are dealing with but its illogical and against all best practices to have this many keys in a single object.

The whole point of this project is to handle efficiently parsing "huge" JSON documents. If 65K keys is considered outrageously large, surely you can make do with a regular JSON parser.

A pattern I've seen is to take something like `{ "users": [{ "id": string, ... }]}` and flatten it into `{ "user_id": { ... } }` so you can deserialize directly into a hashmap. In that case I can see 65k+ keys easily, although for an individual query you would usually limit it.

Let's say you have a localization map: the keys are the localization key and the values are the localized string. 65k is a lot but it's not out of the question.

You could store this as two columnar arrays but that is annoying and hardly anyone does that.

You seem to be assuming that a JSON object is a "struct" with a fixed set of application-defined keys. Very often it can also be used as a "map". So the number of keys is essentially unbounded and just depends on the size of the data.

Every pathological case you can imagine is something someone somewhere has done.

Sticking data into the keys is definitely a thing I've seen.

One I've done personally is dump large portions of a Redis DB into a JSON object. I could guarantee for my use case it would fit into the relevant memory and resource constraints but I would also have been able to guarantee it would exceed 64K keys by over an order of magnitude. "Best practices" didn't matter to me because this wasn't an API call result or something.

There are other things like this you'll find in the wild. Certainly some sort of "keyed by user" dump value is not unheard of and you can easily have more than 64K users, and there's nothing a priori wrong with that. It may be a bad solution for some specific reason, and I think it often is, but it is not automatically a priori wrong. I've written streaming support for both directions, so while JSON may not be optimal it is not necessarily a guarantee of badness. Plus with the computers we have nowadays sometimes "just deserialize the 1GB of JSON into RAM" is a perfectly valid solution for some case. You don't want to do that a thousand times per second, but not every problem is a "thousand times per second" problem.

That's like saying it's illogical to have 65k elements in an array.

What is the difference?

Data shape often outlives the original intentions.

Even if it's "generally unwise" it was a well-thought decision in this particular case. See my other comments. An array of elements with constant size is indexed for free. An array of elements of varying size needs a separate index. SICK's binary representation (EBA) was created with several particular usecases in mind. I needed most compact representation and fastest access (for very underpowered devices), large objects were not a big concern-they can be chunked externally.

When order is important it can be maintained by an external layer with, e.g. a an encoding into a list of pairs.

Since RFC 4627 (the original):

> An object is an unordered collection of zero or more name/value pairs, [...]

Further, since RFC 7159:

> JSON parsing libraries have been observed to differ as to whether or not they make the ordering of object members visible to calling software. Implementations whose behavior does not depend on member ordering will be interoperable in the sense that they will not be affected by these differences.

Both are in the current version (RFC 8259).

OTOH, I find the "but the order is not supposed to be guaranteed!" debate REALLY stupid when it comes to software where it's clear that at some point, a human will have to look at the content and correlate it with another system.

There's nothing more evil than re-shuffling JSON just for the fun of it and making everyone who has to look at the result miserable. Yes, I'm talking about you, ELK devs.

Edit: (And/or whoever wrote the underlying Java/Go libs they use for JSON that don't allow developers to patch ordering in. I remember reading GitHub issues about this.)

An object is unordered, but most (nearly all?) parsing software will preserve the order, and some software may rely on that behaviour, so it's worth mentioning.

No, according to the spec the order is not preserved but most parsers preserve the order (or maintain some order based on side effects) and engineers rely on that (and sometimes that backfires).

Essentially, SICK also maintains some strange order based on values of some homegrown trivial hash function but the only right approach to JSON objects is to treat their keys as an unordered set.

I think this is a generational thing. To a bunch of people now practicing, JSON isn’t just an encoding but has come to mean “nested basic data types”.

> 65k key limit for objects

The limit comes from 2-byte element pointer size. That can be adjusted. We don't have an implementation with larger pointers but it can be done easily.

> while the rest streams in

Yes, there are many usecases where you can use some chunks of the data/rebuild some parts of the structures immediately without any accumulation. The problem is that we don't have a nice streaming abstraction which would suit anyone for any usecase.

SICK as a library is an efficient indexed binary storage for JSON with listed limitations.

SICK as a concept is much more but you might need your own implementation tailored to your usecase.

If the stream contains removal entries, then that is not a data stream but command stream and, again, has nothing to do with JSON itself. We can extrapolate this to some kind of json-rpc-ish stream if we want to keep this aligned with JSON.

Overall, I think that mentioning JSON here at all is simply a mistake. It would be better to just introduce this as streaming protocol/framework for data structures. But then we can do the same thing with literally any format and syntax.