HDFS-10690. Optimize insertion/removal of replica in ShortCircuitCache. Contributed by Fenghua Hu.
Project: http://git-wip-us.apache.org/repos/asf/hadoop/repo Commit: http://git-wip-us.apache.org/repos/asf/hadoop/commit/607705c4 Tree: http://git-wip-us.apache.org/repos/asf/hadoop/tree/607705c4 Diff: http://git-wip-us.apache.org/repos/asf/hadoop/diff/607705c4 Branch: refs/heads/HDFS-10467 Commit: 607705c488fa5263d851cee578a2d319e6e52ecd Parents: de7a0a9 Author: Xiaoyu Yao <x...@apache.org> Authored: Mon Oct 3 10:53:21 2016 -0700 Committer: Xiaoyu Yao <x...@apache.org> Committed: Mon Oct 3 10:53:21 2016 -0700 ---------------------------------------------------------------------- .../hdfs/shortcircuit/ShortCircuitCache.java | 88 ++++++++++++-------- .../hadoop/fs/TestEnhancedByteBufferAccess.java | 17 ++-- .../shortcircuit/TestShortCircuitCache.java | 9 +- 3 files changed, 69 insertions(+), 45 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/hadoop/blob/607705c4/hadoop-hdfs-project/hadoop-hdfs-client/src/main/java/org/apache/hadoop/hdfs/shortcircuit/ShortCircuitCache.java ---------------------------------------------------------------------- diff --git a/hadoop-hdfs-project/hadoop-hdfs-client/src/main/java/org/apache/hadoop/hdfs/shortcircuit/ShortCircuitCache.java b/hadoop-hdfs-project/hadoop-hdfs-client/src/main/java/org/apache/hadoop/hdfs/shortcircuit/ShortCircuitCache.java index 62ade70..bd02a97 100644 --- a/hadoop-hdfs-project/hadoop-hdfs-client/src/main/java/org/apache/hadoop/hdfs/shortcircuit/ShortCircuitCache.java +++ b/hadoop-hdfs-project/hadoop-hdfs-client/src/main/java/org/apache/hadoop/hdfs/shortcircuit/ShortCircuitCache.java @@ -26,13 +26,14 @@ import java.nio.MappedByteBuffer; import java.util.HashMap; import java.util.Map; import java.util.Map.Entry; -import java.util.TreeMap; +import java.util.NoSuchElementException; import java.util.concurrent.ScheduledFuture; import java.util.concurrent.ScheduledThreadPoolExecutor; import java.util.concurrent.TimeUnit; import java.util.concurrent.locks.Condition; import java.util.concurrent.locks.ReentrantLock; +import org.apache.commons.collections.map.LinkedMap; import org.apache.commons.lang.mutable.MutableBoolean; import org.apache.hadoop.classification.InterfaceAudience; import org.apache.hadoop.hdfs.ExtendedBlockId; @@ -107,16 +108,20 @@ public class ShortCircuitCache implements Closeable { int numDemoted = demoteOldEvictableMmaped(curMs); int numPurged = 0; - Long evictionTimeNs = (long) 0; + Long evictionTimeNs; while (true) { - Entry<Long, ShortCircuitReplica> entry = - evictable.ceilingEntry(evictionTimeNs); - if (entry == null) break; - evictionTimeNs = entry.getKey(); + Object eldestKey; + try { + eldestKey = evictable.firstKey(); + } catch (NoSuchElementException e) { + break; + } + evictionTimeNs = (Long)eldestKey; long evictionTimeMs = TimeUnit.MILLISECONDS.convert(evictionTimeNs, TimeUnit.NANOSECONDS); if (evictionTimeMs + maxNonMmappedEvictableLifespanMs >= curMs) break; - ShortCircuitReplica replica = entry.getValue(); + ShortCircuitReplica replica = (ShortCircuitReplica)evictable.get( + eldestKey); if (LOG.isTraceEnabled()) { LOG.trace("CacheCleaner: purging " + replica + ": " + StringUtils.getStackTrace(Thread.currentThread())); @@ -263,11 +268,11 @@ public class ShortCircuitCache implements Closeable { private CacheCleaner cacheCleaner; /** - * Tree of evictable elements. + * LinkedMap of evictable elements. * * Maps (unique) insertion time in nanoseconds to the element. */ - private final TreeMap<Long, ShortCircuitReplica> evictable = new TreeMap<>(); + private final LinkedMap evictable = new LinkedMap(); /** * Maximum total size of the cache, including both mmapped and @@ -281,12 +286,11 @@ public class ShortCircuitCache implements Closeable { private long maxNonMmappedEvictableLifespanMs; /** - * Tree of mmaped evictable elements. + * LinkedMap of mmaped evictable elements. * * Maps (unique) insertion time in nanoseconds to the element. */ - private final TreeMap<Long, ShortCircuitReplica> evictableMmapped = - new TreeMap<>(); + private final LinkedMap evictableMmapped = new LinkedMap(); /** * Maximum number of mmaped evictable elements. @@ -482,13 +486,16 @@ public class ShortCircuitCache implements Closeable { private int demoteOldEvictableMmaped(long now) { int numDemoted = 0; boolean needMoreSpace = false; - Long evictionTimeNs = (long) 0; + Long evictionTimeNs; while (true) { - Entry<Long, ShortCircuitReplica> entry = - evictableMmapped.ceilingEntry(evictionTimeNs); - if (entry == null) break; - evictionTimeNs = entry.getKey(); + Object eldestKey; + try { + eldestKey = evictableMmapped.firstKey(); + } catch (NoSuchElementException e) { + break; + } + evictionTimeNs = (Long)eldestKey; long evictionTimeMs = TimeUnit.MILLISECONDS.convert(evictionTimeNs, TimeUnit.NANOSECONDS); if (evictionTimeMs + maxEvictableMmapedLifespanMs >= now) { @@ -497,7 +504,8 @@ public class ShortCircuitCache implements Closeable { } needMoreSpace = true; } - ShortCircuitReplica replica = entry.getValue(); + ShortCircuitReplica replica = (ShortCircuitReplica)evictableMmapped.get( + eldestKey); if (LOG.isTraceEnabled()) { String rationale = needMoreSpace ? "because we need more space" : "because it's too old"; @@ -527,10 +535,15 @@ public class ShortCircuitCache implements Closeable { return; } ShortCircuitReplica replica; - if (evictableSize == 0) { - replica = evictableMmapped.firstEntry().getValue(); - } else { - replica = evictable.firstEntry().getValue(); + try { + if (evictableSize == 0) { + replica = (ShortCircuitReplica)evictableMmapped.get(evictableMmapped + .firstKey()); + } else { + replica = (ShortCircuitReplica)evictable.get(evictable.firstKey()); + } + } catch (NoSuchElementException e) { + break; } if (LOG.isTraceEnabled()) { LOG.trace(this + ": trimEvictionMaps is purging " + replica + @@ -573,10 +586,11 @@ public class ShortCircuitCache implements Closeable { * @param map The map to remove it from. */ private void removeEvictable(ShortCircuitReplica replica, - TreeMap<Long, ShortCircuitReplica> map) { + LinkedMap map) { Long evictableTimeNs = replica.getEvictableTimeNs(); Preconditions.checkNotNull(evictableTimeNs); - ShortCircuitReplica removed = map.remove(evictableTimeNs); + ShortCircuitReplica removed = (ShortCircuitReplica)map.remove( + evictableTimeNs); Preconditions.checkState(removed == replica, "failed to make %s unevictable", replica); replica.setEvictableTimeNs(null); @@ -593,7 +607,7 @@ public class ShortCircuitCache implements Closeable { * @param map The map to insert it into. */ private void insertEvictable(Long evictionTimeNs, - ShortCircuitReplica replica, TreeMap<Long, ShortCircuitReplica> map) { + ShortCircuitReplica replica, LinkedMap map) { while (map.containsKey(evictionTimeNs)) { evictionTimeNs++; } @@ -861,14 +875,22 @@ public class ShortCircuitCache implements Closeable { IOUtilsClient.cleanup(LOG, cacheCleaner); // Purge all replicas. while (true) { - Entry<Long, ShortCircuitReplica> entry = evictable.firstEntry(); - if (entry == null) break; - purge(entry.getValue()); + Object eldestKey; + try { + eldestKey = evictable.firstKey(); + } catch (NoSuchElementException e) { + break; + } + purge((ShortCircuitReplica)evictable.get(eldestKey)); } while (true) { - Entry<Long, ShortCircuitReplica> entry = evictableMmapped.firstEntry(); - if (entry == null) break; - purge(entry.getValue()); + Object eldestKey; + try { + eldestKey = evictableMmapped.firstKey(); + } catch (NoSuchElementException e) { + break; + } + purge((ShortCircuitReplica)evictableMmapped.get(eldestKey)); } } finally { lock.unlock(); @@ -909,8 +931,8 @@ public class ShortCircuitCache implements Closeable { void visit(int numOutstandingMmaps, Map<ExtendedBlockId, ShortCircuitReplica> replicas, Map<ExtendedBlockId, InvalidToken> failedLoads, - Map<Long, ShortCircuitReplica> evictable, - Map<Long, ShortCircuitReplica> evictableMmapped); + LinkedMap evictable, + LinkedMap evictableMmapped); } @VisibleForTesting // ONLY for testing http://git-wip-us.apache.org/repos/asf/hadoop/blob/607705c4/hadoop-hdfs-project/hadoop-hdfs/src/test/java/org/apache/hadoop/fs/TestEnhancedByteBufferAccess.java ---------------------------------------------------------------------- diff --git a/hadoop-hdfs-project/hadoop-hdfs/src/test/java/org/apache/hadoop/fs/TestEnhancedByteBufferAccess.java b/hadoop-hdfs-project/hadoop-hdfs/src/test/java/org/apache/hadoop/fs/TestEnhancedByteBufferAccess.java index 0ccc07a..9cd46c1 100644 --- a/hadoop-hdfs-project/hadoop-hdfs/src/test/java/org/apache/hadoop/fs/TestEnhancedByteBufferAccess.java +++ b/hadoop-hdfs-project/hadoop-hdfs/src/test/java/org/apache/hadoop/fs/TestEnhancedByteBufferAccess.java @@ -34,6 +34,7 @@ import java.util.Map; import java.util.Random; import java.util.concurrent.TimeoutException; +import org.apache.commons.collections.map.LinkedMap; import org.apache.commons.lang.SystemUtils; import org.apache.commons.lang.mutable.MutableBoolean; import org.apache.commons.logging.Log; @@ -307,8 +308,8 @@ public class TestEnhancedByteBufferAccess { public void visit(int numOutstandingMmaps, Map<ExtendedBlockId, ShortCircuitReplica> replicas, Map<ExtendedBlockId, InvalidToken> failedLoads, - Map<Long, ShortCircuitReplica> evictable, - Map<Long, ShortCircuitReplica> evictableMmapped) { + LinkedMap evictable, + LinkedMap evictableMmapped) { if (expectedNumOutstandingMmaps >= 0) { Assert.assertEquals(expectedNumOutstandingMmaps, numOutstandingMmaps); } @@ -373,8 +374,8 @@ public class TestEnhancedByteBufferAccess { public void visit(int numOutstandingMmaps, Map<ExtendedBlockId, ShortCircuitReplica> replicas, Map<ExtendedBlockId, InvalidToken> failedLoads, - Map<Long, ShortCircuitReplica> evictable, - Map<Long, ShortCircuitReplica> evictableMmapped) { + LinkedMap evictable, + LinkedMap evictableMmapped) { ShortCircuitReplica replica = replicas.get( new ExtendedBlockId(firstBlock.getBlockId(), firstBlock.getBlockPoolId())); Assert.assertNotNull(replica); @@ -410,8 +411,8 @@ public class TestEnhancedByteBufferAccess { public void visit(int numOutstandingMmaps, Map<ExtendedBlockId, ShortCircuitReplica> replicas, Map<ExtendedBlockId, InvalidToken> failedLoads, - Map<Long, ShortCircuitReplica> evictable, - Map<Long, ShortCircuitReplica> evictableMmapped) { + LinkedMap evictable, + LinkedMap evictableMmapped) { finished.setValue(evictableMmapped.isEmpty()); } }); @@ -685,8 +686,8 @@ public class TestEnhancedByteBufferAccess { public void visit(int numOutstandingMmaps, Map<ExtendedBlockId, ShortCircuitReplica> replicas, Map<ExtendedBlockId, InvalidToken> failedLoads, - Map<Long, ShortCircuitReplica> evictable, - Map<Long, ShortCircuitReplica> evictableMmapped) { + LinkedMap evictable, + LinkedMap evictableMmapped) { Assert.assertEquals(expectedOutstandingMmaps, numOutstandingMmaps); ShortCircuitReplica replica = replicas.get(ExtendedBlockId.fromExtendedBlock(block)); http://git-wip-us.apache.org/repos/asf/hadoop/blob/607705c4/hadoop-hdfs-project/hadoop-hdfs/src/test/java/org/apache/hadoop/hdfs/shortcircuit/TestShortCircuitCache.java ---------------------------------------------------------------------- diff --git a/hadoop-hdfs-project/hadoop-hdfs/src/test/java/org/apache/hadoop/hdfs/shortcircuit/TestShortCircuitCache.java b/hadoop-hdfs-project/hadoop-hdfs/src/test/java/org/apache/hadoop/hdfs/shortcircuit/TestShortCircuitCache.java index ac14438..8e217c2 100644 --- a/hadoop-hdfs-project/hadoop-hdfs/src/test/java/org/apache/hadoop/hdfs/shortcircuit/TestShortCircuitCache.java +++ b/hadoop-hdfs-project/hadoop-hdfs/src/test/java/org/apache/hadoop/hdfs/shortcircuit/TestShortCircuitCache.java @@ -34,6 +34,7 @@ import java.util.Iterator; import java.util.Map; import java.util.concurrent.TimeoutException; +import org.apache.commons.collections.map.LinkedMap; import org.apache.commons.lang.mutable.MutableBoolean; import org.apache.commons.logging.Log; import org.apache.commons.logging.LogFactory; @@ -502,8 +503,8 @@ public class TestShortCircuitCache { public void visit(int numOutstandingMmaps, Map<ExtendedBlockId, ShortCircuitReplica> replicas, Map<ExtendedBlockId, InvalidToken> failedLoads, - Map<Long, ShortCircuitReplica> evictable, - Map<Long, ShortCircuitReplica> evictableMmapped) { + LinkedMap evictable, + LinkedMap evictableMmapped) { ShortCircuitReplica replica = replicas.get( ExtendedBlockId.fromExtendedBlock(block)); Assert.assertNotNull(replica); @@ -518,8 +519,8 @@ public class TestShortCircuitCache { public void visit(int numOutstandingMmaps, Map<ExtendedBlockId, ShortCircuitReplica> replicas, Map<ExtendedBlockId, InvalidToken> failedLoads, - Map<Long, ShortCircuitReplica> evictable, - Map<Long, ShortCircuitReplica> evictableMmapped) { + LinkedMap evictable, + LinkedMap evictableMmapped) { ShortCircuitReplica replica = replicas.get( ExtendedBlockId.fromExtendedBlock(block)); Assert.assertNotNull(replica); --------------------------------------------------------------------- To unsubscribe, e-mail: common-commits-unsubscr...@hadoop.apache.org For additional commands, e-mail: common-commits-h...@hadoop.apache.org
