You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@dubbo.apache.org by li...@apache.org on 2020/04/03 02:30:21 UTC
[dubbo] branch master updated: lfu cache (#5734)
This is an automated email from the ASF dual-hosted git repository.
liujun 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 4dd5a0d lfu cache (#5734)
4dd5a0d is described below
commit 4dd5a0db57dec56716a7da146661866be5d05f77
Author: myPrecious <Mo...@users.noreply.github.com>
AuthorDate: Fri Apr 3 10:30:00 2020 +0800
lfu cache (#5734)
fixes #5130
---
.../org/apache/dubbo/common/utils/LFUCache.java | 287 +++++++++++++++++++++
.../apache/dubbo/common/utils/LFUCacheTest.java | 72 ++++++
.../apache/dubbo/cache/support/lfu/LfuCache.java | 80 ++++++
.../dubbo/cache/support/lfu/LfuCacheFactory.java | 43 +++
4 files changed, 482 insertions(+)
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
new file mode 100644
index 0000000..a4c3732
--- /dev/null
+++ b/dubbo-common/src/main/java/org/apache/dubbo/common/utils/LFUCache.java
@@ -0,0 +1,287 @@
+/*
+ * 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.dubbo.common.utils;
+
+import java.util.HashMap;
+import java.util.Map;
+import java.util.concurrent.locks.ReentrantLock;
+
+public class LFUCache<K, V> {
+
+ private Map<K, CacheNode<K, V>> map;
+ private CacheDeque<K, V>[] freqTable;
+
+ private final int capacity;
+ private int evictionCount;
+ private int curSize = 0;
+
+ private final ReentrantLock lock = new ReentrantLock();
+ private static final int DEFAULT_LOAD_FACTOR = 1000;
+
+ private static final float DEFAULT_EVICTION_CAPACITY = 0.75f;
+
+ public LFUCache() {
+ this(DEFAULT_LOAD_FACTOR, DEFAULT_EVICTION_CAPACITY);
+ }
+
+ /**
+ * 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
+ */
+ public LFUCache(final int maxCapacity, final float evictionFactor) {
+ if (maxCapacity <= 0) {
+ throw new IllegalArgumentException("Illegal initial capacity: " +
+ maxCapacity);
+ }
+ boolean factorInRange = evictionFactor <= 1 || evictionFactor < 0;
+ if (!factorInRange || Float.isNaN(evictionFactor)) {
+ throw new IllegalArgumentException("Illegal eviction factor value:"
+ + evictionFactor);
+ }
+ 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<K, V>();
+ }
+ for (int i = 0; i < capacity; i++) {
+ freqTable[i].nextDeque = freqTable[i + 1];
+ }
+ freqTable[capacity].nextDeque = freqTable[capacity];
+ }
+
+ public int getCapacity() {
+ return capacity;
+ }
+
+ public V put(final K key, final V value) {
+ CacheNode<K, V> node;
+ lock.lock();
+ try {
+ if (map.containsKey(key)) {
+ node = map.get(key);
+ if (node != null) {
+ CacheNode.withdrawNode(node);
+ }
+ node.value = value;
+ freqTable[0].addLastNode(node);
+ map.put(key, node);
+ } else {
+ node = freqTable[0].addLast(key, value);
+ map.put(key, node);
+ curSize++;
+ if (curSize > capacity) {
+ proceedEviction();
+ }
+ }
+ } finally {
+ lock.unlock();
+ }
+ return node.value;
+ }
+
+ public V remove(final K key) {
+ CacheNode<K, V> node = null;
+ lock.lock();
+ try {
+ if (map.containsKey(key)) {
+ node = map.remove(key);
+ if (node != null) {
+ CacheNode.withdrawNode(node);
+ }
+ curSize--;
+ }
+ } finally {
+ lock.unlock();
+ }
+ return (node != null) ? node.value : null;
+ }
+
+ public V get(final K key) {
+ CacheNode<K, V> node = null;
+ lock.lock();
+ try {
+ if (map.containsKey(key)) {
+ node = map.get(key);
+ CacheNode.withdrawNode(node);
+ node.owner.nextDeque.addLastNode(node);
+ }
+ } finally {
+ lock.unlock();
+ }
+ return (node != null) ? node.value : null;
+ }
+
+ /**
+ * 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 evictedElements = 0;
+
+ FREQ_TABLE_ITER_LOOP:
+ for (int i = 0; i <= capacity; i++) {
+ CacheNode<K, V> node;
+ while (!freqTable[i].isEmpty()) {
+ node = freqTable[i].pollFirst();
+ remove(node.key);
+ if (targetSize >= curSize) {
+ break FREQ_TABLE_ITER_LOOP;
+ }
+ evictedElements++;
+ }
+ }
+ return evictedElements;
+ }
+
+ /**
+ * Returns cache current size.
+ *
+ * @return cache size
+ */
+ public int getSize() {
+ return curSize;
+ }
+
+ static class CacheNode<K, V> {
+
+ CacheNode<K, V> prev;
+ CacheNode<K, V> next;
+ K key;
+ V value;
+ CacheDeque owner;
+
+ CacheNode() {
+ }
+
+ CacheNode(final K key, final V value) {
+ this.key = key;
+ this.value = value;
+ }
+
+ /**
+ * This method takes specified node and reattaches it neighbors nodes
+ * links to each other, so specified node will no longer tied with them.
+ * Returns united node, returns null if argument is null.
+ *
+ * @param node note to retrieve
+ * @param <K> key
+ * @param <V> value
+ * @return retrieved node
+ */
+ static <K, V> CacheNode<K, V> withdrawNode(
+ final CacheNode<K, V> node) {
+ if (node != null && node.prev != null) {
+ node.prev.next = node.next;
+ if (node.next != null) {
+ node.next.prev = node.prev;
+ }
+ }
+ return node;
+ }
+
+ }
+
+ /**
+ * Custom deque implementation of LIFO type. Allows to place element at top
+ * of deque and poll very last added elements. An arbitrary node from the
+ * deque can be removed with {@link CacheNode#withdrawNode(CacheNode)}
+ * method.
+ *
+ * @param <K> key
+ * @param <V> value
+ */
+ static class CacheDeque<K, V> {
+
+ CacheNode<K, V> last;
+ CacheNode<K, V> first;
+ CacheDeque<K, V> nextDeque;
+
+ /**
+ * Constructs list and initializes last and first pointers.
+ */
+ CacheDeque() {
+ last = new CacheNode<>();
+ first = new CacheNode<>();
+ last.next = first;
+ first.prev = last;
+ }
+
+ /**
+ * Puts the node with specified key and value at the end of the deque
+ * and returns node.
+ *
+ * @param key key
+ * @param value value
+ * @return added node
+ */
+ CacheNode<K, V> addLast(final K key, final V value) {
+ CacheNode<K, V> node = new CacheNode<>(key, value);
+ node.owner = this;
+ node.next = last.next;
+ node.prev = last;
+ node.next.prev = node;
+ last.next = node;
+ return node;
+ }
+
+ CacheNode<K, V> addLastNode(final CacheNode<K, V> node) {
+ node.owner = this;
+ node.next = last.next;
+ node.prev = last;
+ node.next.prev = node;
+ last.next = node;
+ return node;
+ }
+
+ /**
+ * Retrieves and removes the first node of this deque.
+ *
+ * @return removed node
+ */
+ CacheNode<K, V> pollFirst() {
+ CacheNode<K, V> node = null;
+ if (first.prev != last) {
+ node = first.prev;
+ first.prev = node.prev;
+ first.prev.next = first;
+ node.prev = null;
+ node.next = null;
+ }
+ return node;
+ }
+
+ /**
+ * Checks if link to the last node points to link to the first node.
+ *
+ * @return is deque empty
+ */
+ boolean isEmpty() {
+ return last.next == first;
+ }
+
+ }
+
+}
\ 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
new file mode 100644
index 0000000..3453524
--- /dev/null
+++ b/dubbo-common/src/test/java/org/apache/dubbo/common/utils/LFUCacheTest.java
@@ -0,0 +1,72 @@
+/*
+ * 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.dubbo.common.utils;
+
+import org.junit.jupiter.api.Test;
+
+import static org.hamcrest.Matchers.equalTo;
+import static org.hamcrest.MatcherAssert.assertThat;
+
+public class LFUCacheTest {
+
+ @Test
+ public void testCacheEviction() throws Exception {
+ LFUCache<String, Integer> cache = new LFUCache<String, Integer>(8, 0.8f);
+ cache.put("one", 1);
+ cache.put("two", 2);
+ cache.put("three", 3);
+ assertThat(cache.get("one"), equalTo(1));
+ assertThat(cache.get("two"), equalTo(2));
+ assertThat(cache.get("three"), equalTo(3));
+ assertThat(cache.getSize(), equalTo(3));
+ cache.put("four", 4);
+ assertThat(cache.getSize(), equalTo(4));
+ cache.put("five", 5);
+ cache.put("six", 6);
+ assertThat(cache.getSize(), equalTo(6));
+ cache.put("seven", 7);
+ cache.put("eight", 8);
+ cache.put("nine", 9);
+ assertThat(cache.getSize(), equalTo(2));
+ }
+
+ @Test
+ public void testCacheRemove() throws Exception {
+ LFUCache<String, Integer> cache = new LFUCache<String, Integer>(8, 0.8f);
+ cache.put("one", 1);
+ cache.put("two", 2);
+ cache.put("three", 3);
+ assertThat(cache.get("one"), equalTo(1));
+ assertThat(cache.get("two"), equalTo(2));
+ assertThat(cache.get("three"), equalTo(3));
+ assertThat(cache.getSize(), equalTo(3));
+ cache.put("four", 4);
+ assertThat(cache.getSize(), equalTo(4));
+ cache.remove("four");
+ assertThat(cache.getSize(), equalTo(3));
+ cache.put("five", 5);
+ assertThat(cache.getSize(), equalTo(4));
+ cache.put("six", 6);
+ assertThat(cache.getSize(), equalTo(5));
+ }
+
+ @Test
+ public void testCapacity() throws Exception {
+ LFUCache<String, Integer> cache = new LFUCache<String, Integer>();
+ assertThat(cache.getCapacity(), equalTo(1000));
+ }
+}
diff --git a/dubbo-filter/dubbo-filter-cache/src/main/java/org/apache/dubbo/cache/support/lfu/LfuCache.java b/dubbo-filter/dubbo-filter-cache/src/main/java/org/apache/dubbo/cache/support/lfu/LfuCache.java
new file mode 100644
index 0000000..9ccc979
--- /dev/null
+++ b/dubbo-filter/dubbo-filter-cache/src/main/java/org/apache/dubbo/cache/support/lfu/LfuCache.java
@@ -0,0 +1,80 @@
+/*
+ * 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.dubbo.cache.support.lfu;
+
+import org.apache.dubbo.cache.Cache;
+import org.apache.dubbo.common.URL;
+import org.apache.dubbo.common.utils.LFUCache;
+
+/**
+ * This class store the cache value per thread. If a service,method,consumer or provided is configured with key <b>cache</b>
+ * with value <b>lfu</b>, dubbo initialize the instance of this class using {@link LfuCacheFactory} to store method's returns value
+ * to server from store without making method call.
+ * <pre>
+ * e.g. 1) <dubbo:service cache="lfu" cache.size="5000" cache.evictionFactor="0.3"/>
+ * 2) <dubbo:consumer cache="lfu" />
+ * </pre>
+ * <pre>
+ * LfuCache uses url's <b>cache.size</b> value for its max store size, url's <b>cache.evictionFactor</b> value for its eviction factor,
+ * default store size value will be 1000, default eviction factor will be 0.3
+ * </pre>
+ *
+ * @see Cache
+ * @see LfuCacheFactory
+ * @see org.apache.dubbo.cache.support.AbstractCacheFactory
+ * @see org.apache.dubbo.cache.filter.CacheFilter
+ */
+public class LfuCache implements Cache {
+
+ /**
+ * This is used to store cache records
+ */
+ private final LFUCache store;
+
+ /**
+ * Initialize LfuCache, it uses constructor argument <b>cache.size</b> value as its storage max size.
+ * If nothing is provided then it will use 1000 as default size value. <b>cache.evictionFactor</b> value as its eviction factor.
+ * If nothing is provided then it will use 0.3 as default value.
+ * @param url A valid URL instance
+ */
+ public LfuCache (URL url) {
+ final int max = url.getParameter("cache.size", 1000);
+ final float factor = url.getParameter("cache.evictionFactor", 0.75f);
+ this.store = new LFUCache(max, factor);
+ }
+
+ /**
+ * API to store value against a key in the calling thread scope.
+ * @param key Unique identifier for the object being store.
+ * @param value Value getting store
+ */
+ @Override
+ public void put(Object key, Object value) {
+ store.put(key, value);
+ }
+
+ /**
+ * API to return stored value using a key against the calling thread specific store.
+ * @param key Unique identifier for cache lookup
+ * @return Return stored object against key
+ */
+ @Override
+ public Object get(Object key) {
+ return store.get(key);
+ }
+
+}
diff --git a/dubbo-filter/dubbo-filter-cache/src/main/java/org/apache/dubbo/cache/support/lfu/LfuCacheFactory.java b/dubbo-filter/dubbo-filter-cache/src/main/java/org/apache/dubbo/cache/support/lfu/LfuCacheFactory.java
new file mode 100644
index 0000000..f04edca
--- /dev/null
+++ b/dubbo-filter/dubbo-filter-cache/src/main/java/org/apache/dubbo/cache/support/lfu/LfuCacheFactory.java
@@ -0,0 +1,43 @@
+/*
+ * 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.dubbo.cache.support.lfu;
+
+import org.apache.dubbo.cache.Cache;
+import org.apache.dubbo.cache.support.AbstractCacheFactory;
+import org.apache.dubbo.common.URL;
+
+/**
+ * Implement {@link org.apache.dubbo.cache.CacheFactory} by extending {@link AbstractCacheFactory} and provide
+ * instance of new {@link LfuCache}.
+ *
+ * @see AbstractCacheFactory
+ * @see LfuCache
+ * @see Cache
+ */
+public class LfuCacheFactory extends AbstractCacheFactory {
+
+ /**
+ * Takes url as an method argument and return new instance of cache store implemented by LfuCache.
+ * @param url url of the method
+ * @return ThreadLocalCache instance of cache
+ */
+ @Override
+ protected Cache createCache(URL url) {
+ return new LfuCache(url);
+ }
+
+}