hadoop-hdfs-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Walter Su (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (HDFS-8611) Improve the performance of retry cache eviction
Date Mon, 12 Oct 2015 02:25:05 GMT

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

Walter Su commented on HDFS-8611:

bq.  So attempting PriorityQueue#peek or PriorityQueue#poll does not done costly. I think
PriorityQueue#remove is not called at least implicitly.
That's true. {{PriorityQueue#remove}} is called only when there's a collision.
I think the newly added Entry always has the biggest ExpirationTime ( {{accessExpirationPeriod}}
is not used for now). Why not use circular FIFO queue? We can use binarySearch + deletion
bit to achieve O(logn) {{remove(object)}} for updating the collision.

> 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