<html>
<head>
<meta content="text/html; charset=ISO-8859-1"
http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<div class="moz-cite-prefix">Very interesting stuff Matt! <br>
<br>
I find the design that leverages on Infinispan for distributing
the tasks - while maximizing locality and exploiting Infinispan's
fault-tolerance capabilities - modular and elegant. It will be
interesting to evaluate if there is a significant overhead with
respect to a purely JGroups-based mechanism.<br>
<br>
We will be looking at your code, and may pheraps come up with some
use-cases.<br>
<br>
Cheers,<br>
<br>
Paolo<br>
<br>
On 5/9/13 10:52 AM, Manik Surtani wrote:<br>
</div>
<blockquote
cite="mid:9F7DA523-11D6-4128-83E0-2A7C4B53CF32@redhat.com"
type="cite">
<meta http-equiv="Content-Type" content="text/html;
charset=ISO-8859-1">
Hi Matt.
<div><br>
</div>
<div>Thanks for resurrecting and sorry for not responding on the
original thread.</div>
<div><br>
</div>
<div>Interesting discussions. I would intuitively agree with Bela
were it not for the fact that, as you said, you're actually
storing data, require high availability of that data during
server failure, and may possibly chain tasks (as per a local
fork-join) and want to maintain server affinity across related
tasks.</div>
<div><br>
</div>
<div>You could achieve all of this with JGroups but would end up
re-implementing certain bits of Infinispan, specifically:</div>
<div>- task failover</div>
<div>- task cancelling</div>
<div>- consistent hash based node selection for delivery, ensuring
affinity across data and tasks</div>
<div><br>
</div>
<div>So I think it is a pretty valid use case to make use of what
Infinispan already has.</div>
<div><br>
</div>
<div>I'll have a look at your sources and comment more. I'm sure
Paolo and others at CloudTM will probably do the same.</div>
<div><br>
</div>
<div>Cheers</div>
<div>Manik</div>
<div><br>
</div>
<div>
<div>
<div>On 9 May 2013, at 01:50, Matt Hoffman <<a
moz-do-not-send="true" href="mailto:matt@mhoffman.org">matt@mhoffman.org</a>>
wrote:</div>
<br class="Apple-interchange-newline">
<blockquote type="cite">
<div dir="ltr">
<div>Resurrecting this topic: I've put some sample code
on my fork here: <a moz-do-not-send="true"
href="https://github.com/matthoffman/infinispan/tree/dfj"
target="_blank">https://github.com/matthoffman/infinispan/tree/dfj</a></div>
<div>There's a README there that offers an overview. I
hope to do some performance comparisons over the
weekend, but in the meantime, the code is there if
you're curious. </div>
<div><br>
</div>
<div>I'm mainly interested whether this is the type of
thing that Infinispan may be interested in, as an
alternative to the current distributed executor (much
like the ForkJoinPool in the JDK is an alternative to a
traditional thread pool). </div>
<div>If so, the next steps would be to do some performance
tests, pick one implementation to move forward with (out
of the 3 prototypes on that branch) and clean it up
sufficiently to be considered for a pull request. </div>
<div><br>
</div>
<div>If its not something that Infinispan is interested
in, then I'll change approaches and make it more
generic, so that it isn't Infinispan-specific and can be
used with other transports. I'm open to either option...
I think there are pros and cons either way. </div>
<div><br>
</div>
<div><br>
</div>
<div>Thanks!</div>
<div><br>
</div>
<div><br>
</div>
<div>matt</div>
<div><br>
</div>
</div>
<div class="gmail_extra"><br>
<br>
<div class="gmail_quote">On Mon, Mar 4, 2013 at 7:07 AM,
Paolo Romano <span dir="ltr"><<a
moz-do-not-send="true"
href="mailto:romano@inesc-id.pt" target="_blank">romano@inesc-id.pt</a>></span>
wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">
<div bgcolor="#FFFFFF" text="#000000">
<div>This sounds really interesting Matt. In the
Cloud-TM project (<a moz-do-not-send="true"
href="http://www.cloudtm.eu/" target="_blank">www.cloudtm.eu</a>)
we are currently developing a parallel
graph-analysis algorithm on top of Infinispan's
DEF. I would be really curious to take a look at
the framework you developed, and see how it could
be exploited in our application.<br>
<br>
Regards,<br>
<br>
Paolo<span class="HOEnZb"><font
color="#888888"><br>
<br>
<br>
<pre cols="72">--
Paolo Romano, PhD
Coordinator of the Cloud-TM ICT FP7 Project (<a moz-do-not-send="true" href="http://www.cloudtm.eu/" target="_blank">www.cloudtm.eu</a>)
Senior Researcher @ INESC-ID (<a moz-do-not-send="true" href="http://www.inesc-id.pt/" target="_blank">www.inesc-id.pt</a>)
Assistant Professor @ Instituto Superior Tecnico (<a moz-do-not-send="true" href="http://www.ist.utl.pt/" target="_blank">www.ist.utl.pt</a>)
Rua Alves Redol, 9
1000-059, Lisbon Portugal
Tel. <a moz-do-not-send="true" href="tel:%2B%20351%2021%203100300" value="+351213100300" target="_blank">+ 351 21 3100300</a>
Fax <a moz-do-not-send="true" href="tel:%2B%20351%2021%203145843" value="+351213145843" target="_blank">+ 351 21 3145843</a>
Webpage <a moz-do-not-send="true" href="http://www.gsd.inesc-id.pt/%7Eromanop" target="_blank">http://www.gsd.inesc-id.pt/~romanop</a></pre>
</font></span>
<div class="im"> <br>
<br>
On 3/2/13 5:40 PM, matt hoffman wrote:<br>
</div>
</div>
<blockquote type="cite">
<div>
<div class="h5">
<p>Hey guys, </p>
<p>I've been working on a prototype of
integrating Infinispan into our app. We do
a lot of distributed processing across a
small cluster, so I've played with
Infinispan's existing distributed execution
framework (which is nice), as well as using
Infinispan alongside a normal message queue
to distribute tasks. But I've also put
together a prototype of a new distributed
execution framework using fork-join pools
that you all might be interested in. If it
sounds like something that would be
worthwhile for Infinispan, I can raise a
Jira and submit a pull request with what I
have so far. I'd need to get the CA and
company policy stuff finalized; that might
take a couple days. Meanwhile, in case there
is any interest, I've described the approach
I've taken below.</p>
<p>First, a little background:</p>
<p>A while back I worked on a side project
that integrated a distributed work-stealing
algorithm into the standard JDK fork-join
queue. It used JGroups for communication,
because it was quick and easy for
prototyping. So this week I thought i'd take
a stab at porting that over to Infinispan.
The algorithm I came up with for Infinispan
is a bit less of a work-stealing algorithm,
to take advantage of Infinispan's built-in
distribution capabilities, but I think it's
still fairly efficient. </p>
<p>My basic approach was to take in a cache in
the constructor, much like the existing
distributed executor, and then create a
parallel, DIST-mode cache that uses the same
hash & grouping configuration as the
original cache. That new parallel cache is
the "task cache", and we use that to
distribute available tasks across the
cluster. It's a distributed cache so that
tasks are partitioned across a large
cluster, and it uses the hashing config of
the original cache and a KeyAffinityService
to attempt to distribute the tasks to the
same nodes that contain the data being
worked on. Nodes use cache listeners to be
notified when there is new work available,
and the atomic replace() to "check out" the
tasks for execution, and "check in" the
results. </p>
<p>The basic algorithm is something like
this: </p>
<p>For a refresher, a normal FJ pool has a
fork() method that takes in a task, and then
places that task on an internal queue
(actually, one of several queues). When
threads are idle, they look to the nearest
work queue for work. If that work queue does
not have work, they "steal" work from
another thread's queue. So in the best
case, tasks remain on the same thread as the
task that spawned them, so tasks that
process the same data as their parents may
still have that data in the CPU's cache,
etc. There's more to it than that, but
that's the basic idea. </p>
<p>This distributed algorithm just adds an
extra layer on top for tasks that are marked
"distributable" (by extending
DistributedFJTask instead of the normal
ForkJoinTask). When you call fork() with a
DistributedFJTask, it first checks to see if
the local pool's work queue is empty. If so,
we just go ahead and submit it locally;
there's no reason to distribute it. If not,
we put the task in the task cache, and let
Infinispan distribute it. When a node has no
more work to do in its internal fork-join
queues, it looks at the task cache and tries
to pull work from there. </p>
<p>So, it isn't really a "work-stealing"
algorithm, per se; the distributable tasks
are being distributed eagerly using
Infinispan's normal cache distribution. But
I'm hoping that doing that also makes it
easier to handle node failure, since nodes
collectively share a common picture of the
work to be done.</p>
<p>This approach required one change to the
actual FJ classes themselves (in <span>org.infinispan.util.concurrent.jdk8backported).
</span>That's probably the most
controversial change. I had to make the
original ForkJoinTask's fork() method
non-final in order to extend it cleanly.
There's probably a way around that, but
that's the cleanest option I have thought of
thus far. </p>
<p>And lastly, it's not done yet: basic task
distribution is working, but I haven't
tackled failover to any real extent yet. The
biggest questions, though, are around what
to do with the existing distributed
execution interfaces. For example,
DistributedTask has a getCallable() method
because it assumes it's wrapping a Callable.
But ForkJoinTasks don't extend Callable. I
could put in a shim to wrap the
DistributedFJTasks into Callables for the
sake of that method, but I don't know if
it's worth it. Similarly, the
DistributedExecutorService interface exposes
a lot of submit-to-specific-address or
submit-to-all-addresses methods, which are
an odd fit here since tasks are distributed
via their own cache. Even if I used a
KeyAffinityService to target the task to the
given Address, it might get picked up by
another node that shares that same hash. But
I can add in a direct-to-single-Address
capability in if that seems worthwhile.
Alternately, I can just use entirely
different interfaces
(DistributedFJExecutorService,
DistributedFJTask?). </p>
<p>Thoughts? Concerns? Glaring issues? </p>
<br>
<fieldset></fieldset>
<br>
</div>
</div>
<div class="im">
<pre>_______________________________________________
infinispan-dev mailing list
<a moz-do-not-send="true" href="mailto:infinispan-dev@lists.jboss.org" target="_blank">infinispan-dev@lists.jboss.org</a>
<a moz-do-not-send="true" href="https://lists.jboss.org/mailman/listinfo/infinispan-dev" target="_blank">https://lists.jboss.org/mailman/listinfo/infinispan-dev</a></pre>
</div>
</blockquote>
<br>
</div>
<br>
_______________________________________________<br>
infinispan-dev mailing list<br>
<a moz-do-not-send="true"
href="mailto:infinispan-dev@lists.jboss.org">infinispan-dev@lists.jboss.org</a><br>
<a moz-do-not-send="true"
href="https://lists.jboss.org/mailman/listinfo/infinispan-dev"
target="_blank">https://lists.jboss.org/mailman/listinfo/infinispan-dev</a><br>
</blockquote>
</div>
<br>
</div>
_______________________________________________<br>
infinispan-dev mailing list<br>
<a moz-do-not-send="true"
href="mailto:infinispan-dev@lists.jboss.org">infinispan-dev@lists.jboss.org</a><br>
<a class="moz-txt-link-freetext" href="https://lists.jboss.org/mailman/listinfo/infinispan-dev">https://lists.jboss.org/mailman/listinfo/infinispan-dev</a></blockquote>
</div>
<br>
<div apple-content-edited="true">
<span class="Apple-style-span" style="border-collapse:
separate; color: rgb(0, 0, 0); font-family: Helvetica;
font-style: normal; font-variant: normal; font-weight:
normal; letter-spacing: normal; line-height: normal;
orphans: 2; text-align: -webkit-auto; text-indent: 0px;
text-transform: none; white-space: normal; widows: 2;
word-spacing: 0px; border-spacing: 0px;
-webkit-text-decorations-in-effect: none;
-webkit-text-size-adjust: auto; -webkit-text-stroke-width:
0px; font-size: medium; ">
<div style="word-wrap: break-word; -webkit-nbsp-mode: space;
-webkit-line-break: after-white-space; "><span
class="Apple-style-span" style="border-collapse:
separate; color: rgb(0, 0, 0); font-family: Helvetica;
font-style: normal; font-variant: normal; font-weight:
normal; letter-spacing: normal; line-height: normal;
orphans: 2; text-align: -webkit-auto; text-indent: 0px;
text-transform: none; white-space: normal; widows: 2;
word-spacing: 0px; border-spacing: 0px;
-webkit-text-decorations-in-effect: none;
-webkit-text-size-adjust: auto;
-webkit-text-stroke-width: 0px; font-size: medium; ">
<div style="word-wrap: break-word; -webkit-nbsp-mode:
space; -webkit-line-break: after-white-space; "><span
class="Apple-style-span" style="border-collapse:
separate; color: rgb(0, 0, 0); font-family:
Helvetica; font-style: normal; font-variant: normal;
font-weight: normal; letter-spacing: normal;
line-height: normal; orphans: 2; text-indent: 0px;
text-transform: none; white-space: normal; widows:
2; word-spacing: 0px; border-spacing: 0px;
-webkit-text-decorations-in-effect: none;
-webkit-text-size-adjust: auto;
-webkit-text-stroke-width: 0px; font-size: medium; ">
<div style="word-wrap: break-word;
-webkit-nbsp-mode: space; -webkit-line-break:
after-white-space; ">
<div>--</div>
<div>Manik Surtani</div>
<div><a moz-do-not-send="true"
href="mailto:manik@jboss.org">manik@jboss.org</a></div>
<div><a moz-do-not-send="true"
href="http://twitter.com/maniksurtani">twitter.com/maniksurtani</a></div>
<div><br>
</div>
<div>
<div>Platform Architect, JBoss Data Grid</div>
<div><a moz-do-not-send="true"
href="http://red.ht/data-grid">http://red.ht/data-grid</a></div>
</div>
</div>
</span></div>
</span></div>
</span>
</div>
<br>
</div>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<br>
<pre wrap="">_______________________________________________
infinispan-dev mailing list
<a class="moz-txt-link-abbreviated" href="mailto:infinispan-dev@lists.jboss.org">infinispan-dev@lists.jboss.org</a>
<a class="moz-txt-link-freetext" href="https://lists.jboss.org/mailman/listinfo/infinispan-dev">https://lists.jboss.org/mailman/listinfo/infinispan-dev</a></pre>
</blockquote>
<br>
</body>
</html>