Theoretical Fun

The company I work for, like many other tech companies, has a thing where you get to spend a certain amount of your time working on projects of your own choosing. The most well known-example of this is Google’s now-defunct 80/20 rule but there are plenty of others.

This past week I had an opportunity to do some of this, and ended up brushing off my very theoretical computer science roots and digging into some graph theory in order to solve a very practical problem. Of all the things I get to do in software, this is far and away my favourite, and I had a blast working out the possible solutions.

In my career so far I’ve been lucky enough to have several opportunities to solve problems of this nature and then build out the solutions, and even publish some of them to talk about. It is extremely rewarding work. There are of course a few I can’t talk about as they are still internal, but here’s a sort of “hall of fame”: two other problems that I had a ton of fun solving at a computer-science-theoretical level and also resulted in really awesome (and sometimes popular!) practical solutions.

Wheel-of-Fortune Memory Allocator

https://github.com/eapache/wof_alloc

Arguably the overarching project here was Wireshark‘s wmem framework which I also designed and built, but while wmem was a lot of fun to work on it wasn’t particularly novel; it was just another memory pool library with a few minor tweaks to suit Wireshark’s use case and migration path. However, Wireshark’s unique memory allocation pattern demanded a custom allocator algorithm which I eventually extracted into this library.

As far as I can remember this was the first practical problem of this nature that I got to take the entire way: from identifying the problem, designing the solution, to building and shipping it, and I am forever grateful to the Wireshark core team for trusting a (at the time) university student to go and rewrite the deepest foundational layer of the project. At just under 1000 lines of pure C this allocator has been shipping in released versions of the project for 5 years now effectively unchanged, and the standalone version gets a fair number of hits on GitHub.

Sarama Async Producer

https://github.com/Shopify/sarama/wiki/Producer-implementation

A little while later, my first major project at my current job was to write a golang client for the Apache Kafka platform. Like wmem, a lot of it was pretty standard work (in this case implementing message formats and managing TCP connections). However, the design of the producer implementation was another one of these instances of theoretical fun. The requirements on a performant Kafka producer are complex and varied, balancing messages and batching across topics and partitions and brokers, while also maintaining message order in the face of partial failures and retries. I can’t tell you how many evenings I spent wandering around in a fog, stopping occasionally only to make tweaks to weird hypothetical flow diagrams on my whiteboard.

To a certain extent this project was less practical than the allocator; the reference java implementation was open-source and would have been fairly straight-forward to copy, but I did it myself for two main reasons:

  • I was working in Go, which provided me with very different concurrency primitives and indicated a very different design.
  • I was young, and not as aggressively pragmatic at the time.

To a certain extent it was also less successful; it has continued to evolve over the last four years and there are still parts of the design that I’m not entirely happy with. That said, it’s also far and away the most complex single algorithm I’ve ever built, and judging by Sarama’s popularity, it’s doing its job just fine in practice. I even managed to get a conference talk out of it.

GraphQL Warden

https://github.com/rmosolgo/graphql-ruby/issues/1333

If you recall my recent post on what I’ve been working on recently for my “real” job, it won’t surprise you that my most recent project is tangentially related to that. This one hasn’t been built yet (and my own pragmatism means it may never get built) but even from a design perspective I had a lot of fun with the process here. I definitely got way too excited when I realized that I could represent the two halves of the process as symmetric reachability problems in a graph-theoretical isomorphism of the schema.

And just maybe, the next time I get a chance to spend some “me time” at work, I’ll write an actual implementation of it!

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s