Map evacuation trong Go: mở rộng map mà không gây khựng, đo tận nanosecond

Bài map internals cho thấy prealloc nhanh hơn nhiều so với để map tự lớn — vì map tự lớn phải "mở rộng" (evacuation). Nhưng mở rộng một hash table là thao tác đắt: khi số bucket gấp đôi, mọi entry phải được băm lại và chuyển sang bucket mới. Nếu làm tất cả trong một lần, một thao tác m[k]=v bỗng khựng O(n) — với map lớn là hàng trăm mili-giây. Go giải quyết bằng evacuation tăng dần. Bài này đo trực tiếp rằng nó thật sự tránh được khựng.

Cơ chế: load factor 6.5 và evacuation tăng dần

Map Go mở rộng khi số entry vượt 6.5 lần số bucket (load factor 6.5). Khi đó:

1. Runtime cấp một mảng bucket mới gấp đôi (B → B+1), giữ mảng cũ làm oldbuckets.
2. Việc chuyển entry sang bucket mới được làm tăng dần (incremental): mỗi thao tác insert/delete sau đó di chuyển 1-2 bucket cũ sang mới.
3. Trong lúc đang chuyển, tra một khóa phải kiểm cả oldbuckets lẫn buckets mới.
4. Khi mọi bucket cũ đã chuyển hết, oldbuckets được giải phóng.

Ngoài "size growth" (gấp đôi khi load factor cao), còn có "same-size growth": khi map có quá nhiều overflow bucket (thường do xóa nhiều làm map thưa), Go tổ chức lại cùng số bucket để gom entry, giảm chuỗi overflow.

Hình 1: Map mở rộng khi count > 6.5 × bucket. Cấp mảng bucket gấp đôi, giữ oldbuckets, rồi chuyển entry TĂNG DẦN qua nhiều thao tác. Tra khóa kiểm cả hai mảng trong lúc chuyển.

Đo thật: insert chậm nhất chỉ 0.6 ms

Nếu evacuation làm một lần, ta sẽ thấy một thao tác insert cực chậm (khi map đầy, phải chuyển toàn bộ). Đo thời gian mỗi insert khi chèn 2 triệu entry vào map tự lớn:

for i := 0; i < N; i++ {
    t := time.Now()
    m[i] = i
    d := time.Since(t)  // tìm insert chậm nhất
}

Hình 2: Insert trung bình 119 ns, chậm nhất chỉ 0.6 ms — nhỏ hơn ~330 lần so với ~200 ms nếu chuyển hết 2 triệu entry một lần. Bộ nhớ map tăng theo entry với các bậc nhảy khi bucket gấp đôi.

Kết quả chứng minh evacuation tăng dần:

• Insert trung bình 119 ns, insert chậm nhất chỉ 0.6 ms (tại i≈1,7 triệu).
• Nếu evacuation làm một lần: chuyển hết 2 triệu entry trong một insert sẽ tốn ~2.000.000 × 100 ns = ~200 ms — khựng khủng khiếp trong một thao tác.
• Thực tế max chỉ 0.6 ms, nhỏ hơn ~330 lần. Việc chuyển entry được rải qua nhiều insert sau đó, nên không thao tác nào phải gánh toàn bộ.

Trung thực: spike 0.6 ms còn lại chủ yếu đến từ việc cấp mảng bucket mới gấp đôi (một allocation lớn khi map đã có hàng trăm nghìn bucket), không phải từ việc chuyển entry. Việc chuyển entry mới là phần được rải đều — đó là điều evacuation tăng dần giải quyết.

Ứng dụng thực tế

Map Go an toàn cho dịch vụ độ trễ thấp ngay cả khi lớn dần. Nhờ evacuation tăng dần, một map lớn dần trong server không gây spike độ trễ hàng trăm ms mỗi lần mở rộng. Đây là lý do bạn có thể dùng map làm cache/index trong dịch vụ nhạy độ trễ mà không lo khựng.

Nhưng prealloc vẫn tốt hơn khi biết cỡ. Evacuation tăng dần giảm khựng, nhưng vẫn có chi phí (chuyển entry rải rác, kiểm hai mảng trong lúc chuyển, spike cấp bucket). make(map[K]V, n) cấp đủ bucket ngay, tránh hẳn quá trình mở rộng — nhanh hơn và không có spike nào (bài map internals đã đo).

