​

To say the computer system, what technology tradeoff embodies the most incisively and vividly, it is definitely cache. In order to coordinate the speed difference between high-speed parts and low-speed parts, adding an intermediate cache layer is the most effective solution to this conflict.

Among them, JVM in-heap cache is an important part of the cache system, and the most commonly used are FIFO/LRU/LFU algorithms.

  1. FIFOIt’s a simple queue, first in, first out.
  2. LRUThe least recently used data is preferentially removed from the data that has not been used for a long time. isTime dimension.
  3. LFUThe least frequently used data is removed first. isStatistical dimension.

Expiration is also an important feature of caching. So when designing these three caching algorithms, you need extra storage space to store this expiration time.

The operation and design considerations of these three caching algorithms are discussed below, but high concurrency environments are not considered for the time being.

FIFO

First in, first out. If the cache capacity is full, the earliest data added to the cache is removed preferentially. It can be implemented internally using queues.

​

operation

  • Object GET (key) : Retrieves saved data. If the data does not exist or has expired, null is returned.
  • Void PUT (key,value,expireTime) : Adds to the cache. Regardless of whether the key already exists, it is treated as a new key (the old key is removed). If the space is insufficient, the expired keys are removed; if not, the earliest keys are removed. If the expiration time is not specified, it never expires automatically.
  • Note that we allow keys to expire, which is different from normal FIFO, so you need to be careful when designing this problem. (Also interview research point, more design than algorithm)

Common FIFO may be very simple to write, increase the expiration time after consideration, in the design need to consider more. The following example is a FIFO design for a concurrent environment that is not currently considered.

Design ideas

1) Store cached data with a normal hashMap. 2) An additional map is needed to store the expiration feature of the key. In the example, TreeMap is used. “Remaining life time” is taken as the key and TreeMap’s sorting feature is utilized.

