Sunday, September 21, 2008

What is a Memoizer and why should you care about it?

A Memoizer is a class created by Doug Lea/Brian Goetz. It's basically a create-and-store cache. That is, it has one very useful property:


  • A Memoizer is a Generic class that encapsulates the process of creating a value, and remembering the value (memoizing it) so that subsequent calls to get the value will return the memoized value, and not call the Factory method to create it.

Why do you care?

  • A Memoizer encapsulates the process of "getOrCreate()" which is highly useful when you are getting a resource that does not change by a key (think cache) and which is generally considered to be expensive to create.

But, you ask, I already can do that, why do I need a Memoizer? Glad you should ask. Memoizer is unique in its solution, because it caches a value by key, but its implementation is very efficient. It has the following additional properties:

  1. Calls to get items are concurrent

  2. Calls to get items for a particular key are guaranteed to call the Factory method for that key once and only once


It's important to understand that what the Memoizer does is both efficient, and correct. It's relatively easy to roll your own "getOrCreate()" method that has only one of those properties (and most people do). It's not so easy - or obvious - to do both and that's why you should use a Memoizer - and not roll your own.

To review, let's see the strategy most people would use for calling the Factory method once and only once. Here's how to call the Factory method once and only once:

/*** SUB OPTIMAL IMPLEMENTATION THAT IS CORRECT, BUT NOT CONCURRENT ***/
private final Factory<A,V> factory = ...;
private final Map<A, V> map = new HashMap<A, V>();

public V getOrCreate(A key) {
synchronized (map) {
if (map.contains(key)) { return map.get(key); }

// create
V value = factory.create(key);
map.put(key, value);
return value;
}
}

But of course, the line synchronized (map) should be a tip-off that this implementation is not concurrent
since there is only a single lock protecting access to our map. Can we do better? Sure. Let's use a ConcurrentHashMap to make our getOrCreate() method concurrent (but as we'll see, will not have the once-and-only-once property):

/*** SUB OPTIMAL IMPLEMENTATION THAT IS CONCURRENT, BUT NOT CORRECT ***/
private final Factory<A,V> factory = ...;
private final ConcurrentMap<A, V> map = new ConcurrentHashMap<A, V>();

public V getOrCreate(A key) {
if map.contains(key) { return map.get(key); }

// map doesn't contain key, create one -- note that first writer wins,
// all others just throw away their value
map.putIfAbsent(key, Factory.create(key));

// return the value that won
return map.get(key);
}

So, those are the two implementations, each implements either correctness (once and only once) or performance (concurrent puts and gets) but neither accomplishes both simultaneously. Of course, that's the whole point of this article. To introduce you to Memoizer. So how does Memoizer ensure correctness (once and only once) while being simultaneously concurrent?

The trick is to delay the call to the Factory create method into the future. We already know how to make the operation concurrent, but making the operation concurrent means that the first writer will win, and all the other writers will lose. So we delay the Factory create call by wrapping that call in a FutureTask. In other words, instead of putting the actual value into the map, we put a Future (which is a wrapper for getting the value sometime in the future) into the Map.

(Note: If you have not yet become familiar with the Future and FutureTask classes introduced in the JDK 1.5, you should)

By putting a Future into the map - and not our actual value - we can move the work of calling the Factory create method into the future - specifically we can move it until after the winner of the race to put the value into the map has been determined. That enables us to call get - which calls create on the Factory - on the one and only Future instance that is contained within the Map.

The full code for Memoizer illustrates this trick. Note that the Computable interface specifies a generic "Factory". Also note that I have not been able to find a library or canonical reference for Memoizer. The best I have is here: Memoizer.java.

Here it is re-created for your convenience (note that I have adjusted it slightly, for example allowing the user to specify the number of segments created in the underlying ConcurrentHashMap):

public interface Computable<A, V>
{
V compute(A arg) throws InterruptedException;
}

