NodeJS 中的异步 LRU 缓存（CLOCK-2 手）实现
CLOCK 缓存（LRU 近似算法），缓存命中 O(1)，最多 N 个异步缓存未命中的 O(1)
引言
缓存是提高各种应用程序高性能最重要优化之一。在服务器端 JavaScript（Web 应用）中，文件和视频 blob 的缓存以及对页面模板的快速访问至关重要。操作系统（如 Ubuntu）已经有了自己的文件缓存，但当同一台服务器上运行多个 Web 应用时，如果一个应用正在流式传输大量视频数据，那么其他应用的缓存内容可能会频繁失效，性能也会下降。
为应用资源设计的专用最近最少使用（缓存驱逐）算法可以使应用独立于同一服务器上其他应用的缓存污染。
背景
缓存的基本思想是从一个已经（预计算）的数据列表中提供一些（计算成本）高昂的数据。没有缓存，吞吐量将取决于数据来源的最慢存储。如果是文件，那就是 HDD。HDD 太慢了，约 100MB/s，SSD 仍然很慢，约 500MB/s，即使是 NVME 也比货架上最便宜的 RAM 模块慢（5GB/s）。将文件内容缓存到 RAM 中不仅可以提高吞吐量，还可以降低延迟。在 Web 应用中，尤其是在 NodeJS 中，操作的延迟（如果是在非异步函数中）决定了何时可以为其他客户端提供服务。因此，拥有 LRU 缓存可以将性能提高 2 倍到 100 倍，具体取决于最慢数据存储的性能。另一方面，拥有异步 LRU 应该可以隐藏任何缓存未命中延迟。
什么是缓存未命中、缓存命中和命中率？缓存未命中是在缓存读取和缓存写入操作中，从慢速数据存储中获取数据并将其分配给缓存中的一个牺牲槽的操作。“写回”是指写入后备存储。本文从最简单的只读缓存形式开始，然后添加写缓存功能和优化。LRU 表示最近最少使用的数据将被新数据驱逐。缓存命中是指在缓存（和 RAM）中存在一个键，可以快速访问。命中率是指缓存命中次数与总（未命中+命中）访问次数的比例。
Using the Code
首先，为 LRU 对象构造函数定义一个单独的模块文件（最新版本：https://github.com/tugrul512bit/LruJS）
（这是源代码的初始版本，仅包含基本的读缓存，并侧重于简洁性。）
'use strict';
let Lru = function(cacheSize,callbackBackingStoreLoad,elementLifeTimeMs=1000){
let me = this;
let maxWait = elementLifeTimeMs;
let size = parseInt(cacheSize,10);
let mapping = {};
let mappingInFlightMiss = {};
let buf = [];
for(let i=0;i<size;i++)
{
let rnd = Math.random();
mapping[rnd] = i;
buf.push({data:"",visited:false, key:rnd, time:0, locked:false});
}
let ctr = 0;
let ctrEvict = parseInt(cacheSize/2,10);
let loadData = callbackBackingStoreLoad;
this.get = function(key,callbackPrm){
let callback = callbackPrm;
if(key in mappingInFlightMiss)
{
setTimeout(function(){
me.get(key,function(newData){
callback(newData);
});
},0);
return;
}
if(key in mapping)
{
// RAM speed data
if((Date.now() - buf[mapping[key]].time) > maxWait)
{
if(buf[mapping[key]].locked)
{
setTimeout(function(){
me.get(key,function(newData){
callback(newData);
});
},0);
}
else
{
delete mapping[key];
me.get(key,function(newData){
callback(newData);
});
}
}
else
{
buf[mapping[key]].visited=true;
buf[mapping[key]].time = Date.now();
callback(buf[mapping[key]].data);
}
}
else
{
// datastore loading + cache eviction
let ctrFound = -1;
while(ctrFound===-1)
{
if(!buf[ctr].locked && buf[ctr].visited)
{
buf[ctr].visited=false;
}
ctr++;
if(ctr >= size)
{
ctr=0;
}
if(!buf[ctrEvict].locked && !buf[ctrEvict].visited)
{
// evict
buf[ctrEvict].locked = true;
ctrFound = ctrEvict;
}
ctrEvict++;
if(ctrEvict >= size)
{
ctrEvict=0;
}
}
mappingInFlightMiss[key]=true;
let f = function(res){
delete mapping[buf[ctrFound].key];
buf[ctrFound] =
{data: res, visited:false, key:key, time:Date.now(), locked:false};
mapping[key] = ctrFound;
callback(buf[ctrFound].data);
delete mappingInFlightMiss[key];
};
loadData(key,f);
}
};
};
exports.Lru = Lru;
文件缓存示例
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 */);
Lru 构造函数接收参数（缓存大小、带有自身键和回调的缓存未命中回调、缓存元素生命周期）来构造 CLOCK 缓存。
异步缓存未命中回调的工作原理如下：
- 某些
get()调用在缓存中找不到键 - 算法找到一个牺牲槽
- 运行此回调
- 在回调内部，异步地进行昂贵的计算
- 在回调的最后，调用回调的回调将数据返回给 LRU 缓存
- 下次访问相同键时，其数据将从 RAM 中获取
为了保持简单，此实现只有一个 get() 方法。
fileCache.get("./test.js",function(dat){
httpResponse.writeHead(dat.stat);
httpResponse.end(dat.data);
});
由于结果数据有另一个回调，因此也可以异步运行。
它是如何工作的？
- 在大多数流行的 LRU 实现中，总会有一个从键到缓存槽的“映射”对象，以实现 O(1) 的键搜索时间复杂度（就缓存槽的数量而言）。这个实现也不例外。实际上，JavaScript 使这变得非常容易。
映射对象
let mapping = {};在映射中查找（字符串/整数）键
if(key in mapping) { // key found, get data from RAM }这很高效（O(1）且简单（至少比 C++ 版本简单得多）。
- 一旦映射指向一个缓存槽，就可以轻松地从中获取数据。
buf[mapping[key]].visited=true; buf[mapping[key]].time = Date.now(); callback(buf[mapping[key]].data);
visited标志用于通知 CLOCK 的指针（ctr和ctrEvict）保存此槽以避免被驱逐。time字段用于槽的生命周期管理。每次访问（缓存命中）都会刷新time字段，使其可以保留在缓存中。callback函数是用户为get()方法提供的用于检索缓存槽数据的函数。 - 在直接从映射槽获取数据之前，会测量其生命周期。如果已过期，则通过删除其映射并使用相同的键重试（这会导致缓存未命中）来使其失效。
if((Date.now() - buf[mapping[key]].time) > maxWait) { delete mapping[key]; me.get(key,function(newData){ callback(newData); }); }由于映射已被删除，因此没有其他异步访问会干扰其内部状态。
- 如果在映射对象中找不到键，则会运行 LRU 驱逐（实际上是其近似算法，具有 2 个指针的 CLOCK（又名二次机会））逻辑。寻找牺牲槽很容易。
let ctrFound = -1; while(ctrFound===-1) { if(!buf[ctr].locked && buf[ctr].visited) { buf[ctr].visited=false; } ctr++; if(ctr >= size) { ctr=0; } if(!buf[ctrEvict].locked && !buf[ctrEvict].visited) { // evict buf[ctrEvict].locked = true; ctrFound = ctrEvict; } ctrEvict++; if(ctrEvict >= size) { ctrEvict=0; } }第一个“
if”块检查由“二次机会”指针（ctr）指向的槽是否未锁定且已被访问。如果是，则作为第二次机会，它不会驱逐，而是将其标记为未访问。第三个“
if”块检查由“驱逐”指针（ctrEvict）指向的槽是否未锁定且未被访问。如果是，则将该槽标记为“locked”（以防止对get()方法的异步访问），找到牺牲槽，然后循环结束。请注意，两个指针
ctr和ctrEvict初始化时具有 50% 的相位差。let ctr = 0; let ctrEvict = parseInt(cacheSize/2,10);
而在“
while”循环中，它们以相同的方式递增。这意味着一个指针总是按顺序跟随另一个指针，以不断检查彼此的结果。缓存槽越多，牺牲槽的查找就越好。一个键至少需要 N/2 次时钟指针移动才能避免被驱逐。 - 找到牺牲槽后，将删除映射以避免未来的异步冲突，并在加载数据存储后重新创建映射。
mappingInFlightMiss[key]=true; let f = function(res){ delete mapping[buf[ctrFound].key]; buf[ctrFound] = {data: res, visited:false, key:key, time:Date.now(), locked:false}; mapping[key] = ctrFound; callback(buf[ctrFound].data); delete mappingInFlightMiss[key]; }; loadData(key,f);由于用户提供的数据存储加载函数（
loadData）可以是异步的，因此此缓存最多可以有 N 个正在进行的缓存未命中。这是一项优化，可以隐藏多达 N 个缓存未命中延迟。隐藏延迟对于提高吞吐量（尤其是在 Web 应用中每秒有数千名访问者时）至关重要。超过 N 个异步缓存未命中/访问会导致死锁，因此具有 100 个槽的缓存可以异步服务多达 100 个用户。或者，可以将其限制为低于 N 的较低值（M），并在多个（K）通道中进行计算（其中 M x K = 总访问次数）。由于可以隐藏缓存未命中，而缓存命中速度是 RAM 级别的，因此整体性能对于缓存未命中和缓存命中看起来都是 O(1)。但对于每个元素访问，每次访问可能需要多次时钟指针迭代，尤其是在缓存槽很少的情况下。当缓存槽数量增加时，它会接近 O(1)。
在此
loadData回调内部，新槽的locked字段被设置为false，这使得该槽可供其他异步访问使用。 - 如果发生缓存命中，并且找到的槽被锁定且其生命周期已过期，则访问操作会使用 0 时间参数的
setTimeout延迟（这比setImmediate更 CPU 友好）在 JavaScript 消息队列的末尾执行。已锁定的操作（缓存未命中）在此setTimeout之前结束的概率为 100%，并且在时间复杂度方面，这仍然计为 O(1)（延迟较大），但它被隐藏在已锁定操作的等待延迟后面。if(buf[mapping[key]].locked) { setTimeout(function(){ me.get(key,function(newData){ callback(newData); }); },0); } - 最后，如果某个键在正在进行的缓存未命中映射中，它将被推迟到消息队列的稍后位置，通过
setTimeout。if(key in mappingInFlightMiss) { setTimeout(function(){ me.get(key,function(newData){ callback(newData); }); },0); return; }这样就避免了数据重复。
基准测试
异步缓存未命中基准测试
"use strict";
// number of asynchronous accessors(1000 here) need to be equal to or less than
// cache size(1000 here) or it makes dead-lock
let Lru = require("./lrucache.js").Lru;
let cache = new Lru(1000, async function(key,callback){
// cache-miss data-load algorithm
setTimeout(function(){
callback(key+" processed");
},1000);
},1000 /* cache element lifetime */);
let ctr = 0;
let t1 = Date.now();
for(let i=0;i<1000;i++)
{
cache.get(i,function(data){
console.log("data:"+data+" key:"+i);
if(i.toString()+" processed" !== data)
{
console.log("error: wrong key-data mapping.");
}
if(++ctr === 1000)
{
console.log("benchmark: "+(Date.now()-t1)+" miliseconds");
}
});
}
为避免任何死锁，LRU 大小选择为 1000，或者 for 循环最多迭代 1000 次。
输出
benchmark: 1127 miliseconds
由于每次缓存未命中都有 1000 毫秒的延迟，同步加载 1000 个元素将花费 15 分钟，但通过重叠的缓存未命中，它会快得多。这在 I/O 繁重的工作负载（如从 HDD 或网络流式传输数据）中尤其有用。
缓存命中率基准测试
10% 的命中率
- 键生成：随机，可能值 10000 个
- 1000 个槽
"use strict";
// number of asynchronous accessors(1000 here) need to be equal to or less than
// cache size(1000 here) or it makes dead-lock
let Lru = require("./lrucache.js").Lru;
let cacheMiss = 0;
let cache = new Lru(1000, async function(key,callback){
cacheMiss++;
// cache-miss data-load algorithm
setTimeout(function(){
callback(key+" processed");
},100);
},100000000 /* cache element lifetime */);
let ctr = 0;
let t1 = Date.now();
let asynchronity = 500;
let benchRepeat = 100;
let access = 0;
function test()
{
ctr = 0;
for(let i=0;i<asynchronity;i++)
{
let key = parseInt(Math.random()*10000,10); // 10% hit ratio
cache.get(key.toString(),function(data){
access++;
if(key.toString()+" processed" !== data)
{
console.log("error: wrong key-data mapping.");
}
if(++ctr === asynchronity)
{
console.log("benchmark: "+(Date.now()-t1)+" miliseconds");
console.log("cache hit: "+(access - cacheMiss));
console.log("cache miss: "+(cacheMiss));
console.log("cache hit ratio: "+((access - cacheMiss)/access));
if(benchRepeat>0)
{
benchRepeat--;
test();
}
}
});
}
}
test();
结果
benchmark: 10498 miliseconds
cache hit: 6151
cache miss: 44349
cache hit ratio: 0.1218019801980198
由于基准测试分 100 步进行，每次缓存未命中延迟 100 毫秒，结果是 10 秒（接近 100 x 100 毫秒）。命中率接近预期的 10%。
50% 命中率测试
let key = parseInt(Math.random()*2000,10); // 50% hit ratio
Result:
benchmark: 10418 miliseconds
cache hit: 27541
cache miss: 22959
cache hit ratio: 0.5453663366336634
同样，接近预期的 50% 命中率。
99% 命中率测试
let key = parseInt(Math.random()*1010,10); // 99% hit ratio
Result:
benchmark: 10199 miliseconds
cache hit: 49156
cache miss: 1344
cache hit ratio: 0.9733861386138614
键的随机性导致了 0.9733 的命中率。
100% 命中率测试
let key = parseInt(Math.random()*999,10); // 100% hit ratio
结果
benchmark: 1463 miliseconds
cache hit: 49501
cache miss: 999
cache hit ratio: 0.9802178217821782
在基准测试的第一步（无法避免缓存未命中）之后，所有内容都来自 RAM，大大降低了总延迟。
关注点
异步代码中的错误很难发现。为了克服这个问题，我不得不使用一个调试器对象，该对象在每次函数调用时记录所有槽值及其各自的 Date.now() 时间，然后按每个元素的 time 字段对记录数组进行排序，并查看每个键访问的路径。这有点累人，但比仅仅盯着屏幕用眼睛跟踪 N 条路径要容易。
编辑：使用“update”方法，在“write”操作的情况下，可以从后备存储重新获取缓存项。最新版本（约 160 行代码）对异步进行了某些优化（并解决了死锁问题）。
'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
reload: evicts all cache to reload new values from backing store
reloadKey: only evicts selected item (to reload its new value on next access)
*/
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;
// refresh all cache content
this.reload=function(){
for(let i=0;i<size;i++)
{
bufTime[i]=0;
}
};
// refresh item in cache by triggering eviction
this.reloadKey=function(key){
if(key in mapping)
{
bufTime[mapping[key]]=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;
使用此版本，死锁不会永远发生，只会持续到正在进行的项获取数量减少到 N。刷新一个项
cache.reloadKey(someKey);
不会立即将新值写入缓存。只有当该项被 get 方法请求时才会发生，并且是异步的，与所有其他正在进行的缓存未命中异步进行。这比按需刷新具有更好的延迟隐藏效果，但每项的总延迟可能会增加，因为刷新被推迟到下一次“get”访问。
关于回调地狱？
由于这是一个基于回调的缓存，一次请求多个数据在公共同步点会导致类似这样的代码库。
cache.get(key1, function(data1){
cache.get(key2, function(data2){
cache.get(key3, function(data3)){
...
};
});
});
当一个像素值（图像处理应用）需要相邻的 25 个像素值时，情况会更糟。即使是代码最小化，与此相比也显得很不错。这个问题的解决方案很简单。
this.getMultiple = function(callback, ... keys){
let result = [];
let ctr = keys.length;
for(let i=0;i<ctr;i++)
result.push(0);
let ctr2 = 0;
keys.forEach(function(key){
let ctr3=ctr2++; // keep order of outputs
// async operation
me.get(key,function(data){
result[ctr3] = data;
ctr--;
if(ctr==0)
{
callback(result);
}
});
});
};
这里，使用可变参数函数，允许用户通过回调后的逗号分隔的键请求任意数量的值。由于没有像 C++ 那样的原子操作或多线程，因此只需要递减计数器即可检查所有操作是否完成。
每个操作都获取一个键的值并增加计数器。一旦获得最后一个异步数据，ctr 计数器将递减到零。然后，将带有结果数组的回调被调用。用法如下。
cache.getMultiple(function(dataArray){
console.log(dataArray); // [.., .., .., .., ..]
},"a key",5,"another key",someKeyVariable,"my last key");
这可以进一步优化，但为了用户的使用方便。JavaScript 中的Promise对此很有用。它们可以很容易地构造如下。
this.getAwaitable = function(key){
return new Promise( (success,fail)=>{
me.get(key, function(data){ success(data); });
});
};
然后从用户空间看起来是这样的。
let mySynchronizedValue = await cache.getAwaitable(myKey);
但这打破了异步缓存的目标。Await 使运行应用程序的 JavaScript 的（单个）线程等待该值，并且无法在同一作用域中启动新的缓存获取操作。为了稍微优化一下，用户可以这样编写。
// all asynchronous, starts working as soon as their Promise is created
let myAsync1 = cache.getAwaitable(myKey1);
let myAsync2 = cache.getAwaitable(myKey2);
let myAsync3 = cache.getAwaitable(myKey3);
// synchronized between each other, only waits completion of all 3 operations
let mySync1 = await myAsync1;
let mySync2 = await myAsync2;
let mySync3 = await myAsync3;
此外，在紧密循环中使用Promise（分配/释放资源）比纯回调慢，因为Promise在后台执行更多操作，并且它们通常在构造后立即“await”（这会降低与自由运行回调相比的并发性）。下面的代码是来自 github 的最新源代码，其中包含更多优化和功能。
'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
reload: evicts all cache to reload new values from backing store
reloadKey: only evicts selected item (to reload its new value on next access)
*/
let Lru = function(cacheSize,callbackBackingStoreLoad,
elementLifeTimeMs=1000,callbackBackingStoreSave){
const me = this;
const aTypeGet = 0;
const aTypeSet = 1;
const maxWait = elementLifeTimeMs;
const size = parseInt(cacheSize,10);
const mapping = new Map();
const mappingInFlightMiss = new Map();
const bufData = new Array(size);
const bufVisited = new Uint8Array(size);
const bufEdited = 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.set(rnd,i);
bufData[i]="";
bufVisited[i]=0;
bufEdited[i]=0;
bufKey[i]=rnd;
bufTime[i]=0;
bufLocked[i]=0;
}
let ctr = 0;
let ctrEvict = parseInt(cacheSize/2,10);
const loadData = callbackBackingStoreLoad;
const saveData = callbackBackingStoreSave;
let inFlightMissCtr = 0;
// refresh all items time-span in cache
this.reload=function(){
for(let i=0;i<size;i++)
{
bufTime[i]=0;
}
};
// refresh item time-span in cache by triggering eviction
this.reloadKey=function(key){
if(mapping.has(key))
{
bufTime[mapping[key]]=0;
}
};
// get value by key
this.get = function(keyPrm,callbackPrm){
// aType=0: get
access(keyPrm,callbackPrm,aTypeGet);
};
// set value by key (callback returns same value)
this.set = function(keyPrm,valuePrm,callbackPrm){
// aType=1: set
access(keyPrm,callbackPrm,aTypeSet,valuePrm);
};
// aType=0: get
// aType=1: set
function access(keyPrm,callbackPrm,aType,valuePrm){
const key = keyPrm;
const callback = callbackPrm;
const value = valuePrm;
// stop dead-lock when many async get calls are made
if(inFlightMissCtr>=size)
{
setTimeout(function(){
// get/set
access(key,function(newData){
callback(newData);
},aType,value);
},0);
return;
}
// if key is busy, then delay the request towards end of the cache-miss completion
if(mappingInFlightMiss.has(key))
{
setTimeout(function(){
// get/set
access(key,function(newData){
callback(newData);
},aType,value);
},0);
return;
}
if(mapping.has(key))
{
// slot is an element in the circular buffer of CLOCK algorithm
let slot = mapping.get(key);
// RAM speed data
if((Date.now() - bufTime[slot]) > maxWait)
{
// if slot is locked by another operation, postpone the current operation
if(bufLocked[slot])
{
setTimeout(function(){
access(key,function(newData){
callback(newData);
},aType,value);
},0);
}
else // slot is not locked and its lifespan has ended
{
// if it was edited, update the backing-store first
if(bufEdited[slot] == 1)
{
bufLocked[slot] = 1;
bufEdited[slot]=0;
mappingInFlightMiss.set(key,1); // lock key
inFlightMissCtr++;
// update backing-store, this is async
saveData(bufKey[slot],bufData[slot],function(){
mappingInFlightMiss.delete(key); // unlock key
bufLocked[slot] = 0;
inFlightMissCtr--;
mapping.delete(key); // disable mapping for current key
// re-simulate the access, async
access(key,function(newData){
callback(newData);
},aType,value);
});
}
else
{
mapping.delete(key); // disable mapping for current key
access(key,function(newData){
callback(newData);
},aType,value);
}
}
}
else // slot life span has not ended
{
bufVisited[slot]=1;
bufTime[slot] = Date.now();
// if it is a "set" operation
if(aType == aTypeSet)
{
bufEdited[slot] = 1; // later used when data needs to be written
// to data-store (write-cache feature)
bufData[slot] = value;
}
callback(bufData[slot]);
}
}
else
{
// datastore loading + cache eviction
let ctrFound = -1;
let oldVal = 0;
let oldKey = 0;
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])
{
// eviction preparations, lock the slot
bufLocked[ctrEvict] = 1;
inFlightMissCtr++;
ctrFound = ctrEvict;
oldVal = bufData[ctrFound];
oldKey = bufKey[ctrFound];
}
ctrEvict++;
if(ctrEvict >= size)
{
ctrEvict=0;
}
}
// user-requested key is now asynchronously in-flight &
// locked for other operations
mappingInFlightMiss.set(key,1);
// eviction function. least recently used data is gone,
// newest recently used data is assigned
let evict = function(res){
mapping.delete(bufKey[ctrFound]);
bufData[ctrFound]=res;
bufVisited[ctrFound]=0;
bufKey[ctrFound]=key;
bufTime[ctrFound]=Date.now();
bufLocked[ctrFound]=0;
mapping.set(key,ctrFound);
callback(res);
inFlightMissCtr--;
mappingInFlightMiss.delete(key);
};
// if old data was edited, send it to data-store first, then fetch new data
if(bufEdited[ctrFound] == 1)
{
if(aType == aTypeGet)
bufEdited[ctrFound] = 0;
// old edited data is sent back to data-store
saveData(oldKey,oldVal,function(){
if(aType == aTypeGet)
loadData(key,evict);
else if(aType == aTypeSet)
evict(value);
});
}
else
{
if(aType == aTypeSet)
bufEdited[ctrFound] = 1;
if(aType == aTypeGet)
loadData(key,evict);
else if(aType == aTypeSet)
evict(value);
}
}
};
this.getAwaitable = function(key){
return new Promise(function(success,fail){
me.get(key,function(data){
success(data);
});
});
}
this.setAwaitable = function(key,value){
return new Promise(function(success,fail){
me.set(key,value,function(data){
success(data);
});
});
}
this.getMultiple = function(callback, ... keys){
let result = [];
let ctr1 = keys.length;
for(let i=0;i<ctr1;i++)
result.push(0);
let ctr2 = 0;
keys.forEach(function(key){
let ctr3 = ctr2++;
me.get(key,function(data){
result[ctr3] = data;
ctr1--;
if(ctr1==0)
{
callback(result);
}
});
});
};
this.setMultiple = function(callback, ... keyValuePairs){
let result = [];
let ctr1 = keys.length;
for(let i=0;i<ctr1;i++)
result.push(0);
let ctr2 = 0;
keyValuePairs.forEach(function(pair){
let ctr3 = ctr2++;
me.set(pair.key,pair.value,function(data){
result[ctr3] = data;
ctr1--;
if(ctr1==0)
{
callback(result);
}
});
});
};
this.getMultipleAwaitable = function(... keys){
return new Promise(function(success,fail){
me.getMultiple(function(results){
success(results);
}, ... keys);
});
};
this.setMultipleAwaitable = function(... keyValuePairs){
return new Promise(function(success,fail){
me.setMultiple(function(results){
success(results);
}, ... keyValuePairs);
});
};
// push all edited slots to backing-store and reset all slots lifetime
// to "out of date"
this.flush = function(callback){
let ctr1 = 0;
function waitForReadWrite(callbackW){
// if there are in-flight cache-misses cache-write-misses
// or active slot locks, then wait
if(mappingInFlightMiss.size > 0 ||
bufLocked.reduce((e1,e2)=>{return e1+e2;}) > 0)
{
setTimeout(()=>{ waitForReadWrite(callbackW); },0);
}
else
callbackW();
}
waitForReadWrite(function(){
// flush all slots
for(let i=0;i<size;i++)
{
bufTime[i]=0;
if(bufEdited[i] == 1)
ctr1++;
}
for(let i=0;i<size;i++)
{
if(bufEdited[i] == 1)
{
// async
me.set(bufKey[i],bufData[i],function(val){
ctr1--;
if(ctr1 == 0)
{
callback(); // flush complete
}
});
}
}
});
};
};
exports.Lru = Lru;
以下基准测试结果来自一个旧版本，其中映射由简单的 { } 对象维护。
通过完全异步的值请求数千个文件、文件块、http 请求和其他任务，JavaScript 语言的性能劣势被最小化。
更多优化
在使缓存正常工作后，可以进行更多优化。其中之一是不要使用简单的对象进行映射。（完整源代码的最新版本在基准测试部分之后，在文章末尾。）
let mapping = {}; // sub-optimal performance, sometimes breaks running
因为这会阻止程序输入 "__proto__" 或类似的 JavaScript 特定 string 作为键。与其微调基本对象以应对这些故障，不如应该由为此设计的数据结构来处理。
let mapping = new Map(); // faster than {} and even objects can be keys now
由于 Map 实现为哈希表或红黑树，其 get/set/has/size 方法经过优化，具有摊销 O(1) 时间复杂度。使用 Map 时，重要的是不要将其与普通对象混淆。可能会意外地这样做。
let mapping = new Map();
mapping[aKey] = aValue; // this sets object { } properties instead
这不会使用其优化方法。必须直接这样使用。
let mapping = new Map();
mapping.set(aKey,aValue)); // optimized for frequent calls
mapping.get(aKey); // optimized for frequent calls
Map 的另一个特点是具有更高的最大缓存大小，因为它在内存占用方面比简单对象更高效。能够容纳更多缓存项也使其适用于不同类型的工作。使用这个管理中等规模的数据库是可能的。
尽管 Map 在内存效率方面更好，但正在进行的 get/set 操作的数量会暂时增加内存消耗。当缓存大小为 25 个元素（32 位整数键，64 位浮点值）且并发度为 5 时，NodeJs 应用程序消耗高达 45 MB 用于处理 400x400 图像数据。当并发度为 800000 时，内存消耗从 105MB 开始增长到 225MB，尽管缓存中只有 25 个元素，因为有 800k 个项目在队列中等待进入缓存的 25 个槽。分配100 万个元素（缓存槽）的缓存并具有5 并发度（一次请求 5 个像素），内存消耗为140MB-280MB，具体取决于垃圾回收器的活动。当并发度增加到 800000（所有循环迭代都异步进行）时，需求增加到 370MB。正在进行的缓存未命中函数会导致更高的内存需求，但在并发度不高时可以忽略不计。
需要至少 140MB 的 100 万个元素缓存相当于每个缓存项 140 字节。这是为异步操作进行簿记的成本，以隐藏多个后备存储延迟（以提高性能/易用性），同时保持每毫秒数千次操作的吞吐量。
与其他具有自身缓存的内存数据库进行比较。
- Redis 100 万个小项成本 85MB 内存。
- Hazelcast 100 万个项目成本至少 50MB 内存。
与其他 LRU 缓存算法的 Github 存储库进行比较。
- Isaac 的 LRU 缓存：0.8 百万个键 = ~64 MB（根据 issues 标签中的基准测试）
- Karlseguin 的高并发缓存：100 万个键 = 350 MB（根据自述文件）
将普通对象替换为 Map 后，缓存的构造部分以这个开始。
const mapping = new Map(); // key --> value mapping
const mappingInFlightMiss = new Map(); // key --> busy? mapping
const bufData = new Array(size); // value of cache slots
const bufVisited = new Uint8Array(size); // second chance status of cache slots
const bufEdited = new Uint8Array(size); // edited status of cache slots
const bufKey = new Array(size); // keys of cache slots
const bufTime = new Float64Array(size); // life-span info of cache slots
const bufLocked = new Uint8Array(size); // slot busy status of cache slots
在第一个版本中，只有一个 buf 通用数组来保存所有缓存槽的状态信息。但在这里，一个“缓存槽”（循环缓冲区元素）的所有变量都被分开，以避免每次需要一个 8 位值时都加载整个槽。这有助于低端系统保持最低性能，并使 CPU 缓存污染更少，这对所有类型的系统都有好处。测试系统只有 9-10 GB/s 的内存带宽，并从这项优化中受益。
写缓存
下一件重要的事情是将“写入”操作卸载到缓存。在此之前，如果用户需要更新后备存储，则需要直接（缓慢地）完成，然后调用缓存上的 reloadKey() 以通过 get() 方法获取最新信息。在产品画廊网站上，这不像访问网站的客户端那样频繁更新产品信息/用户信息/网页内容/附加图像，因此不是那么重要。但一旦需要高效的数据更新，缓存是一个不错的选择。写缓存可以在从论坛到开放世界游戏的许多应用程序中有用。特别是在开放世界游戏中，当玩家改变世界数据时，玩家再次访问同一地点时需要记住它，但又不会溢出 RAM 并且比 HDD 快。
向缓存添加“set”方法不仅可以减少额外的 API 调用（如 reloadKey() ），还可以提高写入性能，类似于读取性能，因为它使用相同的 LRU 驱逐，代码只有少量更改。为了将写缓存功能添加到算法中，需要一个名为“bufEdited”的额外状态字段。
每当数据写入缓存槽时，缓存槽的“edited”状态将更改为 1。当数据更新到后备存储时，它被设置为 0。Edited 相当于“需要在后备存储上更新”或换句话说，“脏位”。
由于写入和读取操作都运行在相同的驱逐算法上，因此无需重复驱逐特定代码。get()/set() 方法成为隐藏的 access() 方法的包装器。Access 方法接受更多参数以选择 get 或 set 算法。
function access(keyPrm,callbackPrm,aType,valuePrm){ .. }
aType 参数选择操作类型。如果它是 aTypeGet（0），则运行 get 操作，否则（aTypeSet）它是 set 操作。然后有一个 valuePrm 参数用于 set 操作，该操作将 valuePrm 分配给具有 keyPrm 键的数据槽。
此外，缓存不知道后备存储是什么以及如何执行写入。它像构造函数中提供的缓存未命中函数一样，由用户提供。
let cache = new Lru(cacheSize,
callbackBackingStoreLoad,
elementLifeTimeMs,
callbackBackingStoreSave);
当缓存槽具有“edited”状态并需要更新后备存储时，缓存会调用 callbackBackingStoreSave 函数。缓存调用它并带有 3 个参数：Key、value 和一个 callback。
let cache = new Lru(cacheSize,
callbackBackingStoreLoad,
elementLifeTimeMs,
function(key,value,callback){
backing_store[key] = value;
callback();
});
此用户定义的函数是驱逐算法的数据存储部分。callbackBackingStoreLoad 是读取缓存未命中驱逐的数据加载部分。由于通用缓存不知道如何处理 SSD 或数据库，因此用户通过回调提供必要的详细信息。
实现中执行后备存储“写入”的第一部分是过时分支（当缓存项的时间已过期时）。
...
else // slot is not locked and its lifespan has ended
{
// if it was edited, update the backing-store first
if(bufEdited[slot] == 1)
{
bufLocked[slot] = 1;
bufEdited[slot]=0;
mappingInFlightMiss.set(key,1); // lock key
inFlightMissCtr++;
// update backing-store, this is async
saveData(bufKey[slot],bufData[slot],function(){
mappingInFlightMiss.delete(key); // unlock key
bufLocked[slot] = 0;
inFlightMissCtr--;
mapping.delete(key); // disable mapping for current key
// re-simulate the access, async
access(key,function(newData){
callback(newData);
},aType,value);
});
}
else // not edited, can be discarded
{
mapping.delete(key); // disable mapping for current key
access(key,function(newData){
callback(newData);
},aType,value);
}
}
这部分做了什么。
- 阻止其他正在进行的写入操作进入同一缓存槽或使用同一键。
- 这对于避免重复很重要。
- 清除已编辑状态。
- 因为很快就会写入后备存储。
- 将数据保存到后备存储（可能异步写入数据库或文件）。
- 用户定义的函数。
- 写入完成后，解锁键和槽。
- 从映射中删除键以“释放”用于驱逐目的的槽。
- 重新发出相同的访问（get/set）。
- 重新发出的访问找到另一个槽来工作。
第二部分发生写入操作是在驱逐附近。
// if old data was edited, send it to data-store first, then fetch new data
if(bufEdited[ctrFound] == 1)
{
if(aType == aTypeGet)
bufEdited[ctrFound] = 0;
// old edited data is sent back to data-store
saveData(oldKey,oldVal,function(){
if(aType == aTypeGet)
loadData(key,evict);
else if(aType == aTypeSet)
evict(value);
});
}
else
{
if(aType == aTypeSet)
bufEdited[ctrFound] = 1;
if(aType == aTypeGet)
loadData(key,evict);
else if(aType == aTypeSet)
evict(value);
}
驱逐很简单。找到牺牲槽没有改变，但数据更新部分已更改。
- 如果槽被编辑过，
- 如果是
get()操作，则清除已编辑状态。 - 将数据保存到后备存储。
- 如果是
get()操作，则加载新数据，然后驱逐。 - 如果是
set()操作，则只需驱逐。
- 如果是
- else
- 如果是
set()操作，则设置已编辑状态。 - 如果是
get()，则加载数据，然后驱逐。- 如果是
set()，则只需驱逐。
- 如果是
- 如果是
由于缓存负责最新写入的位以及非常旧的写入数据，因此需要一个 flush() 方法来最终将所有具有已编辑状态（但尚未驱逐）的槽写入。此缓存实现是无源的，因此仅在调用 get 和 set 时才工作。因此，通过旧的 set() 调用的一些数据可能未到达后备存储。这由 flush() 调用维护。
// push all edited slots to backing-store and reset all slots lifetime to "out of date"
this.flush = function(callback){
function waitForReadWrite(callbackW){
// if there are in-flight cache-misses cache-write-misses or active slot locks, then wait
if(mappingInFlightMiss.size > 0 || bufLocked.reduce((e1,e2)=>{return e1+e2;}) > 0)
{
setTimeout(()=>{ waitForReadWrite(callbackW); },0);
}
else
callbackW();
}
waitForReadWrite(function(){
for(let i=0;i<size;i++)
{
bufTime[i]=0;
if(bufEdited[i] == 1)
{
// synced flushing = better stability when cache is big
await me.setAwaitable(bufKey[i],bufData[i]);
}
}
callback(); // flush complete
});
};
};
- 等待所有正在进行的缓存未命中（所有
set和get调用）。 - 模拟所有已编辑槽上的
set操作，以间接更新后备存储。
当缓存位于数据库前面时（以减少数据库的读写频率），在关闭应用程序之前或在一定间隔后，应将最新的未写入数据刷新到数据库。在 flush 之前发出的所有操作都保证会发送到后备存储，但在此期间发出的任何操作都不会。
基准测试
测试系统：FX8150 @ 2.1GHz，1 通道 DDR3 1600 MHz 4GB RAM，Ubuntu 18.04 LTS 64bit。
峰值读缓存命中性能测试
- 读取次数：100 万
- 并发度：5000
- 缓存大小：1000 个元素
- 访问：固定索引（5）强制除第一次访问外的所有访问都缓存读取命中。
"use strict";
let N_bench_repeats = 10;
let N_access = 1000000;
let N_concurrency = 5000;
let Lru = require("./lrucache.js").Lru;
let cache_elements = 1000;
let cache_element_expire_ms = 100000;
let cache = new Lru(cache_elements, async function(key,callback){
// simulated slow access
setTimeout(function(){
callback(Math.random() /* database[key] */);
},100);
},cache_element_expire_ms, async function(key,value,callback){
// simulated slow access
setTimeout(function(){
// database[key]=value;
callback();
},100);
});
async function benchmark(){
let request_keys = [];
for(let j=0;j<N_concurrency;j++)
{
request_keys.push(5);
}
let bench_time = Date.now();
for(let i=0;i<N_access;i+=N_concurrency)
{
/* constant key = only 1 database-read should happen */
let values = await cache.getMultipleAwaitable(... request_keys);
}
console.log("run-time: "+(Date.now() - bench_time)+"ms");
console.log("------------------------------------------");
}
function repeat(){
N_bench_repeats--;
if(N_bench_repeats>0)
benchmark().then(repeat);
}
repeat();
输出
run-time: 926ms
------------------------------------------
run-time: 705ms
------------------------------------------
run-time: 676ms
------------------------------------------
run-time: 682ms
------------------------------------------
run-time: 679ms
------------------------------------------
run-time: 681ms
------------------------------------------
run-time: 682ms
------------------------------------------
run-time: 685ms
------------------------------------------
run-time: 679ms
------------------------------------------
100 万次读取 680 毫秒相当于每毫秒 1470 次读取。
峰值写缓存命中性能测试
与读取版本相同，区别在于调用了 setMultipleAwaitable 方法，并将键值对数组传递给该方法。
async function benchmark(){
let pairs = [];
for(let j=0;j<N_concurrency;j++)
{
pairs.push({key:5, value:100});
}
let bench_time = Date.now();
for(let i=0;i<N_access;i+=N_concurrency)
{
/* constant key = only 1 database-read should happen */
let values = await cache.setMultipleAwaitable(... pairs);
}
console.log("run-time: "+(Date.now() - bench_time)+"ms");
console.log("------------------------------------------");
}
输出
run-time: 717ms
------------------------------------------
run-time: 662ms
------------------------------------------
run-time: 672ms
------------------------------------------
run-time: 662ms
------------------------------------------
run-time: 649ms
------------------------------------------
run-time: 645ms
------------------------------------------
run-time: 648ms
------------------------------------------
run-time: 649ms
------------------------------------------
run-time: 643ms
------------------------------------------
这是每毫秒 1550 次写入。
每秒约 150 万次读/写足以满足一些开放世界视频游戏的纹理、几何图形、任何世界数据（只要玩家不超出缓存内容）或可能无法装入 RAM 的数千个训练数据的 AI 程序。
峰值写缓存未命中性能测试
为了测试写缓存未命中性能，基准应用程序使用了 100% 的唯一键访问。所有访问都通过后备存储。换句话说，0% 缓存命中。
- 读取次数：100 万
- 并发度：5000
- 缓存大小：1000 个元素
- 访问：唯一键强制除第一次访问外的所有访问都缓存写入未命中。
"use strict";
let N_bench_repeats = 10;
let N_access = 1000000;
let N_concurrency = 5000;
let Lru = require("./lrucache.js").Lru;
let cache_elements = 1000;
let cache_element_expire_ms = 100000;
let cache = new Lru(cache_elements, async function(key,callback){
// simulated slow access
setTimeout(function(){
callback(Math.random() /* database[key] */);
},10);
},cache_element_expire_ms, async function(key,value,callback){
// simulated slow access
setTimeout(function(){
// database[key]=value;
callback();
},10);
});
let unique_id = 0;
async function benchmark(){
let pairs = [];
for(let j=0;j<N_concurrency;j++)
{
pairs.push({key:unique_id++, value:Math.random()});
}
let bench_time = Date.now();
for(let i=0;i<N_access;i+=N_concurrency)
{
/* constant key = only 1 database-read should happen */
let values = await cache.setMultipleAwaitable(... pairs);
}
console.log("run-time: "+(Date.now() - bench_time)+"ms");
console.log("------------------------------------------");
}
function repeat(){
N_bench_repeats--;
if(N_bench_repeats>0)
benchmark().then(repeat);
}
repeat();
10 毫秒后备存储延迟。
run-time: 17768ms
------------------------------------------
run-time: 17540ms
------------------------------------------
run-time: 17753ms
------------------------------------------
1 毫秒后备存储延迟。
run-time: 6092ms
------------------------------------------
run-time: 5786ms
------------------------------------------
run-time: 5656ms
------------------------------------------
run-time: 5660ms
------------------------------------------
零延迟后备存储（假设它仍然可以并发提供数据）。
run-time: 6010ms
------------------------------------------
run-time: 5683ms
------------------------------------------
run-time: 5704ms
------------------------------------------
run-time: 5663ms
------------------------------------------
同步后备存储（在缓存未命中参数中移除 setTimeout）。
run-time: 1348ms
------------------------------------------
run-time: 1186ms
------------------------------------------
run-time: 1181ms
------------------------------------------
run-time: 1177ms
------------------------------------------
run-time: 1175ms
------------------------------------------
run-time: 1171ms
------------------------------------------
写缓存未命中性能更多地取决于后备存储性能，其峰值是每 1000000 次操作 1171 毫秒，或每毫秒 853 次缓存未命中。
峰值读缓存未命中性能测试
"use strict";
let N_bench_repeats = 10;
let N_access = 1000000;
let N_concurrency = 5000;
let Lru = require("./lrucache.js").Lru;
let cache_elements = 1000;
let cache_element_expire_ms = 100000;
let cache = new Lru(cache_elements, async function(key,callback){
// simulated slow access
setTimeout(function(){
callback(Math.random() /* database[key] */);
},10);
},cache_element_expire_ms, async function(key,value,callback){
// simulated slow access
setTimeout(function(){
// database[key]=value;
callback();
},10);
});
let unique_id = 0;
async function benchmark(){
let keys = [];
for(let j=0;j<N_concurrency;j++)
{
keys.push(unique_id++);
}
let bench_time = Date.now();
for(let i=0;i<N_access;i+=N_concurrency)
{
/* constant key = only 1 database-read should happen */
let values = await cache.getMultipleAwaitable(... keys);
}
console.log("run-time: "+(Date.now() - bench_time)+"ms");
console.log("------------------------------------------");
}
function repeat(){
N_bench_repeats--;
if(N_bench_repeats>0)
benchmark().then(repeat);
}
repeat();
10 毫秒后备存储延迟。
run-time: 18255ms
------------------------------------------
run-time: 18033ms
------------------------------------------
run-time: 18248ms
------------------------------------------
1 毫秒后备存储延迟。
run-time: 6039ms
------------------------------------------
run-time: 5759ms
------------------------------------------
run-time: 5786ms
------------------------------------------
零延迟后备存储。
run-time: 5998ms
------------------------------------------
run-time: 5789ms
------------------------------------------
run-time: 5818ms
------------------------------------------
同步后备存储（在缓存未命中参数中移除 setTimeout）。
run-time: 1357ms
------------------------------------------
run-time: 1209ms
------------------------------------------
run-time: 1191ms
------------------------------------------
峰值缓存读取未命中性能是每毫秒 839 次读取。
当后备存储延迟为 10 毫秒时，100 万次操作的总延迟约为3 小时。异步缓存将3 小时的串行读取会话时间缩短到18 秒。隐藏比率为 3 小时 / 18 秒 = 600。
尽管将并发度设置为 5000，但对于此特定基准测试代码（setTimeout = 10 毫秒设置），有效并发度为 600。这可能是 NodeJs（v14）或操作系统或某些其他因素（1 通道内存 = 仅 9-10 GB/s）的限制。
随机读写组合性能测试
- 读取次数：100 万，在一个 100 万长度的纯 Js 数组上。
- 写入次数：100 万，在同一个数组上使用相同的缓存。
- 并发度：5000 x2。
- 缓存大小：500k 个元素。
- 访问：0 到 999999 之间的随机键，以强制对读取和写入进行 50% 的缓存命中与未命中。
"use strict";
let N_bench_repeats = 10;
let N_access = 1000000;
let N_concurrency = 5000;
let backing_store = {};
let cache_read_miss = 0;
let cache_write_miss = 0;
for(let i=0;i<N_access;i++)
{
backing_store[i]=i;
}
let Lru = require("./lrucache.js").Lru;
let cache_elements = 500000;
let cache_element_expire_ms = 100000;
let cache = new Lru(cache_elements, async function(key,callback){
// simulated slow access
cache_read_miss++;
callback(backing_store[key]);
},cache_element_expire_ms, async function(key,value,callback){
// simulated slow access
cache_write_miss++;
backing_store[key]=value;
callback();
});
async function benchmark(){
cache_read_miss = 0;
cache_write_miss = 0;
let bench_time = Date.now();
for(let i=0;i<N_access;i+=N_concurrency)
{
let ctr = 0;
let res = new Promise((success,fail)=>{
for(let j=0;j<N_concurrency;j++)
{
cache.get(Math.floor(Math.random()*N_access),
function(data){ ctr++; if(ctr==N_concurrency) success(1);});
cache.set(Math.floor(Math.random()*N_access), Math.random(),
function(data){ ctr++; if(ctr==N_concurrency) success(1);});
}
});
res = await res;
}
console.log("run-time: "+(Date.now() - bench_time)+"ms");
console.log("cache-read-hit-ratio: "+
(100*(N_access - cache_read_miss)/(N_access))+"%");
console.log("cache-write-hit-ratio: "+
(100*(N_access - cache_write_miss)/(N_access))+"%");
console.log("total-hit-ratio: "+
(100*(2*N_access - cache_write_miss - cache_read_miss)/(2*N_access))+"%");
console.log("------------------------------------------");
}
function repeat(){
N_bench_repeats--;
if(N_bench_repeats>0)
benchmark().then(repeat);
}
repeat();
输出
>
run-time: 4392ms
cache-read-hit-ratio: 42.3823%
cache-write-hit-ratio: 59.5218%
total-hit-ratio: 50.95205%
------------------------------------------
run-time: 3712ms
cache-read-hit-ratio: 49.9964%
cache-write-hit-ratio: 33.3312%
total-hit-ratio: 41.6638%
------------------------------------------
run-time: 3909ms
cache-read-hit-ratio: 49.9807%
cache-write-hit-ratio: 33.296%
total-hit-ratio: 41.63835%
------------------------------------------
run-time: 4123ms
cache-read-hit-ratio: 49.9926%
cache-write-hit-ratio: 33.2964%
total-hit-ratio: 41.6445%
------------------------------------------
run-time: 3943ms
cache-read-hit-ratio: 50.0449%
cache-write-hit-ratio: 33.3457%
total-hit-ratio: 41.6953%
------------------------------------------
run-time: 4102ms
cache-read-hit-ratio: 49.9443%
cache-write-hit-ratio: 33.3026%
total-hit-ratio: 41.62345%
------------------------------------------
run-time: 3816ms
cache-read-hit-ratio: 50.0713%
cache-write-hit-ratio: 33.2516%
total-hit-ratio: 41.66145%
------------------------------------------
执行 200 万次操作 3816 毫秒 =每毫秒 524 次操作。这是在缓存大小为数据集一半的情况下，同一循环中混合读写操作的性能。读取操作仍然可能强制驱逐已编辑的页面（并导致写入未命中），但写入操作不会导致任何额外的缓存读取未命中，这就是为什么缓存写入比率下降的原因。
缓存大小 = 800k（数据集的 80%）。
run-time: 3724ms
cache-read-hit-ratio: 56.1437%
cache-write-hit-ratio: 95.1107%
total-hit-ratio: 75.6272%
------------------------------------------
run-time: 3143ms
cache-read-hit-ratio: 79.9688%
cache-write-hit-ratio: 70.1968%
total-hit-ratio: 75.0828%
------------------------------------------
run-time: 3406ms
cache-read-hit-ratio: 79.9668%
cache-write-hit-ratio: 66.9695%
total-hit-ratio: 73.46815%
------------------------------------------
run-time: 3078ms
cache-read-hit-ratio: 80.0162%
cache-write-hit-ratio: 66.612%
total-hit-ratio: 73.3141%
------------------------------------------
run-time: 3379ms
cache-read-hit-ratio: 80.0395%
cache-write-hit-ratio: 66.5492%
total-hit-ratio: 73.29435%
------------------------------------------
run-time: 3536ms
cache-read-hit-ratio: 79.9812%
cache-write-hit-ratio: 66.5147%
total-hit-ratio: 73.24795%
------------------------------------------
run-time: 3089ms
cache-read-hit-ratio: 79.9878%
cache-write-hit-ratio: 66.5399%
total-hit-ratio: 73.26385%
------------------------------------------
缓存大小 = 990k（数据集的 99%）。
run-time: 4558ms
cache-read-hit-ratio: 56.7343%
cache-write-hit-ratio: 100%
total-hit-ratio: 78.36715%
------------------------------------------
run-time: 2916ms
cache-read-hit-ratio: 94.1668%
cache-write-hit-ratio: 100%
total-hit-ratio: 97.0834%
------------------------------------------
run-time: 2757ms
cache-read-hit-ratio: 98.8937%
cache-write-hit-ratio: 98.9428%
total-hit-ratio: 98.91825%
------------------------------------------
run-time: 2708ms
cache-read-hit-ratio: 98.9939%
cache-write-hit-ratio: 98.1394%
total-hit-ratio: 98.56665%
------------------------------------------
run-time: 2749ms
cache-read-hit-ratio: 99.0013%
cache-write-hit-ratio: 98.1331%
total-hit-ratio: 98.5672%
------------------------------------------
顺序写读组合性能测试
- 读取次数：100 万，在一个 100 万长度的纯 Js 数组上。
- 写入次数：100 万，在同一个数组上使用相同的缓存和相同的键，但就在读取之前。
- 并发度：5000 x2。
- 缓存大小：500k 个元素。
- 访问：0 到 999999 之间的顺序键。
"use strict";
let N_bench_repeats = 10;
let N_access = 1000000;
let N_concurrency = 5000;
let backing_store = {};
let cache_read_miss = 0;
let cache_write_miss = 0;
for(let i=0;i<N_access;i++)
{
backing_store[i]=i;
}
let Lru = require("./lrucache.js").Lru;
let cache_elements = 500000;
let cache_element_expire_ms = 100000;
let cache = new Lru(cache_elements, async function(key,callback){
// simulated slow access
cache_read_miss++;
callback(backing_store[key]);
},cache_element_expire_ms, async function(key,value,callback){
// simulated slow access
cache_write_miss++;
backing_store[key]=value;
callback();
});
async function benchmark(){
cache_read_miss = 0;
cache_write_miss = 0;
let bench_time = Date.now();
for(let i=0;i<N_access;i+=N_concurrency)
{
let ctr = 0;
let res = new Promise((success,fail)=>{
for(let j=0;j<N_concurrency;j++)
{
cache.set(i+j, Math.random(),function(data)
{ ctr++; if(ctr==N_concurrency) success(1);});
cache.get(i+j, function(data)
{ ctr++; if(ctr==N_concurrency) success(1);});
}
});
res = await res;
}
console.log("run-time: "+(Date.now() - bench_time)+"ms");
console.log("cache-read-hit-ratio: "+
(100*(N_access - cache_read_miss)/(N_access))+"%");
console.log("cache-write-hit-ratio: "+
(100*(N_access - cache_write_miss)/(N_access))+"%");
console.log("total-hit-ratio: "+
(100*(2*N_access - cache_write_miss - cache_read_miss)/(2*N_access))+"%");
console.log("------------------------------------------");
}
function repeat(){
N_bench_repeats--;
if(N_bench_repeats>0)
benchmark().then(repeat);
}
repeat();
输出
run-time: 3160ms
cache-read-hit-ratio: 100%
cache-write-hit-ratio: 50%
total-hit-ratio: 75%
------------------------------------------
run-time: 2862ms
cache-read-hit-ratio: 100%
cache-write-hit-ratio: 0%
total-hit-ratio: 50%
------------------------------------------
run-time: 2869ms
cache-read-hit-ratio: 100%
cache-write-hit-ratio: 0%
total-hit-ratio: 50%
------------------------------------------
run-time: 2820ms
cache-read-hit-ratio: 100%
cache-write-hit-ratio: 0%
total-hit-ratio: 50%
读取操作总是受益于相同键的写入操作，但第二次重复后每次写入都会导致写入未命中，因为写入没有数据重用。
缓存的最新版本源代码。
'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
reload: evicts all cache to reload new values from backing store
reloadKey: only evicts selected item (to reload its new value on next access)
*/
let Lru = function(cacheSize,callbackBackingStoreLoad,elementLifeTimeMs=1000,
callbackBackingStoreSave){
const me = this;
const aTypeGet = 0;
const aTypeSet = 1;
const maxWait = elementLifeTimeMs;
const size = parseInt(cacheSize,10);
const mapping = new Map();
const mappingInFlightMiss = new Map();
const bufData = new Array(size);
const bufVisited = new Uint8Array(size);
const bufEdited = 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.set(rnd,i);
bufData[i]="";
bufVisited[i]=0;
bufEdited[i]=0;
bufKey[i]=rnd;
bufTime[i]=0;
bufLocked[i]=0;
}
let ctr = 0;
let ctrEvict = parseInt(cacheSize/2,10);
const loadData = callbackBackingStoreLoad;
const saveData = callbackBackingStoreSave;
let inFlightMissCtr = 0;
// refresh all items time-span in cache
this.reload=function(){
for(let i=0;i<size;i++)
{
bufTime[i]=0;
}
};
// refresh item time-span in cache by triggering eviction
this.reloadKey=function(key){
if(mapping.has(key))
{
bufTime[mapping[key]]=0;
}
};
// get value by key
this.get = function(keyPrm,callbackPrm){
// aType=0: get
access(keyPrm,callbackPrm,aTypeGet);
};
// set value by key (callback returns same value)
this.set = function(keyPrm,valuePrm,callbackPrm){
// aType=1: set
access(keyPrm,callbackPrm,aTypeSet,valuePrm);
};
// aType=0: get
// aType=1: set
function access(keyPrm,callbackPrm,aType,valuePrm){
const key = keyPrm;
const callback = callbackPrm;
const value = valuePrm;
// stop dead-lock when many async get calls are made
if(inFlightMissCtr>=size)
{
setTimeout(function(){
// get/set
access(key,function(newData){
callback(newData);
},aType,value);
},0);
return;
}
// if key is busy, then delay the request towards end of the cache-miss completion
if(mappingInFlightMiss.has(key))
{
setTimeout(function(){
// get/set
access(key,function(newData){
callback(newData);
},aType,value);
},0);
return;
}
if(mapping.has(key))
{
// slot is an element in the circular buffer of CLOCK algorithm
let slot = mapping.get(key);
// RAM speed data
if((Date.now() - bufTime[slot]) > maxWait)
{
// if slot is locked by another operation, postpone the current operation
if(bufLocked[slot])
{
setTimeout(function(){
access(key,function(newData){
callback(newData);
},aType,value);
},0);
}
else // slot is not locked and its lifespan has ended
{
// if it was edited, update the backing-store first
if(bufEdited[slot] == 1)
{
bufLocked[slot] = 1;
bufEdited[slot]=0;
mappingInFlightMiss.set(key,1); // lock key
inFlightMissCtr++;
// update backing-store, this is async
saveData(bufKey[slot],bufData[slot],function(){
mappingInFlightMiss.delete(key); // unlock key
bufLocked[slot] = 0;
inFlightMissCtr--;
mapping.delete(key); // disable mapping for current key
// re-simulate the access, async
access(key,function(newData){
callback(newData);
},aType,value);
});
}
else
{
mapping.delete(key); // disable mapping for current key
access(key,function(newData){
callback(newData);
},aType,value);
}
}
}
else // slot life span has not ended
{
bufVisited[slot]=1;
bufTime[slot] = Date.now();
// if it is a "set" operation
if(aType == aTypeSet)
{
bufEdited[slot] = 1; // later used when data needs to be
// written to data-store (write-cache feature)
bufData[slot] = value;
}
callback(bufData[slot]);
}
}
else
{
// datastore loading + cache eviction
let ctrFound = -1;
let oldVal = 0;
let oldKey = 0;
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])
{
// eviction preparations, lock the slot
bufLocked[ctrEvict] = 1;
inFlightMissCtr++;
ctrFound = ctrEvict;
oldVal = bufData[ctrFound];
oldKey = bufKey[ctrFound];
}
ctrEvict++;
if(ctrEvict >= size)
{
ctrEvict=0;
}
}
// user-requested key is now asynchronously in-flight &
// locked for other operations
mappingInFlightMiss.set(key,1);
// eviction function. least recently used data is gone,
// newest recently used data is assigned
let evict = function(res){
mapping.delete(bufKey[ctrFound]);
bufData[ctrFound]=res;
bufVisited[ctrFound]=0;
bufKey[ctrFound]=key;
bufTime[ctrFound]=Date.now();
bufLocked[ctrFound]=0;
mapping.set(key,ctrFound);
callback(res);
inFlightMissCtr--;
mappingInFlightMiss.delete(key);
};
// if old data was edited, send it to data-store first, then fetch new data
if(bufEdited[ctrFound] == 1)
{
if(aType == aTypeGet)
bufEdited[ctrFound] = 0;
// old edited data is sent back to data-store
saveData(oldKey,oldVal,function(){
if(aType == aTypeGet)
loadData(key,evict);
else if(aType == aTypeSet)
evict(value);
});
}
else
{
if(aType == aTypeSet)
bufEdited[ctrFound] = 1;
if(aType == aTypeGet)
loadData(key,evict);
else if(aType == aTypeSet)
evict(value);
}
}
};
this.getAwaitable = function(key){
return new Promise(function(success,fail){
me.get(key,function(data){
success(data);
});
});
}
this.setAwaitable = function(key,value){
return new Promise(function(success,fail){
me.set(key,value,function(data){
success(data);
});
});
}
// as many keys as required can be given, separated by commas
this.getMultiple = function(callback, ... keys){
let result = [];
let ctr1 = keys.length;
for(let i=0;i<ctr1;i++)
result.push(0);
let ctr2 = 0;
keys.forEach(function(key){
let ctr3 = ctr2++;
me.get(key,function(data){
result[ctr3] = data;
ctr1--;
if(ctr1==0)
{
callback(result);
}
});
});
};
// as many key-value pairs ( in form of { key:foo, value:bar } ) can be given,
// separated by commas
this.setMultiple = function(callback, ... keyValuePairs){
let result = [];
let ctr1 = keyValuePairs.length;
for(let i=0;i<ctr1;i++)
result.push(0);
let ctr2 = 0;
keyValuePairs.forEach(function(pair){
let ctr3 = ctr2++;
me.set(pair.key,pair.value,function(data){
result[ctr3] = data;
ctr1--;
if(ctr1==0)
{
callback(result);
}
});
});
};
// as many keys as required can be given, separated by commas
this.getMultipleAwaitable = function(... keys){
return new Promise(function(success,fail){
me.getMultiple(function(results){
success(results);
}, ... keys);
});
};
// as many key-value pairs ( in form of { key:foo, value:bar } ) can be given,
// separated by commas
this.setMultipleAwaitable = function(... keyValuePairs){
return new Promise(function(success,fail){
me.setMultiple(function(results){
success(results);
}, ... keyValuePairs);
});
};
// push all edited slots to backing-store and reset all slots
// lifetime to "out of date"
this.flush = function(callback){
function waitForReadWrite(callbackW){
// if there are in-flight cache-misses cache-write-misses
// or active slot locks, then wait
if(mappingInFlightMiss.size > 0 ||
bufLocked.reduce((e1,e2)=>{return e1+e2;}) > 0)
{
setTimeout(()=>{ waitForReadWrite(callbackW); },10);
}
else
callbackW();
}
waitForReadWrite(async function(){
for(let i=0;i<size;i++)
{
bufTime[i]=0;
if(bufEdited[i] == 1)
{
// less concurrency pressure, less failure
await me.setAwaitable(bufKey[i],bufData[i]);
}
}
callback(); // flush complete
});
};
};
exports.Lru = Lru;
按图像软化样本缓存命中率（来自 Github）。
它使用 25 的缓存大小对 8x8 图像应用 5 点平滑内核，并将每个结果像素通过另一个相同大小的缓存写入输出缓冲区。然后输出缓存命中率。由于每隔一行像素使用前一行像素（或每个像素使用接近的 4 个相邻像素），因此存在一些大于 1 的数据重用率。这种模式使得仅 25 个缓存元素能够有效地缓存 384 次读/写访问的约 75%。
输出
run-time: 5704 ms 320 reads 64 writes
cache read hit ratio=72.91666666666667
cache write hit ratio=77.08333333333333
历史
- 2021 年 4 月 8 日
- 算法的基本覆盖，一些示例。
- 2021 年 9 月 19 日
- 添加了项刷新功能（作为推迟的“写入”操作）并通过解决死锁问题优化了异步。
- 2021 年 9 月 25 日
- 添加了多个键值请求方法以避免回调地狱和一些基准测试结果。
- 2021 年 9 月 29 日
- 添加了写缓存功能、各种优化和新的基准测试。
- 更新了标题，加上了“asynchronous”一词。
- 将标签更改为一组更好的标签。