Mini-challenge — Implement LRU Cache thủ công không dùng LinkedHashMap

Cache memory-bound — máy chủ chỉ giữ được N entry trong RAM. Khi cache đầy và cần thêm entry mới, phải chọn entry nào để đẩy ra. Least Recently Used (LRU) nói: đẩy entry lâu nhất chưa được truy cập — giả định rằng nếu bạn chưa dùng đến nó lâu, bạn ít có khả năng cần nó ngay bây giờ.

LeetCode 146 yêu cầu get và put đều O(1). Có thể dùng LinkedHashMap với accessOrder=true — nhưng bài này yêu cầu implement thủ công để hiểu tại sao cần kết hợp HashMap với DoublyLinkedList, và tại sao không cấu trúc dữ liệu nào khác đáp ứng được cả hai ràng buộc cùng lúc.

Sau bài này bạn implement được LRU mà Caffeine, Redis, Memcached, và Linux page cache đều dùng pattern này — chỉ tinh chỉnh thêm metric, TTL, và evict policy lên trên cùng skeleton.

🎯 Yêu cầu bài toán

Viết LRUCache(K, V) với API sau:

• Constructor: LRUCache(capacity) — khởi tạo cache với dung lượng tối đa.
• get(key) — trả về value nếu key tồn tại trong cache, NIL nếu miss. Khi hit, đánh dấu key là recently used (promote lên MRU — Most Recently Used, đầu vừa-dùng-gần-nhất, đối lập với LRU ở cuối).
• put(key, value) — insert hoặc update. Nếu key đã tồn tại, update value và promote lên MRU. Nếu cache đầy khi insert key mới, evict LRU entry trước.

Yêu cầu Big-O:

Ràng buộc:

• Không dùng LinkedHashMap hay bất kỳ linked map built-in nào.
• Implement DoublyLinkedList và Node thủ công.

Dành 20–25 phút tự làm trước khi xem gợi ý.

🧪 Test cases (pseudocode)

c <- LRUCache(capacity=2)
c.put(1, 100)
c.put(2, 200)
-- Trạng thái: LRU -> [1, 2] <- MRU

c.get(1)   -- hit, key 1 promote lên MRU, trả 100
-- Trạng thái: LRU -> [2, 1] <- MRU

c.put(3, 300)   -- đầy, evict LRU = key 2
-- Trạng thái: LRU -> [1, 3] <- MRU

c.get(2)   -- miss, đã evict, trả NIL
c.get(1)   -- hit, trả 100
c.get(3)   -- hit, trả 300

c.put(4, 400)   -- trước put: LRU -> [1, 3] <- MRU (get(3) vừa promote 3)
                -- evict LRU = key 1
-- Trạng thái: LRU -> [3, 4] <- MRU

c.get(1)   -- miss, đã evict, trả NIL
c.get(3)   -- hit, trả 300
c.get(4)   -- hit, trả 400

Bonus stress test: capacity = 1000, 100k random get/put xen kẽ. Verify rằng cache size không bao giờ vượt capacity, và hit rate trên Zipfian access pattern cao hơn đáng kể so với random eviction.

💡 Gợi ý

Map: {1: nodeA, 2: nodeB, 3: nodeC}

DoublyLinkedList (HEAD=LRU sentinel, TAIL=MRU sentinel):
  [HEAD] <-> nodeA(1,v1) <-> nodeB(2,v2) <-> nodeC(3,v3) <-> [TAIL]

get(2):
  1. Map.get(2) -> nodeB                    (O(1))
  2. removeNode(nodeB): nodeA.next=nodeC,   (O(1))
                        nodeC.prev=nodeA
  3. addBeforeTail(nodeB): insert trước     (O(1))
                            TAIL sentinel
  Kết quả: HEAD <-> nodeA <-> nodeC <-> nodeB <-> TAIL

🗺️ Sơ đồ cấu trúc

graph LR
    subgraph MAP["Map (O(1) lookup)"]
        K1["key=1"] --> N1
        K2["key=2"] --> N2
        K3["key=3"] --> N3
    end

    subgraph DLL["DoublyLinkedList (thứ tự LRU → MRU)"]
        HEAD(["HEAD\n(sentinel)"]) <--> N1(["node\nkey=1, v1"])
        N1 <--> N2(["node\nkey=2, v2"])
        N2 <--> N3(["node\nkey=3, v3"])
        N3 <--> TAIL(["TAIL\n(sentinel)"])
    end

