This is an automated email from the ASF dual-hosted git repository.
albumenj pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/dubbo.git
The following commit(s) were added to refs/heads/master by this push:
new cd6b63d92d Revert "[LFUCache]Add frequency of key and delete the empty
cache queue (#7967)" (#10086)
cd6b63d92d is described below
commit cd6b63d92d21bd3cd568ab1216a9d7ab8cf58ca2
Author: zhaoguhong <[email protected]>
AuthorDate: Wed Jun 29 09:28:56 2022 +0800
Revert "[LFUCache]Add frequency of key and delete the empty cache queue
(#7967)" (#10086)
This reverts commit e8581fd7ff93fd8d579e24f0d45f131bff87cac9.
---
.../org/apache/dubbo/common/utils/LFUCache.java | 214 ++++-----------------
.../apache/dubbo/common/utils/LFUCacheTest.java | 30 ---
2 files changed, 35 insertions(+), 209 deletions(-)
diff --git
a/dubbo-common/src/main/java/org/apache/dubbo/common/utils/LFUCache.java
b/dubbo-common/src/main/java/org/apache/dubbo/common/utils/LFUCache.java
index e584dc4b96..8230bd6886 100644
--- a/dubbo-common/src/main/java/org/apache/dubbo/common/utils/LFUCache.java
+++ b/dubbo-common/src/main/java/org/apache/dubbo/common/utils/LFUCache.java
@@ -16,35 +16,26 @@
*/
package org.apache.dubbo.common.utils;
-import java.util.ArrayList;
import java.util.HashMap;
-import java.util.List;
import java.util.Map;
-import java.util.Set;
-import java.util.TreeMap;
-import java.util.concurrent.atomic.AtomicInteger;
-import java.util.concurrent.atomic.AtomicLong;
-import java.util.concurrent.locks.ReentrantReadWriteLock;
+import java.util.concurrent.locks.ReentrantLock;
public class LFUCache<K, V> {
private Map<K, CacheNode<K, V>> map;
- private Map<Long, CacheDeque<K, V>> freqTable;
+ private CacheDeque<K, V>[] freqTable;
private final int capacity;
private int evictionCount;
private int curSize = 0;
- private long removeFreqEntryTimeout;
- private final ReentrantReadWriteLock lock = new ReentrantReadWriteLock();
+ private final ReentrantLock lock = new ReentrantLock();
private static final int DEFAULT_INITIAL_CAPACITY = 1000;
private static final float DEFAULT_EVICTION_FACTOR = 0.75f;
- private static final long DEFAULT_REMOVE_FREQ_TABLE_TIME_OUT = 1800000L;
-
public LFUCache() {
- this(DEFAULT_INITIAL_CAPACITY, DEFAULT_EVICTION_FACTOR,
DEFAULT_REMOVE_FREQ_TABLE_TIME_OUT);
+ this(DEFAULT_INITIAL_CAPACITY, DEFAULT_EVICTION_FACTOR);
}
/**
@@ -69,36 +60,14 @@ public class LFUCache<K, V> {
this.capacity = maxCapacity;
this.evictionCount = (int) (capacity * evictionFactor);
this.map = new HashMap<>();
- this.freqTable = new TreeMap<>(Long::compareTo);
- freqTable.put(1L, new CacheDeque<>());
- }
-
- /**
- * Constructs and initializes cache with specified capacity and eviction
- * factor. Unacceptable parameter values followed with
- * {@link IllegalArgumentException}.
- *
- * @param maxCapacity cache max capacity
- * @param evictionFactor cache proceedEviction factor
- * @param removeFreqEntryTimeout cache queue remove timeout
- */
- @SuppressWarnings("unchecked")
- public LFUCache(final int maxCapacity, final float evictionFactor, final
long removeFreqEntryTimeout) {
- if (maxCapacity <= 0) {
- throw new IllegalArgumentException("Illegal initial capacity: " +
- maxCapacity);
+ this.freqTable = new CacheDeque[capacity + 1];
+ for (int i = 0; i <= capacity; i++) {
+ freqTable[i] = new CacheDeque<>();
}
- boolean factorInRange = evictionFactor <= 1 && evictionFactor > 0;
- if (!factorInRange || Float.isNaN(evictionFactor)) {
- throw new IllegalArgumentException("Illegal eviction factor value:"
- + evictionFactor);
+ for (int i = 0; i < capacity; i++) {
+ freqTable[i].nextDeque = freqTable[i + 1];
}
- this.capacity = maxCapacity;
- this.evictionCount = (int) (capacity * evictionFactor);
- this.removeFreqEntryTimeout = removeFreqEntryTimeout;
- this.map = new HashMap<>();
- this.freqTable = new TreeMap<>(Long::compareTo);
- freqTable.put(1L, new CacheDeque<>());
+ freqTable[capacity].nextDeque = freqTable[capacity];
}
public int getCapacity() {
@@ -107,31 +76,31 @@ public class LFUCache<K, V> {
public V put(final K key, final V value) {
CacheNode<K, V> node;
- lock.writeLock().lock();
+ lock.lock();
try {
node = map.get(key);
if (node != null) {
CacheNode.withdrawNode(node);
node.value = value;
- moveToNextFreqQueue(node.incrFreq(), node);
+ freqTable[0].addLastNode(node);
map.put(key, node);
} else {
- if (curSize + 1 > capacity) {
- proceedEviction();
- }
- node = freqTable.get(1L).addLast(key, value);
+ node = freqTable[0].addLast(key, value);
map.put(key, node);
curSize++;
+ if (curSize > capacity) {
+ proceedEviction();
+ }
}
} finally {
- lock.writeLock().unlock();
+ lock.unlock();
}
return node.value;
}
public V remove(final K key) {
CacheNode<K, V> node = null;
- lock.writeLock().lock();
+ lock.lock();
try {
if (map.containsKey(key)) {
node = map.remove(key);
@@ -141,96 +110,26 @@ public class LFUCache<K, V> {
curSize--;
}
} finally {
- lock.writeLock().unlock();
+ lock.unlock();
}
return (node != null) ? node.value : null;
}
public V get(final K key) {
CacheNode<K, V> node = null;
- lock.writeLock().lock();
+ lock.lock();
try {
if (map.containsKey(key)) {
node = map.get(key);
CacheNode.withdrawNode(node);
- moveToNextFreqQueue(node.incrFreq(), node);
+ node.owner.nextDeque.addLastNode(node);
}
} finally {
- lock.writeLock().unlock();
+ lock.unlock();
}
return (node != null) ? node.value : null;
}
- /**
- * Returns size of the freq table
- *
- * @return size
- */
- public int getFreqTableSize(){
- return freqTable.size();
- }
-
- /**
- * Returns freq of the element
- *
- * @return freq
- */
- public Long getFreq(final K key) {
- CacheNode<K, V> node = null;
- lock.readLock().lock();
- try {
- if (map.containsKey(key)) {
- node = map.get(key);
- return node.getFreq();
- }
- } finally {
- lock.readLock().unlock();
- }
- return null;
- }
-
- /**
- * Returns node list of this frequency
- *
- * @return node list
- */
- private List<CacheNode<K,V>> getFreqList(final Long freq){
- if(freq == null){
- return null;
- }
- lock.writeLock().lock();
- try {
- if (freqTable.containsKey(freq)) {
- if(freqTable.get(freq).nodeMap.size() > 0){
- return new
ArrayList<>(freqTable.get(freq).nodeMap.values());
- }
- }
- } finally {
- lock.writeLock().unlock();
- }
- return null;
- }
-
- /**
- * Returns node list's size of this frequency
- *
- * @return node list's size
- */
- public int getFreqListSize(final Long freq){
- if(freq == null){
- return 0;
- }
- lock.writeLock().lock();
- try {
- if (freqTable.containsKey(freq)) {
- return freqTable.get(freq).size.get();
- }
- } finally {
- lock.writeLock().unlock();
- }
- return 0;
- }
-
/**
* Evicts less frequently used elements corresponding to eviction factor,
* specified at instantiation step.
@@ -238,40 +137,24 @@ public class LFUCache<K, V> {
* @return number of evicted elements
*/
private int proceedEviction() {
- int targetSize = capacity - evictionCount - 1;
+ int targetSize = capacity - evictionCount;
int evictedElements = 0;
- Set<Long> freqKeys = freqTable.keySet();
- boolean evictionEnd = false;
- for (Long freq : freqKeys) {
- CacheDeque<K, V> q = freqTable.get(freq);
+
+ FREQ_TABLE_ITER_LOOP:
+ for (int i = 0; i <= capacity; i++) {
CacheNode<K, V> node;
- if(!evictionEnd) {
- while (!q.isEmpty()) {
- node = q.pollFirst();
- remove(node.key);
- evictedElements++;
- if (targetSize >= curSize) {
- evictionEnd = true;
- break;
- }
+ while (!freqTable[i].isEmpty()) {
+ node = freqTable[i].pollFirst();
+ remove(node.key);
+ if (targetSize >= curSize) {
+ break FREQ_TABLE_ITER_LOOP;
}
- }
- // If the queue is empty for a long time, delete the queue
- if (removeFreqEntryTimeout > 0 && freq > 1 && q.isEmpty() &&
(System.currentTimeMillis() - q.getLastReqTime()) >= removeFreqEntryTimeout) {
- freqTable.remove(freq);
+ evictedElements++;
}
}
return evictedElements;
}
- /**
- * Move the node to the next cache queue
- */
- private void moveToNextFreqQueue(long newFreq, CacheNode<K, V> node){
- freqTable.putIfAbsent(newFreq, new CacheDeque<>());
- freqTable.get(newFreq).addLastNode(node);
- }
-
/**
* Returns cache current size.
*
@@ -287,7 +170,6 @@ public class LFUCache<K, V> {
CacheNode<K, V> next;
K key;
V value;
- volatile AtomicLong freq = new AtomicLong(1);
CacheDeque<K, V> owner;
CacheNode() {
@@ -298,14 +180,6 @@ public class LFUCache<K, V> {
this.value = value;
}
- long incrFreq(){
- return freq.incrementAndGet();
- }
-
- long getFreq(){
- return freq.get();
- }
-
/**
* This method takes specified node and reattaches it neighbors nodes
* links to each other, so specified node will no longer tied with
them.
@@ -322,8 +196,6 @@ public class LFUCache<K, V> {
node.prev.next = node.next;
if (node.next != null) {
node.next.prev = node.prev;
- node.owner.nodeMap.remove(node.key);
- node.owner.size.decrementAndGet();
}
}
return node;
@@ -344,9 +216,8 @@ public class LFUCache<K, V> {
CacheNode<K, V> last;
CacheNode<K, V> first;
- Map<K, CacheNode<K, V>> nodeMap;
- long lastReqTime;
- volatile AtomicInteger size = new AtomicInteger(0);
+ CacheDeque<K, V> nextDeque;
+
/**
* Constructs list and initializes last and first pointers.
*/
@@ -355,7 +226,6 @@ public class LFUCache<K, V> {
first = new CacheNode<>();
last.next = first;
first.prev = last;
- nodeMap = new HashMap<>();
}
/**
@@ -373,8 +243,6 @@ public class LFUCache<K, V> {
node.prev = last;
node.next.prev = node;
last.next = node;
- this.setLastReqTime(System.currentTimeMillis());
- this.size.incrementAndGet();
return node;
}
@@ -384,9 +252,6 @@ public class LFUCache<K, V> {
node.prev = last;
node.next.prev = node;
last.next = node;
- this.setLastReqTime(System.currentTimeMillis());
- this.nodeMap.put(node.key, node);
- this.size.incrementAndGet();
return node;
}
@@ -403,8 +268,6 @@ public class LFUCache<K, V> {
first.prev.next = first;
node.prev = null;
node.next = null;
- this.nodeMap.remove(node.key);
- this.size.decrementAndGet();
}
return node;
}
@@ -418,13 +281,6 @@ public class LFUCache<K, V> {
return last.next == first;
}
- public CacheDeque<K, V> setLastReqTime(long lastReqTime) {
- this.lastReqTime = lastReqTime;
- return this;
- }
-
- public long getLastReqTime() {
- return lastReqTime;
- }
}
+
}
\ No newline at end of file
diff --git
a/dubbo-common/src/test/java/org/apache/dubbo/common/utils/LFUCacheTest.java
b/dubbo-common/src/test/java/org/apache/dubbo/common/utils/LFUCacheTest.java
index 8d86261ce3..d7a725089e 100644
--- a/dubbo-common/src/test/java/org/apache/dubbo/common/utils/LFUCacheTest.java
+++ b/dubbo-common/src/test/java/org/apache/dubbo/common/utils/LFUCacheTest.java
@@ -73,36 +73,6 @@ public class LFUCacheTest {
assertThat(cache.getCapacity(), equalTo(1000));
}
- @Test
- public void testGetFreq() throws Exception {
- LFUCache<String, Integer> cache = new LFUCache<>();
- cache.put("one", 1);
- cache.put("two", 2);
- cache.put("two", 2);
- assertThat(cache.getFreq("one"), equalTo(1L));
- assertThat(cache.getFreq("two"), equalTo(2L));
- }
-
- @Test
- public void testRemoveEmptyCacheQueue() throws Exception {
- LFUCache<String, Integer> cache = new LFUCache<>(2, 0.5f, 1000);
- cache.put("one", 1);
- cache.put("two", 2);
- assertThat(cache.getFreqTableSize(), equalTo(1));
- cache.put("two", 2);
- assertThat(cache.getFreqTableSize(), equalTo(2));
- cache.remove("two");
- cache.put("three",3);
- cache.put("four", 4);
- assertThat(cache.getSize(), equalTo(1));
- assertThat(cache.getFreqTableSize(), equalTo(2));
- Thread.sleep(1000);
- cache.put("five",5);
- cache.put("six", 6);
- assertThat(cache.getSize(), equalTo(1));
- assertThat(cache.getFreqTableSize(), equalTo(1));
- }
-
@Test
public void testErrorConstructArguments() throws IOException {
Assertions.assertThrows(IllegalArgumentException.class, () -> new
LFUCache<>(0, 0.8f));