Public class FIFOCache {// Save all key-value private final Map<String, value > CACHE = new LinkedHashMap<>(); // We do not consider concurrency, we think there is no duplicate key in the same time, if the modification, You can change value to Set Private Final TreeMap<Long, String> EXPIRED = new TreeMap<>(); private final int capacity; public FIFOCache(int capacity) { this.capacity = capacity; } public Object get(String key) { // Value value = CACHE.get(key); if (value == null) { return null; } // If no expiration time is included long expired = value.expired; long now = System.nanoTime(); // Expired if (expired > 0 && expired <= now) {cache.remove (key); EXPIRED.remove(expired); return null; } return value.value; } public void put(String key,Object value) { put(key,value,-1); } public void put(String key,Object value,int seconds) {// If the capacity is insufficient, If (capacity < cache.size ()) {long now = system.nanotime (); Iterator<Long> Iterator = expired.keyset ().iterator(); while (iterator.hasNext()) { long _key = iterator.next(); If (_key > now) {break; } // Remove all EXPIRED keys at once String _value = expired.get (_key); CACHE.remove(_value); iterator.remove(); If (capacity < cache.size ()) {Iterator<String> Iterator = cache.keyset ().iterator(); while (iterator.hasNext() && capacity < CACHE.size()) { String _key = iterator.next(); Value _value = CACHE.get(_key); long expired = _value.expired; if (expired > 0) { EXPIRED.remove(expired); } iterator.remove(); }} // If the key already exists, remove old data Value current = cache.remove (key); if (current ! = null && current.expired > 0) { EXPIRED.remove(current.expired); } // If (seconds > 0) {long expireTime = expiredTime(seconds); EXPIRED.put(expireTime,key); CACHE.put(key,new Value(expireTime,value)); } else { CACHE.put(key,new Value(-1,value)); } } private long expiredTime(int expired) { return System.nanoTime() + TimeUnit.SECONDS.toNanos(expired); } public void remove(String key) { Value value = CACHE.remove(key); if(value == null) { return; } long expired = value.expired; if (expired > 0) { EXPIRED.remove(expired); } } class Value { long expired; // Expiration time, nanosecond Object value; Value(long expired,Object value) { this.expired = expired; this.value = value; }}}Copy the code

#LRU

At present, it is one of the most commonly used cache algorithms and design schemes. Its removal policy is “When the cache (page) is full, the latest and longest unused data is removed first”. It is easy to design and use and applies to a wide range of scenarios. For the algorithm, see Leetcode 146 (LRU Cache).

operation

  • Object GET (key) : Retrieves the data corresponding to the key from the cache. If the key has expired, it is removed and null is returned.
  • Void PUT (key,value,expired) : Set k-V. If the capacity is insufficient, remove the oldest unused key based on the LRU replacement algorithm. Note that keys that have expired are removed first based on the LRU, and keys that have not expired are removed based on the LRU. If the expiration time is not set, the system considers that it will never expire automatically.
  • The design key here is the expiration time feature, which is different from regular LRU.

Design ideas

  • LRU basic algorithm, need to understand; The access time corresponding to the key needs to be updated each time the PUT and GET are performed. A data structure is required to store the last access time of the key and sort it.
  • Since the expiration time feature is included, keys with expiration time require additional data structures to hold.
  • Don’t consider concurrent operations for now; Try to balance space complexity and time complexity.
  • This question is still more of a design question than a pure algorithm question.

This code is basically the same as FIFO, except for the get() method. For LRU, the get method needs to reset the access time (i.e. the order in the cache).

public Object get(String key) { // Value value = CACHE.get(key); if (value == null) { return null; } // If no expiration time is included long expired = value.expired; long now = System.nanoTime(); // Expired if (expired > 0 && expired <= now) {cache.remove (key); EXPIRED.remove(expired); return null; } // Add sequential reset cache.remove (key) with respect to FIFO; CACHE.put(key,value); return value.value; }Copy the code

LFU

When the cache capacity is full, the least frequently accessed element is removed. If there are multiple elements that have been accessed the same number of times, the most frequently accessed element is removed. See Leetcode 460 (LFU Cache) for design requirements.

Private Map<String, Object> keyToValue = new HashMap<>(); private Map<String, Object> keyToValue = new HashMap<>(); Private Map<String, Integer> keyToCount = new HashMap<>(); // The list of keys accessed for the same number of times is sorted by access times. Value is the list of keys accessed for the same number of times. private TreeMap<Integer, LinkedHashSet<String>> countToLRUKeys = new TreeMap<>(); private int capacity; public LFUCache(int capacity) { this.capacity = capacity; } public Object get(String key) {if (! keyToValue.containsKey(key)) { return null; } touch(key); return keyToValue.get(key); } /** * If a key is accessed, the number of times it is accessed should be adjusted. * @param key */ private void touch(String key) { int count = keyToCount.get(key); keyToCount.put(key, count + 1); Counttolrukeys.get (count).remove(key); If (counttolrukeys.get (count).size() == 0) {counttolrukeys.remove (count); } LinkedHashSet<String> countKeys = counttolrukeys. get(count + 1); if (countKeys == null) { countKeys = new LinkedHashSet<>(); countToLRUKeys.put(count + 1,countKeys); } countKeys.add(key); } public void put(String key, Object value) { if (capacity <= 0) { return; } if (keyToValue.containsKey(key)) { keyToValue.put(key, value); touch(key); return; } // After the capacity is exceeded, Remove the least visited element if (keytoValue.size () >= Capacity) {map.entry <Integer,LinkedHashSet<String>> Entry = countToLRUKeys.firstEntry(); Iterator<String> it = entry.getValue().iterator(); String evictKey = it.next(); it.remove(); if (! it.hasNext()) { countToLRUKeys.remove(entry.getKey()); } keyToCount.remove(evictKey); keyToValue.remove(evictKey); } keyToValue.put(key, value); keyToCount.put(key, 1); LinkedHashSet<String> keys = countToLRUKeys.get(1); if (keys == null) { keys = new LinkedHashSet<>(); countToLRUKeys.put(1,keys); } keys.add(key); }}Copy the code

End

This article tries to compare three basic caching algorithms to get a general sense of the path to cache construction.

For a more user-friendly cache, see Guava’s implementation. I hope you found these three code templates helpful.

​

= = =