V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
GrapeCityChina
V2EX  ›  推广

NodeJS 中的 LRU 缓存(CLOCK-2-hand)实现

  •  
  •   GrapeCityChina · 2021-04-30 11:08:05 +08:00 · 488 次点击
    这是一个创建于 1064 天前的主题,其中的信息可能已经有所发展或是发生改变。
    转载请注明出处:葡萄城官网,葡萄城为开发者提供专业的开发工具、解决方案和服务,赋能开发者。



    在文章的开始我们需要了解什么是缓存?缓存是预先根据数据列表准备一些重要数据。没有缓存的话,系统的吞吐量就取决于存储速度最慢的数据,因此保持应用程序高性能的一个重要优化就是缓存。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 算法缓存的实现,希望可以为大家提供新的思路,更好的在开发中提升系统性能。
    目前尚无回复
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2855 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 13:39 · PVG 21:39 · LAX 06:39 · JFK 09:39
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.