Ratas - A hierarchical timer wheel

Posted on 2016-07-27 in General

Last week I needed a timer wheel for a hobby project. That's a data structure that's been reimplemented over and over in the last three decades, but for various reasons I couldn't get excited by any of the freely available ones. Obviously this means that one more implementation was needed, hence Ratas - a hierarchical timer wheel. Unfortunately my vacation ran out before I could get back to the original project, but that's the nature of yak shaving.

In this post I'll first explain briefly what timer wheels are - you might want to read one of the references instead if you've got the time - and then go into more detail on why I wrote a new one.

... Continue reading ...

The many ways of handling TCP RST packets

Posted on 2016-02-01 in Networking

What could be a simpler networking concept than TCP's RST packet? It just crudely closes down a connection, nothing subtle about it. Due to some odd RST behavior we saw at work, I went digging in RFCs to check what's the technically correct behavior and in different TCP implementations to see what's actually done in practice.

... Continue reading ...

json-to-multicsv - Convert hierarchical JSON to multiple CSV files

Posted on 2016-01-12 in General, Perl

Introduction

json-to-multicsv is a little program to convert a JSON file to one or more CSV files in a way that preserves the hierarchical structure of nested objects and lists. It's the kind of dime a dozen data munging tool that's too trivial to talk about, but I'll write a bit anyway for a couple of reasons.

The first one is that I spent an hour looking for an existing tool that did this and didn't find one. Lots of converters to other formats, all of which seem to assume the JSON is effectively going to be a list of records, but none that supported arbitrary nesting. Did I just somehow manage to miss all the good ones? Or is this truly something that nobody has ever needed to do?

Second, this is as good an excuse as any to start talking a bit about some patterns in how command line programs get told what to do (I'd use the word "configured", except that's not quite right).

... Continue reading ...

A rating system for asymmetric multiplayer games

Posted on 2015-11-18 in Games

Introduction

A couple of years ago I wrote a quick and dirty rating system for a online boardgame site I run. It wasn't particularly well thought out, but it did the job. Some discussion about the system made me revisit it, with two years of hindsight and orders of magnitude more data.

How well does the system actually work, and how predictive are the ratings? There are some obvious tweaks to the system — would implementing them make things better or worse? Would anything be gained from switching to a more principled (but more complicated) approach. For this last bit, I used Microsoft's TrueSkill as the benchmark. It has some desirable properties and appears to be the gold standard of team based rating systems right now.

The code and the data are available on GitHub in my rating-eval repository.

... Continue reading ...

Flow disruptor - a deterministic per-flow network condition simulator

Posted on 2015-10-01 in Networking

Introduction

I finally got around to open sourcing flow disruptor, a tool I wrote at work late last year. What does it do? Glad you asked! Flow disruptor is a deterministic per-flow network condition simulator.

To unpack that description a bit, per-flow means that the network conditions are simulated separately for each TCP connection rather than on the link layer. Deterministic means that we normalize as many network conditions as possible (e.g. RTT, bandwidth), and any changes in those conditions happen at preconfigured times rather than randomly. For example the configuration could specify that the connection experiences a packet loss exactly 5s after it was initiated, and then a packet loss every 1s after that. Or that packet loss happens at a specifed level of bandwidth limit based queueing.

You can check the Github repo linked above for the code and for documentation on e.g. configuration. This blog post is more on why this tool exists and why it looks the way it does.

... Continue reading ...

The most obsolete infrastructure money could buy - my worst job ever

Posted on 2015-09-01 in General

Today marks the 10th anniversary of the most bizarre, and possibly the saddest, job I ever took.

The year was 2005. My interest in writing a content management system in Java for the company that bought our startup had been steadily draining away, while my real passion was working on compilers and other programming language infrastructure (mostly SBCL). One day I spotted a job advert looking for compiler people, which was a rare occurrence in that time and place. I breezed through the job interview, but did not ask the right questions and ignored a couple of warning signs. Oops.

It turned out to be a bit of an adventure in retrocomputing.

... Continue reading ...

Mobile TCP optimization - lessons learned in production

Posted on 2015-08-25 in Networking

I did a keynote presentation at the SIGCOMM'15 HotMiddlebox workshop, "Mobile TCP optimization - Lessons Learned in Production". The title was set before I had any idea of what I'd really be talking about, just that it'd be about some of the stuff we've been working on at Teclo. So apologies if the content isn't an exact match for the title.

This post contains my slides, interleaved with my speaker's notes for that slide. It won't be an exact transcription of what I actually ended up saying, they were just written to make sure that I had at least something coherent to say re: each slide. We've got an endless supply of network horror story anecdotes, and I can't actually remember which ones I ended up using in the talk :-/

I'm particularly happy that my points on transparency of optimization got a positive reception. To us it's a key part of making optimization be a good networking citizen, and has seemingly been getting short shrift so far. Hilariously the other TCP optimization talk at the workshop brought up a transparency issue we'd never had to consider, lack of MAC transparency causing a Wifi security gateway to think connections were being spoofed.

Thanks to Teclo for letting me talk about some of this stuff publicly, and to everyone who attended HotMiddlebox. It was a lot of fun, and I got a bunch of useful information from the hallway discussions.

... Continue reading ...

Use cases for CHANGE-CLASS in Common Lisp

Posted on 2015-07-27 in Lisp

This is a post on use cases for Common Lisp's CHANGE-CLASS operation [0]. As the name suggests, it changes the class of an object without changing its object identity. It's an operation that a certain class of programmers would consider totally abhorrent. I think it's both cool and useful.

As far as I an see, the class of an instance has three effects in Common Lisp. It determines the set of slots the object has, it determines which methods will be executed when a generic function is called with that object as one of the arguments, and it determines how the object interacts with the rest of the system based on the metaclass of the class of the object.

... Continue reading ...

Detecting cheaters in an asynchronous online game

Posted on 2015-07-22 in Games

Introduction

This post is a description of some tools and data analysis I did for detecting players using multiple user accounts in an asynchronous online game. The code is available at GitHub.

A couple of months ago one of the players on my Online Terra Mystica site had some concerns that some of the players in the tournament were playing with multiple accounts. So I decided to do a bit of digging into the logs to see whether it was really happening or just paranoia.

... Continue reading ...

Unit testing a TCP stack

Posted on 2015-07-09 in Networking

Last year in an online discussion someone used in-kernel TCP stacks as a canonical example of code that you can't apply modern testing practices to. Now, that might be true but if so the operative phrase there is "in-kernel", not "TCP stack". When the TCP implementation is just a normal user-space application, there's no particular reason it can't be written in a way that's testable and amenable to a test driven development approach.

... Continue reading ...