葡萄城技术团队：NodeJS中的LRU缓存（CLOCK-2-hand）实现

当前位置博文首页 > 葡萄城技术团队：NodeJS中的LRU缓存（CLOCK-2-hand）实现

葡萄城技术团队：NodeJS中的LRU缓存（CLOCK-2-hand）实现

作者：葡萄城技术团队时间：2021-04-30 18:17

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

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

在文章的开始我们需要了解什么是缓存？缓存是预先根据数据列表准备一些重要数据。没有缓存的话，系统的吞吐量就取决于存储速度最慢的数据，因此保持应用程序高性能的一个重要优化就是缓存。web应用程序中有两项很重要的工作，分别是文件和视频Blob的缓存和快速访问页面模板。而在NodeJS中，非异步功能操作的延迟会决定系统什么时候为其他客户端提供服务，尽管操作系统有自己的文件缓存机制，但是同一个服务器中有多个web应用程序同时运行，且其中一个应用正在传输大量视频数据的时候，其他应用的缓存内容就可能会频繁失效，此时程序效率会大幅降低。

而针对应用程序资源的LRU算法能有效解决这个问题，使应用程序不被同一服务器中的其他应用程序缓存所影响。考虑到存储速度最慢数据决系统吞吐量的这一点，LRU缓存的存在能将系统性能提高2倍至100倍；同时，异步LRU会隐藏全部高速缓存未命中的延迟。

接下来我们一起来看具体实现的内容。

代码展示

首先构建一个用来构造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;

文件缓存示例：

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

异步缓存未命中回调的工作方式如下：

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

结果数据还有另一个回调，因此可以异步运行

工作原理

现在大多LRU的工作过程始终存在从键到缓存槽的“映射”对象，就缓存槽的数量而言实现O（1）键搜索时间复杂度。但是用JavaScript就简单多了：

映射对象：

1 let mapping = {};

在映射中找到一个（字符串/整数）键：

1 if(key in mapping)
2 {
3    // key found, get data from RAM
4 }

高效且简单

只要映射对应一个缓存插槽，就可以直接从其中获取数据：

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()函数提供用于检索高速缓存插槽的数据。

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

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 }

删除映射后其他异步访问不会再影响其内部状态

如果在映射对象中没找到密钥，就运行LRU逐出逻辑寻找目标：

 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个时针运动才从从逐出中保存。

找到目标插槽后，删除映射防止异步冲突的发生，并在加载数据存储区后重新创建映射：

 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）遍中进行计算（其中M x K =总访问次数）。

我们都知道高速缓存命中就是RAM的速度，但因为高速缓存未命中可以隐藏，所以对于命中和未命中而言，总体性能看起来的时间复杂度都是O（1）。当插槽很少时，每个访问可能有多个时钟指针迭代，但如果增加插槽数时，它接近O（1）。

在此loadData回调中，将新插槽数据的locked字段设置为false，可以使该插槽用于其他异步访问。

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

上一篇：来份锅包肉：Python 元编程 - 装饰器

下一篇：没有了

立即下载 - IIS7 站长工具包