[jira] [Commented] (HDFS-8611) Improve the performance of retry cache eviction

["Walter Su (JIRA)" <ji...@apache.org>]

    [ 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
(v6.3.4#6332)