You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@dubbo.apache.org by al...@apache.org on 2021/06/07 07:16:40 UTC
[dubbo] branch master updated: [LFUCache]Add frequency of key and
delete the empty cache queue (#7967)
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 e8581fd [LFUCache]Add frequency of key and delete the empty cache queue (#7967)
e8581fd is described below
commit e8581fd7ff93fd8d579e24f0d45f131bff87cac9
Author: maizi <36...@qq.com>
AuthorDate: Mon Jun 7 15:16:23 2021 +0800
[LFUCache]Add frequency of key and delete the empty cache queue (#7967)
* 1.Change the freqTable from Array to TreeMap
2.Add a timeout field to determine if an empty queue can be deleted
* 1.Change the freqTable from Array to TreeMap
2.Add a timeout field to determine if an empty queue can be deleted
3.Add a method to get frequency of the key
* 1.Change the freqTable from Array to TreeMap
2.Add a timeout field to determine if an empty queue can be deleted
3.Add a method to get frequency of the key
* remove unused imports
Co-authored-by: liwenliang <li...@weidian.com>
---
.../org/apache/dubbo/common/utils/LFUCache.java | 214 +++++++++++++++++----
.../apache/dubbo/common/utils/LFUCacheTest.java | 30 +++
2 files changed, 209 insertions(+), 35 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 8230bd6..e584dc4 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,26 +16,35 @@
*/
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.concurrent.locks.ReentrantLock;
+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;
public class LFUCache<K, V> {
private Map<K, CacheNode<K, V>> map;
- private CacheDeque<K, V>[] freqTable;
+ private Map<Long, CacheDeque<K, V>> freqTable;
private final int capacity;
private int evictionCount;
private int curSize = 0;
+ private long removeFreqEntryTimeout;
- private final ReentrantLock lock = new ReentrantLock();
+ private final ReentrantReadWriteLock lock = new ReentrantReadWriteLock();
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);
+ this(DEFAULT_INITIAL_CAPACITY, DEFAULT_EVICTION_FACTOR, DEFAULT_REMOVE_FREQ_TABLE_TIME_OUT);
}
/**
@@ -60,14 +69,36 @@ public class LFUCache<K, V> {
this.capacity = maxCapacity;
this.evictionCount = (int) (capacity * evictionFactor);
this.map = new HashMap<>();
- this.freqTable = new CacheDeque[capacity + 1];
- for (int i = 0; i <= capacity; i++) {
- freqTable[i] = new CacheDeque<>();
+ 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);
}
- for (int i = 0; i < capacity; i++) {
- freqTable[i].nextDeque = freqTable[i + 1];
+ boolean factorInRange = evictionFactor <= 1 && evictionFactor > 0;
+ if (!factorInRange || Float.isNaN(evictionFactor)) {
+ throw new IllegalArgumentException("Illegal eviction factor value:"
+ + evictionFactor);
}
- freqTable[capacity].nextDeque = freqTable[capacity];
+ 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<>());
}
public int getCapacity() {
@@ -76,31 +107,31 @@ public class LFUCache<K, V> {
public V put(final K key, final V value) {
CacheNode<K, V> node;
- lock.lock();
+ lock.writeLock().lock();
try {
node = map.get(key);
if (node != null) {
CacheNode.withdrawNode(node);
node.value = value;
- freqTable[0].addLastNode(node);
+ moveToNextFreqQueue(node.incrFreq(), node);
map.put(key, node);
} else {
- node = freqTable[0].addLast(key, value);
- map.put(key, node);
- curSize++;
- if (curSize > capacity) {
+ if (curSize + 1 > capacity) {
proceedEviction();
}
+ node = freqTable.get(1L).addLast(key, value);
+ map.put(key, node);
+ curSize++;
}
} finally {
- lock.unlock();
+ lock.writeLock().unlock();
}
return node.value;
}
public V remove(final K key) {
CacheNode<K, V> node = null;
- lock.lock();
+ lock.writeLock().lock();
try {
if (map.containsKey(key)) {
node = map.remove(key);
@@ -110,52 +141,138 @@ public class LFUCache<K, V> {
curSize--;
}
} finally {
- lock.unlock();
+ lock.writeLock().unlock();
}
return (node != null) ? node.value : null;
}
public V get(final K key) {
CacheNode<K, V> node = null;
- lock.lock();
+ lock.writeLock().lock();
try {
if (map.containsKey(key)) {
node = map.get(key);
CacheNode.withdrawNode(node);
- node.owner.nextDeque.addLastNode(node);
+ moveToNextFreqQueue(node.incrFreq(), node);
}
} finally {
- lock.unlock();
+ lock.writeLock().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.
*
* @return number of evicted elements
*/
private int proceedEviction() {
- int targetSize = capacity - evictionCount;
+ int targetSize = capacity - evictionCount - 1;
int evictedElements = 0;
-
- FREQ_TABLE_ITER_LOOP:
- for (int i = 0; i <= capacity; i++) {
+ Set<Long> freqKeys = freqTable.keySet();
+ boolean evictionEnd = false;
+ for (Long freq : freqKeys) {
+ CacheDeque<K, V> q = freqTable.get(freq);
CacheNode<K, V> node;
- while (!freqTable[i].isEmpty()) {
- node = freqTable[i].pollFirst();
- remove(node.key);
- if (targetSize >= curSize) {
- break FREQ_TABLE_ITER_LOOP;
+ if(!evictionEnd) {
+ while (!q.isEmpty()) {
+ node = q.pollFirst();
+ remove(node.key);
+ evictedElements++;
+ if (targetSize >= curSize) {
+ evictionEnd = true;
+ break;
+ }
}
- evictedElements++;
+ }
+ // 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);
}
}
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.
*
* @return cache size
@@ -170,6 +287,7 @@ public class LFUCache<K, V> {
CacheNode<K, V> next;
K key;
V value;
+ volatile AtomicLong freq = new AtomicLong(1);
CacheDeque<K, V> owner;
CacheNode() {
@@ -180,6 +298,14 @@ 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.
@@ -196,6 +322,8 @@ 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;
@@ -216,8 +344,9 @@ public class LFUCache<K, V> {
CacheNode<K, V> last;
CacheNode<K, V> first;
- CacheDeque<K, V> nextDeque;
-
+ Map<K, CacheNode<K, V>> nodeMap;
+ long lastReqTime;
+ volatile AtomicInteger size = new AtomicInteger(0);
/**
* Constructs list and initializes last and first pointers.
*/
@@ -226,6 +355,7 @@ public class LFUCache<K, V> {
first = new CacheNode<>();
last.next = first;
first.prev = last;
+ nodeMap = new HashMap<>();
}
/**
@@ -243,6 +373,8 @@ public class LFUCache<K, V> {
node.prev = last;
node.next.prev = node;
last.next = node;
+ this.setLastReqTime(System.currentTimeMillis());
+ this.size.incrementAndGet();
return node;
}
@@ -252,6 +384,9 @@ 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;
}
@@ -268,6 +403,8 @@ 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;
}
@@ -281,6 +418,13 @@ 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 d7a7250..8d86261 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
@@ -74,6 +74,36 @@ public class LFUCacheTest {
}
@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));
Assertions.assertThrows(IllegalArgumentException.class, () -> new LFUCache<>(-1, 0.8f));