Hàm băm và ứng dụng (Phần 2)
Hàm băm phi mật mã (Non-cryptographic hash function)
Ở phần trước chúng ta đẵ tìm hiểu về loại hàm băm mật mã, các bạn có thể xem tại đây. Nếu chúng ta bỏ qua một số tính chất bảo mật nhất định để đổi lấy tốc độ thực thi nhưng vẫn giữ được độ phân phối tốt thì các hàm băm phi mật mã thích hợp hơn cả. Sự khác biệt giữa hàm băm phi mật mã và hàm băm mật mã đó chính độ khả thi tính toán để có thể tìm được thông điệp gốc từ dãy hash (reversable). Điều này có nghĩa là khả năng đụng độ (collision) sẽ cao hơn và khả năng lan truyền (avalanche effect) thấp hơn so với các` hàm băm mật mã dẫn đến các giá trị hash có thể trùng nhau. Một số hàm băm thuộc loại phi mật mã có thể kể đến như MurmurHash3, FNV1, SuperFastHash, CityHash, xxHash… Ở bài viết này tôi sẽ tập trung nói về hàm xxHash vì nó khá là mới mẻ và cực kỳ nhanh.
xxHash
Ví dụ đơn cử ở team ZaloPay đang sử dụng hàm xxHash để băm các key. Mặc dù là một hàm băm rất nhanh nhưng độ bảo mật của xxHash vẫn đảm bảo tốt. xxHash không phải là một hàm băm mật mã mạnh, ví dụ như họ SHA nhưng nó vẫn đạt 10 điểm trên bài test SMHasher về độ phân phối (distribution), khả năng đụng độ (collision) và hiệu năng (performance). Số điểm này ngang với điểm của hai hàm băm mật mã trước kia là MD5 và SHA1. Tính duy nhất (Uniqueness) của xxHash là tương đương với MD5 nhưng khác biệt so với SHA1.
Tốc độ
xxHash được thiết kế từ đầu để chạy nhanh nhất có thể trên các CPU hiện đại. Về tốc độ, ta tiến hành benchmark hai implementation của xxHash tương ứng với hai hệ kiến trúc 32-bit và 64-bit. Ở bản 32-bit, xxHash có thể hash lượng lớn data với tốc độ 5.4 Gb/s tức là 324 Gb/minute, nhanh gấp 16 lần so với MD5 (0.33 Gb/s) và 20 lần so với SHA1 (0.28 Gb/s). Ở phiên bản 64-bit, tốc độ được tăng lên rất nhiều: 13 Gb/s tức là khoảng 780 Gb/minute. Mặc dù ta có thể chạy phiên bản xxHash 64-bit trên kiến trúc 32-bit nhưng tốc độ lại bị giảm chỉ còn 1.9 Gb/s. Trong khi đó phiên bản xxHash 32-bit chạy trên kiến trúc 64-bit lại có tốc độ tăng lên thành 6.8 Gb/s. Bảng sau hiện thị thông số benchmark của các hàm băm trên bài test SMHasher biên dịch với Visual C trên Windows Seven 32-bit ở chế độ đơn luồng:
Thuật toán
Hầu hết các hàm băm phi mật mã, như FNV duyệt qua từng byte của dữ liệu đầu vào. Điều này dẫn đến lệ thuộc khiến cho CPU bị đình trệ (stalling) vì làm việc trên byte hiện tại yêu cầu công việc xử lý ở byte trước đó phải hoàn tất. Có những thuật toán đã cải thiện vấn đề này đôi chút bằng cách duyệt qua từng khối byte một lần. Ví dụ như CRC Slicing-by-4/8/16 xử lý 4/8/16 byte mỗi bước thay vì chỉ 1 byte nên tốc độ hash được tăng. Tuy nhiên, chúng ta vẫn dính phải vấn đề ban đầu: làm việc trên block hiện tại yêu cầu công việc xử lý ở block trước đó phải hoàn tất!
Để dứt điểm triệt để vấn đề phụ thuộc giữa các thành phần của dữ liệu, xxHash chia nhỏ dữ liệu đầu vào thành bốn luồng độc lập. Mỗi luồng như vậy sẽ xử lý 4 byte mỗi bước và lưu vào state tạm thời. Chỉ duy nhất bước cuối cùng sẽ tổng hợp 4 state đã được sinh từ 4 luồng thành một state duy nhất. Lợi thế đáng kể của việc làm này đó chính là trình tạo mã có rất nhiều cơ hội để sắp xếp lại các opcodes để phòng tránh độ trễ.
Dưới đây là implementation của xxHash bản 32-bit đọc 16 byte mỗi lần. Đây là code đã được đơn giản hóa nhưng vẫn giữ được nguyên lý chung. Để biết thêm chi tiết hơn các bạn có thể xem tại đây.
Cùng thử chạy demo. Ở đây tôi sử dụng những thư viện có sẵn của Python:
Kết quả chạy:
Locality Sensitive Hashing (LSH)
Bài toán “tìm hàng xóm gần nhất” (nearest neighbours) rất phổ biến khi áp dụng cho các tập dữ liệu lớn. Một số ứng dụng hay gặp đó là tìm bản sao hay các tài liệu giống nhau, tìm kiếm audio/video. Cách thông thường ta hay nghĩ đến đó là sử dụng kỹ thuật vét cạn (brute force) để kiểm tra tất cả các tổ hợp có thể để lấy được chính xác cặp hàng xóm gần nhau nhất. Tuy nhiên, cách làm đó rất khó scale cho tập dữ liệu lớn. Thế nên, các thuật toán xấp xỉ được đề cử cho vấn đề trên. Các thuật toán xấp xỉ sẽ không cho bạn câu trả lời chính xác nhưng chúng cung cấp độ xấp xỉ tốt với tốc độ nhanh và dễ scale.
Localilty Sensity Hashing (LSH) là một trong những thuật toán đó. Ý tưởng của LSH là sử dụng một hàm băm (có một họ các hàng băm cho LSH gọi là LSH families) để hash các điểm dữ liệu vào từng bucket sao cho các điểm dữ liệu gần nhau sẽ có xác suất cao rơi vào cùng một bucket, ngược lại chúng sẽ bị băm vào hai bucket khác nhau. Khi truy vấn, ta chỉ cấn tính mã băm tương ứng của dữ liệu đầu vào và trả về tất cả các điểm dữ liệu lưu trong bucket tương ứng với mã băm đó. Vì LSH mang tính chất xấp xỉ và phải cung cấp tốc độ thực thi cao nên các hàm băm sử dụng trong họ LSH thuộc các hàm băm phi mật mã.
LSH đã trở thành một kỹ thuật đa dụng để áp dụng vào những vấn đề như:
- Tìm trùng lặp gần nhất: LSH được dùng phổ biến cho việc phát hiện bản sao trong số lượng lớn các tài liệu, trang web và các tệp.
- Nghiên cứu bộ gen: các nhà sinh học thường sử dụng LSH để xác định các biểu hiện gen tương tự trong cơ sở dữ liệu bộ gen.
- Tìm kiếm hình ảnh quy mô lớn: Google sử dụng LSH với PageRank để xây dựng công nghệ tìm kiếm hình ảnh của họ là VisualRank
- Vân tay Audio/Video: Trong công nghệ truyền thông, LSH được sử dụng làm công nghệ vân tay cho các dữ liệu dạng Audio/Video.
Hãy cùng tìm hiểu thuật toán đằng sau LSH.
Ở bài viết này tôi sẽ lấy ví dụ về bài toán “tìm hai văn bản gần nhau nhất” để minh họa cách hoạt động của LSH. Giả sử ta có ba văn bản như sau:
A: "We are not alone"
B: "We are so close"
C: "Those are good old times"Để phát hiện hai câu trên là trùng nhau hay không, dùng công thức tính khoảng cách giữa các string — Jaccard Index là một cách đơn giản và hiệu quả. Công thức tóm gọn như sau:
Để áp dụng công thức trên dễ dàng, ta sẽ chia hai câu trên thành từng từ. Minh họa Jaccard Index cho hai câu A và B như sau:
Ta thấy số lượng từ giao nhau là 2 và tổng số lượng từ là 6 nên Jaccard Index sẽ có giá trị 2/6 = 0.333.
Mọi việc tưởng như thật đơn giản nhưng cách làm trên lại không dễ scale: số lượng các phép so sánh là 0.5 * n(n -1) nên độ phức tạp thời gian sẽ là O(n²). Ta có thể biểu diễn lại hai câu trên dưới dạng ma trận Boolean để thuận tiện cho việc so sánh. Ta xây dựng một tập tất cả các từ riêng biệt tổng hợp từ hai câu, nếu một từ nằm trong một câu thì ta đánh dấu là 1, ngược lại là 0:
Đến đây vẫn chưa tối ưu vì lưu trữ một ma trận như vậy rất tốn bộ nhớ. Có một cách để giải quyết vấn đề này đó chính là dùng hàm băm. Đây cũng là phần quan trọng nhất trong bài viết về LSH. Có nhiều hàm băm cho ta lựa chọn nhưng hàm băm thích hợp cho Jaccard Index đó chính là MinHashing.
Các bước quan trọng trong quá trình này bao gồm:
Bước 1: Hoán vị ngẫu nhiên index dòng của ma trận Boolean ta đã xây dựng:
Bước 2: Hàm hash sử dụng trong MinHashing là: ở mỗi cột tương ứng với các văn bản, duyệt đến khi ta tìm được một ô có giá trị 1 mà tại đó đối chiếu qua cột index (đã được hoán vị ngẫu nhiên) có giá trị nhỏ nhất. Giá trị hash chính là giá trị của index đó.
Như hình trên ta hash ra được một dòng trong ma trận chữ ký là [2, 1, 3]
Làm lại các bước trên nhiều lần với mỗi lần cột index được hoán vị ngẫu nhiên ta được một ma trận chữ ký đầy đủ hơn:
Ma trận chữ ký hash ra được sẽ là:
Đến đây ta đã có thể tính được độ giống nhau dựa trên ma trận chữ ký: Sự giống nhau giữa các chữ ký là tỉ lệ mà số hàm min-hash (các hàng) có cùng giá trị với nhau. Ví dụ với ma trận chữ ký ở trên, sự giống nhau giữa A và B là 2/3 vì chúng có cột 1 và 3 giống nhau.
Ta cùng thử tính độ giống nhau giữa các cột còn lại và so sánh với kết quả của Jaccard Index:
Ta thây có sự khác biệt gía trị giữa hai loại phép tính vì độ dài ma trận chữ ký ở đây là 3 — khá ngắn. Nếu ta tăng độ dài đó lên thì độ giống nhau sẽ khít hơn nữa.
Consistent Hashing — Hàm băm ổn định
Ta có một tập nhiều cặp key-value và N server để lưu trữ các key-value này. Ta cần tìm cách để phân bố các cặp key-value này trên các server để có thể tìm lại được vị trí của chúng dễ dàng.
Đơn giản thôi, ta sẽ băm key và dùng phép mod N (N là số lượng các server) để tìm ra server cần lưu. server = hash(key) mod N. Kết quả sẽ là chỉ số của server ta sẽ lưu cặp key-value này.
Ví dụ: Ta có 3 server A, B, C và một vài key với giá trị hash của nó:
Với cách thức trên các key sẽ được phân bố như sau:
Khi ta muốn lấy value của key John. Giá trị hash mod 3 của John là 2, vì vậy ta sẽ tìm đến server C
Vấn đề Rehashing
Cách trên đơn giản, trực quan, và có vẻ hoạt động ổn. Nhưng nếu ta thay đổi số lượng server thì sao? Ví dụ như khi một server bị crash hoặc khi ta muốn thêm vào một server mới? Lúc này ta phải sắp xếp lại phần lớn các key vì số lượng server đã thay đổi dẫn đến hash(key) mod N thay đổi. Đây gọi là vấn đề rehashing.
Từ ví dụ trên, nếu C bị crash, lúc này vị trí các key sẽ thay đổi như sau:
Ta thấy rằng với ví dụ này, không chỉ các key thuộc server C thay đổi mà tất cả các key đều bị thay đổi,
Bài toán lúc này là làm sao để số lượng cặp key-value phải di chuyển là nhỏ nhất khi ta tăng hoặc giảm số lượng server.
Ta sẽ sử dụng hàm băm ổn định — consistent hashing
Hàm băm ổn định
Ta sẽ sử dụng một vòng tròn, mỗi điểm trên vòng tròn này được đánh số từ 0,1,2,...,MAX_INT. Lúc này ta tính giá trị hash(key), và tính được vị trí của key trên vòng tròn này.
Lúc này ta sẽ đặt các server lên vòng tròn này, ví dụ ta có thể hash IP của server để tìm ra vị trí sẽ đặt các server.
Lúc này với mỗi key sẽ có 2 trường hợp xảy ra:
- Vị trí của key trùng với 1 trong 3 server
- Vị trí của key khác với vị trí của cả 3 server
Khi vị trí của key trùng với một server: Key và value của nó sẽ thuộc server này.
Trường hợp còn lại: ta thực hiện một thao tác tìm kiếm server sẽ lưu trữ value này bằng cách tìm server gần nhất theo chiều kim đồng hồ.
Trong trường hợp trên:
Nhìn về phương diện lập trình, ta sẽ lưu giá trị của server vào một sorted list. Với mỗi key, ta sử dụng list này tìm giá trị bằng hoặc lớn hơn mà nhỏ nhất so với hash(key). Nếu không tìm thấy, ta lấy giá trị đầu tiên.
Để đảm bảo các key được phân bố đều trên các server, ta có thể đặt nhiều vị trí cho một server. Thay vì 3 điểm A, B, C; ta có thể đặt A0 .. A9, B0 .. B9, C0 .. C9, tất cả xen kẽ dọc theo vòng tròn.
Vậy điểm mạnh của cách tiếp cận này là gì?
Giả sử C bị crash. Để xử lí tình huống này, đàu tiên ta sẽ xóa các điểm C0 .. C9 trên vòng tròn. Điều này dẫn đến chỉ các key thuộc về server C bị thay đổi, các key này sẽ được chuyển vào server A hoặc B. Các key ban đầu thuộc về server A và B sẽ không bị thay đổi. Tuyệt!
Tương tự, giả sử ta thêm một server D vào hệ thống server A và B ban nãy (giả sử thay thế cho C). Ta thêm D0 .. D9 vào vòng tròn. Kết quả là chỉ khoảng 1/3 các key thuộc server A và B bị thay đổi, phần còn lại vẫn giữ nguyên.
Đây là cách hàm băm ổn định giải quyết vấn đề rehashing.
Lời kết
Tùy vào từng tình huống nhất định ta sẽ sử dựng các hàm băm phù hợp. Giả sử nếu tình huống yêu cầu tính bảo mật cao ví dụ trong việc truyền dữ liệu, ta nên cân nhắc sử dụng các hàm băm mật mã. Ngược lại nếu không quá quan trọng về vấn đề bảo mật như việc xử lí và truy hồi dữ liệu, hàm băm phi mật mã sẽ phù hợp hơn vì các hàm băm này cung cấp tốc độ thực thi tốt hơn mà vẫn giữ một độ phân phối tốt.
Bài viết khá dài, hy vọng qua bài viết có thể giúp bạn có cái nhìn tổng quan hơn về hàm băm, hẹn gặp lại ở các bài viết tiếp theo!
Bài viết được đồng hành bởi Trân.