Xóa nhiều không thu nhỏ map. Map không bao giờ giảm số bucket khi bạn xóa entry — nó chỉ tổ chức lại (same-size growth). Một map từng có 10 triệu entry rồi xóa còn 10 entry vẫn giữ bộ nhớ cho hàng triệu bucket. Muốn giải phóng, phải tạo map mới và copy sang.

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

Evacuation tăng dần đổi khựng lấy bộ nhớ gấp đôi tạm thời. Trong lúc chuyển, cả oldbuckets và buckets mới cùng tồn tại — map dùng ~gấp đôi bộ nhớ tới khi chuyển xong. Với map rất lớn đang mở rộng, đây là spike bộ nhớ đáng kể. Đánh đổi có chủ đích: độ trễ ổn định quan trọng hơn bộ nhớ đỉnh cho hầu hết dịch vụ.

Tra khóa hơi chậm hơn trong lúc đang mở rộng. Vì phải kiểm cả hai mảng bucket, các thao tác trong giai đoạn chuyển tốn thêm chút. Không đáng kể với hầu hết code, nhưng benchmark map ngay lúc mở rộng có thể thấy dao động.

Load factor 6.5 là chi tiết cài đặt. Con số 6.5, cách chọn bucket để chuyển, ngưỡng overflow — đều là chi tiết runtime có thể đổi (Go 1.24 chuyển sang Swiss Tables với cơ chế khác). Dựa vào tính chất "mở rộng tăng dần, không khựng lớn", không phải con số cụ thể.

Ba ý mang về

1. Map mở rộng khi load factor vượt 6.5: khi count > 6.5 × số bucket, Go cấp mảng bucket gấp đôi và giữ oldbuckets — rồi chuyển entry sang tăng dần qua nhiều thao tác sau đó, trong lúc chuyển tra khóa kiểm cả hai mảng.
2. Evacuation tăng dần tránh khựng O(n): đo thật, chèn 2 triệu entry thì insert chậm nhất chỉ 0.6 ms — nhỏ hơn ~330 lần so với ~200 ms nếu chuyển hết một lần; đây là lý do map Go an toàn cho dịch vụ độ trễ thấp khi lớn dần.
3. Prealloc vẫn tốt hơn, và map không thu nhỏ: make(map, n) tránh hẳn mở rộng (không spike); và map không giảm bucket khi xóa — muốn giải phóng bộ nhớ phải tạo map mới, đánh đổi của evacuation tăng dần là bộ nhớ gấp đôi tạm thời.

Bài tập làm thử

Bài 1 (đọc hiểu). Map sẽ kích hoạt mở rộng khi nào? Nếu một map có 20 bucket, cần bao nhiêu entry để vượt load factor và kích hoạt mở rộng?

Bài 2 (đọc hiểu số liệu). Bài đo cho thấy insert trung bình 119 ns nhưng insert chậm nhất là 0,6 ms (khoảng 5223 lần trung bình). Bài viết giải thích spike này chủ yếu đến từ đâu — có phải từ việc chuyển entry cũ sang bucket mới không?

Bài 3 (vận dụng thực tế/sửa lỗi). Đoạn code dưới đây tạo một map với 10 triệu entry, xoá gần hết chỉ còn giữ 10 entry, rồi mong bộ nhớ giảm mạnh. Điều này có đúng không? Nếu muốn thực sự giải phóng bộ nhớ thì phải làm gì?

m := make(map[int]int, 10_000_000)
for i := 0; i < 10_000_000; i++ {
    m[i] = i
}
for i := 10; i < 10_000_000; i++ {
    delete(m, i)
}
// kỳ vọng bộ nhớ của m giảm mạnh vì chỉ còn 10 entry

m2 := make(map[int]int, 10)
for k, v := range m {
    m2[k] = v
}
m = m2

Bài 4 (đọc hiểu cơ chế). Trong lúc map đang mở rộng (evacuation chưa xong), tra một khóa k cần kiểm những mảng bucket nào? Vì sao?

Bài 5 (bẫy/đánh đổi). Bài viết kết luận "evacuation tăng dần đổi khựng lấy bộ nhớ gấp đôi tạm thời." Hãy giải thích đánh đổi này, và so sánh với việc dùng make(map[K]V, n) khi biết trước cỡ — cách nào tránh được cả hai vấn đề?

Phần sau ta chuyển sang một kiểu cơ bản có bố cục bộ nhớ tinh tế: Phần sau mổ xẻ string internals — vì sao string bất biến, cấu trúc header 16 byte, và chuyển đổi string ↔ []byte tốn kém thế nào.