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à $\Theta (\log n)$ của số nút tham gia $n$ (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 ý^[1] 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.^[2]^[3]

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

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

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 $k$ bất kì, một nút hoặc có ID sở hữu $k$ hoặc có liên kết tới một nút ở gần $k$ 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 $k$ 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 $k$ 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 $k$ 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 đó $n$ là số nút tham gia DHT:

Bậc $O(1)$ , độ dài đường $O(n)$
Bậc $O(\log n)$ , độ dài đường $O(\log n/\log \log n)$
Bậc $O(\log n)$ , độ dài đường $O(\log n)$
Bậc $O({\sqrt {n}})$ , độ dài đường $O(1)$

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.^[4] 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 [1] Lưu trữ 2008-12-10 tại Wayback Machine
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

^ Guido Urdaneta, Guillaume Pierre and Maarten van Steen. A Survey of DHT Security Techniques. ACM Computing Surveys, 2009.
^ 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 Lưu trữ 2004-09-10 tại Wayback Machine. Ph. D. Thesis (Stanford University), tháng 8 năm 2004.
^ Ali Ghodsi. Distributed k-ary System: Algorithms for Distributed Hash Tables. KTH-Royal Institute of Technology, 2006.

Liên kết ngoài

Distributed Hash Tables, Part 1 by Brandon Wiley.
Distributed Hash Tables links Lưu trữ 2009-02-26 tại Wayback Machine 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 Lưu trữ 2008-01-18 tại Wayback Machine supports a DHT with optional redundancy for high availability
Tangosol Coherence Lưu trữ 2013-12-03 tại Wayback Machine 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.

[1] Guido Urdaneta, Guillaume Pierre and Maarten van Steen. A Survey of DHT Security Techniques. ACM Computing Surveys, 2009.

[2] Moni Naor and Udi Wieder. Novel Architectures for P2P Applications: the Continuous-Discrete Approach. Proc. SPAA, 2003.

[3] Gurmeet Singh Manku. Dipsea: A Modular Distributed Hash Table Lưu trữ 2004-09-10 tại Wayback Machine. Ph. D. Thesis (Stanford University), tháng 8 năm 2004.

[4] Ali Ghodsi. Distributed k-ary System: Algorithms for Distributed Hash Tables. KTH-Royal Institute of Technology, 2006.

[1]

[2]

[3]

[4]