Avoiding fallback in distributed systems

As previously mentioned, I was recently able to contribute to the Amazon Builders' Library. I'd also like to share another post that I wrote for the series, entitled Avoiding fallback in distributed systems. I'm especially excited to be able to publish it, as it's based on an internal Amazon document I wrote in 2006 entitled Modes Considered Harmful. It provoked a lot of interesting discussions over the years, so I'm happy to be able to share a (hopefully slightly better written) version of it publicly. Here's a quick abstract of the article:

This article covers fallback strategies and why we almost never use them at Amazon. In the world of distributed systems, fallback strategies are among the most difficult challenges to handle, especially for time-sensitive services. Compounding this difficulty is that bad fallback strategies can take a long time (even years) to leave repercussions, and the difference between a good strategy and a bad strategy is subtle. In this article, the focus will be on how fallback strategies can cause more problems than they fix. We’ll include examples of where fallback strategies have caused problems at Amazon. Finally, we’ll discuss alternatives to fallback that we use at Amazon.

Challenges with distributed systems

I was recently invited to contribute to the Amazon Builders' Library. One article I'd been wanting to publish publicly is about how bizarre distributed systems are, and what's been the biggest challenge building them, in my experience.

Please check out the article and here's a quick abstract:

Developing distributed utility computing services, such as reliable long-distance telephone networks, or Amazon Web Services (AWS) services, is hard. Distributed computing is also weirder and less intuitive than other forms of computing because of two interrelated problems. Independent failures and nondeterminism cause the most impactful issues in distributed systems. In addition to the typical computing failures most engineers are used to, failures in distributed systems can occur in many other ways. What’s worse, it’s impossible always to know whether something failed. This article reviews the concepts that contribute to why distributed computing is so, well, weird.

Please Don't Write Bruby

This doc is about how to write Ruby code instead of writing hybrid yuck Bruby code. Ruby code, is, well, Ruby code; i.e., code written in Ruby and not some other language. I strongly believe that once you have chosen to write code in Ruby, you should try to keep writing code in Ruby. Specifically, please don't write Bruby, which is an unholy mishmash of Bash and Ruby. Bruby is hard to read, flaky, slower (usually), and always harder to reason about. It's even harder to write. There is almost no reason to shell out to Bash from Ruby.

Here's a canonical example of Bruby code:

output = `somecommand | egrep -v '^snord[123]' | sort | uniq`
if $? == 0
  # ...do stuff with 'output' such as:
  foo output
end

There are a number of problems with this code. For one thing, it's unnecessary to use Bash in the first place. Ruby is just as good at grepping, regular expressions, sorting and uniqifying. The more you mix different programming languages, the more the reader of the code has to switch gears mentally. As a frequent code-reviewer, I implore you: please don't make your readers switch gears mentally (unless there's a really good reason), it causes brain damage after a while. Also, Bash pipelines easily hide bugs and mask failures. By default, Bash ignores errors from an "interior" command in a pipeline, as the following code illustrates:

def lower_nuclear_plant_control_rods
  # The following line will *not* raise an exception, even though it
  # will barf.
  rods = `cat /etc/plants/springfield/control_rods | sort --revesre | uniq`
  # 'rods' is now an empty string and $? will be 0, indicating that 
  # everything is ok, when it isn't.
  if $? != 0
    # This will never happen. Millions of lives will be lost in the
    # ensuing calamity.
    page_operator "Springfield Ops Center", :sev_1, "Meltdown Imminent"
  else
    rods.split.each do |rod|
      lower rod
    end
  end
end

Despite the subtly bad arguments to sort, the above code won't raise an exception, and will fail to lower the control rods and also fail to notify the operators (because $? will be 0). Thus the town of Springfield will be wiped off the map. Do you want the same type of errors to accidentally blow away all of your production databases from an errant invocation of some admin script?

One way to fix the above would be to add the pipefail option into the string of Bash code:

rods = `set -o pipefail; cat /etc/plants/springfield/control_rods | sort --revesre | uniq`

But that's easy to forget, difficult to mechanistically catch, and ugly to read. The better solution is to remember that you can write Ruby in Ruby:

def lower_nuclear_plant_control_rods
  File.readlines('/etc/plants/springfield/control_rods').sort.reverse.uniq do |rod|
    lower rod
  end
rescue
  page_operator "Springfield Ops Center", :sev_1, "Meltdown Imminent"
  raise
end

The above code is shorter, easier to read (no switching mental gears) and is guaranteed to raise exceptions if something is wrong. The specific changes are:

cat

Ruby's good at opening files, just use File.readlines if you want to read a file line-by-line.

sort

Ruby Enumerables have sort built in.

--reverse

Use Enumerable's built-in reverse method.

uniq

Use Enumerable's uniq method.

Error-handling

Any errors in the invocation (for example misspelling reverse as revesre) will result in an exception being raised).

