Comments on the BED format

[jlouis]

I'm running all of the specification in indentation, and keeping my comments here. This will give me the ability to comment on parts of the document a bit at a time.

::: Binary Electronic Data specification

This binary data serialization format was created for use in
RESTful services or with Websockets. Compared to most other
formats, it comes with three special types: hyperlinks,
symbols and RFC 3339 dates.

The idea of including hyperlinks is huge. We need that for HATEOAS, so why not simply include it right away? That move is brilliant. Keep it! Also, the RFC 3339 support beats ISO8601 due to simplicity. I like it a lot.

…

We are looking for any kind of feedback at this point.

Two precedents that must be studied:

• data.fressian—the storage format of Datomic
• UBF(A/B)—Joe Armstrong's Universal binary format

The reason to study these two is that they get a lot of things right that other formats gets wrong. If you avoid something from these formats, you must at the least provide rationale for doing so.

The data.fressian format is described here https://github.com/Datomic/fressian/wiki

The ubf format is described here http://ubf.github.io/ubf/ubf-user-guide.en.html

• The data.fressian format generalizes BED-symbols by using bytes for caching any part of the data. This is useful since you can cache an 8-byte timestamp value as a 1-byte entry.
• A (mathematical) Set type is included
• UUIDs are included in the format as a core type
• Regular expressions is a data type
• Large pieces of data—strings and binaries—are stored chunked in 64 Kilobyte chunks. This helps with decoders since they can stream-process data.

And for ubf(a):

• UBF(A) has semantic tags. That is, a way to annotate data with a tag. This means you can avoid user-defined data if it can be built from the data already in the BED spec. Because you can just tag it semantically with its meaning.
• UBF(A) runs as a virtual machine with a recognition stack. This allows you to cache data by pushing the stack to a register and pulling it back again.

Also, one thing I have considered is to build up things with a two-stage format. First you encode the structure of the data, followed by the data itself. This means you can re-use the map keys in multiple map entries which look the same. It avoids a lot of the needless copying of keys in JSON. In addition, a parser can exit early if it doesn't recognize the structure as valid. It can force correct structure early.

…

In addition to these types, it is possible to define up to
255 additional application-specific types using extensions.

I would probably use semantic tags for this to avoid half a billion different variants of the format.

:: Media type

…

: `application/x-bed`

…

: `application/x-bed-stream`

I really like this distinction.

…

:: Types

…

: Symbol

Symbols are a very simple and yet very important optimization
and serve to greatly reduce the quantity of data being sent.

I think I would look at generalized caching instead of this.

: Binary
: String

Strings must be valid UTF-8 text, as defined in RFC 3629.

Yes! Split binaries and strings in the spec. Good move.

: RFC 3339 date

…

: Integer

…

: IEEE 754 binary64

Double precision floating-point numbers can be encoded using
the IEEE 754 binary64 format. This format uses 64 bits to
encode the number.

…

: IEEE 754 decimal64

Decimal numbers can be encoded using the IEEE 754 decimal64
format. This format uses 64 bits to encode the number.

…

: Map

Maps are an unordered list of a fixed number of key/value pairs.

Keys can be of any type, although they probably should be
symbols when possible. Values can of course be of any type.

The order of key/value pairs has no meaning and does not
need to be preserved.

There must not be any key duplicate in the map. If a duplicate
is found then decoding must stop immediately and an error must
be thrown. Decoders can of course provide an option to disable
this behavior.

I really like that you rule out the corner-cases right away. This usually helps. Consider encodings where keys can be reused efficiently among several maps in an array.

: Array

Arrays are an ordered list of a fixed number of values.

Values can be of any type.

Thought: call these vectors and force all values to be the same type.

…

: List

…

:: Extensions

…

:: Binary representation

The BED format uses network byte order (big endian).

…

:: Encoding/decoding state

To be able to encode or decode symbols appropriately, state
must be maintained.

…

:: Security considerations

The format provides no security mechanism. A number of problems
may occur during decoding or after decoding a message.

During decoding, extra care must be taken to avoid running out
of memory. Some of the types allow for very large values. However
it is not recommended to limit the size of these directly. Two
solutions are available.

…

[essen]

OK here's my reply. Hopefully I did not forget things, but might have as you said a lot. :-)

Links are what made me work on this in the first place so I'm glad you like it. Dates came later as a realization that there's too many ways to represent a date and we should really settle on one (for interchange purposes anyway, applications can then do what they want).

I did look at both Fressian and UBF while working on this.

Generalizing symbols is equivalent to creating your own compression and is not terribly interesting. If you are going to have data that repeats itself over and over you should probably deflate the message or stream. Symbols are doing the best effort scenario in that we win a lot without sacrificing much speed or using too much CPU. There's only a limited number of them even in long streams, unlike things like timestamps. Also in the case of the Web, there's very little things that actually repeat themselves so the costs of implementing that mechanism aren't that obvious, especially compared to just enabling compression through HTTP or Websocket, should you really need it.

I am not sure what a mathematical set type gives us.

UUIDs I had in mind but could not work out a reason to create a separate type. They are just a 128bit number. We can store these already. I'm not sure what we would gain from differentiating them.

I had no idea how a regular expressions type would be useful, let alone why would anyone send a regular expression as part of a message. I totally understand it in the case of a programming language, but having a simple way to identify them as regular expression doesn't help an external system understand on what they should be used, so it wouldn't convey enough information if we were to have a type for them.

There is 0 issues with streaming the large strings and binaries as they are. The intermediate representation used by encoders/decoders simply has two ways of representing them, one for small ones and another for large ones. This has no incidence on the actual encoded data though, it's purely an implementation concern. The only case when chunks become useful is when we can't know the size in advance, and these are quite specific to the application at hand, and need to be specified in its custom media type so that the receiver can understand what it is it's receiving and what to do with it.

Nothing prevents you from using formats defined in the BED spec when using extensions. The extension value or blob can be anything you need it to be, including BED types. Only their interpretation is specific to the extension. You could very well do something like extension(array(currency_symbol, money_decimal, timestamp)) for example, and use the same encoder/decoder code for the values inside the extension blob. I know it's probably a poor man's semantic tags, but considering JSON I do not think many people care about such things anyway (as unfortunate as it may be). So the goal here is to allow extensibility for those that need more, not make it a central part of the format that nobody will care about.

I'm not sure what you mean by the recognition stack.

I see your point about map keys (pretty much how maps work in erlang), but encoding the structure also makes it hard to update it when using streams, and we would lose the flexibility that people expect. Wanting to error out when a map has a little more or a little less data than expected is pretty niche (again, as bad as it may sound), most applications would rather gracefully (or less gracefully) handle these cases when they appear.

Forcing arrays to all have the same type would add nothing to the format itself, because even if we have an array of integers, these might be encoded differently depending on the value and so we can't avoid having the type byte before each value. The actual enforcing then makes little sense in the encoder/decoder and can be left as an option for the application to perform.

Thanks for the feedback!!