微服务之服务器缓存

//以下是使用Collections.synchronizedMap()方法创建容器的常见api，都是通过synchronized关键字保证的并发安全，但是无法保证高并发下的高吞吐量public V get(Object key) {    synchronized (mutex) {return m.get(key);}}public V put(K key, V value) {    synchronized (mutex) {return m.put(key, value);}}public V remove(Object key) {    synchronized (mutex) {return m.remove(key);}}

/** *  LRUCache implementation * * @author disaster * @version 1.0 * * @param <K> * @param <V> */public class LRUCache<K, V> extends LinkedHashMap<K, V> {    public static final LRUCache<String,ReentrantLock> LOCK_CACHE_INSTANCE = new LRUCache<String,ReentrantLock>(10000);
    private static final long serialVersionUID = -5167631809472116969L;
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;
    private static final int DEFAULT_MAX_CAPACITY = 1000;    private final Lock lock = new ReentrantLock();    private volatile int maxCapacity;
    public LRUCache() {        this(DEFAULT_MAX_CAPACITY);    }
    public LRUCache(int maxCapacity) {        super(16, DEFAULT_LOAD_FACTOR, true);        this.maxCapacity = maxCapacity;    }
    @Override    protected boolean removeEldestEntry(java.util.Map.Entry<K, V> eldest) {        return size() > maxCapacity;    }
    @Override    public boolean containsKey(Object key) {        try {            lock.lock();            return super.containsKey(key);        } finally {            lock.unlock();        }    }
    @Override    public V get(Object key) {        try {            lock.lock();            return super.get(key);        } finally {            lock.unlock();        }    }
    @Override    public V put(K key, V value) {        try {            lock.lock();            return super.put(key, value);        } finally {            lock.unlock();        }    }
    @Override    public V remove(Object key) {        try {            lock.lock();            return super.remove(key);        } finally {            lock.unlock();        }    }
    @Override    public int size() {        try {            lock.lock();            return super.size();        } finally {            lock.unlock();        }    }
    @Override    public void clear() {        try {            lock.lock();            super.clear();        } finally {            lock.unlock();        }    }
    public int getMaxCapacity() {        return maxCapacity;    }
    public void setMaxCapacity(int maxCapacity) {        this.maxCapacity = maxCapacity;    }
}

/** * 哈希链表实现LRU *  * @author disaster * @version 1.0 * @param <K> * @param <V> */public class ILRUCache<K, V> {    private HashMap<K, Node<K, V>> map;    private BidirectionalLinkedList<K, V> cache;    // 最大容量    private int cap;
    public ILRUCache(int cap) {        this.cap = cap;        this.map = new HashMap<K, Node<K, V>>();        this.cache = new BidirectionalLinkedList<K, V>();    }
    public void put(K key, V value) {        if (map.containsKey(key)) {            remove(key);            addRecently(key, value);            return;        }        if (map.size() == cap) {            removeLeastRecently();        }        addRecently(key, value);    }

    public V get(K key) {        if (!map.containsKey(key)) {            return null;        }        makeRecently(key);        return map.get(key).getValue();    }
    public void makeRecently(K key) {        Node<K, V> kvNode = map.get(key);        cache.remove(kvNode);        cache.addLast(kvNode);    }
    public void removeLeastRecently() {        Node<K, V> kvNode = cache.removeFirst();        // 同时别忘了从 map 中删除它的 key        assert kvNode != null;        K deletedKey = kvNode.key;        map.remove(deletedKey);    }
    public void remove(K key) {        Node<K, V> x = map.get(key);        cache.remove(x);        map.remove(key);        cap--;    }
    public void addRecently(K key, V value) {        Node<K, V> kvNode = new Node<>(key, value);        cache.addLast(kvNode);        map.put(key, kvNode);        cap++;    }

    private static class BidirectionalLinkedList<K, V> {        private Node<K, V> head, tail;        private int size;
        public BidirectionalLinkedList() {            this.head = new Node<K, V>((K) new Object(), (V) new Object());            this.tail = new Node<K, V>((K) new Object(), (V) new Object());            this.size = 0;        }
        public void addLast(Node<K, V> x) {            x.prev = tail.prev;            x.next = tail;            tail.prev.next = x;            tail.prev = x;            size++;        }
        // 删除链表中的 x 节点（x 一定存在）        // 由于是双链表且给的是目标 Node 节点，时间 O(1)        public void remove(Node<K, V> x) {            x.prev = x.next;            x.next.prev = x.prev;            size--;        }
        // 删除链表中第一个节点，并返回该节点，时间 O(1)        public Node<K, V> removeFirst() {            if (head.next == tail) {                return null;            }            Node<K, V> first = head.next;            remove(first);            return first;        }
        public int size() {            return size;        }
    }
    private static class Node<K, V> {        private K key;        private V value;        private Node<K, V> prev;        private Node<K, V> next;
        public Node(K key, V value) {            this.key = key;            this.value = value;        }
        public K getKey() {            return key;        }
        public void setKey(K key) {            this.key = key;        }
        public V getValue() {            return value;        }
        public void setValue(V value) {            this.value = value;        }
        public Node<K, V> getPrev() {            return prev;        }
        public void setPrev(Node<K, V> prev) {            this.prev = prev;        }
        public Node<K, V> getNext() {            return next;        }
        public void setNext(Node<K, V> next) {            this.next = next;        }    }}

/** * LFU implementation * * @author wangwei * @version 1.0 * @param <K> * @param <V> */public class LFUCache<K, V> {    public final static LFUCache<String,Object> CONDITIONS_RESULT_CACHE = new LFUCache<String,Object>(10000,0.75f);    public final static LFUCache<String,ReentrantLock> LOCK_CACHE_INSTANCE = new LFUCache<String,ReentrantLock>(10000,0.75f);    public final static String PREFIX = "LFU_PREFIX";    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_INITIAL_CAPACITY = 1000;
    private static final float DEFAULT_EVICTION_FACTOR = 0.75f;
    public LFUCache() {        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_EVICTION_FACTOR);    }
    /**     * 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     */    @SuppressWarnings("unchecked")    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) {            throw new IllegalArgumentException("Illegal eviction factor value:"                    + evictionFactor);        }        this.capacity = maxCapacity;        this.evictionCount = (int) (capacity * evictionFactor);        this.map = new HashMap<K, CacheNode<K, V>>();        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 {            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<K, V> 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<K, V>();            first = new CacheNode<K, V>();            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<K, V>(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;        }
    }}