You are viewing a plain text version of this content. The canonical link for it is here.
Posted to common-user@hadoop.apache.org by Jane Wayne <ja...@gmail.com> on 2012/09/26 17:36:09 UTC
strategies to share information between mapreduce tasks
hi,
i know that some algorithms cannot be parallelized and adapted to the
mapreduce paradigm. however, i have noticed that in most cases where i
find myself struggling to express an algorithm in mapreduce, the
problem is mainly due to no ability to cross-communicate between
mappers or reducers.
one naive approach i've seen mentioned here and elsewhere, is to use a
database to store data for use by all the mappers. however, i have
seen many arguments (that i agree with largely) against this approach.
in general, my question is this: has anyone tried to implement an
algorithm using mapreduce where mappers required cross-communications?
how did you solve this limitation of mapreduce?
thanks,
jane.
Re: strategies to share information between mapreduce tasks
Posted by Jane Wayne <ja...@gmail.com>.
thanks. those issues pointed out do cover the pain points i'm experiencing.
On Wed, Sep 26, 2012 at 3:11 PM, Harsh J <ha...@cloudera.com> wrote:
> Also read: http://arxiv.org/abs/1209.2191 ;-)
>
> On Thu, Sep 27, 2012 at 12:24 AM, Bertrand Dechoux <de...@gmail.com> wrote:
>> I wouldn't so surprised. It takes times, energy and money to solve problems
>> and make solutions that would be prod-ready. A few people would consider
>> that the namenode/secondary spof is a limit for Hadoop itself in order to
>> go into a critical production environnement. (I am only quoting it and
>> don't want to start a discussion about it.)
>>
>> One paper that I heard about (but didn't have the time to read as of now)
>> might be related to your problem space
>> http://arxiv.org/abs/1110.4198
>> But research paper does not mean prod ready for tomorrow.
>>
>> http://research.google.com/archive/mapreduce.html is from 2004.
>> and http://research.google.com/pubs/pub36632.html (dremel) is from 2010.
>>
>> Regards
>>
>> Bertrand
>>
>> On Wed, Sep 26, 2012 at 8:18 PM, Jane Wayne <ja...@gmail.com>wrote:
>>
>>> jay,
>>>
>>> thanks. i just needed a sanity check. i hope and expect that one day,
>>> hadoop will mature towards supporting a "shared-something" approach.
>>> the web service call is not a bad idea at all. that way, we can
>>> abstract what that ultimate data store really is.
>>>
>>> i'm just a little surprised that we are still in the same state with
>>> hadoop in regards to this issue (there are probably higher priorities)
>>> and that no research (that i know of) has come out of academia to
>>> mitigate some of these limitations of hadoop (where's all the funding
>>> to hadoop/mapreduce research gone to if this framework is the
>>> fundamental building block of a vast amount of knowledge mining
>>> activities?).
>>>
>>> On Wed, Sep 26, 2012 at 12:40 PM, Jay Vyas <ja...@gmail.com> wrote:
>>> > The reason this is so rare is that the nature of map/reduce tasks is that
>>> > they are orthogonal i.e. the word count, batch image recognition, tera
>>> > sort -- all the things hadoop is famous for are largely orthogonal tasks.
>>> > Its much more rare (i think) to see people using hadoop to do traffic
>>> > simulations or solve protein folding problems... Because those tasks
>>> > require continuous signal integration.
>>> >
>>> > 1) First, try to consider rewriting it so that ll communication is
>>> replaced
>>> > by state variables in a reducer, and choose your keys wisely, so that all
>>> > "communication" between machines is obviated by the fact that a single
>>> > reducer is receiving all the information relevant for it to do its task.
>>> >
>>> > 2) If a small amount of state needs to be preserved or cached in real
>>> time
>>> > two optimize the situation where two machines might dont have to redo the
>>> > same task (i.e. invoke a web service to get a peice of data, or some
>>> other
>>> > task that needs to be rate limited and not duplicated) then you can use a
>>> > fast key value store (like you suggested) like the ones provided by
>>> basho (
>>> > http://basho.com/) or amazon (Dynamo).
>>> >
>>> > 3) If you really need alot of message passing, then then you might be
>>> > better of using an inherently more integrated tool like GridGain... which
>>> > allows for sophisticated message passing between asynchronously running
>>> > processes, i.e.
>>> >
>>> http://gridgaintech.wordpress.com/2011/01/26/distributed-actors-in-gridgain/
>>> .
>>> >
>>> >
>>> > It seems like there might not be a reliable way to implement a
>>> > sophisticated message passing architecutre in hadoop, because the system
>>> is
>>> > inherently so dynamic, and is built for rapid streaming reads/writes,
>>> which
>>> > would be stifled by significant communication overhead.
>>>
>>
>>
>>
>> --
>> Bertrand Dechoux
>
>
>
> --
> Harsh J
Re: strategies to share information between mapreduce tasks
Posted by Harsh J <ha...@cloudera.com>.
Also read: http://arxiv.org/abs/1209.2191 ;-)
On Thu, Sep 27, 2012 at 12:24 AM, Bertrand Dechoux <de...@gmail.com> wrote:
> I wouldn't so surprised. It takes times, energy and money to solve problems
> and make solutions that would be prod-ready. A few people would consider
> that the namenode/secondary spof is a limit for Hadoop itself in order to
> go into a critical production environnement. (I am only quoting it and
> don't want to start a discussion about it.)
>
> One paper that I heard about (but didn't have the time to read as of now)
> might be related to your problem space
> http://arxiv.org/abs/1110.4198
> But research paper does not mean prod ready for tomorrow.
>
> http://research.google.com/archive/mapreduce.html is from 2004.
> and http://research.google.com/pubs/pub36632.html (dremel) is from 2010.
>
> Regards
>
> Bertrand
>
> On Wed, Sep 26, 2012 at 8:18 PM, Jane Wayne <ja...@gmail.com>wrote:
>
>> jay,
>>
>> thanks. i just needed a sanity check. i hope and expect that one day,
>> hadoop will mature towards supporting a "shared-something" approach.
>> the web service call is not a bad idea at all. that way, we can
>> abstract what that ultimate data store really is.
>>
>> i'm just a little surprised that we are still in the same state with
>> hadoop in regards to this issue (there are probably higher priorities)
>> and that no research (that i know of) has come out of academia to
>> mitigate some of these limitations of hadoop (where's all the funding
>> to hadoop/mapreduce research gone to if this framework is the
>> fundamental building block of a vast amount of knowledge mining
>> activities?).
>>
>> On Wed, Sep 26, 2012 at 12:40 PM, Jay Vyas <ja...@gmail.com> wrote:
>> > The reason this is so rare is that the nature of map/reduce tasks is that
>> > they are orthogonal i.e. the word count, batch image recognition, tera
>> > sort -- all the things hadoop is famous for are largely orthogonal tasks.
>> > Its much more rare (i think) to see people using hadoop to do traffic
>> > simulations or solve protein folding problems... Because those tasks
>> > require continuous signal integration.
>> >
>> > 1) First, try to consider rewriting it so that ll communication is
>> replaced
>> > by state variables in a reducer, and choose your keys wisely, so that all
>> > "communication" between machines is obviated by the fact that a single
>> > reducer is receiving all the information relevant for it to do its task.
>> >
>> > 2) If a small amount of state needs to be preserved or cached in real
>> time
>> > two optimize the situation where two machines might dont have to redo the
>> > same task (i.e. invoke a web service to get a peice of data, or some
>> other
>> > task that needs to be rate limited and not duplicated) then you can use a
>> > fast key value store (like you suggested) like the ones provided by
>> basho (
>> > http://basho.com/) or amazon (Dynamo).
>> >
>> > 3) If you really need alot of message passing, then then you might be
>> > better of using an inherently more integrated tool like GridGain... which
>> > allows for sophisticated message passing between asynchronously running
>> > processes, i.e.
>> >
>> http://gridgaintech.wordpress.com/2011/01/26/distributed-actors-in-gridgain/
>> .
>> >
>> >
>> > It seems like there might not be a reliable way to implement a
>> > sophisticated message passing architecutre in hadoop, because the system
>> is
>> > inherently so dynamic, and is built for rapid streaming reads/writes,
>> which
>> > would be stifled by significant communication overhead.
>>
>
>
>
> --
> Bertrand Dechoux
--
Harsh J
Re: strategies to share information between mapreduce tasks
Posted by Bertrand Dechoux <de...@gmail.com>.
I wouldn't so surprised. It takes times, energy and money to solve problems
and make solutions that would be prod-ready. A few people would consider
that the namenode/secondary spof is a limit for Hadoop itself in order to
go into a critical production environnement. (I am only quoting it and
don't want to start a discussion about it.)
One paper that I heard about (but didn't have the time to read as of now)
might be related to your problem space
http://arxiv.org/abs/1110.4198
But research paper does not mean prod ready for tomorrow.
http://research.google.com/archive/mapreduce.html is from 2004.
and http://research.google.com/pubs/pub36632.html (dremel) is from 2010.
Regards
Bertrand
On Wed, Sep 26, 2012 at 8:18 PM, Jane Wayne <ja...@gmail.com>wrote:
> jay,
>
> thanks. i just needed a sanity check. i hope and expect that one day,
> hadoop will mature towards supporting a "shared-something" approach.
> the web service call is not a bad idea at all. that way, we can
> abstract what that ultimate data store really is.
>
> i'm just a little surprised that we are still in the same state with
> hadoop in regards to this issue (there are probably higher priorities)
> and that no research (that i know of) has come out of academia to
> mitigate some of these limitations of hadoop (where's all the funding
> to hadoop/mapreduce research gone to if this framework is the
> fundamental building block of a vast amount of knowledge mining
> activities?).
>
> On Wed, Sep 26, 2012 at 12:40 PM, Jay Vyas <ja...@gmail.com> wrote:
> > The reason this is so rare is that the nature of map/reduce tasks is that
> > they are orthogonal i.e. the word count, batch image recognition, tera
> > sort -- all the things hadoop is famous for are largely orthogonal tasks.
> > Its much more rare (i think) to see people using hadoop to do traffic
> > simulations or solve protein folding problems... Because those tasks
> > require continuous signal integration.
> >
> > 1) First, try to consider rewriting it so that ll communication is
> replaced
> > by state variables in a reducer, and choose your keys wisely, so that all
> > "communication" between machines is obviated by the fact that a single
> > reducer is receiving all the information relevant for it to do its task.
> >
> > 2) If a small amount of state needs to be preserved or cached in real
> time
> > two optimize the situation where two machines might dont have to redo the
> > same task (i.e. invoke a web service to get a peice of data, or some
> other
> > task that needs to be rate limited and not duplicated) then you can use a
> > fast key value store (like you suggested) like the ones provided by
> basho (
> > http://basho.com/) or amazon (Dynamo).
> >
> > 3) If you really need alot of message passing, then then you might be
> > better of using an inherently more integrated tool like GridGain... which
> > allows for sophisticated message passing between asynchronously running
> > processes, i.e.
> >
> http://gridgaintech.wordpress.com/2011/01/26/distributed-actors-in-gridgain/
> .
> >
> >
> > It seems like there might not be a reliable way to implement a
> > sophisticated message passing architecutre in hadoop, because the system
> is
> > inherently so dynamic, and is built for rapid streaming reads/writes,
> which
> > would be stifled by significant communication overhead.
>
--
Bertrand Dechoux
Re: strategies to share information between mapreduce tasks
Posted by Jane Wayne <ja...@gmail.com>.
jay,
thanks. i just needed a sanity check. i hope and expect that one day,
hadoop will mature towards supporting a "shared-something" approach.
the web service call is not a bad idea at all. that way, we can
abstract what that ultimate data store really is.
i'm just a little surprised that we are still in the same state with
hadoop in regards to this issue (there are probably higher priorities)
and that no research (that i know of) has come out of academia to
mitigate some of these limitations of hadoop (where's all the funding
to hadoop/mapreduce research gone to if this framework is the
fundamental building block of a vast amount of knowledge mining
activities?).
On Wed, Sep 26, 2012 at 12:40 PM, Jay Vyas <ja...@gmail.com> wrote:
> The reason this is so rare is that the nature of map/reduce tasks is that
> they are orthogonal i.e. the word count, batch image recognition, tera
> sort -- all the things hadoop is famous for are largely orthogonal tasks.
> Its much more rare (i think) to see people using hadoop to do traffic
> simulations or solve protein folding problems... Because those tasks
> require continuous signal integration.
>
> 1) First, try to consider rewriting it so that ll communication is replaced
> by state variables in a reducer, and choose your keys wisely, so that all
> "communication" between machines is obviated by the fact that a single
> reducer is receiving all the information relevant for it to do its task.
>
> 2) If a small amount of state needs to be preserved or cached in real time
> two optimize the situation where two machines might dont have to redo the
> same task (i.e. invoke a web service to get a peice of data, or some other
> task that needs to be rate limited and not duplicated) then you can use a
> fast key value store (like you suggested) like the ones provided by basho (
> http://basho.com/) or amazon (Dynamo).
>
> 3) If you really need alot of message passing, then then you might be
> better of using an inherently more integrated tool like GridGain... which
> allows for sophisticated message passing between asynchronously running
> processes, i.e.
> http://gridgaintech.wordpress.com/2011/01/26/distributed-actors-in-gridgain/.
>
>
> It seems like there might not be a reliable way to implement a
> sophisticated message passing architecutre in hadoop, because the system is
> inherently so dynamic, and is built for rapid streaming reads/writes, which
> would be stifled by significant communication overhead.
Re: strategies to share information between mapreduce tasks
Posted by Jay Vyas <ja...@gmail.com>.
The reason this is so rare is that the nature of map/reduce tasks is that
they are orthogonal i.e. the word count, batch image recognition, tera
sort -- all the things hadoop is famous for are largely orthogonal tasks.
Its much more rare (i think) to see people using hadoop to do traffic
simulations or solve protein folding problems... Because those tasks
require continuous signal integration.
1) First, try to consider rewriting it so that ll communication is replaced
by state variables in a reducer, and choose your keys wisely, so that all
"communication" between machines is obviated by the fact that a single
reducer is receiving all the information relevant for it to do its task.
2) If a small amount of state needs to be preserved or cached in real time
two optimize the situation where two machines might dont have to redo the
same task (i.e. invoke a web service to get a peice of data, or some other
task that needs to be rate limited and not duplicated) then you can use a
fast key value store (like you suggested) like the ones provided by basho (
http://basho.com/) or amazon (Dynamo).
3) If you really need alot of message passing, then then you might be
better of using an inherently more integrated tool like GridGain... which
allows for sophisticated message passing between asynchronously running
processes, i.e.
http://gridgaintech.wordpress.com/2011/01/26/distributed-actors-in-gridgain/.
It seems like there might not be a reliable way to implement a
sophisticated message passing architecutre in hadoop, because the system is
inherently so dynamic, and is built for rapid streaming reads/writes, which
would be stifled by significant communication overhead.
Re: strategies to share information between mapreduce tasks
Posted by Harsh J <ha...@cloudera.com>.
Apache Giraph is a framework for graph processing, currently runs over
"MR" (but is getting its own coordination via YARN soon):
http://giraph.apache.org.
You may also checkout the generic BSP system (Giraph uses BSP too, if
am not wrong, but doesn't use Hama - works over MR instead), Apache
Hama: http://hama.apache.org
On Wed, Sep 26, 2012 at 9:51 PM, Jane Wayne <ja...@gmail.com> wrote:
> i'll look for myself, but could you please let me know what is giraph?
> is it another layer on hadoop like hive/pig or an api like mahout?
>
>
>
> On Wed, Sep 26, 2012 at 12:09 PM, Jonathan Bishop <jb...@gmail.com> wrote:
>> Yes, Giraph seems like the best way to go - it is mainly a vertex
>> evaluation with message passing between vertices. Synchronization is
>> handled for you.
>>
>> On Wed, Sep 26, 2012 at 8:36 AM, Jane Wayne <ja...@gmail.com>wrote:
>>
>>> hi,
>>>
>>> i know that some algorithms cannot be parallelized and adapted to the
>>> mapreduce paradigm. however, i have noticed that in most cases where i
>>> find myself struggling to express an algorithm in mapreduce, the
>>> problem is mainly due to no ability to cross-communicate between
>>> mappers or reducers.
>>>
>>> one naive approach i've seen mentioned here and elsewhere, is to use a
>>> database to store data for use by all the mappers. however, i have
>>> seen many arguments (that i agree with largely) against this approach.
>>>
>>> in general, my question is this: has anyone tried to implement an
>>> algorithm using mapreduce where mappers required cross-communications?
>>> how did you solve this limitation of mapreduce?
>>>
>>> thanks,
>>>
>>> jane.
>>>
--
Harsh J
Re: strategies to share information between mapreduce tasks
Posted by Jane Wayne <ja...@gmail.com>.
i'll look for myself, but could you please let me know what is giraph?
is it another layer on hadoop like hive/pig or an api like mahout?
On Wed, Sep 26, 2012 at 12:09 PM, Jonathan Bishop <jb...@gmail.com> wrote:
> Yes, Giraph seems like the best way to go - it is mainly a vertex
> evaluation with message passing between vertices. Synchronization is
> handled for you.
>
> On Wed, Sep 26, 2012 at 8:36 AM, Jane Wayne <ja...@gmail.com>wrote:
>
>> hi,
>>
>> i know that some algorithms cannot be parallelized and adapted to the
>> mapreduce paradigm. however, i have noticed that in most cases where i
>> find myself struggling to express an algorithm in mapreduce, the
>> problem is mainly due to no ability to cross-communicate between
>> mappers or reducers.
>>
>> one naive approach i've seen mentioned here and elsewhere, is to use a
>> database to store data for use by all the mappers. however, i have
>> seen many arguments (that i agree with largely) against this approach.
>>
>> in general, my question is this: has anyone tried to implement an
>> algorithm using mapreduce where mappers required cross-communications?
>> how did you solve this limitation of mapreduce?
>>
>> thanks,
>>
>> jane.
>>
Re: strategies to share information between mapreduce tasks
Posted by Jonathan Bishop <jb...@gmail.com>.
Yes, Giraph seems like the best way to go - it is mainly a vertex
evaluation with message passing between vertices. Synchronization is
handled for you.
On Wed, Sep 26, 2012 at 8:36 AM, Jane Wayne <ja...@gmail.com>wrote:
> hi,
>
> i know that some algorithms cannot be parallelized and adapted to the
> mapreduce paradigm. however, i have noticed that in most cases where i
> find myself struggling to express an algorithm in mapreduce, the
> problem is mainly due to no ability to cross-communicate between
> mappers or reducers.
>
> one naive approach i've seen mentioned here and elsewhere, is to use a
> database to store data for use by all the mappers. however, i have
> seen many arguments (that i agree with largely) against this approach.
>
> in general, my question is this: has anyone tried to implement an
> algorithm using mapreduce where mappers required cross-communications?
> how did you solve this limitation of mapreduce?
>
> thanks,
>
> jane.
>
Re: strategies to share information between mapreduce tasks
Posted by Andrew Purtell <ap...@apache.org>.
HBase is usually distributed with Hadoop, well integrated with the
platform, and use of it in MapReduce applications is quite common.
On Wednesday, September 26, 2012, Jane Wayne wrote:
> my problem is more general (than graph problems) and doesn't need to
> have logic built around synchronization or failure. for example, when
> a mapper is finished successfully, it just writes/persists to a
> storage location (could be disk, could be database, could be memory,
> etc...). when the next input is processed (could be on the same mapper
> or different mapper), i just need to do a lookup from the storage
> location (that is accessible by all task nodes). if the mapper fails,
> this doesn't hurt my processing, although i would like for no failures
> (and it's good if hadoop can spawn another task to mitigate).
>
>
>
> On Wed, Sep 26, 2012 at 11:43 AM, Bertrand Dechoux <dechouxb@gmail.com<javascript:;>>
> wrote:
> > The difficulty with data transfer between tasks is handling
> synchronisation
> > and failure.
> > You may want to look at graph processing done on top of Hadoop (like
> > Giraph).
> > That's one way to do it but whether it is relevant or not to you will
> > depend on your context.
> >
> > Regards
> >
> > Bertrand
> >
> > On Wed, Sep 26, 2012 at 5:36 PM, Jane Wayne <jane.wayne2978@gmail.com<javascript:;>
> >wrote:
> >
> >> hi,
> >>
> >> i know that some algorithms cannot be parallelized and adapted to the
> >> mapreduce paradigm. however, i have noticed that in most cases where i
> >> find myself struggling to express an algorithm in mapreduce, the
> >> problem is mainly due to no ability to cross-communicate between
> >> mappers or reducers.
> >>
> >> one naive approach i've seen mentioned here and elsewhere, is to use a
> >> database to store data for use by all the mappers. however, i have
> >> seen many arguments (that i agree with largely) against this approach.
> >>
> >> in general, my question is this: has anyone tried to implement an
> >> algorithm using mapreduce where mappers required cross-communications?
> >> how did you solve this limitation of mapreduce?
> >>
> >> thanks,
> >>
> >> jane.
> >>
> >
> >
> >
> > --
> > Bertrand Dechoux
>
--
Best regards,
- Andy
Problems worthy of attack prove their worth by hitting back. - Piet Hein
(via Tom White)
Re: strategies to share information between mapreduce tasks
Posted by Jane Wayne <ja...@gmail.com>.
my problem is more general (than graph problems) and doesn't need to
have logic built around synchronization or failure. for example, when
a mapper is finished successfully, it just writes/persists to a
storage location (could be disk, could be database, could be memory,
etc...). when the next input is processed (could be on the same mapper
or different mapper), i just need to do a lookup from the storage
location (that is accessible by all task nodes). if the mapper fails,
this doesn't hurt my processing, although i would like for no failures
(and it's good if hadoop can spawn another task to mitigate).
On Wed, Sep 26, 2012 at 11:43 AM, Bertrand Dechoux <de...@gmail.com> wrote:
> The difficulty with data transfer between tasks is handling synchronisation
> and failure.
> You may want to look at graph processing done on top of Hadoop (like
> Giraph).
> That's one way to do it but whether it is relevant or not to you will
> depend on your context.
>
> Regards
>
> Bertrand
>
> On Wed, Sep 26, 2012 at 5:36 PM, Jane Wayne <ja...@gmail.com>wrote:
>
>> hi,
>>
>> i know that some algorithms cannot be parallelized and adapted to the
>> mapreduce paradigm. however, i have noticed that in most cases where i
>> find myself struggling to express an algorithm in mapreduce, the
>> problem is mainly due to no ability to cross-communicate between
>> mappers or reducers.
>>
>> one naive approach i've seen mentioned here and elsewhere, is to use a
>> database to store data for use by all the mappers. however, i have
>> seen many arguments (that i agree with largely) against this approach.
>>
>> in general, my question is this: has anyone tried to implement an
>> algorithm using mapreduce where mappers required cross-communications?
>> how did you solve this limitation of mapreduce?
>>
>> thanks,
>>
>> jane.
>>
>
>
>
> --
> Bertrand Dechoux
Re: strategies to share information between mapreduce tasks
Posted by Bertrand Dechoux <de...@gmail.com>.
The difficulty with data transfer between tasks is handling synchronisation
and failure.
You may want to look at graph processing done on top of Hadoop (like
Giraph).
That's one way to do it but whether it is relevant or not to you will
depend on your context.
Regards
Bertrand
On Wed, Sep 26, 2012 at 5:36 PM, Jane Wayne <ja...@gmail.com>wrote:
> hi,
>
> i know that some algorithms cannot be parallelized and adapted to the
> mapreduce paradigm. however, i have noticed that in most cases where i
> find myself struggling to express an algorithm in mapreduce, the
> problem is mainly due to no ability to cross-communicate between
> mappers or reducers.
>
> one naive approach i've seen mentioned here and elsewhere, is to use a
> database to store data for use by all the mappers. however, i have
> seen many arguments (that i agree with largely) against this approach.
>
> in general, my question is this: has anyone tried to implement an
> algorithm using mapreduce where mappers required cross-communications?
> how did you solve this limitation of mapreduce?
>
> thanks,
>
> jane.
>
--
Bertrand Dechoux