Key Value Stores?

[Arun Sharma]

Have you guys thought about how to write and read back flatbuffers from/to key value stores?

 -Arun

[Wouter van Oortmerssen]

A FlatBuffer is just a binary string of bytes, so any key/value store that can have that as its value should work.

On Thu, Aug 25, 2016 at 4:12 PM, Arun Sharma <arun....@gmail.com> wrote:

Have you guys thought about how to write and read back flatbuffers from/to key value stores?

 -Arun

--
You received this message because you are subscribed to the Google Groups "FlatBuffers" group.
To unsubscribe from this group and stop receiving emails from it, send an email to flatbuffers+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Arun Sharma]

Forgot to cc the group

On Aug 26, 2016 7:13 PM, "Arun Sharma" <arun....@gmail.com> wrote:

I was thinking about support for storing some part of the buffer on the key and the rest on the value to allow for efficient lookup, range queries etc.

Would need relaxation of the single key per table constraint or a new syntax.

[Wouter van Oortmerssen]

Ok, I thought you were referring to interop between an key/value db and FlatBuffers.

It is also already possible to store a key/value vector using the `key` attribute, `CreateVectorOfSortedTables` and `Vector::Lookup`. (in C++, but was just added to Java/C# as well).

What exactly are you looking to do?

[Arun Sharma]

On Mon, Aug 29, 2016 at 10:02 AM, Wouter van Oortmerssen <w...@google.com> wrote:
> Ok, I thought you were referring to interop between an key/value db and
> FlatBuffers.
>
> It is also already possible to store a key/value vector using the `key`
> attribute, `CreateVectorOfSortedTables` and `Vector::Lookup`. (in C++, but
> was just added to Java/C# as well).
>
> What exactly are you looking to do?

There are a set of encoding schemes to encode tables into key value
stores such that the tuple ordering of the table is that same as the
string key in the key-value store. https://github.com/ndimiduk/orderly
is an example of such a library.

These encoding schemes are decoupled from in-memory and network
focused encoding schemes such as flatbuffers.

I'm looking to eliminate data copies when reading from a key-value
store, performing some in-memory filtering and sending the buffer over
the wire.

Sample schema:

table Person (original_order) {
country:string (key);
age:long (key);
score:double (key);
id:long (key);
name:string;
mydata:string;
};

could be stored as <country, age, score, id> => <name, mydata> in a
sorted-map type of key-value store.

One requirement is that metadata such as vtables, lengths of
strings/vectors can't be stored on the "key" since they affect
sorting. Storing on the "value" part of the row should be ok though.

-Arun

[Wouter van Oortmerssen]

There's no reason why we can't sort on multiple keys, there is already a generated code function for the comparison, it can work on 3 fields rather than one. Lookup currently expects a single value, that may be a bit harder to change.

[Arun Sharma]

On Mon, Aug 29, 2016 at 4:49 PM, Wouter van Oortmerssen <w...@google.com> wrote:
> There's no reason why we can't sort on multiple keys, there is already a
> generated code function for the comparison, it can work on 3 fields rather
> than one. Lookup currently expects a single value, that may be a bit harder
> to change.

Here's a proof of concept hack (breaks some of the unit tests, but
hopefully gets the ideas across better).

https://github.com/adsharma/flatbuffers/commit/3371c8aadb8615506dd177f85520f3a07eafdf10

Although many key value stores accept a custom compare function, they
work a lot better when keys are sorted lexicographically. So I took
the approach of generating byte arrays that can be passed to memcmp
instead of comparators that take 3 keys.

Not done yet:

* Only obj->GetKey() is generated, we need obj->GetValue()
* string keys are not handled. My understanding is that they're stored
out of line. But we need them inline for lexicographically ordered
keys
* Building the object from the key/value read from a key value store:
SetKey/SetValue methods.

obj->ByteOrderFields() and obj->HostOrderFields() are probably cheaper
on big-endian machines. As you can see from serialize.h, they
manipulate the data in place.

In some sense, what I'm thinking of is similar to Apache Arrow, but
for row oriented key value stores instead of column oriented.

-Arun

[Wouter van Oortmerssen]

Had a look, but.. it is not that clear. Why is the code related to this host/byte order stuff needed? what's the bit twiddling in there doing?

In FlatBuffers, everything is already always little endian, on any system.

If you included the newly generated code in the commit, it be easier to follow. Maybe some comments.

[Arun Sharma]

On Fri, Sep 9, 2016 at 5:48 PM, Wouter van Oortmerssen <w...@google.com> wrote:
> Had a look, but.. it is not that clear. Why is the code related to this
> host/byte order stuff needed? what's the bit twiddling in there doing?

The reason why it's needed is, the key value store (at least the ones
that implement a sorted-map) wants a raw string that compares the same
way as a std::tuple<key-columns> Some python examples:

