Реализация кеширования LRU в Javascript

Map должен быть O (1) в среднем случае большинства реализаций. Поскольку карта сохраняет порядок вставки, добавление небольшого количества кода вокруг нее даст вам LRU, и для большинства случаев это должно быть достаточно быстрым.

Мне нужен был простой LRU-кеш для небольшого количества дорогостоящих операций (1 секунда). Мне было легче скопировать небольшой код вместо того, чтобы вводить что-то внешнее, но, поскольку я не нашел этого, я написал это:

class LRU {
    constructor(max = 10) {
        this.max = max;
        this.cache = new Map();
    }

    get(key) {
        let item = this.cache.get(key);
        if (item) {
            // refresh key
            this.cache.delete(key);
            this.cache.set(key, item);
        }
        return item;
    }

    set(key, val) {
        // refresh key
        if (this.cache.has(key)) this.cache.delete(key);
        // evict oldest
        else if (this.cache.size == this.max) this.cache.delete(this.first());
        this.cache.set(key, val);
    }

    first() {
        return this.cache.keys().next().value;
    }
}

Использование:

> let cache = new LRU(3)
> [1, 2, 3, 4, 5].forEach(v => cache.set(v, 'v:'+v))
> cache.get(2)
undefined
> cache.get(3)
"v:3"
> cache.set(6, 6)
> cache.get(4)
undefined
> cache.get(3)
"v:3"

Этот:

https://github.com/monsur/jscache

кажется, вам подходит, хотя setItem (т.е. положить) - это O (N) в худшем случае, это происходит, если кеш заполняется при вставке. В этом случае выполняется поиск в кэше, чтобы удалить элементы с истекшим сроком действия или элементы, которые использовались недавно. getItem равно O (1), и истечение срока обрабатывается в операции getItem (т.е. если срок действия извлекаемого элемента истек, удаляет его и возвращает ноль).

Код достаточно компактен, чтобы его было легко понять.

P.S. Может быть полезно добавить в конструктор возможность указать fillFactor, который имеет фиксированное значение 0,75 (это означает, что при очистке кеша его размер уменьшается по крайней мере до 3/4 от максимального размера)

Об этом стоит упомянуть: https://github.com/rsms/js-lru

Базовый набор функций - O (1), а код сильно комментируется (с ASCII-артом тоже!)

Реализация monsur.com - O (n) при вставке только потому, что у нее есть элементы, срок действия которых истекает в реальном времени. Это не простой LRU. Если вы заботитесь только о последних использованных элементах без учета реального времени, это можно сделать в O (1). Очередь, реализованная как двусвязный список, имеет значение O (1) для вставки или удаления с конца, и это все, что вам нужно для кеширования. Что касается поиска, то хеш-карта, которую javascript упрощает до некоторой степени, должна подходить для поиска почти O (1) (при условии, что движок javascript использует хорошую хэш-карту, это, конечно, зависит от реализации). Итак, у вас есть связанный список элементов с хеш-картой, указывающей на элементы. При необходимости манипулируйте концами связанного списка, чтобы поместить новые элементы и запрошенные элементы на один конец и удалить старые элементы с другого.

Эта библиотека runtime-memcache реализует lru и несколько других схем кэширования в javascript.

Он использует модифицированный двусвязный список для достижения O (1) для get, set и remove. Вы можете проверить довольно простую реализацию.

Это не кеш LRU, но у меня есть мой реализация собственной связанной карты. Поскольку он использует объекты JS в качестве хранилища, он будет иметь аналогичные характеристики производительности (объекты-оболочки и хеш-функция ухудшают производительность).

В настоящее время документация в основном не -existant, но есть связанный SO-ответ.

Метод each() передаст текущий ключ, текущее значение и логическое значение, указывающее, есть ли еще элементы в качестве аргументов функции обратного вызова.

В качестве альтернативы цикл можно выполнить вручную с помощью

for(var i = map.size; i--; map.next()) {
    var currentKey = map.key();
    var currentValue = map.value();
}

Я понимаю, что это старый вопрос, но я добавляю ссылку для использования в будущем. Ознакомьтесь с https://github.com/monmohan/dsjslib. В нем есть реализация LRU Cache в дополнение к некоторым другим структурам данных. Такие кеши (и этот тоже) поддерживают двусвязный список записей кеша в порядке LRU, то есть записи перемещаются в начало по мере доступа к ним и удаляются из хвоста, когда они возвращаются (скажем, по истечении срока действия или из-за того, что был достигнут предел размера). Его O (1), поскольку он включает только постоянное количество манипуляций с указателем.

(Это просто длинный комментарий)

Вот кеш часов (который является приближением LRU), который работает только со строками / целыми числами в качестве ключей и имеет только метод get:

• O (1) попадание в кеш, нет движения узла (дружественный сборщик мусора)

