NodeJS 中的 LRU 缓存（CLOCK-2-hand）实现

[GrapeCityChina]

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



在文章的开始我们需要了解什么是缓存？缓存是预先根据数据列表准备一些重要数据。没有缓存的话，系统的吞吐量就取决于存储速度最慢的数据，因此保持应用程序高性能的一个重要优化就是缓存。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 ），但它隐藏在锁定操作延迟的延迟的之后。
1 if(buf[mapping[key]].locked)
2 {
3 setTimeout(function(){
4 me.get(key,function(newData){
5 callback(newData);
6 });
7 },0);
8 }
最后，如果某个键处于进行中的高速缓存未命中映射中，则通过 setTimeout 将其推迟到消息队列的末尾：
1 if(key in mappingInFlightMiss)
2 {
3
4 setTimeout(function(){
5 me.get(key,function(newData){
6 callback(newData);
7 });
8 },0);
9 return;
10 }
这样，就可以避免数据的重复。

标杆管理

异步高速缓存未命中基准
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 benchmark: 1127 miliseconds
由于每个高速缓存未命中都有 1000 毫秒的延迟，因此同步加载 1000 个元素将花费 15 分钟，但是重叠的高速缓存未命中会更快。这在 I / O 繁重的工作负载（例如来自 HDD 或网络的流数据）中特别有用。

缓存命中率基准
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 秒的时间（接近 100 x 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
基准测试的第一步（无法逃避缓存未命中）之后，所有内容都来自 RAM，并大大减少了总延迟。

总结：

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