>>> 3 < 257
True

// Little Endian - different answer
>>> struct.pack('q', 3) < struct.pack('q', 257)
False

// Big Endian - same answer
>>> struct.pack('>q', 3) < struct.pack('>q', 257)
True

However, even big endian fails for signed integers.

>>> 3 < -4
False

>>> struct.pack('>q', 3) < struct.pack('>q', -4)
True

requiring some sign bit dependent bit twiddling. More details in the
unit tests here:

https://github.com/adsharma/keyencoder/blob/master/python/encoding.py

There is a C++ implementation in the same github repo. I adopted these
algorithms to a header-only library that does it in-place (as opposed
to encoding to another string).

>
> In FlatBuffers, everything is already always little endian, on any system.
>

That's great and I understand why. But it won't sort as desired by a
key value store using its default comparator.

> If you included the newly generated code in the commit, it be easier to
> follow. Maybe some comments.

I pasted the generated code in a comment on this commit (all the way
at the end):

https://github.com/adsharma/flatbuffers/commit/3371c8aadb8615506dd177f85520f3a07eafdf10

Desired result for the write path:

The in-memory representation of the table is persisted to the key
value store with a minimal amount of in-place bit-twiddling for ints
and doubles. Strings need no bit-twiddling.

Desired result for the read path:

The key value store has read the data from storage and we want to send
the object to a client over the network. It's possible that a hot
object is requested thousands of times. I'd like to pay the
->HostOrderFields() cost once and subsequently ship bits over the wire
with zero copy.

Glitch: the current vtable based format doesn't guarantee that the
memory returned by GetKey() is usable for db->Write(key, value), where
key and value are pointers to strings. We may have to generate another
method using techniques such as Cords/Ropes, while minimizing copy.

https://en.wikipedia.org/wiki/Rope_(data_structure)

-Arun

[Wouter van Oortmerssen]

I think I see what you're doing now.

I feel this is a bit too specialized a use case to be supported by the core of FlatBuffers, it be better if it was implemented on top of it.

Btw, for guaranteeing that multiple scalars are adjacent in memory, use a struct? That doesn't cover strings though.

As for little endian producing the wrong sort order, I'm not sure that is a problem as long as you're looking up a single item by equality (as opposed to a range of values).

I guess RocksDB doesn't take a comparison function instead of a block of memory?

Another path would be to replace all your key values with just a `string`. Then you can just pack the std::tuple into that, and it be ready for instant lookup on the other side.

[Arun Sharma]

On Mon, Sep 12, 2016 at 12:11 PM, Wouter van Oortmerssen <w...@google.com> wrote:
> I think I see what you're doing now.
> I feel this is a bit too specialized a use case to be supported by the core
> of FlatBuffers, it be better if it was implemented on top of it.

Agreed. I'm looking for minimal (optional) codgen hooks into flatc to
get it done. The rest of the support libraries could live elsewhere.

>
> Btw, for guaranteeing that multiple scalars are adjacent in memory, use a
> struct? That doesn't cover strings though.
>

structs don't allow schema evolution?

> As for little endian producing the wrong sort order, I'm not sure that is a
> problem as long as you're looking up a single item by equality (as opposed
> to a range of values).

Many use cases involve ranges and multi-item indexing.

>
> I guess RocksDB doesn't take a comparison function instead of a block of
> memory?
>

RocksDB does allow custom comparators. However, these comparators add
costs even when the app is not accessing storage. For eg: when the LSM
(log structured merge tree) is doing background compaction.

As a result, most LSM based database systems (MySQL, Mongo, HBase etc)
use a simple lexicographic (byte ordered) comparator.

> Another path would be to replace all your key values with just a `string`.
> Then you can just pack the std::tuple into that, and it be ready for instant
> lookup on the other side.

That's exactly what I'm trying to accomplish. Instead of ad-hoc string
encodings that everyone does differently, standardize it and build it
into the schema code generation system.

-Arun

[Arun Sharma]

