Hoopla! - Jack Danger Canty

What does `bundle exec` do?

2015-07-14T00:00:00-07:00

A colleague asked me why sometimes we’ll run a command that’s provided by a Ruby gem (e.g. “rspec”) and it fails unless we type bundle exec before it.

What Bundler gives us

Bundler is a Ruby gem that’s a little special because it manages other Ruby gems. It does basically three things:

It does a topological sort of the gems listed in your Gemfile to print a complete graph of your project’s dependencies into Gemfile.lock
It retrieves the gems your project needs from the source(s) you’ve defined
And it makes it so when you require files the right file is loaded.

The importance of ENV in Ruby

The two most popular Ruby version managers are RVM and rbenv (though I strongly recommend chruby). They work in totally different ways (RVM overwrites your cd shell builtin function!) but the output of all these tools is the same: They export environment variables so your Ruby code operates on a particular version of Ruby with a particular set of gems.

Here’s a diff[1] of the environment when we’re using one version of Ruby versus another:

$ diff <(rvm use 2.2 && env) <(rvm use 2.1 && env)
1c1
< Using /Users/jackdanger/.rvm/gems/ruby-2.2.1
---
> Using /Users/jackdanger/.rvm/gems/ruby-2.1.5
13,14c13,14
< GEM_HOME=/Users/jackdanger/.rvm/gems/ruby-2.2.1
< GEM_PATH=/Users/jackdanger/.rvm/gems/ruby-2.2.1:/Users/jackdanger/.rvm/gems/ruby-2.2.1@global
---
> GEM_HOME=/Users/jackdanger/.rvm/gems/ruby-2.1.5
> GEM_PATH=/Users/jackdanger/.rvm/gems/ruby-2.1.5:/Users/jackdanger/.rvm/gems/ruby-2.1.5@global
19c19
< IRBRC=/Users/jackdanger/.rvm/rubies/ruby-2.2.1/.irbrc
---
> IRBRC=/Users/jackdanger/.rvm/rubies/ruby-2.1.5/.irbrc
37c37
< MY_RUBY_HOME=/Users/jackdanger/.rvm/rubies/ruby-2.2.1
---
> MY_RUBY_HOME=/Users/jackdanger/.rvm/rubies/ruby-2.1.5
42c42
< PATH=/Users/jackdanger/.rvm/gems/ruby-2.2.1/bin:...
---
> PATH=/Users/jackdanger/.rvm/gems/ruby-2.1.5/bin:...
51c51
< RUBY_VERSION=ruby-2.2.1
---
> RUBY_VERSION=ruby-2.1.5
103c103
< rvm_ruby_string=ruby-2.2.1
---
> rvm_ruby_string=ruby-2.1.5

Looking at just the keys, you can see that RVM sets a little bit of internal stuff but mostly it just sets the PATH for running commands like ruby and rspec and it sets GEM_HOME and GEM_PATH and such:

$ diff <(rvm use 2.2 >/dev/null && env) <(rvm use 2.1 >/dev/null && env) | \
awk -F= '{print $1}' | awk '{print $2}' | sort | uniq

GEM_HOME
GEM_PATH
IRBRC
MY_RUBY_HOME
PATH
RUBY_VERSION
rvm_ruby_string

Ruby core source has no unified way of resolving dependencies from these environmental variables. Rubygems is a project outside of Ruby core that is periodically imported in to the main Ruby trunk as a vendored dependency. It reads GEM_HOME and GEM_PATH and such. And then Bundler is a separate project that overloads the Rubygems functionality.

And all of this song and dance is to make it possible for you to type require 'my_file' and the right my_file.rb or my_file.bundle[2] or my_file.so is read from disk, parsed, and evaluated line-by-line.

The actual implementation is full of edge cases but actually kind of simple to understand: require and gem are just methods in Ruby, not reserved keywords. It works like this:

Ruby core defines Kernel.require
then Rubygems saves require as Kernel.gem_original_require for its own use but totally redefines Kernel.require and defines a Kernel.gem.
Then Bundler reverses what Rubygems did to require and overrides the gem method.

Right, but why do we need “bundle exec”?

Let’s use the same diff trick to compare a process’s environment with and without bundle exec:

$ diff <(bundle exec env) <(env)
< _ORIGINAL_GEM_PATH=/Users/jackdanger/.rvm/gems/ruby-2.2.0:/Users/jackdanger/.rvm/gems/ruby-2.2.0@global
< RUBYOPT=-rbundler/setup
< RUBYLIB=/Users/jackdanger/.rvm/gems/ruby-2.2.0/gems/bundler-1.10.5/lib

That -rANYTHING is the same as evaluating require "ANYTHING" in Ruby source code. It’s weird that there’s no space but it, hilariously, allows there to be an ubygems.rb so ruby -rubygems works.

RUBYOPT is the flag that’s passed to Ruby when invoked. For example, the following two lines are equivalent:

$ ruby -rrails -e 'puts defined?(Rails)'
$ RUBYOPT=-rrails ruby -e 'puts defined?(Rails)'

And RUBYLIB is the default load path that Ruby searches when you require something:

$ echo 'puts :hi!' > myfile.rb
jackdanger $ ruby -rmyfile -e ''
/Users/jackdanger/.rvm/rubies/ruby-2.2.0/lib/ruby/2.2.0/rubygems/core_ext/kernel_require.rb:54:in `require': cannot load such file -- myfile (LoadError)
        from /Users/jackdanger/.rvm/rubies/ruby-2.2.0/lib/ruby/2.2.0/rubygems/core_ext/kernel_require.rb:54:in `require'
jackdanger $ RUBYLIB=. ruby -rmyfile -e ''
hi!

Bundler’s bundle exec requires the Bundler setup file which lets Bundler do all its file-finding hacks for when you later require something. But you may find in some cases that if your environment variables are already set up just right the requires might just work without Bundler’s help. Even then it doesn’t hurt to use bundle exec so you always know you’re using the right versions of everything from the Gemfile you have defined.

Do I have to keep typing this?

No, you don’t. You could hide this command behind aliases:

for cmd in rspec ruby rubocop rails; do
  alias $cmd="bundle exec $cmd"
done

Special thanks to Agis for reviewing this post and providing critical feedback.

Footnotes:

1. ^ That odd <() notation I’m using for executing subcommands is pretty useful. Check this out:

$ cat <(sleep 3 && date) <(sleep 3 && date)
Mon Jul 13 18:32:09 EDT 2015
Mon Jul 13 18:32:09 EDT 2015

cat is short for ‘concatenate’ and was originally written to squish two files together (cat file1 file2 > file3). What I’m doing here is concatenating the output of two different subcomands. We can see how this works if I print the arguments to cat to the screen rather than trying to read them and then print them:

$ echo <(sleep 3 && date) <(sleep 3 && date)
/dev/fd/11 /dev/fd/12

The terminal not only creates subprocesses for the stuff in parentheses but makes a new file descriptor that’s readable by any program (/dev/fd/{n}) and swaps that in as the argument to the current command. So it’s the same as if I’d done this:

$ date > date1
$ date > date2
$ echo date1 date2

The bonus here is that the subcommands are executed in parallel, hence the datestamps matching on the above example. This allowed me to diff the relatively slow rvm use && env subcommand in half the time as would normally be required.

2. ^ .bundle is a packaging format for Mach executables on OS X. .so is for shared objects (binaries meant to be used as libraries rather than executed directly).

Getting Started as a Software Engineer

2015-07-14T00:00:00-07:00

Audience: total beginner software engineers
Reading time: not that long

This January Square hosted the 4th College Code Camp by welcoming women who are studying engineering in college to Square’s SF office for five days of nerdventure.

I’m always really impressed with these students and I tell them in complete honesty that I’m really glad they’re doing what they’re doing so that one day I can work for them.
I’ve said the same when speaking to folks from Hack Bright, Code Fellows, Ada Developers Academy, General Assembly, and Hack Reactor.
The response I get is just about always the same: The students laugh nervously, smile at me, and probably wonder why I think that joke is funny.
It’s not a joke though – they really are going to have bright careers.
Each one of the students currently struggling with the concept of recursion will, if they keep working at it, eventually get it and move on to reach some far further goal. Maybe they’ll build a service that attracts thousands of new users overnight or they’ll make the front page of Reddit or they’ll be condescended to on Hacker News. Then they’ll know they’ve made it in this ridiculous industry.
But at this point in their career where they’re talking to me those things are all a far-away dream. And it’s hard to see how to get from where they are to where they want to be.

Learn to code in three and a half days

When I was starting my career in the mid-2000s there were two ways to educate myself: Reading the source code or giving up. The latter offers terrible odds of success.
Now there’s Coursera, Treehouse, Khan Academy, any number of bootcamp-style programs (including the unbelievably good Ada Developers Academy), Stack Overflow, O’Reilly and basically the entire rest of the internet.
It’s now almost trivially easy to take your first steps as a software engineer.
In fact, thanks to Hour of Code there are tens of millions of people who’ve tried their hand at programming for the first time.

I’m a huge proponent of getting people into engineering and I disregard the critics who say we’re letting prospective students underestimate how difficult it is. Underestimating the difficulty of a task is one of the most consistent character failings of an engineer. So anybody who thinks they can build a distributed messaging graph after 9 weeks is gonna fit right in.

However.

The stuff you’re missing

The skills you have after a Coursera class or a multi-week code school are not enough to get a good job. Unless you’re either independently wealthy or happily poor you don’t really have time to futz around for a few months on hobby projects while making no money. Even more importantly, the skills you have aren’t enough to let you feel confident in your abilities. You can solve some simple problems but you’re going to spend all day faced with terms and concepts that are still far beyond you.

More aggravating is you don’t even know what skills you’re lacking. If you interview you may get feedback that they’re “only looking for very senior people right now” which is code for “we don’t know how to train you and we actually need to hire somebody who can train us.” So I’ll break it down for you: You’re missing two large, entirely separate categories of skills.

Category 1: A broad knowledge of libraries and development patterns

The first category is what employers say they’re looking for: Senior experience in software engineering. They want somebody who knows every data structure. They want somebody who knows why Nginx can process hundreds of megabytes per second with almost zero CPU usage and they want somebody who knows the difference between a linearizable and non-linearizable system. Somebody who can debug a Linux box where all application processes are ‘zombied’ and can explain why Rust is an appropriate language for embedding inside a Ruby gem. They want somebody who can do TDD and write a parser for ARVUN in a day.

Sound intimidating? Yeah, it’s totally intimidating. But you know what? Nobody knows all that stuff. I even made that last one up (ARVUN is just some random letters I typed). As a natural byproduct of your daily work you will absolutely collect these insights into how computers function. What you learn will be different than what your peers will learn. This means you’ll always think everybody around you is a genius for what they know and they’ll think the same thing of you. Software engineering is an infinite field[1] so when a prospective employer lists stuff you should know they’re basically selecting a random set of acronyms that they’ve heard some of their peers mention. You already know stuff that they don’t even know that they need you to know.

A fantastic example of the ridiculous breadth of knowledge required to build software is illustrated by this Code Fellows blog post. I happen to know all of those things (because I learned them one at a time over about 8 years) but I have absolutely no idea how to, say, design a network. Seriously. No idea at all. Network engineers seem like gods to me and I to them.

So you’re screwed – permanently – because you’ll never know most of engineering.

Category 2: Comfort with your language and fundamental concepts

Luckily, those aren’t the skills you need to get a good job. When I hire people at Square and when I’ve hired in the past I look for teachability and familiarity with the primitives of building software. No matter what your training or experience I can’t hire you if you’re unable to learn. No matter how junior you are if you know your tools and know how to build pieces of software with me guiding you through the hard parts I can hire you and I know you’ll keep learning and contributing for your whole tenure at my company.

The largest blocker to your employment is that the tools of your trade don’t yet feel comfortable in your hands. You haven’t mastered your editor, you can’t reflexively set up a new project and get boilerplate code running while your mind is distracted. You haven’t yet tried all the wrong ways to write a recursive function. This is the primary thing keeping you from passing a coding interview (at a good company that actually tests your skill and doesn’t just ask you trick questions). Luckily, it’s also a set of skills that’ll help you be successful on the job as an engineer. Training yourself this way for an interview isn’t cheating yourself or your employer – it’ll really make you more valuable on the job.

You’re going to have to ignore that whole first category of stuff. Learning how each piece of software works is a fun lifetime journey and you can always learn things right when you need to. But if you want to get your first programming job you’ll need to develop a real comfort with the primitive pieces of your craft.

An aside: How to actually learn to program

Let’s get one thing straight: You can’t just watch a video online and know how to do something. This isn’t just about code. You can’t learn to sail a boat that way, you can’t learn to juggle that way, and you can’t learn to type that way. Unless you actually have a project and work on it until it’s done-ish and you face all the hurdles that crop up on your way you can’t develop your skill. And if you want to truly understand what you’ve been learning there’s one ancient, highly-successful method for making the knowledge fixed in your brain: Teach it.

I learned Ruby on Rails at Rails Forum way back in 2006. And I did it not by asking questions but by answering them. Somebody would be stuck with “How do I make an ActiveRecord query that uses multiple tables” or a similarly impossible question and I’d dive into the Rails source code to find an answer - even though I knew nothing more than the person who asked it. This is still the best way make concepts clear in your head. Find a project you want to complete to pick up the basics and teach somebody else those basics in order to master them.

What to learn: Learn your editor

I can’t stress enough how much easier your whole career will go if you make it a habit of memorizing shortcut keys and learning the advanced features of your editor. Whether you’re using Vim and Emacs like some 1980’s proto-hipster or Sublime Text like a modern day one there are advanced features in each that you don’t even know about. In every good editor you can select rectangular blocks of text and manipulate them. You can find all instances of a term in a single file or multiple files and modify them all at once. You can jump automatically from where a method or function is called to where it’s defined. Seriously, every editor can do this.

What to learn: One language

Somebody you know is really excited about the hot new language. Ignore them like you would ignore your crazy uncle’s politics at Thanksgiving. Nod and smile and just keep working on whatever language you have started learning.
Every language is fine to learn because they’re all terrible. Just like human languages[2] – each programming language can do some stuff super well and falls down at others. Ruby is elegant but psychotically inconsistent. Python is straightforward but will literally murder you if you try to upgrade to version 3. Java is powerful but will make you type the word ‘logger’ 5 times if you want to create a new logger (Logger logger = Logger.loggerFactory.iHateMyself.CreateLogger()). Lisp and Haskell will allow you to represent human life in just a single, mathematically-provably perfect line but nobody will care. JavaScript is the blunted stump of what could have grown into a computer language.

So learn a language and figure out how to express yourself in it. Learn its quirks and learn to love it despite its ugly parts. If you like your primary language start reading more about why it’s broken and terrible. It should probably take you about a week to figure out the serious limitations of any language. And only once you hate it a little would I trust you to build something important with it.

What to learn: Building small things

