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.

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.