NodeJS 中的 LRU 緩存（CLOCK-2-hand）實作

在文章的開始我們需要了解什麼是緩存？緩存是預先根據資料清單準備一些重要資料。

沒有緩存的話，系統的吞吐量就取決于存儲速度最慢的資料，是以保持應用程式高性能的一個重要優化就是緩存。

web應用程式中有兩項很重要的工作，分别是檔案和視訊Blob的緩存和快速通路頁面模闆。

而在Nodejs中，非異步功能操作的延遲會決定系統什麼時候為其他用戶端提供服務，盡管作業系統有自己的檔案緩存機制，但是同一個伺服器中有多個web應用程式同時運作，且其中一個應用正在傳輸大量視訊資料的時候，其他應用的緩存内容就可能會頻繁失效，此時程式效率會大幅降低。

而針對應用程式資源的LRU算法能有效解決這個問題，使應用程式不被同一伺服器中的其他應用程式緩存所影響。

考慮到存儲速度最慢資料決系統吞吐量的這一點，LRU緩存的存在能将系統性能提高2倍至100倍；同時，異步LRU會隐藏全部高速緩存未命中的延遲。

接下來我們一起來看具體實作的内容。

代碼展示

首先建構一個用來構造LRU對象子產品的檔案：

'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高速緩存。

異步緩存未命中回調的工作方式如下：

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;
}

這樣，就可以避免資料的重複。

标杆管理

異步高速緩存未命中基準

"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

命中率測試

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

NodeJS 中的 LRU 緩存（CLOCK-2-hand）實作

代碼展示

工作原理

标杆管理

結果：

50％命中率測試

命中率測試

％命中率測試

結果：

總結

繼續閱讀

H5前端存儲

Linux(Centos7版本中安裝mysql5.7 遇到的各種問題，最後由于Centos7安裝mysql5.7需要收費，安裝了 mariadb 資料庫）

InnoDB & index頁-mysql詳解（二）

Redis 的回收程序如何工作的？

【HTTP】711- 圖解 HTTP 緩存

MyBatis一級緩存中增删改要送出事務，查的話就不用

Redis：Creating Server TCP listening socket 127.0.0.1:6379: bind: No error

SpringBoot交友APP項目實戰（詳細介紹+案例源碼） - 9.小視訊（SpringCache緩存）系列文章目錄一、訪客功能二、分布式存儲FastDFS三、視訊功能四、通用緩存SpringCache

redis延遲雙删的政策

自定義SDWebImage圖檔緩沖區自清理機制

分布式緩存的基本原理

redis主從複制讀寫分離總結

redis的選擇和定位redis的選擇和定位

Redis單線程模型和IO多路複用

vue-loader-v16/package.json報錯

ZooKeeper ： Curator架構之資料緩存與監聽CuratorCache