public class Memoizer<A, V> implements Computable<A, V>
{
private final ConcurrentMap<A, Future<V>> cache;
private final Computable<A, V> c;

public Memoizer(Computable<A, V> c)
{
this(c, 16);
}

public Memoizer(Computable<A, V> c, int segments)
{
this.cache = new ConcurrentHashMap<A, Future<V>>();
this.c = c;
}

public V compute(final A arg) throws InterruptedException
{
while (true) {
Future<V> f = cache.get(arg);
if (f == null) {
Callable<V> eval = new Callable<V>() {
public V call() throws InterruptedException {
return c.compute(arg);
}
};
FutureTask<V> ft = new FutureTask<V>(eval);
f = cache.putIfAbsent(arg, ft);
if (f == null) {
f = ft;
ft.run();
}
}
try {
return f.get();
} catch (CancellationException e) {
cache.remove(arg, f);
} catch (ExecutionException e) {
LaunderThrowable.launderThrowable(e);
}
}
}
}

You will of course need the LaunderThrowable implementation to compile this example. For a full code listing, hop on over to Terracotta, where I show not only a full working example, but demonstrate how it works with Terracotta across two nodes:

Full Memoizer Example with Terracotta

Friday, September 19, 2008

What Is Terracotta?

There are so many ways to answer this question - of course our website has it's own way. I recently wrote an e-mail to someone who asked me about Terracotta, and I figured why not share it on my blog?

Here is my response (updated a bit to be more appropriate for a blog)...

Terracotta clusters at the level of the JVM. It is a 100% Java solution. We use the Java API and Memory Model as an abstraction layer into which we inject clustering.

There are some specific differences with the way that we implement clustering and the way that others do (in fact, in that regard, Terracotta is an entirely unique solution, I do not believe there is anything else like it).

There are two main differences in Terracotta -the programming model and the performance (the two go hand in hand, one cannot be had without the other).

For the programmer , Terracotta is injected at the Java level, meaning that programming a "distributed" application with Terracotta is no different than programming a multi-threaded or concurrent application. Terracotta makes use of all of the concurrent facilities built in to the Java language and API so that the definition and operation of those facilities are extended across a cluster - in other words each node that you add to the cluster simply becomes more threads available to your application.

Put another way, you program plain POJOs, and Terracotta manages replication services of those POJOs, maintains the identity of those POJOs and provides locking services using either synchronized/wait/notify or java.util.concurrent libraries e.g. ReentrantReadWriteLock - all across the cluster. (Again the model is simply threads in one node are no different than threads in another node - all standard Java operations "just work")

Of course this doesn't mean that programming across nodes separated by a network is free. Terracotta doesn't believe that an architect doesn't have to know about that interaction. We do think one has to architect for Terracotta, but we do not believe you should have to *program* to it. The analogy is much like that of the garbage collector - you don't program to the Java Garbage Collector, but you do architect your application around it's presence.

From a high level architectural level, Terracotta uses a tiered architecture. All application nodes talk to the Terracotta Server using TCP (never multicast, and never to one another, P2P is provably not scalable to provide coherent locking). The Terracotta Server can be clustered (called the Terracotta Server Array) for availability and scalability. It's a lot like the Database in that regard - the Terracotta Server (Array) is the composer in the symphony, coordinating the actions of the application nodes, and storing the data safely - all the way to disk in fact just like a database (and transparently from the application nodes perspective). When you need more availability or scalability, you just add more Terracotta Servers (no changes to your application are required).

The replicated data in Terracotta is 100% coherent across the cluster, and always stored safely to disk. This feature is unique to Terracotta given the performance levels it can achieve, which is the other main difference between Terracotta and all other solutions in the same space.

Other clustering solutions in the same space claim to have linear scaling, coherent data, and high performance - all delivered at the same time. That's basically a lie - none of them come even close to delivering all three at the same time (e.g. coherent data is possible but it's really slow, high scale can be achieved, but only for non-coherent data). And no product in the same space delivers the same performance that Terracotta does - it is simply in a class of its own since it is the only product that does not rely on brute force replication techniques such as Java Serialization. Coupled with some really innovative ways to eliminate or reduce network latency for locking, Terracotta provides a solution that can give data coherence guarantees, with amazing performance.

