5 ms·

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

124 points by pshirshov 1y ago

Retr0id 1y ago
I started on something a bit like this, but using sqlite instead of a custom serialisation format: https://github.com/DavidBuchanan314/dag-sqlite https://github.com/DavidBuchanan314/dag-sqlite (it's intended to store DAG-CBOR objects but it is trivial to represent a JSON object as DAG-CBOR)
- pshirshov 1y ago
  SQLite was bit too heavy for our usecase unfortunately. We tried it as one of the first options.
gethly 1y ago
It is a bit confusing that JSON is being mention so much when in reality this has nothing to do with it - except to showcase that JSON is not suitable for streaming whereas this format is. Secondly, I fail to see advantages here as the claim is that it allows streaming for partial processing compared to JSON that has to be fully loaded in order to be parseable. Mainly, because the values must be streamed first, before their location/pointers in order for the structure to make sense and be usable for processing, but that also means we need all the parent pointes as well in order to know where to place the children in the root. So all in all, I just do not see why this is advantageous format above JSON(as that is its main complaint here), since you can stream JSON just as easily because you can detect { and } and { and ] and " and , delimiters and know when your token is complete to then process it, without having to wait for the whole structure to finish being streamed or wait for the SICK pointers to arrive in full so you can build the structure. Or, I am just not getting it at all...
- xenadu02 1y ago
  Most existing JSON parsers don't support streaming but that's not inherent in the format. It is definitely possible to stream writes easily but it's just as possible to stream parsing.
- pshirshov 1y ago
  > when in reality this has nothing to do with it It's a specific representation of JSON-like data structures, with an indexed deduplicated binary format and JSON encoders and decoders. Why "nothing"? It's all about it. Mostly it's not about streaming. More efficient streaming is a byproduct of the representation. > because you can detect { and } and { and ] and " and , You need a pushdown automaton for that. In case of SICK you don't need potentially unbounded accumulation for many (not all) usecases. > the values must be streamed first, before their location/pointers Only to avoid accumulation. If you are fine with (some) accumulation, you can reorder. Also think about the updates. But again, streaming is a byproduct. This tool is an indexed binary deduplicating storage which does not require parsing and provides amortized O(1) access time.
  - aaronblohowiak 1y ago
    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”.
- 8organicbits 1y ago
  I think this quote explains the efficient streaming: > There is an interesting observation: when a stream does not contain removal entries it can be safely reordered. So if I'm understanding, the example in the readme could be sent in reverse, allowing the client to immediately use root:0 and then string:2 while the rest streams in. I was looking for something like this, but my use case exceeds the 65k key limit for objects.
  - pshirshov 1y ago
    > 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.
  - gethly 1y ago
    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.
    - pshirshov 1y ago
      > has nothing to do with JSON itself. It's literally a deduplicated indexed binary storage for JSON (plus an approach to JSON representation more suitable for streaming than serialized JSON). > we can do the same thing I would highly encourage doing same things! For some reason people love to fully parse a 50MiB long JSON document when they need just 0.1% of the data in it.
qixxiq 1y ago
Current implementation has the following limitations: Maximum object size: 65534 keys The order of object keys is not preserved ... These limitations may be lifted by using more bytes to store offset pointers and counts on binary level. Though it's hard to imagine a real application which would need that. I've worked on _many_ applications which have needed those features. Object keys is a per implementation detail, but failing at 65k keys seems like a problem people would likely hit if this were to be used at larger scales.
- pshirshov 1y ago
  In our usecase, for which we created the library, we made this tradeoff to save several bytes per pointer and keep binary form more compact. The application splits large objects into smaller chunks. 99% of the structures there are relatively small but there are tons of them. Most likely you can do the same - just split large structures into smaller ones. If you need support for larger structures, you may create your own implementation or extend ours (and I would really like to hear about your usecase). SICK as a concept is simple. SICK as the library was created to cover some particular usecases and may be not suitable for everyone. We would welcome any contributions.
  - duped 1y ago
    If you use varints for pointers you can have the best of both worlds, and achieve even better compaction for the smallest objects.
    - pshirshov 1y ago
      Yep, can be done but they aren't free because of variable size. With constant pointers I can access const-sized elements directly, with varints I would have to do some rituals. I have another binary encoding for different purposes (https://github.com/7mind/baboon https://github.com/7mind/baboon) which relies on varints, in case of SICK I decided to go with pointers of constant size to save some pennies on access efficiency.
