You are viewing a plain text version of this content. The canonical link for it is here.
Posted to gitbox@hive.apache.org by GitBox <gi...@apache.org> on 2020/03/07 01:00:50 UTC
[GitHub] [hive] b-slim opened a new pull request #944: [Hive-22760] Adding
Clock based eviction strategy.
b-slim opened a new pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944
This Pr adds a new Eviction strategy based on simple clock algorithm.
Main goal is to bring down the memory overhead of the cache accounting and make it lock free.
To reduce the memory overhead i have removed the unwanted fields used by lrfu strategy.
To Avoid locking i have added one bit as part of the buffer state that is modified as cas operation.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] odraese commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
odraese commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r395928192
##########
File path: llap-server/src/java/org/apache/hadoop/hive/llap/io/api/impl/LlapIoImpl.java
##########
@@ -91,143 +74,148 @@
public static final Logger CACHE_LOGGER = LoggerFactory.getLogger("LlapIoCache");
public static final Logger LOCKING_LOGGER = LoggerFactory.getLogger("LlapIoLocking");
private static final String MODE_CACHE = "cache";
+ private static final String DISPLAY_NAME = "LlapDaemonCacheMetrics-" + MetricsUtils.getHostName();
+ private static final String IO_DISPLAY_NAME = "LlapDaemonIOMetrics-" + MetricsUtils.getHostName();
// TODO: later, we may have a map
private final ColumnVectorProducer orcCvp, genericCvp;
private final ExecutorService executor;
private final LlapDaemonCacheMetrics cacheMetrics;
private final LlapDaemonIOMetrics ioMetrics;
- private ObjectName buddyAllocatorMXBean;
+ private final ObjectName buddyAllocatorMXBean;
private final Allocator allocator;
private final FileMetadataCache fileMetadataCache;
private final LowLevelCache dataCache;
private final BufferUsageManager bufferManager;
private final Configuration daemonConf;
private final LowLevelCacheMemoryManager memoryManager;
-
- private List<LlapIoDebugDump> debugDumpComponents = new ArrayList<>();
-
- private LlapIoImpl(Configuration conf) throws IOException {
- this.daemonConf = conf;
- String ioMode = HiveConf.getVar(conf, HiveConf.ConfVars.LLAP_IO_MEMORY_MODE);
- boolean useLowLevelCache = LlapIoImpl.MODE_CACHE.equalsIgnoreCase(ioMode);
- LOG.info("Initializing LLAP IO in {} mode", useLowLevelCache ? LlapIoImpl.MODE_CACHE : "none");
- String displayName = "LlapDaemonCacheMetrics-" + MetricsUtils.getHostName();
- String sessionId = conf.get("llap.daemon.metrics.sessionid");
- this.cacheMetrics = LlapDaemonCacheMetrics.create(displayName, sessionId);
-
- displayName = "LlapDaemonIOMetrics-" + MetricsUtils.getHostName();
- String[] strIntervals = HiveConf.getTrimmedStringsVar(conf,
- HiveConf.ConfVars.LLAP_IO_DECODING_METRICS_PERCENTILE_INTERVALS);
- List<Integer> intervalList = new ArrayList<>();
- if (strIntervals != null) {
- for (String strInterval : strIntervals) {
- try {
- intervalList.add(Integer.valueOf(strInterval));
- } catch (NumberFormatException e) {
- LOG.warn("Ignoring IO decoding metrics interval {} from {} as it is invalid", strInterval,
- Arrays.toString(strIntervals));
- }
- }
+ private final List<LlapIoDebugDump> debugDumpComponents = new ArrayList<>();
+
+ /**
+ * Llap IO is created via Reflection by {@link org.apache.hadoop.hive.llap.io.api.LlapProxy}.
+ *
+ * @param conf Configuration containing all the needed parameters and flags to initialize LLAP IO.
+ */
+ private LlapIoImpl(Configuration conf) {
+ this.daemonConf = Preconditions.checkNotNull(conf);
+ final boolean
+ useLowLevelCache =
+ LlapIoImpl.MODE_CACHE.equalsIgnoreCase(HiveConf.getVar(conf, HiveConf.ConfVars.LLAP_IO_MEMORY_MODE));
+ final boolean isEncodeEnabled = useLowLevelCache && HiveConf.getBoolVar(conf, ConfVars.LLAP_IO_ENCODE_ENABLED);
+ LOG.info("Initializing LLAP IO in {} mode, with Encoding = {} ",
+ useLowLevelCache ? LlapIoImpl.MODE_CACHE : "none",
+ isEncodeEnabled);
+
+ //setup metrics reporters
+ final String sessionId = conf.get("llap.daemon.metrics.sessionid");
+ final String[]
+ strIntervals =
+ HiveConf.getTrimmedStringsVar(conf, HiveConf.ConfVars.LLAP_IO_DECODING_METRICS_PERCENTILE_INTERVALS);
+ int[] intArray = stringsToIntegers(strIntervals);
+ if (strIntervals != null && strIntervals.length != intArray.length) {
+ LOG.warn("Ignoring IO decoding metrics interval from {} as it is invalid due to Number format exception",
+ Arrays.toString(strIntervals));
}
- this.ioMetrics = LlapDaemonIOMetrics.create(displayName, sessionId, Ints.toArray(intervalList));
+ this.ioMetrics = LlapDaemonIOMetrics.create(IO_DISPLAY_NAME, sessionId, intArray);
+ this.cacheMetrics = LlapDaemonCacheMetrics.create(DISPLAY_NAME, sessionId);
+ LOG.info("Started llap daemon metrics with displayName: {} sessionId: {}", IO_DISPLAY_NAME, sessionId);
- LOG.info("Started llap daemon metrics with displayName: {} sessionId: {}", displayName,
- sessionId);
+ int numThreads = HiveConf.getIntVar(conf, HiveConf.ConfVars.LLAP_IO_THREADPOOL_SIZE);
+ this.executor =
+ new StatsRecordingThreadPool(numThreads,
+ numThreads,
+ 0L,
+ TimeUnit.MILLISECONDS,
+ new LinkedBlockingQueue<>(),
+ new ThreadFactoryBuilder().setNameFormat("IO-Elevator-Thread-%d").setDaemon(true).build());
+ LOG.info("Created IO Elevator Thread pool with {} Threads ", numThreads);
+ // IO thread pool. Listening is used for unhandled errors for now (TODO: remove?)
+ FixedSizedObjectPool<IoTrace> tracePool = IoTrace.createTracePool(conf, numThreads);
- MetadataCache metadataCache = null;
- SerDeLowLevelCacheImpl serdeCache = null; // TODO: extract interface when needed
- BufferUsageManager bufferManagerOrc = null, bufferManagerGeneric = null;
- boolean isEncodeEnabled = useLowLevelCache
- && HiveConf.getBoolVar(conf, ConfVars.LLAP_IO_ENCODE_ENABLED);
+ final MetadataCache metadataCache;
+ final BufferUsageManager bufferManagerOrc, bufferManagerGeneric;
+ final SerDeLowLevelCacheImpl serdeCache; // TODO: extract interface when needed
if (useLowLevelCache) {
// Memory manager uses cache policy to trigger evictions, so create the policy first.
- boolean useLrfu = HiveConf.getBoolVar(conf, HiveConf.ConfVars.LLAP_USE_LRFU);
- long totalMemorySize = HiveConf.getSizeVar(conf, ConfVars.LLAP_IO_MEMORY_MAX_SIZE);
- int minAllocSize = (int) HiveConf.getSizeVar(conf, ConfVars.LLAP_ALLOCATOR_MIN_ALLOC);
- LowLevelCachePolicy
- realCachePolicy =
- useLrfu ? new LowLevelLrfuCachePolicy(minAllocSize, totalMemorySize, conf) : new LowLevelFifoCachePolicy();
- boolean trackUsage = HiveConf.getBoolVar(conf, HiveConf.ConfVars.LLAP_TRACK_CACHE_USAGE);
- LowLevelCachePolicy cachePolicyWrapper;
- if (trackUsage) {
- cachePolicyWrapper = new CacheContentsTracker(realCachePolicy);
- } else {
- cachePolicyWrapper = realCachePolicy;
- }
+ final long totalMemorySize = HiveConf.getSizeVar(conf, ConfVars.LLAP_IO_MEMORY_MAX_SIZE);
+
+ final LowLevelCachePolicy cachePolicyWrapper = LowLevelCachePolicy.provideFromConf(conf);
+
// Allocator uses memory manager to request memory, so create the manager next.
- this.memoryManager = new LowLevelCacheMemoryManager(
- totalMemorySize, cachePolicyWrapper, cacheMetrics);
- cacheMetrics.setCacheCapacityTotal(totalMemorySize);
+ this.memoryManager = new LowLevelCacheMemoryManager(totalMemorySize, cachePolicyWrapper, cacheMetrics);
+ this.cacheMetrics.setCacheCapacityTotal(totalMemorySize);
// Cache uses allocator to allocate and deallocate, create allocator and then caches.
BuddyAllocator allocator = new BuddyAllocator(conf, memoryManager, cacheMetrics);
this.allocator = allocator;
- LowLevelCacheImpl cacheImpl = new LowLevelCacheImpl(
- cacheMetrics, cachePolicyWrapper, allocator, true);
- dataCache = cacheImpl;
+ LowLevelCacheImpl cacheImpl = new LowLevelCacheImpl(cacheMetrics, cachePolicyWrapper, allocator, true);
+ this.dataCache = cacheImpl;
if (isEncodeEnabled) {
- SerDeLowLevelCacheImpl serdeCacheImpl = new SerDeLowLevelCacheImpl(
- cacheMetrics, cachePolicyWrapper, allocator);
- serdeCache = serdeCacheImpl;
- serdeCacheImpl.setConf(conf);
+ serdeCache = new SerDeLowLevelCacheImpl(cacheMetrics, cachePolicyWrapper, allocator);
+ serdeCache.setConf(conf);
+ } else {
+ serdeCache = null;
}
-
- boolean useGapCache = HiveConf.getBoolVar(conf, ConfVars.LLAP_CACHE_ENABLE_ORC_GAP_CACHE);
- metadataCache = new MetadataCache(
- allocator, memoryManager, cachePolicyWrapper, useGapCache, cacheMetrics);
- fileMetadataCache = metadataCache;
+ final boolean useGapCache = HiveConf.getBoolVar(conf, ConfVars.LLAP_CACHE_ENABLE_ORC_GAP_CACHE);
+ metadataCache = new MetadataCache(allocator, memoryManager, cachePolicyWrapper, useGapCache, cacheMetrics);
+ this.fileMetadataCache = metadataCache;
// And finally cache policy uses cache to notify it of eviction. The cycle is complete!
- EvictionDispatcher e = new EvictionDispatcher(
- dataCache, serdeCache, metadataCache, allocator);
+ final EvictionDispatcher e = new EvictionDispatcher(dataCache, serdeCache, metadataCache, allocator);
cachePolicyWrapper.setEvictionListener(e);
-
cacheImpl.startThreads(); // Start the cache threads.
bufferManager = bufferManagerOrc = cacheImpl; // Cache also serves as buffer manager.
bufferManagerGeneric = serdeCache;
- if (trackUsage) {
- debugDumpComponents.add(cachePolicyWrapper); // Cache contents tracker.
- }
- debugDumpComponents.add(realCachePolicy);
+ debugDumpComponents.add(cachePolicyWrapper); // Cache contents tracker.
debugDumpComponents.add(cacheImpl);
if (serdeCache != null) {
debugDumpComponents.add(serdeCache);
}
- if (metadataCache != null) {
- debugDumpComponents.add(metadataCache);
- }
+ debugDumpComponents.add(metadataCache);
debugDumpComponents.add(allocator);
} else {
this.allocator = new SimpleAllocator(conf);
- fileMetadataCache = null;
- SimpleBufferManager sbm = new SimpleBufferManager(allocator, cacheMetrics);
- bufferManager = bufferManagerOrc = bufferManagerGeneric = sbm;
- dataCache = sbm;
+ final SimpleBufferManager sbm = new SimpleBufferManager(allocator, cacheMetrics);
+ this.bufferManager = bufferManagerOrc = bufferManagerGeneric = sbm;
+ this.dataCache = sbm;
+ this.debugDumpComponents.add(sb -> sb.append("LLAP IO allocator is not in use!"));
+ this.fileMetadataCache = null;
this.memoryManager = null;
- debugDumpComponents.add(new LlapIoDebugDump() {
- @Override
- public void debugDumpShort(StringBuilder sb) {
- sb.append("LLAP IO allocator is not in use!");
- }
- });
+ serdeCache = null;
+ metadataCache = null;
}
- // IO thread pool. Listening is used for unhandled errors for now (TODO: remove?)
- int numThreads = HiveConf.getIntVar(conf, HiveConf.ConfVars.LLAP_IO_THREADPOOL_SIZE);
- executor = new StatsRecordingThreadPool(numThreads, numThreads, 0L, TimeUnit.MILLISECONDS,
- new LinkedBlockingQueue<Runnable>(),
- new ThreadFactoryBuilder().setNameFormat("IO-Elevator-Thread-%d").setDaemon(true).build());
- FixedSizedObjectPool<IoTrace> tracePool = IoTrace.createTracePool(conf);
- // TODO: this should depends on input format and be in a map, or something.
- this.orcCvp = new OrcColumnVectorProducer(
- metadataCache, dataCache, bufferManagerOrc, conf, cacheMetrics, ioMetrics, tracePool);
- this.genericCvp = isEncodeEnabled ? new GenericColumnVectorProducer(
- serdeCache, bufferManagerGeneric, conf, cacheMetrics, ioMetrics, tracePool) : null;
- LOG.info("LLAP IO initialized");
- registerMXBeans();
+ // TODO: this should depends on input format and be in a map, or something.
+ this.orcCvp =
+ new OrcColumnVectorProducer(metadataCache,
+ dataCache,
+ bufferManagerOrc,
+ conf,
+ cacheMetrics,
+ ioMetrics,
+ tracePool);
+ this.genericCvp =
+ isEncodeEnabled ?
+ new GenericColumnVectorProducer(serdeCache,
+ bufferManagerGeneric,
+ conf,
+ cacheMetrics,
+ ioMetrics,
+ tracePool) :
+ null;
+ this.buddyAllocatorMXBean = MBeans.register("LlapDaemon", "BuddyAllocatorInfo", allocator);
+ LOG.info("LLAP IO successful initialized.");
}
- private void registerMXBeans() {
- buddyAllocatorMXBean = MBeans.register("LlapDaemon", "BuddyAllocatorInfo", allocator);
+ private static int[] stringsToIntegers(String[] strings) {
+ if (strings == null) {
+ return new int[0];
+ }
+ return Arrays.stream(strings).map(x -> {
Review comment:
not that I don't appreciate a nice stream function but I suspect this is the least efficient method to covnert integer strings to int. each instance is wrapped into an optional just fo filter out the non-parsable directly again?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] b-slim commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
b-slim commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r396556494
##########
File path: llap-server/src/java/org/apache/hadoop/hive/llap/cache/ClockCachePolicy.java
##########
@@ -0,0 +1,264 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.hadoop.hive.llap.cache;
+
+import com.google.common.annotations.VisibleForTesting;
+import com.google.common.base.Preconditions;
+
+import javax.annotation.concurrent.GuardedBy;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+import java.util.concurrent.locks.Lock;
+import java.util.concurrent.locks.ReentrantLock;
+
+/**
+ * Clock eviction policy. Uses a simple circular list to keep a ring of current used buffers.
+ * New entries are added to tail of the clock hand AKA (clockHand.prev)
+ * Eviction start at the current clock hand following the next pointer.
+ *
+ */
+public class ClockCachePolicy implements LowLevelCachePolicy {
+
+ private static final int DEFAULT_MAX_CIRCLES = 5;
+
+ /**
+ * Lock to protect the state of the policy, used as mutex when modifying the circular linked list.
+ */
+ private final Lock listLock = new ReentrantLock();
+
+ /**
+ * The clock hand shared between threads thus made volatile, to ensure state when read outside of lock.
+ */
+ @GuardedBy("listLock")
+ private volatile LlapCacheableBuffer clockHand;
+
+ private EvictionListener evictionListener;
+ /**
+ * Max number of clock rotation before giving up on clock operation like eviction.
+ */
+ private final int maxCircles;
+
+ public ClockCachePolicy() {
+ maxCircles = DEFAULT_MAX_CIRCLES;
+ }
+
+ public ClockCachePolicy(int maxCircles) {
+ Preconditions.checkState(maxCircles > 0, "Maximum number of clock rotation must be positive and got " + maxCircles);
+ this.maxCircles = maxCircles;
+ }
+
+ /**
+ * Signals to the policy the addition of a new entry to the cache. An entry come with a priority that can be used as
+ * a hint to replacement policy.
+ *
+ * @param buffer buffer to be cached
+ * @param priority the priority of cached element
+ */
+ @Override public void cache(LlapCacheableBuffer buffer, LowLevelCache.Priority priority) {
+ listLock.lock();
+ try {
+ clockHand = appendToCircularList(clockHand, buffer);
+ } finally {
+ listLock.unlock();
+ }
+ }
+
+ /**
+ * Appends new entry to the tail of circular list.
+ *
+ * @param head circular list head.
+ * @param buffer new entry to be added.
+ * @return the ring head.
+ */
+ private static LlapCacheableBuffer appendToCircularList(LlapCacheableBuffer head, LlapCacheableBuffer buffer) {
+ if (head == null) {
+ return linkToItSelf(buffer);
+ }
+ buffer.next = head;
+ buffer.prev = head.prev;
+ head.prev.next = buffer;
+ head.prev = buffer;
+ return head;
+ }
+
+ /**
+ * Links the entry to it self to form a ring.
+ *
+ * @param buffer input
+ * @return buffer
+ */
+ private static LlapCacheableBuffer linkToItSelf(LlapCacheableBuffer buffer) {
+ buffer.prev = buffer;
+ buffer.next = buffer;
+ return buffer;
+ }
+
+ @Override public void notifyLock(LlapCacheableBuffer buffer) {
+ buffer.setClockBit();
+ }
+
+ /**
+ * Notifies the policy that a buffer is unlocked after been used. This notification signals to the policy that an
+ * access to this page occurred.
+ *
+ * @param buffer buffer that just got unlocked after a read.
+ */
+ @Override public void notifyUnlock(LlapCacheableBuffer buffer) {
+
+ }
+
+ /**
+ * Signals to the policy that it has to evict some entries from the cache.
+ * Policy has to at least evict the amount memory requested.
+ * Not that is method will block until at least {@code memoryToReserve} bytes are evicted.
+ *
+ * @param memoryToReserve amount of bytes to be evicted
+ * @return actual amount of evicted bytes.
+ */
+ @Override public long evictSomeBlocks(long memoryToReserve) {
+ long evicted = 0;
+ if (clockHand == null) {
+ return evicted;
+ }
+ int fullClockRotation = 0;
+ listLock.lock();
+ try {
+ // ring tail is used to mark a clock circle
+ LlapCacheableBuffer ringTail = clockHand.prev;
+ // ring head is the current clock position that is under lock. Using local var under lock and updating actual
+ // clock position as soon we are done with looping
+ LlapCacheableBuffer currentClockHead = clockHand;
Review comment:
i agree, thought clock hand is volatile thus i want to avoid the write/read fence when using it.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] b-slim commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
b-slim commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r401790919
##########
File path: llap-server/src/java/org/apache/hadoop/hive/llap/cache/LlapAllocatorBuffer.java
##########
@@ -337,25 +364,34 @@ public Boolean endDiscard() {
return result;
}
- private static final class State {
- public static final int
- FLAG_MOVING = 0b00001, // Locked by someone to move or force-evict.
- FLAG_EVICTED = 0b00010, // Evicted. This is cache-specific.
- FLAG_REMOVED = 0b00100, // Removed from allocator structures. The final state.
- FLAG_MEM_RELEASED = 0b01000, // The memory was released to memory manager.
- FLAG_NEW_ALLOC = 0b10000; // New allocation before the first use; cannot force-evict.
- private static final int FLAGS_WIDTH = 5,
- REFCOUNT_WIDTH = 19, ARENA_WIDTH = 16, HEADER_WIDTH = 24;
-
- public static final long MAX_REFCOUNT = (1 << REFCOUNT_WIDTH) - 1;
-
- private static final int REFCOUNT_SHIFT = FLAGS_WIDTH,
- ARENA_SHIFT = REFCOUNT_SHIFT + REFCOUNT_WIDTH, HEADER_SHIFT = ARENA_SHIFT + ARENA_WIDTH;
-
- private static final long FLAGS_MASK = (1L << FLAGS_WIDTH) - 1,
- REFCOUNT_MASK = ((1L << REFCOUNT_WIDTH) - 1) << REFCOUNT_SHIFT,
- ARENA_MASK = ((1L << ARENA_WIDTH) - 1) << ARENA_SHIFT,
- HEADER_MASK = ((1L << HEADER_WIDTH) - 1) << HEADER_SHIFT;
+ /**
+ * Utility class to manipulate the buffer state.
+ */
+ static final class State {
Review comment:
Sure I will but, it will make the diff bigger therefore more code review :D
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] b-slim commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
b-slim commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r401738178
##########
File path: llap-server/src/java/org/apache/hadoop/hive/llap/cache/ClockCachePolicy.java
##########
@@ -0,0 +1,313 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.hadoop.hive.llap.cache;
+
+import com.google.common.annotations.VisibleForTesting;
+import com.google.common.base.Preconditions;
+import org.apache.hadoop.hive.llap.io.metadata.MetadataCache;
+
+import javax.annotation.concurrent.GuardedBy;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+import java.util.concurrent.locks.Lock;
+import java.util.concurrent.locks.ReentrantLock;
+
+/**
+ * Clock eviction policy. Uses a simple circular list to keep a ring of current used buffers.
+ * New entries are added to tail of the clock hand AKA (clockHand.prev)
+ * Eviction start at the current clock hand following the next pointer.
+ *
+ */
+public class ClockCachePolicy implements LowLevelCachePolicy {
+
+ private static final int DEFAULT_MAX_CIRCLES = 5;
+
+ /**
+ * Lock to protect the state of the policy, used as mutex when modifying the circular linked list.
+ */
+ private final Lock listLock = new ReentrantLock();
+
+ /**
+ * The clock hand shared between threads thus made volatile, to ensure state when read outside of lock.
+ */
+ @GuardedBy("listLock")
+ private volatile LlapCacheableBuffer clockHand;
+
+ private EvictionListener evictionListener;
+ /**
+ * Max number of clock rotation before giving up on clock operation like eviction.
+ */
+ private final int maxCircles;
+
+ public ClockCachePolicy() {
+ maxCircles = DEFAULT_MAX_CIRCLES;
+ }
+
+ public ClockCachePolicy(int maxCircles) {
+ Preconditions.checkState(maxCircles > 0, "Maximum number of clock rotation must be positive and got " + maxCircles);
+ this.maxCircles = maxCircles;
+ }
+
+ /**
+ * Signals to the policy the addition of a new entry to the cache. An entry come with a priority that can be used as
+ * a hint to replacement policy.
+ *
+ * @param buffer buffer to be cached
+ * @param priority the priority of cached element
+ */
+ @Override public void cache(LlapCacheableBuffer buffer, LowLevelCache.Priority priority) {
+ listLock.lock();
+ try {
+ //noinspection NonAtomicOperationOnVolatileField
+ clockHand = appendToCircularList(clockHand, buffer);
+ } finally {
+ listLock.unlock();
+ }
+ }
+
+ /**
+ * Appends new entry to the tail of circular list.
+ *
+ * @param head circular list head.
+ * @param buffer new entry to be added.
+ * @return the ring head.
+ */
+ private static LlapCacheableBuffer appendToCircularList(LlapCacheableBuffer head, LlapCacheableBuffer buffer) {
Review comment:
makes compiler/inlining better and testing much simpler.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] b-slim commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
b-slim commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r396615343
##########
File path: llap-server/src/java/org/apache/hadoop/hive/llap/cache/LlapCacheableBuffer.java
##########
@@ -26,39 +26,71 @@
* using a real programming language.
*/
public abstract class LlapCacheableBuffer {
- protected static final int IN_LIST = -2, NOT_IN_CACHE = -1;
-
- /** Priority for cache policy (should be pretty universal). */
- public double priority;
- /** Last priority update time for cache policy (should be pretty universal). */
- public long lastUpdate = -1;
+ public static final int INVALIDATE_OK = 0, INVALIDATE_FAILED = 1, INVALIDATE_ALREADY_INVALID = 2;
- // TODO: remove some of these fields as needed?
+ public CacheAttribute cacheAttribute;
/** Linked list pointers for LRFU/LRU cache policies. Given that each block is in cache
* that might be better than external linked list. Or not, since this is not concurrent. */
public LlapCacheableBuffer prev = null;
/** Linked list pointers for LRFU/LRU cache policies. Given that each block is in cache
* that might be better than external linked list. Or not, since this is not concurrent. */
public LlapCacheableBuffer next = null;
- /** Index in heap for LRFU/LFU cache policies. */
- public int indexInHeap = NOT_IN_CACHE;
- public static final int INVALIDATE_OK = 0, INVALIDATE_FAILED = 1, INVALIDATE_ALREADY_INVALID = 2;
+ /**
+ * @return result of invalidation.
+ */
protected abstract int invalidate();
+
+ /**
+ * @return size of the buffer in bytes.
+ */
public abstract long getMemoryUsage();
+
+ /**
+ * @param evictionDispatcher dispatcher object to be notified.
+ */
public abstract void notifyEvicted(EvictionDispatcher evictionDispatcher);
+ /**
+ * Set the clock bit to true, should be thread safe
+ */
+ public abstract void setClockBit();
+
+ /**
+ * Set the clock bit to false, should be thread safe.
+ */
+ public abstract void unSetClockBit();
+
+ /**
+ * @return value of the clock bit.
+ */
+ public abstract boolean isClockBitSet();
+
@Override
public String toString() {
return "0x" + Integer.toHexString(System.identityHashCode(this));
}
public String toStringForCache() {
- return "[" + Integer.toHexString(hashCode()) + " " + String.format("%1$.2f", priority) + " "
- + lastUpdate + " " + (isLocked() ? "!" : ".") + "]";
+ return "[" + Integer.toHexString(hashCode()) + " Cache Attributes " + cacheAttribute == null ? "NONE" : cacheAttribute.toString() + " " + (isLocked() ? "!" : ".") + "]";
}
+ /**
+ * @return human readable tag used by the cache content tracker.
+ */
public abstract CacheTag getTag();
+ /**
+ * @return true if the buffer is locked as part of query execution.
+ */
protected abstract boolean isLocked();
+
+ public interface CacheAttribute {
Review comment:
done
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] b-slim commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
b-slim commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r396625480
##########
File path: llap-server/src/java/org/apache/hadoop/hive/llap/cache/LowLevelLrfuCachePolicy.java
##########
@@ -491,29 +499,32 @@ private int moveMinChildUp(int targetPos, long time, double comparePri) {
}
if (leftPri <= rightPri) { // prefer left, cause right might be missing
heap[targetPos] = left;
- left.indexInHeap = targetPos;
+ LrfuCacheAttribute leftCacheAttribute = (LrfuCacheAttribute) left.cacheAttribute;
+ leftCacheAttribute.indexInHeap = targetPos;
Review comment:
less work on the compiler :D i can use setter if you think it is better.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] odraese commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
odraese commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r395926822
##########
File path: llap-server/src/java/org/apache/hadoop/hive/llap/cache/LrfuCacheAttribute.java
##########
@@ -0,0 +1,68 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.hadoop.hive.llap.cache;
+
+public final class LrfuCacheAttribute implements LlapCacheableBuffer.CacheAttribute {
+ /** Priority for cache policy (should be pretty universal). */
+ public double priority;
Review comment:
all these have public setter/getter methods. there isn't any reason to have the fields public as well...?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] prasanthj commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
prasanthj commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r400416933
##########
File path: llap-server/src/java/org/apache/hadoop/hive/llap/cache/ClockCachePolicy.java
##########
@@ -0,0 +1,313 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.hadoop.hive.llap.cache;
+
+import com.google.common.annotations.VisibleForTesting;
+import com.google.common.base.Preconditions;
+import org.apache.hadoop.hive.llap.io.metadata.MetadataCache;
+
+import javax.annotation.concurrent.GuardedBy;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+import java.util.concurrent.locks.Lock;
+import java.util.concurrent.locks.ReentrantLock;
+
+/**
+ * Clock eviction policy. Uses a simple circular list to keep a ring of current used buffers.
+ * New entries are added to tail of the clock hand AKA (clockHand.prev)
+ * Eviction start at the current clock hand following the next pointer.
+ *
+ */
+public class ClockCachePolicy implements LowLevelCachePolicy {
+
+ private static final int DEFAULT_MAX_CIRCLES = 5;
+
+ /**
+ * Lock to protect the state of the policy, used as mutex when modifying the circular linked list.
+ */
+ private final Lock listLock = new ReentrantLock();
+
+ /**
+ * The clock hand shared between threads thus made volatile, to ensure state when read outside of lock.
+ */
+ @GuardedBy("listLock")
+ private volatile LlapCacheableBuffer clockHand;
+
+ private EvictionListener evictionListener;
+ /**
+ * Max number of clock rotation before giving up on clock operation like eviction.
+ */
+ private final int maxCircles;
+
+ public ClockCachePolicy() {
+ maxCircles = DEFAULT_MAX_CIRCLES;
+ }
+
+ public ClockCachePolicy(int maxCircles) {
+ Preconditions.checkState(maxCircles > 0, "Maximum number of clock rotation must be positive and got " + maxCircles);
+ this.maxCircles = maxCircles;
+ }
+
+ /**
+ * Signals to the policy the addition of a new entry to the cache. An entry come with a priority that can be used as
+ * a hint to replacement policy.
+ *
+ * @param buffer buffer to be cached
+ * @param priority the priority of cached element
+ */
+ @Override public void cache(LlapCacheableBuffer buffer, LowLevelCache.Priority priority) {
+ listLock.lock();
+ try {
+ //noinspection NonAtomicOperationOnVolatileField
+ clockHand = appendToCircularList(clockHand, buffer);
+ } finally {
+ listLock.unlock();
+ }
+ }
+
+ /**
+ * Appends new entry to the tail of circular list.
+ *
+ * @param head circular list head.
+ * @param buffer new entry to be added.
+ * @return the ring head.
+ */
+ private static LlapCacheableBuffer appendToCircularList(LlapCacheableBuffer head, LlapCacheableBuffer buffer) {
Review comment:
static required?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] odraese commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
odraese commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r395917171
##########
File path: llap-server/src/java/org/apache/hadoop/hive/llap/cache/ClockCachePolicy.java
##########
@@ -0,0 +1,264 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.hadoop.hive.llap.cache;
+
+import com.google.common.annotations.VisibleForTesting;
+import com.google.common.base.Preconditions;
+
+import javax.annotation.concurrent.GuardedBy;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+import java.util.concurrent.locks.Lock;
+import java.util.concurrent.locks.ReentrantLock;
+
+/**
+ * Clock eviction policy. Uses a simple circular list to keep a ring of current used buffers.
+ * New entries are added to tail of the clock hand AKA (clockHand.prev)
+ * Eviction start at the current clock hand following the next pointer.
+ *
+ */
+public class ClockCachePolicy implements LowLevelCachePolicy {
+
+ private static final int DEFAULT_MAX_CIRCLES = 5;
+
+ /**
+ * Lock to protect the state of the policy, used as mutex when modifying the circular linked list.
+ */
+ private final Lock listLock = new ReentrantLock();
+
+ /**
+ * The clock hand shared between threads thus made volatile, to ensure state when read outside of lock.
+ */
+ @GuardedBy("listLock")
+ private volatile LlapCacheableBuffer clockHand;
+
+ private EvictionListener evictionListener;
+ /**
+ * Max number of clock rotation before giving up on clock operation like eviction.
+ */
+ private final int maxCircles;
+
+ public ClockCachePolicy() {
+ maxCircles = DEFAULT_MAX_CIRCLES;
+ }
+
+ public ClockCachePolicy(int maxCircles) {
+ Preconditions.checkState(maxCircles > 0, "Maximum number of clock rotation must be positive and got " + maxCircles);
+ this.maxCircles = maxCircles;
+ }
+
+ /**
+ * Signals to the policy the addition of a new entry to the cache. An entry come with a priority that can be used as
+ * a hint to replacement policy.
+ *
+ * @param buffer buffer to be cached
+ * @param priority the priority of cached element
+ */
+ @Override public void cache(LlapCacheableBuffer buffer, LowLevelCache.Priority priority) {
+ listLock.lock();
+ try {
+ clockHand = appendToCircularList(clockHand, buffer);
+ } finally {
+ listLock.unlock();
+ }
+ }
+
+ /**
+ * Appends new entry to the tail of circular list.
+ *
+ * @param head circular list head.
+ * @param buffer new entry to be added.
+ * @return the ring head.
+ */
+ private static LlapCacheableBuffer appendToCircularList(LlapCacheableBuffer head, LlapCacheableBuffer buffer) {
+ if (head == null) {
+ return linkToItSelf(buffer);
+ }
+ buffer.next = head;
+ buffer.prev = head.prev;
+ head.prev.next = buffer;
+ head.prev = buffer;
+ return head;
+ }
+
+ /**
+ * Links the entry to it self to form a ring.
+ *
+ * @param buffer input
+ * @return buffer
+ */
+ private static LlapCacheableBuffer linkToItSelf(LlapCacheableBuffer buffer) {
+ buffer.prev = buffer;
+ buffer.next = buffer;
+ return buffer;
+ }
+
+ @Override public void notifyLock(LlapCacheableBuffer buffer) {
+ buffer.setClockBit();
+ }
+
+ /**
+ * Notifies the policy that a buffer is unlocked after been used. This notification signals to the policy that an
+ * access to this page occurred.
+ *
+ * @param buffer buffer that just got unlocked after a read.
+ */
+ @Override public void notifyUnlock(LlapCacheableBuffer buffer) {
+
+ }
+
+ /**
+ * Signals to the policy that it has to evict some entries from the cache.
+ * Policy has to at least evict the amount memory requested.
+ * Not that is method will block until at least {@code memoryToReserve} bytes are evicted.
+ *
+ * @param memoryToReserve amount of bytes to be evicted
+ * @return actual amount of evicted bytes.
+ */
+ @Override public long evictSomeBlocks(long memoryToReserve) {
+ long evicted = 0;
+ if (clockHand == null) {
+ return evicted;
+ }
+ int fullClockRotation = 0;
+ listLock.lock();
+ try {
+ // ring tail is used to mark a clock circle
+ LlapCacheableBuffer ringTail = clockHand.prev;
+ // ring head is the current clock position that is under lock. Using local var under lock and updating actual
+ // clock position as soon we are done with looping
+ LlapCacheableBuffer currentClockHead = clockHand;
+
+ while (evicted < memoryToReserve && currentClockHead != null && fullClockRotation < maxCircles) {
+ if (ringTail == currentClockHead) {
+ fullClockRotation++;
+ }
+ if (currentClockHead.isClockBitSet()) {
Review comment:
isClockBitSet and unSetClockBit could be combined into single method
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] odraese commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
odraese commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r395925007
##########
File path: llap-server/src/java/org/apache/hadoop/hive/llap/cache/LowLevelCachePolicy.java
##########
@@ -26,6 +28,32 @@
*/
public interface LowLevelCachePolicy extends LlapIoDebugDump {
+ static LowLevelCachePolicy provideFromConf(Configuration conf) {
+ final long totalMemorySize = HiveConf.getSizeVar(conf, HiveConf.ConfVars.LLAP_IO_MEMORY_MAX_SIZE);
+ final int minAllocSize = (int) HiveConf.getSizeVar(conf, HiveConf.ConfVars.LLAP_ALLOCATOR_MIN_ALLOC);
+ String policyName = HiveConf.getVar(conf,HiveConf.ConfVars.LLAP_IO_CACHE_STRATEGY);
Review comment:
would it make sense to lowerCase the conf?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] odraese commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
odraese commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r395919011
##########
File path: llap-server/src/java/org/apache/hadoop/hive/llap/cache/ClockCachePolicy.java
##########
@@ -0,0 +1,264 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.hadoop.hive.llap.cache;
+
+import com.google.common.annotations.VisibleForTesting;
+import com.google.common.base.Preconditions;
+
+import javax.annotation.concurrent.GuardedBy;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+import java.util.concurrent.locks.Lock;
+import java.util.concurrent.locks.ReentrantLock;
+
+/**
+ * Clock eviction policy. Uses a simple circular list to keep a ring of current used buffers.
+ * New entries are added to tail of the clock hand AKA (clockHand.prev)
+ * Eviction start at the current clock hand following the next pointer.
+ *
+ */
+public class ClockCachePolicy implements LowLevelCachePolicy {
+
+ private static final int DEFAULT_MAX_CIRCLES = 5;
+
+ /**
+ * Lock to protect the state of the policy, used as mutex when modifying the circular linked list.
+ */
+ private final Lock listLock = new ReentrantLock();
+
+ /**
+ * The clock hand shared between threads thus made volatile, to ensure state when read outside of lock.
+ */
+ @GuardedBy("listLock")
+ private volatile LlapCacheableBuffer clockHand;
+
+ private EvictionListener evictionListener;
+ /**
+ * Max number of clock rotation before giving up on clock operation like eviction.
+ */
+ private final int maxCircles;
+
+ public ClockCachePolicy() {
+ maxCircles = DEFAULT_MAX_CIRCLES;
+ }
+
+ public ClockCachePolicy(int maxCircles) {
+ Preconditions.checkState(maxCircles > 0, "Maximum number of clock rotation must be positive and got " + maxCircles);
+ this.maxCircles = maxCircles;
+ }
+
+ /**
+ * Signals to the policy the addition of a new entry to the cache. An entry come with a priority that can be used as
+ * a hint to replacement policy.
+ *
+ * @param buffer buffer to be cached
+ * @param priority the priority of cached element
+ */
+ @Override public void cache(LlapCacheableBuffer buffer, LowLevelCache.Priority priority) {
+ listLock.lock();
+ try {
+ clockHand = appendToCircularList(clockHand, buffer);
+ } finally {
+ listLock.unlock();
+ }
+ }
+
+ /**
+ * Appends new entry to the tail of circular list.
+ *
+ * @param head circular list head.
+ * @param buffer new entry to be added.
+ * @return the ring head.
+ */
+ private static LlapCacheableBuffer appendToCircularList(LlapCacheableBuffer head, LlapCacheableBuffer buffer) {
+ if (head == null) {
+ return linkToItSelf(buffer);
+ }
+ buffer.next = head;
+ buffer.prev = head.prev;
+ head.prev.next = buffer;
+ head.prev = buffer;
+ return head;
+ }
+
+ /**
+ * Links the entry to it self to form a ring.
+ *
+ * @param buffer input
+ * @return buffer
+ */
+ private static LlapCacheableBuffer linkToItSelf(LlapCacheableBuffer buffer) {
+ buffer.prev = buffer;
+ buffer.next = buffer;
+ return buffer;
+ }
+
+ @Override public void notifyLock(LlapCacheableBuffer buffer) {
+ buffer.setClockBit();
+ }
+
+ /**
+ * Notifies the policy that a buffer is unlocked after been used. This notification signals to the policy that an
+ * access to this page occurred.
+ *
+ * @param buffer buffer that just got unlocked after a read.
+ */
+ @Override public void notifyUnlock(LlapCacheableBuffer buffer) {
+
+ }
+
+ /**
+ * Signals to the policy that it has to evict some entries from the cache.
+ * Policy has to at least evict the amount memory requested.
+ * Not that is method will block until at least {@code memoryToReserve} bytes are evicted.
+ *
+ * @param memoryToReserve amount of bytes to be evicted
+ * @return actual amount of evicted bytes.
+ */
+ @Override public long evictSomeBlocks(long memoryToReserve) {
+ long evicted = 0;
+ if (clockHand == null) {
+ return evicted;
+ }
+ int fullClockRotation = 0;
+ listLock.lock();
+ try {
+ // ring tail is used to mark a clock circle
+ LlapCacheableBuffer ringTail = clockHand.prev;
+ // ring head is the current clock position that is under lock. Using local var under lock and updating actual
+ // clock position as soon we are done with looping
+ LlapCacheableBuffer currentClockHead = clockHand;
+
+ while (evicted < memoryToReserve && currentClockHead != null && fullClockRotation < maxCircles) {
+ if (ringTail == currentClockHead) {
+ fullClockRotation++;
+ }
+ if (currentClockHead.isClockBitSet()) {
+ // case the buffer getting second chance.
+ currentClockHead.unSetClockBit();
+ currentClockHead = currentClockHead.next;
+ } else {
+ // try to evict this victim
+ int invalidateFlag = currentClockHead.invalidate();
+ if (invalidateFlag == LlapCacheableBuffer.INVALIDATE_OK
+ || invalidateFlag == LlapCacheableBuffer.INVALIDATE_ALREADY_INVALID) {
+ if (invalidateFlag == LlapCacheableBuffer.INVALIDATE_OK) {
+ // case we are able to evict the buffer notify and account for it.
+ evictionListener.notifyEvicted(currentClockHead);
+ evicted += currentClockHead.getMemoryUsage();
+ }
+ LlapCacheableBuffer newHand = currentClockHead.next;
+ if (newHand == currentClockHead) {
+ // end of the ring we have looped, nothing else can be done...
+ currentClockHead = null;
+ break;
+ } else {
+ //remove it from the ring.
+ if (currentClockHead == ringTail) {
+ // we are about to remove the current ring tail thus we need to compute new tail
+ ringTail = ringTail.prev;
+ }
+ currentClockHead.prev.next = newHand;
+ newHand.prev = currentClockHead.prev;
+ currentClockHead = newHand;
+ }
+ } else if (invalidateFlag == LlapCacheableBuffer.INVALIDATE_FAILED) {
+ // can not be evicted case locked
+ currentClockHead = currentClockHead.next;
+ } else {
+ throw new IllegalStateException("Unknown invalidation flag " + invalidateFlag);
+ }
+ }
+ }
+ // done with clock rotations, update the current clock hand under lock.
+ clockHand = currentClockHead;
+ return evicted;
+ } finally {
+ listLock.unlock();
+ }
+ }
+
+ @Override public void setEvictionListener(EvictionListener listener) {
+ evictionListener = listener;
+ }
+
+ @Override public long purge() {
+ return evictSomeBlocks(Long.MAX_VALUE);
+ }
+
+ @Override public void debugDumpShort(StringBuilder sb) {
+ if (clockHand == null) {
+ sb.append("Clock is empty");
+ return;
+ }
+ listLock.lock();
+ try {
+ sb.append("Clock Status\n");
+ LlapCacheableBuffer currentClockHand = clockHand;
+ LlapCacheableBuffer lastElement = clockHand.prev;
+ while (currentClockHand != lastElement) {
Review comment:
Dumping all buffers on the cache is the "short" dump?!?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] b-slim commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
b-slim commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r396643767
##########
File path: llap-server/src/java/org/apache/hadoop/hive/llap/io/api/impl/LlapIoImpl.java
##########
@@ -91,143 +74,148 @@
public static final Logger CACHE_LOGGER = LoggerFactory.getLogger("LlapIoCache");
public static final Logger LOCKING_LOGGER = LoggerFactory.getLogger("LlapIoLocking");
private static final String MODE_CACHE = "cache";
+ private static final String DISPLAY_NAME = "LlapDaemonCacheMetrics-" + MetricsUtils.getHostName();
+ private static final String IO_DISPLAY_NAME = "LlapDaemonIOMetrics-" + MetricsUtils.getHostName();
// TODO: later, we may have a map
private final ColumnVectorProducer orcCvp, genericCvp;
private final ExecutorService executor;
private final LlapDaemonCacheMetrics cacheMetrics;
private final LlapDaemonIOMetrics ioMetrics;
- private ObjectName buddyAllocatorMXBean;
+ private final ObjectName buddyAllocatorMXBean;
private final Allocator allocator;
private final FileMetadataCache fileMetadataCache;
private final LowLevelCache dataCache;
private final BufferUsageManager bufferManager;
private final Configuration daemonConf;
private final LowLevelCacheMemoryManager memoryManager;
-
- private List<LlapIoDebugDump> debugDumpComponents = new ArrayList<>();
-
- private LlapIoImpl(Configuration conf) throws IOException {
- this.daemonConf = conf;
- String ioMode = HiveConf.getVar(conf, HiveConf.ConfVars.LLAP_IO_MEMORY_MODE);
- boolean useLowLevelCache = LlapIoImpl.MODE_CACHE.equalsIgnoreCase(ioMode);
- LOG.info("Initializing LLAP IO in {} mode", useLowLevelCache ? LlapIoImpl.MODE_CACHE : "none");
- String displayName = "LlapDaemonCacheMetrics-" + MetricsUtils.getHostName();
- String sessionId = conf.get("llap.daemon.metrics.sessionid");
- this.cacheMetrics = LlapDaemonCacheMetrics.create(displayName, sessionId);
-
- displayName = "LlapDaemonIOMetrics-" + MetricsUtils.getHostName();
- String[] strIntervals = HiveConf.getTrimmedStringsVar(conf,
- HiveConf.ConfVars.LLAP_IO_DECODING_METRICS_PERCENTILE_INTERVALS);
- List<Integer> intervalList = new ArrayList<>();
- if (strIntervals != null) {
- for (String strInterval : strIntervals) {
- try {
- intervalList.add(Integer.valueOf(strInterval));
- } catch (NumberFormatException e) {
- LOG.warn("Ignoring IO decoding metrics interval {} from {} as it is invalid", strInterval,
- Arrays.toString(strIntervals));
- }
- }
+ private final List<LlapIoDebugDump> debugDumpComponents = new ArrayList<>();
+
+ /**
+ * Llap IO is created via Reflection by {@link org.apache.hadoop.hive.llap.io.api.LlapProxy}.
+ *
+ * @param conf Configuration containing all the needed parameters and flags to initialize LLAP IO.
+ */
+ private LlapIoImpl(Configuration conf) {
+ this.daemonConf = Preconditions.checkNotNull(conf);
+ final boolean
+ useLowLevelCache =
+ LlapIoImpl.MODE_CACHE.equalsIgnoreCase(HiveConf.getVar(conf, HiveConf.ConfVars.LLAP_IO_MEMORY_MODE));
+ final boolean isEncodeEnabled = useLowLevelCache && HiveConf.getBoolVar(conf, ConfVars.LLAP_IO_ENCODE_ENABLED);
+ LOG.info("Initializing LLAP IO in {} mode, with Encoding = {} ",
+ useLowLevelCache ? LlapIoImpl.MODE_CACHE : "none",
+ isEncodeEnabled);
+
+ //setup metrics reporters
+ final String sessionId = conf.get("llap.daemon.metrics.sessionid");
+ final String[]
+ strIntervals =
+ HiveConf.getTrimmedStringsVar(conf, HiveConf.ConfVars.LLAP_IO_DECODING_METRICS_PERCENTILE_INTERVALS);
+ int[] intArray = stringsToIntegers(strIntervals);
+ if (strIntervals != null && strIntervals.length != intArray.length) {
+ LOG.warn("Ignoring IO decoding metrics interval from {} as it is invalid due to Number format exception",
+ Arrays.toString(strIntervals));
}
- this.ioMetrics = LlapDaemonIOMetrics.create(displayName, sessionId, Ints.toArray(intervalList));
+ this.ioMetrics = LlapDaemonIOMetrics.create(IO_DISPLAY_NAME, sessionId, intArray);
+ this.cacheMetrics = LlapDaemonCacheMetrics.create(DISPLAY_NAME, sessionId);
+ LOG.info("Started llap daemon metrics with displayName: {} sessionId: {}", IO_DISPLAY_NAME, sessionId);
- LOG.info("Started llap daemon metrics with displayName: {} sessionId: {}", displayName,
- sessionId);
+ int numThreads = HiveConf.getIntVar(conf, HiveConf.ConfVars.LLAP_IO_THREADPOOL_SIZE);
+ this.executor =
+ new StatsRecordingThreadPool(numThreads,
+ numThreads,
+ 0L,
+ TimeUnit.MILLISECONDS,
+ new LinkedBlockingQueue<>(),
+ new ThreadFactoryBuilder().setNameFormat("IO-Elevator-Thread-%d").setDaemon(true).build());
+ LOG.info("Created IO Elevator Thread pool with {} Threads ", numThreads);
+ // IO thread pool. Listening is used for unhandled errors for now (TODO: remove?)
+ FixedSizedObjectPool<IoTrace> tracePool = IoTrace.createTracePool(conf, numThreads);
- MetadataCache metadataCache = null;
- SerDeLowLevelCacheImpl serdeCache = null; // TODO: extract interface when needed
- BufferUsageManager bufferManagerOrc = null, bufferManagerGeneric = null;
- boolean isEncodeEnabled = useLowLevelCache
- && HiveConf.getBoolVar(conf, ConfVars.LLAP_IO_ENCODE_ENABLED);
+ final MetadataCache metadataCache;
+ final BufferUsageManager bufferManagerOrc, bufferManagerGeneric;
+ final SerDeLowLevelCacheImpl serdeCache; // TODO: extract interface when needed
if (useLowLevelCache) {
// Memory manager uses cache policy to trigger evictions, so create the policy first.
- boolean useLrfu = HiveConf.getBoolVar(conf, HiveConf.ConfVars.LLAP_USE_LRFU);
- long totalMemorySize = HiveConf.getSizeVar(conf, ConfVars.LLAP_IO_MEMORY_MAX_SIZE);
- int minAllocSize = (int) HiveConf.getSizeVar(conf, ConfVars.LLAP_ALLOCATOR_MIN_ALLOC);
- LowLevelCachePolicy
- realCachePolicy =
- useLrfu ? new LowLevelLrfuCachePolicy(minAllocSize, totalMemorySize, conf) : new LowLevelFifoCachePolicy();
- boolean trackUsage = HiveConf.getBoolVar(conf, HiveConf.ConfVars.LLAP_TRACK_CACHE_USAGE);
- LowLevelCachePolicy cachePolicyWrapper;
- if (trackUsage) {
- cachePolicyWrapper = new CacheContentsTracker(realCachePolicy);
- } else {
- cachePolicyWrapper = realCachePolicy;
- }
+ final long totalMemorySize = HiveConf.getSizeVar(conf, ConfVars.LLAP_IO_MEMORY_MAX_SIZE);
+
+ final LowLevelCachePolicy cachePolicyWrapper = LowLevelCachePolicy.provideFromConf(conf);
+
// Allocator uses memory manager to request memory, so create the manager next.
- this.memoryManager = new LowLevelCacheMemoryManager(
- totalMemorySize, cachePolicyWrapper, cacheMetrics);
- cacheMetrics.setCacheCapacityTotal(totalMemorySize);
+ this.memoryManager = new LowLevelCacheMemoryManager(totalMemorySize, cachePolicyWrapper, cacheMetrics);
+ this.cacheMetrics.setCacheCapacityTotal(totalMemorySize);
// Cache uses allocator to allocate and deallocate, create allocator and then caches.
BuddyAllocator allocator = new BuddyAllocator(conf, memoryManager, cacheMetrics);
this.allocator = allocator;
- LowLevelCacheImpl cacheImpl = new LowLevelCacheImpl(
- cacheMetrics, cachePolicyWrapper, allocator, true);
- dataCache = cacheImpl;
+ LowLevelCacheImpl cacheImpl = new LowLevelCacheImpl(cacheMetrics, cachePolicyWrapper, allocator, true);
+ this.dataCache = cacheImpl;
if (isEncodeEnabled) {
- SerDeLowLevelCacheImpl serdeCacheImpl = new SerDeLowLevelCacheImpl(
- cacheMetrics, cachePolicyWrapper, allocator);
- serdeCache = serdeCacheImpl;
- serdeCacheImpl.setConf(conf);
+ serdeCache = new SerDeLowLevelCacheImpl(cacheMetrics, cachePolicyWrapper, allocator);
+ serdeCache.setConf(conf);
+ } else {
+ serdeCache = null;
}
-
- boolean useGapCache = HiveConf.getBoolVar(conf, ConfVars.LLAP_CACHE_ENABLE_ORC_GAP_CACHE);
- metadataCache = new MetadataCache(
- allocator, memoryManager, cachePolicyWrapper, useGapCache, cacheMetrics);
- fileMetadataCache = metadataCache;
+ final boolean useGapCache = HiveConf.getBoolVar(conf, ConfVars.LLAP_CACHE_ENABLE_ORC_GAP_CACHE);
+ metadataCache = new MetadataCache(allocator, memoryManager, cachePolicyWrapper, useGapCache, cacheMetrics);
+ this.fileMetadataCache = metadataCache;
// And finally cache policy uses cache to notify it of eviction. The cycle is complete!
- EvictionDispatcher e = new EvictionDispatcher(
- dataCache, serdeCache, metadataCache, allocator);
+ final EvictionDispatcher e = new EvictionDispatcher(dataCache, serdeCache, metadataCache, allocator);
cachePolicyWrapper.setEvictionListener(e);
-
cacheImpl.startThreads(); // Start the cache threads.
bufferManager = bufferManagerOrc = cacheImpl; // Cache also serves as buffer manager.
bufferManagerGeneric = serdeCache;
- if (trackUsage) {
- debugDumpComponents.add(cachePolicyWrapper); // Cache contents tracker.
- }
- debugDumpComponents.add(realCachePolicy);
+ debugDumpComponents.add(cachePolicyWrapper); // Cache contents tracker.
debugDumpComponents.add(cacheImpl);
if (serdeCache != null) {
debugDumpComponents.add(serdeCache);
}
- if (metadataCache != null) {
- debugDumpComponents.add(metadataCache);
- }
+ debugDumpComponents.add(metadataCache);
debugDumpComponents.add(allocator);
} else {
this.allocator = new SimpleAllocator(conf);
- fileMetadataCache = null;
- SimpleBufferManager sbm = new SimpleBufferManager(allocator, cacheMetrics);
- bufferManager = bufferManagerOrc = bufferManagerGeneric = sbm;
- dataCache = sbm;
+ final SimpleBufferManager sbm = new SimpleBufferManager(allocator, cacheMetrics);
+ this.bufferManager = bufferManagerOrc = bufferManagerGeneric = sbm;
+ this.dataCache = sbm;
+ this.debugDumpComponents.add(sb -> sb.append("LLAP IO allocator is not in use!"));
+ this.fileMetadataCache = null;
this.memoryManager = null;
- debugDumpComponents.add(new LlapIoDebugDump() {
- @Override
- public void debugDumpShort(StringBuilder sb) {
- sb.append("LLAP IO allocator is not in use!");
- }
- });
+ serdeCache = null;
+ metadataCache = null;
}
- // IO thread pool. Listening is used for unhandled errors for now (TODO: remove?)
- int numThreads = HiveConf.getIntVar(conf, HiveConf.ConfVars.LLAP_IO_THREADPOOL_SIZE);
- executor = new StatsRecordingThreadPool(numThreads, numThreads, 0L, TimeUnit.MILLISECONDS,
- new LinkedBlockingQueue<Runnable>(),
- new ThreadFactoryBuilder().setNameFormat("IO-Elevator-Thread-%d").setDaemon(true).build());
- FixedSizedObjectPool<IoTrace> tracePool = IoTrace.createTracePool(conf);
- // TODO: this should depends on input format and be in a map, or something.
- this.orcCvp = new OrcColumnVectorProducer(
- metadataCache, dataCache, bufferManagerOrc, conf, cacheMetrics, ioMetrics, tracePool);
- this.genericCvp = isEncodeEnabled ? new GenericColumnVectorProducer(
- serdeCache, bufferManagerGeneric, conf, cacheMetrics, ioMetrics, tracePool) : null;
- LOG.info("LLAP IO initialized");
- registerMXBeans();
+ // TODO: this should depends on input format and be in a map, or something.
+ this.orcCvp =
+ new OrcColumnVectorProducer(metadataCache,
+ dataCache,
+ bufferManagerOrc,
+ conf,
+ cacheMetrics,
+ ioMetrics,
+ tracePool);
+ this.genericCvp =
+ isEncodeEnabled ?
+ new GenericColumnVectorProducer(serdeCache,
+ bufferManagerGeneric,
+ conf,
+ cacheMetrics,
+ ioMetrics,
+ tracePool) :
+ null;
+ this.buddyAllocatorMXBean = MBeans.register("LlapDaemon", "BuddyAllocatorInfo", allocator);
+ LOG.info("LLAP IO successful initialized.");
}
- private void registerMXBeans() {
- buddyAllocatorMXBean = MBeans.register("LlapDaemon", "BuddyAllocatorInfo", allocator);
+ private static int[] stringsToIntegers(String[] strings) {
+ if (strings == null) {
+ return new int[0];
+ }
+ return Arrays.stream(strings).map(x -> {
Review comment:
i removed the wrapping
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] b-slim commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
b-slim commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r396569278
##########
File path: llap-server/src/java/org/apache/hadoop/hive/llap/cache/LlapCacheableBuffer.java
##########
@@ -26,39 +26,71 @@
* using a real programming language.
*/
public abstract class LlapCacheableBuffer {
- protected static final int IN_LIST = -2, NOT_IN_CACHE = -1;
-
- /** Priority for cache policy (should be pretty universal). */
- public double priority;
- /** Last priority update time for cache policy (should be pretty universal). */
- public long lastUpdate = -1;
+ public static final int INVALIDATE_OK = 0, INVALIDATE_FAILED = 1, INVALIDATE_ALREADY_INVALID = 2;
Review comment:
this was there before and not sure what is the main reason i agree this should be enum.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] prasanthj commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
prasanthj commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r400416439
##########
File path: llap-server/src/java/org/apache/hadoop/hive/llap/cache/ClockCachePolicy.java
##########
@@ -0,0 +1,264 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.hadoop.hive.llap.cache;
+
+import com.google.common.annotations.VisibleForTesting;
+import com.google.common.base.Preconditions;
+
+import javax.annotation.concurrent.GuardedBy;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+import java.util.concurrent.locks.Lock;
+import java.util.concurrent.locks.ReentrantLock;
+
+/**
+ * Clock eviction policy. Uses a simple circular list to keep a ring of current used buffers.
+ * New entries are added to tail of the clock hand AKA (clockHand.prev)
+ * Eviction start at the current clock hand following the next pointer.
+ *
+ */
+public class ClockCachePolicy implements LowLevelCachePolicy {
Review comment:
+1. I was expecting this to be ring buffer based lock free implementation as well. This can be done in a follow up too.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] prasanthj commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
prasanthj commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r400420689
##########
File path: llap-server/src/java/org/apache/hadoop/hive/llap/cache/ClockCachePolicy.java
##########
@@ -0,0 +1,264 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.hadoop.hive.llap.cache;
+
+import com.google.common.annotations.VisibleForTesting;
+import com.google.common.base.Preconditions;
+
+import javax.annotation.concurrent.GuardedBy;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+import java.util.concurrent.locks.Lock;
+import java.util.concurrent.locks.ReentrantLock;
+
+/**
+ * Clock eviction policy. Uses a simple circular list to keep a ring of current used buffers.
+ * New entries are added to tail of the clock hand AKA (clockHand.prev)
+ * Eviction start at the current clock hand following the next pointer.
+ *
+ */
+public class ClockCachePolicy implements LowLevelCachePolicy {
+
+ private static final int DEFAULT_MAX_CIRCLES = 5;
+
+ /**
+ * Lock to protect the state of the policy, used as mutex when modifying the circular linked list.
+ */
+ private final Lock listLock = new ReentrantLock();
+
+ /**
+ * The clock hand shared between threads thus made volatile, to ensure state when read outside of lock.
+ */
+ @GuardedBy("listLock")
+ private volatile LlapCacheableBuffer clockHand;
+
+ private EvictionListener evictionListener;
+ /**
+ * Max number of clock rotation before giving up on clock operation like eviction.
+ */
+ private final int maxCircles;
+
+ public ClockCachePolicy() {
+ maxCircles = DEFAULT_MAX_CIRCLES;
+ }
+
+ public ClockCachePolicy(int maxCircles) {
+ Preconditions.checkState(maxCircles > 0, "Maximum number of clock rotation must be positive and got " + maxCircles);
+ this.maxCircles = maxCircles;
+ }
+
+ /**
+ * Signals to the policy the addition of a new entry to the cache. An entry come with a priority that can be used as
+ * a hint to replacement policy.
+ *
+ * @param buffer buffer to be cached
+ * @param priority the priority of cached element
+ */
+ @Override public void cache(LlapCacheableBuffer buffer, LowLevelCache.Priority priority) {
+ listLock.lock();
+ try {
+ clockHand = appendToCircularList(clockHand, buffer);
+ } finally {
+ listLock.unlock();
+ }
+ }
+
+ /**
+ * Appends new entry to the tail of circular list.
+ *
+ * @param head circular list head.
+ * @param buffer new entry to be added.
+ * @return the ring head.
+ */
+ private static LlapCacheableBuffer appendToCircularList(LlapCacheableBuffer head, LlapCacheableBuffer buffer) {
+ if (head == null) {
+ return linkToItSelf(buffer);
+ }
+ buffer.next = head;
+ buffer.prev = head.prev;
+ head.prev.next = buffer;
+ head.prev = buffer;
+ return head;
+ }
+
+ /**
+ * Links the entry to it self to form a ring.
+ *
+ * @param buffer input
+ * @return buffer
+ */
+ private static LlapCacheableBuffer linkToItSelf(LlapCacheableBuffer buffer) {
+ buffer.prev = buffer;
+ buffer.next = buffer;
+ return buffer;
+ }
+
+ @Override public void notifyLock(LlapCacheableBuffer buffer) {
+ buffer.setClockBit();
+ }
+
+ /**
+ * Notifies the policy that a buffer is unlocked after been used. This notification signals to the policy that an
+ * access to this page occurred.
+ *
+ * @param buffer buffer that just got unlocked after a read.
+ */
+ @Override public void notifyUnlock(LlapCacheableBuffer buffer) {
+
+ }
+
+ /**
+ * Signals to the policy that it has to evict some entries from the cache.
+ * Policy has to at least evict the amount memory requested.
+ * Not that is method will block until at least {@code memoryToReserve} bytes are evicted.
+ *
+ * @param memoryToReserve amount of bytes to be evicted
+ * @return actual amount of evicted bytes.
+ */
+ @Override public long evictSomeBlocks(long memoryToReserve) {
+ long evicted = 0;
+ if (clockHand == null) {
+ return evicted;
+ }
+ int fullClockRotation = 0;
+ listLock.lock();
+ try {
+ // ring tail is used to mark a clock circle
+ LlapCacheableBuffer ringTail = clockHand.prev;
+ // ring head is the current clock position that is under lock. Using local var under lock and updating actual
+ // clock position as soon we are done with looping
+ LlapCacheableBuffer currentClockHead = clockHand;
+
+ while (evicted < memoryToReserve && currentClockHead != null && fullClockRotation < maxCircles) {
+ if (ringTail == currentClockHead) {
+ fullClockRotation++;
+ }
+ if (currentClockHead.isClockBitSet()) {
+ // case the buffer getting second chance.
+ currentClockHead.unSetClockBit();
+ currentClockHead = currentClockHead.next;
+ } else {
+ // try to evict this victim
+ int invalidateFlag = currentClockHead.invalidate();
+ if (invalidateFlag == LlapCacheableBuffer.INVALIDATE_OK
+ || invalidateFlag == LlapCacheableBuffer.INVALIDATE_ALREADY_INVALID) {
+ if (invalidateFlag == LlapCacheableBuffer.INVALIDATE_OK) {
+ // case we are able to evict the buffer notify and account for it.
+ evictionListener.notifyEvicted(currentClockHead);
+ evicted += currentClockHead.getMemoryUsage();
+ }
+ LlapCacheableBuffer newHand = currentClockHead.next;
+ if (newHand == currentClockHead) {
+ // end of the ring we have looped, nothing else can be done...
+ currentClockHead = null;
+ break;
+ } else {
+ //remove it from the ring.
+ if (currentClockHead == ringTail) {
+ // we are about to remove the current ring tail thus we need to compute new tail
+ ringTail = ringTail.prev;
+ }
+ currentClockHead.prev.next = newHand;
+ newHand.prev = currentClockHead.prev;
+ currentClockHead = newHand;
+ }
+ } else if (invalidateFlag == LlapCacheableBuffer.INVALIDATE_FAILED) {
+ // can not be evicted case locked
+ currentClockHead = currentClockHead.next;
+ } else {
+ throw new IllegalStateException("Unknown invalidation flag " + invalidateFlag);
+ }
+ }
+ }
+ // done with clock rotations, update the current clock hand under lock.
+ clockHand = currentClockHead;
+ return evicted;
+ } finally {
+ listLock.unlock();
+ }
+ }
+
+ @Override public void setEvictionListener(EvictionListener listener) {
+ evictionListener = listener;
+ }
+
+ @Override public long purge() {
+ return evictSomeBlocks(Long.MAX_VALUE);
+ }
+
+ @Override public void debugDumpShort(StringBuilder sb) {
+ if (clockHand == null) {
+ sb.append("Clock is empty");
+ return;
+ }
+ listLock.lock();
+ try {
+ sb.append("Clock Status\n");
+ LlapCacheableBuffer currentClockHand = clockHand;
+ LlapCacheableBuffer lastElement = clockHand.prev;
+ while (currentClockHand != lastElement) {
+ sb.append(currentClockHand.toStringForCache());
+ currentClockHand = currentClockHand.next;
+ }
+ sb.append(lastElement.toStringForCache());
+ } finally {
+ listLock.unlock();
+ }
+ }
+
+ @VisibleForTesting protected Iterator<LlapCacheableBuffer> getIterator() {
Review comment:
If this is required only for testing. Should there be protected access? Or can it be package private?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] odraese commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
odraese commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r395926574
##########
File path: llap-server/src/java/org/apache/hadoop/hive/llap/cache/LrfuCacheAttribute.java
##########
@@ -0,0 +1,68 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.hadoop.hive.llap.cache;
+
+public final class LrfuCacheAttribute implements LlapCacheableBuffer.CacheAttribute {
Review comment:
Some JavaDoc for this new class would be great.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] b-slim commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
b-slim commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r396623049
##########
File path: llap-server/src/java/org/apache/hadoop/hive/llap/cache/LowLevelLrfuCachePolicy.java
##########
@@ -138,7 +137,7 @@ public void notifyLock(LlapCacheableBuffer buffer) {
// a locked item in either, it will remove it from cache; when we unlock, we are going to
// put it back or update it, depending on whether this has happened. This should cause
// most of the expensive cache update work to happen in unlock, not blocking processing.
- if (buffer.indexInHeap != LlapCacheableBuffer.IN_LIST || !listLock.tryLock()) {
+ if (buffer.cacheAttribute == null || buffer.cacheAttribute.getIndex() != IN_LIST || !listLock.tryLock()) {
Review comment:
i do not see any. good point will remove it.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] odraese commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
odraese commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r395851359
##########
File path: common/src/java/org/apache/hadoop/hive/conf/HiveConf.java
##########
@@ -4187,6 +4188,8 @@ private static void populateLlapDaemonVarsSet(Set<String> llapDaemonVarsSetLocal
"partitions and tables) for reporting."),
LLAP_USE_LRFU("hive.llap.io.use.lrfu", true,
Review comment:
so you want to flag this as deprecated?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] odraese commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
odraese commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r395924266
##########
File path: llap-server/src/java/org/apache/hadoop/hive/llap/cache/LlapCacheableBuffer.java
##########
@@ -26,39 +26,71 @@
* using a real programming language.
*/
public abstract class LlapCacheableBuffer {
- protected static final int IN_LIST = -2, NOT_IN_CACHE = -1;
-
- /** Priority for cache policy (should be pretty universal). */
- public double priority;
- /** Last priority update time for cache policy (should be pretty universal). */
- public long lastUpdate = -1;
+ public static final int INVALIDATE_OK = 0, INVALIDATE_FAILED = 1, INVALIDATE_ALREADY_INVALID = 2;
- // TODO: remove some of these fields as needed?
+ public CacheAttribute cacheAttribute;
/** Linked list pointers for LRFU/LRU cache policies. Given that each block is in cache
* that might be better than external linked list. Or not, since this is not concurrent. */
public LlapCacheableBuffer prev = null;
/** Linked list pointers for LRFU/LRU cache policies. Given that each block is in cache
* that might be better than external linked list. Or not, since this is not concurrent. */
public LlapCacheableBuffer next = null;
- /** Index in heap for LRFU/LFU cache policies. */
- public int indexInHeap = NOT_IN_CACHE;
- public static final int INVALIDATE_OK = 0, INVALIDATE_FAILED = 1, INVALIDATE_ALREADY_INVALID = 2;
+ /**
+ * @return result of invalidation.
+ */
protected abstract int invalidate();
+
+ /**
+ * @return size of the buffer in bytes.
+ */
public abstract long getMemoryUsage();
+
+ /**
+ * @param evictionDispatcher dispatcher object to be notified.
+ */
public abstract void notifyEvicted(EvictionDispatcher evictionDispatcher);
+ /**
+ * Set the clock bit to true, should be thread safe
+ */
+ public abstract void setClockBit();
+
+ /**
+ * Set the clock bit to false, should be thread safe.
+ */
+ public abstract void unSetClockBit();
+
+ /**
+ * @return value of the clock bit.
+ */
+ public abstract boolean isClockBitSet();
+
@Override
public String toString() {
return "0x" + Integer.toHexString(System.identityHashCode(this));
}
public String toStringForCache() {
- return "[" + Integer.toHexString(hashCode()) + " " + String.format("%1$.2f", priority) + " "
- + lastUpdate + " " + (isLocked() ? "!" : ".") + "]";
+ return "[" + Integer.toHexString(hashCode()) + " Cache Attributes " + cacheAttribute == null ? "NONE" : cacheAttribute.toString() + " " + (isLocked() ? "!" : ".") + "]";
}
+ /**
+ * @return human readable tag used by the cache content tracker.
+ */
public abstract CacheTag getTag();
+ /**
+ * @return true if the buffer is locked as part of query execution.
+ */
protected abstract boolean isLocked();
+
+ public interface CacheAttribute {
Review comment:
Could we move this into an own file w/ doc?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] odraese commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
odraese commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r400362498
##########
File path: llap-server/src/java/org/apache/hadoop/hive/llap/cache/LowLevelLrfuCachePolicy.java
##########
@@ -491,29 +499,32 @@ private int moveMinChildUp(int targetPos, long time, double comparePri) {
}
if (leftPri <= rightPri) { // prefer left, cause right might be missing
heap[targetPos] = left;
- left.indexInHeap = targetPos;
+ LrfuCacheAttribute leftCacheAttribute = (LrfuCacheAttribute) left.cacheAttribute;
+ leftCacheAttribute.indexInHeap = targetPos;
Review comment:
would hope that the compiler is optimized to inline the setter code. Using setter makes it better encapsulated.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] b-slim commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
b-slim commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r396571775
##########
File path: llap-server/src/java/org/apache/hadoop/hive/llap/cache/LlapCacheableBuffer.java
##########
@@ -26,39 +26,71 @@
* using a real programming language.
*/
public abstract class LlapCacheableBuffer {
- protected static final int IN_LIST = -2, NOT_IN_CACHE = -1;
-
- /** Priority for cache policy (should be pretty universal). */
- public double priority;
- /** Last priority update time for cache policy (should be pretty universal). */
- public long lastUpdate = -1;
+ public static final int INVALIDATE_OK = 0, INVALIDATE_FAILED = 1, INVALIDATE_ALREADY_INVALID = 2;
- // TODO: remove some of these fields as needed?
+ public CacheAttribute cacheAttribute;
/** Linked list pointers for LRFU/LRU cache policies. Given that each block is in cache
* that might be better than external linked list. Or not, since this is not concurrent. */
public LlapCacheableBuffer prev = null;
/** Linked list pointers for LRFU/LRU cache policies. Given that each block is in cache
* that might be better than external linked list. Or not, since this is not concurrent. */
public LlapCacheableBuffer next = null;
- /** Index in heap for LRFU/LFU cache policies. */
- public int indexInHeap = NOT_IN_CACHE;
- public static final int INVALIDATE_OK = 0, INVALIDATE_FAILED = 1, INVALIDATE_ALREADY_INVALID = 2;
+ /**
+ * @return result of invalidation.
+ */
protected abstract int invalidate();
+
+ /**
+ * @return size of the buffer in bytes.
+ */
public abstract long getMemoryUsage();
+
+ /**
+ * @param evictionDispatcher dispatcher object to be notified.
+ */
public abstract void notifyEvicted(EvictionDispatcher evictionDispatcher);
+ /**
Review comment:
I agree, with you the only thing that is bothering me is if we delegate to actual policy we will need to delegate the buffer state as well which can make the code quite hard to reason about. What am trying to say i do not like that part of the state will be controlled by policy (in this case the bit) and the other part is by the actual buffer internal state biz. Let me know what you think.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] prasanthj commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
prasanthj commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r400418056
##########
File path: llap-server/src/java/org/apache/hadoop/hive/llap/cache/ClockCachePolicy.java
##########
@@ -0,0 +1,313 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.hadoop.hive.llap.cache;
+
+import com.google.common.annotations.VisibleForTesting;
+import com.google.common.base.Preconditions;
+import org.apache.hadoop.hive.llap.io.metadata.MetadataCache;
+
+import javax.annotation.concurrent.GuardedBy;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+import java.util.concurrent.locks.Lock;
+import java.util.concurrent.locks.ReentrantLock;
+
+/**
+ * Clock eviction policy. Uses a simple circular list to keep a ring of current used buffers.
+ * New entries are added to tail of the clock hand AKA (clockHand.prev)
+ * Eviction start at the current clock hand following the next pointer.
+ *
+ */
+public class ClockCachePolicy implements LowLevelCachePolicy {
+
+ private static final int DEFAULT_MAX_CIRCLES = 5;
+
+ /**
+ * Lock to protect the state of the policy, used as mutex when modifying the circular linked list.
+ */
+ private final Lock listLock = new ReentrantLock();
+
+ /**
+ * The clock hand shared between threads thus made volatile, to ensure state when read outside of lock.
+ */
+ @GuardedBy("listLock")
+ private volatile LlapCacheableBuffer clockHand;
+
+ private EvictionListener evictionListener;
+ /**
+ * Max number of clock rotation before giving up on clock operation like eviction.
+ */
+ private final int maxCircles;
+
+ public ClockCachePolicy() {
+ maxCircles = DEFAULT_MAX_CIRCLES;
+ }
+
+ public ClockCachePolicy(int maxCircles) {
+ Preconditions.checkState(maxCircles > 0, "Maximum number of clock rotation must be positive and got " + maxCircles);
+ this.maxCircles = maxCircles;
+ }
+
+ /**
+ * Signals to the policy the addition of a new entry to the cache. An entry come with a priority that can be used as
+ * a hint to replacement policy.
+ *
+ * @param buffer buffer to be cached
+ * @param priority the priority of cached element
+ */
+ @Override public void cache(LlapCacheableBuffer buffer, LowLevelCache.Priority priority) {
+ listLock.lock();
+ try {
+ //noinspection NonAtomicOperationOnVolatileField
+ clockHand = appendToCircularList(clockHand, buffer);
+ } finally {
+ listLock.unlock();
+ }
+ }
+
+ /**
+ * Appends new entry to the tail of circular list.
+ *
+ * @param head circular list head.
+ * @param buffer new entry to be added.
+ * @return the ring head.
+ */
+ private static LlapCacheableBuffer appendToCircularList(LlapCacheableBuffer head, LlapCacheableBuffer buffer) {
+ if (head == null) {
+ return linkToItSelf(buffer);
+ }
+ buffer.next = head;
+ buffer.prev = head.prev;
+ head.prev.next = buffer;
+ head.prev = buffer;
+ return head;
+ }
+
+ /**
+ * Links the entry to it self to form a ring.
+ *
+ * @param buffer input
+ * @return buffer
+ */
+ private static LlapCacheableBuffer linkToItSelf(LlapCacheableBuffer buffer) {
+ buffer.prev = buffer;
+ buffer.next = buffer;
+ return buffer;
+ }
+
+ @Override public void notifyLock(LlapCacheableBuffer buffer) {
+ buffer.setClockBit();
+ }
+
+ /**
+ * Notifies the policy that a buffer is unlocked after been used. This notification signals to the policy that an
+ * access to this page occurred.
+ *
+ * @param buffer buffer that just got unlocked after a read.
+ */
+ @Override public void notifyUnlock(LlapCacheableBuffer buffer) {
+
+ }
+
+ /**
+ * Signals to the policy that it has to evict some entries from the cache.
+ * Policy has to at least evict the amount memory requested.
+ * Not that is method will block until at least {@code memoryToReserve} bytes are evicted.
Review comment:
Will be good to log how long it took to allocate the requested memory for debugging.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] prasanthj commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
prasanthj commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r400423150
##########
File path: llap-server/src/java/org/apache/hadoop/hive/llap/cache/LlapAllocatorBuffer.java
##########
@@ -337,25 +364,34 @@ public Boolean endDiscard() {
return result;
}
- private static final class State {
- public static final int
- FLAG_MOVING = 0b00001, // Locked by someone to move or force-evict.
- FLAG_EVICTED = 0b00010, // Evicted. This is cache-specific.
- FLAG_REMOVED = 0b00100, // Removed from allocator structures. The final state.
- FLAG_MEM_RELEASED = 0b01000, // The memory was released to memory manager.
- FLAG_NEW_ALLOC = 0b10000; // New allocation before the first use; cannot force-evict.
- private static final int FLAGS_WIDTH = 5,
- REFCOUNT_WIDTH = 19, ARENA_WIDTH = 16, HEADER_WIDTH = 24;
-
- public static final long MAX_REFCOUNT = (1 << REFCOUNT_WIDTH) - 1;
-
- private static final int REFCOUNT_SHIFT = FLAGS_WIDTH,
- ARENA_SHIFT = REFCOUNT_SHIFT + REFCOUNT_WIDTH, HEADER_SHIFT = ARENA_SHIFT + ARENA_WIDTH;
-
- private static final long FLAGS_MASK = (1L << FLAGS_WIDTH) - 1,
- REFCOUNT_MASK = ((1L << REFCOUNT_WIDTH) - 1) << REFCOUNT_SHIFT,
- ARENA_MASK = ((1L << ARENA_WIDTH) - 1) << ARENA_SHIFT,
- HEADER_MASK = ((1L << HEADER_WIDTH) - 1) << HEADER_SHIFT;
+ /**
+ * Utility class to manipulate the buffer state.
+ */
+ static final class State {
+ static final int FLAG_MOVING = 0b00001; // Locked by someone to move or force-evict.
+ static final int FLAG_EVICTED = 0b00010; // Evicted. This is cache-specific.
+ static final int FLAG_REMOVED = 0b00100; // Removed from allocator structures. The final state.
+ static final int FLAG_MEM_RELEASED = 0b01000; // The memory was released to memory manager.
+ static final int FLAG_NEW_ALLOC = 0b10000; // New allocation before the first use; cannot force-evict.
+
+ static final int FLAGS_WIDTH = 5;
Review comment:
can you add a comment of how these width's are laid out?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] odraese commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
odraese commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r395921046
##########
File path: llap-server/src/java/org/apache/hadoop/hive/llap/cache/LlapAllocatorBuffer.java
##########
@@ -80,9 +80,32 @@ int tryIncRef() {
return incRefInternal(false);
}
+ /**
Review comment:
More of a general comment: Ths LlapAllocatorBuffer is getting more and more "helper data" and methods, which are specific to one eviction policy. The buffer should just be a buffer and if the eviction policy needs additional information, it should wrap the buffer by itself. We might want to clean this up.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] odraese commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
odraese commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r395919468
##########
File path: llap-server/src/java/org/apache/hadoop/hive/llap/cache/ClockCachePolicy.java
##########
@@ -0,0 +1,264 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.hadoop.hive.llap.cache;
+
+import com.google.common.annotations.VisibleForTesting;
+import com.google.common.base.Preconditions;
+
+import javax.annotation.concurrent.GuardedBy;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+import java.util.concurrent.locks.Lock;
+import java.util.concurrent.locks.ReentrantLock;
+
+/**
+ * Clock eviction policy. Uses a simple circular list to keep a ring of current used buffers.
+ * New entries are added to tail of the clock hand AKA (clockHand.prev)
+ * Eviction start at the current clock hand following the next pointer.
+ *
+ */
+public class ClockCachePolicy implements LowLevelCachePolicy {
+
+ private static final int DEFAULT_MAX_CIRCLES = 5;
+
+ /**
+ * Lock to protect the state of the policy, used as mutex when modifying the circular linked list.
+ */
+ private final Lock listLock = new ReentrantLock();
+
+ /**
+ * The clock hand shared between threads thus made volatile, to ensure state when read outside of lock.
+ */
+ @GuardedBy("listLock")
+ private volatile LlapCacheableBuffer clockHand;
+
+ private EvictionListener evictionListener;
+ /**
+ * Max number of clock rotation before giving up on clock operation like eviction.
+ */
+ private final int maxCircles;
+
+ public ClockCachePolicy() {
+ maxCircles = DEFAULT_MAX_CIRCLES;
+ }
+
+ public ClockCachePolicy(int maxCircles) {
+ Preconditions.checkState(maxCircles > 0, "Maximum number of clock rotation must be positive and got " + maxCircles);
+ this.maxCircles = maxCircles;
+ }
+
+ /**
+ * Signals to the policy the addition of a new entry to the cache. An entry come with a priority that can be used as
+ * a hint to replacement policy.
+ *
+ * @param buffer buffer to be cached
+ * @param priority the priority of cached element
+ */
+ @Override public void cache(LlapCacheableBuffer buffer, LowLevelCache.Priority priority) {
+ listLock.lock();
+ try {
+ clockHand = appendToCircularList(clockHand, buffer);
+ } finally {
+ listLock.unlock();
+ }
+ }
+
+ /**
+ * Appends new entry to the tail of circular list.
+ *
+ * @param head circular list head.
+ * @param buffer new entry to be added.
+ * @return the ring head.
+ */
+ private static LlapCacheableBuffer appendToCircularList(LlapCacheableBuffer head, LlapCacheableBuffer buffer) {
+ if (head == null) {
+ return linkToItSelf(buffer);
+ }
+ buffer.next = head;
+ buffer.prev = head.prev;
+ head.prev.next = buffer;
+ head.prev = buffer;
+ return head;
+ }
+
+ /**
+ * Links the entry to it self to form a ring.
+ *
+ * @param buffer input
+ * @return buffer
+ */
+ private static LlapCacheableBuffer linkToItSelf(LlapCacheableBuffer buffer) {
+ buffer.prev = buffer;
+ buffer.next = buffer;
+ return buffer;
+ }
+
+ @Override public void notifyLock(LlapCacheableBuffer buffer) {
+ buffer.setClockBit();
+ }
+
+ /**
+ * Notifies the policy that a buffer is unlocked after been used. This notification signals to the policy that an
+ * access to this page occurred.
+ *
+ * @param buffer buffer that just got unlocked after a read.
+ */
+ @Override public void notifyUnlock(LlapCacheableBuffer buffer) {
+
+ }
+
+ /**
+ * Signals to the policy that it has to evict some entries from the cache.
+ * Policy has to at least evict the amount memory requested.
+ * Not that is method will block until at least {@code memoryToReserve} bytes are evicted.
+ *
+ * @param memoryToReserve amount of bytes to be evicted
+ * @return actual amount of evicted bytes.
+ */
+ @Override public long evictSomeBlocks(long memoryToReserve) {
+ long evicted = 0;
+ if (clockHand == null) {
+ return evicted;
+ }
+ int fullClockRotation = 0;
+ listLock.lock();
+ try {
+ // ring tail is used to mark a clock circle
+ LlapCacheableBuffer ringTail = clockHand.prev;
+ // ring head is the current clock position that is under lock. Using local var under lock and updating actual
+ // clock position as soon we are done with looping
+ LlapCacheableBuffer currentClockHead = clockHand;
+
+ while (evicted < memoryToReserve && currentClockHead != null && fullClockRotation < maxCircles) {
+ if (ringTail == currentClockHead) {
+ fullClockRotation++;
+ }
+ if (currentClockHead.isClockBitSet()) {
+ // case the buffer getting second chance.
+ currentClockHead.unSetClockBit();
+ currentClockHead = currentClockHead.next;
+ } else {
+ // try to evict this victim
+ int invalidateFlag = currentClockHead.invalidate();
+ if (invalidateFlag == LlapCacheableBuffer.INVALIDATE_OK
+ || invalidateFlag == LlapCacheableBuffer.INVALIDATE_ALREADY_INVALID) {
+ if (invalidateFlag == LlapCacheableBuffer.INVALIDATE_OK) {
+ // case we are able to evict the buffer notify and account for it.
+ evictionListener.notifyEvicted(currentClockHead);
+ evicted += currentClockHead.getMemoryUsage();
+ }
+ LlapCacheableBuffer newHand = currentClockHead.next;
+ if (newHand == currentClockHead) {
+ // end of the ring we have looped, nothing else can be done...
+ currentClockHead = null;
+ break;
+ } else {
+ //remove it from the ring.
+ if (currentClockHead == ringTail) {
+ // we are about to remove the current ring tail thus we need to compute new tail
+ ringTail = ringTail.prev;
+ }
+ currentClockHead.prev.next = newHand;
+ newHand.prev = currentClockHead.prev;
+ currentClockHead = newHand;
+ }
+ } else if (invalidateFlag == LlapCacheableBuffer.INVALIDATE_FAILED) {
+ // can not be evicted case locked
+ currentClockHead = currentClockHead.next;
+ } else {
+ throw new IllegalStateException("Unknown invalidation flag " + invalidateFlag);
+ }
+ }
+ }
+ // done with clock rotations, update the current clock hand under lock.
+ clockHand = currentClockHead;
+ return evicted;
+ } finally {
+ listLock.unlock();
+ }
+ }
+
+ @Override public void setEvictionListener(EvictionListener listener) {
+ evictionListener = listener;
+ }
+
+ @Override public long purge() {
+ return evictSomeBlocks(Long.MAX_VALUE);
+ }
+
+ @Override public void debugDumpShort(StringBuilder sb) {
+ if (clockHand == null) {
+ sb.append("Clock is empty");
+ return;
+ }
+ listLock.lock();
+ try {
+ sb.append("Clock Status\n");
+ LlapCacheableBuffer currentClockHand = clockHand;
+ LlapCacheableBuffer lastElement = clockHand.prev;
+ while (currentClockHand != lastElement) {
+ sb.append(currentClockHand.toStringForCache());
+ currentClockHand = currentClockHand.next;
+ }
+ sb.append(lastElement.toStringForCache());
+ } finally {
+ listLock.unlock();
+ }
+ }
+
+ @VisibleForTesting protected Iterator<LlapCacheableBuffer> getIterator() {
Review comment:
Maybe you should add a header comment here, making it crystal clear that this method cannot be called outside of test as it is not synchronized via the lock?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] odraese commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
odraese commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r395929123
##########
File path: storage-api/src/java/org/apache/hadoop/hive/common/io/CacheTag.java
##########
@@ -239,7 +239,7 @@ public int hashCode() {
/**
* CacheTag for tables with more than one partition level.
*/
- public static final class MultiPartitionCacheTag extends PartitionCacheTag {
+ public static final class MultiPartitionCacheTag extends PartitionCacheTag {
Review comment:
I assume, these additional spaces were unintentional?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] odraese commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
odraese commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r395920504
##########
File path: llap-server/src/java/org/apache/hadoop/hive/llap/cache/LlapAllocatorBuffer.java
##########
@@ -80,9 +80,32 @@ int tryIncRef() {
return incRefInternal(false);
}
+ /**
+ *
+ */
+ @Override
+ public final void setClockBit() {
+ long val = state.get();
+ while (!State.isClockBitSet(val) && !state.compareAndSet(val, State.setClockBit(val))) {
+ val = state.get();
+ }
+ }
+ @Override
+ public final void unSetClockBit() {
Review comment:
There isn't really a need for any unSet as each check against the clockBit (observed) should reset the clock bit.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] odraese commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
odraese commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r395910202
##########
File path: llap-server/src/java/org/apache/hadoop/hive/llap/cache/ClockCachePolicy.java
##########
@@ -0,0 +1,264 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.hadoop.hive.llap.cache;
+
+import com.google.common.annotations.VisibleForTesting;
+import com.google.common.base.Preconditions;
+
+import javax.annotation.concurrent.GuardedBy;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+import java.util.concurrent.locks.Lock;
+import java.util.concurrent.locks.ReentrantLock;
+
+/**
+ * Clock eviction policy. Uses a simple circular list to keep a ring of current used buffers.
+ * New entries are added to tail of the clock hand AKA (clockHand.prev)
+ * Eviction start at the current clock hand following the next pointer.
+ *
+ */
+public class ClockCachePolicy implements LowLevelCachePolicy {
+
+ private static final int DEFAULT_MAX_CIRCLES = 5;
+
+ /**
+ * Lock to protect the state of the policy, used as mutex when modifying the circular linked list.
+ */
+ private final Lock listLock = new ReentrantLock();
+
+ /**
+ * The clock hand shared between threads thus made volatile, to ensure state when read outside of lock.
+ */
+ @GuardedBy("listLock")
+ private volatile LlapCacheableBuffer clockHand;
+
+ private EvictionListener evictionListener;
+ /**
+ * Max number of clock rotation before giving up on clock operation like eviction.
+ */
+ private final int maxCircles;
+
+ public ClockCachePolicy() {
+ maxCircles = DEFAULT_MAX_CIRCLES;
+ }
+
+ public ClockCachePolicy(int maxCircles) {
+ Preconditions.checkState(maxCircles > 0, "Maximum number of clock rotation must be positive and got " + maxCircles);
+ this.maxCircles = maxCircles;
+ }
+
+ /**
+ * Signals to the policy the addition of a new entry to the cache. An entry come with a priority that can be used as
+ * a hint to replacement policy.
+ *
+ * @param buffer buffer to be cached
+ * @param priority the priority of cached element
+ */
+ @Override public void cache(LlapCacheableBuffer buffer, LowLevelCache.Priority priority) {
+ listLock.lock();
+ try {
+ clockHand = appendToCircularList(clockHand, buffer);
+ } finally {
+ listLock.unlock();
+ }
+ }
+
+ /**
+ * Appends new entry to the tail of circular list.
+ *
+ * @param head circular list head.
+ * @param buffer new entry to be added.
+ * @return the ring head.
+ */
+ private static LlapCacheableBuffer appendToCircularList(LlapCacheableBuffer head, LlapCacheableBuffer buffer) {
+ if (head == null) {
+ return linkToItSelf(buffer);
+ }
+ buffer.next = head;
+ buffer.prev = head.prev;
+ head.prev.next = buffer;
+ head.prev = buffer;
+ return head;
+ }
+
+ /**
+ * Links the entry to it self to form a ring.
+ *
+ * @param buffer input
+ * @return buffer
+ */
+ private static LlapCacheableBuffer linkToItSelf(LlapCacheableBuffer buffer) {
+ buffer.prev = buffer;
+ buffer.next = buffer;
+ return buffer;
+ }
+
+ @Override public void notifyLock(LlapCacheableBuffer buffer) {
+ buffer.setClockBit();
+ }
+
+ /**
+ * Notifies the policy that a buffer is unlocked after been used. This notification signals to the policy that an
+ * access to this page occurred.
+ *
+ * @param buffer buffer that just got unlocked after a read.
+ */
+ @Override public void notifyUnlock(LlapCacheableBuffer buffer) {
Review comment:
Maybe unlock would be the better position to set the clock bit (this is the point until the buffer was used). While it is locked, the buffer is protected anyway and no-one is really looking at the clock bit.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] odraese commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
odraese commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r395852162
##########
File path: common/src/java/org/apache/hadoop/hive/conf/HiveConf.java
##########
@@ -4187,6 +4188,8 @@ private static void populateLlapDaemonVarsSet(Set<String> llapDaemonVarsSetLocal
"partitions and tables) for reporting."),
LLAP_USE_LRFU("hive.llap.io.use.lrfu", true,
"Whether ORC low-level cache should use LRFU cache policy instead of default (FIFO)."),
+ LLAP_IO_CACHE_STRATEGY("hive.llap.io.replacement.strategy", "lrfu", new StringSet("fifo", "clock", "lrfu"),
+ "Cache replacement strategy used by low-level (default to LRFU)."),
Review comment:
used by low-level what?
would rewrite to "Replacement strategy for IO/data cache"
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] prasanthj commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
prasanthj commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r400417675
##########
File path: llap-server/src/java/org/apache/hadoop/hive/llap/cache/ClockCachePolicy.java
##########
@@ -0,0 +1,313 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.hadoop.hive.llap.cache;
+
+import com.google.common.annotations.VisibleForTesting;
+import com.google.common.base.Preconditions;
+import org.apache.hadoop.hive.llap.io.metadata.MetadataCache;
+
+import javax.annotation.concurrent.GuardedBy;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+import java.util.concurrent.locks.Lock;
+import java.util.concurrent.locks.ReentrantLock;
+
+/**
+ * Clock eviction policy. Uses a simple circular list to keep a ring of current used buffers.
+ * New entries are added to tail of the clock hand AKA (clockHand.prev)
+ * Eviction start at the current clock hand following the next pointer.
+ *
+ */
+public class ClockCachePolicy implements LowLevelCachePolicy {
+
+ private static final int DEFAULT_MAX_CIRCLES = 5;
+
+ /**
+ * Lock to protect the state of the policy, used as mutex when modifying the circular linked list.
+ */
+ private final Lock listLock = new ReentrantLock();
+
+ /**
+ * The clock hand shared between threads thus made volatile, to ensure state when read outside of lock.
+ */
+ @GuardedBy("listLock")
+ private volatile LlapCacheableBuffer clockHand;
+
+ private EvictionListener evictionListener;
+ /**
+ * Max number of clock rotation before giving up on clock operation like eviction.
+ */
+ private final int maxCircles;
+
+ public ClockCachePolicy() {
+ maxCircles = DEFAULT_MAX_CIRCLES;
+ }
+
+ public ClockCachePolicy(int maxCircles) {
+ Preconditions.checkState(maxCircles > 0, "Maximum number of clock rotation must be positive and got " + maxCircles);
+ this.maxCircles = maxCircles;
+ }
+
+ /**
+ * Signals to the policy the addition of a new entry to the cache. An entry come with a priority that can be used as
+ * a hint to replacement policy.
+ *
+ * @param buffer buffer to be cached
+ * @param priority the priority of cached element
+ */
+ @Override public void cache(LlapCacheableBuffer buffer, LowLevelCache.Priority priority) {
+ listLock.lock();
+ try {
+ //noinspection NonAtomicOperationOnVolatileField
+ clockHand = appendToCircularList(clockHand, buffer);
+ } finally {
+ listLock.unlock();
+ }
+ }
+
+ /**
+ * Appends new entry to the tail of circular list.
+ *
+ * @param head circular list head.
+ * @param buffer new entry to be added.
+ * @return the ring head.
+ */
+ private static LlapCacheableBuffer appendToCircularList(LlapCacheableBuffer head, LlapCacheableBuffer buffer) {
+ if (head == null) {
+ return linkToItSelf(buffer);
+ }
+ buffer.next = head;
+ buffer.prev = head.prev;
+ head.prev.next = buffer;
+ head.prev = buffer;
+ return head;
+ }
+
+ /**
+ * Links the entry to it self to form a ring.
+ *
+ * @param buffer input
+ * @return buffer
+ */
+ private static LlapCacheableBuffer linkToItSelf(LlapCacheableBuffer buffer) {
+ buffer.prev = buffer;
+ buffer.next = buffer;
+ return buffer;
+ }
+
+ @Override public void notifyLock(LlapCacheableBuffer buffer) {
+ buffer.setClockBit();
+ }
+
+ /**
+ * Notifies the policy that a buffer is unlocked after been used. This notification signals to the policy that an
+ * access to this page occurred.
+ *
+ * @param buffer buffer that just got unlocked after a read.
+ */
+ @Override public void notifyUnlock(LlapCacheableBuffer buffer) {
+
+ }
+
+ /**
+ * Signals to the policy that it has to evict some entries from the cache.
+ * Policy has to at least evict the amount memory requested.
+ * Not that is method will block until at least {@code memoryToReserve} bytes are evicted.
Review comment:
nit: Note?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] odraese commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
odraese commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r395924117
##########
File path: llap-server/src/java/org/apache/hadoop/hive/llap/cache/LlapCacheableBuffer.java
##########
@@ -26,39 +26,71 @@
* using a real programming language.
*/
public abstract class LlapCacheableBuffer {
- protected static final int IN_LIST = -2, NOT_IN_CACHE = -1;
-
- /** Priority for cache policy (should be pretty universal). */
- public double priority;
- /** Last priority update time for cache policy (should be pretty universal). */
- public long lastUpdate = -1;
+ public static final int INVALIDATE_OK = 0, INVALIDATE_FAILED = 1, INVALIDATE_ALREADY_INVALID = 2;
- // TODO: remove some of these fields as needed?
+ public CacheAttribute cacheAttribute;
/** Linked list pointers for LRFU/LRU cache policies. Given that each block is in cache
* that might be better than external linked list. Or not, since this is not concurrent. */
public LlapCacheableBuffer prev = null;
/** Linked list pointers for LRFU/LRU cache policies. Given that each block is in cache
* that might be better than external linked list. Or not, since this is not concurrent. */
public LlapCacheableBuffer next = null;
- /** Index in heap for LRFU/LFU cache policies. */
- public int indexInHeap = NOT_IN_CACHE;
- public static final int INVALIDATE_OK = 0, INVALIDATE_FAILED = 1, INVALIDATE_ALREADY_INVALID = 2;
+ /**
+ * @return result of invalidation.
+ */
protected abstract int invalidate();
+
+ /**
+ * @return size of the buffer in bytes.
+ */
public abstract long getMemoryUsage();
+
+ /**
+ * @param evictionDispatcher dispatcher object to be notified.
+ */
public abstract void notifyEvicted(EvictionDispatcher evictionDispatcher);
+ /**
Review comment:
As mentioned in the LlapAllocatorBuffer: we should keep the CachableBuffer clear of eviction policy specific methods.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] prasanthj commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
prasanthj commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r400414707
##########
File path: llap-server/src/java/org/apache/hadoop/hive/llap/cache/CacheAttribute.java
##########
@@ -0,0 +1,42 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.hadoop.hive.llap.cache;
+
+/**
+ * Cache attributes Interface to allow sophisticated cache policy add their api without adding memory overhead.
+ */
+public interface CacheAttribute {
+ /**
+ * @return buffer priority (actual semantic is up to {@link LowLevelCachePolicy}).
+ */
+ double getPriority();
+ void setPriority(double priority);
+
+ /**
+ * @return actual time where the buffer was touched last.
+ */
+ long getLastUpdate();
+ void setTouchTime(long time);
Review comment:
nit: add interface doc for the public methods?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] b-slim commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
b-slim commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r396563288
##########
File path: llap-server/src/java/org/apache/hadoop/hive/llap/cache/ClockCachePolicy.java
##########
@@ -0,0 +1,264 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.hadoop.hive.llap.cache;
+
+import com.google.common.annotations.VisibleForTesting;
+import com.google.common.base.Preconditions;
+
+import javax.annotation.concurrent.GuardedBy;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+import java.util.concurrent.locks.Lock;
+import java.util.concurrent.locks.ReentrantLock;
+
+/**
+ * Clock eviction policy. Uses a simple circular list to keep a ring of current used buffers.
+ * New entries are added to tail of the clock hand AKA (clockHand.prev)
+ * Eviction start at the current clock hand following the next pointer.
+ *
+ */
+public class ClockCachePolicy implements LowLevelCachePolicy {
+
+ private static final int DEFAULT_MAX_CIRCLES = 5;
+
+ /**
+ * Lock to protect the state of the policy, used as mutex when modifying the circular linked list.
+ */
+ private final Lock listLock = new ReentrantLock();
+
+ /**
+ * The clock hand shared between threads thus made volatile, to ensure state when read outside of lock.
+ */
+ @GuardedBy("listLock")
+ private volatile LlapCacheableBuffer clockHand;
+
+ private EvictionListener evictionListener;
+ /**
+ * Max number of clock rotation before giving up on clock operation like eviction.
+ */
+ private final int maxCircles;
+
+ public ClockCachePolicy() {
+ maxCircles = DEFAULT_MAX_CIRCLES;
+ }
+
+ public ClockCachePolicy(int maxCircles) {
+ Preconditions.checkState(maxCircles > 0, "Maximum number of clock rotation must be positive and got " + maxCircles);
+ this.maxCircles = maxCircles;
+ }
+
+ /**
+ * Signals to the policy the addition of a new entry to the cache. An entry come with a priority that can be used as
+ * a hint to replacement policy.
+ *
+ * @param buffer buffer to be cached
+ * @param priority the priority of cached element
+ */
+ @Override public void cache(LlapCacheableBuffer buffer, LowLevelCache.Priority priority) {
+ listLock.lock();
+ try {
+ clockHand = appendToCircularList(clockHand, buffer);
+ } finally {
+ listLock.unlock();
+ }
+ }
+
+ /**
+ * Appends new entry to the tail of circular list.
+ *
+ * @param head circular list head.
+ * @param buffer new entry to be added.
+ * @return the ring head.
+ */
+ private static LlapCacheableBuffer appendToCircularList(LlapCacheableBuffer head, LlapCacheableBuffer buffer) {
+ if (head == null) {
+ return linkToItSelf(buffer);
+ }
+ buffer.next = head;
+ buffer.prev = head.prev;
+ head.prev.next = buffer;
+ head.prev = buffer;
+ return head;
+ }
+
+ /**
+ * Links the entry to it self to form a ring.
+ *
+ * @param buffer input
+ * @return buffer
+ */
+ private static LlapCacheableBuffer linkToItSelf(LlapCacheableBuffer buffer) {
+ buffer.prev = buffer;
+ buffer.next = buffer;
+ return buffer;
+ }
+
+ @Override public void notifyLock(LlapCacheableBuffer buffer) {
+ buffer.setClockBit();
+ }
+
+ /**
+ * Notifies the policy that a buffer is unlocked after been used. This notification signals to the policy that an
+ * access to this page occurred.
+ *
+ * @param buffer buffer that just got unlocked after a read.
+ */
+ @Override public void notifyUnlock(LlapCacheableBuffer buffer) {
+
+ }
+
+ /**
+ * Signals to the policy that it has to evict some entries from the cache.
+ * Policy has to at least evict the amount memory requested.
+ * Not that is method will block until at least {@code memoryToReserve} bytes are evicted.
+ *
+ * @param memoryToReserve amount of bytes to be evicted
+ * @return actual amount of evicted bytes.
+ */
+ @Override public long evictSomeBlocks(long memoryToReserve) {
+ long evicted = 0;
+ if (clockHand == null) {
+ return evicted;
+ }
+ int fullClockRotation = 0;
+ listLock.lock();
+ try {
+ // ring tail is used to mark a clock circle
+ LlapCacheableBuffer ringTail = clockHand.prev;
+ // ring head is the current clock position that is under lock. Using local var under lock and updating actual
+ // clock position as soon we are done with looping
+ LlapCacheableBuffer currentClockHead = clockHand;
+
+ while (evicted < memoryToReserve && currentClockHead != null && fullClockRotation < maxCircles) {
+ if (ringTail == currentClockHead) {
+ fullClockRotation++;
+ }
+ if (currentClockHead.isClockBitSet()) {
Review comment:
will do
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] b-slim commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
b-slim commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r396548828
##########
File path: common/src/java/org/apache/hadoop/hive/conf/HiveConf.java
##########
@@ -4196,6 +4199,9 @@ private static void populateLlapDaemonVarsSet(Set<String> llapDaemonVarsSetLocal
LLAP_LRFU_BP_WRAPPER_SIZE("hive.llap.io.lrfu.bp.wrapper.size", 64, "thread local queue "
+ "used to amortize the lock contention, the idea hear is to try locking as soon we reach max size / 2 "
+ "and block when max queue size reached"),
+ LLAP_IO_MAX_CLOCK_ROTATION("hive.llap.io.clock.max.rotation",
Review comment:
Agree with you this is not for customer at all, it is more for dev nob in case of issue we can push the nob on the customer side without deploying code. Will add more comments about it. this makes me thing that we need to add some annotation about what configs are suppose to be dev configs and the one that can be used by customer. Any other suggestion will be welcomed.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] odraese commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
odraese commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r395920121
##########
File path: llap-server/src/java/org/apache/hadoop/hive/llap/cache/ClockCachePolicy.java
##########
@@ -0,0 +1,264 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.hadoop.hive.llap.cache;
+
+import com.google.common.annotations.VisibleForTesting;
+import com.google.common.base.Preconditions;
+
+import javax.annotation.concurrent.GuardedBy;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+import java.util.concurrent.locks.Lock;
+import java.util.concurrent.locks.ReentrantLock;
+
+/**
+ * Clock eviction policy. Uses a simple circular list to keep a ring of current used buffers.
+ * New entries are added to tail of the clock hand AKA (clockHand.prev)
+ * Eviction start at the current clock hand following the next pointer.
+ *
+ */
+public class ClockCachePolicy implements LowLevelCachePolicy {
Review comment:
One advantage of the real CLOCK implementation is that it can be done lock - free. This implementation of a linked list, keeping a lock (for up to 5 clock rotations) might actually be susceptible to lock contention. At the very least, we should track the lock durations (via the instrumented lock) but in general I would propose to use a fixed size array for the CLOCK buffer and remove the lock all together.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] b-slim commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
b-slim commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r396568465
##########
File path: llap-server/src/java/org/apache/hadoop/hive/llap/cache/LlapAllocatorBuffer.java
##########
@@ -80,9 +80,32 @@ int tryIncRef() {
return incRefInternal(false);
}
+ /**
+ *
+ */
+ @Override
+ public final void setClockBit() {
+ long val = state.get();
+ while (!State.isClockBitSet(val) && !state.compareAndSet(val, State.setClockBit(val))) {
+ val = state.get();
+ }
+ }
+ @Override
+ public final void unSetClockBit() {
Review comment:
did merge it let me know what you think.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] odraese commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
odraese commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r395916820
##########
File path: llap-server/src/java/org/apache/hadoop/hive/llap/cache/ClockCachePolicy.java
##########
@@ -0,0 +1,264 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.hadoop.hive.llap.cache;
+
+import com.google.common.annotations.VisibleForTesting;
+import com.google.common.base.Preconditions;
+
+import javax.annotation.concurrent.GuardedBy;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+import java.util.concurrent.locks.Lock;
+import java.util.concurrent.locks.ReentrantLock;
+
+/**
+ * Clock eviction policy. Uses a simple circular list to keep a ring of current used buffers.
+ * New entries are added to tail of the clock hand AKA (clockHand.prev)
+ * Eviction start at the current clock hand following the next pointer.
+ *
+ */
+public class ClockCachePolicy implements LowLevelCachePolicy {
+
+ private static final int DEFAULT_MAX_CIRCLES = 5;
+
+ /**
+ * Lock to protect the state of the policy, used as mutex when modifying the circular linked list.
+ */
+ private final Lock listLock = new ReentrantLock();
+
+ /**
+ * The clock hand shared between threads thus made volatile, to ensure state when read outside of lock.
+ */
+ @GuardedBy("listLock")
+ private volatile LlapCacheableBuffer clockHand;
+
+ private EvictionListener evictionListener;
+ /**
+ * Max number of clock rotation before giving up on clock operation like eviction.
+ */
+ private final int maxCircles;
+
+ public ClockCachePolicy() {
+ maxCircles = DEFAULT_MAX_CIRCLES;
+ }
+
+ public ClockCachePolicy(int maxCircles) {
+ Preconditions.checkState(maxCircles > 0, "Maximum number of clock rotation must be positive and got " + maxCircles);
+ this.maxCircles = maxCircles;
+ }
+
+ /**
+ * Signals to the policy the addition of a new entry to the cache. An entry come with a priority that can be used as
+ * a hint to replacement policy.
+ *
+ * @param buffer buffer to be cached
+ * @param priority the priority of cached element
+ */
+ @Override public void cache(LlapCacheableBuffer buffer, LowLevelCache.Priority priority) {
+ listLock.lock();
+ try {
+ clockHand = appendToCircularList(clockHand, buffer);
+ } finally {
+ listLock.unlock();
+ }
+ }
+
+ /**
+ * Appends new entry to the tail of circular list.
+ *
+ * @param head circular list head.
+ * @param buffer new entry to be added.
+ * @return the ring head.
+ */
+ private static LlapCacheableBuffer appendToCircularList(LlapCacheableBuffer head, LlapCacheableBuffer buffer) {
+ if (head == null) {
+ return linkToItSelf(buffer);
+ }
+ buffer.next = head;
+ buffer.prev = head.prev;
+ head.prev.next = buffer;
+ head.prev = buffer;
+ return head;
+ }
+
+ /**
+ * Links the entry to it self to form a ring.
+ *
+ * @param buffer input
+ * @return buffer
+ */
+ private static LlapCacheableBuffer linkToItSelf(LlapCacheableBuffer buffer) {
+ buffer.prev = buffer;
+ buffer.next = buffer;
+ return buffer;
+ }
+
+ @Override public void notifyLock(LlapCacheableBuffer buffer) {
+ buffer.setClockBit();
+ }
+
+ /**
+ * Notifies the policy that a buffer is unlocked after been used. This notification signals to the policy that an
+ * access to this page occurred.
+ *
+ * @param buffer buffer that just got unlocked after a read.
+ */
+ @Override public void notifyUnlock(LlapCacheableBuffer buffer) {
+
+ }
+
+ /**
+ * Signals to the policy that it has to evict some entries from the cache.
+ * Policy has to at least evict the amount memory requested.
+ * Not that is method will block until at least {@code memoryToReserve} bytes are evicted.
+ *
+ * @param memoryToReserve amount of bytes to be evicted
+ * @return actual amount of evicted bytes.
+ */
+ @Override public long evictSomeBlocks(long memoryToReserve) {
+ long evicted = 0;
+ if (clockHand == null) {
+ return evicted;
+ }
+ int fullClockRotation = 0;
+ listLock.lock();
+ try {
+ // ring tail is used to mark a clock circle
+ LlapCacheableBuffer ringTail = clockHand.prev;
+ // ring head is the current clock position that is under lock. Using local var under lock and updating actual
+ // clock position as soon we are done with looping
+ LlapCacheableBuffer currentClockHead = clockHand;
+
+ while (evicted < memoryToReserve && currentClockHead != null && fullClockRotation < maxCircles) {
Review comment:
There is currently no code path, which could lead to currentClockHead being null.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] odraese commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
odraese commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r395924616
##########
File path: llap-server/src/java/org/apache/hadoop/hive/llap/cache/LowLevelCachePolicy.java
##########
@@ -26,6 +28,32 @@
*/
public interface LowLevelCachePolicy extends LlapIoDebugDump {
+ static LowLevelCachePolicy provideFromConf(Configuration conf) {
Review comment:
Suggestion: Rename factory method to createForConf
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] odraese commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
odraese commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r395928863
##########
File path: llap-server/src/java/org/apache/hadoop/hive/llap/io/metadata/OrcFileEstimateErrors.java
##########
@@ -32,6 +32,11 @@
import org.apache.hadoop.hive.ql.util.IncrementalObjectSizeEstimator;
import org.apache.hadoop.hive.ql.util.IncrementalObjectSizeEstimator.ObjectEstimator;
+/**
+ * Metadata Cache entry that does hold information about Files.
+ * No actual allocated bytebuffers is used by this class,
Review comment:
bytebuffers -> bytebuffer
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] b-slim commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
b-slim commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r396624247
##########
File path: llap-server/src/java/org/apache/hadoop/hive/llap/cache/LowLevelLrfuCachePolicy.java
##########
@@ -189,26 +188,33 @@ private void doNotifyUnderHeapLock(int count, LlapCacheableBuffer[] cacheableBuf
LlapIoImpl.CACHE_LOGGER.trace("Touching {} at {}", buffer, time);
}
// First, update buffer priority - we have just been using it.
- buffer.priority = (buffer.lastUpdate == -1) ? F0
- : touchPriority(time, buffer.lastUpdate, buffer.priority);
- buffer.lastUpdate = time;
+ LrfuCacheAttribute lrfuCacheAttribute = (LrfuCacheAttribute) buffer.cacheAttribute;
+ if (lrfuCacheAttribute == null) {
+ //This should not happen but it is possible that adding the attribute on cache call happens after this call
+ lrfuCacheAttribute = new LrfuCacheAttribute(F0, time);
+ buffer.cacheAttribute = lrfuCacheAttribute;
+ } else {
+ lrfuCacheAttribute.lastUpdate = time;
+ lrfuCacheAttribute.priority = touchPriority(time, lrfuCacheAttribute.lastUpdate, lrfuCacheAttribute.priority);
+ }
+
// Then, if the buffer was in the list, remove it.
- if (buffer.indexInHeap == LlapCacheableBuffer.IN_LIST) {
+ if (lrfuCacheAttribute.indexInHeap == IN_LIST) {
listLock.lock();
removeFromListAndUnlock(buffer);
}
// The only concurrent change that can happen when we hold the heap lock is list removal;
// we have just ensured the item is not in the list, so we have a definite state now.
- if (buffer.indexInHeap >= 0) {
+ if (lrfuCacheAttribute.indexInHeap >= 0) {
// The buffer has lived in the heap all along. Restore heap property.
heapifyDownUnderLock(buffer, time);
} else if (heapSize == heap.length) {
// The buffer is not in the (full) heap. Demote the top item of the heap into the list.
LlapCacheableBuffer demoted = heap[0];
listLock.lock();
try {
- assert demoted.indexInHeap == 0; // Noone could have moved it, we have the heap lock.
- demoted.indexInHeap = LlapCacheableBuffer.IN_LIST;
+ //assert demoted.indexInHeap == 0; // Noone could have moved it, we have the heap lock.
Review comment:
reverted
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] prasanthj commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
prasanthj commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r400490326
##########
File path: llap-server/src/java/org/apache/hadoop/hive/llap/cache/LowLevelCachePolicy.java
##########
@@ -26,6 +28,32 @@
*/
public interface LowLevelCachePolicy extends LlapIoDebugDump {
+ static LowLevelCachePolicy provideFromConf(Configuration conf) {
+ final long totalMemorySize = HiveConf.getSizeVar(conf, HiveConf.ConfVars.LLAP_IO_MEMORY_MAX_SIZE);
+ final int minAllocSize = (int) HiveConf.getSizeVar(conf, HiveConf.ConfVars.LLAP_ALLOCATOR_MIN_ALLOC);
+ String policyName = HiveConf.getVar(conf,HiveConf.ConfVars.LLAP_IO_CACHE_STRATEGY);
Review comment:
or make the policy name lowercase here to be case insensitive always?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] odraese commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
odraese commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r395852807
##########
File path: common/src/java/org/apache/hadoop/hive/conf/HiveConf.java
##########
@@ -4196,6 +4199,9 @@ private static void populateLlapDaemonVarsSet(Set<String> llapDaemonVarsSetLocal
LLAP_LRFU_BP_WRAPPER_SIZE("hive.llap.io.lrfu.bp.wrapper.size", 64, "thread local queue "
+ "used to amortize the lock contention, the idea hear is to try locking as soon we reach max size / 2 "
+ "and block when max queue size reached"),
+ LLAP_IO_MAX_CLOCK_ROTATION("hive.llap.io.clock.max.rotation",
Review comment:
do we really need to configure this? Sounds to me like something that a customer would never override (and which we would have a const)
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] prasanthj commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
prasanthj commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r400424669
##########
File path: llap-server/src/java/org/apache/hadoop/hive/llap/cache/LlapAllocatorBuffer.java
##########
@@ -337,25 +364,34 @@ public Boolean endDiscard() {
return result;
}
- private static final class State {
- public static final int
- FLAG_MOVING = 0b00001, // Locked by someone to move or force-evict.
- FLAG_EVICTED = 0b00010, // Evicted. This is cache-specific.
- FLAG_REMOVED = 0b00100, // Removed from allocator structures. The final state.
- FLAG_MEM_RELEASED = 0b01000, // The memory was released to memory manager.
- FLAG_NEW_ALLOC = 0b10000; // New allocation before the first use; cannot force-evict.
- private static final int FLAGS_WIDTH = 5,
- REFCOUNT_WIDTH = 19, ARENA_WIDTH = 16, HEADER_WIDTH = 24;
-
- public static final long MAX_REFCOUNT = (1 << REFCOUNT_WIDTH) - 1;
-
- private static final int REFCOUNT_SHIFT = FLAGS_WIDTH,
- ARENA_SHIFT = REFCOUNT_SHIFT + REFCOUNT_WIDTH, HEADER_SHIFT = ARENA_SHIFT + ARENA_WIDTH;
-
- private static final long FLAGS_MASK = (1L << FLAGS_WIDTH) - 1,
- REFCOUNT_MASK = ((1L << REFCOUNT_WIDTH) - 1) << REFCOUNT_SHIFT,
- ARENA_MASK = ((1L << ARENA_WIDTH) - 1) << ARENA_SHIFT,
- HEADER_MASK = ((1L << HEADER_WIDTH) - 1) << HEADER_SHIFT;
+ /**
+ * Utility class to manipulate the buffer state.
+ */
+ static final class State {
Review comment:
There seems to be many global state manipulation. Can you lease a comment that the state manipulations are global. Can rename the class to be CacheState/GlobalCacheState to be more precise about what state it represents.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] prasanthj commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
prasanthj commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r400417050
##########
File path: llap-server/src/java/org/apache/hadoop/hive/llap/cache/ClockCachePolicy.java
##########
@@ -0,0 +1,313 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.hadoop.hive.llap.cache;
+
+import com.google.common.annotations.VisibleForTesting;
+import com.google.common.base.Preconditions;
+import org.apache.hadoop.hive.llap.io.metadata.MetadataCache;
+
+import javax.annotation.concurrent.GuardedBy;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+import java.util.concurrent.locks.Lock;
+import java.util.concurrent.locks.ReentrantLock;
+
+/**
+ * Clock eviction policy. Uses a simple circular list to keep a ring of current used buffers.
+ * New entries are added to tail of the clock hand AKA (clockHand.prev)
+ * Eviction start at the current clock hand following the next pointer.
+ *
+ */
+public class ClockCachePolicy implements LowLevelCachePolicy {
+
+ private static final int DEFAULT_MAX_CIRCLES = 5;
+
+ /**
+ * Lock to protect the state of the policy, used as mutex when modifying the circular linked list.
+ */
+ private final Lock listLock = new ReentrantLock();
+
+ /**
+ * The clock hand shared between threads thus made volatile, to ensure state when read outside of lock.
+ */
+ @GuardedBy("listLock")
+ private volatile LlapCacheableBuffer clockHand;
+
+ private EvictionListener evictionListener;
+ /**
+ * Max number of clock rotation before giving up on clock operation like eviction.
+ */
+ private final int maxCircles;
+
+ public ClockCachePolicy() {
+ maxCircles = DEFAULT_MAX_CIRCLES;
+ }
+
+ public ClockCachePolicy(int maxCircles) {
+ Preconditions.checkState(maxCircles > 0, "Maximum number of clock rotation must be positive and got " + maxCircles);
+ this.maxCircles = maxCircles;
+ }
+
+ /**
+ * Signals to the policy the addition of a new entry to the cache. An entry come with a priority that can be used as
+ * a hint to replacement policy.
+ *
+ * @param buffer buffer to be cached
+ * @param priority the priority of cached element
+ */
+ @Override public void cache(LlapCacheableBuffer buffer, LowLevelCache.Priority priority) {
+ listLock.lock();
+ try {
+ //noinspection NonAtomicOperationOnVolatileField
+ clockHand = appendToCircularList(clockHand, buffer);
+ } finally {
+ listLock.unlock();
+ }
+ }
+
+ /**
+ * Appends new entry to the tail of circular list.
+ *
+ * @param head circular list head.
+ * @param buffer new entry to be added.
+ * @return the ring head.
+ */
+ private static LlapCacheableBuffer appendToCircularList(LlapCacheableBuffer head, LlapCacheableBuffer buffer) {
+ if (head == null) {
+ return linkToItSelf(buffer);
+ }
+ buffer.next = head;
+ buffer.prev = head.prev;
+ head.prev.next = buffer;
+ head.prev = buffer;
+ return head;
+ }
+
+ /**
+ * Links the entry to it self to form a ring.
+ *
+ * @param buffer input
+ * @return buffer
+ */
+ private static LlapCacheableBuffer linkToItSelf(LlapCacheableBuffer buffer) {
Review comment:
same here. why static?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] b-slim commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
b-slim commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r396618448
##########
File path: llap-server/src/java/org/apache/hadoop/hive/llap/cache/LowLevelCachePolicy.java
##########
@@ -26,6 +28,32 @@
*/
public interface LowLevelCachePolicy extends LlapIoDebugDump {
+ static LowLevelCachePolicy provideFromConf(Configuration conf) {
+ final long totalMemorySize = HiveConf.getSizeVar(conf, HiveConf.ConfVars.LLAP_IO_MEMORY_MAX_SIZE);
+ final int minAllocSize = (int) HiveConf.getSizeVar(conf, HiveConf.ConfVars.LLAP_ALLOCATOR_MIN_ALLOC);
+ String policyName = HiveConf.getVar(conf,HiveConf.ConfVars.LLAP_IO_CACHE_STRATEGY);
Review comment:
you mean the policyName to policyname ?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] b-slim commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
b-slim commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r396554267
##########
File path: llap-server/src/java/org/apache/hadoop/hive/llap/cache/ClockCachePolicy.java
##########
@@ -0,0 +1,264 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.hadoop.hive.llap.cache;
+
+import com.google.common.annotations.VisibleForTesting;
+import com.google.common.base.Preconditions;
+
+import javax.annotation.concurrent.GuardedBy;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+import java.util.concurrent.locks.Lock;
+import java.util.concurrent.locks.ReentrantLock;
+
+/**
+ * Clock eviction policy. Uses a simple circular list to keep a ring of current used buffers.
+ * New entries are added to tail of the clock hand AKA (clockHand.prev)
+ * Eviction start at the current clock hand following the next pointer.
+ *
+ */
+public class ClockCachePolicy implements LowLevelCachePolicy {
+
+ private static final int DEFAULT_MAX_CIRCLES = 5;
+
+ /**
+ * Lock to protect the state of the policy, used as mutex when modifying the circular linked list.
+ */
+ private final Lock listLock = new ReentrantLock();
+
+ /**
+ * The clock hand shared between threads thus made volatile, to ensure state when read outside of lock.
+ */
+ @GuardedBy("listLock")
+ private volatile LlapCacheableBuffer clockHand;
+
+ private EvictionListener evictionListener;
+ /**
+ * Max number of clock rotation before giving up on clock operation like eviction.
+ */
+ private final int maxCircles;
+
+ public ClockCachePolicy() {
+ maxCircles = DEFAULT_MAX_CIRCLES;
+ }
+
+ public ClockCachePolicy(int maxCircles) {
+ Preconditions.checkState(maxCircles > 0, "Maximum number of clock rotation must be positive and got " + maxCircles);
+ this.maxCircles = maxCircles;
+ }
+
+ /**
+ * Signals to the policy the addition of a new entry to the cache. An entry come with a priority that can be used as
+ * a hint to replacement policy.
+ *
+ * @param buffer buffer to be cached
+ * @param priority the priority of cached element
+ */
+ @Override public void cache(LlapCacheableBuffer buffer, LowLevelCache.Priority priority) {
+ listLock.lock();
+ try {
+ clockHand = appendToCircularList(clockHand, buffer);
+ } finally {
+ listLock.unlock();
+ }
+ }
+
+ /**
+ * Appends new entry to the tail of circular list.
+ *
+ * @param head circular list head.
+ * @param buffer new entry to be added.
+ * @return the ring head.
+ */
+ private static LlapCacheableBuffer appendToCircularList(LlapCacheableBuffer head, LlapCacheableBuffer buffer) {
+ if (head == null) {
+ return linkToItSelf(buffer);
+ }
+ buffer.next = head;
+ buffer.prev = head.prev;
+ head.prev.next = buffer;
+ head.prev = buffer;
+ return head;
+ }
+
+ /**
+ * Links the entry to it self to form a ring.
+ *
+ * @param buffer input
+ * @return buffer
+ */
+ private static LlapCacheableBuffer linkToItSelf(LlapCacheableBuffer buffer) {
+ buffer.prev = buffer;
+ buffer.next = buffer;
+ return buffer;
+ }
+
+ @Override public void notifyLock(LlapCacheableBuffer buffer) {
+ buffer.setClockBit();
+ }
+
+ /**
+ * Notifies the policy that a buffer is unlocked after been used. This notification signals to the policy that an
+ * access to this page occurred.
+ *
+ * @param buffer buffer that just got unlocked after a read.
+ */
+ @Override public void notifyUnlock(LlapCacheableBuffer buffer) {
Review comment:
The bit set is lock free so i do not think will change much TBH. to avoid changing lot of the tests setup i will keep it as is and change it in the future if we see a strong case for it. Thanks
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] odraese commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
odraese commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r395926383
##########
File path: llap-server/src/java/org/apache/hadoop/hive/llap/cache/LowLevelLrfuCachePolicy.java
##########
@@ -491,29 +499,32 @@ private int moveMinChildUp(int targetPos, long time, double comparePri) {
}
if (leftPri <= rightPri) { // prefer left, cause right might be missing
heap[targetPos] = left;
- left.indexInHeap = targetPos;
+ LrfuCacheAttribute leftCacheAttribute = (LrfuCacheAttribute) left.cacheAttribute;
+ leftCacheAttribute.indexInHeap = targetPos;
Review comment:
why doesn't this use a setter?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] odraese commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
odraese commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r395925302
##########
File path: llap-server/src/java/org/apache/hadoop/hive/llap/cache/LowLevelLrfuCachePolicy.java
##########
@@ -43,6 +43,8 @@
* Additionally, buffer locking has to be handled (locked buffer cannot be evicted).
*/
public final class LowLevelLrfuCachePolicy implements LowLevelCachePolicy {
+ public static final int IN_LIST = -2;
Review comment:
Similar to invalidate constants: a) why negative valeues b) why not enum?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] b-slim commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
b-slim commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r396638475
##########
File path: llap-server/src/java/org/apache/hadoop/hive/llap/cache/ClockCachePolicy.java
##########
@@ -0,0 +1,264 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.hadoop.hive.llap.cache;
+
+import com.google.common.annotations.VisibleForTesting;
+import com.google.common.base.Preconditions;
+
+import javax.annotation.concurrent.GuardedBy;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+import java.util.concurrent.locks.Lock;
+import java.util.concurrent.locks.ReentrantLock;
+
+/**
+ * Clock eviction policy. Uses a simple circular list to keep a ring of current used buffers.
+ * New entries are added to tail of the clock hand AKA (clockHand.prev)
+ * Eviction start at the current clock hand following the next pointer.
+ *
+ */
+public class ClockCachePolicy implements LowLevelCachePolicy {
Review comment:
In theory i totally agree with you, although in practice i benchmarked with lock free FIFO implementations and I can not see anything that really moves the needle, but am up to work on second patch that makes this 100 lock free.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] b-slim commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
b-slim commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r396545711
##########
File path: common/src/java/org/apache/hadoop/hive/conf/HiveConf.java
##########
@@ -4187,6 +4188,8 @@ private static void populateLlapDaemonVarsSet(Set<String> llapDaemonVarsSetLocal
"partitions and tables) for reporting."),
LLAP_USE_LRFU("hive.llap.io.use.lrfu", true,
Review comment:
good point.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] b-slim commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
b-slim commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r396566811
##########
File path: llap-server/src/java/org/apache/hadoop/hive/llap/cache/ClockCachePolicy.java
##########
@@ -0,0 +1,264 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.hadoop.hive.llap.cache;
+
+import com.google.common.annotations.VisibleForTesting;
+import com.google.common.base.Preconditions;
+
+import javax.annotation.concurrent.GuardedBy;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+import java.util.concurrent.locks.Lock;
+import java.util.concurrent.locks.ReentrantLock;
+
+/**
+ * Clock eviction policy. Uses a simple circular list to keep a ring of current used buffers.
+ * New entries are added to tail of the clock hand AKA (clockHand.prev)
+ * Eviction start at the current clock hand following the next pointer.
+ *
+ */
+public class ClockCachePolicy implements LowLevelCachePolicy {
+
+ private static final int DEFAULT_MAX_CIRCLES = 5;
+
+ /**
+ * Lock to protect the state of the policy, used as mutex when modifying the circular linked list.
+ */
+ private final Lock listLock = new ReentrantLock();
+
+ /**
+ * The clock hand shared between threads thus made volatile, to ensure state when read outside of lock.
+ */
+ @GuardedBy("listLock")
+ private volatile LlapCacheableBuffer clockHand;
+
+ private EvictionListener evictionListener;
+ /**
+ * Max number of clock rotation before giving up on clock operation like eviction.
+ */
+ private final int maxCircles;
+
+ public ClockCachePolicy() {
+ maxCircles = DEFAULT_MAX_CIRCLES;
+ }
+
+ public ClockCachePolicy(int maxCircles) {
+ Preconditions.checkState(maxCircles > 0, "Maximum number of clock rotation must be positive and got " + maxCircles);
+ this.maxCircles = maxCircles;
+ }
+
+ /**
+ * Signals to the policy the addition of a new entry to the cache. An entry come with a priority that can be used as
+ * a hint to replacement policy.
+ *
+ * @param buffer buffer to be cached
+ * @param priority the priority of cached element
+ */
+ @Override public void cache(LlapCacheableBuffer buffer, LowLevelCache.Priority priority) {
+ listLock.lock();
+ try {
+ clockHand = appendToCircularList(clockHand, buffer);
+ } finally {
+ listLock.unlock();
+ }
+ }
+
+ /**
+ * Appends new entry to the tail of circular list.
+ *
+ * @param head circular list head.
+ * @param buffer new entry to be added.
+ * @return the ring head.
+ */
+ private static LlapCacheableBuffer appendToCircularList(LlapCacheableBuffer head, LlapCacheableBuffer buffer) {
+ if (head == null) {
+ return linkToItSelf(buffer);
+ }
+ buffer.next = head;
+ buffer.prev = head.prev;
+ head.prev.next = buffer;
+ head.prev = buffer;
+ return head;
+ }
+
+ /**
+ * Links the entry to it self to form a ring.
+ *
+ * @param buffer input
+ * @return buffer
+ */
+ private static LlapCacheableBuffer linkToItSelf(LlapCacheableBuffer buffer) {
+ buffer.prev = buffer;
+ buffer.next = buffer;
+ return buffer;
+ }
+
+ @Override public void notifyLock(LlapCacheableBuffer buffer) {
+ buffer.setClockBit();
+ }
+
+ /**
+ * Notifies the policy that a buffer is unlocked after been used. This notification signals to the policy that an
+ * access to this page occurred.
+ *
+ * @param buffer buffer that just got unlocked after a read.
+ */
+ @Override public void notifyUnlock(LlapCacheableBuffer buffer) {
+
+ }
+
+ /**
+ * Signals to the policy that it has to evict some entries from the cache.
+ * Policy has to at least evict the amount memory requested.
+ * Not that is method will block until at least {@code memoryToReserve} bytes are evicted.
+ *
+ * @param memoryToReserve amount of bytes to be evicted
+ * @return actual amount of evicted bytes.
+ */
+ @Override public long evictSomeBlocks(long memoryToReserve) {
+ long evicted = 0;
+ if (clockHand == null) {
+ return evicted;
+ }
+ int fullClockRotation = 0;
+ listLock.lock();
+ try {
+ // ring tail is used to mark a clock circle
+ LlapCacheableBuffer ringTail = clockHand.prev;
+ // ring head is the current clock position that is under lock. Using local var under lock and updating actual
+ // clock position as soon we are done with looping
+ LlapCacheableBuffer currentClockHead = clockHand;
+
+ while (evicted < memoryToReserve && currentClockHead != null && fullClockRotation < maxCircles) {
+ if (ringTail == currentClockHead) {
+ fullClockRotation++;
+ }
+ if (currentClockHead.isClockBitSet()) {
+ // case the buffer getting second chance.
+ currentClockHead.unSetClockBit();
+ currentClockHead = currentClockHead.next;
+ } else {
+ // try to evict this victim
+ int invalidateFlag = currentClockHead.invalidate();
+ if (invalidateFlag == LlapCacheableBuffer.INVALIDATE_OK
+ || invalidateFlag == LlapCacheableBuffer.INVALIDATE_ALREADY_INVALID) {
+ if (invalidateFlag == LlapCacheableBuffer.INVALIDATE_OK) {
+ // case we are able to evict the buffer notify and account for it.
+ evictionListener.notifyEvicted(currentClockHead);
+ evicted += currentClockHead.getMemoryUsage();
+ }
+ LlapCacheableBuffer newHand = currentClockHead.next;
+ if (newHand == currentClockHead) {
+ // end of the ring we have looped, nothing else can be done...
+ currentClockHead = null;
+ break;
+ } else {
+ //remove it from the ring.
+ if (currentClockHead == ringTail) {
+ // we are about to remove the current ring tail thus we need to compute new tail
+ ringTail = ringTail.prev;
+ }
+ currentClockHead.prev.next = newHand;
+ newHand.prev = currentClockHead.prev;
+ currentClockHead = newHand;
+ }
+ } else if (invalidateFlag == LlapCacheableBuffer.INVALIDATE_FAILED) {
+ // can not be evicted case locked
+ currentClockHead = currentClockHead.next;
+ } else {
+ throw new IllegalStateException("Unknown invalidation flag " + invalidateFlag);
+ }
+ }
+ }
+ // done with clock rotations, update the current clock hand under lock.
+ clockHand = currentClockHead;
+ return evicted;
+ } finally {
+ listLock.unlock();
+ }
+ }
+
+ @Override public void setEvictionListener(EvictionListener listener) {
+ evictionListener = listener;
+ }
+
+ @Override public long purge() {
+ return evictSomeBlocks(Long.MAX_VALUE);
+ }
+
+ @Override public void debugDumpShort(StringBuilder sb) {
+ if (clockHand == null) {
+ sb.append("Clock is empty");
+ return;
+ }
+ listLock.lock();
+ try {
+ sb.append("Clock Status\n");
+ LlapCacheableBuffer currentClockHand = clockHand;
+ LlapCacheableBuffer lastElement = clockHand.prev;
+ while (currentClockHand != lastElement) {
+ sb.append(currentClockHand.toStringForCache());
+ currentClockHand = currentClockHand.next;
+ }
+ sb.append(lastElement.toStringForCache());
+ } finally {
+ listLock.unlock();
+ }
+ }
+
+ @VisibleForTesting protected Iterator<LlapCacheableBuffer> getIterator() {
Review comment:
Sure
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] b-slim commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
b-slim commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r396615084
##########
File path: llap-server/src/java/org/apache/hadoop/hive/llap/cache/ClockCachePolicy.java
##########
@@ -0,0 +1,264 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.hadoop.hive.llap.cache;
+
+import com.google.common.annotations.VisibleForTesting;
+import com.google.common.base.Preconditions;
+
+import javax.annotation.concurrent.GuardedBy;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+import java.util.concurrent.locks.Lock;
+import java.util.concurrent.locks.ReentrantLock;
+
+/**
+ * Clock eviction policy. Uses a simple circular list to keep a ring of current used buffers.
+ * New entries are added to tail of the clock hand AKA (clockHand.prev)
+ * Eviction start at the current clock hand following the next pointer.
+ *
+ */
+public class ClockCachePolicy implements LowLevelCachePolicy {
+
+ private static final int DEFAULT_MAX_CIRCLES = 5;
+
+ /**
+ * Lock to protect the state of the policy, used as mutex when modifying the circular linked list.
+ */
+ private final Lock listLock = new ReentrantLock();
+
+ /**
+ * The clock hand shared between threads thus made volatile, to ensure state when read outside of lock.
+ */
+ @GuardedBy("listLock")
+ private volatile LlapCacheableBuffer clockHand;
+
+ private EvictionListener evictionListener;
+ /**
+ * Max number of clock rotation before giving up on clock operation like eviction.
+ */
+ private final int maxCircles;
+
+ public ClockCachePolicy() {
+ maxCircles = DEFAULT_MAX_CIRCLES;
+ }
+
+ public ClockCachePolicy(int maxCircles) {
+ Preconditions.checkState(maxCircles > 0, "Maximum number of clock rotation must be positive and got " + maxCircles);
+ this.maxCircles = maxCircles;
+ }
+
+ /**
+ * Signals to the policy the addition of a new entry to the cache. An entry come with a priority that can be used as
+ * a hint to replacement policy.
+ *
+ * @param buffer buffer to be cached
+ * @param priority the priority of cached element
+ */
+ @Override public void cache(LlapCacheableBuffer buffer, LowLevelCache.Priority priority) {
+ listLock.lock();
+ try {
+ clockHand = appendToCircularList(clockHand, buffer);
+ } finally {
+ listLock.unlock();
+ }
+ }
+
+ /**
+ * Appends new entry to the tail of circular list.
+ *
+ * @param head circular list head.
+ * @param buffer new entry to be added.
+ * @return the ring head.
+ */
+ private static LlapCacheableBuffer appendToCircularList(LlapCacheableBuffer head, LlapCacheableBuffer buffer) {
+ if (head == null) {
+ return linkToItSelf(buffer);
+ }
+ buffer.next = head;
+ buffer.prev = head.prev;
+ head.prev.next = buffer;
+ head.prev = buffer;
+ return head;
+ }
+
+ /**
+ * Links the entry to it self to form a ring.
+ *
+ * @param buffer input
+ * @return buffer
+ */
+ private static LlapCacheableBuffer linkToItSelf(LlapCacheableBuffer buffer) {
+ buffer.prev = buffer;
+ buffer.next = buffer;
+ return buffer;
+ }
+
+ @Override public void notifyLock(LlapCacheableBuffer buffer) {
+ buffer.setClockBit();
+ }
+
+ /**
+ * Notifies the policy that a buffer is unlocked after been used. This notification signals to the policy that an
+ * access to this page occurred.
+ *
+ * @param buffer buffer that just got unlocked after a read.
+ */
+ @Override public void notifyUnlock(LlapCacheableBuffer buffer) {
+
+ }
+
+ /**
+ * Signals to the policy that it has to evict some entries from the cache.
+ * Policy has to at least evict the amount memory requested.
+ * Not that is method will block until at least {@code memoryToReserve} bytes are evicted.
+ *
+ * @param memoryToReserve amount of bytes to be evicted
+ * @return actual amount of evicted bytes.
+ */
+ @Override public long evictSomeBlocks(long memoryToReserve) {
+ long evicted = 0;
+ if (clockHand == null) {
+ return evicted;
+ }
+ int fullClockRotation = 0;
+ listLock.lock();
+ try {
+ // ring tail is used to mark a clock circle
+ LlapCacheableBuffer ringTail = clockHand.prev;
+ // ring head is the current clock position that is under lock. Using local var under lock and updating actual
+ // clock position as soon we are done with looping
+ LlapCacheableBuffer currentClockHead = clockHand;
+
+ while (evicted < memoryToReserve && currentClockHead != null && fullClockRotation < maxCircles) {
+ if (ringTail == currentClockHead) {
+ fullClockRotation++;
+ }
+ if (currentClockHead.isClockBitSet()) {
+ // case the buffer getting second chance.
+ currentClockHead.unSetClockBit();
+ currentClockHead = currentClockHead.next;
+ } else {
+ // try to evict this victim
+ int invalidateFlag = currentClockHead.invalidate();
+ if (invalidateFlag == LlapCacheableBuffer.INVALIDATE_OK
+ || invalidateFlag == LlapCacheableBuffer.INVALIDATE_ALREADY_INVALID) {
+ if (invalidateFlag == LlapCacheableBuffer.INVALIDATE_OK) {
+ // case we are able to evict the buffer notify and account for it.
+ evictionListener.notifyEvicted(currentClockHead);
+ evicted += currentClockHead.getMemoryUsage();
+ }
+ LlapCacheableBuffer newHand = currentClockHead.next;
+ if (newHand == currentClockHead) {
+ // end of the ring we have looped, nothing else can be done...
+ currentClockHead = null;
+ break;
+ } else {
+ //remove it from the ring.
+ if (currentClockHead == ringTail) {
+ // we are about to remove the current ring tail thus we need to compute new tail
+ ringTail = ringTail.prev;
+ }
+ currentClockHead.prev.next = newHand;
+ newHand.prev = currentClockHead.prev;
+ currentClockHead = newHand;
+ }
+ } else if (invalidateFlag == LlapCacheableBuffer.INVALIDATE_FAILED) {
+ // can not be evicted case locked
+ currentClockHead = currentClockHead.next;
+ } else {
+ throw new IllegalStateException("Unknown invalidation flag " + invalidateFlag);
+ }
+ }
+ }
+ // done with clock rotations, update the current clock hand under lock.
+ clockHand = currentClockHead;
+ return evicted;
+ } finally {
+ listLock.unlock();
+ }
+ }
+
+ @Override public void setEvictionListener(EvictionListener listener) {
+ evictionListener = listener;
+ }
+
+ @Override public long purge() {
+ return evictSomeBlocks(Long.MAX_VALUE);
+ }
+
+ @Override public void debugDumpShort(StringBuilder sb) {
+ if (clockHand == null) {
+ sb.append("Clock is empty");
+ return;
+ }
+ listLock.lock();
+ try {
+ sb.append("Clock Status\n");
+ LlapCacheableBuffer currentClockHand = clockHand;
+ LlapCacheableBuffer lastElement = clockHand.prev;
+ while (currentClockHand != lastElement) {
Review comment:
will fix it.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] b-slim commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
b-slim commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r396638475
##########
File path: llap-server/src/java/org/apache/hadoop/hive/llap/cache/ClockCachePolicy.java
##########
@@ -0,0 +1,264 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.hadoop.hive.llap.cache;
+
+import com.google.common.annotations.VisibleForTesting;
+import com.google.common.base.Preconditions;
+
+import javax.annotation.concurrent.GuardedBy;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+import java.util.concurrent.locks.Lock;
+import java.util.concurrent.locks.ReentrantLock;
+
+/**
+ * Clock eviction policy. Uses a simple circular list to keep a ring of current used buffers.
+ * New entries are added to tail of the clock hand AKA (clockHand.prev)
+ * Eviction start at the current clock hand following the next pointer.
+ *
+ */
+public class ClockCachePolicy implements LowLevelCachePolicy {
Review comment:
In theory i totally agree with you, although in practice i benchmarked with lock free FIFO implementations and I can not see anything that really moves the needle, but am up to work on second patch that makes this 100% lock free.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] odraese commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
odraese commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r395918743
##########
File path: llap-server/src/java/org/apache/hadoop/hive/llap/cache/ClockCachePolicy.java
##########
@@ -0,0 +1,264 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.hadoop.hive.llap.cache;
+
+import com.google.common.annotations.VisibleForTesting;
+import com.google.common.base.Preconditions;
+
+import javax.annotation.concurrent.GuardedBy;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+import java.util.concurrent.locks.Lock;
+import java.util.concurrent.locks.ReentrantLock;
+
+/**
+ * Clock eviction policy. Uses a simple circular list to keep a ring of current used buffers.
+ * New entries are added to tail of the clock hand AKA (clockHand.prev)
+ * Eviction start at the current clock hand following the next pointer.
+ *
+ */
+public class ClockCachePolicy implements LowLevelCachePolicy {
+
+ private static final int DEFAULT_MAX_CIRCLES = 5;
+
+ /**
+ * Lock to protect the state of the policy, used as mutex when modifying the circular linked list.
+ */
+ private final Lock listLock = new ReentrantLock();
+
+ /**
+ * The clock hand shared between threads thus made volatile, to ensure state when read outside of lock.
+ */
+ @GuardedBy("listLock")
+ private volatile LlapCacheableBuffer clockHand;
+
+ private EvictionListener evictionListener;
+ /**
+ * Max number of clock rotation before giving up on clock operation like eviction.
+ */
+ private final int maxCircles;
+
+ public ClockCachePolicy() {
+ maxCircles = DEFAULT_MAX_CIRCLES;
+ }
+
+ public ClockCachePolicy(int maxCircles) {
+ Preconditions.checkState(maxCircles > 0, "Maximum number of clock rotation must be positive and got " + maxCircles);
+ this.maxCircles = maxCircles;
+ }
+
+ /**
+ * Signals to the policy the addition of a new entry to the cache. An entry come with a priority that can be used as
+ * a hint to replacement policy.
+ *
+ * @param buffer buffer to be cached
+ * @param priority the priority of cached element
+ */
+ @Override public void cache(LlapCacheableBuffer buffer, LowLevelCache.Priority priority) {
+ listLock.lock();
+ try {
+ clockHand = appendToCircularList(clockHand, buffer);
+ } finally {
+ listLock.unlock();
+ }
+ }
+
+ /**
+ * Appends new entry to the tail of circular list.
+ *
+ * @param head circular list head.
+ * @param buffer new entry to be added.
+ * @return the ring head.
+ */
+ private static LlapCacheableBuffer appendToCircularList(LlapCacheableBuffer head, LlapCacheableBuffer buffer) {
+ if (head == null) {
+ return linkToItSelf(buffer);
+ }
+ buffer.next = head;
+ buffer.prev = head.prev;
+ head.prev.next = buffer;
+ head.prev = buffer;
+ return head;
+ }
+
+ /**
+ * Links the entry to it self to form a ring.
+ *
+ * @param buffer input
+ * @return buffer
+ */
+ private static LlapCacheableBuffer linkToItSelf(LlapCacheableBuffer buffer) {
+ buffer.prev = buffer;
+ buffer.next = buffer;
+ return buffer;
+ }
+
+ @Override public void notifyLock(LlapCacheableBuffer buffer) {
+ buffer.setClockBit();
+ }
+
+ /**
+ * Notifies the policy that a buffer is unlocked after been used. This notification signals to the policy that an
+ * access to this page occurred.
+ *
+ * @param buffer buffer that just got unlocked after a read.
+ */
+ @Override public void notifyUnlock(LlapCacheableBuffer buffer) {
+
+ }
+
+ /**
+ * Signals to the policy that it has to evict some entries from the cache.
+ * Policy has to at least evict the amount memory requested.
+ * Not that is method will block until at least {@code memoryToReserve} bytes are evicted.
+ *
+ * @param memoryToReserve amount of bytes to be evicted
+ * @return actual amount of evicted bytes.
+ */
+ @Override public long evictSomeBlocks(long memoryToReserve) {
+ long evicted = 0;
+ if (clockHand == null) {
+ return evicted;
+ }
+ int fullClockRotation = 0;
+ listLock.lock();
+ try {
+ // ring tail is used to mark a clock circle
+ LlapCacheableBuffer ringTail = clockHand.prev;
+ // ring head is the current clock position that is under lock. Using local var under lock and updating actual
+ // clock position as soon we are done with looping
+ LlapCacheableBuffer currentClockHead = clockHand;
Review comment:
with standard CLOCK implementation, there isn't really a need to differentiate between hand and current hand. the hand is simply moved forward on the search of the next entry which doesn't have the flag set.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] odraese commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
odraese commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r395925728
##########
File path: llap-server/src/java/org/apache/hadoop/hive/llap/cache/LowLevelLrfuCachePolicy.java
##########
@@ -138,7 +137,7 @@ public void notifyLock(LlapCacheableBuffer buffer) {
// a locked item in either, it will remove it from cache; when we unlock, we are going to
// put it back or update it, depending on whether this has happened. This should cause
// most of the expensive cache update work to happen in unlock, not blocking processing.
- if (buffer.indexInHeap != LlapCacheableBuffer.IN_LIST || !listLock.tryLock()) {
+ if (buffer.cacheAttribute == null || buffer.cacheAttribute.getIndex() != IN_LIST || !listLock.tryLock()) {
Review comment:
Question: what scenario can lead to a null cacheAttribute?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] b-slim commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
b-slim commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r401738771
##########
File path: llap-server/src/java/org/apache/hadoop/hive/llap/cache/ClockCachePolicy.java
##########
@@ -0,0 +1,313 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.hadoop.hive.llap.cache;
+
+import com.google.common.annotations.VisibleForTesting;
+import com.google.common.base.Preconditions;
+import org.apache.hadoop.hive.llap.io.metadata.MetadataCache;
+
+import javax.annotation.concurrent.GuardedBy;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+import java.util.concurrent.locks.Lock;
+import java.util.concurrent.locks.ReentrantLock;
+
+/**
+ * Clock eviction policy. Uses a simple circular list to keep a ring of current used buffers.
+ * New entries are added to tail of the clock hand AKA (clockHand.prev)
+ * Eviction start at the current clock hand following the next pointer.
+ *
+ */
+public class ClockCachePolicy implements LowLevelCachePolicy {
+
+ private static final int DEFAULT_MAX_CIRCLES = 5;
+
+ /**
+ * Lock to protect the state of the policy, used as mutex when modifying the circular linked list.
+ */
+ private final Lock listLock = new ReentrantLock();
+
+ /**
+ * The clock hand shared between threads thus made volatile, to ensure state when read outside of lock.
+ */
+ @GuardedBy("listLock")
+ private volatile LlapCacheableBuffer clockHand;
+
+ private EvictionListener evictionListener;
+ /**
+ * Max number of clock rotation before giving up on clock operation like eviction.
+ */
+ private final int maxCircles;
+
+ public ClockCachePolicy() {
+ maxCircles = DEFAULT_MAX_CIRCLES;
+ }
+
+ public ClockCachePolicy(int maxCircles) {
+ Preconditions.checkState(maxCircles > 0, "Maximum number of clock rotation must be positive and got " + maxCircles);
+ this.maxCircles = maxCircles;
+ }
+
+ /**
+ * Signals to the policy the addition of a new entry to the cache. An entry come with a priority that can be used as
+ * a hint to replacement policy.
+ *
+ * @param buffer buffer to be cached
+ * @param priority the priority of cached element
+ */
+ @Override public void cache(LlapCacheableBuffer buffer, LowLevelCache.Priority priority) {
+ listLock.lock();
+ try {
+ //noinspection NonAtomicOperationOnVolatileField
+ clockHand = appendToCircularList(clockHand, buffer);
+ } finally {
+ listLock.unlock();
+ }
+ }
+
+ /**
+ * Appends new entry to the tail of circular list.
+ *
+ * @param head circular list head.
+ * @param buffer new entry to be added.
+ * @return the ring head.
+ */
+ private static LlapCacheableBuffer appendToCircularList(LlapCacheableBuffer head, LlapCacheableBuffer buffer) {
+ if (head == null) {
+ return linkToItSelf(buffer);
+ }
+ buffer.next = head;
+ buffer.prev = head.prev;
+ head.prev.next = buffer;
+ head.prev = buffer;
+ return head;
+ }
+
+ /**
+ * Links the entry to it self to form a ring.
+ *
+ * @param buffer input
+ * @return buffer
+ */
+ private static LlapCacheableBuffer linkToItSelf(LlapCacheableBuffer buffer) {
Review comment:
Same as above those method are generic enough to be static
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] b-slim commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
b-slim commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r396581324
##########
File path: llap-server/src/java/org/apache/hadoop/hive/llap/cache/ClockCachePolicy.java
##########
@@ -0,0 +1,264 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.hadoop.hive.llap.cache;
+
+import com.google.common.annotations.VisibleForTesting;
+import com.google.common.base.Preconditions;
+
+import javax.annotation.concurrent.GuardedBy;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+import java.util.concurrent.locks.Lock;
+import java.util.concurrent.locks.ReentrantLock;
+
+/**
+ * Clock eviction policy. Uses a simple circular list to keep a ring of current used buffers.
+ * New entries are added to tail of the clock hand AKA (clockHand.prev)
+ * Eviction start at the current clock hand following the next pointer.
+ *
+ */
+public class ClockCachePolicy implements LowLevelCachePolicy {
+
+ private static final int DEFAULT_MAX_CIRCLES = 5;
+
+ /**
+ * Lock to protect the state of the policy, used as mutex when modifying the circular linked list.
+ */
+ private final Lock listLock = new ReentrantLock();
+
+ /**
+ * The clock hand shared between threads thus made volatile, to ensure state when read outside of lock.
+ */
+ @GuardedBy("listLock")
+ private volatile LlapCacheableBuffer clockHand;
+
+ private EvictionListener evictionListener;
+ /**
+ * Max number of clock rotation before giving up on clock operation like eviction.
+ */
+ private final int maxCircles;
+
+ public ClockCachePolicy() {
+ maxCircles = DEFAULT_MAX_CIRCLES;
+ }
+
+ public ClockCachePolicy(int maxCircles) {
+ Preconditions.checkState(maxCircles > 0, "Maximum number of clock rotation must be positive and got " + maxCircles);
+ this.maxCircles = maxCircles;
+ }
+
+ /**
+ * Signals to the policy the addition of a new entry to the cache. An entry come with a priority that can be used as
+ * a hint to replacement policy.
+ *
+ * @param buffer buffer to be cached
+ * @param priority the priority of cached element
+ */
+ @Override public void cache(LlapCacheableBuffer buffer, LowLevelCache.Priority priority) {
+ listLock.lock();
+ try {
+ clockHand = appendToCircularList(clockHand, buffer);
+ } finally {
+ listLock.unlock();
+ }
+ }
+
+ /**
+ * Appends new entry to the tail of circular list.
+ *
+ * @param head circular list head.
+ * @param buffer new entry to be added.
+ * @return the ring head.
+ */
+ private static LlapCacheableBuffer appendToCircularList(LlapCacheableBuffer head, LlapCacheableBuffer buffer) {
+ if (head == null) {
+ return linkToItSelf(buffer);
+ }
+ buffer.next = head;
+ buffer.prev = head.prev;
+ head.prev.next = buffer;
+ head.prev = buffer;
+ return head;
+ }
+
+ /**
+ * Links the entry to it self to form a ring.
+ *
+ * @param buffer input
+ * @return buffer
+ */
+ private static LlapCacheableBuffer linkToItSelf(LlapCacheableBuffer buffer) {
+ buffer.prev = buffer;
+ buffer.next = buffer;
+ return buffer;
+ }
+
+ @Override public void notifyLock(LlapCacheableBuffer buffer) {
+ buffer.setClockBit();
+ }
+
+ /**
+ * Notifies the policy that a buffer is unlocked after been used. This notification signals to the policy that an
+ * access to this page occurred.
+ *
+ * @param buffer buffer that just got unlocked after a read.
+ */
+ @Override public void notifyUnlock(LlapCacheableBuffer buffer) {
+
+ }
+
+ /**
+ * Signals to the policy that it has to evict some entries from the cache.
+ * Policy has to at least evict the amount memory requested.
+ * Not that is method will block until at least {@code memoryToReserve} bytes are evicted.
+ *
+ * @param memoryToReserve amount of bytes to be evicted
+ * @return actual amount of evicted bytes.
+ */
+ @Override public long evictSomeBlocks(long memoryToReserve) {
+ long evicted = 0;
+ if (clockHand == null) {
+ return evicted;
+ }
+ int fullClockRotation = 0;
+ listLock.lock();
+ try {
+ // ring tail is used to mark a clock circle
+ LlapCacheableBuffer ringTail = clockHand.prev;
+ // ring head is the current clock position that is under lock. Using local var under lock and updating actual
+ // clock position as soon we are done with looping
+ LlapCacheableBuffer currentClockHead = clockHand;
+
+ while (evicted < memoryToReserve && currentClockHead != null && fullClockRotation < maxCircles) {
Review comment:
good point.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] b-slim commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
b-slim commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r396567666
##########
File path: llap-server/src/java/org/apache/hadoop/hive/llap/cache/LlapAllocatorBuffer.java
##########
@@ -80,9 +80,32 @@ int tryIncRef() {
return incRefInternal(false);
}
+ /**
Review comment:
I will file a jira for that and do it in second iteration what you think ?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] odraese commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
odraese commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r395923314
##########
File path: llap-server/src/java/org/apache/hadoop/hive/llap/cache/LlapCacheableBuffer.java
##########
@@ -26,39 +26,71 @@
* using a real programming language.
*/
public abstract class LlapCacheableBuffer {
- protected static final int IN_LIST = -2, NOT_IN_CACHE = -1;
-
- /** Priority for cache policy (should be pretty universal). */
- public double priority;
- /** Last priority update time for cache policy (should be pretty universal). */
- public long lastUpdate = -1;
+ public static final int INVALIDATE_OK = 0, INVALIDATE_FAILED = 1, INVALIDATE_ALREADY_INVALID = 2;
Review comment:
Question: what was the reason for negating the return codes. Maybe even more important: why isn't this an enum?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] odraese commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
odraese commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r395925936
##########
File path: llap-server/src/java/org/apache/hadoop/hive/llap/cache/LowLevelLrfuCachePolicy.java
##########
@@ -189,26 +188,33 @@ private void doNotifyUnderHeapLock(int count, LlapCacheableBuffer[] cacheableBuf
LlapIoImpl.CACHE_LOGGER.trace("Touching {} at {}", buffer, time);
}
// First, update buffer priority - we have just been using it.
- buffer.priority = (buffer.lastUpdate == -1) ? F0
- : touchPriority(time, buffer.lastUpdate, buffer.priority);
- buffer.lastUpdate = time;
+ LrfuCacheAttribute lrfuCacheAttribute = (LrfuCacheAttribute) buffer.cacheAttribute;
+ if (lrfuCacheAttribute == null) {
+ //This should not happen but it is possible that adding the attribute on cache call happens after this call
+ lrfuCacheAttribute = new LrfuCacheAttribute(F0, time);
+ buffer.cacheAttribute = lrfuCacheAttribute;
+ } else {
+ lrfuCacheAttribute.lastUpdate = time;
+ lrfuCacheAttribute.priority = touchPriority(time, lrfuCacheAttribute.lastUpdate, lrfuCacheAttribute.priority);
+ }
+
// Then, if the buffer was in the list, remove it.
- if (buffer.indexInHeap == LlapCacheableBuffer.IN_LIST) {
+ if (lrfuCacheAttribute.indexInHeap == IN_LIST) {
listLock.lock();
removeFromListAndUnlock(buffer);
}
// The only concurrent change that can happen when we hold the heap lock is list removal;
// we have just ensured the item is not in the list, so we have a definite state now.
- if (buffer.indexInHeap >= 0) {
+ if (lrfuCacheAttribute.indexInHeap >= 0) {
// The buffer has lived in the heap all along. Restore heap property.
heapifyDownUnderLock(buffer, time);
} else if (heapSize == heap.length) {
// The buffer is not in the (full) heap. Demote the top item of the heap into the list.
LlapCacheableBuffer demoted = heap[0];
listLock.lock();
try {
- assert demoted.indexInHeap == 0; // Noone could have moved it, we have the heap lock.
- demoted.indexInHeap = LlapCacheableBuffer.IN_LIST;
+ //assert demoted.indexInHeap == 0; // Noone could have moved it, we have the heap lock.
Review comment:
why remove the assert?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] odraese commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
odraese commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r400361816
##########
File path: llap-server/src/java/org/apache/hadoop/hive/llap/cache/LowLevelCachePolicy.java
##########
@@ -26,6 +28,32 @@
*/
public interface LowLevelCachePolicy extends LlapIoDebugDump {
+ static LowLevelCachePolicy provideFromConf(Configuration conf) {
+ final long totalMemorySize = HiveConf.getSizeVar(conf, HiveConf.ConfVars.LLAP_IO_MEMORY_MAX_SIZE);
+ final int minAllocSize = (int) HiveConf.getSizeVar(conf, HiveConf.ConfVars.LLAP_ALLOCATOR_MIN_ALLOC);
+ String policyName = HiveConf.getVar(conf,HiveConf.ConfVars.LLAP_IO_CACHE_STRATEGY);
Review comment:
I meant the value, so that FiFo is the same as fifo
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] b-slim commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
b-slim commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r396620424
##########
File path: llap-server/src/java/org/apache/hadoop/hive/llap/cache/LowLevelLrfuCachePolicy.java
##########
@@ -43,6 +43,8 @@
* Additionally, buffer locking has to be handled (locked buffer cannot be evicted).
*/
public final class LowLevelLrfuCachePolicy implements LowLevelCachePolicy {
+ public static final int IN_LIST = -2;
Review comment:
was there before, i can do that in a follow up.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] odraese commented on a change in pull request #944:
[Hive-22760] Adding Clock based eviction strategy.
Posted by GitBox <gi...@apache.org>.
odraese commented on a change in pull request #944: [Hive-22760] Adding Clock based eviction strategy.
URL: https://github.com/apache/hive/pull/944#discussion_r395928629
##########
File path: llap-server/src/java/org/apache/hadoop/hive/llap/io/metadata/MetadataCache.java
##########
@@ -406,7 +405,8 @@ private boolean lockBuffer(LlapBufferOrBuffers buffers, boolean doNotifyPolicy)
for (int i = 0; i < bufferArray.length; ++i) {
if (lockOneBuffer(bufferArray[i], doNotifyPolicy)) continue;
for (int j = 0; j < i; ++j) {
- unlockSingleBuffer(buffer, true);
+ //@TODO this is a bug by it self.
Review comment:
I would suggest to either fix the bug while you're at it or to add more documentation to this comment, why this is a bug.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org