LRU và LFU Cache: Tự thiết kế In-Memory Cache bằng Doubly Linked List + Hash Map

LRU và LFU Cache: Tự thiết kế In-Memory Cache bằng Doubly Linked List + Hash Map | Shanverse

Codetypescript

1class LruNode<K, V> {2  prev: LruNode<K, V> | null = null;3  next: LruNode<K, V> | null = null;45  constructor(6    readonly key: K,7    public value: V,8  ) {}9}1011class LRUCache<K, V> {12  private readonly nodes = new Map<K, LruNode<K, V>>();13  private readonly head = new LruNode<K, V>(undefined as K, undefined as V);14  private readonly tail = new LruNode<K, V>(undefined as K, undefined as V);1516  constructor(private readonly capacity: number) {17    if (!Number.isInteger(capacity) || capacity < 0) {18      throw new Error("capacity must be a non-negative integer");19    }2021    this.head.next = this.tail;22    this.tail.prev = this.head;23  }2425  get size(): number {26    return this.nodes.size;27  }2829  get(key: K): V | undefined {30    const node = this.nodes.get(key);31    if (!node) return undefined;3233    this.moveToFront(node);34    return node.value;35  }3637  has(key: K): boolean {38    return this.nodes.has(key);39  }4041  put(key: K, value: V): void {42    if (this.capacity === 0) return;4344    const existing = this.nodes.get(key);45    if (existing) {46      existing.value = value;47      this.moveToFront(existing);48      return;49    }5051    const node = new LruNode(key, value);52    this.nodes.set(key, node);53    this.addAfterHead(node);5455    if (this.nodes.size > this.capacity) {56      const evicted = this.removeLeastRecentlyUsed();57      if (evicted) this.nodes.delete(evicted.key);58    }59  }6061  delete(key: K): boolean {62    const node = this.nodes.get(key);63    if (!node) return false;6465    this.detach(node);66    return this.nodes.delete(key);67  }6869  clear(): void {70    this.nodes.clear();71    this.head.next = this.tail;72    this.tail.prev = this.head;73  }7475  private moveToFront(node: LruNode<K, V>): void {76    this.detach(node);77    this.addAfterHead(node);78  }7980  private addAfterHead(node: LruNode<K, V>): void {81    const first = this.head.next!;82    node.prev = this.head;83    node.next = first;84    this.head.next = node;85    first.prev = node;86  }8788  private detach(node: LruNode<K, V>): void {89    node.prev!.next = node.next;90    node.next!.prev = node.prev;91    node.prev = null;92    node.next = null;93  }9495  private removeLeastRecentlyUsed(): LruNode<K, V> | null {96    const candidate = this.tail.prev;97    if (!candidate || candidate === this.head) return null;9899    this.detach(candidate);100    return candidate;101  }102}

Codetypescript

1const cache = new LRUCache<string, string>(2);23cache.put("a", "A");4cache.put("b", "B");5cache.get("a");       // a trở thành MRU6cache.put("c", "C"); // b bị evict78console.log(cache.get("b")); // undefined9console.log(cache.get("a")); // A

Codetypescript

1const cache = new LFUCache<string, string>(2);23cache.put("a", "A"); // freq(a)=14cache.put("b", "B"); // freq(b)=15cache.get("a");       // freq(a)=26cache.put("c", "C"); // b bị evict vì freq=1

Codetypescript

1async function getUser(userId: string) {2  const key = `user:${userId}`;3  const cached = cache.get(key);4  if (cached !== undefined) return cached;56  return singleFlight(key, async () => {7    const secondCheck = cache.get(key);8    if (secondCheck !== undefined) return secondCheck;910    const user = await usersRepository.findById(userId);11    if (user) cache.put(key, user);12    return user;13  });14}

LRU và LFU Cache: Tự thiết kế In-Memory Cache bằng Doubly Linked List + Hash Map

Vì sao một Hash Map chưa đủ?

Comments

LRU Cache hoạt động thế nào?

get(key)

put(key, value)

TypeScript: Doubly Linked List + LRU Cache

Invariants của LRU

LFU khác LRU ở đâu?

TypeScript: LFU Cache O(1)

Walkthrough LFU

Complexity so sánh

Chọn LRU hay LFU?

Chọn LRU khi

Chọn LFU khi

Nhược điểm của LRU

Nhược điểm của LFU

LFU có decay

Giới hạn theo số item chưa đủ

Thêm TTL

Cache-aside an toàn

In-memory cache trong nhiều process

Invalidation

Async và concurrency

Redis khác implementation này

Metrics cần có

Test cases quan trọng

LRU

LFU

Production

Anti-patterns

Production checklist

Kết luận

Tài liệu tham khảo

Big O Notation trong thực tế: Đừng để O(N²) làm sập hệ thống

KMP Algorithm: Tìm chuỗi con không duyệt lại từ đầu

Fuzzy Search & Levenshtein Distance: Xây dựng gợi ý “Có phải bạn muốn tìm?”

Vì sao một Hash Map chưa đủ?

Comments

LRU Cache hoạt động thế nào?

get(key)

put(key, value)

TypeScript: Doubly Linked List + LRU Cache

Invariants của LRU

LFU khác LRU ở đâu?

TypeScript: LFU Cache O(1)

Walkthrough LFU

Complexity so sánh

Chọn LRU hay LFU?

Chọn LRU khi

Chọn LFU khi

Nhược điểm của LRU

Nhược điểm của LFU

LFU có decay

Giới hạn theo số item chưa đủ

Thêm TTL

Cache-aside an toàn

In-memory cache trong nhiều process

Invalidation

Async và concurrency

Redis khác implementation này

Metrics cần có

Test cases quan trọng

LRU

LFU

Production

Anti-patterns

Production checklist

Kết luận

Tài liệu tham khảo

Related posts

Big O Notation trong thực tế: Đừng để O(N²) làm sập hệ thống

KMP Algorithm: Tìm chuỗi con không duyệt lại từ đầu

Fuzzy Search & Levenshtein Distance: Xây dựng gợi ý “Có phải bạn muốn tìm?”