Dmitriy Setrakyan manages daily operations of GridGain Systems and brings over 12 years of experience to GridGain Systems which spans all areas of application software development from design and architecture to team management and quality assurance. His experience includes architecture and leadership in development of distributed middleware platforms, financial trading systems, CRM applications, and more. Dmitriy is a DZone MVB and is not an employee of DZone and has posted 57 posts at DZone. You can read more from them at their website. View Full User Profile

True Art Of Functional Cloud Recursion with GridGain 3.0

08.28.2010
| 4041 views |
  • submit to reddit

 

As I mentioned in my previous blog, GridGain 3.0 practically changed the way we think about cloud programming. GridGain has always been simple and natural to use, but after the last 2.1 release this just was not enough anymore. We kept thinking on how to make our product even more natural and more powerful. Well, the addition of Data Grid component in GridGain 3.0 definitely helped, but I think the biggest and most powerful change for us was a significant paradigm shift towards Functional Programming (FP) with rich and powerful APIs. The functional approach for APIs just fits so naturally, I am surprised we have not thought about it before (well... reading books on Scala definitely helped :). In GridGain 3.0 the API's got rich, and the code got terse.

Take a look for example at how you can *recursively* calculate Fibonacci sequence for number 10 in GridGain 3.0 (this is not the most effective implementation, but bare with me for now):
final Grid g = G.start(); // Start grid.

int fib = g.call(UNICAST, new GridClosureX<Integer, Integer>() {
@Override public Integer applyx(Integer n) throws GridException {
return n == 0 ? 0 : n <= 2 ? 1 :
g.call(UNICAST, this, n - 1) + g.call(UNICAST, this, n - 2);
}
}, 10);
Things to notice in the above coding snippet:
  1. GridClosureX is just a function which will be executed on the remote grid or cloud (suffix 'X' means that it throws GridException).
  2. There is no deployment step - GridGain auto-deploys your code on participating nodes on-demand (pretty cool).
  3. We are reusing the same grid variable "g" in local and remote code (even cooler, but it gets better).
  4. Note how we are re-executing the same closure from remote nodes *recursively* by passing "this" into "g.call(..)" method!!!
I hope you are already intrigued, but the above example, as pretty as it is, is not very useful or effective. Nodes may recursively calculate Fibonacci for the same number more than once throughout the same execution. Also, the method returns an integer which is not very practical as Fibonacci numbers grow very large very quickly.

Let's get a little fancier and introduce caching of calculated Fibonacci numbers on remote nodes. Also let's switch to using BigInteger so we can handle really large numbers:
BigInteger fib = g.call(UNICAST, new GridClosureX<Long, BigInteger>() {
@Override public BigInteger applyx(Long n) throws GridException {
System.out.println("Starting fibonacci execution for number: " + n);

// Make sure n is not negative.
n = Math.abs(n);

if (n == 0) {
return BigInteger.ZERO;
}

if (n <= 2) {
return BigInteger.ONE;
}

// Node-local storage is provided by Grid.nodeLocal() method.
GridNodeLocal<Long, BigInteger> nodeLocal = g.nodeLocal();

// Check if value is cached in node-local store first.
BigInteger n1 = nodeLocal.get(n - 1);

// If value is not cached in node-local store, then
// compute it and cache it.
if (n1 == null) {
// Nested recursive distributed execution on the grid.
nodeLocal.putIfAbsent(n - 1, n1 = g.call(UNICAST, this, n - 1, p));
}

// Check if value is cached in node-local store first.
BigInteger n2 = nodeLocal.get(n - 2);

// If value is not cached in node-local store, then
// compute it and cache it.
if (n2 == null) {
// Nested recursive distributed execution on the grid.
nodeLocal.putIfAbsent(n - 2, n2 = g.call(UNICAST, this, n - 2, p));
}

return n1.add(n2);
}
}, 100);

This code snippet is pretty similar to the first one, except that it caches already calculated values directly on remote nodes, so it gets smarter as it progresses. If you run it twice for the same value, no recursion will happen the second time at all, and you will get result immediately from node-local store. All we need to do now is just startup a few grid nodes and give it a go. The result for Fibonacci(100) is '354224848179261915075' by the way.

Now I want you to stop for a second and think about what we have been able to achieve just in a few lines of code above.

This example, along with many others, is shipped with GridGain. I invite you to download it and see it for yourself.

From http://gridgain.blogspot.com/2010/08/true-art-of-functional-cloud-recursion.html

 

Published at DZone with permission of Dmitriy Setrakyan, author and DZone MVB.

(Note: Opinions expressed in this article and its replies are the opinions of their respective authors and not those of DZone, Inc.)

Tags:

Comments

Nikita Ivanov replied on Sat, 2010/08/28 - 11:12am

Just a comment... What's not very visible from this article is that Fibonacci is calculated on the grid of potentially hundreds of nodes, i.e. this is highly distributed and optimized algorithm that works on any grid or cloud. And it took roughly few dozens lines of code to do it...

Richard Lemesle replied on Wed, 2010/10/27 - 8:07am

Hi,


First I want to thank Nikita Ivanov for its excellent presentation about GridGain and Scala at Niort, France.

I have a question about this Fibonacci example.

What I understand here is that calculation is distributed all over the grid BUT is always a sequential work.

Each time a node is calculating :

g.call(UNICAST, this, n - 1) + g.call(UNICAST, this, n - 2)

It is waiting first for the n-1 calculation and then waiting for the n-2 calculation.

So at a time, only one node of the grid is working...

It is highly distributed but the grid gain is hard to see.

Is it possible to modify this code to show how GridGain is able to start n-1 and n-2 calculations at the same time and return the sum only when the two calculations are done ?

Thanks again and good article.

Richard.

 

 

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.