LRU cache (Least Recently Used) là cấu trúc quen thuộc: giữ một số phần tử giới hạn, khi đầy thì đuổi cái ít được dùng gần đây nhất. Nó ở khắp nơi — cache của CPU, của cơ sở dữ liệu, của trình duyệt, của hệ điều hành. Yêu cầu nghe đơn giản, và nhiều người cài bằng một hash map với dấu thời gian rồi "tìm cái cũ nhất khi cần đuổi". Nhưng khi tôi đo, cách đó chậm thảm họa ở cache lớn — và lời giải đúng là một bài học đẹp về kết hợp hai cấu trúc để mỗi cái bù điểm yếu của cái kia. Tôi đo cả hai trong container gcc:13, và con số cho thấy vì sao LRU O(1) cần đúng hai cấu trúc, không phải một.

LRU cache: map + danh sách

Hai khả năng, và không cấu trúc nào cho cả hai

LRU cần hai khả năng: (1) tra key → value nhanh, và (2) biết phần tử nào ít dùng nhất để đuổi khi đầy.

Cách naive: chỉ một hash map key → (value, dấu thời gian lần dùng cuối). Tra cứu O(1), tốt. Nhưng khi cần đuổi, phải quét cả map tìm dấu thời gian nhỏ nhất — O(n). Với cache lớn, mỗi lần đuổi phải duyệt hàng trăm nghìn phần tử.

Cách đúng: kết hợp hai cấu trúc.

Mấu chốt: mỗi khả năng cần một cấu trúc. Chỉ có map thì không biết thứ tự dùng (phải quét tìm cái cũ nhất). Chỉ có danh sách thì tra key chậm (phải duyệt tìm — O(n)). Phải có cả hai, và chúng trỏ lẫn nhau.

Đo: naive O(n), đúng O(1) — chênh 5862 lần

Tôi đo chi phí một lần đuổi (put một khóa mới khi cache đã đầy) ở các kích thước cache khác nhau:

Put khóa mới khi đầy (mỗi lần = một lần đuổi), g++ -O2:

CAP       | GOOD (map + list đôi) | NAIVE (map + quét min) | naive chậm
----------|------------------------|-------------------------|----------
1.000     |   30,4 ns/đuổi         |     832 ns/đuổi          | 27x
10.000    |   22,2 ns              |  10.884 ns              | 491x
100.000   |   21,9 ns              | 128.268 ns              | 5862x

Workload trộn 2 triệu thao tác get/put: GOOD 42,6 ns/thao tác

Nhìn cột GOOD: chi phí mỗi lần đuổi ~hằng số dù cache to nhỏ thế nào — 30 ns ở cache 1.000, 22 ns ở cache 100.000. Đó là O(1): map cho ta node ngay, list xóa node cuối ngay. Còn NAIVE: chi phí tăng tuyến tính theo kích thước cache — 832 ns ở 1.000, 10.884 ns ở 10.000, 128.268 ns (128 µs!) ở 100.000. Đó là O(n): mỗi lần đuổi quét cả map. Ở cache 100 nghìn, naive chậm hơn 5862 lần bản đúng, và khoảng cách giãn ra khi cache lớn hơn — dấu hiệu kinh điển của O(n) so với O(1). Một cache lớn với naive sẽ dành phần lớn thời gian chỉ để tìm cái cần đuổi.

Một lần tôi đo hớ: "chỉ cần một map" và "dùng list là đủ"

Tôi vào đo với niềm tin thực dụng: "LRU thì cần map để tra nhanh; khi đầy thì tìm phần tử cũ nhất rồi bỏ, thế là xong, một cấu trúc là đủ". Đo phá tan: tìm phần tử ít dùng nhất trong map là quét O(n), và với cache 100 nghìn thì mỗi lần đuổi tốn 128 µs — chậm gần 6000 lần bản đúng, và cache lớn thì thảm họa. Một cấu trúc không đủ. Còn niềm tin ngược, cũng sai: "vậy dùng danh sách liên kết là đủ, nó giữ thứ tự dùng". Sai — tra cứu một key trong danh sách là duyệt O(n). Danh sách giữ thứ tự tốt nhưng tra chậm; map tra nhanh nhưng không có thứ tự. LRU O(1) bắt buộc kết hợp cả hai: map để tra, list đôi để giữ thứ tự, và map giữ con trỏ tới node list để mọi thao tác list thành O(1).

