mirror-github-bspeice/speice.io
1
0
Fork 0
mirror of https://github.com/bspeice/speice.io synced 2024-11-14 22:18:10 -05:00
Code Issues Releases Wiki Activity
gh-pages
speice.io/2019/09/binary-format-shootout/index.html

151 lines
51 KiB
HTML
Raw Permalink Normal View History

Deploy website - based on 6dcbc1a72c807487794da173fa5948acd8b76f35
2024-11-10 16:43:02 -05:00
<!doctype html><html lang=en dir=ltr class="blog-wrapper blog-post-page plugin-blog plugin-id-default" data-has-hydrated=false><meta charset=UTF-8><meta name=generator content="Docusaurus v3.6.0"><title data-rh=true>Binary format shootout | The Old Speice Guy</title><meta data-rh=true name=viewport content="width=device-width,initial-scale=1.0"><meta data-rh=true name=twitter:card content=summary_large_image><meta data-rh=true property=og:url content=https://speice.io/2019/09/binary-format-shootout><meta data-rh=true property=og:locale content=en><meta data-rh=true name=docusaurus_locale content=en><meta data-rh=true name=docusaurus_tag content=default><meta data-rh=true name=docsearch:language content=en><meta data-rh=true name=docsearch:docusaurus_tag content=default><meta data-rh=true property=og:title content="Binary format shootout | The Old Speice Guy"><meta data-rh=true name=description content="I've found that in many personal projects,"><meta data-rh=true property=og:description content="I've found that in many personal projects,"><meta data-rh=true property=og:type content=article><meta data-rh=true property=article:published_time content=2019-09-28T12:00:00.000Z><link data-rh=true rel=icon href=/img/favicon.ico><link data-rh=true rel=canonical href=https://speice.io/2019/09/binary-format-shootout><link data-rh=true rel=alternate href=https://speice.io/2019/09/binary-format-shootout hreflang=en><link data-rh=true rel=alternate href=https://speice.io/2019/09/binary-format-shootout hreflang=x-default><script data-rh=true type=application/ld+json>{"@context":"https://schema.org","@id":"https://speice.io/2019/09/binary-format-shootout","@type":"BlogPosting","author":{"@type":"Person","name":"Bradlee Speice"},"dateModified":"2024-11-10T03:06:23.000Z","datePublished":"2019-09-28T12:00:00.000Z","description":"I've found that in many personal projects,","headline":"Binary format shootout","isPartOf":{"@id":"https://speice.io/","@type":"Blog","name":"Blog"},"keywords":[],"mainEntityOfPage":"https://speice.io/2019/09/binary-format-shootout","name":"Binary format shootout","url":"https://speice.io/2019/09/binary-format-shootout"}</script><link rel=alternate type=application/rss+xml href=/rss.xml title="The Old Speice Guy RSS Feed"><link rel=alternate type=application/atom+xml href=/atom.xml title="The Old Speice Guy Atom Feed"><link rel=stylesheet href=https://cdn.jsdelivr.net/npm/katex@0.13.24/dist/katex.min.css integrity=sha384-odtC+0UGzzFL/6PNoE8rX/SPcQDXBJ+uRepguP4QkPCm2LBxH3FA3y+fKSiJ+AmM crossorigin><link rel=stylesheet href=/assets/css/styles.ae6ff4a3.css><script src=/assets/js/runtime~main.751b419d.js defer></script><script src=/assets/js/main.62ce6156.js defer></script><body class=navigation-with-keyboard><script>!function(){var t,e=function(){try{return new URLSearchParams(window.location.search).get("docusaurus-theme")}catch(t){}}()||function(){try{return window.localStorage.getItem("theme")}catch(t){}}();t=null!==e?e:"light",document.documentElement.setAttribute("data-theme",t)}(),function(){try{for(var[t,e]of new URLSearchParams(window.location.search).entries())if(t.startsWith("docusaurus-data-")){var a=t.replace("docusaurus-data-","data-");document.documentElement.setAttribute(a,e)}}catch(t){}}()</script><div id=__docusaurus><div role=region aria-label="Skip to main content"><a class=skipToContent_fXgn href=#__docusaurus_skipToContent_fallback>Skip to main content</a></div><nav aria-label=Main class="navbar navbar--fixed-top"><div class=navbar__inner><div class=navbar__items><button aria-label="Toggle navigation bar" aria-expanded=false class="navbar__toggle clean-btn" type=button><svg width=30 height=30 viewBox="0 0 30 30" aria-hidden=true><path stroke=currentColor stroke-linecap=round stroke-miterlimit=10 stroke-width=2 d="M4 7h22M4 15h22M4 23h22"/></svg></button><a class=navbar__brand href=/><div class=navbar__logo><img src=/img/logo.svg alt="Sierpinski Gasket" class="themedComponent_mlkZ themedComponent--light_NVdE"><img src=/img/logo-dark.svg alt="Sierpinski Gasket" class="themedComponent_mlkZ themedC
<a href=https://en.wikipedia.org/wiki/Analysis_paralysis target=_blank rel="noopener noreferrer">analysis paralysis</a> is particularly deadly.
Making good decisions in the beginning avoids pain and suffering later; if extra research prevents
future problems, I'm happy to continue <del>procrastinating</del> researching indefinitely.</p>
<p>So let's say you're in need of a binary serialization format. Data will be going over the network,
not just in memory, so having a schema document and code generation is a must. Performance is
crucial, so formats that support zero-copy de/serialization are given priority. And the more
languages supported, the better; I use Rust, but can't predict what other languages this could
interact with.</p>
<p>Given these requirements, the candidates I could find were:</p>
<ol>
<li><a href=https://capnproto.org/ target=_blank rel="noopener noreferrer">Cap'n Proto</a> has been around the longest, and is the most established</li>
<li><a href=https://google.github.io/flatbuffers/ target=_blank rel="noopener noreferrer">Flatbuffers</a> is the newest, and claims to have a simpler
encoding</li>
<li><a href=https://github.com/real-logic/simple-binary-encoding target=_blank rel="noopener noreferrer">Simple Binary Encoding</a> has the simplest
encoding, but the Rust implementation is unmaintained</li>
</ol>
<p>Any one of these will satisfy the project requirements: easy to transmit over a network, reasonably
fast, and polyglot support. But how do you actually pick one? It's impossible to know what issues
will follow that choice, so I tend to avoid commitment until the last possible moment.</p>
<p>Still, a choice must be made. Instead of worrying about which is "the best," I decided to build a
small proof-of-concept system in each format and pit them against each other. All code can be found
in the <a href=https://github.com/speice-io/marketdata-shootout target=_blank rel="noopener noreferrer">repository</a> for this post.</p>
<p>We'll discuss more in detail, but a quick preview of the results:</p>
<ul>
<li>Cap'n Proto: Theoretically performs incredibly well, the implementation had issues</li>
<li>Flatbuffers: Has some quirks, but largely lived up to its "zero-copy" promises</li>
<li>SBE: Best median and worst-case performance, but the message structure has a limited feature set</li>
</ul>
<h2 class="anchor anchorWithStickyNavbar_LWe7" id=prologue-binary-parsing-with-nom>Prologue: Binary Parsing with Nom<a href=#prologue-binary-parsing-with-nom class=hash-link aria-label="Direct link to Prologue: Binary Parsing with Nom" title="Direct link to Prologue: Binary Parsing with Nom">​</a></h2>
<p>Our benchmark system will be a simple data processor; given depth-of-book market data from
<a href=https://iextrading.com/trading/market-data/#deep target=_blank rel="noopener noreferrer">IEX</a>, serialize each message into the schema
format, read it back, and calculate total size of stock traded and the lowest/highest quoted prices.
This test isn't complex, but is representative of the project I need a binary format for.</p>
<p>But before we make it to that point, we have to actually read in the market data. To do so, I'm
using a library called <a href=https://github.com/Geal/nom target=_blank rel="noopener noreferrer"><code>nom</code></a>. Version 5.0 was recently released and
brought some big changes, so this was an opportunity to build a non-trivial program and get
familiar.</p>
<p>If you don't already know about <code>nom</code>, it's a "parser generator". By combining different smaller
parsers, you can assemble a parser to handle complex structures without writing tedious code by
hand. For example, when parsing
<a href=https://www.winpcap.org/ntar/draft/PCAP-DumpFileFormat.html#rfc.section.3.3 target=_blank rel="noopener noreferrer">PCAP files</a>:</p>
<div class="codeBlockContainer_Ckt0 theme-code-block" style="--prism-background-color:hsl(230, 1%, 98%);--prism-color:hsl(230, 8%, 24%)"><div class=codeBlockContent_biex><pre tabindex=0 class="prism-code language-text codeBlock_bY9V thin-scrollbar" style="background-color:hsl(230, 1%, 98%);color:hsl(230, 8%, 24%)"><code class=codeBlockLines_e6Vv><span class=token-line style="color:hsl(230, 8%, 24%)"><span class="token plain"> 0 1 2 3</span><br></span><span class=token-line style="color:hsl(230, 8%, 24%)"><span class="token plain"> 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1</span><br></span><span class=token-line style="color:hsl(230, 8%, 24%)"><span class="token plain"> +---------------------------------------------------------------+</span><br></span><span class=token-line style="color:hsl(230, 8%, 24%)"><span class="token plain"> 0 | Block Type = 0x00000006 |</span><br></span><span class=token-line style="color:hsl(230, 8%, 24%)"><span class="token plain"> +---------------------------------------------------------------+</span><br></span><span class=token-line style="color:hsl(230, 8%, 24%)"><span class="token plain"> 4 | Block Total Length |</span><br></span><span class=token-line style="color:hsl(230, 8%, 24%)"><span class="token plain"> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+</span><br></span><span class=token-line style="color:hsl(230, 8%, 24%)"><span class="token plain"> 8 | Interface ID |</span><br></span><span class=token-line style="color:hsl(230, 8%, 24%)"><span class="token plain"> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+</span><br></span><span class=token-line style="color:hsl(230, 8%, 24%)"><span class="token plain">12 | Timestamp (High) |</span><br></span><span class=token-line style="color:hsl(230, 8%, 24%)"><span class="token plain"> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+</span><br></span><span class=token-line style="color:hsl(230, 8%, 24%)"><span class="token plain">16 | Timestamp (Low) |</span><br></span><span class=token-line style="color:hsl(230, 8%, 24%)"><span class="token plain"> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+</span><br></span><span class=token-line style="color:hsl(230, 8%, 24%)"><span class="token plain">20 | Captured Len |</span><br></span><span class=token-line style="color:hsl(230, 8%, 24%)"><span class="token plain"> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+</span><br></span><span class=token-line style="color:hsl(230, 8%, 24%)"><span class="token plain">24 | Packet Len |</span><br></span><span class=token-line style="color:hsl(230, 8%, 24%)"><span class="token plain"> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+</span><br></span><span class=token-line style="color:hsl(230, 8%, 24%)"><span class="token plain"> | Packet Data |</span><br></span><span class=token-line style="color:hsl(230, 8%, 24%)"><span class="token plain"> | ... |</span><br></span></code></pre><div class=buttonGroup__atx><button type=button aria-label="Copy code to clipboard" title=Copy class=clean-btn><span class=copyButtonIcons_eSgA aria-hidden=true><svg viewBox="0 0 24 24" class=copyButtonIcon_y97N><path fill=currentColor d="M19,21H8V7H19M19,5H8A2,2 0 0,0 6,7V21A2,2 0 0,0 8,23H19A2,2 0 0,0 21,21V7A2,2 0 0,0 19,5M16,1H4A2,2 0 0,0 2,3V17H4V3H16V1Z"/></svg><svg viewBox="0 0 24 24" class=copyButtonSuccessIcon_LjdS><path fill=currentColor d=M21,7L9,19L3.5,13.5L4.91,12.09L9,16.17L19.59,5.59L21,7Z /></svg></span></button></div></div></div>
<p>...you can build a parser in <code>nom</code> that looks like
<a href=https://github.com/speice-io/marketdata-shootout/blob/369613843d39cfdc728e1003123bf87f79422497/src/parsers.rs#L59-L93 target=_blank rel="noopener noreferrer">this</a>:</p>
<div class="language-rust codeBlockContainer_Ckt0 theme-code-block" style="--prism-background-color:hsl(230, 1%, 98%);--prism-color:hsl(230, 8%, 24%)"><div class=codeBlockContent_biex><pre tabindex=0 class="prism-code language-rust codeBlock_bY9V thin-scrollbar" style="background-color:hsl(230, 1%, 98%);color:hsl(230, 8%, 24%)"><code class=codeBlockLines_e6Vv><span class=token-line style="color:hsl(230, 8%, 24%)"><span class="token keyword" style="color:hsl(301, 63%, 40%)">const</span><span class="token plain"> </span><span class="token constant" style="color:hsl(35, 99%, 36%)">ENHANCED_PACKET</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">:</span><span class="token plain"> </span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">[</span><span class="token keyword" style="color:hsl(301, 63%, 40%)">u8</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">;</span><span class="token plain"> </span><span class="token number" style="color:hsl(35, 99%, 36%)">4</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">]</span><span class="token plain"> </span><span class="token operator" style="color:hsl(221, 87%, 60%)">=</span><span class="token plain"> </span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">[</span><span class="token number" style="color:hsl(35, 99%, 36%)">0x06</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">,</span><span class="token plain"> </span><span class="token number" style="color:hsl(35, 99%, 36%)">0x00</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">,</span><span class="token plain"> </span><span class="token number" style="color:hsl(35, 99%, 36%)">0x00</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">,</span><span class="token plain"> </span><span class="token number" style="color:hsl(35, 99%, 36%)">0x00</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">]</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">;</span><span class="token plain"></span><br></span><span class=token-line style="color:hsl(230, 8%, 24%)"><span class="token plain"></span><span class="token keyword" style="color:hsl(301, 63%, 40%)">pub</span><span class="token plain"> </span><span class="token keyword" style="color:hsl(301, 63%, 40%)">fn</span><span class="token plain"> </span><span class="token function-definition function" style="color:hsl(221, 87%, 60%)">enhanced_packet_block</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">(</span><span class="token plain">input</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">:</span><span class="token plain"> </span><span class="token operator" style="color:hsl(221, 87%, 60%)">&</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">[</span><span class="token keyword" style="color:hsl(301, 63%, 40%)">u8</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">]</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">)</span><span class="token plain"> </span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">-></span><span class="token plain"> </span><span class="token class-name" style="color:hsl(35, 99%, 36%)">IResult</span><span class="token operator" style="color:hsl(221, 87%, 60%)">&lt;</span><span class="token operator" style="color:hsl(221, 87%, 60%)">&</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">[</span><span class="token keyword" style="color:hsl(301, 63%, 40%)">u8</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">]</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">,</span><span class="token plain"> </span><span class="token operator" style="color:hsl(221, 87%, 60%)">&</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">[</span><span class="token keyword" style="color:hsl(301, 63%, 40%)">u8</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">]</span><span class="token operator" style
<p>While this example isn't too interesting, more complex formats (like IEX market data) are where
<a href=https://github.com/speice-io/marketdata-shootout/blob/369613843d39cfdc728e1003123bf87f79422497/src/iex.rs target=_blank rel="noopener noreferrer"><code>nom</code> really shines</a>.</p>
<p>Ultimately, because the <code>nom</code> code in this shootout was the same for all formats, we're not too
interested in its performance. Still, it's worth mentioning that building the market data parser was
actually fun; I didn't have to write tons of boring code by hand.</p>
<h2 class="anchor anchorWithStickyNavbar_LWe7" id=capn-proto>Cap'n Proto<a href=#capn-proto class=hash-link aria-label="Direct link to Cap'n Proto" title="Direct link to Cap'n Proto">​</a></h2>
<p>Now it's time to get into the meaty part of the story. Cap'n Proto was the first format I tried
because of how long it has supported Rust (thanks to <a href=https://github.com/dwrensha target=_blank rel="noopener noreferrer">dwrensha</a> for
maintaining the Rust port since
<a href=https://github.com/capnproto/capnproto-rust/releases/tag/rustc-0.10 target=_blank rel="noopener noreferrer">2014!</a>). However, I had a ton
of performance concerns once I started using it.</p>
<p>To serialize new messages, Cap'n Proto uses a "builder" object. This builder allocates memory on the
heap to hold the message content, but because builders
<a href=https://github.com/capnproto/capnproto-rust/issues/111 target=_blank rel="noopener noreferrer">can't be re-used</a>, we have to allocate a
new buffer for every single message. I was able to work around this with a
<a href=https://github.com/speice-io/marketdata-shootout/blob/369613843d39cfdc728e1003123bf87f79422497/src/capnp_runner.rs#L17-L51 target=_blank rel="noopener noreferrer">special builder</a>
that could re-use the buffer, but it required reading through Cap'n Proto's
<a href=https://github.com/capnproto/capnproto-rust/blob/master/benchmark/benchmark.rs#L124-L156 target=_blank rel="noopener noreferrer">benchmarks</a>
to find an example, and used
<a href=https://doc.rust-lang.org/std/mem/fn.transmute.html target=_blank rel="noopener noreferrer"><code>std::mem::transmute</code></a> to bypass Rust's borrow
checker.</p>
<p>The process of reading messages was better, but still had issues. Cap'n Proto has two message
encodings: a <a href=https://capnproto.org/encoding.html#packing target=_blank rel="noopener noreferrer">"packed"</a> representation, and an
"unpacked" version. When reading "packed" messages, we need a buffer to unpack the message into
before we can use it; Cap'n Proto allocates a new buffer for each message we unpack, and I wasn't
able to figure out a way around that. In contrast, the unpacked message format should be where Cap'n
Proto shines; its main selling point is that there's <a href=https://capnproto.org/ target=_blank rel="noopener noreferrer">no decoding step</a>.
However, accomplishing zero-copy deserialization required code in the private API
(<a href=https://github.com/capnproto/capnproto-rust/issues/148 target=_blank rel="noopener noreferrer">since fixed</a>), and we allocate a vector on
every read for the segment table.</p>
<p>In the end, I put in significant work to make Cap'n Proto as fast as possible, but there were too
many issues for me to feel comfortable using it long-term.</p>
<h2 class="anchor anchorWithStickyNavbar_LWe7" id=flatbuffers>Flatbuffers<a href=#flatbuffers class=hash-link aria-label="Direct link to Flatbuffers" title="Direct link to Flatbuffers">​</a></h2>
<p>This is the new kid on the block. After a
<a href=https://github.com/google/flatbuffers/pull/3894 target=_blank rel="noopener noreferrer">first attempt</a> didn't pan out, official support
was <a href=https://github.com/google/flatbuffers/pull/4898 target=_blank rel="noopener noreferrer">recently launched</a>. Flatbuffers intends to
address the same problems as Cap'n Proto: high-performance, polyglot, binary messaging. The
difference is that Flatbuffers claims to have a simpler wire format and
<a href=https://google.github.io/flatbuffers/flatbuffers_benchmarks.html target=_blank rel="noopener noreferrer">more flexibility</a>.</p>
<p>On the whole, I enjoyed using Flatbuffers; the <a href=https://crates.io/crates/flatc-rust target=_blank rel="noopener noreferrer">tooling</a> is
nice, and unlike Cap'n Proto, parsing messages was actually zero-copy and zero-allocation. However,
there were still some issues.</p>
<p>First, Flatbuffers (at least in Rust) can't handle nested vectors. This is a problem for formats
like the following:</p>
<div class="codeBlockContainer_Ckt0 theme-code-block" style="--prism-background-color:hsl(230, 1%, 98%);--prism-color:hsl(230, 8%, 24%)"><div class=codeBlockContent_biex><pre tabindex=0 class="prism-code language-text codeBlock_bY9V thin-scrollbar" style="background-color:hsl(230, 1%, 98%);color:hsl(230, 8%, 24%)"><code class=codeBlockLines_e6Vv><span class=token-line style="color:hsl(230, 8%, 24%)"><span class="token plain">table Message {</span><br></span><span class=token-line style="color:hsl(230, 8%, 24%)"><span class="token plain"> symbol: string;</span><br></span><span class=token-line style="color:hsl(230, 8%, 24%)"><span class="token plain">}</span><br></span><span class=token-line style="color:hsl(230, 8%, 24%)"><span class="token plain">table MultiMessage {</span><br></span><span class=token-line style="color:hsl(230, 8%, 24%)"><span class="token plain"> messages:[Message];</span><br></span><span class=token-line style="color:hsl(230, 8%, 24%)"><span class="token plain">}</span><br></span></code></pre><div class=buttonGroup__atx><button type=button aria-label="Copy code to clipboard" title=Copy class=clean-btn><span class=copyButtonIcons_eSgA aria-hidden=true><svg viewBox="0 0 24 24" class=copyButtonIcon_y97N><path fill=currentColor d="M19,21H8V7H19M19,5H8A2,2 0 0,0 6,7V21A2,2 0 0,0 8,23H19A2,2 0 0,0 21,21V7A2,2 0 0,0 19,5M16,1H4A2,2 0 0,0 2,3V17H4V3H16V1Z"/></svg><svg viewBox="0 0 24 24" class=copyButtonSuccessIcon_LjdS><path fill=currentColor d=M21,7L9,19L3.5,13.5L4.91,12.09L9,16.17L19.59,5.59L21,7Z /></svg></span></button></div></div></div>
<p>We want to create a <code>MultiMessage</code> which contains a vector of <code>Message</code>, and each <code>Message</code> itself
contains a vector (the <code>string</code> type). I was able to work around this by
<a href=https://github.com/speice-io/marketdata-shootout/blob/e9d07d148bf36a211a6f86802b313c4918377d1b/src/flatbuffers_runner.rs#L83 target=_blank rel="noopener noreferrer">caching <code>Message</code> elements</a>
in a <code>SmallVec</code> before building the final <code>MultiMessage</code>, but it was a painful process that I
believe contributed to poor serialization performance.</p>
<p>Second, streaming support in Flatbuffers seems to be something of an
<a href=https://github.com/google/flatbuffers/issues/3898 target=_blank rel="noopener noreferrer">afterthought</a>. Where Cap'n Proto in Rust handles
reading messages from a stream as part of the API, Flatbuffers just sticks a <code>u32</code> at the front of
each message to indicate the size. Not specifically a problem, but calculating message size without
that tag is nigh on impossible.</p>
<p>Ultimately, I enjoyed using Flatbuffers, and had to do significantly less work to make it perform
well.</p>
<h2 class="anchor anchorWithStickyNavbar_LWe7" id=simple-binary-encoding>Simple Binary Encoding<a href=#simple-binary-encoding class=hash-link aria-label="Direct link to Simple Binary Encoding" title="Direct link to Simple Binary Encoding">​</a></h2>
<p>Support for SBE was added by the author of one of my favorite
<a href=https://web.archive.org/web/20190427124806/https://polysync.io/blog/session-types-for-hearty-codecs/ target=_blank rel="noopener noreferrer">Rust blog posts</a>.
I've <a href=/2019/06/high-performance-systems>talked previously</a> about how important
variance is in high-performance systems, so it was encouraging to read about a format that
<a href=https://github.com/real-logic/simple-binary-encoding/wiki/Why-Low-Latency target=_blank rel="noopener noreferrer">directly addressed</a> my
concerns. SBE has by far the simplest binary format, but it does make some tradeoffs.</p>
<p>Both Cap'n Proto and Flatbuffers use <a href=https://capnproto.org/encoding.html#structs target=_blank rel="noopener noreferrer">message offsets</a>
to handle variable-length data, <a href=https://capnproto.org/language.html#unions target=_blank rel="noopener noreferrer">unions</a>, and various
other features. In contrast, messages in SBE are essentially
<a href=https://github.com/real-logic/simple-binary-encoding/blob/master/sbe-samples/src/main/resources/example-schema.xml target=_blank rel="noopener noreferrer">just structs</a>;
variable-length data is supported, but there's no union type.</p>
<p>As mentioned in the beginning, the Rust port of SBE works well, but is
<a href=https://users.rust-lang.org/t/zero-cost-abstraction-frontier-no-copy-low-allocation-ordered-decoding/11515/9 target=_blank rel="noopener noreferrer">essentially unmaintained</a>.
However, if you don't need union types, and can accept that schemas are XML documents, it's still
worth using. SBE's implementation had the best streaming support of all formats I tested, and
doesn't trigger allocation during de/serialization.</p>
<h2 class="anchor anchorWithStickyNavbar_LWe7" id=results>Results<a href=#results class=hash-link aria-label="Direct link to Results" title="Direct link to Results">​</a></h2>
<p>After building a test harness
<a href=https://github.com/speice-io/marketdata-shootout/blob/master/src/capnp_runner.rs target=_blank rel="noopener noreferrer">for</a>
<a href=https://github.com/speice-io/marketdata-shootout/blob/master/src/flatbuffers_runner.rs target=_blank rel="noopener noreferrer">each</a>
<a href=https://github.com/speice-io/marketdata-shootout/blob/master/src/sbe_runner.rs target=_blank rel="noopener noreferrer">format</a>, it was
time to actually take them for a spin. I used
<a href=https://github.com/speice-io/marketdata-shootout/blob/master/run_shootout.sh target=_blank rel="noopener noreferrer">this script</a> to run
the benchmarks, and the raw results are
<a href=https://github.com/speice-io/marketdata-shootout/blob/master/shootout.csv target=_blank rel="noopener noreferrer">here</a>. All data reported
below is the average of 10 runs on a single day of IEX data. Results were validated to make sure
that each format parsed the data correctly.</p>
<h3 class="anchor anchorWithStickyNavbar_LWe7" id=serialization>Serialization<a href=#serialization class=hash-link aria-label="Direct link to Serialization" title="Direct link to Serialization">​</a></h3>
<p>This test measures, on a
<a href=https://github.com/speice-io/marketdata-shootout/blob/master/src/main.rs#L268-L272 target=_blank rel="noopener noreferrer">per-message basis</a>,
how long it takes to serialize the IEX message into the desired format and write to a pre-allocated
buffer.</p>
<table><thead><tr><th style=text-align:left>Schema<th style=text-align:left>Median<th style=text-align:left>99th Pctl<th style=text-align:left>99.9th Pctl<th style=text-align:left>Total<tbody><tr><td style=text-align:left>Cap'n Proto Packed<td style=text-align:left>413ns<td style=text-align:left>1751ns<td style=text-align:left>2943ns<td style=text-align:left>14.80s<tr><td style=text-align:left>Cap'n Proto Unpacked<td style=text-align:left>273ns<td style=text-align:left>1828ns<td style=text-align:left>2836ns<td style=text-align:left>10.65s<tr><td style=text-align:left>Flatbuffers<td style=text-align:left>355ns<td style=text-align:left>2185ns<td style=text-align:left>3497ns<td style=text-align:left>14.31s<tr><td style=text-align:left>SBE<td style=text-align:left>91ns<td style=text-align:left>1535ns<td style=text-align:left>2423ns<td style=text-align:left>3.91s</table>
<h3 class="anchor anchorWithStickyNavbar_LWe7" id=deserialization>Deserialization<a href=#deserialization class=hash-link aria-label="Direct link to Deserialization" title="Direct link to Deserialization">​</a></h3>
<p>This test measures, on a
<a href=https://github.com/speice-io/marketdata-shootout/blob/master/src/main.rs#L294-L298 target=_blank rel="noopener noreferrer">per-message basis</a>,
how long it takes to read the previously-serialized message and perform some basic aggregation. The
aggregation code is the same for each format, so any performance differences are due solely to the
format implementation.</p>
<table><thead><tr><th style=text-align:left>Schema<th style=text-align:left>Median<th style=text-align:left>99th Pctl<th style=text-align:left>99.9th Pctl<th style=text-align:left>Total<tbody><tr><td style=text-align:left>Cap'n Proto Packed<td style=text-align:left>539ns<td style=text-align:left>1216ns<td style=text-align:left>2599ns<td style=text-align:left>18.92s<tr><td style=text-align:left>Cap'n Proto Unpacked<td style=text-align:left>366ns<td style=text-align:left>737ns<td style=text-align:left>1583ns<td style=text-align:left>12.32s<tr><td style=text-align:left>Flatbuffers<td style=text-align:left>173ns<td style=text-align:left>421ns<td style=text-align:left>1007ns<td style=text-align:left>6.00s<tr><td style=text-align:left>SBE<td style=text-align:left>116ns<td style=text-align:left>286ns<td style=text-align:left>659ns<td style=text-align:left>4.05s</table>
<h2 class="anchor anchorWithStickyNavbar_LWe7" id=conclusion>Conclusion<a href=#conclusion class=hash-link aria-label="Direct link to Conclusion" title="Direct link to Conclusion">​</a></h2>
<p>Building a benchmark turned out to be incredibly helpful in making a decision; because a "union"
type isn't important to me, I can be confident that SBE best addresses my needs.</p>
<p>While SBE was the fastest in terms of both median and worst-case performance, its worst case
performance was proportionately far higher than any other format. It seems to be that
de/serialization time scales with message size, but I'll need to do some more research to understand
what exactly is going on.</div></article><nav class="pagination-nav docusaurus-mt-lg" aria-label="Blog post page navigation"><a class="pagination-nav__link pagination-nav__link--prev" href=/2019/06/high-performance-systems><div class=pagination-nav__sublabel>Older post</div><div class=pagination-nav__label>On building high performance systems</div></a><a class="pagination-nav__link pagination-nav__link--next" href=/2019/12/release-the-gil><div class=pagination-nav__sublabel>Newer post</div><div class=pagination-nav__label>Release the GIL</div></a></nav></main><div class="col col--2"><div class="tableOfContents_bqdL thin-scrollbar"><ul class="table-of-contents table-of-contents__left-border"><li><a href=#prologue-binary-parsing-with-nom class="table-of-contents__link toc-highlight">Prologue: Binary Parsing with Nom</a><li><a href=#capn-proto class="table-of-contents__link toc-highlight">Cap'n Proto</a><li><a href=#flatbuffers class="table-of-contents__link toc-highlight">Flatbuffers</a><li><a href=#simple-binary-encoding class="table-of-contents__link toc-highlight">Simple Binary Encoding</a><li><a href=#results class="table-of-contents__link toc-highlight">Results</a><ul><li><a href=#serialization class="table-of-contents__link toc-highlight">Serialization</a><li><a href=#deserialization class="table-of-contents__link toc-highlight">Deserialization</a></ul><li><a href=#conclusion class="table-of-contents__link toc-highlight">Conclusion</a></ul></div></div></div></div></div><footer class=footer><div class="container container-fluid"><div class="footer__bottom text--center"><div class=footer__copyright>Copyright © 2024 Bradlee Speice</div></div></div></footer></div>
Reference in New Issue Copy Permalink