Tips

The rest of this document contains a series of tips to help you write Ruby instead of Bruby.

Tip 1: Google for Pure Ruby Bash Equivalents

Whenever you're tempted to shell out in a Ruby script, stop, flagellate yourself 23 times with a birch branch, and then Google for an alternative in Pure Ruby. For example, imagine your script must create a directory, and not fail if the directory already exists, and also create any intermediary directories. But you don't want to write that code yourself because it's yucky and complicated and you know you'll fail to handle some edge condition properly. If you're familiar with Unix, your first inclination might be to write Bruby:

system "mkdir -p '#{ROOT_DIR}'"
if $? != 0
  raise "Unable to create directory #{ROOT_DIR}"
end

The above is clunky. It's also easy to forget to check the value of $?, in which case your code will silently continue even though the directory was not created. Fortunately, this is easy to fix. Just Google for it (after flagellating yourself). You will see that Ruby has a built-in version of mkdir -p.

require 'fileutils'
FileUtils.mkdir_p ROOT_DIR

This version is shorter and easier to read, and, most importantly, raises an exception if anything went wrong:

irb(main):666:0> FileUtils.mkdir_p "/bogon/adfadf"
Errno::EACCES: Permission denied @ dir_s_mkdir - /bogon
 from /usr/local/Cellar/ruby/2.3.0/lib/ruby/2.3.0/fileutils.rb:253:in `mkdir'
 from /usr/local/Cellar/ruby/2.3.0/lib/ruby/2.3.0/fileutils.rb:253:in `fu_mkdir'
 from /usr/local/Cellar/ruby/2.3.0/lib/ruby/2.3.0/fileutils.rb:227:in `block (2 levels) in mkdir_p'
 from /usr/local/Cellar/ruby/2.3.0/lib/ruby/2.3.0/fileutils.rb:225:in `reverse_each'
 from /usr/local/Cellar/ruby/2.3.0/lib/ruby/2.3.0/fileutils.rb:225:in `block in mkdir_p'
 from /usr/local/Cellar/ruby/2.3.0/lib/ruby/2.3.0/fileutils.rb:211:in `each'
 from /usr/local/Cellar/ruby/2.3.0/lib/ruby/2.3.0/fileutils.rb:211:in `mkdir_p'
 from (irb):666
 from /usr/local/bin/irb:11:in `<main>'

This obnoxious error might be obnoxious, but it also might save your life.

Tip 2: Keep unavoidable Bash usage to a minimum

Sometimes it does make sense to shell out. For example, it is hard to find a Ruby equivalent of the command-line dig DNS utility. In these situations, don't throw out the baby with the bathwater; keep the Bash to a minimum. For example, in Bruby, you would write:

dig_command = "dig +qr www.springfield.us any -x 127.0.0.1 isc.org ns +noqr"
mail_server = `#{dig_command} | egrep -w MX | awk '{print $6}'`.chomp

Whereas in Ruby, by contrast, you should use Bash only to run dig, everything else (such as processing the standard output of dig) should be done in Ruby. The built-in Open3 module makes this straightforward in many cases:

require 'open3'
output, error, status = Open3.capture3 dig_command

Open3.capture3 returns a stream containing the standard output of running dig_command, as well as the status of running the command. The next tip covers how to actually replicate the rest of the above pipeline that populated the mail_server variable.

Tip 3: Use Enumerable to replace Bash pipelines

A distinguishing feature of Bash is its ability to chain commands together using pipes, as illustrated in the previous tip:

mail_server = `#{dig_command} | egrep -w MX | awk '{print $6}'`.chomp

Most of the time you can replicate pipelines using Ruby's built-in Enumerable module. Almost everything you think might be an Enumerable actually is an Enumerable: arrays, strings, open files, etc. In particular, if you're trying to convert Bruby to Ruby, you can use methods like IO.popen, or better yet the methods in Open3, to get an Enumerable (or else a string, which can be converted into one with split) over the standard output of that process. From there, you can take advantage of methods such as Enumerable.grep (which, for example, seamlessly handles regular expressions).

In those cases where Enumerable itself doesn't immediately solve the problem, you have the Ruby programming language itself at your beck and call. For example, many of the features of Awk can be found directly in Ruby (if you did enough programming language research you'd probably dig up some indirect connection between the two languages, but that shall be left as an exercise for the reader).

Here are all the equivalents of each part of the above Bash pipeline.

Bruby	Ruby
`#{dig_command}`	Open3.capture3(dig_command)
egrep -w MX	split("\n").grep(/\WMX\W/)
awk '{print $6}'	split[5]

Putting it all together:

require 'open3'
dig_command = "dig +qr www.springfield.us any -x 127.0.0.1 isc.org ns +noqr"
o, e, s = Open3.capture3 dig_command
mail_server = if s.success?
                o.split("\n").grep(/\WMX\W/)[0].split[5]
              else
                raise "Failed: #{dig_command}\n#{e}"
              end

Here are some other common mappings from Bash to Enumerable methods:

Bash	Enumerable
head -n 2	take(2)
tail -n 2	reverse_each.take(2)
sort	sort
uniq	to_a.uniq
grep	grep
grep -v	grep_v

Validate

Six Audacious Goals for Your System

With apologies to the authors of the futurist programming notes, here is a set of audacious goals for your system (by which I mean your collection of web sites, webservices, databases, and so on):

1. Make your entire system runnable (for debugging/development) on a single machine, via a single command,
2. ...without manual configuration,
3. ...without an Internet connection.
4. Demonstrate that your system works flawlessly even when you permanently and unexpectedly unplug the power cable from any one machine (even your most precious database).
5. Make one of your N-tier architectures M-tier, where M < N.
6. Optimize every user-visible action so that it is perceived to complete in less than one second.

Ulrich Drepper's Memory Paper and CL

I recently came across Ulrich Drepper's excellent paper, What Every Programmer Should Know About Memory. There is a lot of fascinating stuff in there about an important class of things you sometimes need to do to achieve excellent performance. While the paper concentrates on C, I was wondering if some of the same effects could be observed in a high-level language like CL (for the record, I think CL is both high- and low-level, but whatever...) I did a quick experiment which suggests that at least one of Ulrich's optimizations works in CL. [Note: the following is not an attempt to produce mathematically correct results, as Ulrich did; I just wanted to see if the order in which memory was accessed seemed to matter.]:

(declaim (optimize (speed 3) (safety 0)))

(defun matrix-multiply-fast? ()
  (let ((m1 (make-array '(1000 1000) :element-type 'fixnum))
        (m2 (make-array '(1000 1000) :element-type 'fixnum))
        (m3 (make-array '(1000 1000) :element-type 'fixnum)))
    (loop repeat 100
       do
       (loop for i upto 1000
          do
          (loop for j upto 1000
             do
             (setf (aref m3 i j) (* (aref m1 i j) (aref m2 i j))))))))

(defun matrix-multiply-slow? ()
  (let ((m1 (make-array '(1000 1000) :element-type 'fixnum))
        (m2 (make-array '(1000 1000) :element-type 'fixnum))
        (m3 (make-array '(1000 1000) :element-type 'fixnum)))
    (loop repeat 100
       do
       (loop for i upto 1000
          do
          (loop for j upto 1000
             do
             (setf (aref m3 i j) (* (aref m1 i j) (aref m2 j i))))))))

Note the only difference between the two functions is the order in which the elements of the 2nd array are accessed. After compiling the above file I did the following from the CL prompt:

CL-USER> (time (matrix-multiply-fast?))
Evaluation took:
  2.776 seconds of real time
  2.508157 seconds of user run time
  0.048003 seconds of system run time
  [Run times include 0.028 seconds GC run time.]
  0 calls to %EVAL
  0 page faults and
  12,000,160 bytes consed.
CL-USER> (time (matrix-multiply-slow?))
Evaluation took:
  3.926 seconds of real time
  3.632227 seconds of user run time
  0.016001 seconds of system run time
  0 calls to %EVAL
  0 page faults and
  12,008,280 bytes consed.

Assuming the above is all correct, it sort-of duplicates Ulrich's result where accessing an array in a column-major order is slower (see figure 6.1 for an illustration). Now, I have to admit that, for lack of time, I didn't read Ulrich's paper in great depth and kind of lazily jumped to section six. I'd be curious to know if this sort of optimization is already well-known in the CL world (and/or for other "high-level" programming languages). Some casual googling turned up an excellent paper about optimizing CL via type annotations, but I didn't see anyone directly addressing Ulrich's points. I'd be curious if any readers of this blog know more.

The Icarus Ultimatum

It is unlikely that every programmer is familiar with Icarus, but I bet that almost all programmers have something in common with him. Programmers are saturated with advice not to do things, similar to the advice Icarus' dad gave him about aviation. Don't use threads unless you really know what you're doing (and then don't use them anyway.) Don't use new language features (they're too dangerous.) Use the "right tool for the right job" (i.e., not the one you like.) Don't "prematurely" optimize (note: it's always premature.) Don't use macros, nobody will be able to read your code. Don't use multiple inheritance. You ain't gonna need it (you dork!) Don't, don't, don't; no, No, NO! For the rest of this essay I will refer to such advice as "Dead" advice, in honor of Icarus' father, Daedalus (and also to honor my own lack of spelling ability.)