- halayli 1y ago
deleted 1y ago
[deleted]
deleted 1y ago
[deleted]
keyliejener 1y ago
[flagged]
noobcoder 1y ago
it could be really useful for cases where youre repeatedly processing similar JSON structure like in case of analytical events but any plans for language bindings beyond the current implementation?
- pshirshov 1y ago
  > any plans for language bindings beyond the current implementation? If we need more bindings for the projects we work on - we will implement and opensource them. E.g. recently we added rudimentary JS support (no cursors, just encoder/decoder). For many reasons, we avoid working on something we don't use ourselves and we are not paid for. But your contributions are very welcome. Also we would be happy to have you as a paying client.
slashdave 1y ago
So... isn't this just a database, and a bespoke one at that?
- pshirshov 1y ago
  Yes, it's a specific JSON repiesentation and a tiny database based on it.
IshKebab 1y ago
This sounds quite similar to Amazon Ion which is one of the few binary JSON formats that allows sparse reads, and deduplicated keys. However I found that in cases where you have the requirements of streaming/random access and every entry is the same... SQLite is a really great choice. It's way faster and more space efficient than it has any right to be, and it gets you proper random access (not just efficient streaming), and there are nice GUIs for it. And you can query it.
- pshirshov 1y ago
  SQLite was assessed for our usecase. SQLite representations of our data were much bigger, it was much slower with our access patterns and we didn't need all the power of SQL.
kordlessagain 1y ago
Use for vectors and stream smaller projections first?

124 points by pshirshov 1y ago

I started on something a bit like this, but using sqlite instead of a custom serialisation format: https://github.com/DavidBuchanan314/dag-sqlite https://github.com/DavidBuchanan314/dag-sqlite (it's intended to store DAG-CBOR objects but it is trivial to represent a JSON object as DAG-CBOR)

pshirshov 1y ago
SQLite was bit too heavy for our usecase unfortunately. We tried it as one of the first options.

gethly 1y ago

It is a bit confusing that JSON is being mention so much when in reality this has nothing to do with it - except to showcase that JSON is not suitable for streaming whereas this format is. Secondly, I fail to see advantages here as the claim is that it allows streaming for partial processing compared to JSON that has to be fully loaded in order to be parseable. Mainly, because the values must be streamed first, before their location/pointers in order for the structure to make sense and be usable for processing, but that also means we need all the parent pointes as well in order to know where to place the children in the root. So all in all, I just do not see why this is advantageous format above JSON(as that is its main complaint here), since you can stream JSON just as easily because you can detect { and } and { and ] and " and , delimiters and know when your token is complete to then process it, without having to wait for the whole structure to finish being streamed or wait for the SICK pointers to arrive in full so you can build the structure. Or, I am just not getting it at all...

xenadu02 1y ago
Most existing JSON parsers don't support streaming but that's not inherent in the format. It is definitely possible to stream writes easily but it's just as possible to stream parsing.
pshirshov 1y ago
> when in reality this has nothing to do with it It's a specific representation of JSON-like data structures, with an indexed deduplicated binary format and JSON encoders and decoders. Why "nothing"? It's all about it. Mostly it's not about streaming. More efficient streaming is a byproduct of the representation. > because you can detect { and } and { and ] and " and , You need a pushdown automaton for that. In case of SICK you don't need potentially unbounded accumulation for many (not all) usecases. > the values must be streamed first, before their location/pointers Only to avoid accumulation. If you are fine with (some) accumulation, you can reorder. Also think about the updates. But again, streaming is a byproduct. This tool is an indexed binary deduplicating storage which does not require parsing and provides amortized O(1) access time.
- aaronblohowiak 1y ago
  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”.
