找回密码
 立即注册

QQ登录

只需一步，快速开始

首页 › 技术交流区 › 葡萄城技术博客 › 查看内容
发新帖

葡萄城花卷

超级版主

97

主题

104

帖子

739

积分

超级版主

Rank: 8Rank: 8

积分
739

微信认证勋章讲师达人元老葡萄圣诞拼拼乐

最新发帖

[前端] 你有一份解决NodeJS缓存的攻略待查收——LRU值得拥有

葡萄城花卷
超级版主   /  发表于：2021-9-10 13:49  /   查看：2610  /  回复：0
本帖最后由 葡萄城花卷 于 2021-9-10 14:14 编辑
转载请注明出处：葡萄城官网，葡萄城为开发者提供专业的开发工具、解决方案和服务，赋能开发者。

在文章的开始我们需要了解什么是缓存？
缓存是预先根据数据列表准备一些重要数据。没有缓存的话，系统的吞吐量就取决于存储速度最慢的数据，因此保持应用程序高性能的一个重要优化就是缓存。web应用程序中有两项很重要的工作，分别是文件和视频Blob的缓存和快速访问页面模板。
而在NodeJS中，非异步功能操作的延迟会决定系统什么时候为其他客户端提供服务，尽管操作系统有自己的文件缓存机制，但是同一个服务器中有多个web应用程序同时运行，且其中一个应用正在传输大量视频数据的时候，其他应用的缓存内容就可能会频繁失效，此时程序效率会大幅降低。
而针对应用程序资源的LRU算法能有效解决这个问题，使应用程序不被同一服务器中的其他应用程序缓存所影响。考虑到存储速度最慢数据决系统吞吐量的这一点，LRU缓存的存在能将系统性能提高2倍至100倍；同时，异步LRU会隐藏全部高速缓存未命中的延迟。
接下来我们一起来看具体实现的内容。
代码展示
l   首先构建一个用来构造LRU对象模块的文件：

  1. 'use strict';
  2. let Lru = function(cacheSize,callbackBackingStoreLoad,elementLifeTimeMs=1000){
  3.     let me = this;
  4.     let maxWait = elementLifeTimeMs;
  5.     let size = parseInt(cacheSize,10);
  6.     let mapping = {};
  7.     let mappingInFlightMiss = {};
  8.     let buf = [];
  9.     for(let i=0;i<size;i++)
  10.     {
  11.         let rnd = Math.random();
  12.         mapping[rnd] = i;
  13.         buf.push({data:"",visited:false, key:rnd, time:0, locked:false});
  14.     }
  15.     let ctr = 0;
  16.     let ctrEvict = parseInt(cacheSize/2,10);
  17.     let loadData = callbackBackingStoreLoad;
  18.     this.get = function(key,callbackPrm){
  19.       
  20.         let callback = callbackPrm;
  21.         if(key in mappingInFlightMiss)
  22.         {
  23.             setTimeout(function(){
  24.                 me.get(key,function(newData){
  25.                     callback(newData);
  26.                 });
  27.             },0);
  28.             return;
  29.         }

  31.         if(key in mapping)
  32.         {            
  33.             // RAM speed data
  34.             if((Date.now() - buf[mapping[key]].time) > maxWait)
  35.             {               
  36.                 if(buf[mapping[key]].locked)
  37.                 {                                       
  38.                     setTimeout(function(){
  39.                         me.get(key,function(newData){
  40.                             callback(newData);
  41.                         });
  42.                     },0);                    
  43.                 }
  44.                 else
  45.                 {
  46.                     delete mapping[key];
  47.                     
  48.                     me.get(key,function(newData){
  49.                         callback(newData);
  50.                     });                    
  51.                 }               
  52.             }
  53.             else
  54.             {
  55.                 buf[mapping[key]].visited=true;
  56.                 buf[mapping[key]].time = Date.now();
  57.                 callback(buf[mapping[key]].data);
  58.             }
  59.         }
  60.         else
  61.         {
  62.             // datastore loading + cache eviction
  63.             let ctrFound = -1;
  64.             while(ctrFound===-1)
  65.             {
  66.                 if(!buf[ctr].locked && buf[ctr].visited)
  67.                 {
  68.                     buf[ctr].visited=false;
  69.                 }
  70.                 ctr++;
  71.                 if(ctr >= size)
  72.                 {
  73.                     ctr=0;
  74.                 }

  76.                 if(!buf[ctrEvict].locked && !buf[ctrEvict].visited)
  77.                 {
  78.                     // evict
  79.                     buf[ctrEvict].locked = true;
  80.                     ctrFound = ctrEvict;
  81.                 }

  83.                 ctrEvict++;
  84.                 if(ctrEvict >= size)
  85.                 {
  86.                     ctrEvict=0;
  87.                 }
  88.             }
  89.             
  90.             mappingInFlightMiss[key]=true;
  91.             let f = function(res){
  92.                 delete mapping[buf[ctrFound].key];
  93.                 buf[ctrFound] =
  94.                 {data: res, visited:false, key:key, time:Date.now(), locked:false};
  95.                 mapping[key] = ctrFound;
  96.                 callback(buf[ctrFound].data);
  97.                 delete mappingInFlightMiss[key];        
  98.             };
  99.             loadData(key,f);
  100.         }
  101.     };
  102. };

  104. exports.Lru = Lru;
