Wednesday, June 17, 2009

Retrying transactions with exponential backoff

The method I described in my previous post about retrying transactions could use some improvement. A deficiency that will only become relevant in highly congested servers is the constant retry interval. When two or more transactions try to commit at the same time and fail, with the code from the last post they will retry probably simultaneously again. Random runtime events (like process/thread scheduler decisions, JIT compiler invocations, etc.) might help avoid collisions, but in general the collided transactions may well collide again. And again. And then again, until the specified maximum number of retries is reached.


The general method to alleviate such problems is to randomize the retry intervals. The most well-known algorithm in this category is called exponential backoff. This is one way to implement it for the utility method in my previous post (full code in gss):


public T tryExecute(final Callable<T> command) throws Exception {
T returnValue = null;
// Schedule a Future task to call the command after delay milliseconds.
int delay = 0;
ScheduledExecutorService executor = Executors.newScheduledThreadPool(1);
for (int i = 0; i < TRANSACTION_RETRIES; i++) {
final int retry = i;
ScheduledFuture<T> future = executor.schedule(new Callable<T>() {

@Override
public T call() throws Exception {
return command.call();
}
}, delay, TimeUnit.MILLISECONDS);

try {
returnValue = future.get();
break;
} catch (ExecutionException e) {
Throwable cause = e.getCause();
if (!(cause instanceof EJBTransactionRolledbackException) ||
retry == TRANSACTION_RETRIES - 1) {
executor.shutdownNow();
throw new Exception(cause);
}
delay = MIN_TIMEOUT + (int) (MIN_TIMEOUT * Math.random() * (i + 1));
String origCause = cause.getCause() == null ?
cause.getClass().getName() :
cause.getCause().getClass().getName();
logger.info("Transaction retry #" + (i+1) + " scheduled in " + delay +
" msec due to " + origCause);
}

}
executor.shutdownNow();
return returnValue;
}
The notable changes in this version are the delayed invocations of the Callable and the retry interval calculation. The former is accomplished using a ScheduledFuture from the excellent utilities in java.util.concurrent, which gets executed after a random time period. The interval calculation is something that can be implemented in a number of ways, either with monotonically increasing intervals or not. I opted for the formula above since it provided the fastest collision elimination in my tests, much faster than the monotonically increasing interval formulas I tried. The MIN_TIMEOUT constant is more of a black art. It should be tuned to the particular hardware and network setup in order to attain maximum efficiency: the minimum number of retries with the minimum interval between retries.

Another issue raised in a comment in my previous post was that the exception I am using as guard, EJBTransactionRolledbackException, may be too generic for this purpose. This is definitely true, EJBTransactionRolledbackException just wraps an OptimisticLockException as one would expect for this case, which in turn wraps the Hibernate-specific StaleObjectStateException that is thrown initially. However, contention in a database table, index or row might not necessarily result in optimistic locking violations, but in deadlocks as well, when one transaction holds exclusive locks on resources that are needed by the other and vice versa. Deadlock detection is performed by the DBMS, which forces a rollback of both transactions. This time however the initial exception (at least in my testing, might be DBMS or JDBC driver-specific) is GenericJDBCException which gets wrapped in a PersistenceException, which in turn is put inside a EJBTransactionRolledbackException before being received by our call site. Therefore, the generic nature of the guard is not a problem in this case. On the contrary it covers more relevant cases and one might argue even that there is no better service that can be offered to the caller, than retrying in all such occasions.

Monday, June 15, 2009

Retrying transactions in Java

When building a web-based system, the most often encountered persistence solution is the use of a relational DBMS. This provides many benefits, but probably the most important one is that its behavior and usage are widely understood after so many decades of use. The simplicity of the ACID transactional model, coupled with the nice fit of the HTTP request/response protocol, make for a killer combination.

The simplicity starts to break down however, when the load on the DBMS server increases, causing transactions to start failing. The DBMS can guarantee that no data corruption will occur, but handling such cases is not that simple. The scalable Optimistic Locking model requires transactions to be resubmitted when failure occurs. Since this is supposed to be rather rare (otherwise optimistic locking should probably not be used), developers often cheat by not dealing with such errors, letting them bubble up to the user, who is then responsible for resubmitting the transaction. This leads to simple, elegant codebases and unhappy users.

