Chính sách cache 'tốt nhất' đôi khi trúng đúng 0% — thua cả tung xúc xắc

Bàn làm việc của bạn chỉ để vừa dăm cuốn sách, còn cả giá thì hàng trăm. Khi cần lấy cuốn mới mà bàn đã đầy, bạn cất bớt cuốn nào? Trực giác ai cũng giống nhau: cất cuốn lâu nhất không đụng tới. Đó chính là LRU (least recently used), và nó có mặt ở mọi tầng của một hệ thống — cache CPU, bộ đệm trang hệ điều hành, cache trình duyệt, Redis đứng trước cơ sở dữ liệu. Câu hỏi "chỗ đầy rồi, đuổi mục nào" là chung, và LRU là câu trả lời phổ biến nhất. Tôi 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à nó thật sự trúng nhiều tới đâu — trong đó có một trường hợp LRU tệ đến mức tôi phải đọc lại kết quả hai lần.

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(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.

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. Tôi đã hố khi 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.

Và có lúc LRU 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.

Rút ra một điều: "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ề đến code hằng ngày

Điều đầ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, hay Caffeine/Guava CacheBuilder cho cache production — chúng chính là băm-cộng-danh-sách gói lại; Go thì có container/list ghép với map, hay thư viện hashicorp/golang-lru.

Điều 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.

Và cái hố quét-tuần-tự ở trên chính là thứ những người vận hành cơ sở dữ liệu phải sống chung. Một truy vấn quét cả bảng lớn hơn bộ đệm sẽ đẩy sạch vùng dữ liệu nóng ra khỏi cache nếu chính sách là LRU thuần — nên PostgreSQL cố tình dùng vòng đệm nhỏ (ring buffer) riêng cho các lần seq-scan lớn để không giẫm nát shared_buffers, còn MySQL InnoDB chia buffer pool thành vùng "young/old" đúng để chống mẫu quét này. Ở tầng ứng dụng, đây là lý do một job báo cáo chạy đêm quét toàn bộ dữ liệu có thể làm chậm cả API ban ngày: nó không "dùng nhiều RAM" một cách vô hại, nó đuổi mất đúng những gì người dùng cần. Mẫu số chung: 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 — "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.

Muốn tự thấy thì với Python, functools.lru_cache cho bạn một LRU miễn phí: 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, 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 đã vừa). Rồi thử một mẫu "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.