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 Lukas Vlcek <lu...@gmail.com> on 2008/07/14 23:10:42 UTC
Ideal number of mappers and reducers; any physical limits?
Hi,
I have a couple of *basic* questions about Hadoop internals.
1) If I understood correctly the ideal number of Reducers is equal to number
of distinct keys (or custom Partitioners) emitted from from all Mappers at
given Map-Reduce iteration. Is that correct?
2) In configuration there can be set maximum number of Reducers. How does
Hadoop handle the situation when there are more intermediate keys emitted
from Mappers then this number? AFAIK the intermediate results are stored in
SequenceFiles. Does it mean that this intermetidate persistent storeage is
somehow scanned to all records of the same key (or custom Partinioner value)
and such chunk of data is send to one Reduced and if no Reducer is left them
the process waits unitl some of them is done and can be assigned a new chunk
of data?
3) Is there any recommendation about how to set up a job if number of
intermediate keys is not know beforehand?
4) Is there any physical limit of number of Reducers given by internal
Hadoop architecture?
... and finally ...
5) Does anybody know how and what exactly do folks in Yahoo! use Hadoop for?
If the biggest reported Hadoop cluster has something like 2000 machines then
the total number of Mappers/Reducers can be like 2000*200 (assuming there
are for example 200 Reducers running on each machine), which is a big number
but still probably not big enough to handle processing of really large
graphs data structures IMHO. As far as I understood Google is not directly
using Map-Reduce form of PageRank calculation for whole internet graph
processing (see http://www.youtube.com/watch?v=BT-piFBP4fE). So, if Yahoo!
needs scaling algorithm for really large tasks, what do they use if not
Hadoop?
Regards,
Lukas
--
http://blog.lukas-vlcek.com/
Re: Ideal number of mappers and reducers; any physical limits?
Posted by "Edward J. Yoon" <ed...@apache.org>.
> I doubt that it is stored as an explicit matrix. Each page would probably
> have a big table (or file) entry and would have a list of links including
> link text.
Oh.. Probably, and some random walk on the link graph.
On Wed, Oct 29, 2008 at 2:12 PM, Ted Dunning <te...@gmail.com> wrote:
> On Tue, Oct 28, 2008 at 5:15 PM, Edward J. Yoon <ed...@apache.org>wrote:
>
>> ...
>> In single machine, as far as we
>> know graph can be stored to linked list or matrix.
>>
>
> Since the matrix is normally very sparse for large graphs, these two
> approaches are pretty similar.
>
>
>> ... So, I guess google's web graph will be stored as a matrix in a
>> bigTable.
>>
>
> I doubt that it is stored as an explicit matrix. Each page would probably
> have a big table (or file) entry and would have a list of links including
> link text.
>
>
> Have you seen my 2D block algorithm post?? --
>> http://blog.udanax.org/2008/10/parallel-matrix-multiply-on-hadoop.html
>>
>
> I have now. Block decomposition for multiplies almost always applies only
> to dense matrix operations. For most sparse matrix representations
> extracting a block is only efficient if it is full width or height. For
> very sparse matrix operations, the savings due to reuse of intermediate
> results are completely dominated by the I/O cost so block decompositions are
> much less helpful.
>
> In many cases, it isn't even very helpful to send around entire rows and
> sending individual elements is about as efficient.
>
> FYI, Hama (http://incubator.apache.org/hama/) will be handled graph
>> algorithms since it is a related with adjacency matrix and topological
>> algebra. And I think 2000 node hadoop/hbase cluster is big enough if a
>> sequential/random read/write speed will be improved 800%. :-)
>>
>
> I think that a 5 node cluster is big enough without any improvement in
> read/write speed.
>
> Of course, it depends on the size of the problem. I was only working with a
> matrix with a few tens of billions of non-zero values.
>
--
Best regards, Edward J. Yoon
edwardyoon@apache.org
http://blog.udanax.org
Re: Ideal number of mappers and reducers; any physical limits?
Posted by "Edward J. Yoon" <ed...@apache.org>.
> extracting a block is only efficient if it is full width or height. For
> very sparse matrix operations, the savings due to reuse of intermediate
> results are completely dominated by the I/O cost so block decompositions are
> much less helpful.
Hmm, Yes. Thanks for your great comments. :-)
> Of course, it depends on the size of the problem. I was only working with a
> matrix with a few tens of billions of non-zero values.
It seems extremely large sparse matrix. What kind of operation is big
enough on 5 machine ??
/Edward
On Wed, Oct 29, 2008 at 2:12 PM, Ted Dunning <te...@gmail.com> wrote:
> On Tue, Oct 28, 2008 at 5:15 PM, Edward J. Yoon <ed...@apache.org>wrote:
>
>> ...
>> In single machine, as far as we
>> know graph can be stored to linked list or matrix.
>>
>
> Since the matrix is normally very sparse for large graphs, these two
> approaches are pretty similar.
>
>
>> ... So, I guess google's web graph will be stored as a matrix in a
>> bigTable.
>>
>
> I doubt that it is stored as an explicit matrix. Each page would probably
> have a big table (or file) entry and would have a list of links including
> link text.
>
>
> Have you seen my 2D block algorithm post?? --
>> http://blog.udanax.org/2008/10/parallel-matrix-multiply-on-hadoop.html
>>
>
> I have now. Block decomposition for multiplies almost always applies only
> to dense matrix operations. For most sparse matrix representations
> extracting a block is only efficient if it is full width or height. For
> very sparse matrix operations, the savings due to reuse of intermediate
> results are completely dominated by the I/O cost so block decompositions are
> much less helpful.
>
> In many cases, it isn't even very helpful to send around entire rows and
> sending individual elements is about as efficient.
>
> FYI, Hama (http://incubator.apache.org/hama/) will be handled graph
>> algorithms since it is a related with adjacency matrix and topological
>> algebra. And I think 2000 node hadoop/hbase cluster is big enough if a
>> sequential/random read/write speed will be improved 800%. :-)
>>
>
> I think that a 5 node cluster is big enough without any improvement in
> read/write speed.
>
> Of course, it depends on the size of the problem. I was only working with a
> matrix with a few tens of billions of non-zero values.
>
--
Best regards, Edward J. Yoon
edwardyoon@apache.org
http://blog.udanax.org
Re: Ideal number of mappers and reducers; any physical limits?
Posted by "Edward J. Yoon" <ed...@apache.org>.
> I doubt that it is stored as an explicit matrix. Each page would probably
> have a big table (or file) entry and would have a list of links including
> link text.
Oh.. Probably, and some random walk on the link graph.
On Wed, Oct 29, 2008 at 2:12 PM, Ted Dunning <te...@gmail.com> wrote:
> On Tue, Oct 28, 2008 at 5:15 PM, Edward J. Yoon <ed...@apache.org>wrote:
>
>> ...
>> In single machine, as far as we
>> know graph can be stored to linked list or matrix.
>>
>
> Since the matrix is normally very sparse for large graphs, these two
> approaches are pretty similar.
>
>
>> ... So, I guess google's web graph will be stored as a matrix in a
>> bigTable.
>>
>
> I doubt that it is stored as an explicit matrix. Each page would probably
> have a big table (or file) entry and would have a list of links including
> link text.
>
>
> Have you seen my 2D block algorithm post?? --
>> http://blog.udanax.org/2008/10/parallel-matrix-multiply-on-hadoop.html
>>
>
> I have now. Block decomposition for multiplies almost always applies only
> to dense matrix operations. For most sparse matrix representations
> extracting a block is only efficient if it is full width or height. For
> very sparse matrix operations, the savings due to reuse of intermediate
> results are completely dominated by the I/O cost so block decompositions are
> much less helpful.
>
> In many cases, it isn't even very helpful to send around entire rows and
> sending individual elements is about as efficient.
>
> FYI, Hama (http://incubator.apache.org/hama/) will be handled graph
>> algorithms since it is a related with adjacency matrix and topological
>> algebra. And I think 2000 node hadoop/hbase cluster is big enough if a
>> sequential/random read/write speed will be improved 800%. :-)
>>
>
> I think that a 5 node cluster is big enough without any improvement in
> read/write speed.
>
> Of course, it depends on the size of the problem. I was only working with a
> matrix with a few tens of billions of non-zero values.
>
--
Best regards, Edward J. Yoon
edwardyoon@apache.org
http://blog.udanax.org
Re: Ideal number of mappers and reducers; any physical limits?
Posted by Ted Dunning <te...@gmail.com>.
On Tue, Oct 28, 2008 at 5:15 PM, Edward J. Yoon <ed...@apache.org>wrote:
> ...
> In single machine, as far as we
> know graph can be stored to linked list or matrix.
>
Since the matrix is normally very sparse for large graphs, these two
approaches are pretty similar.
> ... So, I guess google's web graph will be stored as a matrix in a
> bigTable.
>
I doubt that it is stored as an explicit matrix. Each page would probably
have a big table (or file) entry and would have a list of links including
link text.
Have you seen my 2D block algorithm post?? --
> http://blog.udanax.org/2008/10/parallel-matrix-multiply-on-hadoop.html
>
I have now. Block decomposition for multiplies almost always applies only
to dense matrix operations. For most sparse matrix representations
extracting a block is only efficient if it is full width or height. For
very sparse matrix operations, the savings due to reuse of intermediate
results are completely dominated by the I/O cost so block decompositions are
much less helpful.
In many cases, it isn't even very helpful to send around entire rows and
sending individual elements is about as efficient.
FYI, Hama (http://incubator.apache.org/hama/) will be handled graph
> algorithms since it is a related with adjacency matrix and topological
> algebra. And I think 2000 node hadoop/hbase cluster is big enough if a
> sequential/random read/write speed will be improved 800%. :-)
>
I think that a 5 node cluster is big enough without any improvement in
read/write speed.
Of course, it depends on the size of the problem. I was only working with a
matrix with a few tens of billions of non-zero values.
Re: Ideal number of mappers and reducers; any physical limits?
Posted by Ted Dunning <te...@gmail.com>.
On Tue, Oct 28, 2008 at 5:15 PM, Edward J. Yoon <ed...@apache.org>wrote:
> ...
> In single machine, as far as we
> know graph can be stored to linked list or matrix.
>
Since the matrix is normally very sparse for large graphs, these two
approaches are pretty similar.
> ... So, I guess google's web graph will be stored as a matrix in a
> bigTable.
>
I doubt that it is stored as an explicit matrix. Each page would probably
have a big table (or file) entry and would have a list of links including
link text.
Have you seen my 2D block algorithm post?? --
> http://blog.udanax.org/2008/10/parallel-matrix-multiply-on-hadoop.html
>
I have now. Block decomposition for multiplies almost always applies only
to dense matrix operations. For most sparse matrix representations
extracting a block is only efficient if it is full width or height. For
very sparse matrix operations, the savings due to reuse of intermediate
results are completely dominated by the I/O cost so block decompositions are
much less helpful.
In many cases, it isn't even very helpful to send around entire rows and
sending individual elements is about as efficient.
FYI, Hama (http://incubator.apache.org/hama/) will be handled graph
> algorithms since it is a related with adjacency matrix and topological
> algebra. And I think 2000 node hadoop/hbase cluster is big enough if a
> sequential/random read/write speed will be improved 800%. :-)
>
I think that a 5 node cluster is big enough without any improvement in
read/write speed.
Of course, it depends on the size of the problem. I was only working with a
matrix with a few tens of billions of non-zero values.
Fwd: Ideal number of mappers and reducers; any physical limits?
Posted by "Edward J. Yoon" <ed...@apache.org>.
Just FWD, so I would also like to hear about some advice about
matrix/graph algorithms from mahout developers..
---------- Forwarded message ----------
From: Edward J. Yoon <ed...@apache.org>
Date: Wed, Oct 29, 2008 at 9:05 AM
Subject: Re: Ideal number of mappers and reducers; any physical limits?
To: core-user@hadoop.apache.org
Hi,
I'm interested in graph algorithms. In single machine, as far as we
know graph can be stored to linked list or matrix. Do you know about
difference benefit between linked list and matrix? So, I guess
google's web graph will be stored as a matrix in a bigTable.
Have you seen my 2D block algorithm post?? --
http://blog.udanax.org/2008/10/parallel-matrix-multiply-on-hadoop.html
Moreover, I believe there is a more efficient and less time-intensive
way even if we use a map/reduce.
FYI, Hama (http://incubator.apache.org/hama/) will be handled graph
algorithms since it is a related with adjacency matrix and topological
algebra. And I think 2000 node hadoop/hbase cluster is big enough if a
sequential/random read/write speed will be improved 800%. :-)
/Edward
On Tue, Jul 15, 2008 at 6:10 AM, Lukas Vlcek <lu...@gmail.com> wrote:
> Hi,
>
> I have a couple of *basic* questions about Hadoop internals.
>
> 1) If I understood correctly the ideal number of Reducers is equal to number
> of distinct keys (or custom Partitioners) emitted from from all Mappers at
> given Map-Reduce iteration. Is that correct?
>
> 2) In configuration there can be set maximum number of Reducers. How does
> Hadoop handle the situation when there are more intermediate keys emitted
> from Mappers then this number? AFAIK the intermediate results are stored in
> SequenceFiles. Does it mean that this intermetidate persistent storeage is
> somehow scanned to all records of the same key (or custom Partinioner value)
> and such chunk of data is send to one Reduced and if no Reducer is left them
> the process waits unitl some of them is done and can be assigned a new chunk
> of data?
>
> 3) Is there any recommendation about how to set up a job if number of
> intermediate keys is not know beforehand?
>
> 4) Is there any physical limit of number of Reducers given by internal
> Hadoop architecture?
>
> ... and finally ...
>
> 5) Does anybody know how and what exactly do folks in Yahoo! use Hadoop for?
> If the biggest reported Hadoop cluster has something like 2000 machines then
> the total number of Mappers/Reducers can be like 2000*200 (assuming there
> are for example 200 Reducers running on each machine), which is a big number
> but still probably not big enough to handle processing of really large
> graphs data structures IMHO. As far as I understood Google is not directly
> using Map-Reduce form of PageRank calculation for whole internet graph
> processing (see http://www.youtube.com/watch?v=BT-piFBP4fE). So, if Yahoo!
> needs scaling algorithm for really large tasks, what do they use if not
> Hadoop?
>
> Regards,
> Lukas
>
> --
> http://blog.lukas-vlcek.com/
>
--
Best regards, Edward J. Yoon
edwardyoon@apache.org
http://blog.udanax.org
--
Best regards, Edward J. Yoon
edwardyoon@apache.org
http://blog.udanax.org
Re: Ideal number of mappers and reducers; any physical limits?
Posted by "Edward J. Yoon" <ed...@apache.org>.
Hi,
I'm interested in graph algorithms. In single machine, as far as we
know graph can be stored to linked list or matrix. Do you know about
difference benefit between linked list and matrix? So, I guess
google's web graph will be stored as a matrix in a bigTable.
Have you seen my 2D block algorithm post?? --
http://blog.udanax.org/2008/10/parallel-matrix-multiply-on-hadoop.html
Moreover, I believe there is a more efficient and less time-intensive
way even if we use a map/reduce.
FYI, Hama (http://incubator.apache.org/hama/) will be handled graph
algorithms since it is a related with adjacency matrix and topological
algebra. And I think 2000 node hadoop/hbase cluster is big enough if a
sequential/random read/write speed will be improved 800%. :-)
/Edward
On Tue, Jul 15, 2008 at 6:10 AM, Lukas Vlcek <lu...@gmail.com> wrote:
> Hi,
>
> I have a couple of *basic* questions about Hadoop internals.
>
> 1) If I understood correctly the ideal number of Reducers is equal to number
> of distinct keys (or custom Partitioners) emitted from from all Mappers at
> given Map-Reduce iteration. Is that correct?
>
> 2) In configuration there can be set maximum number of Reducers. How does
> Hadoop handle the situation when there are more intermediate keys emitted
> from Mappers then this number? AFAIK the intermediate results are stored in
> SequenceFiles. Does it mean that this intermetidate persistent storeage is
> somehow scanned to all records of the same key (or custom Partinioner value)
> and such chunk of data is send to one Reduced and if no Reducer is left them
> the process waits unitl some of them is done and can be assigned a new chunk
> of data?
>
> 3) Is there any recommendation about how to set up a job if number of
> intermediate keys is not know beforehand?
>
> 4) Is there any physical limit of number of Reducers given by internal
> Hadoop architecture?
>
> ... and finally ...
>
> 5) Does anybody know how and what exactly do folks in Yahoo! use Hadoop for?
> If the biggest reported Hadoop cluster has something like 2000 machines then
> the total number of Mappers/Reducers can be like 2000*200 (assuming there
> are for example 200 Reducers running on each machine), which is a big number
> but still probably not big enough to handle processing of really large
> graphs data structures IMHO. As far as I understood Google is not directly
> using Map-Reduce form of PageRank calculation for whole internet graph
> processing (see http://www.youtube.com/watch?v=BT-piFBP4fE). So, if Yahoo!
> needs scaling algorithm for really large tasks, what do they use if not
> Hadoop?
>
> Regards,
> Lukas
>
> --
> http://blog.lukas-vlcek.com/
>
--
Best regards, Edward J. Yoon
edwardyoon@apache.org
http://blog.udanax.org