复制代码

l   文件缓存示例：
  1. let Lru = require("./lrucache.js").Lru;
  2. let fs = require("fs");
  3. let path = require("path");

  5. let fileCache = new Lru(500, async function(key,callback){
  6.   // cache-miss data-load algorithm
  7.     fs.readFile(path.join(__dirname,key),function(err,data){
  8.       if(err) {                                 
  9.         callback({stat:404, data:JSON.stringify(err)});
  10.       }
  11.       else
  12.       {                                
  13.         callback({stat:200, data:data});
  14.       }                                                        
  15.     });
  16. },1000 /* cache element lifetime */);
复制代码
使用LRU构造函数获取参数（高速缓存大小、高速缓存未命中的关键字和回调、高速缓存要素生命周期）来构造CLOCK高速缓存。
l   异步缓存未命中回调的工作方式如下：
1.一些get()在缓存中找不到密钥
2.算法找到对应插槽
3.运行此回调：
在回调中，重要计算异步完成
回调结束时，将回调函数的回调返回到LRU缓存中
4. 再次访问同一密钥的数据来自RAM

该依赖的唯一实现方法get()：

  1. fileCache.get("./test.js",function(dat){
  2.      httpResponse.writeHead(dat.stat);
  3.      httpResponse.end(dat.data);
  4. });
复制代码
结果数据还有另一个回调，因此可以异步运行
工作原理
l   现在大多LRU的工作过程始终存在从键到缓存槽的“映射”对象，就缓存槽的数量而言实现O（1）键搜索时间复杂度。但是用JavaScript就简单多了：

映射对象：

  1. let mapping = {};
复制代码
在映射中找到一个（字符串/整数）键：
  1. if(key in mapping)
  2. {
  3.    // key found, get data from RAM
  4. }
复制代码
高效且简单

l   只要映射对应一个缓存插槽，就可以直接从其中获取数据：
  1. buf[mapping[key]].visited=true;
  2. buf[mapping[key]].time = Date.now();
  3. callback(buf[mapping[key]].data);
复制代码
visited用来通知CLOCK指针（ctr和ctrEvict）保存该插槽，避免它被驱逐。time字段用来管理插槽的生命周期。只要访问到高速缓存命中都会更新time字段，把它保留在高速缓存中。
用户使用callback函数给get()函数提供用于检索高速缓存插槽的数据。

l   想要直接从映射插槽获取数据之前，需要先查看它的生命周期，如果生命周期已经结束，需要删除映射并用相同键重试使高速缓存丢失：

  1. if((Date.now() - buf[mapping[key]].time) > maxWait)
  2. {
  3.     delete mapping[key];
  4.     me.get(key,function(newData){
  5.         callback(newData);
  6.     });
  7. }
复制代码
删除映射后其他异步访问不会再影响其内部状态
如果在映射对象中没找
  1. let ctrFound = -1;
  2. while(ctrFound===-1)
  3. {
  4.     if(!buf[ctr].locked && buf[ctr].visited)
  5.     {
  6.         buf[ctr].visited=false;
  7.     }
  8.     ctr++;
  9.     if(ctr >= size)
  10.     {
  11.         ctr=0;
  12.     }

  14.     if(!buf[ctrEvict].locked && !buf[ctrEvict].visited)
  15.     {
  16.         // evict
  17.         buf[ctrEvict].locked = true;
  18.         ctrFound = ctrEvict;
  19.     }

  21.     ctrEvict++;
  22.     if(ctrEvict >= size)
  23.     {
  24.         ctrEvict=0;
  25.     }
  26. }
复制代码
第一个“ if”块检查“第二次机会”指针（ctr）指向的插槽状态，如果是未锁定并已访问会将其标记为未访问，而不是驱逐它。
第三“If”块检查由ctrEvict指针指向的插槽状态，如果是未锁定且未被访问，则将该插槽标记为“ locked”，防止异步访问get() 方法，并找到逐出插槽，然后循环结束。

