NodeJS 中的 LRU 緩存（CLOCK-2-hand）實(shí)現(xiàn)
代碼展示
;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 dataif((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 evictionlet 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){// evictbuf[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 algorithmfs.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構(gòu)造函數(shù)獲取參數(shù)（高速緩存大小、高速緩存未命中的關(guān)鍵字和回調(diào)、高速緩存要素生命周期）來(lái)構(gòu)造CLOCK高速緩存。
異步緩存未命中回調(diào)的工作方式如下：
1、一些get()在緩存中找不到密鑰
2、算法找到對(duì)應(yīng)插槽
3、運(yùn)行此回調(diào)：
在回調(diào)中，重要計(jì)算異步完成
回調(diào)結(jié)束時(shí)，將回調(diào)函數(shù)的回調(diào)返回到LRU緩存中
再次訪問同一密鑰的數(shù)據(jù)來(lái)自RAM
該依賴的唯一實(shí)現(xiàn)方法get()：
fileCache.get("./test.js",function(dat){httpResponse.writeHead(dat.stat);httpResponse.end(dat.data);});
結(jié)果數(shù)據(jù)還有另一個(gè)回調(diào)，因此可以異步運(yùn)行
工作原理
現(xiàn)在大多LRU的工作過(guò)程始終存在從鍵到緩存槽的“映射”對(duì)象，就緩存槽的數(shù)量而言實(shí)現(xiàn)O（1）鍵搜索時(shí)間復(fù)雜度。但是用JavaScript就簡(jiǎn)單多了：
映射對(duì)象：
let mapping = {};
在映射中找到一個(gè)（字符串/整數(shù)）鍵：
if(key in mapping){// key found, get data from RAM}
高效且簡(jiǎn)單
只要映射對(duì)應(yīng)一個(gè)緩存插槽，就可以直接從其中獲取數(shù)據(jù)：
buf[mapping[key]].visited=true;buf[mapping[key]].time = Date.now();callback(buf[mapping[key]].data);
visited用來(lái)通知CLOCK指針（ctr和ctrEvict）保存該插槽，避免它被驅(qū)逐。time字段用來(lái)管理插槽的生命周期。只要訪問到高速緩存命中都會(huì)更新time字段，把它保留在高速緩存中。
用戶使用callback函數(shù)給get()函數(shù)提供用于檢索高速緩存插槽的數(shù)據(jù)。
想要直接從映射插槽獲取數(shù)據(jù)之前，需要先查看它的生命周期，如果生命周期已經(jīng)結(jié)束，需要?jiǎng)h除映射并用相同鍵重試使高速緩存丟失：
if((Date.now() - buf[mapping[key]].time) > maxWait){delete mapping[key];me.get(key,function(newData){callback(newData);});}
刪除映射后其他異步訪問不會(huì)再影響其內(nèi)部狀態(tài)
如果在映射對(duì)象中沒找到密鑰，就運(yùn)行LRU逐出邏輯尋找目標(biāo)：
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){// evictbuf[ctrEvict].locked = true;ctrFound = ctrEvict;}ctrEvict++;if(ctrEvict >= size){ctrEvict=0;}}
第一個(gè)“ if”塊檢查“第二次機(jī)會(huì)”指針（ctr）指向的插槽狀態(tài)，如果是未鎖定并已訪問會(huì)將其標(biāo)記為未訪問，而不是驅(qū)逐它。
第三“If”塊檢查由ctrEvict指針指向的插槽狀態(tài)，如果是未鎖定且未被訪問，則將該插槽標(biāo)記為“ locked”，防止異步訪問get() 方法，并找到逐出插槽，然后循環(huán)結(jié)束。
對(duì)比可以發(fā)現(xiàn)ctr和ctrEvict的初始相位差為50％：
let ctr = 0;let ctrEvict = parseInt(cacheSize/2,10);
并且在“ while”循環(huán)中二者均等遞增。這意味著，這二者循環(huán)跟隨另一方，互相檢查。高速緩存插槽越多，對(duì)目標(biāo)插槽搜索越有利。對(duì)每個(gè)鍵而言，每個(gè)鍵至少停留超過(guò)N / 2個(gè)時(shí)針運(yùn)動(dòng)才從從逐出中保存。
找到目標(biāo)插槽后，刪除映射防止異步?jīng)_突的發(fā)生，并在加載數(shù)據(jù)存儲(chǔ)區(qū)后重新創(chuàng)建映射：
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);
由于用戶提供的緩存缺失數(shù)據(jù)存儲(chǔ)加載功能（loadData）可以異步進(jìn)行，所以該緩存在運(yùn)行中最多可以包含N個(gè)緩存缺失，最多可以隱藏N個(gè)緩存未命中延遲。
隱藏延遲是影響吞吐量高低的重要因素，這一點(diǎn)在web應(yīng)用中尤為明顯。
一旦應(yīng)用中出現(xiàn)了超過(guò)N個(gè)異步緩存未命中/訪問就會(huì)導(dǎo)致死鎖，因此具有100個(gè)插槽的緩存可以異步服務(wù)多達(dá)100個(gè)用戶，甚至可以將其限制為比N更低的值（M），并在多次（K）遍中進(jìn)行計(jì)算（其中M x K =總訪問次數(shù)）。
我們都知道高速緩存命中就是RAM的速度，但因?yàn)楦咚倬彺嫖疵锌梢噪[藏，所以對(duì)于命中和未命中而言，總體性能看起來(lái)的時(shí)間復(fù)雜度都是O（1）。
當(dāng)插槽很少時(shí)，每個(gè)訪問可能有多個(gè)時(shí)鐘指針迭代，但如果增加插槽數(shù)時(shí)，它接近O（1）。
在此loadData回調(diào)中，將新插槽數(shù)據(jù)的locked字段設(shè)置為false，可以使該插槽用于其他異步訪問。
如果存在命中，并且找到的插槽生命周期結(jié)束且已鎖定，則訪問操作setTimeout將0 time參數(shù)延遲到JavaScript消息隊(duì)列的末尾。
鎖定操作（cache-miss）在setTimeout之前結(jié)束的概率為100％，就時(shí)間復(fù)雜度而言，仍算作具有較大的延遲的O（1），但它隱藏在鎖定操作延遲的延遲的之后。
if(buf[mapping[key]].locked){setTimeout(function(){me.get(key,function(newData){callback(newData);});},0);}
最后，如果某個(gè)鍵處于進(jìn)行中的高速緩存未命中映射中，則通過(guò)setTimeout將其推遲到消息隊(duì)列的末尾：
if(key in mappingInFlightMiss){setTimeout(function(){me.get(key,function(newData){callback(newData);});},0);return;}
這樣，就可以避免數(shù)據(jù)的重復(fù)。
標(biāo)桿管理
異步高速緩存未命中基準(zhǔn)
;// number of asynchronous accessors(1000 here) need to be equal to or less than// cache size(1000 here) or it makes dead-locklet Lru = require("./lrucache.js").Lru;let cache = new Lru(1000, async function(key,callback){// cache-miss data-load algorithmsetTimeout(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");}});}
為了避免死鎖的出現(xiàn)，可以將LRU大小選擇為1000，或者for只允許循環(huán)迭代1000次。
輸出：
benchmark: 1127 miliseconds
由于每個(gè)高速緩存未命中都有1000毫秒的延遲，因此同步加載1000個(gè)元素將花費(fèi)15分鐘，但是重疊的高速緩存未命中會(huì)更快。這在I / O繁重的工作負(fù)載（例如來(lái)自HDD或網(wǎng)絡(luò)的流數(shù)據(jù)）中特別有用。
緩存命中率基準(zhǔn)
10％的命中率：
密鑰生成：隨機(jī)，可能有10000個(gè)不同的值
1000個(gè)插槽
"use strict";// number of asynchronous accessors(1000 here) need to be equal to or less than// cache size(1000 here) or it makes dead-locklet Lru = require("./lrucache.js").Lru;let cacheMiss = 0;let cache = new Lru(1000, async function(key,callback){cacheMiss++;// cache-miss data-load algorithmsetTimeout(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 ratiocache.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();
結(jié)果：
benchmark: 10498 milisecondscache hit: 6151cache miss: 44349cache hit ratio: 0.1218019801980198
由于基準(zhǔn)測(cè)試是按100個(gè)步驟進(jìn)行的，每個(gè)緩存丟失的延遲時(shí)間為100毫秒，因此產(chǎn)生了10秒的時(shí)間（接近100 x 100毫秒）。命中率接近預(yù)期值10％。
50％命中率測(cè)試
let key = parseInt(Math.random()*2000,10); // 50% hit ratioResult:benchmark: 10418 milisecondscache hit: 27541cache miss: 22959cache hit ratio: 0.5453663366336634
命中率測(cè)試
let key = parseInt(Math.random()*1010,10); // 99% hit ratioResult:benchmark: 10199 milisecondscache hit: 49156cache miss: 1344cache hit ratio: 0.9733861386138614
結(jié)果產(chǎn)生了0.9733比率的鍵的隨機(jī)性
％命中率測(cè)試
let key = parseInt(Math.random()*999,10); // 100% hit ratio
結(jié)果：
benchmark: 1463 milisecondscache hit: 49501cache miss: 999cache hit ratio: 0.9802178217821782
基準(zhǔn)測(cè)試的第一步（無(wú)法逃避緩存未命中）之后，所有內(nèi)容都來(lái)自RAM，并大大減少了總延遲。
總結(jié)
文本詳細(xì)介紹了NodeJS中LRU算法緩存的實(shí)現(xiàn)，希望可以為大家提供新的思路，更好的在開發(fā)中提升系統(tǒng)性能。
學(xué)習(xí)更多技能
請(qǐng)點(diǎn)擊下方公眾號(hào)
