The Blink Protocol
blinkprotocol.org
blinkprotocol.org
- The messages are prefixed with the message length; this allows has a variety of advantages (ie. splitting up messages with minimal parsing) but forces you to know your message size in advance. In the general case, this requires processing the full structure before the first byte can be written. (On the other hand, protocol buffers can be written incrementally, with a single pass over the data and using constant memory.)
- Since the blink format contains no metadata, the recipient must have the schema with which the message was written. If schema migrations must be supported, this requires prefixing each batch of messages with the (encoded) schema. This may only be efficient when the batch size is large. (See Apache Avro [1] for another format that makes this tradeoff; since Avro is intended for processing in Hadoop, where the typical dataset has some millions of records, prefixing with the schema is not significant overhead.)
[0] http://blog.blinkprotocol.org/2013/01/blink-compared-to-goog... [1] http://avro.apache.org/docs/current/spec.html
This is essentially a non-starter for me after a couple years of building distributed systems using protocol buffers, for which protocol evolution is the first feature.
Anders
If you don't transmit the schema of the message, you're in the same spot as Thrift or Protocol Buffers. Which, then, leaves you with that eternal question: pourquoi, ets-ce que?
"Finally, Blink defines a method of transferring a serialized schema that can be used to notify a receiver of a Blink message stream of the structure of the transferred messages. A similar method could be added on top of GPB, but would again be non-standard."
I think this is incorrect; the protobuf library includes exactly the same thing, unless I'm misunderstanding what the Blink authors are talking about. protoc can turn a textual schema into a protobuf-serialized message that describes it, which a receiver can use to decode messages of that type with no prior information:
https://code.google.com/p/protobuf/source/browse/trunk/src/g...
https://developers.google.com/protocol-buffers/docs/referenc...
Rolf
The problem was that it causes unnecessary complexity in validation and parsing, as <length-of-message><message>... describes a context-sensitive grammar, while a more XML-, JSON-like syntax with delimiters <delim><message></delim>... is context-free. The complexity of proper CSG validation can be exploited for resource-depletion/DOS attacks, while not validating the syntax of a message leaves part of the program that uses the data in these messages with potentially invalid data, putting it into an inconsistent state, possibly leading to DOS or worse exploits.
At least that's what I got from their presentation, which was very interesting BTW, especially the part about "weird machines"--that's basically the inconsistent state, the emergent machine that is made out of all the things an attacker can make a system do by exploiting it. It was also extremely geeky.
It just left me wondering: if I understood this right, every protocol that uses message-length prefixes is at least vulnerable to resource-depletion attacks, and there's no way of solving this short of proving P=NP. But that's quite a lot of protocols! Why isn't the Internet burning down as we speak?
Should take care of any resource depletion issues, and do it way faster than eating data waiting for an end of field marker would.
For the reader a message consists of <length>+<blob>+<length>+<blob>+ etc. It can be in two states, having enough data, so pass the blob on to the parser (and it doesn't have to validate that the blob is length bytes, we know that already); or awaiting more data (you can attack that by dribbling data slowly, but you can do that with any protocol).
EDIT: Ok, I used a flat structure there, it would be different in a recursive structure with length on every element. But a top level reader that reads <length> bytes of the outer wrapper and doesn't muck about with the innards is still a sensible thing.
> But in any normal design you never put the message length into the same parser, you use it to read the message, and the parser is fed the message when you have received that many bytes.
Won't work, this is a fundamental problem in computing science.
Splitting the parser into a pre-parser and a post-parser isn't going to help solve the fundamental problem, because the combination of two parsers is still a parser.
One of the problems is, you cannot distinguish <blob> bytes from <length> bytes. If the data stream gets out of sync with the parser state (hiccup, dropped packet), you have a very non-trivial problem on your hands. A context-free grammer however, is free of context (ohh!) and can therefore resync in time proportional to how deep it's nested.
Speaking of nesting, that's another bit where I expect CSGs to become incredibly hairy: Of course you can use a hybrid approach: length-prefixed messages for the "outer stream", and a context-free XML/JSON/Lisp style format (delimiters on both sides[0]) for recursive structures. But why would you do that? If you wanted to save bytes by avoiding the delimiters on the very outer structures, there's a lot more of them to be saved if you apply the same "optimization" to any inner recursive structures. If you don't know what I'm talking about, think about how a tree-like recursive datastructure is represented in the memory of a C program. Yes pointers. Alternatively you could length-prefix them like before, C programs don't do that because you need to scan through everything and it's less efficient. Regardless, both approaches are context-sensitive and good luck on distinguishing malformed data from correct ones.
Now, this whole "formal languages and automatons" is a very complex subject matter[1], so while it may seem that the whole argument hinges on dropping a packet and desyncing the parser[2], I got the feeling from that talk that there are other (similarly fundamental) problems, but this particular one I understood and can make a compelling argument for :)
[0] afaik you might actually get away with a delimiter on just one side, but that makes it harder to parse because you need strict precedence rules to resolve ambiguities (e.g. 2+34+182+1+1+74321+0)
[1] it was considered one of the hardest courses during my CS college years (the other one being on "formal proofs of program correctness"), for various reasons I retook this course 4 times (underestimating its difficulty at first being one of those reasons), but when I finally did pass, I did so with a score of 9 out of 10, I'm kinda proud of that :P But the real* benefit of studying 4 times for the same difficult course is that you never really forget it (some parallels there with that post about "spaced repetition learning" last week).
[2] another thing they recommended that makes a lot of sense, but again is a parsing complexity (security) vs bandwidth efficiency trade-off: to make the delimiters (say, parentheses) to be out-of-band characters. so they're not allowed in binary blobs. this saves you from all sorts of escaping exploits (think XSS), makes resyncing more efficient and parsing a lot easier. of course it's really hard to step out of the "we really need all 8 bits in a byte"-paradigm, or how else can you design data formats with out-of-band characters? I don't know, and the talk I watched didn't give a solution either, just that it would be a good idea (to which I agree).
A more robust encoding reserves some bit-pattern as a <start-of-message> marker, and escapes regular appearance of this marker in the payload with some special sequence. (see, for example, http://en.wikipedia.org/wiki/High-Level_Data_Link_Control ).
When you start putting (for example) single "blink"-messages in distinct payloads in such a framing container, then the <length-of-message> byte of blink becomes redundant, of course.
"Why?" is the big question which sits there unanswered.
EDIT: Damn, I forgot to mention MessagePack. ;-)
- Suitability for FPGA implementation
Rolf
* XML and JSON can be slow.
* XML parser are big
* XML file size is big
* JSON lacks proper binary support
* Thrift defines a entire transport stack, so if you already have you already have a transport layer, you are adding more bloat
* Some people may find protocol buffers and thrift files too hard/tedious
* Why not? Sometimes it's easier/more fun to roll out your solution
(i.e. the Web is not the Internet)
That's an interesting requirement you don't see very often.
The protocol comes from Pantor Engineering, which apparently provides an "advanced trading system" out of Stockholm. Neat.
http://blog.blinkprotocol.org/2013/01/blink-compared-to-goog...
As you can see in a comment by Rolf, part of the perf limitation of GPB is the implementation and not the wire protocol.
Anders
From the docs:
"You should be very careful about marking fields as required. If at some point you wish to stop writing or sending a required field, it will be problematic to change the field to an optional field – old readers will consider messages without this field to be incomplete and may reject or drop them unintentionally. You should consider writing application-specific custom validation routines for your buffers instead. Some engineers at Google have come to the conclusion that using required does more harm than good; they prefer to use only optional and repeated. However, this view is not universal."
How is it TCP without the headers? And how can you put a layer on top of TCP and call that saving space? Shouldn't you just be using TCP? It's late I must be missing something ...
When both client and server know the definitions (written in the meta-language), they can determine which kind of message the other side is using because of the metadata sent with the message (their "message type system") without the need for any extra information, like a HTTP content-type header.
It looks like blink has far fewer special cases so the need for an official test suite might not be as great. Might be something worth considering anyway.
"We did not know how to make use of ASN.1 without making Blink a lot more complex."
This is the same reason Protocol Buffers exist: it was more fun to write something new than to understand how to use a better but more complex technology.
It's not about understanding the more complex technology. At least in the case of protocol buffers, they understood ASN.1. Implementing all that complexity comes with a price. If nothing else, it takes time away from other priorities.
If you look at protocol buffers, there are still ways to make the code faster, cleaner, etc., even without adding new features.
Having worked with a variety of ASN.1 libraries in a variety of ways, I can tell you that in almost every case, I found either performance bugs, functional bugs, or just missing features that literally got in my way.
And it applies to anything?