Bài học đo lường: LRU cache O(1) không phải MỘT cấu trúc mà là SỰ KẾT HỢP hai — HASH MAP (tra key O(1)) + DANH SÁCH LIÊN KẾT ĐÔI (thứ tự dùng: đưa lên đầu / đuổi cuối đều O(1)); dùng riêng một cái thì thao tác kia thành O(n) (naive map-quét-min đuổi O(n): 128.268 ns ở cache 100k, chậm 5862x bản đúng 21,9 ns, càng lớn càng tệ; chỉ list thì tra O(n)). Nếu tôi tin "một map là đủ", tôi tạo ra một cache chạy nhanh với cache nhỏ rồi bò như rùa với cache lớn — đúng lúc cache lớn mới cần hiệu năng. Sức mạnh của LRU nằm ở cách hai cấu trúc trỏ lẫn nhau, không ở cấu trúc nào riêng lẻ.

Vì sao điều này quan trọng khi lập trình

Hệ quả đầu tiên: cài LRU đúng chuẩn map + list đôi, hoặc dùng cấu trúc có sẵn. Nhiều ngôn ngữ có sẵn: LinkedHashMap (Java, với accessOrder=true), OrderedDict/functools.lru_cache (Python) đều dựa trên ý tưởng này. Nếu tự cài, đừng dùng một map với dấu thời gian rồi quét — đó là O(n) mỗi lần đuổi. Mẫu chuẩn là unordered_map<key, list_iterator> + list<(key,value)>, dùng splice để đưa node lên đầu O(1).

Hệ quả thứ hai: nhận ra khi một bài toán cần nhiều cấu trúc phối hợp. LRU là ví dụ kinh điển của "không có một cấu trúc nào làm được, phải kết hợp". Cùng mẫu này xuất hiện nhiều nơi: một hàng đợi ưu tiên có thể cập nhật khóa cần heap + map (chỉ số vị trí trong heap); một cấu trúc "top-k theo tần suất" cần map đếm + cấu trúc thứ tự. Khi một cấu trúc đơn không cho cả hai thao tác bạn cần ở O(1), hỏi "hai cấu trúc trỏ lẫn nhau có làm được không".

Hệ quả thứ ba là tinh thần đo lường: độ phức tạp của một cách cài phụ thuộc cấu trúc, và một tối ưu quan trọng nhất là chọn đúng sự kết hợp. Con số mang theo: LRU cache O(1) = HASH MAP (tra O(1)) + DANH SÁCH LIÊN KẾT ĐÔI (thứ tự dùng, lên đầu/đuổi cuối O(1)), map giữ con trỏ tới node list; cài bằng MỘT map rồi quét tìm min timestamp khi đuổi là O(n) — 128.268 ns/đuổi ở cache 100k (chậm 5862x bản đúng 21,9 ns), càng lớn càng tệ; workload trộn bản đúng 42,6 ns/thao tác. Chỉ map thì không có thứ tự dùng; chỉ list thì tra O(n) — phải CẢ HAI. Đôi khi cấu trúc dữ liệu đúng là hai cấu trúc, khéo léo nối với nhau.

Thử ba mươi giây

Cài LRU cache hai cách. Cách một: một hash map key → (value, số đếm lần dùng); khi đầy, lặp qua toàn bộ map tìm số đếm nhỏ nhất rồi xóa. Cách hai: một hash map key → iterator cộng một std::list giữ thứ tự; khi dùng, splice node lên đầu; khi đầy, xóa node cuối. Đổ vào cả hai vài triệu thao tác get/put với cache cỡ vài chục nghìn, và bấm giờ. Bạn sẽ thấy cách hai nhanh hơn hàng trăm tới hàng nghìn lần — và nếu tăng kích thước cache, khoảng cách giãn ra, vì cách một quét cả cache mỗi lần đuổi (O(n)) còn cách hai luôn O(1). Ba mươi giây đó cho bạn thấy điều mà "LRU chỉ là một cache đơn giản" giấu đi: để đạt O(1) cho cả tra cứu lẫn đuổi, bạn cần hai cấu trúc phối hợp — map cho tốc độ tra, list đôi cho thứ tự dùng — và chính sự kết hợp ấy, không phải cấu trúc nào riêng, là lời giải.