hadoop-hdfs-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Tsz Wo Nicholas Sze (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (HDFS-11535) Performance analysis of new DFSNetworkTopology#chooseRandom
Date Sat, 18 Mar 2017 01:31:41 GMT

    [ https://issues.apache.org/jira/browse/HDFS-11535?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15930979#comment-15930979

Tsz Wo Nicholas Sze commented on HDFS-11535:

Thanks Chen for taking my proposal.

> ... the threshold-based approach will likely always take one call, which makes it always
either 1* (call old) or 1.6* (call new) of old time in most siturations. ...

Strictly speaking, the threshold-based approach does not give 1* when calling old since the
trials may fail; more details below.

Suppose p = #target-storage / #all-storage.  Then p is also the probability of successfully
picking the right storage randomly.  1-p is the failure probability.  The expected trials
for the old algorithm is:
p + 2p(1-p) + 3p(1-p)^2 + 4p(1-p)^3 + ...
- The first term p: it succeeds in the 1st trial.  Cost: 1 trial.
- The second term 2p(1-p): it fails in the 1st trial and succeeds in the 2nd trial, it costs
2 trials
- n-th term np(1-p)^(n-1): it fails in the first n-1 trials and succeeds in the n-th trials,
the cost is n trials.

This is an arithmetic–geometric sequence and the sum to infinity is 1/p.
p + 2p(1-p) + 3p(1-p)^2 + 4p(1-p)^3 + ...  = 1/p for 0 < p <= 1.

If the threshold is 0.6 and p is 0.61, then the expected cost of the old algorithm is 1/0.61
= 1.64.  So the new algorithm is better in this case.

The threshold must be at least 1/1.6 = 0.625 so that the old algorithm could possibly better
than the new algorithm.  Again, choosing a good threshold is complicated.

> Performance analysis of new DFSNetworkTopology#chooseRandom
> -----------------------------------------------------------
>                 Key: HDFS-11535
>                 URL: https://issues.apache.org/jira/browse/HDFS-11535
>             Project: Hadoop HDFS
>          Issue Type: Sub-task
>          Components: namenode
>            Reporter: Chen Liang
>            Assignee: Chen Liang
>         Attachments: HDFS-11535.001.patch, PerfTest.pdf
> This JIRA is created to post the results of some performance experiments we did.  For
those who are interested, please the attached .pdf file for more detail. The attached patch
file includes the experiment code we ran. 
> The key insights we got from these tests is that: although *the new method outperforms
the current one in most cases*. There is still *one case where the current one is better*.
Which is when there is only one storage type in the cluster, and we also always look for this
storage type. In this case, it is simply a waste of time to perform storage-type-based pruning,
blindly picking up a random node (current methods) would suffice.
> Therefore, based on the analysis, we propose to use a *combination of both the old and
the new methods*:
> say, we search for a node of type X, since now inner node all keep storage type info,
we can *just check root node to see if X is the only type it has*. If yes, blindly picking
a random leaf will work, so we simply call the old method, otherwise we call the new method.
> There is still at least one missing piece in this performance test, which is garbage
collection. The new method does a few more object creation when doing the search, which adds
overhead to GC. I'm still thinking of any potential optimization but this seems tricky, also
I'm not sure whether this optimization worth doing at all. Please feel free to leave any comments/suggestions.
> Thanks [~arpitagarwal] and [~szetszwo] for the offline discussion.

This message was sent by Atlassian JIRA

To unsubscribe, e-mail: hdfs-issues-unsubscribe@hadoop.apache.org
For additional commands, e-mail: hdfs-issues-help@hadoop.apache.org

View raw message