对比可以发现ctr和ctrEvict的初始相位差为50％：

  1. let ctr = 0;
  2. let ctrEvict = parseInt(cacheSize/2,10);
复制代码
并且在“ while”循环中二者均等递增。这意味着，这二者循环跟随另一方，互相检查。高速缓存插槽越多，对目标插槽搜索越有利。对每个键而言，每个键至少停留超过N / 2个时针运动才从从逐出中保存。

l   找到目标插槽后，删除映射防止异步冲突的发生，并在加载数据存储区后重新创建映射：
  1. mappingInFlightMiss[key]=true;
  2. let f = function(res){
  3.     delete mapping[buf[ctrFound].key];
  4.     buf[ctrFound] = {data: res, visited:false, key:key, time:Date.now(), locked:false};
  5.     mapping[key] = ctrFound;
  6.     callback(buf[ctrFound].data);
  7.     delete mappingInFlightMiss[key];
  8. };

  10. loadData(key,f);
复制代码
由于用户提供的缓存缺失数据存储加载功能（loadData）可以异步进行，所以该缓存在运行中最多可以包含N个缓存缺失，最多可以隐藏N个缓存未命中延迟。隐藏延迟是影响吞吐量高低的重要因素，这一点在web应用中尤为明显。一旦应用中出现了超过N个异步缓存未命中/访问就会导致死锁，因此具有100个插槽的缓存可以异步服务多达100个用户，甚至可以将其限制为比N更低的值（M），并在多次（K）遍中进行计算（其中Mx K =总访问次数）。
我们都知道高速缓存命中就是RAM的速度，但因为高速缓存未命中可以隐藏，所以对于命中和未命中而言，总体性能看起来的时间复杂度都是O（1）。当插槽很少时，每个访问可能有多个时钟指针迭代，但如果增加插槽数时，它接近O（1）。
在此loadData回调中，将新插槽数据的locked字段设置为false，可以使该插槽用于其他异步访问。

l   如果存在命中，并且找到的插槽生命周期结束且已锁定，则访问操作setTimeout将0 time参数延迟到JavaScript消息队列的末尾。锁定操作（cache-miss）在setTimeout之前结束的概率为100％，就时间复杂度而言，仍算作具有较大的延迟的O（1），但它隐藏在锁定操作延迟的延迟的之后。

  1. if(buf[mapping[key]].locked)
  2. {
  3.     setTimeout(function(){
  4.         me.get(key,function(newData){
  5.             callback(newData);
  6.         });
  7.     },0);
  8. }
复制代码
l   最后，如果某个键处于进行中的高速缓存未命中映射中，则通过setTimeout将其推迟到消息队列的末尾：
  1. if(key in mappingInFlightMiss)

  3. {



  7.   setTimeout(function(){

  9.      me.get(key,function(newData){

  11.               callback(newData);

  13.      });

  15.   },0);

  17.   return;

  19. }
复制代码
这样，就可以避免数据的重复。

标杆管理

l   异步高速缓存未命中基准
  1. "use strict";
  2. // number of asynchronous accessors(1000 here) need to be equal to or less than
  3. // cache size(1000 here) or it makes dead-lock
  4. let Lru = require("./lrucache.js").Lru;

  6. let cache = new Lru(1000, async function(key,callback){
  7.     // cache-miss data-load algorithm
  8.     setTimeout(function(){
  9.         callback(key+" processed");
  10.     },1000);
  11. },1000 /* cache element lifetime */);

  13. let ctr = 0;
  14. let t1 = Date.now();
  15. for(let i=0;i<1000;i++)
  16. {
  17.     cache.get(i,function(data){
  18.         console.log("data:"+data+" key:"+i);
  19.         if(i.toString()+" processed" !== data)
  20.         {
  21.             console.log("error: wrong key-data mapping.");
  22.         }
  23.         if(++ctr === 1000)
  24.         {
  25.             console.log("benchmark: "+(Date.now()-t1)+" miliseconds");
  26.         }
  27.     });
  28. }
复制代码
为了避免死锁的出现，可以将LRU大小选择为1000，或者for只允许循环迭代1000次。

输出：
  1. <p class="MsoNormal"><span lang="EN-US" style="font-size:6.5pt">benchmark: 1127
  2. miliseconds<o:p></o:p></span></p>
复制代码

