LRU cache tự cài trong Go: get/put O(1) bằng map và danh sách liên kết đôi

Cache có dung lượng hữu hạn, nên khi đầy phải loại bớt. LRU (Least Recently Used) là chính sách loại bỏ phổ biến nhất: bỏ phần tử lâu nhất chưa được dùng, vì thứ lâu không đụng tới nhiều khả năng sẽ không cần nữa. Nghe đơn giản, nhưng cài đúng và nhanh thì cần một mẹo hay: bạn phải làm hai việc đều trong O(1) — tra cứu một key, và cập nhật "thứ tự dùng gần đây".

Không cấu trúc đơn lẻ nào làm được cả hai: map tra cứu O(1) nhưng không biết thứ tự; danh sách liên kết đôi giữ thứ tự và chèn/xóa O(1) nhưng tra cứu O(n). Lời giải kinh điển là kết hợp cả hai — map trỏ thẳng vào node của danh sách. Bài này tự cài LRU cache từ đầu trong Go, đo thật hành vi loại bỏ và chứng minh get/put là O(1).

Ý tưởng: hai cấu trúc bù nhau

// LRU = Least Recently Used: khi đầy, loại phần tử LÂU NHẤT chưa dùng.
// Cần 2 việc đều O(1): (1) tra cứu theo key, (2) cập nhật thứ tự dùng.
// map -> tra cứu O(1) nhưng KHÔNG có thứ tự.
// danh sách liên kết đôi -> chèn/xóa/đẩy-lên-đầu O(1) nhưng tra cứu O(n).
// Kết hợp: map trỏ vào node của list -> cả hai việc đều O(1).

Cấu trúc

type LRU struct {
	cap   int
	ll    *list.List            // đầu = mới nhất, cuối = ít dùng nhất
	items map[int]*list.Element // key -> node trong list
}

container/list của Go là một danh sách liên kết đôi sẵn dùng. Quy ước: đầu danh sách là phần tử mới dùng nhất, cuối là ít dùng nhất. Map items ánh xạ key sang chính node trong danh sách — đây là cầu nối làm mọi thứ O(1).

Get: tra map rồi đẩy node lên đầu

func (c *LRU) Get(key int) (int, bool) {
	if el, ok := c.items[key]; ok {
		c.ll.MoveToFront(el) // dùng -> đẩy lên đầu (mới nhất)
		return el.Value.(*entry).val, true
	}
	return 0, false
}

Truy cập một key vừa trả giá trị, vừa đánh dấu nó là "vừa dùng" bằng cách đẩy node lên đầu danh sách. Vì map cho ta node trực tiếp, MoveToFront chỉ nối lại vài con trỏ — O(1), không quét.

Put: thêm vào đầu, loại cuối khi vượt sức chứa

func (c *LRU) Put(key, val int) {
	if el, ok := c.items[key]; ok { // đã có -> cập nhật + đẩy đầu
		el.Value.(*entry).val = val
		c.ll.MoveToFront(el); return
	}
	el := c.ll.PushFront(&entry{key, val}) // thêm vào đầu
	c.items[key] = el
	if c.ll.Len() > c.cap { // vượt sức chứa
		last := c.ll.Back()  // node cuối = ít dùng nhất
		c.ll.Remove(last)
		delete(c.items, last.Value.(*entry).key) // loại khỏi CẢ list và map
	}
}

Điểm dễ sai nhất khi tự cài: khi loại bỏ, phải xóa phần tử khỏi cả danh sách và map. Quên một trong hai gây rò rỉ bộ nhớ hoặc key "ma" trỏ vào node đã xóa. list.Back() cho node cuối (ít dùng nhất) trong O(1), và ta lấy key từ node đó để xóa khỏi map.

Hình 1: LRU cache tự cài — map ánh xạ key sang node của danh sách liên kết đôi; Get đẩy node lên đầu (đánh dấu vừa dùng), Put thêm vào đầu và loại node cuối (ít dùng nhất) khỏi cả list và map khi vượt sức chứa — mọi thao tác O(1).

Đo thật: hành vi loại bỏ và hiệu năng

Dựng LRU sức chứa 3, minh họa loại bỏ:

Put 1,2,3 -> cache đầy [3,2,1] (mới->cũ)
Get(1)    -> đẩy 1 lên đầu: [1,3,2]
Put(4,40) -> loại 2 (ít dùng nhất): [4,1,3]
Get(2) còn? false (đã bị loại) | Get(4)=40 có? true
Thứ tự hiện tại (mới->cũ): 4 1 3
Tổng số lần loại bỏ: 1

Đọc kỹ hành vi: sau khi thêm 1,2,3 thì thứ tự là [3,2,1] (3 mới nhất). Get(1) đẩy 1 lên đầu thành [1,3,2] — giờ 2 là ít dùng nhất. Khi Put(4,40) làm cache vượt sức chứa 3, nó loại đúng 2 (ít dùng nhất), không phải 1 hay 3. Get(2) trả false (đã bị loại), Get(4) trả 40. Chính hành động Get(1) đã "cứu" 1 khỏi bị loại — đó là bản chất của LRU: dùng gần đây thì sống lâu hơn.

Về hiệu năng, benchmark một vòng Put (có loại bỏ khi vượt sức chứa) + Get:

BenchmarkLRUPutGet   79.60 ns/op   64 B/op   2 allocs/op

79.6 ns cho cả put lẫn get, và quan trọng nhất: thời gian này không tăng theo số phần tử trong cache — đó là O(1) thật sự. Bí quyết là map cho tra cứu O(1) cộng với danh sách liên kết đôi cho đẩy/xóa node O(1); vì map trỏ thẳng vào node, ta không bao giờ phải quét danh sách.

