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: [email protected] With regards, Apache Git Services --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