The best developers I know aren’t the ones who’ve crafted some huge system (though many have). The best developers can start and finish a small project in a single day. Maybe it just mashes up Instagram data with their Google Calendar but it’ll be about fifty lines of code and it’ll do exactly one thing properly. The more of these you write the more confidence you will have when solving any kind of technical problem.

I even have some suggestions for stuff to build as practice. These little things will give you the reflexes you need to pass a technical interview and they’ll also make the act of programming move from an intellectual exercise to muscle memory.

Project #1: Building a hip-hop name generator.

This is an easy and a fun one. Pick a list of first words and a list of second words then randomly print bad rap names for people by combining one element from each. “Lil’ Dicey”, “Ebenezer Money”, “Shady Slurpdog”. Set aside an hour and you’ll be able to print randomly generated names to the screen. Skills you’ll learn: arrays, using randomness, concatenation, printing to the screen.

Project #2: Building a word search solver.

You know those boring airport time-waster puzzles where there’s a grid of letters and you have to find the words in it? Make a program that can find the words ‘jack’, ‘danger’, and ‘coding’ in this:

CRZJPHJ
OEEMAAS
DGUGCCJ
INSKNEK
NAKATAD
GDSHJED

This’ll take you a couple hours if you’re familiar with your tools or all day if this kind of problem is new to you. Skills you’ll learn: depth-first or breadth-first search, nested arrays.

Project #3: Generating a maze on a screen.

Give this one a full day. It requires solving two different problems: You need to figure out the logic of how to generate a maze and you need to decide on some way of drawing something on the screen. A primitive, perfectly acceptable way would be to print “|” and “_” characters on a screen to symbolize walls.
Here’s an example of a pretty sweet-looking one: mazegenerator.net
The way you should build this is by cheating as hard as you possibly can. Seriously, just Google “building a maze generator” and follow along with how other people have done it. Skills you’ll learn: recursion, depth-first search, managing multiple data structures at once.

Project #4: Building a sudoku solver.

SO. FUN. Okay, maybe not the funnest thing ever, but if you like Sudoku it’s a blast. Same instructions as above and I recommend cheating on this one as well. Peter Norvig has a lovely and complete example of doing this in Python.

Project #5: Project Euler

Project Euler is kind of the gold standard for programming puzzles. It asks you to use any programming language in any environment you want to solve simple number questions. The first few problems are very easy and if you sort the problems by the number of people who’ve finished them you can find all the most accessible ones. Don’t worry if one is too tough, there are questions there for kids learning to code and questions for math Ph.Ds. Hopefully you’ll even find yourself accidentally learning the fun parts of math as you go. Project Euler will definitely make you a better developer because you’ll need to set up simple functions over and over and over and the nuts and bolts of programming will start to become muscle memory while you let your brain work on higher-level stuff.

Project #6: My interview question

Let’s Bike Across Europe!

That link above is the question I would ask you if I were to interview you for a job. It will be harder to solve the problem on your own at home rather than alongside me because you don’t have me explaining the hard parts but you’re welcome to try it. Cheat as hard as you can. If you come in to interview at Square and I asked you that question and you say “I tried it at home until I was good at it - watch this!” and then you did it really well I’d just hire you on the spot. That kind of initiative is what makes people successful in this industry.

You’re going to be fine

With each of these (except the first) you’re sure to run into some walls where you feel stuck and when that happens I’d love if you reached out to me on Twitter and we’ll crowd-source some help.

Even after building several projects you may still be feeling like computers are magic and you’re a dummy and maybe you don’t have what it takes to do this work. You may feel like everybody else ‘gets it’ and you’re missing something but don’t know what it is. You may even feel like everybody else is the same as each other and you’re the odd person out. Regardless, you’re going to do really well in this industry. You can type, you can think, and you can make computers obey you. In a couple years it’ll be your turn to teach newcomers the basics and to help them calm down and trust that they can do this. Until then just practice with your editor, practice with your language, and above all remember that you do have what it takes and you’re going to be fine.

Special thanks to the engineers Liz Rush, Danielle Sublett, and Davida Marion who reviewed drafts of this post.

Footienotes:

1. ^ The process of learning software involves writing
software which adds to the overall corpus of what there is to learn.
We have ten million people making new (often confusing APIs) and the
percentage of the whole that even the experts know is only
decreasing.

2. ^ Chinese is terrible for crosswords, a complete set of rules for English is impossibly large, Arabic and Hebrew don’t write down their vowels, Proto-Indo European had the singular, the plural, and a separate number form for “more than two”, Bengali distinguishes ‘bh’, ‘b’, ‘p’, and ‘ph’ (the only variance is the timing of when your vocal cords vibrate), Finnish has 16 (!!) cases, and French is wrong.

Danger's rules for working remotely

2015-07-11T00:00:00-07:00

At the time of this writing I’ve been working full time in the Square San Francisco office for about four years. The culture here relies on high-bandwidth interpersonal interactions and working in close physical collaboration. Some of my colleagues, when they work from home for a day or two, will return to the office and say they’re happy to be back because home “has too many distractions”. Others can’t wait to get home and away from the distractions of the office to focus.

My career in professional software started when I was 21 and until I joined Square 8 years later I only ever worked remotely and with flexible hours. The first three or so years I struggled to keep a schedule and stay on task but I eventually found a system that works for me really well. So well, actually, that when I joined Square my productivity took a hit as I tried to adjust to the distractions of a communal working space. Here are the rules that I developed for myself over most of a decade to make remote, flexible work more productive than being physically close to my colleagues.

Rule #1 Dress up

One of the side-effects of going to an office that we tend to miss is that it forces us to look and act respectably. When you dress well you’re going to feel good. It’s not just for other people - it’s something you do for yourself.

One of the oft-lauded benefits of working from home is the ability to work naked or be in your underwear or pajamas. The fact that you can do this is great. But this should be exceedingly rare. Because the moment it no longer feels special to work in your pajamas you become a human who lives in your pajamas. It’s a self-image you have to spend energy fighting against if you want to feel professional.

I once founded a company with a partner and worked for a full year on it without ever seeing him or any of the rest of our company in person. Everything was over the phone, email, chat, or laggy, low-fidelity video chat. It worked great. But it also meant that I could have spent 12 full months wearing nothing but the same greasy clothes and forewent every form of personal hygiene until I cried myself to sleep every night in a sweaty ball of self-disrespect.

So don’t skimp on nice clothes and a good morning bathing routing. You’re not doing it because somebody else expects it of you, you’re doing it because you’re a professional and you’re good at what you do and you should look good doing it - even if the only person who sees you is yourself in the mirror.

Rule #2: Don’t touch your computer until you go outside once

This is both the hardest rule to follow and the easiest. Years ago I had a morning workout routine that saw me at the gym at 7am. Once I stopped going so early I just began work that much earlier. And then I started hating every day because I’d wake up and immediately open my email. There were a few days where the sun had set and I was still in bed, furiously trying to do something that seemed really urgent.

Maybe you don’t need this rule but I am a person of extremes. So, to keep myself from forgetting about the unfathomable wonder of our planet, I go outside – even just to walk around the block – before my email gets a chance to eat me alive. As a side effect this forces me to also put on clothes which, if I want to keep them clean, forces me to shower.

Rule #3: Initiate relational connections

The Square SF office has some 600 people all in one giant room. This is amazing when you want to make friends out of your colleagues; there are so many people around that it’s really easy to start a conversation.

But even having so many lovely people all in the same place every day isn’t enough to prevent loneliness. Building a relationship requires more than “Hi, how are you? I’m fine” with a hundred different people each day - it takes initiating vulnerably and sharing your real self with someone.

The difference between how this works in an office or remotely is only in the very first step. If you see someone while walking past their desk then you might stop to chat. If you’re remote you have to go initiate a chat. You can do this without having a work-related question, without any particular topic to discuss, solely for the purpose of building a relationship.

One-on-one meetings serve this function but so do watercooler-style chat rooms and end-of-week Google Hangouts where everybody in the team joins and just plays around with putting on funny hats and sharing jokes. Getting past that first step – just saying you want to connect with somebody – is the only distinct skill needed to work remotely.

Rule #4: Record your daily accomplishments

An unfortunate truth of office work is that we evaluate the output of our colleagues and reports by how much time they seem to spend at work. If they’re in the office before us and leave after us we say they’re hard workers. And if we don’t see them for two weeks we assume they’re at home marathoning Netflix.

In my opinion this creates work cultures where there’s no distinction between the cost of the work and the value. The cost is how much of your time and energy and willpower and emotional investment it took to perform a task. And the value is how much competitive advantage and/or profit was provided to the business. Your company should seek to minimize its costs and maximize value, right? Which would mean minimizing how much of employee time is spent at work doing non-valuable things. And maximizing what each person produces.

Sadly, if you don’t provide a clear story about the value you provide you’ll be measured by the cost you incur working. If you want to prove your value to your colleagues/lead/clients you need to actually communicate what you’ve accomplished. Not what you’re working on – your accomplishments. When your face isn’t visible your output neds to be. I did this for years and it allowed me to find tasks that took only an hour but would provide a full day’s value. Then I could either take off the rest of the day or, more likely, work on things that I wanted to do that I knew wouldn’t have a direct visible output.

When I first started managing a team at Square I set up an iDoneThis.com account that asked each of us the same question every evening: “What is different in the world because of your work today?” I like this question because you don’t get to say how you spent your time. I don’t care how somebody I’m paying spent their time – I care what they accomplished. And I’m not interested in providing an incentive structure that rewards worthless, hard tasks.

This is one of the great liberations of remote work – you can just think about the value. What have you actually accomplished today? Is your client/customer satisfied? If so, you did a great job, even if you did it in 15 minutes.

Rule #5: SPINE

Several years ago a close friend pointed out to me that it was obvious to him why I’d get depressed during the work day. He introduced me to a silly acronym “SPINE” that represents the things you need to get each and every day.

Sleep

A full night’s sleep, no exceptions. If you report to me and you didn’t get enough sleep the night before I’ll ask you to take an afternoon nap. We’re about as useful working while sleep-deprived as we are driving while sleep-deprived: You can do most of it fine but you’ll miss a few details and that can make all the difference.

Pleasure

This might be reading a book or dancing to music. It might be sex or going to a movie. Whatever you do for pleasure, do at least one of those things every day.

Intimacy

We need intimacy with someone every day. Parents who’re stuck at home with little ones understand this best when they realize they’d chop off an arm for a single adult conversation. Just being close to someone who understands you whom you can understand makes a world of difference. I believe this is something that needs to be scheduled in alongside work stuff at a very high priority.

Nutrition

One of the great advantages that Silicon Valley-style startups have is that they provide healthy food to their employees. In my time at Square I’ve seen people look healthier a few weeks into joining the company thanks to the food.

Exercise

When I was first dating my ex-wife we’d plan a day together and she would ask “But when am I going to get exercise?” I was baffled the first few times because she had just exercised the previous day, why’s she doing it again? After a while that question burrowed into me and I started asking it, too. Between 2006 and 2009 I lost 50 pounds and transitioned from being a non-runner to finishing a half-Ironman. Yeah, this is me all braggy-braggy but it’s true and it’s because I made exercise a daily thing, not a sometimes thing. Walking totally counts. So does dancing. Anything where I move my body.

These rules could be distilled into just two: Take care of yourself and take care of the needs of the person who’s paying you. If you do that then there’s no reason you can’t make your job happen in a hammock on a beach somewhere.

Figuring out what's in any Unix file

2015-06-28T00:00:00-07:00

If you have a file that ends in a known extension like list.txt or mountain.jpg then you can guess what’s inside it. But how do you actually know? After all, you could mv list.txt kitten.png and suddenly your plain text file is pretending to be an image of an adorable little cat.

If the contents of the file are text then the easiest way to look inside is the head command:

> $ head kitten.png
Go to the store and buy:
* Overpriced avocados
* Organic lawn furniture
* Seven gallons of 1% milk

head shows you the first 10 (by default) lines of any file. And as long as it’s a text file with newline characters signifying line breaks then this shows you something readable. But what if it’s actually an image file?

