Swissmap
Go 1.24 mặc định sẽ dùng SwissMap, vậy SwissMap là gì? Tại sao nó lại quan trọng?
SwissMap và SwissTable cung cấp giải pháp cải tiến cho bảng băm hiệu năng cao, tiết kiệm bộ nhớ trong Golang.
Vấn đề ban đầu
Trong nhiều ứng dụng, bảng băm (hash table) đóng vai trò quan trọng, đặc biệt khi cần truy cập dữ liệu với tốc độ cao sử dụng bộ nhớ tối thiểu. Tuy nhiên, bảng băm tích hợp sẵn (built-in map) của Golang, mặc dù thuận tiện cho các trường hợp phổ thông, nó lại tiêu tốn nhiều bộ nhớ hơn và có thể không đủ nhanh cho các tình huống yêu cầu hiệu suất cao (ví dụ DoltDB).
Ý tưởng đằng sau SwissMap
Giải thuật SwissMap tạo ra bảng băm cho tốc độ truy cập nhanh hơn, đồng thời tiết kiệm bộ nhớ hơn so với map trong Golang. SwissMap dựa trên SwissTable, thiết kế bảng băm trong thư viện Abseil của Google, nổi tiếng với bố cục hiệu quả, thân thiện với cache. Thay vì dùng băm mở (open-hashing) như trong map của Golang, SwissTable sử dụng băm đóng (closed-hashing), cho phép tìm kiếm nhanh hơn. Thiết kế này tối ưu hóa việc sử dụng cache và hỗ trợ các lệnh SIMD (Single Instruction, Multiple Data) cho phép so sánh nhanh hơn, đạt được hệ số tải (load factor) cao hơn (14/16 so với 6.5/8 của Golang), cho phép lưu trữ nhiều dữ liệu hơn trong cùng một không gian bộ nhớ.
Cơ Chế
map Sử dụng giải thuật băm mở (open-hashing) trong đó, một khi xảy ra hiện tượng xung đột (collision - tức là các cặp khoá - giá trị (key-value) khác nhau có cùng 1 giá trị băm), thì các cặp khóa - giá trị đó được lưu trong cùng một “bucket”. Khi cần tìm kiếm dữ liệu, giải thuật sẽ nhanh chóng chạy đến đúng bucket, nhưng sau đó phải duyệt qua từng cặp khóa - giá trị trong bucket để tìm ra khóa phù hợp.
Để tối ưu hóa việc so sánh trong từng bucket, map sử dụng thêm các bit băm bổ sung (extra hash bits).Trước khi so sánh trực tiếp khóa truy vấn (query key) với một khóa tiềm năng, đầu tiên thuật toán sẽ so sánh băm 8-bit của mỗi khóa (không phụ thuộc vào băm của bucket) để xem liệu có khả năng khớp hay không. Bước tiền kiểm tra (pre-check) này có tỷ lệ dương tính giả (false-positive) là 1/256 và giúp tăng tốc đáng kể các tìm kiếm trong bucket trong toàn bộ bảng băm. Để tìm hiểu thêm về thiết kế của map tích hợp trong Golang, hãy tham khảo bài nói chuyện của Keith Randall tại GopherCon 2016: “Inside the Map Implementation.”
SwissTable sử dụng một cấu trúc (scheme) băm khác được gọi là băm đóng (closed-hashing). Thay vì gom nhóm các phần tử xung đột vào chung bucket, mỗi cặp khóa - giá trị trong bảng băm được gán một slot riêng. Vị trí của slot này được xác định bởi một thuật toán thăm dò (probing algorithm), với điểm bắt đầu được xác định bằng giá trị băm của khóa. Ví dụ đơn giản nhất là thăm dò tuyến tính, bắt đầu từ vị trí hash(key) mod size và dừng lại khi tìm thấy khóa mong muốn hoặc khi gặp một slot trống. Phương pháp thăm dò này được sử dụng để tìm cả các khóa hiện có và cả vị trí thích hợp để thêm các khóa mới (insert point). Giống như map trong Golang, SwissTable sử dụng các “băm ngắn” (short hashes) để tăng tốc quá trình kiểm tra trong khi thăm dò. Tuy nhiên, không giống như map, metadata băm của cặp khoá - giá trị được lưu trữ riêng biệt với dữ liệu khóa - giá trị.
Bố cục bộ nhớ phân đoạn của SwissTable là yếu tố chính giúp tăng hiệu suất của nó. Các chuỗi thao tác thăm dò trên bảng băm chỉ truy cập mảng metadata cho đến khi tìm thấy một băm ngắn khớp. Kiểu truy cập này tối ưu hóa tính cục bộ của bộ nhớ cache trong quá trình thăm dò. Một khi khớp giá trị băm trong metadata, các khóa tương ứng gần như chắc chắn cũng sẽ khớp.
Việc tách ra một một mảng metadata riêng biệt cũng cho phép sử dụng các lệnh SSE để so sánh đồng thời 16 băm ngắn! Sử dụng lệnh SSE không chỉ nhanh hơn mà còn là lí do SwissTable cho phép hệ số tải tối đa lên đến 14/16.
Quan sát thấy: các thăm dò âm (negative probes - tìm kiếm một khóa không có trong bảng) chỉ kết thúc khi gặp một slot trống. Càng ít slot trống trong bảng, chuỗi thao tác thăm dò trung bình sẽ càng dài (vì sẽ khó bắt gặp slot trống hơn). Để duy trì thời gian truy cập O(1) cho bảng băm, ta cần giơi shanj chuỗi thăm dò trung bình bằng một hệ số nhỏ và không đổi. Để đạt hiệu quả với việc sử dụng lệnh SSE, ta sẽ chia độ dài chuỗi thăm dò trung bình cho 16. Các phép đo thực nghiệm cho thấy ngay cả ở tải tối đa, số bước thăm dò trung bình ít hơn hai lần so sánh theo cụm 16! Nếu bạn muốn tìm hiểu sâu hơn về thiết kế của SwissTable, hãy xem bài nói chuyện của Matt Kulukundis tại CppCon 2017: “Designing a Fast, Efficient, Cache-friendly Hash Table, Step by Step”.