Bảng băm phân tán

Bảng băm phân tán (tiếng Anh: "distributed hash table", viết tắt DHT) là một lớp các hệ thống phân tán không tập trung, cung cấp một dịch vụ tra cứu tương tự như một bảng băm: các cặp ("khóa", "giá trị") được lưu trữ trong DHT, và bất kỳ nút mạng tham gia nào cũng có thể lấy được giá trị liên kết với một khóa cho trước một cách hiệu quả. Nhiệm vụ lưu trữ ánh xạ từ khóa tới giá trị được phân tán giữa các nút, bằng cách đó sẽ giảm bớt lỗi nếu có thay đổi trong một tập hợp các nút tham gia. Điều này cho phép sử dụng DHT cho một số lượng cực lớn các nút mạng và xử lý việc vào, ra, và lỗi các nút mạng một cách liên tục.
DHT tạo nên cơ sở hạ tầng cho việc xây dựng các dịch vụ phức tạp hơn, chẳng hạn như các hệ thống file phân tán, chia sẻ file trong mạng đồng đẳng, hệ thống phân phối nội dung ("content distribution"), web cache có tính hợp tác, multicast, anycast, dịch vụ tên miền và instant messaging. Các mạng phân tán nổi tiếng sử dụng DHT bao gồm máy theo dõi phân tán của BitTorrent, mạng eDonkey, mạng bot Storm, YaCy, và Coral Content Distribution Network.
Tính chất.
DHT nhấn mạnh các tính chất sau:
Một kĩ thuật quan trọng để đạt được những mục tiêu này là mỗi nút chỉ nên cộng tác với một vài nút khác trong hệ thống – thông dụng nhất là formula_1 của số nút tham gia formula_2 (xem bên dưới) – để mỗi thay đổi đối với việc ra/vào hệ thống chỉ đòi hỏi lượng nhỏ công việc xử lý tình huống.
Một số thiết kế DHT hướng đến tính an toàn trước các thành viên ác ý và cho phép các thành viên giữ tình trạng ẩn danh, tuy điều này ít thông dụng hơn tại nhiều hệ thống đồng đẳng khác (đặc biệt là các hệ thống chia sẻ file); xem anonymous P2P.
Cuối cùng, DHT phải xử lý được các vấn đề cố hữu của các hệ thống phân tán, chẳng hạn như load balancing, data integrity, và hiệu năng (cụ thể là đảm bảo rằng các thao tác như định tuyến và lưu trữ hoặc lấy dữ liệu đòi hỏi thời gian thi hành ngắn).
Cấu trúc.
Cấu trúc của một DHT có thể được phân thành một số thành phần chính. 
Một khi các thành phần này được lắp ráp vào đúng chỗ, một tình huống điển hình của việc sử dụng DHT cho việc lưu trữ và lấy dữ liệu như sau. Giả sử không gian khóa là một tập các xâu 160-bit. Để lưu trữ một file với formula_3 và formula_4 cho trước vào DHT, thực hiện băm SHA1 cho formula_3, tạo một khóa formula_6 kích thước 160-bit, và thông điệp formula_7 được gửi tới một nút bất kì tham gia DHT. Thông điệp này được gửi chuyển tiếp từ nút này tới nút khác qua mạng overlay cho đến khi nó đến được nút duy nhất chịu trách nhiệm cho khóa formula_6 theo như quy hoạch không gian khóa đã quy định, cặp formula_9 sau đó được lưu trữ tại nút này. Từ đó, một khách hàng bất kì có thể lấy nội dung của file bằng cách lại thực hiện hàm băm cho formula_3 để lấy khóa formula_6 và yêu cầu một nút DHT bất kì tìm dữ liệu được liên hệ với khóa formula_6 bằng một thông điệp formula_13. Thông điệp này sẽ lại được định tuyến theo mạng overlay để tới được nút chịu trách nhiệm cho khóa formula_6, nút này sẽ trả lời bằng formula_4 được lưu trữ tại đó.
Các thành phần phân hoạch không gian khóa và mạng overlay được mô tả ở dưới đây theo các nguyên lý chính thông dụng cho hầu hết các DHT; chi tiết còn tùy theo các thiết kế khác nhau.
Phân hoạch không gian khóa.
Đa số các DHT dùng một dạng hàm băm ổn định ("consistent hashing") để ánh xạ từ khóa tới các nút. Kĩ thuât này sử dụng một hàm formula_16 định nghĩa một khái niệm trừu tượng là "khoảng cách" từ khóa formula_17 tới khóa formula_18, khái niệm này không liên quan đến khoảng cách địa lý hay độ trễ mạng. Mỗi nút được gán một khóa đơn, gọi là định danh của nút (ID). Một nút với ID formula_19 sở hữu tất cả các khóa mà formula_19 là ID gần nhất theo hàm khoảng cách formula_21.
Ví dụ. DHT Chord coi các khóa như là các điểm trên một đường tròn, còn formula_16 là độ dài cung tròn nối từ formula_17 tới formula_18 theo chiều kim đồng hồ. Không gian khóa tròn này được phân thành các cung liền nhau, trong đó các điểm mút là định danh của các nút. Nếu formula_25 và formula_26 là hai ID liên tiếp, thì nút với ID formula_26 sở hữu tất cả các khóa nằm giữa formula_25 và formula_26.
Consistent hashing có tính chất quan trọng rằng việc xóa hay thêm một nút chỉ làm thay đổi tập khóa thuộc sở hữu các nút có ID liền đó, và không ảnh hưởng đến tất cả các nút khác. Tính chất này trái với bảng băm truyền thống mà trong đó việc thêm hoặc bớt một bucket dẫn đến việc phải ánh xạ lại gần như toàn bộ không gian khóa. Do mỗi thay đổi về sở hữu thường tương ứng với một loạt các di chuyển tốn kém về băng thông khi các đối tượng được lưu tại nút này chuyển sang nút khác, việc tối thiểu hóa các hoạt động tái tổ chức như vậy là cần thiết cho việc hỗ trợ có hiệu quả tần suất cao của hiện tượng nút đến và đi.
Mạng nằm ngang.
Mỗi nút lưu trữ một tập các liên kết tới các nút khác (danh sách "hàng xóm" hoặc bảng định tuyến). Các liên kết này tạo nên mạng nằm ngang. Một nút lựa chọn danh sách hàng xóm của mình theo một cấu trúc nhất định, được gọi là photo mạng.
Tất cả các tô pô DHT đều có một biến thể nào đó của tính chất quan trọng nhất: với khóa formula_6 bất kì, một nút hoặc có ID sở hữu formula_6 hoặc có liên kết tới một nút ở "gần" formula_6 hơn, theo khái niệm khoảng cách không gian khóa được định nghĩa ở trên. Khi đó, có thể dễ dàng định tuyến một thông điệp tới chủ sở hữu của một khóa formula_6 bất kì bằng thuật toán ăn tham (thuật toán không nhất thiết tối ưu toàn cục) sau đây: tại mỗi bước, gửi chuyển tiếp thông điệp tới hàng xóm có ID gần formula_6 nhất. Khi không có hàng xóm nào như vậy là khi ta đã đến được nút gần nhất—chủ sở hữu của khóa formula_6 theo định nghĩa ở trên. Kiểu định tuyến này đôi khi được gọi là định tuyến theo chìa khóa ("key based routing").
Vượt ra ngoài tính đúng đắn cơ bản của việc định tuyến, còn có hai ràng buộc quan trọng về photo:
Tất nhiên, để có các tuyến đường ngắn thì cần có bậc tối đa cao. Dưới đây là một số lựa chọn thông dụng cho bậc tối đa và độ dài đường, trong đó formula_2 là số nút tham gia DHT:
Lựa chọn thứ ba là thông dụng nhất, tuy không tối ưu lắm về tương quan giữa bậc và độ dài đường, vì các tô pô như vật thường cho phép lựa chọn hàng xóm một cách mềm dẻo hơn. Nhiều DHT sử dụng sự mềm dẻo đó để chọn hàng xóm ở gần theo nghĩa độ trễ của mạng vật lý bên dưới.
Các thuật toán cho mạng overlay.
Bên cạnh các thuật toán định tuyến, có nhiều thuật toán khai thác cấu trúc của mạng overlay cho việc gửi thông điệp tới tất các nút hoặc một tập con các nút của một DHT. Các thuật toán này được sử dụng trong các ứng dụng để gửi lan truyền multicast, range queries, hoặc để thu thập thống kê.