Zakelly commented on code in PR #26237: URL: https://github.com/apache/flink/pull/26237#discussion_r1977020363
########## flink-state-backends/flink-statebackend-forst/src/main/java/org/apache/flink/state/forst/fs/cache/DoubleListLru.java: ########## @@ -0,0 +1,442 @@ +/* + * 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.flink.state.forst.fs.cache; + +import org.apache.flink.annotation.VisibleForTesting; +import org.apache.flink.api.java.tuple.Tuple2; + +import java.util.HashMap; +import java.util.Iterator; +import java.util.NoSuchElementException; + +/** + * A double link LRU (Least Recently Used) cache implementation. This cache maintains two linked + * lists to manage the cache entries. The first list contains the most recently used entries, and + * the second list contains the less recently used entries. The cache also maintains a middle + * pointer to efficiently manage the entries. No thread-safe guarantees are provided. + * + * @param <K> the type of keys maintained by this cache + * @param <V> the type of mapped values + */ +public abstract class DoubleListLru<K, V> implements Iterable<Tuple2<K, V>> { + + class Node { + K key; + V value; + Node prev; + Node next; + boolean isBeforeMiddle; + + Node(K key, V value) { + this.key = key; + this.value = value; + this.isBeforeMiddle = false; + } + } + + private Node head; + private Node tail; + private Node middle; + private int size; + private int secondSize; + private final HashMap<K, Node> map; + + public DoubleListLru() { + this.head = null; + this.tail = null; + this.middle = null; + this.size = 0; + this.map = new HashMap<>(); + } + + // ------------------- + // Hook methods + // ------------------- + + /** + * Checks if it is safe to add a value to the first list. Will be called before adding a value + * to the first list. + * + * @param value the value to be added to the first list + * @return true if it is safe to add the value to the first list, false otherwise. + */ + abstract boolean isSafeToAddFirst(V value); + + /** + * Hook method called when a new node is created. + * + * @param value the value of the new node + * @param n the new node + */ + abstract void newNodeCreated(V value, Node n); + + /** + * Hook method called when a value is added to the first list. + * + * @param value the value added to the first list + */ + abstract void addedToFirst(V value); + + /** + * Hook method called when a value is added to the second list. + * + * @param value the value added to the second list + */ + abstract void addedToSecond(V value); + + /** + * Hook method called when a value is removed from the first list. + * + * @param value the value removed from the first list + */ + abstract void removedFromFirst(V value); + + /** + * Hook method called when a value is removed from the second list. + * + * @param value the value removed from the second list + */ + abstract void removedFromSecond(V value); + + /** + * Hook method called when a value is moved to the first list. + * + * @param value the value moved to the first list + */ + abstract void movedToFirst(V value); + + /** + * Hook method called when a value is moved to the second list. + * + * @param value the value moved to the second list + */ + abstract void movedToSecond(V value); + + /** + * Hook method called when a node is accessed in the second list. + * + * @param value the value of the accessed node + * @return true if the node should be promoted to the first list, false otherwise + */ + abstract boolean nodeAccessedAtSecond(V value); + + /** + * Hook method called when a value is promoted to the first list. + * + * @param value the promoted value + */ + abstract void promotedToFirst(V value); + + /** + * Adds a new entry to the front of the cache. + * + * @param key the key of the entry + * @param value the value of the entry + */ + public void addFirst(K key, V value) { + if (!isSafeToAddFirst(value)) { + addSecond(key, value); + return; + } + Node newNode = new Node(key, value); + newNodeCreated(value, newNode); + map.put(key, newNode); Review Comment: No we don't support different value for one key. the cache key is from the source path of MappingEntry, so IIUC in rescaling scenario, we still have one-to-one mapping from key to value here. -- 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. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