Let's remember one thing about Icarus. Yes, he died a fiery, horrible death. But at the same time, he flew close to the freakin' Sun! How cool is that? Likewise, the most exciting developments in software have been crazy stupid. I remember how quixotic the notion that you could index and search the entire Internet (or even a significant part of it) once seemed. Only by thinking big does anything cool get done, it doesn't get done by sitting around pondering all the things you shouldn't be doing.

Dead advice exists for many reasons, of course. Programming is so open-ended that it is easy to create unmaintainable, unreliable, slow software. Programs start out as a blank slate; one can do anything. Without discipline, anything turns into unmitigated crap. Thus experienced programmers observe mistakes (including their own) and, sometimes, craft memorable axioms as a result. Unfortunately, these well-intentioned rules-of-thumb often turn into blindly-followed commandments by the time they penetrate the consciousness of millions of programmers.
For example, the original advice about premature optimization has become twisted over the years, such that programmers are afraid ever to optimize lest their effort be labeled "premature". Similarly, Microsoft's infamous detour into Hungarian notation started with a misunderstood paper by future astronaut Charles Simonyi. But this sort of telephone game isn't the only source of Dead advice.

"It's not guns that kill people, It's these little hard things!"
--- the Flash from "The Trickster Returns"

Sometimes Dead advice emerges not from a misinterpretation of the original advice but from a failure to perceive a problem's underlying cause. The treatment of threads in computer science illustrates this phenomenon well. Typical computer science programs teach little, if anything about threads; threads are an "implementation detail" with minor theoretical import (compared, say, to data structures, Big O, recursion, etc). What one does learn about them, though, makes them sound cool. Heck, let's face it, they are pretty darn cool. They're the expression of multitasking; a piece of magic. Junior programmers are disappointed when, on their first job, their mentors seem ready to pour boiling sulphuric acid on their keyboard if they so much as mention the possibility of using a thread. "My advice is not to use threads unless you're extremely experienced, a thread wizard, and even then don't use them." That's what they'll hear.

I'm going to step out on a limb here, insert earplugs to drown out the chorus of "boos" that I can already hear even though nobody's read this post yet, and state: there's nothing wrong with using threads. This is a big reversal for me; I spread the threads are evil gospel for many years. Yet I have confidence in this assertion for a number of reasons, foremost among them being that the admonitions against threads haven't helped much. How many applications have you used where the user interface freezes up every time the application does something that takes longer than a second or two? How many times have you found Cancel buttons (you know, those ones you're trying to hit when you realize you're accidentally deleting all of your un-backed-up files?) that take minutes to have any effect?

If anti-thread prohibitions haven't worked, what would? I've been casually researching this issue for a long time. At first I decided, like many, that threads are indeed evil, and that event-driven programming was the only way to go (programmers love nothing more than a dichotomy.) When other programmers would point out to me that event-driven programming is, at times, a giant pain in the rear, I'd silently mark them as wimps. Finally, I read a series of papers, including this one, that convinced me there was, at least, more to the story. Even more recently, someone clued me in to the work of Joe Armstrong, one of the only people outside of academia to have stepped back from the problem of threads and tackle, instead, concurrency, which was the real issue all along. By far the coolest thing Joe did was realize that you can in fact fly close to the Sun and spawn as many darn "threads" as the problem you're solving truly warrants. You can also use events, too, there having been, it turns out, no dichotomy between events and threads either.

I found this revelatory after having wasted a lot of time, over the years, writing things like HTTP parsers in frameworks that either force you to use only events, or frameworks that let you spawn threads easily (though not necessarily efficiently) but have no standard event-passing mechanism. It's not just that I didn't think of it myself, it's that almost everyone I talked to about this sort of issue was either in the "threads are evil" camp or the "events are confusing" camp. I wasted a lot of time following bad advice.

Experiences with Dead advice such as "threads are evil" have led me to question other Dead advice, such as:

• Premature optimization is the root of all evil.


• Never use multiple inheritance.


• YAGNI.


• Never use macros.

Each of these have a kernel of truth to them, but are also too easily misunderstood and have not had the overall effect on programming that was originally intended. If I have some time I'll try to give more examples of each of the above. In the meantime, I do have to mention one piece of (arguably) Dead advice that I haven't found any fault with yet:

• Don't repeat yourself.
  

Proactive Optimization

In the programming world, one of the most widely repeated maxims is, "Premature optimization is the root of all evil." Having found this to be one of the most well-intended yet misunderstood pieces of advice in the history of the Universe, I was all set to write a blog about why. Unfortunately, for me, a quick trip to Wikipedia led me to this article: The Fallacy of Premature Optimization, by Randall Hyde, which said everything I intended to say, and more, and did so more eloquently that I could ever hoped to have (although I might have put in some better jokes).

So the only thing I really have to add to that article is the following crude attempt at marketing: let's put a little spin on that phrase and turn it around! Whenever you hear "premature optimization is the root of all evil", retort (politely) with "but proactive optimization is the root of all goodness."