NodeJS 中的 LRU 缓存(CLOCK-2-hand)实现
代码展示
;
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高速缓存。
异步缓存未命中回调的工作方式如下:
1、一些get()在缓存中找不到密钥
2、算法找到对应插槽
3、运行此回调:
在回调中,重要计算异步完成
回调结束时,将回调函数的回调返回到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
}
高效且简单
只要映射对应一个缓存插槽,就可以直接从其中获取数据:
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逐出逻辑寻找目标:
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,可以使该插槽用于其他异步访问。
如果存在命中,并且找到的插槽生命周期结束且已锁定,则访问操作setTimeout将0 time参数延迟到JavaScript消息队列的末尾。
锁定操作(cache-miss)在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;
}
这样,就可以避免数据的重复。
标杆管理
异步高速缓存未命中基准
;
// 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
命中率测试
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比率的键的随机性
%命中率测试
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,并大大减少了总延迟。
总结
文本详细介绍了NodeJS中LRU算法缓存的实现,希望可以为大家提供新的思路,更好的在开发中提升系统性能。
学习更多技能
请点击下方公众号