NodeJS 中的 LRU 缓存(CLOCK-2-hand)实现

更新日期: 2021-04-30阅读: 1.5k标签: node
转载请注明出处:葡萄城官网,葡萄城为开发者提供专业的开发工具、解决方案和服务,赋能开发者。

原文参考:https://www.codeproject.com/Articles/5299328/LRU-Cache-CLOCK-2-hand-Implementation-In-NodeJS

文章的开始我们需要了解什么是缓存?缓存是预先根据数据列表准备一些重要数据。

没有缓存的话,系统的吞吐量就取决于存储速度最慢的数据,因此保持应用程序高性能的一个重要优化就是缓存。

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

基准测试的第一步(无法逃避缓存未命中)之后,所有内容都来自RAM,并大大减少了总延迟。


总结:

文本详细介绍了NodeJS中LRU算法缓存的实现,希望可以为大家提供新的思路,更好的在开发中提升系统性能。

本文是由葡萄城技术开发团队发布,转载请注明出处:葡萄城官网


链接: https://www.fly63.com/article/detial/10258

关于 Node.js 里 ES6 Modules 的一次更新说明

关于 Node.js 里 ES6 Modules 的一次更新说明,总结来说:CommonJS 与 ES6 Modules 之间的关键不同在于代码什么时候知道一个模块的结构和使用它。

用node.js开发一个可交互的命令行应用

在这个教程中,我们会开发一个命令行应用,它可以接收一个 CSV 格式的用户信息文件,教程的内容大纲:“Hello,World”,处理命令行参数,运行时的用户输入,异步网络会话,美化控制台的输出,封装成 shell 命令,JavaScript 之外

Node启动https服务器

首先你需要生成https证书,可以去付费的网站购买或者找一些免费的网站,可能会是key或者crt或者pem结尾的。不同格式之间可以通过OpenSSL转换

nodejs 异步转同步

nodej项目在微信环境开发,nodejs的异步特效,会导致请求没有完成就执行下面的代码,出现错误。经过多方查找,可以使用async模块来异步转同步,只有前一个function执行callback,下一个才会执行。

基于node服务器的大文件(G级)上传

3G的大文件分1500个2M二进度文件,通post方法发送给node服务,服务器全部接收到文件后,进组装生成你上文件。

为什么要把 JavaScript 放到服务器端上运行?

JavaScript比C的开发门槛要低,尽管服务器端JavaScript存在已经很多年了,但是后端部分一直没有市场,JavaScript在浏览器中有广泛的事件驱动方面的应用,考虑到高性能、符合事件驱动、没有历史包袱这3个主要原因,JavaScript成为了Node的实现语言。

了解node.js事件循环

node.js的第一个基本论点是I / O的性能消耗是很昂贵。因此,使用当前编程技术的最大浪费来自于等待I / O完成。有几种方法可以处理性能影响

Node.js 应用:Koa2 使用 JWT 进行鉴权

在前后端分离的开发中,通过 Restful API 进行数据交互时,如果没有对 API 进行保护,那么别人就可以很容易地获取并调用这些 API 进行操作。那么服务器端要如何进行鉴权呢?

Node.js 前端开发指南

我们经常跟Node.js打交道,即使你是一名前端开发人员 -- npm脚本,webpack配置,gulp任务,程序打包 或 运行测试等。即使你真的不需要深入理解这些任务,但有时候你会感到困惑,会因为缺少Node.js的一些核心概念而以非常奇怪的方式来编码。

happypack提升项目构建速度

运行在 Node.js 之上的 Webpack 是单线程模型的,也就是说 Webpack 需要处理的任务需要一件件挨着做,不能多个事情一起做。happypack把任务分解给多个子进程去并发的执行,子进程处理完后再把结果发送给主进程。

点击更多...

内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!