Adding ORM to the mix only makes things worse. In JavaEE, the JPA API hides much of the complexity of dealing with relational databases, but corner cases become harder. Add the container-managed transaction boundaries provided by session EJBs and one might be tempted to raise his hands up in despair.

However a solution is not as hard as it sounds. Provided that session EJB methods are sufficiently free from side effects, one can replay a transaction for a number of times from the call site (external to the session bean) with a small amount of code and a small added complexity to the call sites. Since I seem to come up against this requirement quite often, I thought I should describe one way to do it. The following tryExecute() helper method, retries any action supplied in a standard Callable interface for a number of times, in the face of optimistic locking violations:


public T tryExecute(Callable<T> command) throws Exception {
T returnValue = null;
for (int i = 0; i < TRANSACTION_RETRIES; i++) {
try {
returnValue = command.call();
break;
} catch(EJBTransactionRolledbackException trbe) {
if (i == TRANSACTION_RETRIES - 1)
throw trbe;
} catch (Exception e) {
throw e;
}
logger.debug("Transaction retry: " + (i+1));
}
return returnValue;
}


By abstracting away the session bean method code in a parameterized class we can reuse this method in every place that needs to retry transactions. Using a Callable as a parameter lets us return any values received from the session bean. For supplying bean methods that do not return values, we could create Runnable instances and wrap them to Callable using Executors.callable(). You can see the original code here.

If you use the above code in a JavaSE environment without EJB, you should probably need to catch OptimisticLockException for JPA, or even StaleObjectStateException, if you don't mind depending on a Hibernate API. I use the above helper method like this in my code:


file = new TransactionHelper<FileHeaderDTO>().tryExecute(new Callable<FileHeaderDTO>() {
@Override
public FileHeaderDTO call() throws Exception {
return sessionBean.createFile(user.getId(), folder.getId(), name, mimeType, uploadedFile);
}
});


Java's verbosity makes this not that easy to understand at first sight, but what happens is very simple indeed: I wrap a one-liner call to the session bean method createFile(), in a Callable and supply it to tryExecute(). The result from the bean method is received in a local variable as usual. One thing to keep in mind though is that since Java doesn't have closures, the above anonymous function can only receive final variables as parameters. In my example user, folder, name, mimeType and uploadedFile are all final. You might have to resort to using temporary local variables for storing final values on some occasions.

Thursday, June 4, 2009

Ubuntu on EEE PC

A few weeks ago I set out to upgrade Ubuntu on my EEE PC 901 from Intrepid to Jaunty. It was an, um, interesting experience, so I'm jotting down these notes for next time. Upgrading from Update Manager was not an option, because my root partition was not big enough to host the upgrade. The 901 has a 4GB SSD that I'm using as root and an 8GB (or 12GB) SSD that I've put /home on. It turns out that 4GB is OK for running a modern operating system, but a little short for updating it.

The usual procedure for upgrading is to use the official ISO images to boot from. As always you need a USB stick, or an external optical drive. I settled for the former, as you can see below.

The good news with Jaunty is that a special netbook edition is available for download. With previous editions you had to start with the desktop edition and do lots of tweaking, to arrive at a satisfactory result. With the netbook edition however things were unbelievably smooth. Everything worked out of the box with my EEE PC. Well, almost everything, but I will get to that in a while.

The first step after downloading the ISO (for the security paranoid at least) is verifying the download:


$ md5sum ubuntu-9.04-netbook-remix-i386.img
8f921e001aebc3e98e8e8e7d29ee1dd4 ubuntu-9.04-netbook-remix-i386.img

Then, we can write the image to the disk. I used Ubuntu ImageWriter (package usb-imagewriter) from another Ubuntu PC:


That went very smooth. Next step was booting the EEE PC with the newly formatted USB disk. Hitting ESC on boot, allows one to change the boot drive sequence. If this is the first time you are replacing the original OS, you probably need to disable Boot Booster from the BIOS first.