• O (1) промах в кэше, асинхронный

• количество асинхронных средств доступа (или асинхронных промахов кеша) должно быть равно или меньше размера кеша, в противном случае возникает временная тупиковая блокировка

lrucache.js:

'use strict';
/* 
cacheSize: number of elements in cache, constant, must be greater than or equal to number of asynchronous accessors / cache misses
callbackBackingStoreLoad: user-given cache-miss function to load data from datastore
elementLifeTimeMs: maximum miliseconds before an element is invalidated, only invalidated at next get() call with its key
*/

let Lru = function(cacheSize,callbackBackingStoreLoad,elementLifeTimeMs=1000){
    const me = this;
    
    const maxWait = elementLifeTimeMs;
    const size = parseInt(cacheSize,10);
    const mapping = {};
    const mappingInFlightMiss = {};
    const bufData = new Array(size);
    const bufVisited = new Uint8Array(size);
    const bufKey = new Array(size);
    const bufTime = new Float64Array(size);
    const bufLocked = new Uint8Array(size);
    for(let i=0;i<size;i++)
    {
        let rnd = Math.random();
        mapping[rnd] = i;
        
        bufData[i]="";
        bufVisited[i]=0;
        bufKey[i]=rnd;
        bufTime[i]=0;
        bufLocked[i]=0;
    }
    let ctr = 0;
    let ctrEvict = parseInt(cacheSize/2,10);
    const loadData = callbackBackingStoreLoad;
    let inFlightMissCtr = 0;
    this.get = function(keyPrm,callbackPrm){
        const key = keyPrm;
        const callback = callbackPrm;
        
        // stop dead-lock when many async get calls are made
        if(inFlightMissCtr>=size)
                {
                    setTimeout(function(){
                me.get(key,function(newData){
                    callback(newData);
                });
            },0);
                    return;
            }
        
        // delay the request towards end of the cache-miss completion
        if(key in mappingInFlightMiss)
        {

            setTimeout(function(){
                me.get(key,function(newData){
                    callback(newData);
                });
            },0);
            return;
        }

        if(key in mapping)
        {
            let slot = mapping[key];
            // RAM speed data
            if((Date.now() - bufTime[slot]) > maxWait)
            {
                
                if(bufLocked[slot])
                {                                       
                    setTimeout(function(){
                        me.get(key,function(newData){
                            callback(newData);
                        });
                    },0);
                    
                }
                else
                {
                    delete mapping[key];
                    
                    me.get(key,function(newData){
                        callback(newData);
                    });
                    
                }
                
            }
            else
            {
                bufVisited[slot]=1;
                bufTime[slot] = Date.now();
                callback(bufData[slot]);
            }
        }
        else
        {
            // datastore loading + cache eviction
            let ctrFound = -1;
            while(ctrFound===-1)
            {
                // give slot a second chance before eviction
                if(!bufLocked[ctr] && bufVisited[ctr])
                {
                    bufVisited[ctr]=0;
                }
                ctr++;
                if(ctr >= size)
                {
                    ctr=0;
                }

                // eviction conditions
                if(!bufLocked[ctrEvict] && !bufVisited[ctrEvict])
                {
                    // evict
                    bufLocked[ctrEvict] = 1;
                    inFlightMissCtr++;
                    ctrFound = ctrEvict;
                }

                ctrEvict++;
                if(ctrEvict >= size)
                {
                    ctrEvict=0;
                }
            }
            
            mappingInFlightMiss[key]=1;
            let f = function(res){
                delete mapping[bufKey[ctrFound]];

                bufData[ctrFound]=res;
                bufVisited[ctrFound]=0;
                bufKey[ctrFound]=key;
                bufTime[ctrFound]=Date.now();
                bufLocked[ctrFound]=0;

                mapping[key] = ctrFound;
                callback(bufData[ctrFound]);
                inFlightMissCtr--;
                delete mappingInFlightMiss[key];        
            };
            loadData(key,f);

        }
    };
};

exports.Lru = Lru;

Аннулирование на основе времени происходит только во время операции cache.get (), поэтому он не использует обработчик событий для каких-либо элементов.

Пример использования:

let Lru = require("./lrucache.js").Lru;
let num_cache_elements = 1000;
let element_life_time_miliseconds = 1000;
let cache = new Lru(num_cache_elements, async function(key,callback){
  // datastore access for filling the missing cache element when user access key
  callback(some_time_taking_io_work_or_heavy_computation(key)); 
}, element_life_time_miliseconds);


cache.get("some_key_string",function(data){
    // data comes from datastore or RAM depending on its lifetime left or the key acceess pattern
    // do_something_with(data);
});

Пример кеширования файлов:

let Lru = require("./lrucache.js").Lru;
let fs = require("fs");
let path = require("path");

