HBase
  1. HBase
  2. HBASE-1186

Memory-aware Maps with LRU eviction for Cell Cache

    Details

    • Type: New Feature New Feature
    • Status: Closed
    • Priority: Critical Critical
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: 0.20.0
    • Component/s: None
    • Labels:
      None

      Description

      Caching is key for 0.20. We need a set of memory-aware data structures to manage our caches.

      I propose two initial classes: LruHashMap and LruBlockMap

      LruHashMap is currently being used over in HBASE-80 for the Cell cache. Erik Holstad has done extensive testing and benchmarking and will post results over in this issue.

      • Memory-aware
      • Fixed size
      • LRU eviction

      LruBlockMap can be used for the block caching of the new file format in HBASE-61. It should try to use all available memory, but must contend with Memcaches so is resizable to deal with heap pressure. Adding high priority blocks (evicted last) gives us in-memory functionality as described in bigtable paper.

      • Memory-aware
      • Fully resizable
      • LRU eviction (with some additions)
      • High priority blocks
      • Optional: Scan resistant algorithm

      Part of this issue is also solving how we will determine the size of cached objects.

      1. hbase-1186-v2.patch
        35 kB
        Jonathan Gray
      2. hbase-1186-v3.patch
        33 kB
        Jonathan Gray
      3. hbase-1186-v4.patch
        45 kB
        Jonathan Gray
      4. HeapSize.java
        2 kB
        Jonathan Gray
      5. LruHashMap.java
        30 kB
        Jonathan Gray

        Issue Links

          Activity

          Hide
          Erik Holstad added a comment -

          Adding the code for the current implementation of the LruHashMap.
          Same code as HBASE-80 right now.

          Show
          Erik Holstad added a comment - Adding the code for the current implementation of the LruHashMap. Same code as HBASE-80 right now.
          Hide
          Jonathan Gray added a comment -

          Stripped down, partially tested.

          Show
          Jonathan Gray added a comment - Stripped down, partially tested.
          Hide
          stack added a comment -

          You think we should go to bother of trying to elicit if 32-bit vs. 64-bit? (There is probably a canonical way but perhaps looking at bytes in an Integer would be a flag)? When HeapSize is classloaded, it could run static methods to figure 32-bit vs. 64-bit and then adjust the defines in this class accordingly? Then have methods on HeapSize that implementers call to size themselves for the different architectures? Maybe thats something for later, for the embedded hbase (smile)? Lets just go w/ 64-bit for now.

          Let me know if you want me to run some tests on profiler to check your sizings.

          For next version of LruHashMap, fix spacing – its two spaces by default and no tabs – and add apache license.

          Why do you have transient datamembers? Are your Maps meant to be (java) serializable?

          Make most of the data members private rather than default access?

          So, maxMemUsage is passed in? It'll be some percentage of the heap?

          We're not soft referencing it because of your testing showing soft references are not LRU?

          It'll be really interesting watching this thing at core of a concurrent app. There are no synchronizes anywhere. Whats the plan for that?

          Good stuff

          Show
          stack added a comment - You think we should go to bother of trying to elicit if 32-bit vs. 64-bit? (There is probably a canonical way but perhaps looking at bytes in an Integer would be a flag)? When HeapSize is classloaded, it could run static methods to figure 32-bit vs. 64-bit and then adjust the defines in this class accordingly? Then have methods on HeapSize that implementers call to size themselves for the different architectures? Maybe thats something for later, for the embedded hbase (smile)? Lets just go w/ 64-bit for now. Let me know if you want me to run some tests on profiler to check your sizings. For next version of LruHashMap, fix spacing – its two spaces by default and no tabs – and add apache license. Why do you have transient datamembers? Are your Maps meant to be (java) serializable? Make most of the data members private rather than default access? So, maxMemUsage is passed in? It'll be some percentage of the heap? We're not soft referencing it because of your testing showing soft references are not LRU? It'll be really interesting watching this thing at core of a concurrent app. There are no synchronizes anywhere. Whats the plan for that? Good stuff
          Hide
          Jonathan Gray added a comment -

          I didn't have time to finish work on this yesterday. I just posted up what I had finished before I left, it's definitely not done yet.

          Will properly format it, etc well before it's ready to be included.

          Re: 32-bit vs 64-bit there are some tests that can be used. My current plan is to go forward with assuming 64bit and in the future we can easily add something to detect like you said. It would then just change the size of REFERENCE which would bubble up into anything implementing HeapSize which should be using that static to compute its size.

          There is some stuff left over from other code in there (transient datamembers and such) that I will be taking out. I see no need for serialization. Same goes for making things private, have been working on the lru and heapsize elements and not so much the rest of the code. Will clean it up next week.

          Currently, maxMemUsage is passed in. This LRU is intended for cell cache which I think should be a per-regionserver setting. This can be adapted to work for the block cache as well in any number of ways. There are a few reasons I don't think softrefs are the way to go for block caching, definitely not the way to go for cell caching. Next week I'll put together the proposal for why I think we should use our own LRU mechanism rather than relying on softrefs across the board. The primary issues are how this will interact with existing memcache/heap monitoring, unpredictability of softref eviction, and the ability to implement in-memory tables very simply if we have our own lru mechanism (implemented in the way described in the bigtable paper).

          Same goes for synchronization. This is an early version not ready for prime time. Not sure what my plan is yet will post thoughts here. Will be working on this early in the week.

          Thanks for the review stack.

          Show
          Jonathan Gray added a comment - I didn't have time to finish work on this yesterday. I just posted up what I had finished before I left, it's definitely not done yet. Will properly format it, etc well before it's ready to be included. Re: 32-bit vs 64-bit there are some tests that can be used. My current plan is to go forward with assuming 64bit and in the future we can easily add something to detect like you said. It would then just change the size of REFERENCE which would bubble up into anything implementing HeapSize which should be using that static to compute its size. There is some stuff left over from other code in there (transient datamembers and such) that I will be taking out. I see no need for serialization. Same goes for making things private, have been working on the lru and heapsize elements and not so much the rest of the code. Will clean it up next week. Currently, maxMemUsage is passed in. This LRU is intended for cell cache which I think should be a per-regionserver setting. This can be adapted to work for the block cache as well in any number of ways. There are a few reasons I don't think softrefs are the way to go for block caching, definitely not the way to go for cell caching. Next week I'll put together the proposal for why I think we should use our own LRU mechanism rather than relying on softrefs across the board. The primary issues are how this will interact with existing memcache/heap monitoring, unpredictability of softref eviction, and the ability to implement in-memory tables very simply if we have our own lru mechanism (implemented in the way described in the bigtable paper). Same goes for synchronization. This is an early version not ready for prime time. Not sure what my plan is yet will post thoughts here. Will be working on this early in the week. Thanks for the review stack.
          Hide
          Jonathan Gray added a comment -

          There's a discussion that needs to happen around how we'll implement block caching. I'm going to create a new issue for that, this one will be about the LruHashMap used for the cell cache.

          Show
          Jonathan Gray added a comment - There's a discussion that needs to happen around how we'll implement block caching. I'm going to create a new issue for that, this one will be about the LruHashMap used for the cell cache.
          Hide
          Jonathan Gray added a comment -

          Apache-friendly. Thread-safe. Heavily commented as this will serve as the base to other memory-aware structures.

          Still partially untested but would like a general code review before moving forward.

          Show
          Jonathan Gray added a comment - Apache-friendly. Thread-safe. Heavily commented as this will serve as the base to other memory-aware structures. Still partially untested but would like a general code review before moving forward.
          Hide
          Jonathan Gray added a comment -

          A few small changes. Now includes two functions for debugging/unit test purposes. One returns a sorted List of entries in the LRU in order of their access time (oldest/first to evict is first). The other returns a Set of all elements found in the hash table.

          The two of these data structures can be used to ensure the LRU is being updated properly and that the linked list does not become out of sync with the hash table.

          Show
          Jonathan Gray added a comment - A few small changes. Now includes two functions for debugging/unit test purposes. One returns a sorted List of entries in the LRU in order of their access time (oldest/first to evict is first). The other returns a Set of all elements found in the hash table. The two of these data structures can be used to ensure the LRU is being updated properly and that the linked list does not become out of sync with the hash table.
          Hide
          Jonathan Gray added a comment -

          Working version. Fixes a few small bugs.

          This patch does not contain the unit test. Will post another patch when that's cleaned up.

          Show
          Jonathan Gray added a comment - Working version. Fixes a few small bugs. This patch does not contain the unit test. Will post another patch when that's cleaned up.
          Hide
          Jonathan Gray added a comment -

          Contains unit test and changes to HeapSize interface.

          Show
          Jonathan Gray added a comment - Contains unit test and changes to HeapSize interface.
          Hide
          Jonathan Gray added a comment -

          Tested and ready for review/commit.

          Show
          Jonathan Gray added a comment - Tested and ready for review/commit.
          Hide
          Andrew Purtell added a comment -

          I've reviewed this and except for a minor collision with the patch now it looks good. I'm just waiting for HBASE-1274 to be resolved first so I can claim that all local tests pass before committing this.

          Show
          Andrew Purtell added a comment - I've reviewed this and except for a minor collision with the patch now it looks good. I'm just waiting for HBASE-1274 to be resolved first so I can claim that all local tests pass before committing this.
          Hide
          Andrew Purtell added a comment -

          Committed to trunk. Passes all local tests, including the new test case addition for this feature.

          Show
          Andrew Purtell added a comment - Committed to trunk. Passes all local tests, including the new test case addition for this feature.

            People

            • Assignee:
              Jonathan Gray
              Reporter:
              Jonathan Gray
            • Votes:
              0 Vote for this issue
              Watchers:
              0 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved:

                Development