[
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:
{code}
p + 2p(1-p) + 3p(1-p)^2 + 4p(1-p)^3 + ...
{code}
- 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.
{code}
p + 2p(1-p) + 3p(1-p)^2 + 4p(1-p)^3 + ... = 1/p for 0 < p <= 1.
{code}
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
(v6.3.15#6346)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
