Wednesday, December 3, 2008

Principles of FAST Encoding

I've been working with the FAST protocol recently, and have been very impressed with its performance. FAST is a compression standard used largely in the market data industry, but has obvious applications in distributed computing due to its high compression, low latency algorithm.

How is FAST so effective at compression? Its not rocket science. FAST uses four core principles that many of us have thought of before:

Implicit Tagging
Tagging the beginning and end of each field, as is done in FIX and XML, is obviously wasteful. Instead FAST encoders and decoders agree upon the field order ahead of time, so that these delimiters are unnecessary.

Encode Variable-Length Data
It is common to pass around PODS, or Plain Old Data Structures between messaging partners. It is even thought to be efficient. But why send all 8 bytes for a 64-bit integer with a value of 0? Zero is a value which can be expressed in a single byte. Extreme cases like this are more common than you would think, and very wasteful. Instead FAST uses stop-bit encoding, in which the most significant bit of each byte is a stop bit. When a 1 is encountered in the stop bit, the end of the field has been reached. Decoders calculate values by a combination of masking and shifting. Zero is always a single byte.

Don't Encode Certain Instances
By various means, we can often deduce a field value, because it is unchanged from the previous sample, or a default value. Instead FAST encoders and decoders agree upon a deduction algorithm likely to be fruitful for each field ahead of time.

Encode only Part of a Value
When the size of the field is larger than the change between samples, it makes little sense to encode the whole. Instead FAST encoders can encode a delta value, while a decoder can apply that delta value to a previous value.

Using these 4 simple principles, FAST has come up with some impressive results.

Want to learn more, including strategies for improved FAST compression? Consider enrolling in my Introduction To FAST training course.

Implementing FAST on your own? Consider hiring OCI to help.

No comments: