hadoop-hdfs-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Kai Sasaki (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (HDFS-8611) Improve the performance of retry cache eviction
Date Wed, 17 Jun 2015 01:55:02 GMT

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

Kai Sasaki commented on HDFS-8611:

As discussed in HDFS-7609, removing expired entry from retry cache can be costly.

Although we assume removing arbitrary object from retry cache can be costly, is removing expired
entry the same case?
Each entry is stored in {{PriorityQueue}} and these are sorted by expiration time. So attempting
{{PriorityQueue#peek}} or {{PriorityQueue#poll}} does not done costly. I think {{PriorityQueue#remove}}
is not called at least implicitly.

> Improve the performance of retry cache eviction
> -----------------------------------------------
>                 Key: HDFS-8611
>                 URL: https://issues.apache.org/jira/browse/HDFS-8611
>             Project: Hadoop HDFS
>          Issue Type: Improvement
>            Reporter: Kihwal Lee
>            Priority: Critical
> As discussed in HDFS-7609, removing expired entry from retry cache can be costly.  Following
is the comment left by [~szetszwo] in HDFS-7609.
> {quote}
> PriorityQueue#remove is O\(n), so that definitely could be problematic. It's odd that
there would be so many collisions that this would become noticeable though. Are any of you
running a significant number of legacy applications linked to the RPC code before introduction
of the retry cache support? If that were the case, then perhaps a huge number of calls are
not supplying a call ID, and then the NN is getting a default call ID value from protobuf
decoding, thus causing a lot of collisions.
> {quote}
> The priority queue can be improved using a balanced tree as stated in the java comment
in LightWeightCache.  We should do it if it could fix the problem.
> {code}
> //LightWeightCache.java
>   /*
>    * The memory footprint for java.util.PriorityQueue is low but the
>    * remove(Object) method runs in linear time. We may improve it by using a
>    * balanced tree. However, we do not yet have a low memory footprint balanced
>    * tree implementation.
>    */
>   private final PriorityQueue<Entry> queue;
> {code}
> BTW, the priority queue is used to evict entries according the expiration time.  All
the entries (with any key, i.e. any caller ID) are stored in it.

This message was sent by Atlassian JIRA

View raw message