由于每个高速缓存未命中都有1000毫秒的延迟，因此同步加载1000个元素将花费15分钟，但是重叠的高速缓存未命中会更快。这在I / O繁重的工作负载（例如来自HDD或网络的流数据）中特别有用。
l   缓存命中率基准
10％的命中率：
密钥生成：随机，可能有10000个不同的值

1000个插槽
  1. "use strict";
  2. // number of asynchronous accessors(1000 here) need to be equal to or less than
  3. // cache size(1000 here) or it makes dead-lock
  4. let Lru = require("./lrucache.js").Lru;

  6. let cacheMiss = 0;
  7. let cache = new Lru(1000, async function(key,callback){
  8.     cacheMiss++;
  9.     // cache-miss data-load algorithm
  10.     setTimeout(function(){
  11.         callback(key+" processed");
  12.     },100);
  13. },100000000 /* cache element lifetime */);

  15. let ctr = 0;
  16. let t1 = Date.now();
  17. let asynchronity = 500;
  18. let benchRepeat = 100;
  19. let access = 0;

  21. function test()
  22. {
  23.     ctr = 0;
  24.     for(let i=0;i<asynchronity;i++)
  25.     {
  26.         let key = parseInt(Math.random()*10000,10); // 10% hit ratio
  27.         cache.get(key.toString(),function(data){     
  28.             access++;
  29.             if(key.toString()+" processed" !== data)
  30.             {
  31.                 console.log("error: wrong key-data mapping.");
  32.             }
  33.             if(++ctr === asynchronity)
  34.             {
  35.                 console.log("benchmark: "+(Date.now()-t1)+" miliseconds");
  36.                 console.log("cache hit: "+(access - cacheMiss));
  37.                 console.log("cache miss: "+(cacheMiss));
  38.                 console.log("cache hit ratio: "+((access - cacheMiss)/access));
  39.                 if(benchRepeat>0)
  40.                 {
  41.                     benchRepeat--;
  42.                     test();
  43.                 }
  44.             }
  45.         });
  46.     }
  47. }

  49. test();
复制代码
结果：
  1. benchmark: 10498 miliseconds
  2. cache hit: 6151
  3. cache miss: 44349
  4. cache hit ratio: 0.1218019801980198
复制代码
由于基准测试是按100个步骤进行的，每个缓存丢失的延迟时间为100毫秒，因此产生了10秒的时间（接近100x 100毫秒）。命中率接近预期值10％。

50％命中率测试
  1. let key = parseInt(Math.random()*2000,10); // 50% hit ratio

  3. Result:

  5. benchmark: 10418 miliseconds
  6. cache hit: 27541
  7. cache miss: 22959
  8. cache hit ratio: 0.5453663366336634
复制代码
99％命中率测试

  1. let key = parseInt(Math.random()*1010,10); // 99% hit ratio

  3. Result:

  5. benchmark: 10199 miliseconds
  6. cache hit: 49156
  7. cache miss: 1344
  8. cache hit ratio: 0.9733861386138614
复制代码

结果产生了0.9733比率的键的随机性

100％命中率测试

  1. let key = parseInt(Math.random()*999,10); // 100% hit ratio
复制代码

l   结果：
  1. benchmark: 1463 miliseconds
  2. cache hit: 49501
  3. cache miss: 999
  4. cache hit ratio: 0.9802178217821782
复制代码

基准测试的第一步（无法逃避缓存未命中）之后，所有内容都来自RAM，并大大减少了总延迟。
总结：
文本详细介绍了NodeJS中LRU算法缓存的实现，希望可以为大家提供新的思路，更好的在开发中提升系统性能。


0 个回复

高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册
产品与服务
活字格低代码平台
Wyn 商业智能软件
SpreadJS纯前端表格控件
技术服务体系
技术博客
低代码技术
客户与案例
典型客户
成功案例
用户访谈
合作与生态
合作伙伴网络
葡萄城市场
葡萄城与国产化
活字格用友客开工具
品牌活动
葡萄城公开课
品牌战略发布会
赋能开发者高峰论坛
企业级低代码发展研讨会
企业级低代码应用大赛
表格技术研讨会
了解葡萄城
葡萄城简介
愿景使命
研发与创新
荣誉奖项
加入我们
联系方式
联系我们
400-657-6008

葡萄城社区二维码

关注“葡萄城社区”

赋能开发者

西安葡萄城软件有限公司
专业的软件开发技术和低代码平台提供商

陕ICP备2020018819号  |   陕公网安备：61019002000258  |   隐私政策  |   网站地图  

邮箱： info.xa@grapecity.com  |  © 2024 葡萄城软件，保留所有权利

Archiver| 手机版| 小黑屋|

返回顶部