[
https://issues.apache.org/jira/browse/HBASE-2663?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12893323#action_12893323
]
Jonathan Gray commented on HBASE-2663:
--------------------------------------
bq. The traversal can be avoided by keeping a running size that gets updated on
adds and removes?
Yeah, you'd have to keep running tabs on the size of each priority (and
decrement it when evicting) in addition to keeping the up-to-date LRU linked
list. I went the way of keeping locks out of the get/set path and pushing
overhead to eviction. If we track as we go, we'll introduce a number of locks.
I'm just unsure of a clear win here. Only if it's truly a non-trivial amount
of overhead to do the iteration and build the PQ does pushing overhead into the
getter/setters make sense.
In that case, would we then no longer use a background eviction thread? The
benefit is you never hold up get/set with eviction (trade-off is you can't
utilize the entire cache to the brim since you rely on high/low watermarks
rather than checking for capacity on each set). But if the eviction thread
actually acts directly against the sorted linked lists and the actively-tracked
priority sizes, it will need to at least partially lock these things during the
eviction process so new gets/sets don't interfere with an active eviction
process.
> LRU cache makes needless datastructure copies during eviction
> -------------------------------------------------------------
>
> Key: HBASE-2663
> URL: https://issues.apache.org/jira/browse/HBASE-2663
> Project: HBase
> Issue Type: Improvement
> Components: regionserver
> Reporter: Todd Lipcon
>
> Was browsing the LRU eviction code and came upon some very inefficient code.
> When we do eviction, BlockBucket.free() calls queue.get() which first inserts
> everything from the PriorityQueue<Block> into a LinkedList, then copies that
> entire linked list into an array. We then iterate over usually just a small
> percentage of the array to free some blocks until we have freed the requested
> amount.
> We ought to be able to just pull items out of the PriorityQueue directly and
> avoid all the churn.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
