TechHui

Hawaiʻi's Technology Community

A few weeks ago, Stripe hosted their 3rd Capture the Flag competition.  Their first two CTFs were focused on security where you had to exploit a vulnerability in a small system or application to move on to each level until the final level is completed.  

For their 3rd CTF, they've decided to switch gears and focus on distributed systems.  Each of the 5 CTF levels focused on a different problem in the field and solutions were submitted via git to Stripe's grading system.  Over 7500 people participated and only 216 made it through.  The prize was bragging rights and a t-shirt, but the experience itself made it worthwhile.

Rather than going in detail how I solved each level, you can read one of the many walkthroughs out there.  However are the gists of each level:

Level 0 - Optimization Warmup (Ruby)

Not really a distributed system problem.  I think this level was meant as a confidence builder.  Essentially, the solution was to switch from a linear dictionary lookup to a constant lookup.  People went as far as reimplementing it in C, but time is money.

Level 1 - Gitcoin (Bash and Git)

This level delved into the area of cryptocurrency.  Cryptocurrencies, like bitcoin, are mined using hash algorithms to generate blockchains that are verified over a distributed system.  To successfully mine a gitcoin, one has to generate a commit with a git SHA1 hash that has a predetermined number of leading zeros and git commit successfully.  The git's repository history acts as a blockchain and a commit fails if someone beats you to the punch.  The goal is to mine quicker than a swarm of bots looking to out-mine you.  My solution was a looped version of the git hash function in C++ such that I didn't have to shell out to the git call each time I wanted to generate a hash.  This sped it up by multiple orders of magnitude.  Other people went as far as writing GPU miners.  That would have been interesting, but who has that kind of time :).  This level definitely gave me a deeper understanding of how cryptocurrencies work. 

Level 2 - DDoS Defense (Node.js)

In my opinion, this was easier than Level 1.  The goal was to modify a proxy written in node.js such that spam traffic is filtered so that the backend servers would not get bogged down.  However, points were taken away if the backend servers were too idle, preventing you from filtering all traffic.  My solution was a piece of filtering code to drop packets with source addresses that were seen too often, but would periodically let spam traffic seep through.

Level 3 - Instant Code Search (Scala)

The goal here was to improve upon a distributed search written in Scala.  My solution involved inverted indices,  sharding documents across different Scala instances and combining the result... i.e. map reduce.  This was my least favorite level as I was struggling more with Scala and spending the vast majority of time waiting for the code to compile and waiting for the instances to spin up.  I guess that's a problem developing with most JVM languages.

Level 4 Finale - SQL Cluster (Go)

Having to code in Go for the final level had me motivated to complete this competition.  This level tackled a truly difficult problem in distributed systems; high availability and failover.  Given a multi-node SQL database written in Go, we had to improve upon naive failover implementation.  The hint was to implement a consensus algorithm that involves an election algorithm and ensuring data integrity(handling duplicates, out of sequence data, etc..).  I  managed to write a simple consensus algorithm based off the raft algorithm that worked pretty well.

Post-mortem

Stripe wrote a blog on how they created and implemented the architecture to create the grading system.  For those of you interested in the distributed system field, take a look at that blog.  Their design is quite elegant and it's an awesome blueprint to have in your toolbox.

Why did I participate?

Trying out new languages and tackling problems you normally wouldn't face in your everyday job will not only help refine your skills, but help you stave off complacency.  Participating in coding competitions is one way of doing so, but also working on side projects or open source projects helps too.  I particularly like Stripe's competitions because they are close to real world problems.  I'm looking forward to getting the prized t-shirt in the mail, as well as their next competition.

 

 

Views: 310

Comment

You need to be a member of TechHui to add comments!

Join TechHui

Comment by Daniel Nishimura on March 7, 2014 at 5:33pm

@Joseph - I wish.  That guy is insane.

Comment by Joseph Lui on March 7, 2014 at 4:51pm

Way cool. Are you Nefarious Zhen?

Sponsors

web design, web development, localization

© 2024   Created by Daniel Leuck.   Powered by

Badges  |  Report an Issue  |  Terms of Service