You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@hbase.apache.org by "Todd Lipcon (JIRA)" <ji...@apache.org> on 2010/06/04 01:07:57 UTC
[jira] Created: (HBASE-2663) LRU cache makes needless datastructure
copies during eviction
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.
[jira] Commented: (HBASE-2663) LRU cache makes needless
datastructure copies during eviction
Posted by "stack (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HBASE-2663?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12891314#action_12891314 ]
stack commented on HBASE-2663:
------------------------------
What you thinking? A PriorityDequeue? An implementation is not easy to come by. It'd be less performant keeping sort up on both ends. I wonder if we just used a NavigableSet, if that'd be performant enough. We'd have to change the compare to take into consideration priority.
> 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.
[jira] Commented: (HBASE-2663) LRU cache makes needless
datastructure copies during eviction
Posted by "Jonathan Gray (JIRA)" <ji...@apache.org>.
[ 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.
[jira] Commented: (HBASE-2663) LRU cache makes needless
datastructure copies during eviction
Posted by "Jonathan Gray (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HBASE-2663?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12893148#action_12893148 ]
Jonathan Gray commented on HBASE-2663:
--------------------------------------
The implementation of the lru was originally intended to put all overhead at eviction time and as little as possible for reads/writes. This included an attempted lock-free design based around the ConcurrentHashMap as the data structure for blocks.
Given we're in java land, this background memory usage still impacts us, not sure how significant, but for sure it's lots of objects.
You could get rid of the shallow copy into the structure that sorts by accessTime by keeping an up-to-date linked list for each priority. I think you need to roll your own LL implementation because the java one won't let you get the LL pointers referenced into some other object (you want a LL but you also need a constant time operation like removeAndPushToFront). Needs to be thread-safe too, blocks being updated by concurrent reads and a concurrent eviction process.
You'd still have to iterate the entire list and calculate the total sizes for each priority and you'll still need the hash map, right?
So then, in the end, are you using the same amount of memory but keeping it around and maintaining it in order versus re-allocating and calculating on the fly at eviction time?
> 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.
[jira] Commented: (HBASE-2663) LRU cache makes needless
datastructure copies during eviction
Posted by "Jonathan Gray (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HBASE-2663?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12893152#action_12893152 ]
Jonathan Gray commented on HBASE-2663:
--------------------------------------
i see the original copy you are talking about. can definitely clean that up but i still think the other thoughts floating around are valid on a more broad scope.
one thing to note about the copy in queue.get() is that we don't usually iterate just a small percentage of what is in the queue. The queue won't contain all the blocks, just the minimum number of least-recently-used blocks that would need to be evicted given a specified max to free. We pass in the maximum amount of bytes that would possibly have to be freed from each priority. So we won't always iterate all of them, but not too bad. still definitely should fix it.
> 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.
[jira] Commented: (HBASE-2663) LRU cache makes needless
datastructure copies during eviction
Posted by "Todd Lipcon (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HBASE-2663?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12892573#action_12892573 ]
Todd Lipcon commented on HBASE-2663:
------------------------------------
Why not track the blocks through a linked list, drop the "accessTime" member, and whenever it's accessed, move it to the front of the list? Then when we want to evict, just scan from the end of the list?
At least we could avoid the complete shallow copy into a LinkedList at LruBlockCache.java:422 - here we copy the entire PriorityQueue out into a LinkedList when we call queue.get(), and then we only iterate the first couple elements of the linked list. Instead, we could just pull elements off the PrioritiyQueue directly, one by one, evicting until we've evicted enough.
> 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.
[jira] Commented: (HBASE-2663) LRU cache makes needless
datastructure copies during eviction
Posted by "Jonathan Gray (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HBASE-2663?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12893389#action_12893389 ]
Jonathan Gray commented on HBASE-2663:
--------------------------------------
@Ryan, not sure I follow. In what case do you not "defer evictions"? I don't see how the blocks tenuring would be impacted by the approaches discussed above. In all cases they would still be in the cache for the same amount of time and with same numbers of accesses? In the case that we keep things up to date, we'll access more objects more often so more ref counting. Am I missing something?
> 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.
[jira] Commented: (HBASE-2663) LRU cache makes needless
datastructure copies during eviction
Posted by "ryan rawson (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HBASE-2663?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12893359#action_12893359 ]
ryan rawson commented on HBASE-2663:
------------------------------------
So there is another thing here, by deferring the evictions to the
background thread you increase the chance that the block will be
tenured then it must be collected from CMS space, thus radically
increasing the GC complexity of the cache. Originally when the LRU
block cache came in, it made my collections 10x as slow until I
disabled the block cache for compactions.
Unfortunately all these micro-optimizations might be falling under the
GC wayside.
> 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.
[jira] Commented: (HBASE-2663) LRU cache makes needless
datastructure copies during eviction
Posted by "stack (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HBASE-2663?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12893262#action_12893262 ]
stack commented on HBASE-2663:
------------------------------
bq. You'd still have to iterate the entire list and calculate the total sizes for each priority and you'll still need the hash map, right?
The traversal can be avoided by keeping a running size that gets updated on adds and removes?
bq. ...you also need a [thread-safe] constant time operation like removeAndPushToFront..
This'd be the interesting bit.
FYI, this change, 674cf0d9b0648d146d5a67d95443826f1298b27a, got rid of the creation of an array of CachedBlocks -- instead we just return the just-made LL instead and iterate that. e.g.
{code}
@@ -414,10 +419,10 @@ public class LruBlockCache implements BlockCache, HeapSize {
}
public long free(long toFree) {
- CachedBlock [] blocks = queue.get();
+ LinkedList<CachedBlock> blocks = queue.get();
long freedBytes = 0;
- for(int i=0; i<blocks.length; i++) {
- freedBytes += evictBlock(blocks[i]);
+ for(CachedBlock cb: blocks) {
+ freedBytes += evictBlock(cb);
if(freedBytes >= toFree) {
return freedBytes;
}
{code}
> 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.
[jira] Commented: (HBASE-2663) LRU cache makes needless
datastructure copies during eviction
Posted by "stack (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HBASE-2663?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12892607#action_12892607 ]
stack commented on HBASE-2663:
------------------------------
bq. Then when we want to evict, just scan from the end of the list
You'd use the LinkedList in addition to PriorityQueue, just so pull off the end of the queue? Or you thinking dump PriorityQueue and just use LinkedList (do they have same add/remove characteristic?).
You'd run three linked lists, one for SINGLE, MULTI and MEMORY (see head of BlockPriority)?
We'd need to keep running counts on each of the three linked lists lettting any of them grow to fill space unused by others?
> 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.