{ tinou bao }

Fail Fast, Debugging and Systems that Never Stop

If you're a Java guy you're probably familiar with the phrase "fail fucking fast" in the context of Iterators (I added the fucking part).  But fail fast is much more than just iterators, it's a general design principle--and a very important one at that. 

Jim Gray on fail fast: "it [the process] should either function correctly or it should detect the fault, signal failure and stop operating."  You can replace "the process" with component, class, etc.  Whatever you designate as your logical unit, the fail fast principle remains.  What you absolutely don't want to do is detect the fault, don't signal failure and continue.  This is why swallowing exceptions is one of my all time pet peeves.  Fail fast is often described in terms of fault detection latency, the time between initial error detection and the fault.  You want your latency to be small. 

There are two advantages to failing fast. First, easier debugging and analysis.  It complicates things greatly if your code detects errors but continues.  Eventually something will go wrong but now you can't easily track down the root cause.  I recently worked with a component (one that shall remain nameless) that doesn't follow the fail fast principle.  During initialization the component knew it was missing a configuration file but instead of halting it continued on.  When the component was finally invoked things obviously did not work, but the root cause was not obvious.  Ended up wasting two days tracking down the root cause, when it really should have taken 30 seconds. 

Second, ability to build "systems that never stop".  Failing fast is so important to building highly available systems that Joe Armstrong talks about it at great lengths in his presentation on "systems that never stop (and Erlang)."  In this presentation he presents 6 laws,

1. Isolation
2. Concurrency
3. Failure Detection
4. Fault Identification
5. Live Code Upgrade
6. Stable Storage

Without failure detection you can't fail fast, and if you can't fail fast you can't achieve isolation.  Real world example: Amazon S3's massive outage last year.  A huge embarrassment to Amazon's otherwise great cloud stack.  Their code didn't have adequate failure detection, allowing a single corrupt bit to propagate throughout the system.  The result was hours of downtime while engineers scrambled.  If Amazon had been able to detect the single corrupt bit then they could have isolated the failing component instead of letting the error bring down the entire system.

Few of us will be coding S3 like systems, but it doesn't mean we can't follow the fail fast approach.  It will make debugging easier and just might prevent similar embarrassments.  I think some programmers don't like to fail fast because they worry they'll be blamed for the failure, so just pretend things are good and pray nothing bad happens downstream.  I suppose it depends on how much you believe in God. 

Lock Coarsening, Biased Locking, Escape Analysis for Dummies

The other day I saw that Sun released JDK 1.6 Update 14 that includes version 14 of their HotSpot Virtual Machine.  I think for the first time they included in the release notes a section mentioning the VM now accepts a DoEscapeAnalysis flag.  Escape analysis has been a much talked about optimization technique, but while it's been around for a while this was the first time I've seen Sun officially document it. 

My coworker then pointed me to an article that questioned whether escape analysis actually did anything (bing "did escape analysis escape Java").  The article is quite informative, but I was skeptical of the benchmark test and its conclusions.  I mean, there are really smart people at Sun (not just guys like me with a blog who tries to sound smart) and I found it hard to believe that -XX:+DoEscapeAnalysis did nothing.  In fairness, there's a second part to the blog, also quite informative, that digs a little deeper into benchmarks and clarifies some things.

Uneducated Guesses

Playing around a bit (with Java scientific benchmark) I think -XX:+DoEscapeAnalysis does offer a performance gain, but it's not as much as some of us had hoped (some of us are always hoping the next "breakthrough" will solve all our problems).  Also, it seems that escape analysis is not as predictable as the other concurrency optimization techniques.  One runs saw little gains, the next saw more substantial gains;  whereas biased locking and lock coarsening predictably, consistently saw big performance improvements.  Escape analysis doesn't seem to kick it sometimes.  This is all guessing on my part.  I have no idea on a low level how these techniques are implemented. 

At this point some might be asking, what is escape analysis, biased locking and lock coarsening, anyway?  I wrote a little bit about biased locking here last year.  But now that I have OmniGraffle Pro I'll explain things better with diagrams.

Lock Coarsening

Let's start with lock coarsening.  You enable lock coarsening with -XX:+EliminateLocks.  This does not mean locks are completely removed/eliminated.  Rather, instead of a thread repeatedly acquiring and releasing the same lock the VM will combine these calls.

  In figure 1 you can see two critical sections guarded by the same lock.  Lock coarsening will merge the two critical sections, along with the non-critical section, into a larger synchronized block.  Instead of two acquire/release calls there's only one.  Moreover, with a larger block of code to work with other optimizations can be better applied.  While this reduces the locking overhead it should be noted larger critical sections may cause the application to be less responsive.  Some may notice the irony that we often try to break up large synchronized blocks. 

Biased Locking

Up next is biased locking.  Biased locking stems from real world observations that most locks are uncontended and at most one thread tries to acquire the lock.  Here's how two threads locking two different objects work without biased locking.

As each thread enters the critical section it tries to acquire the (different, uncontended) lock.  This involves expensive operations: operating system mutexes, conditional variables, compare and swaps, etc.  Given real word observations we can optimize by biasing objects to threads base on some heuristics (e.g., which thread created the object).  The threads can then lock/unlock without expensive operations.

  The downside is if there's another thread that comes along and attempts to acquire the same lock  the lock bias has to be revoked then.  If I remember correctly the VM does some sort of bulk rebiasing to amortize the overhead.

Escape Analysis

