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

在文章的开始我们需要了解什么是缓存？缓存是预先根据数据列表准备一些重要数据。

没有缓存的话，系统的吞吐量就取决于存储速度最慢的数据，因此保持应用程序高性能的一个重要优化就是缓存。

web应用程序中有两项很重要的工作，分别是文件和视频Blob的缓存和快速访问页面模板。

而在Nodejs中，非异步功能操作的延迟会决定系统什么时候为其他客户端提供服务，尽管操作系统有自己的文件缓存机制，但是同一个服务器中有多个web应用程序同时运行，且其中一个应用正在传输大量视频数据的时候，其他应用的缓存内容就可能会频繁失效，此时程序效率会大幅降低。

而针对应用程序资源的LRU算法能有效解决这个问题，使应用程序不被同一服务器中的其他应用程序缓存所影响。

考虑到存储速度最慢数据决系统吞吐量的这一点，LRU缓存的存在能将系统性能提高2倍至100倍；同时，异步LRU会隐藏全部高速缓存未命中的延迟。

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

代码展示

首先构建一个用来构造LRU对象模块的文件：

'use strict';
let Lru = function (cacheSize, callbackBackingStoreLoad, elementLifeTimeMs = 1000) {
    let me = this;
    let maxWait = elementLifeTimeMs;
    let size = parseInt(cacheSize, 10);
    let mapping = {};
    let mappingInFlightMiss = {};
    let buf = [];
    for (let i = 0; i < size; i++) {
        let rnd = Math.random();
        mapping[rnd] = i;
        buf.push({
            data: "",
            visited: false,
            key: rnd,
            time: 0,
            locked: false
        });
    }
    let ctr = 0;
    let ctrEvict = parseInt(cacheSize / 2, 10);
    let loadData = callbackBackingStoreLoad;
    this.get = function (key, callbackPrm) {

        let callback = callbackPrm;
        if (key in mappingInFlightMiss) {
            setTimeout(function () {
                me.get(key, function (newData) {
                    callback(newData);
                });
            }, 0);
            return;
        }

        if (key in mapping) {
            // RAM speed data
            if ((Date.now() - buf[mapping[key]].time) > maxWait) {
                if (buf[mapping[key]].locked) {
                    setTimeout(function () {
                        me.get(key, function (newData) {
                            callback(newData);
                        });
                    }, 0);
                } else {
                    delete mapping[key];

                    me.get(key, function (newData) {
                        callback(newData);
                    });
                }
            } else {
                buf[mapping[key]].visited = true;
                buf[mapping[key]].time = Date.now();
                callback(buf[mapping[key]].data);
            }
        } else {
            // datastore loading + cache eviction
            let ctrFound = -1;
            while (ctrFound === -1) {
                if (!buf[ctr].locked && buf[ctr].visited) {
                    buf[ctr].visited = false;
                }
                ctr++;
                if (ctr >= size) {
                    ctr = 0;
                }

                if (!buf[ctrEvict].locked && !buf[ctrEvict].visited) {
                    // evict
                    buf[ctrEvict].locked = true;
                    ctrFound = ctrEvict;
                }

                ctrEvict++;
                if (ctrEvict >= size) {
                    ctrEvict = 0;
                }
            }

            mappingInFlightMiss[key] = true;
            let f = function (res) {
                delete mapping[buf[ctrFound].key];
                buf[ctrFound] = {
                    data: res,
                    visited: false,
                    key: key,
                    time: Date.now(),
                    locked: false
                };
                mapping[key] = ctrFound;
                callback(buf[ctrFound].data);
                delete mappingInFlightMiss[key];
            };
            loadData(key, f);
        }
    };
};

exports.Lru = Lru;

文件缓存示例：

let Lru = require("./lrucache.js").Lru;
let fs = require("fs");
let path = require("path");

let fileCache = new Lru(500, async function (key, callback) {
    // cache-miss data-load algorithm
    fs.readFile(path.join(__dirname, key), function (err, data) {
        if (err) {
            callback({
                stat: 404,
                data: JSON.stringify(err)
            });
        } else {
            callback({
                stat: 200,
                data: data
            });
        }
    });
}, 1000 /* cache element lifetime */ );

使用LRU构造函数获取参数（高速缓存大小、高速缓存未命中的关键字和回调、高速缓存要素生命周期）来构造CLOCK高速缓存。

异步缓存未命中回调的工作方式如下： 1、一些get()在缓存中找不到密钥 2、算法找到对应插槽 3、运行此回调： 在回调中，重要计算异步完成 回调结束时，将回调函数的回调返回到LRU缓存中

再次访问同一密钥的数据来自RAM 该依赖的唯一实现方法get()：

fileCache.get("./test.js",function(dat){
    httpResponse.writeHead(dat.stat);
    httpResponse.end(dat.data);
});

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

工作原理

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

let mapping = {};

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

if(key in mapping) {
   // key found, get data from RAM
}

高效且简单

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

buf[mapping[key]].visited = true;
buf[mapping[key]].time = Date.now();
callback(buf[mapping[key]].data);

visited用来通知CLOCK指针（ctr和ctrEvict）保存该插槽，避免它被驱逐。time字段用来管理插槽的生命周期。只要访问到高速缓存命中都会更新time字段，把它保留在高速缓存中。

用户使用callback函数给get()函数提供用于检索高速缓存插槽的数据。

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

if ((Date.now() - buf[mapping[key]].time) > maxWait) {
    delete mapping[key];
    me.get(key, function (newData) {
        callback(newData);
    });
}

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

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