let fileCache = new Lru(500, async function(key,callback){
  // cache-miss data-load algorithm
    fs.readFile(path.join(__dirname,key),function(err,data){
      if(err) {                                 
        callback({stat:404, data:JSON.stringify(err)});
      }
      else
      {                             
        callback({stat:200, data:data});
      }                                                     
    });
},1000 /* cache element lifetime */);

// test with a file
// cache-miss
let t1 = Date.now();
fileCache.get("./test.js",function(dat){   
  console.log("Cache-miss time:");
  console.log(Date.now()-t1);
  console.log("file data:");
  console.log(dat.data.length+" bytes");
  
  // cache-hit
  t1 = Date.now();
  fileCache.get("./test.js",function(dat){
    console.log("Cache-hit time:");
    console.log(Date.now()-t1);
    console.log("file data:");
    console.log(dat.data.length+" bytes");

  });     
});

Тест асинхронного пропускания кэша:

let Lru = require("./lrucache.js").Lru;
let benchSize = 500;
let cacheMiss= 0;
let cacheAccess= 0;
let cache = new Lru(900, async function(key,callback){
    // cache-miss data-load algorithm
    setTimeout(function(){
        cacheMiss++
        callback(key+" processed");
    },1000);
},1000 /* cache element lifetime */);
    
let ctrBench = 0;

function bench()
{
    let ctr = 0;
    let t1 = Date.now();
    for(let i=0;i<benchSize;i++)
    {
    let key = parseInt(Math.random()*1000,10);
        cache.get(key,function(data){ 
            cacheAccess++;
            if(key.toString()+" processed" !== data)
            {
                console.log("error: wrong key-data mapping.");
                
            }
            if(++ctr === benchSize)
            {
                console.log("benchmark: "+(Date.now()-t1)+" miliseconds");
            console.log("cache hit: "+(cacheAccess-cacheMiss));
            console.log("cache miss: "+(cacheMiss));
            if(ctrBench<20)
            {
                ctrBench++
                bench();
            }
            }
        });
    }
}

bench();

вывод:

benchmark: 1034 miliseconds
cache hit: 125
cache miss: 375
benchmark: 1015 miliseconds
cache hit: 374
cache miss: 626
benchmark: 1017 miliseconds
cache hit: 571
cache miss: 929
benchmark: 1013 miliseconds
cache hit: 750
cache miss: 1250
benchmark: 1016 miliseconds
cache hit: 950
cache miss: 1550
benchmark: 1017 miliseconds
cache hit: 1132
cache miss: 1868
benchmark: 1013 miliseconds
cache hit: 1324
cache miss: 2176
benchmark: 1014 miliseconds
cache hit: 1485
cache miss: 2515
benchmark: 1016 miliseconds
cache hit: 1675
cache miss: 2825
benchmark: 1016 miliseconds
cache hit: 1872
cache miss: 3128
benchmark: 1012 miliseconds
cache hit: 2053
cache miss: 3447
benchmark: 1015 miliseconds
cache hit: 2224
cache miss: 3776
benchmark: 1015 miliseconds
cache hit: 2405
cache miss: 4095
benchmark: 1016 miliseconds
cache hit: 2580
cache miss: 4420
benchmark: 1015 miliseconds
cache hit: 2760
cache miss: 4740
benchmark: 1013 miliseconds
cache hit: 2930
cache miss: 5070
benchmark: 1047 miliseconds
cache hit: 3105
cache miss: 5395
benchmark: 1015 miliseconds
cache hit: 3280
cache miss: 5720
benchmark: 1012 miliseconds
cache hit: 3449
cache miss: 6051
benchmark: 1015 miliseconds
cache hit: 3636
cache miss: 6364
benchmark: 1016 miliseconds
cache hit: 3818
cache miss: 6682

Срок службы 1000 мс здесь снижает коэффициент попадания в кеш. В противном случае ожидается 90% -ный коэффициент попадания.

Поскольку нам нужны операции чтения, записи, обновления и удаления в O (1), мы используем две структуры данных.

1. Объект (или карта) в JavaScript обеспечивает поиск за O (1).
2. A Doubly LinkedList(Custom data structure we create) makes below functionalities in O(1)
   • change position of the most used element to the top
   • удалить наименее используемый элемент из кеша при достижении лимита кеша.

Ниже приводится настраиваемая реализация кэша Дважды связанных списков и Наименее недавно использованных с четким объяснением.

https://medium.com/dsinjs/implementing-lru-cache-in-javascript-94ba6755cda9

Внешний пакет / библиотека не требуется, мы можем написать наш собственный код для реализации LRU в javascript, пожалуйста, обратитесь к https://dev.to/udayvunnam/implementing-lru-cache-in-javascript-3c8g, чтобы узнать подробности.