Giải thích cơ bản đơn giản về Bảng băm phân tán (DHT)

Question

Có thể giải thích về cách DHT hoạt động không?

Không có gì quá nặng, chỉ là vấn đề cơ bản.

Answer 1

Ok, họ về cơ bản là một ý tưởng khá đơn giản. Một DHT cung cấp cho bạn một giao diện giống như từ điển, nhưng các nút được phân phối trên mạng. Bí quyết với DHT là nút được lưu trữ một khóa cụ thể được tìm thấy bằng cách băm khóa đó, do đó, hiệu lực các nhóm bảng băm của bạn hiện là các nút độc lập trong mạng.

Điều này mang lại rất nhiều lỗi và độ tin cậy, và có thể một số lợi ích hiệu suất, nhưng nó cũng ném lên rất nhiều đau đầu. Ví dụ, điều gì sẽ xảy ra khi một nút rời khỏi mạng, bằng cách thất bại hay không? Và làm thế nào để bạn phân phối lại các phím khi một nút gia nhập sao cho tải được cân bằng. Hãy nghĩ về nó, làm thế nào để bạn phân phối đồng đều các phím dù sao? Và khi một nút tham gia, làm thế nào để bạn tránh phục hồi tất cả mọi thứ? (Hãy nhớ rằng bạn phải làm điều này trong một bảng băm bình thường nếu bạn tăng số lượng nhóm).

Một ví dụ DHT giải quyết một số vấn đề này là một vòng logic của các nút n, mỗi nút chịu trách nhiệm về 1/n của không gian phím. Khi bạn thêm một nút vào mạng, nó sẽ tìm một vị trí trên vòng để đặt giữa hai nút khác và chịu trách nhiệm về một số khóa trong các nút anh chị em của nó. Vẻ đẹp của phương pháp này là không ai trong số các nút khác trong vòng bị ảnh hưởng; chỉ có hai nút anh chị em phải phân phối lại các phím.

Ví dụ: giả sử trong nút ba nút, nút đầu tiên có các phím 0-10, từ thứ 2 đến thứ 2 và thứ 2 là 21-30. Nếu nút thứ tư xuất hiện và chèn chính nó giữa các nút 3 và 0 (nhớ, chúng nằm trong một vòng), nó có thể chịu trách nhiệm cho một nửa không gian phím của 3, vì vậy bây giờ nó giao dịch với 26-30 và nút 3 giao dịch với 21 -25.

Có rất nhiều cấu trúc lớp phủ khác như điều này sử dụng định tuyến dựa trên nội dung để tìm nút bên phải để lưu khóa. Định vị một khóa trong vòng yêu cầu tìm vòng quanh một nút tại một thời điểm (trừ khi bạn giữ một bảng tra cứu cục bộ, có vấn đề trong một DHT của hàng nghìn nút), đó là định tuyến O (n) -hop. Các cấu trúc khác - bao gồm các vòng tăng cường - đảm bảo định tuyến O (log n) -hop, và một số yêu cầu định tuyến O (1) -hop với chi phí bảo trì cao hơn.

Đọc trang wikipedia và nếu bạn thực sự muốn biết một chút sâu, hãy xem coursepage tại Harvard có danh sách đọc khá toàn diện này.

Answer 2

DHT cung cấp cùng một loại giao diện cho người dùng dưới dạng thẻ bắt buộc bình thường (tra cứu giá trị theo khóa), nhưng dữ liệu được phân phối trên số lượng nút được kết nối tùy ý. Wikipedia có một giới thiệu cơ bản tốt mà tôi sẽ chủ yếu được regurgitating nếu tôi viết thêm -

http://en.wikipedia.org/wiki/Distributed_hash_table

Answer 3

Check-out this Wikipedia article Hoặc này powerpoint slide

Answer 4

xem Dynamo của Amazon, nó giải thích việc triển khai DHT đơn giản nhưng mới lạ dựa trên vòng tròn băm phù hợp.

Answer 5

Tôi muốn thêm vào câu trả lời hữu ích của HenryR vì tôi chỉ có một cái nhìn sâu sắc về băm nhất quán. Một tra cứu hash bình thường/ngây thơ là một hàm của hai biến, một trong số đó là số lượng các nhóm. Vẻ đẹp của băm nhất quán là chúng ta loại bỏ số lượng các thùng "n", từ phương trình.

Trong băm ngây thơ, biến đầu tiên là khóa của đối tượng được lưu trữ trong bảng. Chúng tôi sẽ gọi khóa "x".Biến thứ hai là số nhóm, "n". Vì vậy, để xác định xem thùng/máy nào được lưu trữ trong đối tượng, bạn phải tính toán: hash (x) mod (n). Do đó, khi bạn thay đổi số lượng nhóm, bạn cũng thay đổi địa chỉ mà hầu hết mọi đối tượng được lưu trữ.

So sánh điều này với băm nhất quán. Hãy định nghĩa "R" là phạm vi của hàm băm. R chỉ là một số hằng số. Trong băm nhất quán, địa chỉ của một đối tượng được đặt tại băm (x)/R. Vì tra cứu của chúng tôi không còn là chức năng của số nhóm, nên chúng tôi sẽ kết thúc với ít bản đồ hơn khi chúng tôi thay đổi số lượng nhóm.

http://michaelnielsen.org/blog/consistent-hashing/