Finally, escape analysis.  First, the virtual machine analyzes execution to see which objects escapes into the unknown and which are confined to the thread/stack frame.  Objects that are confined can be optimized.  The VM does two kinds of optimization on these confined objects.  First, since the objects are confined to the thread it is safe to remove locking (no other thread can possibly come along and use the the confined objects).  The fancy term is lock elision.  The most basic example is with a local StringBuffer, but there are actually some really interesting examples that aren't so obvious, i.e., examples that can't be optimized statically at compile time. 

The second optimization that can be done after escape analysis is allocation optimization.  In Java when you do a new FooBar() the object is allocated on the heap.  Heap allocation is actually really faster, contrary to what many might say, but then you have to deal with garbage collection (the de-allocation part).  There's also an interesting issue with latency from cache misses due to the fact that memory is hierarchical. (google Brian Goetz, he explains it better). 

However, since the VM knows that these objects won't escape it can allocate them on the stack or put them in the registers, known as stack allocation and scalar replacement, respectively.  For example, if FooBar was a simple class that contained just a single int it could avoid allocation and the int field could be place in the register.  This avoids allocation, garbage collection and cache misses.

Just as with lock coarsening, escape analysis leads to further optimization opportunities.

But as I've said before, my dream is to one day never have to deal with locks.  I'm still waiting transactional memory, which might be coming soon hardware transactional memory.

Beyond Locks and Conditional Variables

The other day I mentioned ConcurrentHashMap favored the judicious use of volatile over locks for read operations. The code becomes significantly more difficult to understand, but the performance gain is also significant. Write operations, however, still involved locking. The question is then, can we improve on write operations and its use of locks? The answer is yes. There are at least two approaches, both of which take a more optimistic approach than locking.

Lock-Free Algorithms

The first is to re-implement our hash table using a lock-free algorithm. Many standard data structures (linked lists, deques, hash tables, etc.) have lock-free implementations. For example, we could use Cliff Click's non-blocking (concurrent, lock-free) hash table as a replacement for our ConcurrentHashMap.

The lock-free approach typically uses a compare-and-set (CAS) or load-link/store-conditional (LL/SC) to atomicity modify values. This is significantly faster than locks under low to moderate contention. I don't know the exact details, but intuitively this makes sense since these instructions are low-level, directly hardware supported, whereas locks are more heavyweight (and are implemented using these very instructions).

/**
 * Atomically increments by one the current value.
 *
 * @return the previous value
 */
public final int getAndIncrement() {
  for (;;) {
    int current = get();
    int next = current + 1;
    if (compareAndSet(current, next))
      return current;
  }
}

When it's just a single variable that requires modification, as in the above example taken from AtomicInteger, things are pretty straightforward. It's when you have to update multiple variables, as when you need to modify the tail pointer and the next to last node in a linked-list, that lock-free implementations become hairy. One way to handle this situation is to put the data structure in a state such that the next operation can put the data structure back into a consistent state, as in the concurrent linked queue implementation below.

/**
 * Inserts the specified element at the tail of this queue.
 *
 * @return <tt>true</tt> (as specified by {@link java.util.Queue#offer})
 * @throws NullPointerException if the specified element is null
 */
public boolean offer(E e) {
  if (e == null) throw new NullPointerException();
  Node<E> n = new Node<E>(e, null);
  for (;;) {
    Node<E> t = tail;
    Node<E> s = t.getNext();
    if (t == tail) {
      if (s == null) {
        if (t.casNext(s, n)) {
          casTail(t, n);
          return true;
        }
      } else {
        casTail(t, s);
      }
    }
  }
}

A key observation with lock-free algorithms is it's optimistic. Locks are pessimistic: I need to modify this variable, so I'm going to lock it to prevent others from also modifying it. The lock-free approach is optimistic: I'm going to modify this variable, if someone has modified it, I'll retry until I succeed. You can intuitively see how under low to moderate contention lock-free wins.

Transactional Memory

Now, all this is interesting, but programming lock-free algorithms is soooo 1996. For me, it's all about Software Transactional Memory (STM), a second approach to concurrency without locks. STM can perform better than the lock-based approach but without the complexity of lock-free algorithms. I can across STM while reading a paper on "Executing Java Programs with Transactional Memory" in which the authors tried mapping the existing synchronized construct to STM transactions. Granted, it was written by a bunch of Stanfurd guys, but I'll cut them some slack.

STM leverages the work done in the database community around transactions and takes a different approach to concurrency. Instead of using locks or complicated CAS tests in your code, STM code is just normal code with the addition of transactional boundaries. STM enabled code might look something like this

atomic {
 balance = myHT.get(accountNumber);
 myHT.put(accountNumber, balance + 10}
}

There are no locks in STM, just (atomic) transactions. The beauty of this approach is you can't have deadlocks (*). Moreover, code is now easily "composable" since you don't have to deal with how multiple locks interact when composing different blocks of code that rely on different locks. Performance-wise, if there are not too many conflicts you can intuitively see that it's better than explicitly obtaining a lock.

With STM it's the runtime's responsibility to detect conflicts. Just as in a database transaction you don't explicitly lock a table, with STM you don't explicitly lock your data. You simply tell the runtime that you want to execute this block of code in a transaction. STM is an optimistic approach: you execute your transaction and if there are conflicts you rollback/re-execute. Intuitively, optimistic approaches perform better when there is low to moderate contention/conflict. Transactional memory isn't mainstream yet but I can easily see how it'll make our programming lives so much better once all the kinks are worked out.

Conclusions

In summary, there are at least two approaches we can employ in lieu of locks. We can use lock-free algorithms but this requires extremely careful reasoning about the states of your data. Or we can think of concurrency in terms of transactions and use transactional memory to deal with conflicts.