8organicbits 1y ago
I think this quote explains the efficient streaming: > There is an interesting observation: when a stream does not contain removal entries it can be safely reordered. So if I'm understanding, the example in the readme could be sent in reverse, allowing the client to immediately use root:0 and then string:2 while the rest streams in. I was looking for something like this, but my use case exceeds the 65k key limit for objects.
- pshirshov 1y ago
  > 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.
- gethly 1y ago
  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.
  - pshirshov 1y ago
    > has nothing to do with JSON itself. It's literally a deduplicated indexed binary storage for JSON (plus an approach to JSON representation more suitable for streaming than serialized JSON). > we can do the same thing I would highly encourage doing same things! For some reason people love to fully parse a 50MiB long JSON document when they need just 0.1% of the data in it.

qixxiq 1y ago

Current implementation has the following limitations: Maximum object size: 65534 keys The order of object keys is not preserved ... These limitations may be lifted by using more bytes to store offset pointers and counts on binary level. Though it's hard to imagine a real application which would need that. I've worked on _many_ applications which have needed those features. Object keys is a per implementation detail, but failing at 65k keys seems like a problem people would likely hit if this were to be used at larger scales.

pshirshov 1y ago
In our usecase, for which we created the library, we made this tradeoff to save several bytes per pointer and keep binary form more compact. The application splits large objects into smaller chunks. 99% of the structures there are relatively small but there are tons of them. Most likely you can do the same - just split large structures into smaller ones. If you need support for larger structures, you may create your own implementation or extend ours (and I would really like to hear about your usecase). SICK as a concept is simple. SICK as the library was created to cover some particular usecases and may be not suitable for everyone. We would welcome any contributions.
- duped 1y ago
  If you use varints for pointers you can have the best of both worlds, and achieve even better compaction for the smallest objects.
  - pshirshov 1y ago
    Yep, can be done but they aren't free because of variable size. With constant pointers I can access const-sized elements directly, with varints I would have to do some rituals. I have another binary encoding for different purposes (https://github.com/7mind/baboon https://github.com/7mind/baboon) which relies on varints, in case of SICK I decided to go with pointers of constant size to save some pennies on access efficiency.
halayli 1y ago

deleted 1y ago

[deleted]

deleted 1y ago

[deleted]

keyliejener 1y ago

[flagged]

noobcoder 1y ago

it could be really useful for cases where youre repeatedly processing similar JSON structure like in case of analytical events but any plans for language bindings beyond the current implementation?

pshirshov 1y ago
> any plans for language bindings beyond the current implementation? If we need more bindings for the projects we work on - we will implement and opensource them. E.g. recently we added rudimentary JS support (no cursors, just encoder/decoder). For many reasons, we avoid working on something we don't use ourselves and we are not paid for. But your contributions are very welcome. Also we would be happy to have you as a paying client.

slashdave 1y ago

So... isn't this just a database, and a bespoke one at that?

pshirshov 1y ago
Yes, it's a specific JSON repiesentation and a tiny database based on it.

IshKebab 1y ago

This sounds quite similar to Amazon Ion which is one of the few binary JSON formats that allows sparse reads, and deduplicated keys. However I found that in cases where you have the requirements of streaming/random access and every entry is the same... SQLite is a really great choice. It's way faster and more space efficient than it has any right to be, and it gets you proper random access (not just efficient streaming), and there are nice GUIs for it. And you can query it.

pshirshov 1y ago
SQLite was assessed for our usecase. SQLite representations of our data were much bigger, it was much slower with our access patterns and we didn't need all the power of SQL.

kordlessagain 1y ago

Use for vectors and stream smaller projections first?