Map trỏ thẳng đến node trong DoublyLinkedList — đây là chìa khoá cho O(1) promote. HEAD.next = LRU (cũ nhất), TAIL.prev = MRU (mới nhất).

✅ Lời giải

-- Node của DoublyLinkedList
Node:
    key
    value
    prev <- NIL
    next <- NIL

-- LRUCache
LRUCache(capacity):
    this.capacity <- capacity
    this.map      <- Map rỗng      -- Map(key -> Node)
    this.head     <- Node(NIL, NIL)  -- sentinel LRU
    this.tail     <- Node(NIL, NIL)  -- sentinel MRU
    head.next <- tail
    tail.prev <- head

get(key):
    node <- map.get(key)
    if node = NIL: return NIL     -- cache miss
    moveToTail(node)              -- promote lên MRU
    return node.value

put(key, value):
    node <- map.get(key)
    if node != NIL:
        -- Key đã tồn tại: cập nhật value và promote
        node.value <- value
        moveToTail(node)
        return
    -- Evict LRU nếu đầy
    if map.size() = capacity:
        lru <- head.next          -- LRU là ngay sau sentinel head
        removeNode(lru)
        map.remove(lru.key)
    -- Insert entry mới vào MRU
    fresh <- Node(key, value)
    addBeforeTail(fresh)
    map.put(key, fresh)

-- Xoá node khỏi vị trí hiện tại trong linked list
removeNode(node):
    node.prev.next <- node.next
    node.next.prev <- node.prev

-- Chèn node ngay trước sentinel tail (= vị trí MRU)
addBeforeTail(node):
    node.prev      <- tail.prev
    node.next      <- tail
    tail.prev.next <- node
    tail.prev      <- node

-- Di chuyển node lên vị trí MRU
moveToTail(node):
    removeNode(node)
    addBeforeTail(node)

⚠️ Pitfall phổ biến

Pitfall 1 — Không dùng sentinel: null pointer khi remove node đầu hoặc cuối.

-- SAI: không sentinel, removeNode crash khi node là phần tử duy nhất
removeNode(node):
    if node.prev != NIL: node.prev.next <- node.next  -- không đủ
    if node.next != NIL: node.next.prev <- node.prev  -- bỏ sót update head pointer

-- Khi list có 1 phần tử: node.prev = NIL, node.next = NIL
-- head pointer của list vẫn trỏ vào node vừa xoá -- dangling reference

Dùng sentinel nodes: removeNode luôn có node.prev và node.next hợp lệ (ít nhất là sentinel) — không cần null check, không có edge case.

Pitfall 2 — Quên map.remove(lru.key) khi evict.

-- SAI: xoá node khỏi linked list nhưng để lại stale entry trong Map
evictLRU():
    lru <- head.next
    removeNode(lru)
    -- map.remove(lru.key)  -- THIẾU dòng này!

-- Hệ quả:
-- map vẫn giữ {lru.key: lru_node} — node không còn trong linked list
-- get(lru.key) sẽ trả value của node đã evict -- logic sai
-- map.size() tăng nhưng linked list không tăng -- capacity check bị lệch
-- cache thực sự có thể vượt capacity

Pitfall 3 — get(key) trên miss không nên throw exception.

-- SAI: cache miss là bình thường, không phải lỗi
get(key):
    node <- map.get(key)
    if node = NIL: throw "NoSuchElementException"  -- anti-pattern

-- ĐÚNG: trả NIL (hoặc Optional.empty())
get(key):
    node <- map.get(key)
    if node = NIL: return NIL
    moveToTail(node)
    return node.value

Cache miss là kết quả bình thường — không phải lỗi. Caller phải bắt exception cho mọi lookup, kể cả cold-start khi cache rỗng. Return NIL là đúng contract.

📊 Benchmark tham khảo

Capacity 10k, 1M ops (50% get / 50% put), JVM warm-up 3 lần:

  Custom LRUCache (bài này):   ~80ms
  LinkedHashMap (accessOrder): ~85ms
  Caffeine cache (W-TinyLFU):  ~50ms