The installation process is quite simple. The only important thing was partitioning in my case, since I wanted to preserve my /home partition intact. Last time I installed Ubuntu I went with ext2 filesystems, trying to squeeze as much life from my solid state disks as I could. After doing some more research on the subject, I decided that I'll probably throw away my EEE long before the disks begin to wear out. Either that, or I'll throw an SD card in the expansion slot. Life is full of choices, particularly on the $300 range.

So I selected manual partitioning and chose ext3 for my first SSD. This is a screenshot from my first attempt. No, actually it was my second attempt. I screwed up the first one. Turns out I screwed up this one, too. See if you can spot why.


It may not be that obvious, but swap should not be on the first disk. If you are using swap at all (and I know many suggest that you don't), it would be a better choice to put it on the second disk. With 1GB of RAM, swap should be at least 1GB, which leaves only 3GB for Linux. The default installation needs something north of 2GB, so that leaves less than a gig to install software you use. Unless of course you are planning to play symlink tricks, in which case I should probably offer my condolences. Anyway, I ended up chopping 1GB with gparted from the second disk and redoing the installation again, but fortunately you won't have to.

What you should definitely do however, is put aside 16MB of space in the first disk for enabling Boot Booster in the BIOS again. This is an ASUS feature that persists the BIOS configuration on the disk, shaving a couple of seconds on each boot. It may not seem much, but think about how many times you are going to boot this thing. If you add them up, it starts to matter. Boot Booster needs only 8MB of disk to function, but I found that the installer's partition editor would only allocate one cylinder for 8MB, while we need two. Using 16MB did the right thing.

The regular customization I always do is to put /tmp and /var/tmp on tmpfs, so that many common operations don't touch the disks at all. Put the following lines in fstab to do that:


tmpfs /tmp tmpfs defaults,noexec,nosuid 0 0
tmpfs /var/tmp tmpfs defaults,noexec,nosuid 0 0

After editing /etc/fstab the proper way to remount these file systems is by following these steps:
  1. Log out of the Ubuntu desktop in order to minimize the number of open temp files.
  2. Press CTRL-ALT-F1 on your keyboard. You should see a login prompt. Login with your usual user/pass.
  3. Clear out the files in the existing /tmp and /var/tmp directories.
    sudo rm -rf /tmp/* /var/tmp/*
  4. Mount the filesystems using tmpfs.
    sudo mount /tmp
    sudo mount /var/tmp
  5. Reboot the EEE PC.
    sudo shutdown -r now
Next, from the boot-as-fast-as-you-can department comes another tweak. In /boot/grub/menu.lst set "timeout 0" in order to skip the kernel selection delay. If I ever need to boot a different kernel, I'll change it back to something larger, thankyouverymuch.

  1. Log out of the Ubuntu desktop. (Yes.. I said log out. This will go a long way to ensuring the fewest number of temp files are currently open.)
  2. Press CTRL-ALT-F1 on your keyboard. You should see a login prompt. Login with your usual user/pass.
  3. Clear out the files in the existing /tmp and /var/tmp directories.
    sudo rm -rf /tmp/* /var/tmp/*
  4. Mount the filesystems using tmpfs.
    sudo mount /tmp
    sudo mount /var/tmp
  5. Reboot the EEE PC.
    sudo shutdown -r now
Now in order to enable back Boot Booster follow these instructions for configuring the small partition we created earlier. When you reboot make sure to enable the option in the BIOS (it will be hidden when the proper partition isn't found).

Now you are all set. At least if you have no use for WPA-secured WiFi. Because if you do, you'll hit a bug with the included rt2860 driver. The details aren't that interesting, but the available options are two: either use the array.org kernel or patch the driver. The former solution used to be necessary with Intrepid, since lots of things were not working with the default kernel. However after trying out both, I don't see much need for Adam's kernel in Jaunty, unless you are terrified when encountering patch, make and their ilk. Since I'm on first name basis with them, I went with the second option, hoping that a future kernel update will bring along the fixes.

All in all, the process this time around was very easy. Almost easy peasy. My EEE PC with Ubuntu Netbook Remix makes me almost forget that I'm not on my beloved Mac.

Almost.

Creative Commons License Unless otherwise expressly stated, all original material in this weblog is licensed under a Creative Commons Attribution 3.0 License.