Background

• LRU( lease recently used) is a cache eviction strategy, where if the cache size has reached the maximun allocated capacity, the least recently accessed object in the cache will be evicted.

  There’s a pretty of embed caching framework provides the LRUCache, For example:

  • Java: Ehcache
  • Golang: golang-lru: Golang LRU cache
  • Ruby: lru_redux: An efficient optionally thread safe LRU Cache

as a developer we can just simply use it.

BUT….If you want to learn how those tools works under the hood, This is the article demonstrate how we can write a simple LRU cache of our own.

背景介绍

• LRU全称Least Recently Used（最近最少使用），是一种缓存清理策略， 如果当实际存储数据的大小大于缓存设定的大小之后，最近最少使用的对象会被清理出缓存。

  绝大部分的开发语言都有关于LRUCache的实现框架。 例如 ：

  • Java: Ehcache
  • Golang: golang-lru: Golang LRU cache
  • Ruby: lru_redux: An efficient optionally thread safe LRU Cache

  绝大部分时候作为程序员的我们，只用把它引入到项目中来用它就好了。

  但是如果你想了解LRUCache的实现原理，这篇文章会介绍我们如何自己实现一个简单的LRU Cache。

How to design a LRU Cache:

1. The cache can set with a List of Maps.
   1. The List contains the fixed maximum allocated size
   2. The Map contains the key and value, and making sure value can be inserted or updated with the same key.
   3. A list should define the order. (making sure Last Recent Used item at the last of the List and Most Recent Used at first. In this way, we can simply delete the last one if the List reach to maximum allocated size)
   4. If the Map contains order, then the implementation could be straightforward because we don’t have to manage the order of our own. But if we choose a map that doest contains order, then we may need to manage the list order of our own.
      1. Javascript Map contains order
      2. Java LinkedHashMap have order as well. However, it is not thread-safe by default. So I will implement it by using ConcurrentHashMap and simple Doubly-Linked-List. (This DLL helps us achieve the LRU eviction strategy, where the objects accessed frequently will be at the tail end, and the items accessed the least will be towards the head of the List. )
2. How to insert a value:
   • When inserting a value, we need to check if it is existed by finding the value from the key in the Map.
     • If the value existed, we need to update the value from the key and also change the order to top of the List
     • If the value doesn’t exist, we inserted the value and put it into a top list. Also, that important: remove the bottom item from the list size is larger than the defined maximum size expected.

     Rseudocode :

       public void put(K key, V value) {
           if (map.contains(key)) {
               // remove the value of the key
               // set the new key and value at the top list.
           } else {
               if (map.size() == maxCapacity) {
                   //remove value from first item of the list.
                   // set the new key and value at the top list.
                   map.put(key, value)
           } else {
           // set the new key and value at the top list.
               map.put(key,value)
           }
       }
     

3. How to get a value:
   • Get value from list

   • Move the value to the end of the list,

     Rseudo Code:

       public V get(K key) {
               // get value of the key
               //remove Item contains the key
               //insert Item at first
       }
     

如何设计一个LRU Cache

1. 缓存可以用一个Map数组来定义
   • 这个数组会定义最大的数组范围值
   • Map包括一个键值对，我们可以根据这个键的内容来插入，修改和查找内容。
   • 数组的内容需要有顺序，最少用到的放在数组的最后，最多用到的放在最前边。这样，我们就可以很轻松的删除那些不常用的内容。
   • 如果Map实现的本身就自带顺序，那我们的LRU Cache的实现也变得比较容易，因为他可以直接利用数组的顺序来管理，但是如果Map本身不带顺序，那我们究竟需要自己用一个方法来做顺序的管理，常见的方法是做Linked list 例如：
     1. JavaScript的Map就自我包含了顺序
     2. Java的linkedHashMap也自带顺序，但是他不是线程安全的。
     3. 我们的Java实现会采用结合ConcurrentHashMap和Doubly-Linked-List.的方法来实现，
2. 怎么插入值
   1. 当插入值的时候，我们需要查看这个值所在的key是不是已经存在，
      1. 如果存在，我们需要的不是插入，而是修改值的内容
      2. 如果不存在，我们就需要插入值，但是非常重要的是，我们在之前，需要比较这个数组的总长度，看他是否已经超过了本身能容纳的长度。删除数组中第一个数据内容。因为他是最近最少用的数据。

   伪代码如下：

   public void put(K key, V value) {
       if (map.contains(key)) {
           // remove the value of the key
           // set the new key and value at the top list.
       } else {
           if (map.size() == maxCapacity) {
               //remove value from first item of the list.
               // set the new key and value at the top list.
               map.put(key, value)
       } else {
       // set the new key and value at the top list.
           map.put(key,value)
       }
   }
   

3. 怎么获取想要的值
   1. 用键来从数组中查找获取值。
   2. 如果值能够获取，那么我们需要把这个值的顺序挪到数组的最前边来。（因为他是最近最多获取的）

   伪代码如下：

   ```java public V get(K key) { // get value of the key //remove Item contains the key //insert Item at first }

Full Code Example:

• Java(Double Linked List with ConcurrentMap): code
• Typscript (ES6 Map): code

• Background
• 背景介绍
• How to design a LRU Cache:
• 如何设计一个LRU Cache
• Full Code Example: