海屿文章列表

JS 实现LRU缓存

为什么不直接用对象这种k-v结构,因为内存空间很宝贵而且是有限的。
在浏览器我们无所谓,但服务端就不一样了,例如nuxt就是用了LRU算法缓存接口数据或者渲染后的dom对象。

LRU(Least Recently Used)把最近没用过的一个置换出去,意思就是如果最近用到了就放到前面,如果不够了最后一个就是最近没使用的,将其删除掉就好。使用双链表就能满足这种需求。

/*
 * Illustration of the design:
 *
 *       entry             entry             entry             entry
 *       ______            ______            ______            ______
 *      | tail |.newer => |      |.newer => |      |.newer => | head |
 *      |  A   |          |  B   |          |  C   |          |  D   |
 *      |______| <= older.|______| <= older.|______| <= older.|______|
 *
 */
class Node {
    prev = null;
    next = null;
    constructor(k, v) {
        if (valid(k)) this.key = k;
        if (valid(v)) this.value = v;
    }

    valid(e) {
        return typeof key != "undefined" && key !== null
    }
}

class LRU {
    size = 0;
    head = null;
    tail = null;
    map = {};
    constructor(limit = 1000) {
        this.limit = limit
    }

    setHead(node) {
        node.next = this.head;
        node.prev = null;
        if (this.head !== null) this.head.prev = node;
        if (this.tail === null) this.tail = node;
        this.size++;
        this.map[node.key] = node;
    }

    set(k, v) {
        const node = new Node(k,v);
        if (this.map[key]) {
            this.map[key].value = node.value;
            this.remove(node.key);
        } else {
            if (this.size >= this.limit) {
                delete this.map[this.tail.key];
                this.size--;
                this.tail = this.tail.prev;
                this.tail.next = null;
            }
        }
        this.setHead(node);
    }

    get(k) {
        if (this.map[k]) {
            const value = this.map[k].value;
            const node = new Node(k, v);
            this.remove(k);
            this.setHead(node);
            return value;
        } else {
            console.log("Key " + k + " does not exist in the cache.")
        }
    }

    remove(key) {
        const node = this.map[key];
        if (node.prev !== null) {
            node.prev.next = node.next;
        } else {
            this.head = node.next;
        }
        if (node.next !== null) {
            node.next.prev = node.prev;
        } else {
            this.tail = node.prev;
        }
        delete this.map[key];
        this.size--;
    }
}

插入删除时间复杂度都是O(1)

现在为止我们实现了最为核心部分,但是缓存也不能无限的停留在内存中,像接口这些数据有时会发生改变,所以还需要为缓存加上有效期,在get时判断是否过期。

LRU能带给我们一定的收益,但是他也让我们的程序拥有了状态,也就不能做分布式来多实例负载均衡。

HP 440 G5 安装黑苹果

  • 这里选择最新镜像下载
  • 使用 balenaEtcher 烧录至U盘
  • BIOS设置

    • 启用UEFI启动
    • 禁用安全启动
    • 禁用快速启动
    • IGPU图形内存设置为64mb(Broadwell和Skylake)
    • 如果可用,通过BIOS选项禁用串行端口
    • 如果可用,禁用“LAN / WLAN切换”
    • 禁用“局域网唤醒”和“USB唤醒”
  • 下载EFI文件并将其放到引导分区中,注意备份你之前的文件

其他注意事项:
安装完成后按F3显示隐藏启动项,第一次选择preboot进入
无线网卡无法驱动,需要用USB无线网卡。推荐comfast的wu810n无线网卡,十几块钱。驱动下载
耳机🎧驱动VoodooHDA.kext.zip

Typescript AOP 模式

AOP(Aspect Oriented Program)表示面向切面编程,它是OOP的补充,主要作用是将多个OOP模块中的通用代码抽取出来。切面的意思是系统中的一些通用功能,例如日志记录,缓存或验证。

例如,下面代码包含了日志记录等功能全部耦合在代码中,难以维护。

function sample(arg: string) {
    console.log("sample: " + arg);
    if(!isUserAuthenticated()) {
        throw new Error("User is not authenticated");
    }

    if(cache.has(arg)) {
        return cache.get(arg);
    }

    const result = 42; // TODO complex calculation
    cache.set(arg, result);
    return result;
}

通过TypeScript装饰器可以改写如下形式:

@log
@authorize
@cache
function sample(arg: string) {
    const result = 42;
    return result;
}

在JS中使用装饰器,可以参考该提案

基于布隆过滤器的依赖注入

如果你读过Shadowsocks或者Angular的代码,你会发现他里面都自己实现了一个布隆过滤器。
SS用他来匹配GFW名单,Angular中用来依赖注入服务名单。NodeInjector是Ivy渲染器引入的Angular注入器,它大量使用bloom过滤器来检索令牌。

Bloom过滤器的基本数据结构是位向量。

Bloom Filter原理:当一个元素被加入集合时,通过K个Hash函数将这个元素映射成一个位阵列(Bit array)中的K个点,把它们置为1。检索时,我们只要看看这些点是不是都是1就(大约)知道集合中有没有它了:如果这些点有任何一个0,则被检索元素一定不在;如果都是1,则被检索元素很可能在。

Angular中的bloom比特位为256,因此我们有一个256位的向量,它被分成8个部分。

Angular 通过递增整数值生成(如果尚未定义)令牌的唯一ID,并将其置于静态__NG_ELEMENT_ID__属性。
它通过按位AND(&)运算符获取该数字并使其适合bloom大小,以便结果始终在0-255之间。

// 用原始 bloomBit 值决定检查那个 bloom 过滤器桶
// e.g: bf0 = [0 - 31], bf1 = [32 - 63], bf2 = [64 - 95], bf3 = [96 - 127], etc
const b7 = bloomBit & 0x80;
const b6 = bloomBit & 0x40;
const b5 = bloomBit & 0x20;
const tData = tView.data as number[];

if (b7) {
  b6 ? (b5 ? (tData[injectorIndex + 7] |= mask) : (tData[injectorIndex + 6] |= mask)) :
       (b5 ? (tData[injectorIndex + 5] |= mask) : (tData[injectorIndex + 4] |= mask));
} else {
  b6 ? (b5 ? (tData[injectorIndex + 3] |= mask) : (tData[injectorIndex + 2] |= mask)) :
       (b5 ? (tData[injectorIndex + 1] |= mask) : (tData[injectorIndex] |= mask));
}

代码都是位运算,看起来挺复杂,其实就是将2^bloomBit位置为1。下面是一个简单例子:

const bloomBit = 3 % 255 // 3
const mask = 1 << bloomBit;
             1 << 3 // 8
8..toString(2) // 1000
                           
1 bucket          00000000000000000000000000001000
....
8 bucket          00000000000000000000000000000000