Streaming KDB IPC Data – Some Assembly Required

It used to be the case that we rewrote c.java to be more efficient. I haven’t downloaded it for ages, and have a feeling that it now uses primitive arrays under the covers for data-types which were formally stored as arrays-of-objects (e.g. java.sql.Time[]).

Another improvement which is possible to make is processing as much of the IPC message as possible from whatever partial amount of input data you receive, without waiting for it all to arrive. I’m not sure that anyone using kdb+ is working on a slow network but I suppose they could be working in a resource-constrained environment (a dev-VM, perhaps), so using a fixed-size read-buffer may be attractive.

Anyway, to resume parsing, all you need to do is figure out from where in your object graph to resume deserialising.

Preliminaries

What you need to do is decide which elements of the stream must be read atomically: for example, in the libraries where I’ve used this technique, the code refuses to consume a partial vector-header. Given, say, four of the six bytes that comprise the header, you could determine the type to instantiate and its attribute, but not know its length — and you’d have to remember the two bytes of length-data until the rest of it arrived. Similarly, it would refuse to read half an int64_t value.

This feels a lot like something you could solve with a coroutine: all you need to do is remember how many bytes you’ve consumed, and on each successive deserialisation pass, walk the incomplete object graph, computing how many bytes would have been read by the data you’ve materialised, until it’s time to “lower the stylus” and decode more of the IPC data.

A quick primer on type encoding:

Atoms

KDB encodes its atom values as a type-byte and a value. Here’s a boolean true:

0xff                 type byte -1
    01               "true"

Here’s an int32_t:

0xfa                 type-byte -6
    2a000000         "42" in little-endian format

The annoyance of parsing KDB IPC data comes mostly from its symbol data, which are null-terminated C-strings (the annoyance being that you have to visit each byte to see whether we’re there yet, whereas regular types have length element-count * element-width):

0xf5                 type byte -11
    416e6e6f79656400 "Annoyed\0"

Vectors

KDB encodes its vectors with not just their element-count but an attribute as well, denoting whether they’re sorted, parted, grouped etc.. Here’s a character vector:

0x0a                                       type byte      10
    00                                     no special attribute
      0d000000                             length         13
              48656c6c6f2c20776f726c6421   character data "Hello, world!""

Dictionaries

Dictionaries are simply a type-byte followed by two KDB “sequences”, which includes lists and vectors. A Dictionary can have a table as its key, and if it has a table as its value we know it as a keyed-table. The encoding is very compact. Here is "abc"!"def":

0x63
    0a0003000000616263
    0a0003000000646566

Tables

KDB takes the idea that its tables are a specialisation of dictionaries to the full extent and encodes a table as a dictionary but with a couple of bytes prepended (flip`a`b!enlist each "ab"):

0x62                                   type byte -98
    00                                 
     63                                dictionary type -99
       0b000200000061006200            symbol-vector `a`b
       000002000000                    column-list of length 2
                   0a000100000061      first column, containing "a"
                   0a000100000062      second colum, containing "b"

Yes, and?

The point of reciting the above is simply to illustrate how you might choose where the read-boundaries lie.

I’ve typically decided upon being willing to read an atom’s type-byte, without being able to complete the read of its payload. Guid atoms are only 17 bytes. Even a very long symbol is unlikely to challenge the resource-constrained.

I’ve chosen to read a vector header completely or not at all, and I choose not to read partial elements, by which I mean I will not read part of an int32_t, or part of a symbol. Lists are different: once I’ve read the list’s header I’m happy to have a partial object representation in its storage between decoding passes.

Dictionaries aren’t really even part of this design process as they (like atoms) have only a single byte to read before you’re onto their payload. I prefer to read all three bytes of a table-header before proceeding.

What about compression?

It turns out that as long as you store a few state-variables between decompression-runs, you can make progress even with a partial read of compressed data. You do need to figure out the algorithm that tells you how many input bytes will be required to complete the current block, which is simple enough, give or take a couple of gotchas. Then the partial message you’ve decompressed can be fed into the resumable IPC parser, allowing you to make progress while bytes are theoretically still on the wire. I’m mindful of recent claims that the network will outpace the CPU, but even so, you can “get stuff done” between reads.

If you were aiming to be as economical as possible with memory, you could think about how to free the bytes you’ve decompressed as soon as they’ve been consumed by the parser. However, this adds significant complexity as the compression algorithm uses a look-behind mechanism: you need to know what you decompressed at index I so you can replay N bytes of it. It really is just simpler to retain the decompressed IPC bytes, which is what I’ve done in the C++ library.

A C++ library I’m working on

Can be found here.