expirationCheck optimization ，use lazy and timeAfter check , just like redis key expired policy

[liulanghai]

now expirationCheck will Iter hole map，it will cost more cpu

[ljluestc]

// PriorityQueue class for managing expiration times
class PriorityQueue {
    constructor() {
        this.items = [];
    }

    // Add an item to the heap
    enqueue(key, expiration) {
        const item = { key, expiration };
        this.items.push(item);
        this._bubbleUp(this.items.length - 1);
    }

    // Remove and return the item with the earliest expiration
    dequeue() {
        if (this.items.length === 0) return null;
        if (this.items.length === 1) return this.items.pop();

        const min = this.items[0];
        this.items[0] = this.items.pop();
        this._sinkDown(0);
        return min;
    }

    // Peek at the earliest expiration without removing
    peek() {
        return this.items[0] || null;
    }

    // Get the size of the queue
    size() {
        return this.items.length;
    }

    // Helper to maintain heap property upward
    _bubbleUp(index) {
        const item = this.items[index];
        while (index > 0) {
            const parentIndex = Math.floor((index - 1) / 2);
            const parent = this.items[parentIndex];
            if (item.expiration >= parent.expiration) break;
            this.items[index] = parent;
            index = parentIndex;
        }
        this.items[index] = item;
    }

    // Helper to maintain heap property downward
    _sinkDown(index) {
        const length = this.items.length;
        const item = this.items[index];

        while (true) {
            let minIndex = index;
            const leftChild = 2 * index + 1;
            const rightChild = 2 * index + 2;

            if (leftChild < length && this.items[leftChild].expiration < this.items[minIndex].expiration) {
                minIndex = leftChild;
            }
            if (rightChild < length && this.items[rightChild].expiration < this.items[minIndex].expiration) {
                minIndex = rightChild;
            }
            if (minIndex === index) break;

            this.items[index] = this.items[minIndex];
            this.items[minIndex] = item;
            index = minIndex;
        }
    }
}

// Cache class with efficient expiration checking
class Cache {
    constructor() {
        this.items = new Map();
        this.expirationQueue = new PriorityQueue();
    }

    // Set a key-value pair with a TTL (in milliseconds)
    set(key, value, ttl) {
        const expiration = Date.now() + ttl;
        this.items.set(key, { value, expiration });

        // Add to priority queue
        this.expirationQueue.enqueue(key, expiration);
    }

    // Get a value if it hasn't expired
    get(key) {
        const item = this.items.get(key);
        if (!item) return null;
        if (Date.now() > item.expiration) {
            this.items.delete(key); // Lazy deletion
            return null;
        }
        return item.value;
    }

    // Check and remove expired items efficiently
    expirationCheck() {
        const now = Date.now();
        while (this.expirationQueue.size() > 0) {
            const item = this.expirationQueue.peek();
            if (!item || item.expiration > now) break; // No more expired items
            this.expirationQueue.dequeue();
            // Only delete from map if the item still exists and matches the expiration
            const cacheItem = this.items.get(item.key);
            if (cacheItem && cacheItem.expiration === item.expiration) {
                this.items.delete(item.key);
            }
        }
    }

    // Run expiration check periodically
    runExpirationCheck(interval) {
        setInterval(() => this.expirationCheck(), interval);
    }
}

// Example usage
const cache = new Cache();

// Add items with different TTLs
cache.set("key1", "value1", 2000); // Expires in 2 seconds
cache.set("key2", "value2", 5000); // Expires in 5 seconds

// Start periodic expiration check (every 1 second)
cache.runExpirationCheck(1000);

// Test retrieval over time
const test = setInterval(() => {
    console.log("key1:", cache.get("key1"));
    console.log("key2:", cache.get("key2"));
}, 1000);

// Stop testing after 6 seconds
setTimeout(() => clearInterval(test), 6000);