10 ms·
This reminded me of a tight-packed binary format we used in the trading systems domain almost 20 years ago. Instead of including metadata/field names in each me
by hliyan 5y ago
This reminded me of a tight-packed binary format we used in the trading systems domain almost 20 years ago. Instead of including metadata/field names in each message, it had a central message dictionary that every client/server would first download a copy from. Messages had only type IDs, followed by binary packed data in the correct field order. Because of microsecond latency requirements, we even avoided the serialization/deserialization process by making the memory format of the message and the wire format one and the same. The message class contained the same buffer that you would send/store. The GetInt(fieldID) method of the class simply points to the right place in the buffer and does a cast to int. Application logs contained these messages, rather than plain text. There was a special reader to read logs. Messages were exchanged over raw TCP. They contained their own application layer sequence number so that streams could resume after disconnection.
In that world, lantencies were so low that the response to your order submission would land in your front-end before you've had time to lift your finger off the enter key. I now work with web based systems. On days like this, I miss the old ways.
- secondcoming 5y agoI assume you were using C++? I'm not sure what you describe is possible these days due to UB. At the very least just casting bytes received over the wire to a type is UB, so you technically need a memcpy() and hope that the compiler optimises it out.
- hliyan 5y agoYes, it was C++. I was unfamiliar with the acronym "UB" so did a Google search. Does it mean "Undefined Behavior"? If I remember correctly, primitive types other than strings are memcpy'd. GetStr basically returned a char* to the right place in the buffer.
- secondcoming 5y agoApologies, yes Undefined Behaviour
- gpderetta 5y agoIt is not UB if it is correctly aligned. It is UB if the underlying dynamic type is not compatible from the access type As the bytes are coming from the kernel, you get to decide the dynamic type.
- oandrew 5y agoInteresting. Confluent Avro + Schema registry + Kafka uses exactly the same approach - binary serialized Avro datums are prefixed with schema id which can be resolved via Schema registry
- angstrom 5y agoAnd to top it off you could fit the entire message into whatever the MTU of your network supported. Cap it at 1500 bytes and subtract the overhead for the frame headers and you get an extremely tight TCP/IP sequence stream that buffers through 16MB without needing to boil the ocean for a compound command sequence. Having been in industry only 2 decades it amuses me how many times this gets rediscovered.
- hliyan 5y agoThat just reminded me of the most mysterious scaling issue I ever faced. We had a message to disseminate market data for multiple markets (e.g. IBM: 100/100.12 @ NYSE, 101/102 @ NASDAQ etc.). The system performed admirably under load testing (think 50,000 messages per second). One day we onboarded a single new regional exchange and the whole market data load test collapsed. We searched high and low for days without success, until someone figured out that the new market addition had caused the market data message to exceed the Ethernet frame size for the first time. Problem was not at the application layer or the transport, it was data link layer fragmentation! Figuring that out felt like solving a murder mystery (I wasn't the one who figured it out though).
- jkhdigital 5y agoClassic example of a leaky abstraction, and the principle that implementation details inevitably become undocumented API behavior.
- kabdib 5y agoA lot of "transparent RPC" systems are like this. "It's just like a normal function call, it's sooo convenient" . . . until it isn't, because it involves the network hardware and configuration, routing environment, firewalls, equipment failure . . .
- andylynch 5y agoI’ve worked on systems like this too - the max packet size is very well documented. Then post trade it all gets turned into FIXML which somehow manages to be both more verbose and less readable.
- armchairhacker 5y agoI don't understand why serialization formats that separate structure and content aren't more popular. Imagine a system every message is a UID or DID (https://www.w3.org/TR/did-core/ https://www.w3.org/TR/did-core/) followed by raw binary data. The UID completely describes the shape of the rest of the message. You can also transmit messages to define new UIDs: these messages' UID is a shared global UID that everyone knows about. Once a client learns a UID, messages are about as compact as possible. And the data defining UIDs can be much more descriptive than e.g. property names in JSON. You can send documentation and other excess data when defining the UID, because you don't have to worry about size, because you're only sending the UID once. And UIDs can reference other UIDs to reduce duplication.
- mtrovo 5y agoI think the system OP is describing is a little bit more complex. You're not just describing message types, you also have message templates; a template declares a message type and a set of prefilled fields. You save data by just sending the subset of fields that are actually changing, which is a very good abstraction for market data. The template is hydrated on the protocol parsing layer so your code only has to deal with message types itself.
- dboreham 5y agoThis is protocol buffers + a global type registry. I worked on such a system.
- pcarolan 5y agoIs it public? Id love to learn more about it.
- jenny91 5y agoIf you read the protobuf source, you can see a bunch of places where you can hook in custom type-fetching code, e.g. in the google.protobuf.Any type. After studying it a bit, I'm certain this is how it's used inside Google (might also be mentioned elsewhere). All you'd really need to do is to compile all protos into a repository (you can spit out the binary descriptors from protoc), then fetch those and decode in the client. It'd actually be quite straightforward to set up,
- Aeolun 5y ago> In that world, lantencies were so low that the response to your order submission would land in your front-end before you've had time to lift your finger off the enter key. If the order submission process depends on the manual press on the enter key (+/- 50ms) is there any point to that though?
- sodality2 5y agoIt was probably used with high frequency trading so fully automated unless you happened to be testing it manually.
- hliyan 5y agoDespite all the algorithms we employed, the concept of a manual trade never went away. Also, when the front-end was taken out of the equation, the latencies were in the microsecond range. 50ms would be excruciatingly slow for an algorithm.
- danachow 5y agoOT but keyboard latency can and often is far below 50ms, more like 1ms. It seems to be a common misconception that denouncing mandates increased lag.
- Aeolun 5y agoI was thinking more of the time a human finger needs to push the button down.
- formerly_proven 5y agoThat's because a lot of input hardware uses moronic debouncing.
- dan-robertson 5y agoIs this a number that came from an actual benchmark or from some marketing material from a keyboard maker? I ask this because [1] finds latency (measured from touching the key to the usb packet arriving) of 15ms with the fastest keyboard and around 50ms with others, though apparently some manufacturers have since improved. Or are you talking about midi keyboards where I guess latency is more noticeable to users? [1] https://danluu.com/keyboard-latency/ https://danluu.com/keyboard-latency/
- FpUser 5y agoI had exactly the same implementation except that type / version belonged to the whole message and would map to appropriate binary buffer in memory. No real de/serialization was needed. I still use it in my UDP game servers, with added packet id if message exceeds max datagram length and has to be split
- ericbarrett 5y agoThe one concern I'd have with this format is a length field getting corrupted in transit and causing an out-of-bounds memory access. The network protocols' checksums won't save you 100% of the time, especially if there's bad hardware in the loop. If every field is fixed length this is less of a concern, of course; you might get bad data but you won't get e.g. a string with length 64M.
- hliyan 5y agoIn our system, if the message didn't unpack properly, the application would send a retransmit request with that message's sequence number. But in practice, this scenario never occurred because TCP already did this for us.
- FpUser 5y agoI do not remember it ever happening but being semi-paranoid I had length in 2 places - beginning and the end of the message.
- mendigou 5y agoThis is exactly how it's done for spacecraft telemetry and telecommand too, but in this case it's to save bytes rather than processing time. I also miss working on those systems.
- porker 5y agoFab story, thank you! I understood up to "Messages were exchanged over raw TCP. They contained their own application layer sequence number so that streams could resume after disconnection." Can you go into more details about how the sequence number and resuming after disconnection worked?
- hliyan 5y agoPretty basic. The receiving process usually has an input thread that just puts the messages into a queue. Then a processing thread processes (maybe logic, maybe disk writes, maybe send) the messages and queues up periodic batch acks to the sender. The sender uses these acks to clear its own queue. The receiver persists the last acked sequence number, so that in case of a restart, it can tell upstream senders to restart sending messages from that point.
- mianos 5y agoThe number of times people have "invented" ASN.1 now is ridiculous.
- mtrovo 5y agoServer used a global sequence number for all messages they transmit. Clients are stateful so they know exactly what was the latest message they processed and would send that id when creating a new connection. This was very important as a lot of the message types used delta values, one of the most important ones being the order book. So in order to apply a new message you had to make sure that you're internal state was at the correct sequence id, failing to do so would make your state go bonkers, specially when you're talking about hundreds of messages being received per second. It's scary but you had a special message type that would send you a snapshot of the expected state with a sequence id that they correspond to. So your error handling code would fetch one of these and them ask for all the messages newer than that.
- hliyan 5y agoThis is exactly right. It was almost always deltas in favor of snapshots. One of the downsides was that sometimes, debugging an issue required replaying the entire market up to the point of the crash/bug.
- ktzar 5y agoIs it FIX messages? https://en.wikipedia.org/wiki/Financial_Information_eXchange https://en.wikipedia.org/wiki/Financial_Information_eXchange It's a good idea, extensible (ranges available for banks to implement their own codes), and fast.
- nly 5y agoOld school texty FIX is incredibly slow. FAST FIX is faster but not fun to use. Largely SBE has won adoption on the market data side, with huge platforms like Euronext (biggest on Europe) using it.
- hliyan 5y agoIt was a proprietary messaging middleware library. We actually found even FAST FIX slow.
- o_bender 5y agoFAST FIX protocol is terrible performance-wise, its format requires multiple branching at every field parsing. Even "high-performance" libraries like mFAST are slow: I recently helped a client to optimize parsing for several messages and got 8x speed improvement over mFAST (which is a big deal in HFT space).
- amitport 5y agoWell that's just like using C structs. The best serialization protocol :).
- nly 5y agoSome finance software systems do that too. It tends to be a nightmare because people end up adding new message types just to add a single field
- sattoshi 5y agoApache Thrift works on the same principle of separating structure from data.
- nly 5y agoWhat you're describing is exactly what still takes place in trading platforms, although a few i've seen now use SBE for consistency sake (it's very common on the market data side)
- mtrovo 5y agoDon't know if you're describing the original FIX itself with the TCP connection. On FAST FIX they got rid of the TCP connection and market data was sent over UDP using several parallel connections, data was reordered on the client side at consumption time and it only used a TCP connection to recover data when a sequence gap was found.
- hliyan 5y agoActually, even FAST was too slow for us. This was a proprietary messaging middleware library. And this particular market data feed was the direct one into the matching engine itself. For the rest of the system, we used a sort of reliable multicast using UDP for the first transmission and TCP for missed messages. We initially tried out a Gossip/Epidemic protocol but that didn't work out too well.
- erenon 5y agoWe do something very similar in binlog: https://github.com/morganstanley/binlog https://github.com/morganstanley/binlog Serialization is platform-dependent (to make it a simple memcpy most of the time), and the schema is sent up front (but can be updated later, with in-bound messages at will). See the User Guide (http://binlog.org/UserGuide.html http://binlog.org/UserGuide.html) and the Internals (http://binlog.org/Internals.html http://binlog.org/Internals.html) for more.
- lordnacho 5y agoSame here, I wrote an exchange core that did this using SBE. Basically you don't serialize in the classical sense, because you're simply taking whatever bytes are at your pointer and using them as some natural type. The internals of the exchange also simply used the same layout, so there was minimal copying and interpreting. On the way out it was the same, all you had to do was mask a few fields that you didn't want everyone to see and ship it onto the network. Even an unoptimized version of this managed to get throughput in the 300K/s range. Somehow it's the endpoint of my journey into serialization. Basically, avoid it if you need to be super fast. For most things though, it's useful to have something that you can read by eye, so if you're not in that HFT bracket it might be nicer to just use JSON or whatever.
- makotobestgirl 5y agoSounds like Google's flatbuffers [0], which indexes directly into a byte buffer using the field size prefix. [0] https://google.github.io/flatbuffers/ https://google.github.io/flatbuffers/
- mrlemke 5y agoVery neat and similar to a project I am starting for packet radio. I went further with the dictionary concept so that it contains common data. This way, your message contains only a few dictionary "pointers" (integers in base 64). This makes it easier to fit messages in ASCII for 300 baud links.
- atlgator 5y agoWe did the same in high fidelity flight simulators for a lot less money I'm sure.