Hình 2: Đo thật LRU sức chứa 3 — loại đúng phần tử 2 (ít dùng nhất sau khi Get(1) cứu 1), thứ tự cuối 4 1 3; benchmark get+put 79.6 ns/op không tăng theo số phần tử, chứng minh O(1) hằng số nhờ map trỏ vào node danh sách.

Đánh đổi cần cân nhắc

Bản này không an toàn cho đồng thời — phải tự bọc khóa. Code trên không có khóa; nhiều goroutine cùng gọi Get/Put sẽ đua tranh trên cả map lẫn list (chạy với -race sẽ tố cáo ngay). Để dùng đa luồng, bọc mọi thao tác trong sync.Mutex. Lưu ý: ngay cả Get cũng ghi (nó gọi MoveToFront), nên không thể dùng RWMutex với RLock cho Get — phải Lock đầy đủ, hoặc thiết kế lại (ví dụ cập nhật thứ tự kiểu xấp xỉ). Đây là lý do các thư viện LRU sản xuất (như hashicorp/golang-lru) có phiên bản khóa sẵn.

LRU không phải chính sách tốt nhất cho mọi tải. LRU giả định "vừa dùng thì sắp dùng lại" (tính cục bộ thời gian). Đúng cho nhiều tải, nhưng có ca xấu: một lần quét tuần tự qua tập dữ liệu lớn hơn cache sẽ đẩy hết phần tử nóng ra ngoài (cache pollution) mà không phần tử quét nào được dùng lại — làm hỏng cache. Với tải như vậy, các chính sách như LFU (theo tần suất) hoặc ARC/2Q (chống quét) tốt hơn — nhưng phức tạp hơn để cài.

Chi phí bộ nhớ cho cấu trúc phụ. Mỗi phần tử tốn thêm một node danh sách (hai con trỏ) và một mục map, ngoài giá trị thật. Với phần tử nhỏ (như int), overhead này đáng kể so với dữ liệu. LRU đáng dùng khi giá trị được cache đắt để tính lại hoặc lấy về (query DB, gọi API), nơi tiết kiệm nhờ hit áp đảo overhead cấu trúc.

Ba ý mang về

1. LRU cache cần cả tra cứu và cập nhật thứ tự đều O(1) — không cấu trúc đơn lẻ nào làm được, nên kết hợp map (tra cứu O(1)) với danh sách liên kết đôi (thứ tự dùng, chèn/xóa O(1)), map trỏ thẳng vào node để không phải quét.
2. Loại đúng phần tử ít dùng nhất, O(1) hằng số: đo thật, cache sức chứa 3 loại đúng phần tử 2 (ít dùng nhất sau khi Get(1) cứu 1), và benchmark cho 79.6 ns/op cho cả put+get kể cả khi có loại bỏ — thời gian không tăng theo số phần tử.
3. Nêu rõ đánh đổi: bản cơ bản không an toàn đồng thời (phải bọc sync.Mutex, và Get cũng ghi nên không RLock được), LRU bị quét tuần tự làm hỏng cache (cân nhắc LFU/ARC cho tải đó), và có overhead bộ nhớ cho node+map nên chỉ đáng khi giá trị cache đắt để lấy lại.

Bài tập làm thử

Bài 1 (đọc hiểu). LRU cache sức chứa 3 vừa thực hiện Put(1,10), Put(2,20), Put(3,30) theo thứ tự đó (không có thao tác Get nào ở giữa). Thứ tự danh sách hiện tại (mới→cũ) là gì? Nếu Put(4,40) được gọi tiếp theo, phần tử nào bị loại?

Bài 2 (sửa lỗi). Đoạn mã Put sau có lỗi khiến bộ nhớ bị rò rỉ dần theo thời gian. Chỉ ra thiếu gì so với mẫu bài đã trình bày.

func (c *LRU) Put(key, val int) {
	if el, ok := c.items[key]; ok {
		el.Value.(*entry).val = val
		c.ll.MoveToFront(el)
		return
	}
	el := c.ll.PushFront(&entry{key, val})
	c.items[key] = el
	if c.ll.Len() > c.cap {
		last := c.ll.Back()
		c.ll.Remove(last)
	}
}

if c.ll.Len() > c.cap {
	last := c.ll.Back()
	c.ll.Remove(last)
	delete(c.items, last.Value.(*entry).key)
}

Bài 3 (vận dụng thực tế). Dịch vụ của bạn cache kết quả gọi một API bên ngoài chậm (mỗi lần gọi mất 200ms), dùng LRU sức chứa 1000. Dựa vào đánh đổi nêu trong bài, giải thích tại sao LRU đáng dùng ở đây, kể cả với overhead bộ nhớ của node và map.

Bài 4 (bẫy/đánh đổi). Hai goroutine cùng gọi cache.Get(5) đồng thời trên bản LRU cài trong bài (không có khóa). Điều gì có thể xảy ra, và tại sao không thể chỉ dùng sync.RWMutex với RLock() cho hàm Get?

Bài 5 (đọc hiểu số liệu Go). Benchmark cho BenchmarkLRUPutGet 79.60 ns/op 64 B/op 2 allocs/op, và bài khẳng định "thời gian này không tăng theo số phần tử trong cache". Giải thích tại sao thao tác loại bỏ phần tử ít dùng nhất (khi cache đầy) không làm chậm thao tác này khi cache có 10 phần tử so với khi có 10 triệu phần tử.

Phần sau ta xét công cụ tìm bug tự động tích hợp sẵn trong Go: fuzzing native (từ Go 1.18) — cách go test -fuzz tự sinh đầu vào ngẫu nhiên tìm panic và ca biên, đo thật một bug được tìm ra.