let ctrFound = -1;
while (ctrFound === -1) {
    if (!buf[ctr].locked && buf[ctr].visited) {
        buf[ctr].visited = false;
    }
    ctr++;
    if (ctr >= size) {
        ctr = 0;
    }

    if (!buf[ctrEvict].locked && !buf[ctrEvict].visited) {
        // evict
        buf[ctrEvict].locked = true;
        ctrFound = ctrEvict;
    }

    ctrEvict++;
    if (ctrEvict >= size) {
        ctrEvict = 0;
    }
}

第一个“ if”块检查“第二次机会”指针（ctr）指向的插槽状态，如果是未锁定并已访问会将其标记为未访问，而不是驱逐它。

第三“If”块检查由ctrEvict指针指向的插槽状态，如果是未锁定且未被访问，则将该插槽标记为“ locked”，防止异步访问get() 方法，并找到逐出插槽，然后循环结束。

对比可以发现ctr和ctrEvict的初始相位差为50％：

let ctr = 0;
let ctrEvict = parseInt(cacheSize/2,10);

并且在“ while”循环中二者均等递增。这意味着，这二者循环跟随另一方，互相检查。高速缓存插槽越多，对目标插槽搜索越有利。对每个键而言，每个键至少停留超过N / 2个时针运动才从从逐出中保存。

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

mappingInFlightMiss[key] = true;
let f = function (res) {
    delete mapping[buf[ctrFound].key];
    buf[ctrFound] = {
        data: res,
        visited: false,
        key: key,
        time: Date.now(),
        locked: false
    };
    mapping[key] = ctrFound;
    callback(buf[ctrFound].data);
    delete mappingInFlightMiss[key];
};

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），但它隐藏在锁定操作延迟的延迟的之后。

if (buf[mapping[key]].locked) {
    setTimeout(function () {
        me.get(key, function (newData) {
            callback(newData);
        });
    }, 0);
}

最后，如果某个键处于进行中的高速缓存未命中映射中，则通过setTimeout将其推迟到消息队列的末尾：

if (key in mappingInFlightMiss) {

    setTimeout(function () {
        me.get(key, function (newData) {
            callback(newData);
        });
    }, 0);
    return;
}

这样，就可以避免数据的重复。

标杆管理

异步高速缓存未命中基准

"use strict";
// number of asynchronous accessors(1000 here) need to be equal to or less than 
// cache size(1000 here) or it makes dead-lock
let Lru = require("./lrucache.js").Lru;

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

let ctr = 0;
let t1 = Date.now();
for (let i = 0; i < 1000; i++) {
    cache.get(i, function (data) {
        console.log("data:" + data + " key:" + i);
        if (i.toString() + " processed" !== data) {
            console.log("error: wrong key-data mapping.");
        }
        if (++ctr === 1000) {
            console.log("benchmark: " + (Date.now() - t1) + " miliseconds");
        }
    });
}

为了避免死锁的出现，可以将LRU大小选择为1000，或者for只允许循环迭代1000次。

输出：

benchmark: 1127 miliseconds

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

缓存命中率基准

10％的命中率： 密钥生成：随机，可能有10000个不同的值 1000个插槽

"use strict";
// number of asynchronous accessors(1000 here) need to be equal to or less than 
// cache size(1000 here) or it makes dead-lock
let Lru = require("./lrucache.js").Lru;

let cacheMiss = 0;
let cache = new Lru(1000, async function (key, callback) {
    cacheMiss++;
    // cache-miss data-load algorithm
    setTimeout(function () {
        callback(key + " processed");
    }, 100);
}, 100000000 /* cache element lifetime */ );

let ctr = 0;
let t1 = Date.now();
let asynchronity = 500;
let benchRepeat = 100;
let access = 0;

function test() {
    ctr = 0;
    for (let i = 0; i < asynchronity; i++) {
        let key = parseInt(Math.random() * 10000, 10); // 10% hit ratio
        cache.get(key.toString(), function (data) {
            access++;
            if (key.toString() + " processed" !== data) {
                console.log("error: wrong key-data mapping.");
            }
            if (++ctr === asynchronity) {
                console.log("benchmark: " + (Date.now() - t1) + " miliseconds");
                console.log("cache hit: " + (access - cacheMiss));
                console.log("cache miss: " + (cacheMiss));
                console.log("cache hit ratio: " + ((access - cacheMiss) / access));
                if (benchRepeat > 0) {
                    benchRepeat--;
                    test();
                }
            }
        });
    }
}

test();

结果：

benchmark: 10498 miliseconds
cache hit: 6151
cache miss: 44349
cache hit ratio: 0.1218019801980198

由于基准测试是按100个步骤进行的，每个缓存丢失的延迟时间为100毫秒，因此产生了10秒的时间（接近100 x 100毫秒）。命中率接近预期值10％。

50％命中率测试

let key = parseInt(Math.random()*2000,10); // 50% hit ratio

Result:

benchmark: 10418 miliseconds
cache hit: 27541
cache miss: 22959
cache hit ratio: 0.5453663366336634

命中率测试

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

Result:

benchmark: 10199 miliseconds
cache hit: 49156
cache miss: 1344
cache hit ratio: 0.9733861386138614

结果产生了0.9733比率的键的随机性

％命中率测试

let key = parseInt(Math.random()*999,10); // 100% hit ratio

结果：

benchmark: 1463 miliseconds
cache hit: 49501
cache miss: 999
cache hit ratio: 0.9802178217821782

基准测试的第一步（无法逃避缓存未命中）之后，所有内容都来自RAM，并大大减少了总延迟。