Bộ nhớ nhanh thì đắt và ít; dữ liệu thì nhiều. Nên khắp mọi tầng của một hệ thống — cache CPU, bộ đệm trang của hệ điều hành, cache của trình duyệt, Redis trước cơ sở dữ liệu — đều có một câu hỏi giống nhau: khi chỗ chứa đầy và cần nhường chỗ cho mục mới, đuổi mục nào? Câu trả lời phổ biến nhất là LRU — đuổi mục lâu nhất không được dùng tới. Bài này cài LRU đúng chuẩn O(1) rồi đo hai thứ: cấu trúc dữ liệu nào làm nó nhanh, và LRU thật sự trúng nhiều tới đâu — trong đó có một trường hợp LRU tệ đến mức bất ngờ.
LRU cần hai cấu trúc ghép lại
LRU giữ K mục và, khi đầy, đuổi mục được dùng xa nhất trong quá khứ. Đặt cược của nó là tính cục bộ thời gian: cái vừa dùng nhiều khả năng sắp được dùng lại. Để phục vụ mỗi lần truy cập, LRU phải làm ba việc thật nhanh: tra một khóa có trong cache không, đánh dấu một khóa là "vừa dùng" (đưa lên đầu thứ tự), và tìm mục "cũ nhất" để đuổi. Không cấu trúc đơn lẻ nào làm cả ba trong O(1).
Cách cài chuẩn ghép hai cấu trúc. Một bảng băm ánh xạ khóa sang nút, cho việc tra tức thì O(1). Một danh sách liên kết đôi xâu các nút theo thứ tự dùng gần đây: đầu danh sách là mục vừa chạm, cuối là mục cũ nhất. Mỗi lần truy cập trúng, ta gỡ nút khỏi vị trí hiện tại và móc lại lên đầu — mà danh sách liên kết đôi làm việc gỡ-và-móc này trong O(1) (chỉ sửa vài con trỏ), điều một mảng không làm nổi vì phải dịch phần tử. Khi đầy, đuổi chính là nút ở cuối. Băm lo tốc độ tra, danh sách lo thứ tự — hai điểm yếu bù cho nhau.
Đo: O(1) so với O(n) ngây thơ
Để thấy vì sao phải ghép hai cấu trúc, tôi cài thêm một bản LRU "ngây thơ": chỉ một mảng các mục kèm dấu thời gian, mỗi lần truy cập quét tuyến tính để tìm khóa, và khi đầy lại quét tuyến tính lần nữa để tìm mục cũ nhất — cả hai đều O(n) theo kích thước cache. Rồi đo thời gian mỗi thao tác của hai bản ở các cỡ cache tăng dần:
Thời gian mỗi thao tác (ns), workload Zipf:
cache 100 : O(1) hash+DLL = 22 ns | O(n) ngây thơ = 193 ns
cache 1.000 : O(1) hash+DLL = 27 ns | O(n) ngây thơ = 1.124 ns
cache 10.000 : O(1) hash+DLL = 14 ns | O(n) ngây thơ = 4.526 ns
Bản O(1) giữ thời gian phẳng — quanh 14–27 ns bất kể cache lớn cỡ nào, đúng như một cấu trúc O(1) phải thế. Bản O(n) ngây thơ tăng tuyến tính theo cache: 193 → 1.124 → 4.526 ns. Ở cache 10.000 mục, bản đúng nhanh hơn 323 lần. Đây là lý do thực tế của việc ghép băm với danh sách: không phải để trông "học thuật", mà vì một cache lớn cài sai cấu trúc sẽ chậm gấp hàng trăm lần — và cache thì luôn muốn lớn.
Đo tỉ lệ trúng: lợi giảm dần rất nhanh
Nhưng tốc độ mỗi thao tác chỉ là nửa câu chuyện. Cái người ta thật sự quan tâm ở một cache là tỉ lệ trúng (hit rate): bao nhiêu phần trăm truy cập tìm thấy dữ liệu sẵn trong cache, khỏi phải xuống nguồn chậm. Tôi chạy một workload Zipf (phân bố 80–20 điển hình của truy cập thực: ít khóa nóng, rất nhiều khóa nguội) trên 100.000 khóa, 2 triệu lượt, và đo hit rate của LRU theo kích thước cache:
Tỉ lệ trúng của LRU theo cache size (Zipf, 100K khóa):
cache 100 : 29,0%
cache 2.000 : 57,7%
cache 10.000 : 75,1%
cache 50.000 : 94,8%
Con số tăng, nhưng hãy nhìn lợi trên mỗi ô thêm vào. Từ 100 lên 2.000 mục (thêm 1.900 ô) hit nhảy từ 29% lên 57,7%. Nhưng từ 2.000 lên 50.000 (thêm 48.000 ô — gấp 24 lần số ô vừa rồi) chỉ thêm được 37 điểm phần trăm. Cache to gấp 25 lần không cho hit tốt gấp 25 lần; nó cho một chút cải thiện với chi phí bộ nhớ khổng lồ. Đây là lợi giảm dần: mấy khóa nóng nhất được cache che ngay với ít ô đầu tiên; các ô sau chỉ bắt được những khóa ngày một nguội, hiếm được hỏi lại. Đo hớ đầu tiên của tôi là tưởng "cache to hơn luôn tốt hơn nhiều" — đường cong nói ngược: sau khi cache đã chứa được vùng làm việc (working set) nóng, mỗi ô thêm gần như vô ích.
Một lần tôi đo hớ nặng hơn: LRU có lúc là tệ nhất
Định kiến lớn hơn mà tôi mang vào là "LRU là chính sách đuổi tốt nhất". Nó thường tốt, nhưng "tốt nhất" là một tuyên bố về mọi workload, và tôi đem đo. Trên chính workload Zipf, so LRU với FIFO (đuổi mục vào sớm nhất, bất kể có dùng hay không) và với đuổi ngẫu nhiên:
cache = 2.000, tỉ lệ trúng theo chính sách:
Zipf (có cục bộ thời gian): LRU 57,7% | FIFO 53,6% | ngẫu nhiên 53,6%
Đúng như kỳ vọng: LRU thắng, vì nó khai thác đúng tính cục bộ thời gian mà Zipf có. Nhưng rồi tôi đổi sang một workload khác — một lượt quét tuần tự lặp vòng qua 3.000 khóa (0, 1, 2, ..., 2999, rồi lại 0, 1, 2...), với cache chỉ chứa 2.000:
QUÉT vòng 3.000 khóa (lớn hơn cache 2.000):
LRU 0,0% | FIFO 0,0% | ngẫu nhiên 41,6%
LRU trúng 0% — không một lần nào! Đây là ca bệnh kinh điển của LRU. Khi bạn quét vòng qua nhiều mục hơn sức chứa, thì đúng vào lúc bạn quay lại một khóa, LRU đã vừa đuổi nó đi (nó là mục "cũ nhất" ngay trước khi bạn cần lại). LRU đuổi chính xác cái sắp cần, mỗi lần, một cách hệ thống. FIFO cũng chết y hệt (0%). Nhưng đuổi ngẫu nhiên lại được 41,6%: vì nó không đuổi theo quy luật nào, một phần may mắn số mục vẫn còn đó khi vòng quét quay lại. Trên workload này, chính sách "ngu ngốc" đánh bại LRU tuyệt đối.
Bài học đo lường: "tốt nhất" không có nghĩa nếu chưa hỏi "trên mẫu truy cập nào". LRU tối ưu cho cục bộ thời gian và tệ nhất cho quét tuần tự; đó là lý do các hệ thống thật (như bộ đệm của PostgreSQL hay Linux) không dùng LRU thuần mà dùng các biến thể chống quét (LRU-K, ARC, hay tách vùng cho scan) — chính vì đã đo và thấy cái hố này.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: cài LRU thì ghép băm với danh sách liên kết đôi, đừng quét mảng. Với cache vài chục mục thì cách nào cũng được, nhưng cache lớn mà cài O(n) sẽ chậm gấp hàng trăm lần — và điều trớ trêu là cache tồn tại để tăng tốc, nên một cache tự nó chậm là phản tác dụng. Nhiều ngôn ngữ đã có sẵn: OrderedDict của Python (hay functools.lru_cache), LinkedHashMap của Java (chế độ access-order) — chúng chính là băm-cộng-danh-sách gói lại.
Hệ quả thứ hai: đừng mặc định "thêm cache là hết chậm". Đo đường cong hit theo kích thước trước khi tăng RAM: nếu bạn đã ở phần bằng phẳng của đường cong (đã chứa được vùng làm việc), gấp đôi cache tốn gấp đôi tiền mà gần như không thêm hit. Số tiền đó có khi đáng để đầu tư vào chỗ khác — làm nguồn nhanh hơn, hay giảm chính lượng dữ liệu nóng.
Hệ quả thứ ba là bài học đo lường bao trùm: hiệu quả của một chính sách cache phụ thuộc hoàn toàn vào mẫu truy cập, nên phải đo trên workload thật của bạn. Con số mang theo: LRU cài O(1) bằng băm + danh sách liên kết đôi (nhanh 323 lần bản O(n) ở cache 10.000); hit rate của nó có lợi giảm dần theo kích thước (cache gấp 25 lần chỉ thêm 37 điểm hit); và trên một lượt quét tuần tự lớn hơn cache, LRU trúng 0% — tệ nhất có thể — trong khi đuổi ngẫu nhiên được 41,6%. "Cache to hơn" và "LRU là tốt nhất" đều là những câu nghe hiển nhiên mà đo lên thì có điều kiện. Đo workload của bạn, đừng tin khẩu hiệu.
Thử ba mươi giây
Nếu bạn dùng Python, functools.lru_cache cho bạn một LRU miễn phí trên bất kỳ hàm nào: trang trí một hàm tính chậm bằng @lru_cache(maxsize=128), gọi nó nhiều lần với các đối số lặp lại, rồi in hàm.cache_info() — bạn sẽ thấy hits, misses, và currsize. Thử tăng maxsize gấp đôi và xem hits có tăng tương xứng không (thường là không, nếu vùng làm việc của bạn đã vừa). Rồi thử một mẫu truy cập "quét": gọi hàm với dãy đối số 0,1,...,N,0,1,...,N mà N lớn hơn maxsize — bạn sẽ thấy hits tụt về gần 0, tận mắt cái hố quét-tuần-tự mà bài này đo, và hiểu vì sao cỡ cache và mẫu truy cập phải được nhìn cùng nhau.
