LRU chỉ cần một map? Cái bẫy O(n) khiến cache lớn chậm 5862 lần

Hình dung một quầy giữ đồ đông khách. Muốn nó chạy trơn, bạn cần hai thứ cùng lúc: một tập phiếu đánh số để khách đưa phiếu là lấy được đúng món trong tích tắc, và một cái giá xếp các món theo thứ tự lần cuối ai đó chạm vào để khi hết chỗ, bạn biết ngay món nào lâu nhất không ai đụng mà đem cất kho. Thiếu tập phiếu, tìm một món phải lục cả giá. Thiếu cái giá theo thứ tự, muốn biết bỏ món nào phải đi hỏi từng món "lần cuối bạn được lấy là bao giờ". Một LRU cache cần đúng hai thứ đó — và đó là lý do nó không phải một cấu trúc, mà là hai.

LRU cache (Least Recently Used) ở 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: 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. 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.

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ử — đúng cảnh đi hỏi từng món trên giá.

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

• Hash map: key → con trỏ tới một node trong danh sách. Tra cứu O(1) — tập phiếu đánh số.
• Danh sách liên kết đôi: giữ thứ tự dùng. Đầu danh sách = mới dùng nhất, cuối = ít dùng nhất. Khi một phần tử vừa được dùng, đưa node của nó lên đầu — O(1) vì map đã cho ta con trỏ tới node. Khi đuổi, xóa node cuối — O(1). Đây là cái giá xếp theo thứ tự chạm.

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ôi trường đo: container gcc:13 trên host ARM AArch64, g++ -O2, mỗi số lấy MIN sau warmup. Con số tuyệt đối đổi theo máy; cái cần nhìn là GOOD phẳng theo kích thước (O(1)) còn NAIVE dốc lên tuyến tính (O(n)), nên tỉ số càng lớn với cache càng to.)

Hai niềm tin đối nghịch, cùng sai

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à đủ". Con số bác thẳng: 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 đủ.

Nhưng niềm tin ngược lại cũng sai: "vậy dùng danh sách liên kết là đủ, nó giữ sẵn 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). Sức mạnh 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ề đến code hằng ngày

Điều đầu tiên: cài LRU đúng chuẩn map + list đôi, hoặc dùng cấu trúc có sẵn. 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 trong C++ là unordered_map<key, list_iterator> + list<(key,value)>, dùng splice để đưa node lên đầu O(1).

Điều 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ãy hỏi "hai cấu trúc trỏ lẫn nhau có làm được không".

Và bạn sẽ vui khi biết rằng ở các ngôn ngữ cao cấp, đúng sự kết hợp này thường được đóng gói sẵn dưới một cái tên gọn. Java có LinkedHashMap — chính là hash map cộng danh sách liên kết đôi bên trong — và bật cờ accessOrder=true rồi override removeEldestEntry là bạn có ngay một LRU O(1), khỏi tự nối hai cấu trúc. Python thì functools.lru_cache (và OrderedDict.move_to_end) làm y hệt dưới nắp capo. Ở tầng hệ thống, Redis cho phép chọn chính sách đuổi allkeys-lru, còn các database (bộ đệm trang của PostgreSQL, InnoDB của MySQL) dùng các biến thể xấp xỉ LRU như CLOCK/second-chance — hy sinh một chút chính xác để tránh chi phí duy trì danh sách chặt chẽ dưới tải cao. Cùng một ý tưởng phiếu-đánh-số-cộng-giá-theo-thứ-tự, được tinh chỉnh cho từng quy mô.

Muốn tự thấy thì 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). Vài phút đó 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.