Hadoop Map/Reduce
  1. Hadoop Map/Reduce
  2. MAPREDUCE-2494

Make the distributed cache delete entires using LRU priority

    Details

    • Type: Improvement Improvement
    • Status: Closed
    • Priority: Major Major
    • Resolution: Fixed
    • Affects Version/s: 0.20.205.0, 0.21.0
    • Fix Version/s: 0.20.205.0, 0.23.0
    • Component/s: distributed-cache
    • Labels:
      None
    • Hadoop Flags:
      Reviewed
    • Release Note:
      Hide
      Added config option mapreduce.tasktracker.cache.local.keep.pct to the TaskTracker. It is the target percentage of the local distributed cache that should be kept in between garbage collection runs. In practice it will delete unused distributed cache entries in LRU order until the size of the cache is less than mapreduce.tasktracker.cache.local.keep.pct of the maximum cache size. This is a floating point value between 0.0 and 1.0. The default is 0.95.
      Show
      Added config option mapreduce.tasktracker.cache.local.keep.pct to the TaskTracker. It is the target percentage of the local distributed cache that should be kept in between garbage collection runs. In practice it will delete unused distributed cache entries in LRU order until the size of the cache is less than mapreduce.tasktracker.cache.local.keep.pct of the maximum cache size. This is a floating point value between 0.0 and 1.0. The default is 0.95.

      Description

      Currently the distributed cache will wait until a cache directory is above a preconfigured threshold. At which point it will delete all entries that are not currently being used. It seems like we would get far fewer cache misses if we kept some of them around, even when they are not being used. We should add in a configurable percentage for a goal of how much of the cache should remain clear when not in use, and select objects to delete based off of how recently they were used, and possibly also how large they are/how difficult is it to download them again.

      1. MAPREDUCE-2494-20.20X-V1.patch
        17 kB
        Robert Joseph Evans
      2. MAPREDUCE-2494-20.20X-V3.patch
        17 kB
        Robert Joseph Evans
      3. MAPREDUCE-2494-V1.patch
        15 kB
        Robert Joseph Evans
      4. MAPREDUCE-2494-V2.patch
        16 kB
        Robert Joseph Evans

        Issue Links

          Activity

          Hide
          caofangkun added a comment -

          Hi Robert Joseph Evans :
          LinkedHashMap has two ordering mode : insertion-order and access-order.
          In this issue why don't U use access-order(It is more like LRU )?
          That is :
          private static LinkedHashMap<String, CacheStatus> cachedArchives = new LinkedHashMap<String, CacheStatus>(16, 0.75f, true);

          Show
          caofangkun added a comment - Hi Robert Joseph Evans : LinkedHashMap has two ordering mode : insertion-order and access-order. In this issue why don't U use access-order(It is more like LRU )? That is : private static LinkedHashMap<String, CacheStatus> cachedArchives = new LinkedHashMap<String, CacheStatus>(16, 0.75f, true);
          Hide
          Matt Foley added a comment -

          Closed upon release of 0.20.205.0

          Show
          Matt Foley added a comment - Closed upon release of 0.20.205.0
          Hide
          Mahadev konar added a comment -

          Just pushed this to 0.20-security branch. Thanks bobby!

          Show
          Mahadev konar added a comment - Just pushed this to 0.20-security branch. Thanks bobby!
          Hide
          Robert Joseph Evans added a comment -

          I have confirmed it. The deletion is happening in LRU order.

          Show
          Robert Joseph Evans added a comment - I have confirmed it. The deletion is happening in LRU order.
          Hide
          Mahadev konar added a comment -

          thanks bobby. Ill push it as soon as you confirm the results!

          Show
          Mahadev konar added a comment - thanks bobby. Ill push it as soon as you confirm the results!
          Hide
          Robert Joseph Evans added a comment -

          I have now run it on a 10 node cluster with gridmix and everything looks stable. I still need to verify that the cache deletes things in LRU order, but I should have those results shortly.

          Show
          Robert Joseph Evans added a comment - I have now run it on a 10 node cluster with gridmix and everything looks stable. I still need to verify that the cache deletes things in LRU order, but I should have those results shortly.
          Hide
          Robert Joseph Evans added a comment -

          I have done some manual verification, but nothing on a cluster over 1 node. I will try to see what I can do on a smaller cluster.

          Show
          Robert Joseph Evans added a comment - I have done some manual verification, but nothing on a cluster over 1 node. I will try to see what I can do on a smaller cluster.
          Hide
          Mahadev konar added a comment -

          fair enough. Any chance you could verify the LRU deletion on a small cluster?

          Show
          Mahadev konar added a comment - fair enough. Any chance you could verify the LRU deletion on a small cluster?
          Hide
          Robert Joseph Evans added a comment -

          I really would prefer to have this in 205. I originally wanted to put it into 204. I have a customer that has really been pushing for this to help them bring down the time on some of their jobs so that they have a comfortable headroom on their SLAs. Also we have looked at distributed cache usage in some of our grids and there are a handful of blocks that get read so often that each one consistently accounts for over 1 TB of network traffic each day. Every day 4000 nodes read each of these blocks and then throw them away. If we can cut that out because those blocks are still in the cache it is a huge win for us.

          What more testing do you want before you consider this acceptable?

          Show
          Robert Joseph Evans added a comment - I really would prefer to have this in 205. I originally wanted to put it into 204. I have a customer that has really been pushing for this to help them bring down the time on some of their jobs so that they have a comfortable headroom on their SLAs. Also we have looked at distributed cache usage in some of our grids and there are a handful of blocks that get read so often that each one consistently accounts for over 1 TB of network traffic each day. Every day 4000 nodes read each of these blocks and then throw them away. If we can cut that out because those blocks are still in the cache it is a huge win for us. What more testing do you want before you consider this acceptable?
          Hide
          Mahadev konar added a comment -

          Can we move this to 206, so that we can do a little more testing on this?

          Show
          Mahadev konar added a comment - Can we move this to 206, so that we can do a little more testing on this?
          Hide
          Devaraj Das added a comment -

          The 20.2xx patch looks in line with the trunk one. +1

          Show
          Devaraj Das added a comment - The 20.2xx patch looks in line with the trunk one. +1
          Hide
          Robert Joseph Evans added a comment -

          The patch is not for trunk, but for the Security branch. These are the results of test-patch.

          [exec] +1 overall.
          [exec]
          [exec] +1 @author. The patch does not contain any @author tags.
          [exec]
          [exec] +1 tests included. The patch appears to include 3 new or modified tests.
          [exec]
          [exec] +1 javadoc. The javadoc tool did not generate any warning messages.
          [exec]
          [exec] +1 javac. The applied patch does not increase the total number of javac compiler warnings.
          [exec]
          [exec] +1 findbugs. The patch does not introduce any new Findbugs (version 1.3.9) warnings.

          Show
          Robert Joseph Evans added a comment - The patch is not for trunk, but for the Security branch. These are the results of test-patch. [exec] +1 overall. [exec] [exec] +1 @author. The patch does not contain any @author tags. [exec] [exec] +1 tests included. The patch appears to include 3 new or modified tests. [exec] [exec] +1 javadoc. The javadoc tool did not generate any warning messages. [exec] [exec] +1 javac. The applied patch does not increase the total number of javac compiler warnings. [exec] [exec] +1 findbugs. The patch does not introduce any new Findbugs (version 1.3.9) warnings.
          Hide
          Hadoop QA added a comment -

          -1 overall. Here are the results of testing the latest attachment
          http://issues.apache.org/jira/secure/attachment/12487708/MAPREDUCE-2494-20.20X-V3.patch
          against trunk revision 1150533.

          +1 @author. The patch does not contain any @author tags.

          +1 tests included. The patch appears to include 3 new or modified tests.

          -1 patch. The patch command could not apply the patch.

          Console output: https://builds.apache.org/job/PreCommit-MAPREDUCE-Build/497//console

          This message is automatically generated.

          Show
          Hadoop QA added a comment - -1 overall. Here are the results of testing the latest attachment http://issues.apache.org/jira/secure/attachment/12487708/MAPREDUCE-2494-20.20X-V3.patch against trunk revision 1150533. +1 @author. The patch does not contain any @author tags. +1 tests included. The patch appears to include 3 new or modified tests. -1 patch. The patch command could not apply the patch. Console output: https://builds.apache.org/job/PreCommit-MAPREDUCE-Build/497//console This message is automatically generated.
          Hide
          Robert Joseph Evans added a comment -

          In light of MAPREDUCE-2572 I have updated the default value took keep around to be 95% instead of the first 75%.

          Show
          Robert Joseph Evans added a comment - In light of MAPREDUCE-2572 I have updated the default value took keep around to be 95% instead of the first 75%.
          Hide
          Robert Joseph Evans added a comment -

          I am requesting that someone please review the patch for the 0.20 security line. The changes are almost identical to what went into trunk.

          Thanks

          Show
          Robert Joseph Evans added a comment - I am requesting that someone please review the patch for the 0.20 security line. The changes are almost identical to what went into trunk. Thanks
          Hide
          Hudson added a comment -

          Integrated in Hadoop-Mapreduce-trunk #722 (See https://builds.apache.org/job/Hadoop-Mapreduce-trunk/722/)

          Show
          Hudson added a comment - Integrated in Hadoop-Mapreduce-trunk #722 (See https://builds.apache.org/job/Hadoop-Mapreduce-trunk/722/ )
          Hide
          Hudson added a comment -

          Integrated in Hadoop-Mapreduce-trunk-Commit #720 (See https://builds.apache.org/job/Hadoop-Mapreduce-trunk-Commit/720/)
          MAPREDUCE-2573. Fix new findbugs warning introduced by MAPREDUCE-2494. Contributed by Robert Joseph Evans.

          todd : http://svn.apache.org/viewcvs.cgi/?root=Apache-SVN&view=rev&rev=1134121
          Files :

          • /hadoop/mapreduce/trunk/src/java/org/apache/hadoop/mapreduce/filecache/TrackerDistributedCacheManager.java
          • /hadoop/mapreduce/trunk/CHANGES.txt
          Show
          Hudson added a comment - Integrated in Hadoop-Mapreduce-trunk-Commit #720 (See https://builds.apache.org/job/Hadoop-Mapreduce-trunk-Commit/720/ ) MAPREDUCE-2573 . Fix new findbugs warning introduced by MAPREDUCE-2494 . Contributed by Robert Joseph Evans. todd : http://svn.apache.org/viewcvs.cgi/?root=Apache-SVN&view=rev&rev=1134121 Files : /hadoop/mapreduce/trunk/src/java/org/apache/hadoop/mapreduce/filecache/TrackerDistributedCacheManager.java /hadoop/mapreduce/trunk/CHANGES.txt
          Hide
          Hadoop QA added a comment -

          -1 overall. Here are the results of testing the latest attachment
          http://issues.apache.org/jira/secure/attachment/12481842/MAPREDUCE-2494-20.20X-V1.patch
          against trunk revision 1133226.

          +1 @author. The patch does not contain any @author tags.

          +1 tests included. The patch appears to include 3 new or modified tests.

          -1 patch. The patch command could not apply the patch.

          Console output: https://builds.apache.org/job/PreCommit-MAPREDUCE-Build/365//console

          This message is automatically generated.

          Show
          Hadoop QA added a comment - -1 overall. Here are the results of testing the latest attachment http://issues.apache.org/jira/secure/attachment/12481842/MAPREDUCE-2494-20.20X-V1.patch against trunk revision 1133226. +1 @author. The patch does not contain any @author tags. +1 tests included. The patch appears to include 3 new or modified tests. -1 patch. The patch command could not apply the patch. Console output: https://builds.apache.org/job/PreCommit-MAPREDUCE-Build/365//console This message is automatically generated.
          Hide
          Robert Joseph Evans added a comment -

          This patch also takes into account the issues shown with MAPREDUCE-2573. This is for the security branch.

          [exec] +1 overall.
          [exec]
          [exec] +1 @author. The patch does not contain any @author tags.
          [exec]
          [exec] +1 tests included. The patch appears to include 3 new or modified tests.
          [exec]
          [exec] +1 javadoc. The javadoc tool did not generate any warning messages.
          [exec]
          [exec] +1 javac. The applied patch does not increase the total number of javac compiler warnings.
          [exec]
          [exec] +1 findbugs. The patch does not introduce any new Findbugs (version 1.3.9) warnings.

          Show
          Robert Joseph Evans added a comment - This patch also takes into account the issues shown with MAPREDUCE-2573 . This is for the security branch. [exec] +1 overall. [exec] [exec] +1 @author. The patch does not contain any @author tags. [exec] [exec] +1 tests included. The patch appears to include 3 new or modified tests. [exec] [exec] +1 javadoc. The javadoc tool did not generate any warning messages. [exec] [exec] +1 javac. The applied patch does not increase the total number of javac compiler warnings. [exec] [exec] +1 findbugs. The patch does not introduce any new Findbugs (version 1.3.9) warnings.
          Hide
          Robert Joseph Evans added a comment -

          Reopening to add in patch for 0.20.2XX branch

          Show
          Robert Joseph Evans added a comment - Reopening to add in patch for 0.20.2XX branch
          Hide
          Todd Lipcon added a comment -

          Not sure why it didn't show up on the test-patch, but please take a look at MAPREDUCE-2573 - I think this commit added a findbugs warning.

          Show
          Todd Lipcon added a comment - Not sure why it didn't show up on the test-patch, but please take a look at MAPREDUCE-2573 - I think this commit added a findbugs warning.
          Hide
          Hudson added a comment -

          Integrated in Hadoop-Mapreduce-trunk #690 (See https://builds.apache.org/hudson/job/Hadoop-Mapreduce-trunk/690/)
          MAPREDUCE-2494. Order distributed cache deletions by LRU.
          Contributed by Robert Joseph Evans

          cdouglas : http://svn.apache.org/viewcvs.cgi/?root=Apache-SVN&view=rev&rev=1127386
          Files :

          • /hadoop/mapreduce/trunk/src/java/org/apache/hadoop/mapreduce/filecache/TrackerDistributedCacheManager.java
          • /hadoop/mapreduce/trunk/CHANGES.txt
          • /hadoop/mapreduce/trunk/src/test/mapred/org/apache/hadoop/mapreduce/filecache/TestTrackerDistributedCacheManager.java
          • /hadoop/mapreduce/trunk/src/java/org/apache/hadoop/mapreduce/server/tasktracker/TTConfig.java
          Show
          Hudson added a comment - Integrated in Hadoop-Mapreduce-trunk #690 (See https://builds.apache.org/hudson/job/Hadoop-Mapreduce-trunk/690/ ) MAPREDUCE-2494 . Order distributed cache deletions by LRU. Contributed by Robert Joseph Evans cdouglas : http://svn.apache.org/viewcvs.cgi/?root=Apache-SVN&view=rev&rev=1127386 Files : /hadoop/mapreduce/trunk/src/java/org/apache/hadoop/mapreduce/filecache/TrackerDistributedCacheManager.java /hadoop/mapreduce/trunk/CHANGES.txt /hadoop/mapreduce/trunk/src/test/mapred/org/apache/hadoop/mapreduce/filecache/TestTrackerDistributedCacheManager.java /hadoop/mapreduce/trunk/src/java/org/apache/hadoop/mapreduce/server/tasktracker/TTConfig.java
          Hide
          Hudson added a comment -

          Integrated in Hadoop-Mapreduce-trunk-Commit #699 (See https://builds.apache.org/hudson/job/Hadoop-Mapreduce-trunk-Commit/699/)
          MAPREDUCE-2494. Order distributed cache deletions by LRU.
          Contributed by Robert Joseph Evans

          cdouglas : http://svn.apache.org/viewcvs.cgi/?root=Apache-SVN&view=rev&rev=1127386
          Files :

          • /hadoop/mapreduce/trunk/src/java/org/apache/hadoop/mapreduce/filecache/TrackerDistributedCacheManager.java
          • /hadoop/mapreduce/trunk/CHANGES.txt
          • /hadoop/mapreduce/trunk/src/test/mapred/org/apache/hadoop/mapreduce/filecache/TestTrackerDistributedCacheManager.java
          • /hadoop/mapreduce/trunk/src/java/org/apache/hadoop/mapreduce/server/tasktracker/TTConfig.java
          Show
          Hudson added a comment - Integrated in Hadoop-Mapreduce-trunk-Commit #699 (See https://builds.apache.org/hudson/job/Hadoop-Mapreduce-trunk-Commit/699/ ) MAPREDUCE-2494 . Order distributed cache deletions by LRU. Contributed by Robert Joseph Evans cdouglas : http://svn.apache.org/viewcvs.cgi/?root=Apache-SVN&view=rev&rev=1127386 Files : /hadoop/mapreduce/trunk/src/java/org/apache/hadoop/mapreduce/filecache/TrackerDistributedCacheManager.java /hadoop/mapreduce/trunk/CHANGES.txt /hadoop/mapreduce/trunk/src/test/mapred/org/apache/hadoop/mapreduce/filecache/TestTrackerDistributedCacheManager.java /hadoop/mapreduce/trunk/src/java/org/apache/hadoop/mapreduce/server/tasktracker/TTConfig.java
          Hide
          Chris Douglas added a comment -

          +1

          I committed this. Thanks, Robert!

          Show
          Chris Douglas added a comment - +1 I committed this. Thanks, Robert!
          Hide
          Hadoop QA added a comment -

          +1 overall. Here are the results of testing the latest attachment
          http://issues.apache.org/jira/secure/attachment/12480159/MAPREDUCE-2494-V2.patch
          against trunk revision 1126591.

          +1 @author. The patch does not contain any @author tags.

          +1 tests included. The patch appears to include 3 new or modified tests.

          +1 javadoc. The javadoc tool did not generate any warning messages.

          +1 javac. The applied patch does not increase the total number of javac compiler warnings.

          +1 findbugs. The patch does not introduce any new Findbugs (version 1.3.9) warnings.

          +1 release audit. The applied patch does not increase the total number of release audit warnings.

          +1 core tests. The patch passed core unit tests.

          +1 contrib tests. The patch passed contrib unit tests.

          +1 system test framework. The patch passed system test framework compile.

          Test results: https://builds.apache.org/hudson/job/PreCommit-MAPREDUCE-Build/298//testReport/
          Findbugs warnings: https://builds.apache.org/hudson/job/PreCommit-MAPREDUCE-Build/298//artifact/trunk/build/test/findbugs/newPatchFindbugsWarnings.html
          Console output: https://builds.apache.org/hudson/job/PreCommit-MAPREDUCE-Build/298//console

          This message is automatically generated.

          Show
          Hadoop QA added a comment - +1 overall. Here are the results of testing the latest attachment http://issues.apache.org/jira/secure/attachment/12480159/MAPREDUCE-2494-V2.patch against trunk revision 1126591. +1 @author. The patch does not contain any @author tags. +1 tests included. The patch appears to include 3 new or modified tests. +1 javadoc. The javadoc tool did not generate any warning messages. +1 javac. The applied patch does not increase the total number of javac compiler warnings. +1 findbugs. The patch does not introduce any new Findbugs (version 1.3.9) warnings. +1 release audit. The applied patch does not increase the total number of release audit warnings. +1 core tests. The patch passed core unit tests. +1 contrib tests. The patch passed contrib unit tests. +1 system test framework. The patch passed system test framework compile. Test results: https://builds.apache.org/hudson/job/PreCommit-MAPREDUCE-Build/298//testReport/ Findbugs warnings: https://builds.apache.org/hudson/job/PreCommit-MAPREDUCE-Build/298//artifact/trunk/build/test/findbugs/newPatchFindbugsWarnings.html Console output: https://builds.apache.org/hudson/job/PreCommit-MAPREDUCE-Build/298//console This message is automatically generated.
          Hide
          Robert Joseph Evans added a comment -

          In a different conversation with Chris he mentioned that sleeps in the tests are bad, and that if they have to be there then they should be tied together with some constant values. I am reworking the tests to deal with constant values.

          Show
          Robert Joseph Evans added a comment - In a different conversation with Chris he mentioned that sleeps in the tests are bad, and that if they have to be there then they should be tied together with some constant values. I am reworking the tests to deal with constant values.
          Hide
          Hadoop QA added a comment -

          +1 overall. Here are the results of testing the latest attachment
          http://issues.apache.org/jira/secure/attachment/12479370/MAPREDUCE-2494-V1.patch
          against trunk revision 1103921.

          +1 @author. The patch does not contain any @author tags.

          +1 tests included. The patch appears to include 3 new or modified tests.

          +1 javadoc. The javadoc tool did not generate any warning messages.

          +1 javac. The applied patch does not increase the total number of javac compiler warnings.

          +1 findbugs. The patch does not introduce any new Findbugs (version 1.3.9) warnings.

          +1 release audit. The applied patch does not increase the total number of release audit warnings.

          +1 core tests. The patch passed core unit tests.

          +1 contrib tests. The patch passed contrib unit tests.

          +1 system test framework. The patch passed system test framework compile.

          Test results: https://builds.apache.org/hudson/job/PreCommit-MAPREDUCE-Build/251//testReport/
          Findbugs warnings: https://builds.apache.org/hudson/job/PreCommit-MAPREDUCE-Build/251//artifact/trunk/build/test/findbugs/newPatchFindbugsWarnings.html
          Console output: https://builds.apache.org/hudson/job/PreCommit-MAPREDUCE-Build/251//console

          This message is automatically generated.

          Show
          Hadoop QA added a comment - +1 overall. Here are the results of testing the latest attachment http://issues.apache.org/jira/secure/attachment/12479370/MAPREDUCE-2494-V1.patch against trunk revision 1103921. +1 @author. The patch does not contain any @author tags. +1 tests included. The patch appears to include 3 new or modified tests. +1 javadoc. The javadoc tool did not generate any warning messages. +1 javac. The applied patch does not increase the total number of javac compiler warnings. +1 findbugs. The patch does not introduce any new Findbugs (version 1.3.9) warnings. +1 release audit. The applied patch does not increase the total number of release audit warnings. +1 core tests. The patch passed core unit tests. +1 contrib tests. The patch passed contrib unit tests. +1 system test framework. The patch passed system test framework compile. Test results: https://builds.apache.org/hudson/job/PreCommit-MAPREDUCE-Build/251//testReport/ Findbugs warnings: https://builds.apache.org/hudson/job/PreCommit-MAPREDUCE-Build/251//artifact/trunk/build/test/findbugs/newPatchFindbugsWarnings.html Console output: https://builds.apache.org/hudson/job/PreCommit-MAPREDUCE-Build/251//console This message is automatically generated.
          Hide
          Robert Joseph Evans added a comment -

          First patch, uses LinkedHashMap to keep track of LRU ordering of cachedArchives, so that removal of them can happen in an orderly manor.

          Show
          Robert Joseph Evans added a comment - First patch, uses LinkedHashMap to keep track of LRU ordering of cachedArchives, so that removal of them can happen in an orderly manor.
          Hide
          Robert Joseph Evans added a comment -

          I agree completely. The 10 min is already configurable, sort of. It should also be very simple to add it in. The hardest part will probably be updating the tests. I figure I will make the reference count inc/dec in the CacheStatus methods, and then if the reference count ever goes to 0 we update a timestamp to indicate when it was last used, so we can purge oldest objects first.

          Show
          Robert Joseph Evans added a comment - I agree completely. The 10 min is already configurable, sort of. It should also be very simple to add it in. The hardest part will probably be updating the tests. I figure I will make the reference count inc/dec in the CacheStatus methods, and then if the reference count ever goes to 0 we update a timestamp to indicate when it was last used, so we can purge oldest objects first.
          Hide
          Owen O'Malley added a comment -

          I was also surprised when I walked through the code and saw that it was deleting all currently unused objects.

          I think a straight LRU with a goal percentage of the threshold makes sense. For a first pass of this, I think the object's size should be ignored until we understand better how it interacts with the rest of the system.

          So something like:

          when (free space on partition < free-limit or 
                disk usage of dist cache > cache-limit) and 
               time since last purge > 10 minutes:
            purge LRU unused objects to reach goal size of cache-limit*cache-usage-goal
          

          Does that make sense?

          Show
          Owen O'Malley added a comment - I was also surprised when I walked through the code and saw that it was deleting all currently unused objects. I think a straight LRU with a goal percentage of the threshold makes sense. For a first pass of this, I think the object's size should be ignored until we understand better how it interacts with the rest of the system. So something like: when (free space on partition < free-limit or disk usage of dist cache > cache-limit) and time since last purge > 10 minutes: purge LRU unused objects to reach goal size of cache-limit*cache-usage-goal Does that make sense?

            People

            • Assignee:
              Robert Joseph Evans
              Reporter:
              Robert Joseph Evans
            • Votes:
              0 Vote for this issue
              Watchers:
              15 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved:

                Development