LRU list not cleaned up when cache entry expires during `get()` operation

[eightHundreds]

Bug Report: LRU list not cleaned up when cache entry expires during get() operation

First of all, I sincerely apologize. This is an AI-generated analysis report, and I haven't thoroughly verified its accuracy.

A memory leak did occur in my service. Based on the service symptoms, I asked the AI to scrutinize this project's code, and it ultimately helped me identify this issue.

I was using version 1.9.0, but the AI discovered that this problem still exists in the latest version.

Description

When a cache entry expires and is detected during a get() or getRaw() operation, the entry is removed from the store (Map) but not from the LRU linked list. This can lead to:

1. "Ghost" entries occupying LRU slots, reducing effective cache capacity
2. Duplicate nodes in the LRU list when the same key is re-set after expiration

Affected Files

• packages/memory/src/index.ts - CacheableMemory.get() (line 310-313)
• packages/memory/src/index.ts - CacheableMemory.getRaw() (line 350-353)
• packages/memory/src/index.ts - CacheableMemory.checkExpiration() (line 631-639)

Steps to Reproduce

import { CacheableMemory } from '@cacheable/memory';

const cache = new CacheableMemory({ lruSize: 3, ttl: 100 });

// Step 1: Fill the cache
cache.set('key1', 'value1');
cache.set('key2', 'value2');
cache.set('key3', 'value3');

// Step 2: Wait for expiration
await new Promise(resolve => setTimeout(resolve, 150));

// Step 3: Access expired key (triggers removal from store but not LRU)
cache.get('key1'); // Returns undefined, removes from store

// Step 4: Re-set the same key
cache.set('key1', 'newValue');

// Issue: LRU list now has duplicate 'key1' nodes
// The old expired node is still in the linked list

Expected Behavior

When an expired entry is detected and removed from the store, it should also be removed from the LRU linked list to maintain consistency.

Actual Behavior

The expired entry is only removed from the store (Map), leaving a "ghost" node in the LRU linked list.

Code in question (index.ts:310-313):

if (item.expires && Date.now() > item.expires) {
    store.delete(key);  // Only removes from store
    return undefined;   // Does NOT remove from LRU list
}

Impact

1. Reduced LRU efficiency: Expired keys occupy LRU slots until they are naturally evicted, potentially causing valid entries to be evicted prematurely.

2. Duplicate nodes: When re-setting an expired key:

   • store.has(key) returns false (already deleted)
   • lruAddToFront(key) is called instead of lruMoveToFront(key)
   • This creates a new node while the old node remains in the list
   • nodesMap.set() overwrites the reference, orphaning the old node

3. Incorrect eviction: When the orphaned old node reaches the tail and gets evicted, nodesMap.delete(key) removes the reference to the new node, corrupting the LRU state.

Suggested Fix

1. Add a remove(key) method to DoublyLinkedList:

remove(value: T): boolean {
    const node = this.nodesMap.get(value);
    if (!node) return false;

    if (node.prev) node.prev.next = node.next;
    if (node.next) node.next.prev = node.prev;
    if (this.head === node) this.head = node.next;
    if (this.tail === node) this.tail = node.prev;

    this.nodesMap.delete(value);
    return true;
}

2. Call LRU removal when detecting expired entries:

if (item.expires && Date.now() > item.expires) {
    store.delete(key);
    this._lru.remove(key);  // Add this line
    return undefined;
}

3. Apply the same fix to getRaw(), checkExpiration(), keys getter, and items getter.

Environment

• Package: @cacheable/memory
• Condition: lruSize > 0 (LRU enabled)

[jaredwray]

@eightHundreds - thanks for the post and we are looking into this.

[jaredwray]

#1571

[eightHundreds]

Hasn't it been released yet?

[jaredwray]

@eightHundreds I believe it has

[eightHundreds]

You modified the @cacheable/memory But it was updated last year

[jaredwray]

It will be published this week