Custom LRUCache và LinkedHashMap có throughput tương đương vì cùng algorithm. Caffeine nhanh hơn nhờ algorithm tốt hơn (Window TinyLFU — kết hợp LRU và LFU), không phải do Java code tối ưu hơn. Implication: khi optimize cache performance, chọn đúng eviction policy thường quan trọng hơn micro-optimize code.

🔗 Variant để tự thử

Variant 1 — TTL-based eviction:

Mỗi node thêm expiryMs. Trong get(key), sau khi hit: kiểm tra currentTime > node.expiryMs → nếu expired, evict và return NIL. put(key, value, ttlMs) tính expiryMs = now + ttlMs.

Câu hỏi: cleanup proactive (background thread sweep) có cần thiết không? Khi cache đầy và toàn bộ entries đã expired, head.next là LRU expired — evict nó là đúng. Khi cache không đầy và entries expired ngồi im: chỉ lãng phí capacity nhưng không trả wrong data. Background sweep giúp free capacity sớm hơn — nhưng thêm độ phức tạp threading.

Variant 2 — Thread-safe LRU:

Cách đơn giản nhất: lock toàn bộ get và put. Đúng nhưng tạo bottleneck toàn bộ cache serialize qua một lock.

Nâng lên: ReadWriteLock — nhiều thread đọc đồng thời, write lock khi put/evict. Nhưng get vẫn phải write-lock vì nó gọi moveToTail (mutates linked list). Thực ra với LRU, mọi get đều mutate state — read/write lock không giúp nhiều.

Production: Caffeine dùng buffer bất đồng bộ — get chỉ ghi access event vào ring buffer, thread riêng drain buffer định kỳ để update order. Không lock on hot path. Cross-link: bài 05 module này (circular buffer) là cơ chế Caffeine dùng cho access event buffer.

Variant 3 — LFU Cache (LeetCode 460):

Least Frequently Used: evict entry bị truy cập ít nhất. Cần thêm count per entry và Map(frequency -> Set(keys)) map từ frequency đến set of keys với that frequency. Dùng biến minFreq để track frequency thấp nhất hiện tại — O(1) evict. Khó hơn LRU đáng kể.

🔗 LeetCode liên quan

• 146. LRU Cache — bài chính. Đúng spec bài này.
• 460. LFU Cache — Least Frequently Used. Evict by access count.
• 432. All O`one Data Structure — O(1) increment/decrement count, get min/max key — cần DoublyLinkedList của buckets.

🏭 Applied note

Caffeine (com.github.benmanes.caffeine) — production Java cache library. Dùng Window TinyLFU thay pure LRU: chia cache thành window (20%) + protected (80%) + probationary segment. Entry mới vào window trước, nếu được truy cập đủ nhiều thì được admit vào protected. Giảm "cache pollution" từ scan access pattern.

Linux page cache — kernel dùng "active list" và "inactive list" (two-list LRU variant). Entry mới vào inactive list. Nếu được truy cập lần thứ hai, promote lên active list. Tránh "scan resistance" problem: đọc một file lớn một lần không đẩy toàn bộ working set ra khỏi cache.

Redis maxmemory-policy — cấu hình tại runtime:

• allkeys-lru — evict LRU entry trong toàn bộ keyspace.
• volatile-lru — evict LRU entry chỉ trong set keys có TTL.
• allkeys-lfu — evict LFU entry (Redis 4.0+).
• noeviction — return error khi hết memory, không evict.

Cross-link: bài 02 module này (Linked List) — DoublyLinkedList và O(1) delete khi có node ref. Bài 05 module này (Circular buffer) — ring buffer Caffeine dùng để buffer access event mà không lock. Thuật toán Cốt lõi — Module 1 lesson 02 (HashMap internals) — cơ chế hash collision, load factor, resize.

✨ Điều bạn vừa làm được

• Implement LRU Cache đạt O(1) get và put bằng cách kết hợp Map (O(1) lookup) và DoublyLinkedList (O(1) promote-to-MRU khi có node ref).
• Hiểu tại sao sentinel head/tail loại bỏ toàn bộ null check edge case trong linked list operations.
• Biết ba pitfall phổ biến: không sentinel, quên map.remove khi evict, throw exception on cache miss.
• Nhận ra pattern này là nền tảng của Caffeine, Redis, Linux page cache — thêm metric, TTL, và evict policy lên trên cùng skeleton.

Bài tiếp theo: Case Study: LMAX Disruptor