请选择 进入手机版 | 继续访问电脑版
 找回密码
 立即注册

QQ登录

只需一步,快速开始

葡萄城花卷
超级版主   /  发表于:2021-9-10 13:49  /   查看:1614  /  回复: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.         }

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

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

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

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

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

  4. let fileCache = new Lru(500, async function(key,callback){
  5.   // cache-miss data-load algorithm
  6.     fs.readFile(path.join(__dirname,key),function(err,data){
  7.       if(err) {                                 
  8.         callback({stat:404, data:JSON.stringify(err)});
  9.       }
  10.       else
  11.       {                                
  12.         callback({stat:200, data:data});
  13.       }                                                        
  14.     });
  15. },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.     }

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

  19.     ctrEvict++;
  20.     if(ctrEvict >= size)
  21.     {
  22.         ctrEvict=0;
  23.     }
  24. }
复制代码
第一个“ 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. };

  9. 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)

  2. {



  3.   setTimeout(function(){

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

  5.               callback(newData);

  6.      });

  7.   },0);

  8.   return;

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

标杆管理

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;

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

  11. let ctr = 0;
  12. let t1 = Date.now();
  13. for(let i=0;i<1000;i++)
  14. {
  15.     cache.get(i,function(data){
  16.         console.log("data:"+data+" key:"+i);
  17.         if(i.toString()+" processed" !== data)
  18.         {
  19.             console.log("error: wrong key-data mapping.");
  20.         }
  21.         if(++ctr === 1000)
  22.         {
  23.             console.log("benchmark: "+(Date.now()-t1)+" miliseconds");
  24.         }
  25.     });
  26. }
复制代码
为了避免死锁的出现,可以将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;

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

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

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

  45. 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

  2. Result:

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

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

  2. Result:

  3. benchmark: 10199 miliseconds
  4. cache hit: 49156
  5. cache miss: 1344
  6. 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 个回复

您需要登录后才可以回帖 登录 | 立即注册
返回顶部