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:

 Phi tập trung (decentralization): tập thể các nút mạng tạo nên hệ thống mà không cần một sự điều phối từ trung tâm.
 Ổn định: hệ thống hoạt động hiệu quả ngay cả khi trong đó có hàng nghìn hay hàng triệu nút.
 Chịu lỗi (fault tolerance): hệ thống đáng tin cậy (theo một nghĩa nào đó) ngay cả khi các nút mạng liên tục ra vào mạng và gặp sự cố.

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à  của số nút tham gia  (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 ýGuido Urdaneta, Guillaume Pierre and Maarten van Steen. A Survey of DHT Security Techniques. ACM Computing Surveys, 2009. 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.Moni Naor and Udi Wieder. Novel Architectures for P2P Applications: the Continuous-Discrete Approach. Proc. SPAA, 2003.Gurmeet Singh Manku. Dipsea: A Modular Distributed Hash Table . Ph. D. Thesis (Stanford University), tháng 8 năm 2004. 
 Nền tảng là một không gian khóa (keyspace) trừu tượng, chẳng hạn tập các xâu kích thước 160-bit.
 Một phương án phân hoạch không gian khóa (keyspace partitioning) chia tách sở hữu không gian khóa này giữa các nút thành viên.
 Một mạng overlay kết nối các nút, cho phép chúng tìm nút chủ của một khóa nào đó trong không gian khóa.

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  và  cho trước vào DHT, thực hiện băm SHA1 cho , tạo một khóa  kích thước 160-bit, và thông điệp  đượ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  theo như quy hoạch không gian khóa đã quy định, cặp  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  để lấy khóa  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  bằng một thông điệp . 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 , nút này sẽ trả lời bằng  đượ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  định nghĩa một khái niệm trừu tượng là khoảng cách từ khóa  tới khóa , 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  sở hữu tất cả các khóa mà  là ID gần nhất theo hàm khoảng cách .

Ví dụ. DHT Chord coi các khóa như là các điểm trên một đường tròn, còn  là độ dài cung tròn nối từ  tới  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  và  là hai ID liên tiếp, thì nút với ID  sở hữu tất cả các khóa nằm giữa  và .

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  bất kì, một nút hoặc có ID sở hữu  hoặc có liên kết tới một nút ở gần  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  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  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  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:
 đảm bảo giữ độ dài tối đa của một tuyến bất kì ở mức thấp, để các yêu cầu có thể được hoàn thành trong thời gian ngắn;
 đảm bảo số hàng xóm tối đa của mỗi nút (bậc tối đa của nút bất kì) ở mức thấp, để chi phí bảo quản không quá cao.
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 đó  là số nút tham gia DHT:

 Bậc , độ dài đường 
 Bậc , độ dài đường 
 Bậc , độ dài đường 
 Bậc , độ dài đường 

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.Ali Ghodsi. Distributed k-ary System: Algorithms for Distributed Hash Tables. KTH-Royal Institute of Technology, 2006. 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ê.

 Ví dụ 
 Các giao thức và cài đặt DHT 
 CAN (Content Addressable Network)
 Chord
 Kademlia
 Pastry
 P-Grid
 Tapestry

 Các ứng dụng dùng DHT 

 BitTorrent: phân phối file. BitTorrent có thể dùng DHT làm công cụ lần vết phân tán để cho phép các mối liên hệ giữa các khách hàng cùng chia sẻ một file cụ thể nào đó (xem BitTorrent client)
 The Circle: chia sẻ file và chat
 Codeen: Web caching
 Coral Content Distribution Network
 Freenet: mạng ẩn danh chống kiểm duyệt
 Dijjer: mạng phân phối giống như Freenet
 eMule: chia sẻ file
 FAROO: động cơ tìm kiếm web đồng đẳng
 GNUnet: mạng phân phối giống như Freenet, có một cài đặt DHT  
 JXTA: Nền nguồn mở P2P
 LimeWire: Chia sẻ file
 NEOnet: Chia sẻ file
 OneSwarm: Chia sẻ file. Kademlia DHT dùng để lưu các địa chỉ IP được mã hóa.
 Overnet: Chia sẻ file
 Transmission: BitTorrent Client
 µTorrent: BitTorrent client
 Vuze: BitTorrent client đầu tiên cài DHT, khi đó được gọi là Azureus.
 Warez P2P: Chia sẻ file
 YaCy: động cơ tìm kiếm phân tán

 Xem thêm 

 memcached
 Cây băm tiền tố (Prefix hash tree)

 Chú thích 

 Liên kết ngoài 
 Distributed Hash Tables, Part 1 by Brandon Wiley.
 Distributed Hash Tables links  Carles Pairot's Page on DHT and P2P research
 Infinispan, an open source, P2P Java based data grid platform, makes use of DHTs at its core.
 GemStone's GemFire  supports a DHT with optional redundancy for high availability
 Tangosol Coherence  includes a structure similar to a DHT, though all nodes have knowledge of the other participants
 kademlia.scs.cs.nyu.edu Archive.org snapshots of kademlia.scs.cs.nyu.edu
 Open DHT: A publicly accessible distributed hash table (DHT) service.
 Cacheonix uses an approach similar to DHT with added replication for better failure-tolerance
 Hazelcast: P2P and partitioned DHT implementation.

Thể loại:Cấu trúc dữ liệu phân tán
Thể loại:Kiến trúc mạng
Thể loại:Chia sẻ tập tin
Thể loại:Lưu trữ dữ liệu phân tán
Thể loại:Băm