What all of this translates into is a solution that is flexible (a programmer can pick and choose his/her own programming stack and domain model), fast (no other clustering solution can send delta updates over the network), and more importantly, manageable. The Terracotta architecture is not an accident - it is an intentional design decision that ensures that managing a Terracotta Cluster is simple and efficient. Just like the proven 3-tier architecture of web application nodes and database servers, Terracotta stores application clustered memory in a well known location - the Terracotta Server Array. Loss of application nodes in a Terracotta Server Cluster, like in a 3-tier application, does not risk data-loss in any way, and likewise, loss of the Terracotta Server process(es) does not jeopardize the data in any way.

Tuesday, September 09, 2008

Cluster Deadlocks *ROCK* with Terracotta

Am I crazy or what?

No not really. You see I just happen to have seen more than one customer run into a cluster deadlock, and it turns out that solving the issue with Terracotta is awesome (actually, Terracotta can automatically detect it in an upcoming version, but shhh don't tell anyone I told you that)

It's funny, really, because I have been hearing this dumb idea that somehow clustered deadlocks with Terracotta is actually this really scary thing -- ooooh watch out for that complicated Terracotta thing, it uses LOCKING (oh gosh) and that can lead to CLUSTERED DEADLOCKS. Oh my. (Anyone know where I can get a clustered deadlock costume, it's almost halloween!)

Really. It's like a bad rumor I keep hearing over and over again. What do they call that when people try to scare other people with rumors that aren't true .... F.....oh nevermind. Here's why deadlocks truly are better with Terracotta:

First, what do we get with Terracotta?
- Kill a JVM, release its lock.
- Kill a JVM, don't lose your state

Why does that matter? Well what do you do when you see a deadlock with a regular Java application? Since it's pretty much hosed, you have to restart it (usually you probably debug the hell out of it first and try to fix the deadlock). But the app is hosed. Unless you happen to have coded a "stateless" app - you've also lost your app state. Bummer :(

Well, not so with an app running on Terracotta. First of all, you don't have to kill the whole app. In fact, if you do actually get a clustered deadlock, you just have to kill one half of the deadlock (because the locks are released, get it?) and the other half will actually get to complete it's operation. How do you do that? Well since the app state is highly available, you can kill any node at will.

So it's simple to resolve a clustered deadlock with Terracotta - just do a rolling restart of every client JVM. That's it. When you hit one half of the deadlock, and kill that JVM, the lock that the other side of the clustered deadlock wants will be freed, and it will go on its merry way.

Now of course, you still need to debug the hell out of your app :). When you fix the app, just update it in place, do another rolling restart, and voila! Fixed deadlock with no downtime.

So to summarize, deadlocks with Java:
- Have to restart
- Lose app state
- Downtime BAD

Deadlocks with Terracotta (e.g. Clustered Deadlocks):
- Rolling restart of application nodes
- Preserve application state
- No downtime GOOD

Monday, September 08, 2008

How can I make sure Terracotta is wired into my application?

Per the title of this blog post, I'm going to show you how to make sure that Terracotta is enabled in your application.
One of the funny things about Terracotta is that applications typically don't know it's there.  This is normally a really good thing - it means you can use the 'ole binary search debug trick.  (Just remove Terracotta from one half of the application one debug session at a time to quickly narrow down the issue).
But of course, in production, we want to make doubly sure Terracotta is actually running - yeah sure the application might be happy as a clam churning out txns, but we want to make sure those txns are getting replicated for high availability, right? :)
Fortunately, finding out if Terracotta is wired into your app is really easy.  We can make use of the fact that most of the regular Java classes are instrumented by default, so we can use reflection to interrogate one of them.  I chose String since I think it's a well known class.  Here's the code:

public static final boolean isTCEnabled()
{
try {
String.class.getMethod("__tc_decompress");
return true;
} catch (Exception e) {
return false;
}
}
That's it! We just test to see if a special Terracotta method is present, and if so, we know Terracotta is wired in. All you have to do is put that into your application startup somewhere, and complain loudly if the method returns false :)