On Mon, Sep 12, 2016 at 12:23 PM, Arun Sharma <ar...@sharma-home.net> wrote:
> On Mon, Sep 12, 2016 at 12:11 PM, Wouter van Oortmerssen <w...@google.com> wrote:
>> I think I see what you're doing now.
>> I feel this is a bit too specialized a use case to be supported by the core
>> of FlatBuffers, it be better if it was implemented on top of it.
>
> Agreed. I'm looking for minimal (optional) codgen hooks into flatc to
> get it done. The rest of the support libraries could live elsewhere.
>

Made some changes on the github branch in response to the discussion.

Here's what I'm thinking:

* Most of the key value store logic can stay inside a "builder" that guarantees layout and knows about the key vs value fields. This could either stay out of tree if you prefer or in some loosely coupled directory.

* Need a new data type similar to flatbuffers::Vector. The main difference is that it doesn't assume that length and data are adjacent to each other in memory. Instead, the layout could be <f1, f2, f3> => <length, &f2> if f1, f3 are ints and f2 is a key string. Perhaps call it IndirectVector?

-Arun

[Wouter van Oortmerssen]

Made some changes on the github branch in response to the discussion.

Here's what I'm thinking:

* Most of the key value store logic can stay inside a "builder" that guarantees layout and knows about the key vs value fields. This could either stay out of tree if you prefer or in some loosely coupled directory.

Yes, this is all a bit too specialized to be modifications to the main FlatBuffers implementation. 

* Need a new data type similar to flatbuffers::Vector. The main difference is that it doesn't assume that length and data are adjacent to each other in memory. Instead, the layout could be <f1, f2, f3> => <length, &f2> if f1, f3 are ints and f2 is a key string. Perhaps call it IndirectVector?

What is this used for?

Wouter

[Arun Sharma]

On Mon, Sep 19, 2016 at 10:58 AM, Wouter van Oortmerssen <w...@google.com> wrote:

>>
>> * Need a new data type similar to flatbuffers::Vector. The main difference
>> is that it doesn't assume that length and data are adjacent to each other in
>> memory. Instead, the layout could be <f1, f2, f3> => <length, &f2> if f1, f3
>> are ints and f2 is a key string. Perhaps call it IndirectVector?
>
> What is this used for?

To ensure that only the actual bytes in the string f2 (not the length)
are returned by GetKey().

-Arun

[Arun Sharma]

On Mon, Sep 19, 2016 at 11:18 AM, Arun Sharma <ar...@sharma-home.net> wrote:

>> What is this used for?
>
> To ensure that only the actual bytes in the string f2 (not the length)
> are returned by GetKey().
>

Some code here to explain what I'm thinking:
https://github.com/adsharma/flatbuffers/commit/51f46e430b39fe9a0cc0817918e2cb3b5e72b8d7

Rest of the commits are accessible from:

https://github.com/adsharma/flatbuffers/commits/byteorder

The minimal changes to flatbuffer repo I can think of:

* Indirect vector/string in the above commit. No changes to the
existing vector/string classes.
* Lines 56-82 in this file to be code generated:

https://github.com/adsharma/flatbuffers/blob/41a60f63a599e681e7377eb81f5a855415a7b8d8/tests/kvstore_test1_generated.h#L56

The rest of it can probably live in a KeyValueStoreBuilder class elsewhere.

-Arun

[ch...@jumis.com]

Thanks for posting these, Arun.

I've come up across similar use cases with sorted data and flatbuffers.

 

https://github.com/adsharma/flatbuffers/commits/byteorder
https://github.com/adsharma/flatbuffers/blob/41a60f63a599e681e7377eb81f5a855415a7b8d8/tests/kvstore_test1_generated.h#L56

 

-Charles

 

[Arun Sharma]

Glad you found it interesting Charles.

The work in progress patches are here:
https://github.com/adsharma/flatbuffers/commits/byteorder2

Still TODO:

* Complete the skeleton KVStoreBuilder. Right now, using this code
requires you to carefully do fbb.add_member() in LIFO order (v2, v1,
k2, k1) if you want: <k1, k2> => <v1, v2>. I'd like to remove this
restriction

* Handle strings and vectors. I have added the concept of indirect
strings and indirect vectors, but they're not used yet.

The main idea is that strings on the key side have metadata (length
and buffer offset) stored on the value side, but the actual bytes are
stored in the key.

* Support reading from key value store. The code that exists allows
you to write to a key value store while maintaining sorting. But the
code to read needs to be hand written. I'd rather code generate it
(also requires reconstruction of the vtable from schema).

If anyone is interested in working on this or reviewing patches,
please ping this thread or watch the git repo above.

-Arun