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

转载请注明出处：葡萄城官网，葡萄城为开发者提供专业的开发工具、解决方案和服务，赋能开发者。

在文章的开始我们需要了解什么是缓存？

缓存是预先根据数据列表准备一些重要数据。没有缓存的话，系统的吞吐量就取决于存储速度最慢的数据，因此保持应用程序高性能的一个重要优化就是缓存。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. 
    
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.                 }
    
75. 
    
76.                 if(!buf[ctrEvict].locked && !buf[ctrEvict].visited)
    
77.                 {
    
78.                     // evict
    
79.                     buf[ctrEvict].locked = true;
    
80.                     ctrFound = ctrEvict;
    
81.                 }
    
82. 
    
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. };
     
103. 
     
104. exports.Lru = Lru;
     

复制代码

l   文件缓存示例：

1. let Lru = require("./lrucache.js").Lru;
   
2. let fs = require("fs");
   
3. let path = require("path");
   
4. 
   
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.     }
    
13. 
    
14.     if(!buf[ctrEvict].locked && !buf[ctrEvict].visited)
    
15.     {
    
16.         // evict
    
17.         buf[ctrEvict].locked = true;
    
18.         ctrFound = ctrEvict;
    
19.     }
    
20. 
    
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. };
   
9. 
   
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)
   
2. 
   
3. {
   
4. 
   
5. 
   
6. 
   
7.   setTimeout(function(){
   
8. 
   
9.      me.get(key,function(newData){
   
10. 
    
11.               callback(newData);
    
12. 
    
13.      });
    
14. 
    
15.   },0);
    
16. 
    
17.   return;
    
18. 
    
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;
   
5. 
   
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 */);
    
12. 
    
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;
   
5. 
   
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 */);
    
14. 
    
15. let ctr = 0;
    
16. let t1 = Date.now();
    
17. let asynchronity = 500;
    
18. let benchRepeat = 100;
    
19. let access = 0;
    
20. 
    
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. }
    
48. 
    
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
   
2. 
   
3. Result:
   
4. 
   
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
   
2. 
   
3. Result:
   
4. 
   
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算法缓存的实现，希望可以为大家提供新的思路，更好的在开发中提升系统性能。