Cách chia dữ liệu ra nhiều máy đơn giản nhất là lấy mã băm của khoá rồi chia lấy dư cho số máy — khoá có số dư 0 về máy 0, số dư 1 về máy 1, cứ thế. Cách này hoạt động hoàn hảo, rất nhanh, và cực kỳ dễ hiểu. Cho tới đúng cái ngày bạn cần thêm máy thứ tư vào một cụm ba máy.
Khi số máy đổi từ 3 thành 4, phép chia dư đổi theo, và gần như mọi khoá đều được tính ra một máy khác. Cả cụm rơi vào một cơn bão chuyển dữ liệu: hàng loạt khoá phải di chuyển qua mạng sang máy mới của chúng, trong khi vẫn phải phục vụ người dùng. Với một hệ thống co giãn — thêm bớt máy là chuyện thường ngày — đây là một khiếm khuyết chí mạng. Consistent hashing sinh ra để chữa đúng bệnh này.
Xếp mọi thứ lên một vòng tròn
Ý tưởng là băm cả khoá lẫn máy chủ vào cùng một không gian, hình dung như một vòng tròn. Mỗi khoá thuộc về máy chủ đầu tiên nó gặp khi đi theo chiều kim đồng hồ từ vị trí của mình. Thế thôi — nhưng chính cách sắp xếp này thay đổi hoàn toàn hành vi khi thêm bớt máy.
Thêm một máy chủ mới giờ chỉ ảnh hưởng đúng đoạn cung nằm ngay trước nó trên vòng: những khoá trong đoạn đó, vốn trước kia đi tiếp tới máy kế, nay dừng lại ở máy mới. Trung bình, đó là khoảng 1/n tổng dữ liệu phải di chuyển — thay vì gần như tất cả. Bỏ một máy cũng đối xứng như vậy: chỉ phần dữ liệu của riêng máy đó trôi sang máy kế tiếp trên vòng, mọi khoá khác đứng yên. Cơn bão chuyển dữ liệu biến thành một cơn gió nhẹ cục bộ.
Vấn đề phân bố lệch và cách chữa
Sơ đồ đẹp đẽ ở trên giấu một vấn đề thực tế: với số máy ít, các điểm rơi của chúng trên vòng không đều nhau. Băm là ngẫu nhiên, nên hoàn toàn có thể có một máy ôm một cung dài gấp mấy lần máy khác — và thế là nó nhận nhiều dữ liệu, nhiều tải hơn hẳn, trong khi máy khác ngồi rỗi. Phân bố lệch này làm hỏng chính lợi ích mà ta muốn.
Cách chữa chuẩn mực là nút ảo: thay vì băm mỗi máy vật lý vào vòng đúng một lần, ta băm nó vào hàng trăm vị trí khác nhau. Giờ mỗi máy ôm hàng trăm cung nhỏ rải khắp vòng thay vì một cung lớn duy nhất, và theo luật số lớn, tổng chiều dài các cung của mỗi máy hội tụ về gần bằng nhau — phân bố tải trở nên đều. Nút ảo còn mang lại một lợi ích tiện lợi nữa: một máy mạnh có thể được cấp nhiều vị trí hơn máy yếu, tức là nhận phần tải lớn hơn một cách có chủ ý, cho phép chia việc theo đúng năng lực thật của từng máy thay vì cào bằng.
Nơi bạn đã gặp nó
Consistent hashing là một trong những viên gạch nền âm thầm của hệ thống phân tán, có mặt ở khắp nơi: các bộ nhớ đệm phân tán, các cơ sở dữ liệu khoá–giá trị chia mảnh trên nhiều máy, các mạng phân phối nội dung khi chọn máy chủ biên gần người dùng, và cả trong cân bằng tải khi cần đảm bảo cùng một người dùng luôn được đưa về cùng một máy để tận dụng trạng thái đã lưu sẵn ở đó.
Nhưng cũng nên nói thẳng một điều để tránh dùng thừa: nếu hệ thống của bạn chỉ có một máy, và nhiều khả năng sẽ mãi chỉ một máy, thì đừng dựng thứ này. Consistent hashing giải bài toán co giãn — thêm bớt máy mà không xáo trộn toàn bộ — và nó chỉ đáng công khi bài toán co giãn đó là thật. Dựng nó cho một hệ thống không bao giờ mở rộng chỉ là thêm độ phức tạp để giải quyết một vấn đề bạn không có.
Thảo luận