3 ms·
Anyone know of an efficient binary format similar to MessagePack that supports deserializing only whitelisted keys, and not paying the penalty of parsing data t
by atombender 7y ago
Anyone know of an efficient binary format similar to MessagePack that supports deserializing only whitelisted keys, and not paying the penalty of parsing data that isn't needed?
MessagePack is great, but libraries generally only support deserializing the whole thing. I have an application where these structured documents can be very large, and scanning code sometimes only needs a very small subset of keys.
I believe Cap'n Proto has this feature, but unlike MessagePack it's not schemaless.
For example, given a struct like this:
{
"id": "123",
"name": "Developers",
"members": [{
"id": "567",
"permissions": [
{"type": "read"},
{"type": "write"}
}
}]
}
Let's say I only want the name, the ID of each member, and whether permissions.read is set. I may want to do something like (Go):
StreamingUnmarshal(b,
func(keypath string, parse func() interface{}) {
switch keypath {
case "id", "members.id":
value := parse()
// ... use value ...
case "members.permissions.type":
if parse().(string) == "read" {
// ...
}
}
})
Random access could be also work, as long as it didn't need to sequentially parse from the beginning of the data to get to the right value each time. Something like:
id := GetKey(b, "id")
memberIDs := GetKey(b, "members.id")
permissionTypes := GetKey(b, "roles.permissions.type")
The trickiest bit is treating arrays of nested structs (as in "roles.permissions.read") correctly, although efficient scanning of keys becomes an important optimization point, too.
Probably the best method would be to store the keys pre-sorted at the beginning of the data, so that they'd better fit in the CPU cache, and have pointers to the offsets of the values:
KEY1,KEY2,KEY3,VALUE1,VALUE2,VALUE3
Arrays of structs are tricky here, again, but this is solvable.
- kentonv 7y agoHave you considered using a sqlite file? No, seriously: It doesn't require an external schema, supports every kind of indexing and fast random access you could want, is supported in like every language, OS, and architecture, has copious tooling, documentation, and community support, and is battle-tested across literally billions of installations worldwide.
- atombender 7y agoNo, that would not make any sense. SQLite cannot deal with structured, hierarchical data like the stuff I described in my comment. Also, I am talking about individual documents that already live in a database such as PostgreSQL. I can't store an entire SQLite database in a single column.
- kentonv 7y ago> I can't store an entire SQLite database in a single column. Sure you can, it's just a file. :) sqlite scales down nicely to data sets of just a few kilobytes -- if you're worried about parse time of your documents then I assume they are larger than that. That said, if you're already loading the whole blob from a single row in Postgres anyway, then is random access such a big win? Or is the idea that you would selectively read byte ranges out of Postgres? If you're already pulling the bytes into RAM then avoiding the parse isn't that huge of a win. (I say this as the author of Cap'n Proto which is all about zero-copy random access... it's only a big win in certain use cases, like mmap() or shared memory IPC.)
- atombender 7y agoWell, many documents are several megabytes, but many are in the order of 100 bytes. I need a serialization scheme that scales up to large documents and down to tiny ones. I can't imagine that the overhead of initializing an SQLite database from a small byte array in memory is that small, not to mention the overhead of maintaining the table schema. Out of pure curiosity, I glanced at the Go bindings for SQLite, and there's no provision for initializing a database from a byte array, or accessing the raw underlying byte data of a live database. The C API supports implementing your own VFS for custom storage, but that's not supported by the Go bindings, and seems like a lot of work. You're right about loading whole blobs; I was misremembering a little bit. The application in question already pares down the document keys in its queries to avoid sending everything. I'm in the middle of a research project into an alternative backend where the documents are stored as binary data, not JSON, and given a set of keys/keypaths, I want to do a little better than deserializing the whole blob.
- dnr 7y agoTake a look at FlexBuffers, part of FlatBuffers. FlatBuffers itself is similar to CapnProto and requires a schema, but FlexBuffers is a related schema-less format that uses a bunch of the encoding techniques from FlatBuffers to gain advantages like (I believe) not having to parse unneeded substructures.
- atombender 7y agoThanks, that looks nice. But it looks like FlexBuffers is only implemented in C++ and Java.