> $ head actually_a_kitten.png
âPNG
IæãR
+iCCPICC Profile(œùíw\ì˚æŸÉïÜå∞˜^Dˆô≤D!$1$
                                        ≈Öà
T.ê¢à´eHùà(HQk±ä®®4ëœßıˆˆ~û=ê|∏º
⎼▒☃┌⎽ └▒⎽├e⎼ $

Oh lovely. That last line there (ending in a $) is actually the prompt for your next command. We just accidentally sent so many weird characters to the screen that some of them changed the encoding of your terminal. No fun.

A safer way to do this would be with the less command which creates a new full-terminal buffer and safely returns you to your (working) prompt when you’re done. But even then you need to parse this binary with your eyes and hope that the âPNG is, in fact, a sign that this is a valid png file.

The `file` command

Luckily, any Unixy OS has the file utility installed. This is a program that will try to guess the type of a file based on examining details of the contents.

> $ file actually_a_kitten.png
actually_a_kitten.png: PNG image data, 8 x 8, 8-bit/color RGBA, non-interlaced

Not only do we know for sure that it’s a PNG but we know the resolution and the color depth. Handy.

How does `file` work?

This utility first tries to make a distinction about whether the argument is a file that’s safe to print on the screen (“text”), executable, or any other kind of data.

The procedure for determining this is to first look at the file on disk and see if it’s special in some way, empty, or if there’s some other significant issue with it that makes examining the contents unnecessary. It basically runs the stat command on your file:

> $ stat kitten.png
  File: 'kitten.png'
  Size: 3084            Blocks: 8          IO Block: 4096   regular file
Device: fd00h/64768d    Inode: 533679      Links: 1
Access: (0644/-rw-r--r--)  Uid: ( 1193/jackdanger)   Gid: ( 1193/jackdanger)
Access: 2015-06-28 07:35:35.864034633 +0000
Modify: 2015-06-28 07:35:35.864034633 +0000
Change: 2015-06-28 07:35:35.864034633 +0000

It’s a file (not a symlink or a directory) and it takes up 8 blocks of space, using a total of 3084 bytes. Alright then, let’s read it and figure out what’s inside.

Finding the magic on your computer

When I first learned how this worked the person showing me the ropes asked “Do you want to see where the magic is?” and I was utterly confused. Then he ran man file and pointed out that the process of determining what’s inside a file from individual heuristics is, in fact, known as magic.

Or, or more specifically:

> $ man file | tr ' ' "\n" | grep /magic  # this tr will swap spaces for newlines
/etc/magic
/etc/magic,
/usr/share/misc/magic
/usr/share/misc/magic.mgc
/usr/share/misc/magic.mgc,

Before we look inside one of these files by hand let’s practice using file itself:

> $ file /usr/share/misc/magic.mgc
/usr/share/misc/magic: symbolic link to `../file/magic.mgc'

Oh, that didn’t even inspect the contents of the file – it stopped at the stat step. What did it see there?

> $ stat /usr/share/misc/magic.mgc
  File: ‘/usr/share/misc/magic.mgc’ -> ‘../file/magic.mgc’
  Size: 17              Blocks: 0          IO Block: 4096   symbolic link
Device: ca01h/51713d    Inode: 2023        Links: 1
Access: (0777/lrwxrwxrwx)  Uid: (    0/    root)   Gid: (    0/    root)
Access: 2015-06-28 08:12:44.599057183 +0000
Modify: 2014-07-10 17:48:04.000000000 +0000
Change: 2014-12-15 08:35:19.791057183 +0000
 Birth: -

Yeah, I see the words ‘symbolic link’ there for sure. Now let’s follow the symlink and see what’s really inside it:

> $ readlink -f /usr/share/misc/magic.mgc
/usr/share/file/magic.mgc  # The following is identical to:
> $ file $(readlink -f !$)  # "file /usr/share/file/magic.mgc"
/usr/share/file/magic.mgc: magic binary file
for file(1) cmd (version 8) (little endian)

This is great. It knows this file so well that it knows it’s its own magic file-detection file. So what’s inside it?

> $ less /usr/share/file/magic.mgc
BINARY DATA STUFF

Yech. How about one of the others?

> $ head -n 15 /usr/share/file/magic
##------------------------------------------------------------------------------
## $File: acorn,v 1.5 2009/09/19 16:28:07 christos Exp $
## acorn:  file(1) magic for files found on Acorn systems
##

## RISC OS Chunk File Format
## From RISC OS Programmer's Reference Manual, Appendix D
## We guess the file type from the type of the first chunk.
0       lelong          0xc3cbc6c5      RISC OS Chunk data
>12     string          OBJ_            \b, AOF object
>12     string          LIB_            \b, ALF library

# RISC OS AIF, contains "SWI OS_Exit" at offset 16.
16      lelong          0xef000011      RISC OS AIF executable

Now we’re talking. This format is a series of specific checks for byte values in a file. The first couple examples are kinda hard to make sense of so I’ll skip down to a simpler one:

0       string          \x89PNG\x0d\x0a\x1a\x0a         PNG image data
!:mime  image/png
>16     belong          x               \b, %ld x
>20     belong          x               %ld,
>24     byte            x               %d-bit
>25     byte            0               grayscale,
>25     byte            2               \b/color RGB,
>25     byte            3               colormap,
>25     byte            4               gray+alpha,
>25     byte            6               \b/color RGBA,
#>26    byte            0               deflate/32K,
>28     byte            0               non-interlaced
>28     byte            1               interlaced

This means “If the string of bytes starting at position 0 are as follows then it’s a ‘PNG image data’”. Each of the lines starting with > can refine the result, adding more data to it. Apparently it’s part of the PNG format that if the 25th byte is a 4 then this is a gracscale image with an alpha channel. Cool.

Hey, we can detect Photoshop files, too!

0       string          8BPS Adobe Photoshop Image
!:mime  image/vnd.adobe.photoshop
>4   beshort 2 (PSB)
>18  belong  x \b, %d x
>14  belong  x %d,
>24  beshort 0 bitmap
>24  beshort 1 grayscale
>>12 beshort 2 with alpha
>24  beshort 2 indexed
>24  beshort 3 RGB
>>12 beshort 4 \bA
>24  beshort 4 CMYK
>>12 beshort 5 \bA
>24  beshort 7 multichannel
>24  beshort 8 duotone
>24  beshort 9 lab
>12  beshort > 1
>>12  beshort x \b, %dx
>12  beshort 1 \b,
>22  beshort x %d-bit channel
>12  beshort > 1 \bs

There are some 500 known formats in here (egrep -c '^# .* file' /usr/share/misc/magic) detecting all kinds of things. How correct is this set of heuristics, though? Since it’s just looking for key data and ignoring most other bytes is it possible to fool it?

To generate fake data we’re going to read from /dev/urandom and write it straight to standard out (i.e. your screen). we’ll do this 512 bytes at a time and pipe it straight to file as a special (-s) file:

> $ dd if=/dev/urandom bs=512 | file -s -
/dev/stdin: data

Okay, not much. It’s “data”. Great. But if we try that in a bash loop…

> $ for _ in {0..20}; do dd if=/dev/urandom bs=512 | file -s -; done
/dev/stdin: data
/dev/stdin: data
/dev/stdin: data
/dev/stdin: data
/dev/stdin: data
/dev/stdin: data
/dev/stdin: data
/dev/stdin: data
/dev/stdin: data
/dev/stdin: data
/dev/stdin: data
/dev/stdin: data
/dev/stdin: data
/dev/stdin: data
/dev/stdin: MPEG ADTS, layer III, v1,  40 kbps, 48 kHz, Monaural
/dev/stdin: data
/dev/stdin: data
/dev/stdin: data
/dev/stdin: data
/dev/stdin: data
/dev/stdin: data

Wait. What? What’s an MPEG ADTS file? Doesn’t matter, we generated data that fit the profile of it with just a few bytes in the right place.

And if we run this in a loop and ignore the misses we see way more interesting stuff.

> $ while :; do dd if=/dev/urandom bs=512 | file -s - | grep -v ': data'; done
/dev/stdin: Sendmail frozen configuration  - version =\236\207\021\033\316h\312d\236i\326\033\236\350C\234\373
/dev/stdin: 8086 relocatable (Microsoft)
/dev/stdin: hp200 (68010) BSD
/dev/stdin: Sendmail frozen configuration  - version \332\317\022?\310]\272s+^\021\032\212\234Q\341;\326\320
/dev/stdin: SysEx File - Fujitsu
/dev/stdin: DBase 3 data file
/dev/stdin: DBase 3 data file (899713281 records)
/dev/stdin: MPEG-4 LOAS, single stream
/dev/stdin: DBase 3 data file with memo(s) (1054998150 records)
/dev/stdin: Dyalog APL version 219 .105

This really is magic, then, in the sense that this isn’t predictable and isn’t super reliable. But it’s still more effective than trying to cat it to your screen and look at the bytes yourself.

Essential terminal commands for new engineers

2015-02-04T00:00:00-08:00

These are often called “bash shortcuts” or “bash tips” but, really, these apply to multiple different shell programs. Bash, ZSH (“zee shell”), etc. and any program that uses a library called ‘readline’ in it all work with (most) of the stuff on this page.

There are literally thousands of these kinds of shortcuts that you could adopt as part of your daily workflow but I’m deliberately presenting just the most commonly useful ones that are truly worth your time. My promise to you: learn these by heart and you’ll move twice as fast in the terminal for the rest of your career.

Reusing parts of previous commands

The !$ shortcut

Most of the commands you type look something like this:

$ command_name --some --arguments filename

The file that you’re working with is the most important part of this because you’re probably not just going to do one thing with that file. More likely you’ll call less filename on it to take a look inside or python filename to run it or vim filename to edit it or cat filename to pipe it to some program or maybe grep filename to check if there’s a specific word or phrase inside it.

Because the filename is the last argument it’s worth practicing the terminal shortcut for inserting the last argument of the previous command into your current one. Try this out in your terminal right now to see what I mean:

# Making a file, examining it, giving it an extension, and making sure it has what we need
$ echo "My name is" >> somefile
$ echo "Jack Danger" >> somefile
$ less somefile
$ mv somefile somefile.text
$ ls -lAG somefile.text
$ grep "Jack Danger" somefile.text

How many times did you just type “somefile”? Now try typing out this one:

$ echo "My name is" >> somefile
$ echo "Jack Danger" >> !$
$ less !$
$ mv !$ !$.text
$ ls -lAG !$
$ grep "Jack Danger" !$

The !$ shortcut means “the last argument of the last command I ran”. I use this all day every day. It’s worth teaching your fingers to type those two characters in quick succession because this muscle memory will help you stay in a state of flow and not fall out just because of the tedium of typing and trying to get filenames right. Particularly if instead of somefile you’re working with apache-http-webserver-nightly-2015011223.tgz

The !! shortcut

This one is slightly less commonly used but is really handy in a specific situation. When you’ve typed a command and you needed to run it with sudo you can either do this:

$ rm file_that_I_hate
> rm: Permission denied
$ sudo rm file_that_I_hate

Sure, that’s fine. But to save yourself some typing and, more importantly so you don’t mess up the actual command typing it by hand again, this is better:

$ rm file_that_I_hate
> rm: Permission denied
$ sudo !!

The !! is a fill-in for the entire previous command.

Text Manipulation

Finding text in a file

Grep is your best friend. There are other, faster versions of this program (hint: brew install ag && ag --help) but grep is installed on every unix box everywhere and it’s good enough. The primary way you’ll use grep is to see which files have what you need:

$ grep "Error:" /var/log/*.log

If you have a regular expression you’d like to use you can just run egrep instead of grep:

$ egrep "Error:|http" /var/log/*.log

And, while there are many flags you can use to customize how you use grep, the one I recommend getting familiar with right away is -C (C for “context”). It will print out lines above and below the match for what you’re searching for. So

$ grep -C 1 "Error:" /var/log/*.log

Will show you not just the lines with “Error:” but will show you one line before and after so you can maybe figure out what’s causing the error.

Printing columns of data

This one is deceptively useful and only requires a little bit of arcane syntax (which you can hide away if you want). You’re often going to have data printed to your screen like this:

$ grep "Error:" my.log
> [error] 2015-01-05 12:31:40 Error: SadComputer - [log level: 1]
> [error] 2015-01-05 12:31:41 Error: BrokeComputer - [log level: 1]
> [error] 2015-01-05 12:31:43 Error: NoFunAtAll - [log level: 1]
> [error] 2015-01-05 12:31:48 Error: ThingsAreTwistedAllUp - [log level: 1]

Maybe all you want is the actual error message here. No problem! There’s a program called awk that’s perfect for this. It does a lot of fancy stuff but without anything special it’s really good at splitting input up into columns and letting you pick which ones you want.

The “SadComputer” message in the first line is the 5th column of text (each column is any contiguous set of characters separated by whitespace). Here’s how we just print that column:

$ grep "Error:" my.log | awk '{print $5}'
> SadComputer
> BrokeComputer
> NoFunAtAll
> ThingsAreTwistedAllUp

That syntax (a print $5 inside curly braces inside quotes) is worth memorizing. But if you dont want to you can always throw this into your ~/.bash_profile and you can make yourself a shortcut:

awkc () {
  awk "{print \$$1 }"
}

That defines a new function that formats a call to awk for you. You’d use it like this:

$ grep "Error:" my.log | awkc 5
> SadComputer
> BrokeComputer
> NoFunAtAll
> ThingsAreTwistedAllUp

Navigating

Try the tab key

I first started using Linux even before I knew how to program because I couldn’t afford a very powerful computer when I was in college. I remember copying and pasting commands out of web pages to try to install programs. Then, inevitably, I’d be typing some filename that was 60+ characters long and a typo was nearly guaranteed. Nobody told me that you could hit the tab key and your shell will automatically complete filenames for you. Not only that, but depending on the context it may even complete long command invocations for you. When in doubt - hit the tab key.

Go back to the directory you were just in

Running cd - will go back to the directory you were in last and typing it again will return you to where you are now. Super useful if you’re switching mostly between just two places.
git checkout - does the exact same thing but with two git branches.

Finding files

There’s a program called find that is kind of user-unfriendly. You find files like this:

$ find /some/directory -name filename.text

And the filename has to be exactly filename.text. If you want a fuzzy match you have to add asterisks and quotes:

$ find /some/directory -name "*filename*"

Personally, I find all this to be cumbersome because I’m often just want to type part of the filename and I usually intend to find it just in the current directory. So I use this shell function as a wrapper (again, you can just put this in your ~/.bash_profile) and it’ll get picked up:

name () {
  # If the second argument ($2) is not an empty string
  if [[ -n $2 ]]; then
     dir=$2 # You typed a second argument, it's a directory to search in
  else
     dir=. # No second argument given, let's use the current directory
  fi
  find $dir -name "*$1*"
}

Then you can look for files by name like this:

$ name fonts
# finds anything named "*fonts*" in the current directory
$ name fonts /var/log

There are so many variations of these commands you can play with but, like learning any skill or exploring any new system, I recommend taking things one step at a time. When you find you use one of these commands really frequently in the same way feel free to add more to your ~/.bash_profile so you can save yourself some typing (and typos).

And please do copy freely from my ‘dotfiles’ repo on Github.

Making two ActiveRecord models look like one

2014-12-16T00:00:00-08:00

I recently encountered a MySQL table backing an ActiveRecord model that grew so unexpectedly fast that it ran out of space. Our engineering team did what anybody would do in an emergency: moved all the existing data somewhere with more space and created a new, empty table so we wouldn’t lose new writes.

Due to the nature of this data and the code that references it we couldn’t immediately move all queries to just use the new storage location. We had to keep both datasets for a while and we needed existing references to the ActiveRecord model to just keep working.

Note: Our “fix” was purely temporary. What I’m about to describe is a gross hack that got us through the immediate crisis but we immediately began work to properly collapse these two datasets into one with a better runway for future growth. It’s a useful example of Ruby’s flexibility but please don’t put what follows into production unless you absolutely have to.

What we did was swap out the ActiveRecord model for a bare class that simply delegates all the messages an instance receives to both of the MySQL datastores to present a unified view of two totally different tables on two different hosts.

Here’s how we did it.

Delegating everything

All of our code was referencing TheModel and expecting it to behave like ActiveRecord. So the first step was to hide the actual model as inner class of a BasicObject (which is an object that has almost no methods defined). Then we created a second inner class that referenced the new dataset. Then we took all the existing, shared behavior from the original model and put it in a module to be included by both.

class TheModel < BasicObject
  module ExistingBehavior  # methods that used to be inside TheModel
    def self.included(model)
      model.class_eval do  # method calls that used to be in the class
                           # e.g. `belongs_to :user`
      end
    end
  end
  class New < ::ActiveRecord::Base
    establish_connection "original_datastore"  # Connect to the right db
    self.table_name = :records
    include ExistingBehavior
  end
  class Old < ::ActiveRecord::Base
    include ExistingBehavior
    establish_connection "other_datastore"  # Connect to the right db
    self.table_name = :records_other
  end
end

Reading from two places
What we’ll need is a way to turn calls for TheModel.all or TheModel.where(some_condition).all actually reads from two different datastores. It’s not too hard to proxy to just one datastore because all we need to do is delegate a few calls on the TheModel class to the inner model:

class TheModel < BasicObject
  class << self
    delegate :all,
             :where,  # This isn't a complete list,
             :first,  # of creation methods but
             :last,   # it'll do for now
             :new,
             :create,
             :create!,
             :to => :'TheModel::New'
  end
  class New < ActiveRecord::Base
  end
end

Now if you run TheModel.all you’re actually calling TheModel::New.all. And any chained messages you add on to the result of that call will go to the right place.

But what we really want is to have TheModel.all return TheModel::New.all + TheModel::Old.all. Let’s start with a naive approach:

class TheModel < BasicObject
  class << self                            # Keep delegating constructor methods
  delegate :new, :create, :create!,        # to the new dataset
           :to => :'TheModel::New'
  end

  def self.method_missing(method_name, *args, &block)  # all other calls get sent to
    New.send(method_name, *args, &block) +             # both models and joined
    Old.send(method_name, *args, &block)
  end
end

But that assumes that all of our operations will be immediately concatenating two values. That’s not true, sometimes we want to chain up successive where calls. To make this possible we need some kind of intermediate object that holds state before we’re ready to concatenate the results:

class TheModel < BasicObject
  def self.method_missing(method_name, *args, &block)
    FindInTwoPlaces.new(New, Old).send(method_name, *args, &block)
  end

  class FindInTwoPlaces
    def initialize(new_dataset, old_dataset)
      @new_dataset, @old_dataset = new_dataset, old_dataset
    end

    def all
      @new_dataset.all + @old_dataset.all
    end

    def method_missing(method_name, *args, &block)
      FindInTwoPlaces.new(                                    # All calls except `all`
        @new_dataset.send(method_name, *args, &block),        # just create a new instance
        @old_dataset.send(method_name, *args, &block)
      )
   end
end

This FindInTwoPlaces class is initialized with two datastores. Initially that’s just the bare models representing the complete datastores. But as we chain messages each datastore object gets further refined. If you call TheModel.where("id=1") you get a FindInTwoPlaces instances that contains TheModel::New.where("id=1") and TheModel::Old.where("id=1"). When you then call .all on that object they get concatenated together.

So far so good, but we’re getting a lot of complexity for just the .all class method. We can do better by defining all of the final methods that we will want to use and proxying all other messages to a new intermediate object. For now let’s just implement all, count, and to_a

class TheModel < BasicObject
  def self.method_missing(method_name, *args, &block)
    FindInTwoPlaces.new(New, Old).send(method_name, *args, &block)
  end

  class FindInTwoPlaces
    def initialize(new_dataset, old_dataset)
      @new_dataset, @old_dataset = new_dataset, old_dataset
    end

    def all
      @new_dataset.all + @old_dataset.all
    end

    def count
      @new_dataset.count + @old_dataset.count
    end

    def to_a
      @new_dataset.all + @old_dataset.all
    end

    def method_missing(method_name, *args, &block)
      FindInTwoPlaces.new(
        @new_dataset.send(method_name, *args, &block),
        @old_dataset.send(method_name, *args, &block)
      )
   end
end

Now TheModel.where("id=1").order("created_at DESC").limit(2).all works as expected. It’ll return all records from both datasets that match those conditions. However, if you call .first at the end instead of .all it’ll totally fail to work. Let’s fix that.

class TheModel < BasicObject
  def self.method_missing(method_name, *args, &block)
    FindInTwoPlaces.new(New, Old).send(method_name, *args, &block)
  end

  class FindInTwoPlaces
    def initialize(new_dataset, old_dataset)
      @new_dataset, @old_dataset = new_dataset, old_dataset
    end

    def first
      @new_dataset.first || @old_dataset.first
    end

    def all
      @new_dataset.all + @old_dataset.all
    end

    def count
      @new_dataset.count + @old_dataset.count
    end

    def to_a
      @new_dataset.all + @old_dataset.all
    end

    def method_missing(method_name, *args, &block)
      FindInTwoPlaces.new(
        @new_dataset.send(method_name, *args, &block),
        @old_dataset.send(method_name, *args, &block)
      )
    end
  end
end

Here we’ve introduced our first application-specific decision. It may be that you want one dataset prioritized over another. For my case here I need the newer one if it exists. We’ve also introduced our first operation that isn’t concatenative. If we implement all possible final methods we’ll have to be careful to use + or || or other operators as is appropriate.

Let’s implement all of the rest of the methods that might appear as the final part of an ActiveRecord query chain. And to save on some typing I’m going to go ahead and refactor them into lists of method names grouped by operator. I’ll also be fixing a bug that exists in the above implementations by ensuring that all arguments to these methods get properly forwarded to the internal datastore objects.

class TheModel < BasicObject
  def self.method_missing(method_name, *args, &block)
    FindInTwoPlaces.new(New, Old).send(method_name, *args, &block)
  end

  class FindInTwoPlaces < Struct(:new_dataset, :old_dataset)  # Making this a struct lets us skip
    %w{all count to_a pluck}.each do |m|                     # writing an initializer and it
      define_method m do |*args, &block|                     # gives us accessors for free
        new_dataset.send(m, *args, &block) + old_dataset.send(m, *args, &block)
      end
    end

    %w{first last}.each do |m|
      define_method m do |*args, &block|
        new_dataset.send(m, *args, &block) || old_dataset.send(m, *args, &block)
      end
    end

    def empty?
      new_store.empty? && old_store.empty?
    end

    def method_missing(method_name, *args, &block)
      FindInTwoPlaces.new(
        new_dataset.send(method_name, *args, &block),
        old_dataset.send(method_name, *args, &block)
      )
   end
end

You may notice I haven’t implemented the entire API of an ActiveRecord model. That’s because the full API includes a ton more methods including both .forty_two and .forty_two!.
If we needed all of those operations we’d probably have deeper problems because the objects in an application need to communicate over the narrowest API possible to keep the app simple. However, blindly passing them off to method_missing will have indeterminate results. So we should explicitly disallow their use.

Here, then is the final version of our wacky meta-model. It presents two totally separate ActiveRecord datastores (possibly on different hosts or even using different database technology) as a single, unified datastore:

class TheModel < BasicObject
  class << self
    delegate :new, :create, :create!, :to => :'TheModel::New'
  end

  def self.method_missing(method_name, *args, &block)
    FindInTwoPlaces.new(New, Old).send(method_name, *args, &block)
  end

  module ExistingBehavior
    def self.included(model)
      model.class_eval do
      end
    end
  end
  class New < ::ActiveRecord::Base
    establish_connection "original_datastore"
    self.table_name = :records
    include ExistingBehavior
  end
  class Old < ::ActiveRecord::Base
    include ExistingBehavior
    establish_connection "other_datastore"
    self.table_name = :records_other
  end

  FindInTwoPlaces = Struct.new(:new_dataset, :old_dataset) do

## Concatenating operations
    %w{
      all
      count
      delete_all
      destroy_all
      explain
      ids
      pluck
      sum
      to_a
      update_all
    }.each do |m|
      define_method m do |*args, &block|
        new_dataset.send(m, *args, &block) + old_dataset.send(m, *args, &block)
      end
    end

## Selecting a value from one or the other
    %w{
      any
      first
      include
      last
      many?
    }.each do |m|
      define_method m do |*args, &block|
        new_dataset.send(m, *args, &block) || old_dataset.send(m, *args, &block)
      end
    end

## Impossible operations
    %w{
      average
      calculate
      create
      create_with
      delete
      destroy
      exec_explain
      exists
      fifth
      find
      find_by
      find_each
      find_in_batches
      find_or_create_by
      find_or_initialize_by
      first
      first_or_create
      first_or_initialize
      forty_two
      fourth
      fourth!
      last
      lock
      maximum
      minimum
      readonly
      second
      take
      third
      update
    }.each do |m|
      define_method m do |*args, &block|
        raise "Sorry, #{m} isn't possible via FindInTwoPlaces, do it by hand"
      end
    end

    def method_missing(method_name, *args, &block)
      self.class.new(
        new_dataset.send(method_name, *args, &block),
        old_dataset.send(method_name, *args, &block)
      )
    end
  end
end

Again, please don’t use this in production unless you absolutely have to.

Build a Web Crawler in Go

2014-05-07T00:00:00-07:00

One of the basic tests I use to try out a new programming language is building a web
crawler. I stole the idea from my colleague Mike Lewis and
I love it because it uses all the principles necessary in internet engineering: A web
crawler needs to parse semi-structured text, rely on 3rd-party APIs, manage its internal
state, and perform some basic concurrency.

Starting a new project with Go

This is a tutorial that is accessible for complete beginners to the Go programming
language or to web programming. All the commands you need to run are provided and all
the code you need to type into the .go source code files is shown to you a piece at a
time. Each time I introduce a new concept you’ll need to edit the same file, slowly
building up functionality. When you run each version of the code Go will give you an
exact error message with a line number so you’ll be able to fix any mistakes you make.
If you get totally lost you can just copy straight out of the page into a new file and
pick back up. If you’re new to Go I highly recommend reading the excellent Go
documentation to help you make sense of what’s on this page.

Since this example requires the Go programming language you should start by installing
Go:

sudo apt-get install golang  # (if you're on Linux)
brew install go  # (if you're on a Mac)

Creating the ‘main’ function

Go is so fast that it’s practically a scripting language. All you need to run it
is a ‘main’ package and a ‘main’ function. On my machine the following tiny program
takes only 0.04 seconds to compile. Let’s create a new file and try it out:

//// Put this in a new file 'crawl.go'
package main     // This is technically a perfectly
func main() {}    // valid Go program, even if a bit boring

Now you’re a Go programmer. Hooray! Let’s make it just slightly more interesting by
turning this into a Hello World program.

//// file: crawl.go
package main    // package will always be 'main' for our app.
import (        // the 'import' section is where you specify all
  "fmt"         // dependencies and 'fmt' is the package used for
)               // printing to the screen.

func main() {                   // The 'main' function is always the one that starts
  fmt.Println("I'm a gopher!")  // your program
}

And now let’s run it:

go run crawl.go  # run this in your terminal in whatever directory you created the file.

You could have executed go build crawl.go instead of go run crawl.go and it would
have just compiled the file for you. The “run” command both compiles and executes it so
you’ll find it turns Go into a usable scripting language (indeed, it’s faster than a lot
of Ruby or Python projects).

What’s a web crawler?

A web crawler is the portion of a search engine that scans web pages looking for links
and then follows them. It would normally store the data it finds into some database
where it can be useful but our version is just going to print the URLs to the screen and
move along.

While not quite enterprise grade this’ll let us play with all the same concepts and see
some really satisfying output as our little script wanders the web.

Step 1. Starting from a specific page

You’ve got to start crawling from somewhere and in our program we’ll let the person who
executes the crawler specify what starting page to use. This involves reading a command
line argument which, in most programming languages, will be stored in a variable named
something like ARGV and Go is no exception.

//// file: crawl.go
package main

import (
  "fmt"
  "flag"        // 'flag' helps you parse command line arguments
  "os"          // 'os' gives you access to system calls
)

func main() {
  flag.Parse()         // This stuff with 'flag' converts the command line
  args := flag.Args()  // arguments to a new variable named 'args'
                       // The ':=' form means "this is a brand new variable" and
                       // a '=' here would throw an error.
                       // At this point 'args' will be either an empty list
                       // (if no command line arguments were provided) or it'll
                       // contain some string values.
  if len(args) < 1 {   
    fmt.Println("Please specify start page")  // if a starting page wasn't provided as an argument
    os.Exit(1)                                // show a message and exit.
  }                                           // Note that 'main' doesn't return anything.
}

Now run this file by typing go run crawl.go and see that it yells at you because you
didn’t specify a starting web page. Then try running it with an argument provided (go run crawl.go http://news.google.com) and it won’t show that message anymore.

Step 2. Retrieving a page from the internet

The next thing you need is to download the page your starting URL represents so you can
scan it for links. In Go there is a great http package right in the standard library.
You can use the primitives Go gives you to turn your URL string into a string
representing the page body.

First I’ll show you what this looks like in isolation, then we can incorporate it into our crawler. Put the following in retrieve.go:

//// file: retrieve.go
package main    // Note: this is a new temporary file, not our crawl.go

import (
  "fmt"
  "net/http"    // this is the 'http' package we'll be using to retrieve a page
  "io/ioutil"   // we'll only use 'ioutil' to maek reading and printing
)               // the html page a little easier in this example.

func main() {
  resp, err := http.Get("http://6brand.com.com")  // See how we assign two variables at once here?
                                                  // That destructuring is really common
                                                  // in Go. The way you handle errors in
                                                  // Go is to expect that functions you
                                                  // call will return two things and the
                                                  // second one will be an error. If the
                                                  // error is nil then you can continue
                                                  // but if it's not you need to handle it.
  fmt.Println("http transport error is:", err)

  body, err := ioutil.ReadAll(resp.Body)  // resp.Body isn't a string, it's more like a reference
                                          // to a stream of data. So we use the 'ioutil'
                                          // package to read it into memory for us.
  fmt.Println("read error is:", err)

  fmt.Println(string(body))   // We cast the html body to a string because
}                             // Go hands it to us as a byte array

And run it with go run retrieve.go. You should see the body of
6brand.com printed to your screen. And if you scroll up to the top you’ll see that there were no errors (literally, err was nil) in either the transporting or reading of your http call. Yay, go you.

Let’s copy the new pieces of this code into our crawl.go:

//// file: crawl.go
package main

import (
  "flag"          // 'flag', 'fmt' and 'os' we'll keep around
  "fmt"
  "net/http"      // 'http' will retrieve pages for us
  "io/ioutil"     // 'ioutil' will help us print pages to the screen
  "os"
)

func main() {
  flag.Parse()

  args := flag.Args()
  fmt.Println(args)
  if len(args) < 1 {
    fmt.Println("Please specify start page")
    os.Exit(1)
  }
  retrieve(args[0])  // The reason we can call 'retrieve' is because
                     // it's defined in the same package as the calling function.
}

func retrieve(uri string) {  // This func(tion) takes a parameter and the
                             // format for a function parameter definition is
                             // to say what the name of the parameter is and then
                             // the type.
                             // So here we're expecting to be given a
                             // string that we'll refer to as 'uri'
  resp, err := http.Get(uri)
  if err != nil {            // This is the way error handling typically works in Go.
    return                   // It's a bit verbose but it works.
  }
  defer resp.Body.Close()  // Important: we need to close the resource we opened
                           // (the TCP connection to some web server and our reference
                           // to the stream of data it sends us).
                           // `defer` delays an operation until the function ends.
                           // It's basically the same as if you'd moved the code
                           // you're deferring to the very last line of the func.

  body, _ := ioutil.ReadAll(resp.Body)  // I'm assigning the err to _ 'cause
                                        // I don't care about it but Go will whine
  fmt.Println(string(body))             // if I name it and don't use it
}

What we’ve got now is an excellent start to a web crawler. It’s able to boot, parse the
URL you’ve given it, open a connection to the right remote host, and retrieve the html
content.

Step 3. Parsing hyperlinks from HTML

If you have a page of HTML you may want to use a regular expression to extract the
links. Don’t. Like, really
don’t.
Regular expressions are not a good tool for that. The best way is, sadly, to walk
through the tree structure of the page finding anchor tags and extracting href
attributes from them. In most languages this is no fun but in Go’s standard library it’s
extra not fun (though not nearly as painful as Java) and I won’t subject you to it here.
I’ve encapsulated the act of pulling links from a large HTML string in this
project and you’re welcome to check out the
code if you’re interested.

Now let’s modify our code to extract links from whatever page is provided and print
those links to the screen:

//// file: crawl.go
package main

import (
  "flag"
  "fmt"
  "github.com/jackdanger/collectlinks"  // This is the little library I made for 
  "net/http"                            // parsing links. Go natively allows sourcing
  "os"                                  // Github projects as dependencies. They'll be
)                                       // downloaded to $GOPATH/src/github.com/... on your
                                        // filesystem but you don't have to worry about that.
func main() {
  flag.Parse()

  args := flag.Args()
  fmt.Println(args)
  if len(args) < 1 {
    fmt.Println("Please specify start page")
    os.Exit(1)
  }

  resp, err := http.Get(args[0])
  if err != nil {
    return
  }
  defer resp.Body.Close()
  
  links := collectlinks.All(resp.Body)  // Here we use the collectlinks package

  for _, link := range(links) {  // 'for' + 'range' in Go is like .each in Ruby or
    fmt.Println(link)            // an iterator in many other languages.
  }                              // When we call range() on a list each iteration of the
}                                // contents will set two variables: the index and the value.
                                 // Here we don't care about the index so we set it to '_'
                                 // because if we write 'for index, link := range(links)'
                                 // Go would point out that we left 'index' unused.

If you run this against a simple website this’ll work fine:

go run crawl.go http://6brand.com

But if you try to run it against an https-secured site it may error out because it
can’t validate the SSL cert. We don’t care about security in this toy app so let’s
disable the SSL verification.

//// file: crawl.go
package main

import (
  "crypto/tls"   // we'll import this package to get access to some
  "flag"         // low-level transport customizations
  "fmt"
  "github.com/jackdanger/collectlinks"
  "net/http"
  "os"
)

func main() {
  flag.Parse()

  args := flag.Args()
  fmt.Println(args)
  if len(args) < 1 {
    fmt.Println("Please specify start page")
    os.Exit(1)
  }

  tlsConfig := &tls.Config{                 // The &thing{a: b} syntax is equivalent to
                 InsecureSkipVerify: true,  // new(thing(a: b)) in other languages.
               }                            // It gives you a new 'thing' object (in this
                                            // case a new 'tls.Config' object) and sets the
                                            // 'a' attribute to a value of 'b'.

  transport := &http.Transport{    // And we take that tlsConfig object we instantiated
    TLSClientConfig: tlsConfig,    // and use it as the value for another new object's
  }                                // 'TLSClientConfig' attribute.

  client := http.Client{Transport: transport}  // Go typicaly gives you sane defaults (like 'http.Get')
                                               // and also provides a way to override them.

  resp, err := client.Get(args[0])  // this line is basically the same as before, only
  if err != nil {                   // we're calling 'Get' on a customized client rather
    return                          // than the 'http' package directly.
  }
  defer resp.Body.Close()
  
  links := collectlinks.All(resp.Body)

  for _, link := range(links) {
    fmt.Println(link)
  }
}

Step 4. Concurrency

I’ve asked programming questions that required work similar to what we’re doing here in
programming interviews and the step that candidates need the most help with is building
some kind of queue. If you were to crawl the internet without queueing up the links you
found you’d just visit the top link of every page and rapidly, in a depth-first search
across the whole web, exhaust your resources without ever visiting the second link on
the first page. To avoid that we need to keep some kind of queue where we put links we
find in the back of it and we visit pages that we pull off the front of the queue.

In C# we’d using a ConsumingQueue, in Ruby we’d probably require the stdlib’s Queue,
and in Java we’d use a ConcurrentLinkedQueue or something. Go gives us a great
alternative: a channel. It’s kinda like a lightweight thread that abstracts away some
concurrency primitives for you and functions much like a queue.

We’ll create a channel when we start the program and we’ll put our starting URL into it.
Then we’ll begin to read URLs from the channel and whenever we find new URLs we’ll write
them to the channel, effectively putting them into the back of our queue.

The queue will grow continuously over time because we’re putting things in faster than
we take them out but we just don’t care.

//// file: crawl.go
package main

import (
  "crypto/tls"
  "flag"
  "fmt"
  "github.com/jackdanger/collectlinks"
  "net/http"
  "os"
)

func main() {
  flag.Parse()

  args := flag.Args()
  fmt.Println(args)
  if len(args) < 1 {
    fmt.Println("Please specify start page")
    os.Exit(1)
  }

  queue := make(chan string)         // This gives you a new channel that
                                     // receives and delivers strings. There's nothing
                                     // more you need to do to set it up – it's
                                     // all ready to have data fed into it.

  go func() {            // saying "go someFunction()" means
                         // "run someFunction() asynchronously"
    queue <- args[0]     // This means "put args[0] into the channel".
  }()

  for uri := range queue {     // 'range' is such an effective iterator keyword
                               // that if you ask for the range of a channel it'll
                               // do an efficient, continuous blocking read of
                               // all the channel contents.

    enqueue(uri, queue)  // we pass each URL we find off to be read & enqueued
  }
}

func enqueue(uri string, queue chan string) {
  fmt.Println("fetching", uri)
  tlsConfig := &tls.Config{
    InsecureSkipVerify: true,
  }
  transport := &http.Transport{
    TLSClientConfig: tlsConfig,
  }
  client := http.Client{Transport: transport}
  resp, err := client.Get(uri)
  if err != nil {
    return
  }
  defer resp.Body.Close()

  links := collectlinks.All(resp.Body)

  for _, link := range links {
    go func() { queue <- link }() // We asynchronously enqueue what we've found
  }
}

The flow now is that main has a for loop reading from the channel called queue
and enqueue does the HTTP retrieval and link parsing, putting the discovered
links into the same queue used by main.

If you try running our code so far it’ll work but you’ll immediately discover two
things: The World Wide Web is a messy place full of invalid links and most pages link to
themselves.

So let’s add some sanity to our code.

Step 5. Data sanitization

To properly explore the web let’s turn all of the relative links we find into absolute
links.

package main

import (
  "crypto/tls"
  "flag"
  "fmt"
  "github.com/jackdanger/collectlinks"
  "net/http"
  "net/url"  // We're going to use the standard library
  "os"       // to fix our URLs
)

func main() {
  flag.Parse()

  args := flag.Args()
  fmt.Println(args)
  if len(args) < 1 {
    fmt.Println("Please specify start page")
    os.Exit(1)
  }

  queue := make(chan string)

  go func() { queue <- args[0] }()

  for uri := range queue {
    enqueue(uri, queue)
  }
}

func enqueue(uri string, queue chan string) {
  fmt.Println("fetching", uri)
  transport := &http.Transport{
    TLSClientConfig: &tls.Config{
      InsecureSkipVerify: true,
    },
  }
  client := http.Client{Transport: transport}
  resp, err := client.Get(uri)
  if err != nil {
    return
  }
  defer resp.Body.Close()

  links := collectlinks.All(resp.Body) 

  for _, link := range links {
    absolute := fixUrl(link, uri)      // Don't enqueue the raw thing we find,
                                       // fix it first.
    if uri != "" {                     // We'll set invalid URLs to blank strings
                                       // so let's never send those to the channel. 
      go func() { queue <- absolute }()
    }
  }
}

func fixUrl(href, base string) (string) {  // given a relative link and the page on
  uri, err := url.Parse(href)              // which it's found we can parse them
  if err != nil {                          // both and use the url package's
    return ""                              // ResolveReference function to figure
  }                                        // out where the link really points.
  baseUrl, err := url.Parse(base)          // If it's not a relative link this
  if err != nil {                          // is a no-op.
    return ""
  }
  uri = baseUrl.ResolveReference(uri)
  return uri.String()                      // We work with parsed url objects in this
}                                          // func but we return a plain string.

Now you’re cookin’. This program will now pretty reliably walk around the web
downloading and parsing pages. However, there’s still one thing we lack.

Step 6. Avoiding Loops

Nothing so far prevents us from visiting a page that has one link pointing to itself and
just looping on that single page forever. That’s dumb, let’s not fetch any page more
than once.

The right data structure for keeping track of the presence or absense of things is a
set. Go, like Javascript, doesn’t have a native way of doing sets so we need to use a
map (a.k.a a hash or hashmap or a dictionary) with urls as keys to keep track of which
pages we’ve visited.

package main

import (
  "crypto/tls"
  "flag"
  "fmt"
  "github.com/jackdanger/collectlinks"
  "net/http"
  "net/url"
  "os"
)

                                     // Putting a variable outside a function is Go's
var visited = make(map[string]bool)  // version of a global variable.
                                     // This is a map of string -> bool, so
                                     // visited["hi"] works but visited[6] doesn't.
                                     // Setting a value in a map is a simple as:
                                     //   visited["google.com"] = true
                                     // and reading is equally so:
                                     //   visited["google.com"] 
func main() {
  flag.Parse()

  args := flag.Args()
  fmt.Println(args)
  if len(args) < 1 {
    fmt.Println("Please specify start page")
    os.Exit(1)
  }

  queue := make(chan string)

  go func() { queue <- args[0] }()

  for uri := range queue {
    enqueue(uri, queue)
  }
}

func enqueue(uri string, queue chan string) {
  fmt.Println("fetching", uri)
  visited[uri] = true                        // Record that we're going to visit this page
  transport := &http.Transport{
    TLSClientConfig: &tls.Config{
      InsecureSkipVerify: true,
    },
  }
  client := http.Client{Transport: transport}
  resp, err := client.Get(uri)
  if err != nil {
    return
  }
  defer resp.Body.Close()

  links := collectlinks.All(resp.Body) 

  for _, link := range links {
    absolute := fixUrl(link, uri)
    if uri != "" {
      if !visited[absolute] {          // Don't enqueue a page twice!
        go func() { queue <- absolute }()
      }
    }
  }
}

func fixUrl(href, base string) (string) {
  uri, err := url.Parse(href)
  if err != nil {
    return ""
  }
  baseUrl, err := url.Parse(base)
  if err != nil {
    return ""
  }
  uri = baseUrl.ResolveReference(uri)
  return uri.String()
}

And now you can start at any html page you like and slowly explore the entire world wide
web.

go run crawl.go http://6brand.com

Full source code is available on GitHub as well.

How do you break up a Rails monolith?

2013-12-22T00:00:00-08:00

This was originally posted on Quora.

Part 1: Why a monolith is hard

Number of contributors

Your application probably made a lot of sense when fewer than a dozen developers contributed to it. As your headcount scales so does the desire of individual engineers to work outside the globally-shared assumptions of a single codebase.

Lines of code

Every additional file makes the percentage of the project that an individual engineer understands smaller. We don’t like to work on things we don’t understand, so unless we built the whole thing a large project just feels wrong.

Data growth

If your application assumes that every piece of data can be relationally joined to any other piece of data then you’re limited to storing only as much data as fits on a single hard drive. At the time of writing the very largest, fastest drive you can get is a 6TB drive from Fusion-IO. It is not cheap. Once you outgrow that you have to split your data up into parts and it may be easier to break up your application than teach your application to connect to multiple datastores.

Speed

Any large application will have some helpful code that is commonly-enough used that it becomes part of the framework. This may be that every web request looks up the user’s physical location via geo-ip or decrypts encrypted cookies, etc. When you have a feature that has to be super-fast you’ll wish it were on its own so all of the main app’s assumptions didn’t apply to it.

Upgrading dependencies

In a huge, well-aged app it’s a giant pain to upgrade the dependencies (like moving to a more modern Rails release). Smaller systems can be more easily upgraded as there are fewer lines of code to modify and fewer changes will be made by other engineers concurrently. This is a bit of a lie, however, because a well-designed monolith has dependencies abstracted away such that the upgrading difficulty is the same.

The underlying problem

Behind the above 4 things is the real problem: tech debt scales poorly. You can get away with crappy code when your application is 99% the Rails framework and 1% your code. Once it’s 15-25% your code then you own the bugs and the poor design. And, unless you have no engineers contributing to or users using the application, there’s inertia behind the current poor design.

Part 2: How to break up your monolith

Extract the most important thing

At AirB&B, Yammer, and Square the first parts extracted from the monolith were the high-performance or high-critical parts. Whatever behavior your app has to do fast, correctly, and constantly that is directly related to your competitive advantage as a business is the first thing you extract. This allows you to rebuild this feature properly and it lightens the stress on the monolith. Once you have, say, credit card payments not running straight through your monolith you can breathe a little easier.

Chances are, though, that after this first extraction there is more code in your monolith because now you’re coordinating the data between the two applications. There are still features in the monolith that depend on data in the extracted service (or vice versa) so you have to bridge them somehow. This has not solved your problem.

Extract more things

Especially if data growth is your problem you can probably buy yourself some runway by finding any data that looks or smells like a log of activity and move it out into a proper logging or analytics service. This still doesn’t solve your problem, however.

Build new features in new services

You’ve reached a tipping point when you have the platform support to create a new service for new features rather than having to build the features first in the monolith. This’ll slow the growth of the monolith by giving you an outlet for new development. It’ll also mean that you have a small team dedicated full-time to coordinating services and building synchronous and batch interfaces between them. This has actually made your problem slightly worse.

If you follow this path long enough and with enough engineers you no longer have a monolith. You have several. There’s the old one (now slightly tamed) and probably at least one new one that, if you were publish the source, would cause people to gawk at its size and sprawl.

Part 2 for real: How to actually break up your monolith

You need to design your systems.

When your startup is tiny and your biggest threat is that you’ll shut down before anybody hears of you then you’re just building whatever works. You’re probably writing good code but you are likely not writing good systems. This is okay in the beginning but once you’re surviving and trying to hire many more engineers you’ll need to rethink how you organize everything.

Start with data

The most important thing in your company is your data, not your code. So build a system that caters to the size and shape of your data. If you do financial work does the schema of your database use domain concepts that a CPA would recognize? What secondary datastore will you need to analyze your data (to avoid ruining the schema and scalability of the db where it was created)? Is there a natural way to shard your customers? What parts of your data are derivable from others? What can be eventually consistent and what needs to be consistent at all times?

One mistake I’ve often made is to try to centralize data about a single entity in a single place. In fact, as long as every entity (e.g. a user) has a unique token generated for it then each service and application can and should keep it’s own private data about the entity and communicate to each other using the unique token. You can always generate a complete synthesis of data by pulling information from multiple services. You don’t need to centralize most data any more than you need to centralize most code.

Think about the usage profile of your services

Once you extract your first service you might be stunned to notice that, now that you have users, some parts of your system have orders of magnitude more usage than others. People might be favoriting/sharing things 10,000 times per second but you’re only seeing signups happen 5 times per second. If this is the case then you can optimize the signup code to be friendly to your designers and ensure a development experience there that’s optimized for rapid iteration and A/B testing at the low cost of a few extra servers. And maybe you need to rewrite your favoriting/sharing service in Clojure from the ground up just to eek out every bit of performance.

There will be parts of your system that require speed, others that require ultra-high-availability, and others that are mere test features where the important quality is that you can ship them and scrap them fast. Each of this requires a different application design and, frankly, probably different programming languages.

Get your interfaces right

When all your code is in one app you know that you’re using other code correctly because you’ll get an ArgumentError if you improperly invoke a method or a NoMethodError if you try to call a method with a typo’d name. This doesn’t work across service boundaries.

You have two choices for inter-service communication:</ br>
Write documentation for humans to read and a build a CURL-able API into every services so that they can verify they did things properly. Pray the service and clients never miss an API update.
Use some machine-parseable contract of the API between client and server. Your options here are Thrift, JSON-schema, Google protobuffers, msgpack, capnproto, Blink and probably a few others. These will allow you to ship your API definition to any client and let them validate the schema of any inter-service message before they send it.

Delete everything you can

If you’ve made it this far then you probably have 20+ services and there are diminishing returns to adding any new service – the system isn’t getting any simpler. So the next step in splitting out your monolith into services is bold: delete old features and code. At some point every company needs to carefully review all the features they’ve written to see if they can be deleted or replaced with something simpler. For example, my team recently deleted 16 large, complex files that operated a flaky batch processing job because the service we were sending batch files to had built a better API in the last two years.

Really, anything to lower the amount of code and/or data going through your system (in any service) will mitigate the pain you felt when you started breaking up this monolith.

Part 3: Doing this with a Rails application

First the good news: Ruby on Rails apps have a standardized organizational structure and years of community best practices that help you keep things in place while you grow. This means that a Monorail (Rails monolith) can grow immensely larger than an application in most languages and still continue to function. As long as you have good tests your 200-controller Rails/ActiveRecord app will be far more pleasant to work with than a 200-controller Java/Hibernate app.

Now, the bad news: Ruby has very poor tooling for in-process dependencies. You are allowed to require anything in the load path at any time and circular dependencies are totally normal as long as you’re willing to do some kind of delayed initialization. This means your Monorail’s class-level dependencies would not, if displayed in a graph, be a tree structure – they’d be a cyclic non-directed graph. This pattern is also called the “big ball of mud” software pattern.

So unless you’re SUPER lucky and your developers read Sandi Metz’ book (search for ‘POODR’) they won’t have added explicit ‘require’ statements at the top of source code files and will instead just assume that everything gets loaded into memory all the time.

So your biggest challenge dissecting a Monorail is straightening out the dependencies such that you know what’s referring to what. Once you know that feature X can live in a separate database (or service) and nothing will try to join its SQL queries across feature X’s tables then the extraction is relatively straightforward. But getting there is hard because there’s currently no tool that I know of to analyze the kinds of queries you make in production and develop a dependency graph of models. Please build this and I’ll totally use it.

The Upside-Down Org Chart

2013-12-01T00:00:00-08:00

A corporate organizational chart is drawn as a tree. It’s got a CEO at the root and then splits out to executives and then keeps branching further until you get to the people doing the actual work. Weirdly, this tree is drawn with the root up in the sky and individual contributors (often drawn very small) at the bottom. We use words like “managing up” and “climbing the corporate ladder” and “the decision came from above” as a reflection of this mental image – CEO on top, people on bottom. The up/down contrast is important because in this structure the people on top have more power to make decisions, more interesting labor to perform, and higher compensation. Those at the top communicate commands and desires down to people at the bottom. The top jobs are in every way better.

"Working at BigCo® is so much fun!"
— BigCo® CEO

This structure is very old. It’s basically patriarchy and appears in armies, farms, and governments almost as far back as we have historical records[1]. This structure is traditionally quite static - wherever you start is where you stay. Nobody wants to give up a higher spot to someone else and certainly nobody wants to move down. Napoleon’s Grande Armèe was one of the first organizations to attempt promotion based on merit and not class and we’ve adopted that compromise in modern corporations. But both in the Napoleon’s case and ours “merit” is so vague as to be indistinguishable from class.

I know hundreds of developers who refuse to work at a large company because of this structure. Nobody wants their work to be compromised by constantly having to “manage up” and certainly nobody wants to hand the benefits of their work to somebody else. There’s a saying I keep hearing that goes “Nobody quits their job, they quit their boss.” And there are plenty of bad managers in tech – often a result of “promoting” a veteran engineer to people management as a retention strategy.

Unions try to solve the problem of bad managers and top-down negative pressure by pushing upwards through collective bargaining. Elon Musk famously claimed you don’t need unions if you just fire the assholes. But if you’ve got nice managers exerting negative pressure downwards [2] because of the very structure of the organization, then firing just the jerks won’t save you.

Some companies are experimenting with a flat management structure to solve this problem. GitHub, Stripe and Valve are famously self-organized. Morning Star is a non-tech company that has succeeded with the non-managerial approach as well. The theory is that if there are fewer people above you on the org chart then there is less negative pressure on you and you’ll be able to produce at the same high potential as if you were entirely self-directed. A self-managed company accepts increased chaos and takes a risk of potential non-productivity and in return gets the value of actually highly increased individual productivity. It’s as if every employee were the CEO of their own little company.

Yehuda isn't a fan of the flat-structure approach.

Removing managers rescues us from TPS reports and micro-managing but we still need to form into teams to accomplish anything of note. We can let these teams occur organically but then we suffer from the realities of emergent behavior: Left alone long enough every self-organizing bay area software team will accidentally build a bartending quad-copter running Node. There will never emerge a QuickBooks replacement that’s tax-compliant in all 50 states and Puerto Rico. You’re going to get a product that meets the immediate, bodily-felt needs of its creators because there’s no structure in place to acquire information from customers, verify the accuracy of this information, and provide it in a usable form to the engineers.

There is a solution to bad managers that doesn’t require a flat company structure: good managers. And I don’t mean good people as managers (most bad managers are very friendly); I mean people who believe their job is to empower those they serve and make it easier for the individuals to function as a group. A good manager directs and augments the energies of a team without adding resistance to that energy. A good manager thinks their team is their boss. And a good manager expects the same support from their manager.

To get leaders like this you don’t just need to hire well, you need to reorganize your structure to illustrate the roles. If we want managers to be empowering we need to fix our org charts to be a proper tree: root on bottom, branches above, leaves on top.

This inverted[3] org chart effectively evens out the broken power dynamics of the patriarchal model. The language itself is fixed: “I rely on my manager.” “I support my team.” “Because we’re way up here the CEO needs us to tell them what we see.” “I’m not sure I want to take on the weight of another team – that’s a lot to support.”

There are no "promotions" here; you can move to positions with less organizational responsibility and more task responsibility or vice versa.

This also helps us fix compensation because if there’s a sense that someone near the root is actually holding up more of the company (and the people they serve feel that support) then it doesn’t feel unjust to pay them more.

For a tech company to describe their structure this way requires some humility from the leadership. It requires accepting that senior positions must be evaluated based on the support given to individuals on the team rather than the support given to the CEO or executives. But it makes the structure one in which nothing is extracted from the laborers – indeed it provides help that an individual could not find working alone.

If you want an engineer to work as slowly and sadly as possible, place them at a BigCo® where all the power is top-down (CEO-down) and tell them what to do. If you want them to produce something amazing, then place them in a team of people with all the resources of a supporting manager, a supporting corporate team, and total freedom to do their best work in the way they best see fit. You need only communicate the needs of the end customer clearly and then the work will get done.

Links:

^ Patriarchy only goes back about 3,000 years and seems to have originated as a survival mechanism during times of trouble. http://en.wikipedia.org/wiki/Patriarchy#cite_ref-18
^ This study asked 3 people to write a paper and put one person nominally in charge. When the group was given 5 cookies the ‘boss’ would eat 2 cookies, not just 1, and would typically do it sloppily with their mouth open and getting crumbs on their shirt: http://psycnet.apa.org/journals/rev/110/2/265/. So the very nature of ‘boss’ causes good people to have a negative effect on those they boss.
^ Let’s be real, this isn’t a new idea. It’s ancient, well-loved, and just very rarely used in human organizations. Or, if you prefer, http://silentvoicesbible.com/voices/42-luke-022.html#026

Skinny Models – the DAO pattern for Ruby persistence

2013-07-20T00:00:00-07:00

For those used to ActiveRecord-style
development the following might not seem all that bad:

class User < ActiveRecord::Base
  belongs_to :account
  has_many   :posts

  validates_format_of :email, :with => /@/

  after_create :deliver_welcome_email
  after_create :mark_pending

  private

  def mark_pending
    update_attributes! :state => 'pending'
  end

  def deliver_welcome_email
    ApplicationMailer.deliver :welcome_email, email
  end
end

If you’ve read Sandi Metz’ book (or have an OO
background) you’ll notice something about this conventional Rails code.
Not only is it a huge mess of dependencies, it violates damn near every
part of
[SOLID](http://en.wikipedia.org/wiki/SOLID_(object-oriented_design)
object-oriented design that we practice as a means of keeping our code
nimble.

So what’s the alternative?. The Data Access
Object pattern uses an
object to manage persistence and doesn’t let that object do anything
else. Effectively, it makes the above class look like this:

class User < ActiveRecord::Base
  belongs_to :account
  has_many :posts
end

Or, if you want to get religious:

class User < ActiveRecord::Base
end

(Personally, I think associations are the thing ActiveRecord does right
so I’m fine leaving those in.)

We just took a lot of code out of the User class and it has to go
somewhere else. Where? Well, that depends on what it does. Consider this
reorganization:

class User < ActiveRecord::Base
  belongs_to :account
  has_many :posts
end

module Validator
  class Invalid < StandardError; end
                                   
  def self.validate!(record)
    unless record.email =~ /@/   
      raise Invalid
    end
  end
end

module Email
  def self.welcome(email)
    ## Handle email delivery
  end
end

class StateMachine

  attr_reader :record
  def initialize(record)  # I'm making the StateMachine instantiable because
    @record = record      # the 'record' object feels like internal state and
  end                     # there may be actions we want to perform on that
                          # object during a state transition
  def pending!
    record.state = 'pending'
    record.save!
  end
end

module Signup
                                   # You now have to use this to tell Signup
  def self.persistence=(db_model)  # what object is in charge of database
    @persistence = db_model        # persistence. This is where you pass in
  end                              # your DAO or, in tests, your stub object
                                 
  def self.complete! data              # I'm not bothering to make Signup an instantiable
    record = @persistence.new(data)    # class at this point because we don't need it yet.
    Validator.validate! record
    record.save!
    StateMachine.new(record).pending!
    Email.welcome data[:email]
  end
end

We now have many more lines of code and many more objects so it might
look like we just added complexity but in fact we’ve reduced it. If
complexity is the entanglement of concepts, then we’ve removed nearly all
complexity from this application. Let’s walk through the changes bit by bit.

Removing callbacks

We turned a couple after_create callbacks into
direct code execution. You now know exactly when the email address will
be validated and when the welcome message will be sent. You also know
how to stub out the objects that perform those functions in your tests.

Introducing a proper state machine

This is my favorite. There’s a Rails application at work that
moves a lot of money around and needs to handle many intermediate states
with very precise rules about when things are purchased, paid for,
approved, rejected, returned, refunded, etc. If we were to try to
implement this logic inside an ActiveRecord class we’d be fighting
against the weight of Rails every time we extended the state graph.

Most Rails applications I’ve worked on have eventually had some kind of
state machine in them. I’ve tried acts_as_state_machine, two gems both
called state_machine and I’ve built several terrible and bug-prone
versions myself. Nothing has worked as well as pulling all the logic out
into a new class and being very explicit about what kind of state
transitions your application allows. You’ll notice the interface to the
persistence object is only two methods large. As long as the object you
pass in responds to state= and save! the StateMachine class will
work. Which means you do NOT need to pass in an ActiveRecord instance in
your tests – any simple mock will do.

Adding sane validations

Two months ago I was in the middle of a Rails2->Rails3 upgrade and I
found myself in a pry console staring at the insides of a
validates_each block deep inside Rails. For trivial validations and/or
trivial applications the Rails way of adding data validation is just
fine. But when you write the validations yourself you get all the
following benefits:

test your validations without simultaneously testing that
ActiveRecord#save still works
test the edge cases of your validations because you actually control
how they’re defined and when they fire
easily debug your validations because you implemented them in a
well-factored class
write hundreds of validation tests if you want because they’ll all run in
less than a second.

Separating application-level features from database objects

The conventional path would have you type User.create! params[:user]
in your controller. This is only good if you’re certain that creating
a new User record is the action you’re trying to complete. But more
likely what you want is to complete a user signup. So
Signup.complete! params[:user] is much more descriptive of what you
want. Maybe you want to create a User record. Maybe you want to create a
Business record. Maybe it’s such an important action that you’ll be
generating Account, Business, User, and Product records all at
once. By keeping the controller-level semantics high-level you won’t
have to change them to keep up with an evolving implementation.

And then your tests go zoom

This post isn’t called ‘how to make your Rails tests faster’ but it
might as well be. The reason your tests are slow is ActiveRecord and
ActionController. Your code (and Ruby) is actually blazing fast but
it’s organized in such a way that you have to test each object’s
dependencies if you want to test the object itself.

The tests

Let’s take a look at what these tests would look like before and after
the above reorganization. First, the conventional Rails way:

## file:spec/models/user_spec.rb
require 'config/environment'  # This loads all of Rails and autoloads
describe User do              # every object automatically
  describe 'creating' do
    subject { User.create! params }
    let(:email) { 'm@rvelo.us' }
    let(:name)  { 'Marvelous'  }
    let(:params) { {
      email: email,
      name:  name
    } }
    context "with invalid email" do
      let(:email) { 'whoops' }
      it "doesn't create a new record" do
        expect { subject }.to_not change { User.count }
      end
    end
    context "with valid params" do
      it "creates a new record" do
        expect { subject }.to change { User.count }.by(1)
      end
      it "sends a welcome email" do
        ActionMailer.should_receive(:deliver).with(:welcome, email)
        subject
      end
      it "sets the 'state' column to 'pending'" do
        subject
        User.last.state.should == 'pending'
      end
    end
  end
end

That’s a respectable spec. It’s reasonably clean, tests most of the
important stuff, and doesn’t go off track testing unnecessary edge cases
or the implementation of the code (other than the ActionMailer bit).

However, every example in that snippet booted all of ActiveRecord and
tested the full forest of callbacks, validations, database connection
mechanisms, and relational associations inside ActiveRecord. Rails has
its own tests so there’s no point in me or you re-testing the Rails
internals. That just turns our app into a Seti@Home that’s guaranteed
not to find anything.

Let’s rewrite that to test only what we care about.

## file:spec/unit/services/signup_spec.rb
require 'app/services/signup'  # We only require the thing we care about
                               # and we trust that _it_ will require any
                               # require any dependencies that it needs.
module FakeDAO
  require 'ostruct'               # We don't want to go saving to the actual
  def self.instance               # database all the time, we'll just assume that
    @instance ||= OpenStruct.new  # ActiveRecord still works.
  end

  def self.new(attrs)
    attrs.each do |k,v|
      instance.send "#{k}=", v
    end
    instance.send "save!=", true
    instance
  end
end

describe Signup do

  before { Signup.persistence = FakeDAO } # This is where we inject the dependency
  subject { Signup.complete! data }

  let(:email) { 'm@rvelo.us' }
  let(:name)  { 'Marvelous'  }
  let(:data) { {
    email: email,
    name:  name
  } }

  context "with invalid email" do
    let(:email) { 'whoops' }
    it "doesn't create a new record" do
      expect { subject }.to raise_error(Validator::Invalid)
    end
  end
  context "with valid data" do
    it "creates a new record" do
      FakeDAO.instance.should_receive(:save!).at_least(1).times
      subject
    end
    it "sends a welcome email" do
      Email.should_receive(:welcome).with(email)
      subject
    end
    it "sets the 'state' column to 'pending'" do
      subject
      FakeDAO.instance.state.should == 'pending'
    end
  end
end

That’s about the same size code as the previous example but it runs in
less than a hundredth of a millisecond. It also explicitly tests only
Signup – the object under test.

We then get to add individual tests for the other components we’ve
extracted. Each of those will be focused and obvious.

You’re stubbing things. What if a bug slips through the cracks?

It’s only okay to stub the dependencies of an object if two conditions
hold: You’re stubbing in such a way that you’re unlikely to change the
core behavior of the object under test and you still have high-level
integration tests that test the whole suite.

So if you’re reasonably sane about what you choose to stub and you still
write a basic high-level test that only tests for the primary cases (not
edge cases) you can get away with this approach.

We’ve had enough success with this pattern at work that
Xavier added the following to our
spec/unit_helper.rb:

RSpec.configure do |config|
  config.before(:suite) do
    if Object.const_defined?("Rails") || Object.const_defined?("ActiveRecord")
      raise "The Rails environment should not be loaded for unit tests."
    end
  end
end

That’s right, we throw an error if you’ve required any part of Rails in
your code. This enforces that you’ve written loosely-coupled,
dependency-injected, DAO-style persistence-oriented classes whether you
are familiar with those terms or not. I can’t recommend this snippet of
code highly enough.

Electricity: the parts I couldn't understand

2013-05-18T00:00:00-07:00

I want to make robots. Not just a simulation running on a computer but
real-life Actual® Stuff® with moving parts. The problem is that I’m a
software engineer and hardware has a steep learning curve. One of the
biggest surprises is that apparently I never understood electricity at
all.

Sometimes it’s helpful to learn from a person who’s just one step ahead of you
rather than a veteran. To that end I’ll do my best to explain a few concepts
that didn’t make sense to me when taught the traditional way and what I’ve
learned as a total amateur. I want to write this all down before I forget what
was so hard about it.

Current

Electrons flow from negatively-charged stuff to positively-charged
stuff. Electricity is the flow of electrons in a current. Sure, thanks.
Let’s rephrase it: stuff that has too many electrons pushes those
electrons away toward stuff with too few electrons. There’s going to be
‘current’ as those electrons get pushed away.

Here’s what I wish I’d somebody had mentioned to me: Electrical diagrams are all written backwards

They describe current flowing from positive to negative (red to
black). Even though electrons are going in the opposite direction. This
has confused me. Badly. I once exploded a car battery in high school
because I knew enough chemistry to understand electron flow but didn’t
know that ‘ground’ meant ‘where the electrons come from’. Ever since
then I’ve struggled to get this straight. Here’s how I now think of it:
electrical current is like the wave of movement in a traffic jam. The
cars are all pointing forward but that’s not the direction of the
current. Whenever the front-most car sees a gap it moves forward, then
the one behind it takes its place, etc. From an outside observer it
appears that there is a wave of open space moving backward. The
electrons are the cars, the wave is the ‘current’.

So if you see an arrow on a circuit diagram it represents the wave
moving backwards on a freeway – not the cars themselves.

Circuits

A circuit is a loop in which electrons can flow. They won’t move
unless you connect a power source to the circuit because the whole point of a
power source is to continuously push too many electrons into a circuit so they
all have to move.

Resistance

One of the most basic ways to modify an electrical circuit is to add resistance
to one part. Here it helps to think of a water pipe that is narrow in the
middle. The water will be able to move fast or slow depending on how much
resistance it feels traveling through the middle. There’ll be higher water
pressure one whichever side the water is coming from but the water will always
move at the same speed on both ends of the pipe. The pressure is irrelevant –
the more you constrain the middle the slower the whole pipe will be able to
move water. It’s like this with an electrical circuit. If you add a resistor
to one part the whole circuit will appear to slow down. You can plug
in a lightbulb to the circuit on either side of the resistor and it will
receive the same (diminished, thanks to the resistor) current. So a resistor
doesn’t just resist current at the point where it’s installed –
it slows the whole circuit down.

Induction

Induction is where magnetism connects one flow of electricity to another.
Induction is useful when you have two circuits that you don’t want physically
touching but you need the current in one to affect the other. Induction motors
work this way; you provide current to the fixed part of the motor and that
current (sharing a magnetic field with the rotating part of the motor) controls
the rotation. The principle behind this is that an inductor resists changes in
current. Said another way: It’s hard to increase the current of a circuit that
contains a inductor and it’s also hard to decrease it afterward. This
resistance to change comes from a sort of magnetic turbulence in the inductor
whenever the current isn’t steady.

Capacitance

A capacitor is basically just a really short-term battery.
Electrons pile up on one side of a capacitor and they’re much-needed on the
other side – but they can’t cross because there’s a small gap. When a
connection is made across the gap then the electrons all flow instantly from
one side to the other (and through the rest of the circuit). This is how camera
flashes work – they store up electricity for a few seconds and then let it all
out at once. Note: I do not understand how capacitors are discharged. There
are two terminals on a capacitor that you can hook up to your circuit but how
do you trigger the discharge? If somebody can explain that to me I’ll update
this page.

I could write about LEDs, motors, batteries, etc. but those all roughly made
sense when I tried studying them. It’s the foundational stuff that confused me
and I hope my perspective on these concepts might help you out too.

The King Cannot Be Removed From the Board

2013-05-05T00:00:00-07:00

My grandmother taught me to play chess
with a special set of pieces that had their
names printed on them. If you picked them up they had words on
the bottom that described their legal moves. “Bishop: can go diagonally
as far as he wants”, “Knight: can go over 2 and diagonally 1, or over 1
and diagonally 2”
Most of the rules were simple and just required memorization to retain
but one rule confused me: The King cannot be removed from the board.

I asked my grandmother what happens when
the king is captured. “The King cannot be captured”. No, see, I can
capture him with even a pawn if it’s
in the right position. “No, you can be about to capture him, but the
game ends right before you do.”

This seemed pretty weird to me. Why not let the king be captured and
immediately after call the game for the winner? Why stop one step
before?

The best book I’ve read on domestic violence is Why does he do
that?.
It breaks apart so many myths about domestic abusers: That they’re
always physically violent, that they can’t control their emotions, that
they’re crazy, that the woman “just needs to leave him”, and many more.
Most of all this book on the psychology of abusers reveals the nature of
patriarchy. Patriarchy is not a system that prefers men to women, it’s a
system designed to meet the needs of specific men at the expense of
the needs of all other men, women, boys, and girls. These men are always
at the top of a clear hierarchy. It’s the father in a family, the CEO in
a company, the king in a nation, the pastor in a church. Other people
can have their needs met – but only after his are satisfied.

Many pieces on a chess board are important. Sure, the pawns are
obviously worthless but the bishops and rooks get to throw their weight
around. Even more, the most powerful piece is the queen! Surely this
game is progressive if the female character can do whatever she likes in
whatever direction. But in testing a social system it’s not enough to
ask “who has power?” You have to go one step further and ask “whose
needs are being served?” Is the queen powerful? Oh yes. When she dies
does the game continue uninterrupted? Yes, in fact most end-game
scenarios assume she’s gone. But not so with the king. When the king is
about to be captured the rules suddenly change.

One common habit of an abuser is that when they are threatened they
manage to change the rules of the game. When the woman has a bad day she
has to deal with it. But when he has a bad day it’s the whole house’s
problem to fix it. When she gets injured the vacation still continues as
planned but when he sprains an ankle the whole world gets rearranged to
deal with his new situation. An abuser will even attempt to change
reality itself to suit his needs. If he’s winning an argument against
his woman but then she is able to score a point then he can switch
positions in the argument and try to make the woman think she’s stupid
and crazy if she notices the change.

When the king is threatened on a chess board the rules change. Suddenly
the fighting isn’t worth it anymore and a new strategy appears. The king
cannot be captured in a struggle for the kingdom because the purpose of
the kingdom is to support the king. This is what I didn’t understand
when my grandmother taught me the game. I didn’t get that the king isn’t
just a piece; the king is the game. The game is played through the eyes
of the king pieces.

This same pattern exists in
every Hollywood movie and most TV shows. When the action moves away
from the man the camera does not follow. When the man is removed from
the story the story ends. When a chess king knows that he has lost then
the game ends. You must stop playing because his role is finished
and he sees no point in letting you continue the script.

I’m glad my grandmother taught me this game (and bought me such
beginner-friendly pieces). But I wish she’d helped me to better
understand the pattern encoded inside the rules. She’s also the one who
introduced me to James Bond films and she set the expectations perfectly
for that: She told me “They’re just movies about sex and death but boy
are they fun.” One day if I have the privilege of teaching a child or
grandchild the ancient game of chess I’ll jump at the chance but I’ll
clarify the rules a bit. I’ll say “This game has one character that
doesn’t pull his weight. The King pretends to be weak and makes
everybody else do his work for him. Some people do this in real life and
you should watch out for them. And don’t be like this yourself or you’ll
hurt people. Okay, you’re white so you go first.”

Calculating Factorials in Ruby

2013-01-20T00:00:00-08:00

The factorial of a number is itself multiplied by itself-1 multiplied
by itself-2, etc. all the way down until you multiply it by 1. By then
it’s a giant number. In mathematics the denotation for this would be
n! or, if n were 12, 12!.

But there’s no way in Ruby to make this mathy syntax work:

  12!  # that's "twelve factorial"

This is because the ! operator (pronounced “bang operator”) is picked up by
the parser and merely negates the next term. If you type the above into
IRB you’ll find that your REPL hangs because it’s waiting for more
input.

One way to calculate a factorial in Ruby is the following

total = 1
12.downto(1) { |n| total *= n }

That’ll give you the correct answer (479,001,600). But… gross. There’s
a local variable defined outside the block unnecessarily. A cleaner way
would be:

12.downto(1).reduce(:*)

That gives the same answer. Let’s unpack that a bit. The 12.downto(1)
would normally be something you’d give a block to, like in the first
example. But in this case we’re not passing a block, we’re calling
.reduce on the return value of .downto.

This works because downto returns an
Enumerator
instance. This is something that you can perform virtually any
Enumerable method on. In this case we’ll call reduce.

If you’re not familiar with reduce, it’s the latter half of the
famous “map/reduce” pair. A reduce function is given to each element in a
list in turn and keeps track of the result from the previous time it was
run. It might be a little clearer to see an example:

reduce = lambda {|last_result, element|  # Here we're creating a lambda (think "function")
  last_result = last_result + element    # that is named reduce that takes a thing and
}                                        # a new thing and adds them.

elements = [1,2,3]                       # Here's a collection that we can reduce.

                                         # We start with an initial value. This is because
                                         # the reduce function's first argument is the result
result = 0                               # of the previous call and to begin with 
                                         # that value needs to be created by hand.

elements.each {|element|                 # Now we call the reduce function we created
  result = reduce.call(result, element)  # once for each element.  Importantly: we remember
}                                        # the result each time and feed it back in
                                         # When we're done the `result` has the value we want
result ## => 6

This is a useful pattern because it allows us to separate our data from
the functions we perform on it. Check out how easy it is to make the
above code work on a list of strings instead of numbers:

elements = ["fee", "fi", "fo"]          # Strings also respond to the '+' method

result = ""                             # We have to initialize the result differently
                                        # now that we are using strings.

elements.each {|element|                # Everything else is the same!
  result = reduce.call(result, element)
}

result ## => "feefifo"

There are still a couple clunky bits here, however. We have to
initialize the result each time and we are doing a fair bit of plumbing
still. Luckily, all good reduce methods smooth out these rough edges.
Here’s the API to the reduce method as implemented in Ruby’s
Enumerable module:

(5..10).reduce(:+)  #=> 45                    # Sum some numbers
(5..10).inject {|sum, n| sum + n }            # Same using a block and inject
(5..10).reduce(1, :*)                         # Multiply some numbers
(5..10).inject(1) {|t, n| t*n }               # Same using a block
%w{ cat sheep bear }.inject do |memo,word|    # find the longest word
   memo.length > word.length ? memo : word
end  ##=> "sheep"

The reduce method is aliased to inject in Ruby so you may
have already used it in your own code.

So the reason this factorial snippet works is that reduce is smart
enough to take the first value from the list if you didn’t give it an
initial value. It’s also smart enough to infer if you give it a proc
object (which is what :* is here — (:*).to_proc == {|a,b| a * b })

Graph Traversal: solving the 8-puzzle with basic A.I.

2013-01-02T00:00:00-08:00

I’ve been working through Peter Norvig and Stuart Russel’s Artificial
Intelligence, A Modern
Approach (thanks to the Square engineering library) and one of the most helpful chapters involved methodically demonstrating basic graph traversal algorithms for problem solving. If that sounds heady, it’s not — I think you’ll enjoy it.

First,
let’s talk about graphs. A graph is any set of points (nodes) and the
lines (edges) between those points. A simple kind of graph is a tree
structure. This is where there’s a single ‘root’ which has 1 or more
branches that then have their own branches, etc. Many things in computer
science can be expressed using some kind of tree structure graph.

Here’s how this relates to AI: the root node (the one at the top of
the tree) is the state the world is in right now. Each other node
represents a different state of the world that’s reachable across an
edge by the node immediately above it. The line between them is some
kind of action. Moving a car’s wheels, turning on a servo, whatever. The
A.I. just needs to know that if you start at node A and do action X
you’ll get to node B. Your software will appear to be intelligent if it
can start at the root node and find its way to a better state of the
world through a series of actions.

A world where you try to get a big number

Let’s reuse the above image as an example. Imagine it’s a complete map
of all possible states of the world. The only actions that are
available to you are “go left” and “go right” (‘cause you’re always
starting at the root (top) node and heading downward). Imagine,
additionally, that the value of the number of a node is how much we like
that node. From a glance you can easily tell that one of the nodes has a
value of 11 and is therefore the “best” node in the graph; it’s the
“best” state of the world that we could possibly get to. If our software
is intelligent it should start at the root node and find the 11 node
as it’s destination.

Since we can easily see where the 11 node is the right answer is “go
left, then right, then right again.” But how do we teach our code to
find the best node?

Recursive Depth-first search

Here’s the simplest way we can find the right node on the given tree.

best = nil
def walk(node)
  best = node if best.nil? || node > best
  node.children.each {|child| walk child }
end
walk root

Here we “walk” down each branch of the tree all the way to the end using
recursion. This is known as recursive depth first search and is a great
tool when you think that any path might have a good node really far down
so you just want to get really deep really fast. It’s also the least
code possible to find a solution to our problem. Unfortunately, the
simple implementation of depth-first involves recursion which means
we’re limited to only traversing graphs that have a total depth less
than our runtime stack frame limit. If you’ve ever seen a “stack
overflow error” it’s because there was so much recursion in your program
that the computer assumed you were caught in an infinite loop and gave
up. To demonstrate this try running this simple program in irb:

def go(n)    # On my machine the last thing printed was 8247 and then I saw:
  puts n     #   SystemStackError: stack level too deep
  go n + 1   # which means Ruby let me use 8,247 stack frames
end          # before giving up. If I were to try going 9,000 nodes deep
go 0         # in a graph I'd get this error.

Now, if you wanted to do a depth-first search without recursion you can
but it’s no longer the simplest code so I’ll skip it here. Suffice to
say that it would mean you’ll have to manually keep track of which nodes
to visit in which order rather than letting your programming language do
it for you.

Breadth-first search in a loop

Another simple way to traverse the graph is to look at the nodes from
left to right on each level rather than going all the way down one
branch and then all the way down another branch. This is called
breadth-first search and is
better if you think there’s a good node close to the root.

This is also a very simple bit of code and it frees us
from having to rely on our runtime’s call stack. Rather than recursing
through methods and letting Ruby keep track of our work (as in the above
example) we’ll just run in a loop and store our work in an array. The
advantage here is you can put more than 9,000 items in an array —
it’s only bounded by how much memory is on your machine.

queue = [root]
best = -1
begin
  current = queue.shift
  best = [current, best].max
  current.children.each {|child| queue.push child }
end until queue.empty?

The name “breadth-first” comes from the fact that it’ll look at all the
nodes at each level from side to side before proceeding down to the next
level. Notice that the array variable is named queue. This is because
in a depth-first implementation you’re always going to have a list that
you put newly-discovered nodes onto the end of and pull nodes to explore
off of the front.

Breadth-first search is easy to reason about, you won’t run out of stack
space like when you used recursion (although it’s possible you’ll run
out of memory), and if your environment supports concurrency primitives
you might be able to run it in parallel quite easily. C# has a Consumer Queue that can help with this and Clojure has multiple ways to iterate
through a list in parallel. Ruby requires you to do more work
synchronizing when threads get to append their newly-discovered nodes to
the end of the queue but otherwise you get the parallelism cheaply.

Solving the sliding-block puzzle

We walk
along the edges of a graph from the starting node to a better
node. With me so far? If this graph represents a set of world states
that are reachable from each other via actions then searching the graph
is the same thing as figuring out what to do.

Let’s use this technique to try to solve a problem that has a clear
starting state and a clear ending state with many (possibly very many)
intermediate states. The sliding-block puzzle (often called an 8-puzzle
or, in it’s larger variant, a 15-puzzle) is a great case for us to
tackle.

In an 8-puzzle you’ve got a bunch of tiles in the wrong places and just
one empty space that you can move around until the tiles are in the
right order. How do you know which move to make first? How do you know
when you’re on the right track? How do you know if you’ve going in
loops?

If we model each possible action as edges in a graph and each potential puzzle
state as a node then we just start at the beginning and begin exploring
the graph. We’ll stop once we’ve found the solution (or, if we built our
code poorly, we’ll stop when we run out of memory or time).

Now, there are two ways we can set up our data for this problem. One is
to generate all possible states (nodes) that the puzzle can have and to
then connect the adjacent states. We would then have a complete graph we
could traverse and we’d even be able to mark the solution ahead of time
and know where it was located in the graph. Unfortunately, the number of
states is 9-factorial or about 360,000. Generating that many puzzle
slide orientations and then iterating through each one would take, at
best, (9!)(9!-1)/2 node-comparison operations (the formula for how
many edges can exist between nodes in a graph is (n * n-1)/2)

So let’s not do that. Rather, let’s start at the root node (the starting
state) and then create branches from each node as we go. We’ll stop
when we discover our solution — hopefully long before we examine 360,000
states.

Defining a puzzle class

We’re going to need a few tools. First, let’s put together a way to
represent a puzzle board with tiles in a particular position:

class Puzzle
  Solution = [0, 1, 2,              # Let's put all the tiles in ascending order
              3, 4, 5,              # the same way you'd see them on a phone keypad.
              6, 7, 8]              # We use a '0' for the blank cell because
                                    # `nil` doesn't play well with others.
  attr_reader :cells
  def initialize cells
    @cells = cells
  end

  def solution?
    Solution == @cells
  end
end

What did we just do there? That is a Puzzle class where each instance
knows whether it’s a solution. The cells/tiles of the puzzle are kept in
a list.

Now let’s construct a way to represent a state (a node on the
solution graph). A state isn’t just a representation of puzzle tile
position but also the history of how that puzzle arrangement was
reached from the starting point. This is key: if we don’t keep track of
how we got to a solution node on the graph then we’ll never be able to
report how to solve the puzzle. So we need to keep a list as we go of
which actions we’ve taken to arrive at the current node.

class Puzzle                                          # We're extending the Puzzle class.
  def zero_position                                   # `zero_position` tells us which cell has
    @cells.index(0)                # the '0'.
  end

  def swap swap_index                                 # `swap` tells the puzzle:
    new_cells = @cells.clone                          # "give me you, but with the '0' cell
    new_cells[zero_position] = new_cells[swap_index]  # replaced by the cell at some other
    new_cells[swap_index] = 0                         # location of my choice."
    Puzzle.new new_cells                              # This is how we'll simulate moving a tile.
  end
end

class State                                           # Each `State` instance represents a node
  Directions = [:left, :right, :up, :down]            # in our solution graph. It keeps track of
                                                      # both a puzzle and the list of actions
                                                      # required to arrive at there from the
  attr_reader :puzzle, :path                          # starting node.
  def initialize puzzle, path = []                     
    @puzzle, @path = puzzle, path                     # The `path` is a list of actions
  end                                                 # like 'up', 'down', 'right', right'

  def solution?                                       # Each node in our graph should
    puzzle.solution?                                  # know if it's a solution.
  end

  def branches                                        # Returns all adjacent possible states
    Directions.map do |dir|                           # including steps needed to get there.
      branch_toward dir                               # Most nodes will have 2-4 branches based
    end.compact.shuffle                               # on how many directions the blank tile
  end                                                 # can try to go.

  private

  def branch_toward direction
    blank_position = puzzle.zero_position
    blankx = blank_position % 3
    blanky = (blank_position / 3).to_i
    cell = case direction                      # The only reason this method is so long
    when :left                                 # is because sometimes the blank tile is already
      blank_position - 1 unless 0 == blankx    # at a wall and that direction isn't possible
    when :right
      blank_position + 1 unless 2 == blankx
    when :up
      blank_position - 3 unless 0 == blanky
    when :down
      blank_position + 3 unless 2 == blanky
    end
    State.new puzzle.swap(cell), @path + [direction] if cell
  end
end

This State class knows about one particular arrangement of the puzzle
and is able to determine next steps. When we call State#branches we get
a list of adjacent puzzle arrangements (anything reachable by moving the
empty space over by 1 square) and each of these new states include the
full list of steps necessary to reach them.

That’s the setup. Now that we have some problem-specific helpers we can
use our breadth-first algorithm from up above to start tackling this.

def search state
  state.branches.reject do |branch|        # Important: don't revisit puzzles
    @visited.include? branch.puzzle.cells  # you've already seen!
  end.each do |branch|                     # The list of places we need to search
    @frontier << branch                    # is known as the 'frontier'
  end
end

require 'set'                           # We'll remember what we've seen in a set, it has
def solve puzzle                        # way better lookup times than an array.
  @visited = Set.new
  @frontier = []
  state = State.new puzzle
  loop {
    @visited << state.puzzle.cells
    break if state.solution?            # This is the `base` or end condition
    search state
    state = @frontier.shift             # Pull another off the list, keep chugging along
  }
  state
end

If we feed in a solveable puzzle we can see that this code works. Let’s
try one where the empty tile was moved right and then down. The solution
should be to move it up and then left:

p solve(Puzzle.new [1, 4, 2,         # `solve` is going to return a State
                    3, 0, 5,         # instance. We care about it's #path
                    6, 7, 8]).path
## => [:up, :left]

So… it works, but it’s just kinda wandering around until it finds a
solution. We gave it a problem that was only 2 steps from a solution so
if we gave it something harder would it ever finish? And how long would the
solution path be?

Here’s our code running with a puzzle who’s optimal solution is 20 steps
away:

p solve(Puzzle.new [7, 6, 2,       # I generated this by creating a solution state and
                    5, 3, 1,       # running `state = state.branches.sample` in a big loop.
                    0, 4, 8]).path
## => [:up, :up, :right, :down, :right, :down, :left, :left,
##     :up, :up, :right, :down, :down, :right, :up, :left,
##     :down, :left, :up, :up]
## Time: 27 seconds

It works! Eventually. But 27 seconds is a bit slow. What if we were
tackling the 15-puzzle instead? Rather than the 9! (360K) options we
would be searching through 16! (20 trillion) options. That would take
almost literally forever.

Uniform-cost search

As we walk the graph we’re keeping a frontier — a list of states
we’re hoping to explore in the future. Since we always add to the back
of the list and take (shift) from the front it’s technically a FIFO queue rather than just a list.

What if, rather than picking the next element from the queue to explore
we tried to pick the best one? Then we wouldn’t have to explore quite
so many trillions of nodes in our state graph.

Uniform-cost search entails keeping track of the how far any given node
is from the root node and using that as its cost. For our puzzle
example that means that however many steps n it takes to get to state
s then s has a cost of n. In code: s.cost = steps_to_reach_from_start(s). A variant of this is called Dijkstra’s
Algorithm.

There’s one missing piece here though: we don’t want to examine every
item in the entire frontier queue every time we want to pick the
next lowest-cost element. What we need is a priority queue that
automatically sorts its members by some value so looking up an element
by cost is cheap and doesn’t slow down the rest of what we’re trying to
do.

class PriorityQueue            # This is a terrible implementation of a
  def initialize &comparator   # priority queue. The `#sort!` method iterates
    @comparator = comparator   # through every item every time.
    @elements = []             # What you want is a priority queue backed by a heap data structure.
  end                          # In Ruby you should use the `PriorityQueue` gem
                               # and on the JVM there's a good Java implementation.
  def << element
    @elements << element
    sort!
  end

  def pop                      # `pop` is the typical queue-polling nomenclature.
    @elements.shift            # Your implementation may call it something else.
  end

  private

  def sort!
    @elements = @elements.sort_by &@comparator  # This line is why this implementation 
                                                # sucks. Don't use this IRL.
  end
end

class State
  def cost                           # The cost is pretty simple to calculate here.
    path.size                        # The path contains all the steps, in order that we
  end                                # used to arrive at this state. So the cost
end                                  # is just the number of steps.

require 'set'
def solve puzzle
  @visited = Set.new
  @frontier = PriorityQueue.new {|s| s.cost }
  state = State.new puzzle
  loop {
    @visited << state.puzzle.cells
    break if state.solution?
    search state
    state = @frontier.pop
  }
  state
end

Sidebar: you may be wondering why this gains us any advantage? Sure,
we’re now picking the the best node from the queue rather than whichever
one was added first but we still have to explore all of them, right?
Actually, no. Because we’re sorting by the ‘cost’ of the nodes we can be
guaranteed that whenever we find a solution it’s the best one. There
may be other paths to solutions in our graph but they are all guaranteed
to be of higher cost. So this Uniform-cost search lets us leave a vast
section of the queue unexplored.

What does that do to our performance? Well, if we re-run our above
20-step puzzle the time will drop considerably from 27 seconds to 10
seconds (on my machine).

This is a big speedup and, for larger problems, can shave days off the
calculation time. But there’s much more we can do.

A* Search

The uniform-cost search picks the best next state from the frontier.
Let’s enhance the code’s understanding of what makes something
“best” by calculating not only the distance from the start to where we
are but the distance from where we are to the goal.

Old cost function: steps_to_get_to(s)

New cost function: steps_to_get_to(s) + steps_to_goal_from(s)

But, uh, how do we know how far we are from the solution? If we knew how
far away the solution was we’d probably already have found it, right?
Right. So rather than being exact, let’s just pick a healthy estimate of
how far we are from a solution. One approximation would be “how many
tiles are out of place?” That would at least differentiate
almost-solution nodes from not-even-close ones. But we’d like to be a
bit more precise.

So let’s say that the distance cost between a given node and the
solution node is the number of tile-movements that would be required if
tiles could move through each other and go straight to their goal
positions. So a near-solution node might have a distance cost of 3 and a
not-even-close node might have a distance cost of 26. That should give
us decent precision while also being fair. It’s important that our
cost-to-get-to-goal function doesn’t accidentaly deprioritize good
near-solution states.

To help us we’ll calculate the Manhattan
Distance between each
tile and where it’s supposed to be. Manhattan Distance is the distance
between two places if you have to travel along city blocks.
Essentially, you’re adding up the short sides of a right triangle rather
than shortcutting across the hypotenuse. The formula is pretty simple:

class Puzzle
  def distance_to_goal                               # Here we `zip` the current puzzle with the solution
    @cells.zip(Solution).inject(0) do |sum, (a,b)|    # and total up the distances between each cell
      sum += manhattan_distance a % 3, (a / 3).to_i, # and where that cell should be.
                                b % 3, (b / 3).to_i  # This % and / stuff is just turning an integer
    end                                              # into puzzle x,y coordinates
  end
  private

  def manhattan_distance x1, y1, x2, y2  # The manhattan distance of something is just
    (x1 - x2).abs + (y1 - y2).abs        # the distance between x coordinates
  end                                    # plus the distance between y coordinates
end

class State
  def cost
    steps_from_start + steps_to_goal    # Now we have a more informed cost method
  end                                   # so our priority queue should be giving
                                        # us better results.
  def steps_from_start
    path.size
  end

  def steps_to_goal
    puzzle.distance_to_goal
  end
end

require 'set'
def solve puzzle
  @visited = Set.new
  @frontier = PriorityQueue.new {|s| s.cost }
  state = State.new puzzle
  loop {
    break if state.solution?
    search state
    state = @frontier.pop
  }
  state
end

If you’re following along at home (and using a real priority queue) you
might think the code is broken because it exited so fast. With a proper
priority queue implementation this latest search took 0.07 seconds.

This A* search is
able to quickly pick the best candidate to explore in
any situation where the distance from the current state to the goal
state is knowable. In real-world pathfinding, e.g., you can use the geospatial
distance between two points. It doesn’t work at all, however, in
situations where you know the goal when you see it but can’t determine
how close you are. A robot trying to find a door in unexplored
territory would not be able to use this, it would have to just keep
bumbling around.

The full reference code for this is on
GitHub
including a full implentation in
Clojure.

Huge thanks to my reviewer Ashish Dixit
without whom this post would have been a typo-filled mess of
half-conveyed ideas.

A quick recap of the relative time and memory costs for these search
algorithms:

uninformed depth-first:               {stack overflow error}
breadth-first w/o tracking `visited`: {out of memory error}
uninformed breadth-first:             27 seconds, 47,892 explored states
uniform-cost (Dijkstra's):            10 seconds, 51,963 explored states
A* search:                            0.07 seconds, 736 explored states