Kademlia

Bách khoa toàn thư mở Wikipedia
Buớc tưới chuyển hướng Bước tới tìm kiếm

Kademlia (DHT) là bảng băm phân tán cho các mạng máy tính ngang hàng phi tập trung được thiết kế bởi Petar Maymounkov và David Mazières vào năm 2002. Nó chỉ định cấu trúc của mạng và trao đổi thông tin thông qua tra cứu nút. Các nút Kademlia giao tiếp với nhau bằng UDP. Một mạng ảo hoặc lớp phủ được hình thành bởi các nút tham gia. Mỗi nút được xác định bởi một số hoặc ID nút. ID nút không chỉ phục vụ như nhận dạng, mà thuật toán Kademlia sử dụng ID nút để định vị các giá trị (thường là băm tập tin hoặc từ khóa). Trong thực tế, ID nút cung cấp một bản đồ trực tiếp đến băm tập tin và nút đó lưu trữ thông tin về nơi lấy tệp hoặc tài nguyên.

Khi tìm kiếm một số giá trị, thuật toán cần biết khóa liên quan và khám phá mạng theo nhiều bước. Mỗi bước sẽ tìm thấy các nút gần với khóa hơn cho đến khi nút được liên hệ trả về giá trị hoặc không tìm thấy nút nào gần hơn. Điều này rất hiệu quả: Giống như nhiều DHT khác, Kademlia chỉ liên lạc với các nút O (\ log (n)) trong quá trình tìm kiếm trong tổng số n nút trong hệ thống.

Những lợi thế hơn nữa được tìm thấy đặc biệt trong cấu trúc phi tập trung, giúp tăng khả năng chống lại cuộc tấn công từ chối dịch vụ (DDoS). Ngay cả khi toàn bộ các nút bị ngập, điều này sẽ ảnh hưởng hạn chế đến tính khả dụng của mạng, vì mạng sẽ tự phục hồi bằng cách đan mạng xung quanh các "lỗ hổng" này.

Chi tiết

Các mạng chia sẻ tệp ngang hàng thế hệ đầu tiên, chẳng hạn như Napster, đã dựa vào cơ sở dữ liệu trung tâm để phối hợp tra cứu trên mạng. Các mạng ngang hàng thế hệ thứ hai, chẳng hạn như Gnutella, đã sử dụng ngập lụt để định vị các tệp, tìm kiếm mọi nút trên mạng. Mạng ngang hàng thế hệ thứ ba sử dụng bảng băm phân tán để tra cứu các tệp trong mạng. Bảng băm phân tán lưu trữ các vị trí tài nguyên trên toàn mạng. Một tiêu chí chính cho các giao thức này là nhanh chóng xác định vị trí các nút mong muốn.

Kademlia sử dụng phép tính "khoảng cách" giữa hai nút. Khoảng cách này được tính là độc quyền hoặc (XOR) của hai ID nút, lấy kết quả làm số nguyên. Các khóa và ID nút có cùng định dạng và độ dài, do đó khoảng cách có thể được tính giữa chúng theo cùng một cách chính xác. ID nút thường là một số ngẫu nhiên lớn được chọn với mục tiêu là duy nhất cho một nút cụ thể. Có thể và có thể xảy ra rằng các nút được phân tách theo địa lý rộng rãi từ Đức và Úc, ví dụ, có thể là "hàng xóm" nếu họ đã chọn ID nút ngẫu nhiên tương tự.

Độc quyền hoặc được chọn vì nó hoạt động như một hàm khoảng cách giữa tất cả các ID nút. Đặc biệt:

khoảng cách giữa một nút và chính nó bằng không nó đối xứng: "khoảng cách" được tính từ A đến B và từ B đến A là như nhau nó theo bất đẳng thức tam giác: cho A, B và C là các đỉnh (điểm) của một tam giác, sau đó khoảng cách từ A đến B ngắn hơn (hoặc bằng) tổng khoảng cách từ A đến C và khoảng cách từ C đến B. Ba điều kiện này đủ để đảm bảo rằng độc quyền hoặc nắm bắt tất cả các tính năng quan trọng, thiết yếu của hàm khoảng cách "thực", trong khi rẻ và đơn giản để tính toán. Do phân phối thống kê này, Kademlia chọn các nút được kết nối dài để được lưu trữ trong các thùng k. Điều này làm tăng số lượng các nút hợp lệ đã biết tại một thời điểm nào đó trong tương lai và cung cấp cho một mạng ổn định hơn.

Khi một k-xô đầy và một nút mới được phát hiện cho k-xô đó, nút ít thấy gần đây nhất trong k-xô là PINGed. Nếu nút được tìm thấy vẫn còn sống, nút mới được đặt trong danh sách phụ, bộ đệm thay thế. Bộ đệm thay thế chỉ được sử dụng nếu một nút trong k-xô dừng đáp ứng. Nói cách khác: các nút mới chỉ được sử dụng khi các nút cũ biến mất.

Các đặc trưng mạng

Một mạng Kademlia được đặc trưng bởi ba hằng số, chúng ta gọi là alpha, B và k. Đầu tiên và cuối cùng là các điều khoản tiêu chuẩn. Thứ hai được giới thiệu vì một số triển khai Kademlia sử dụng độ dài khóa khác nhau.

  • alpha là một số nhỏ biểu thị mức độ song song trong các cuộc gọi mạng, thường là 3
  • B là kích thước tính theo bit của các khóa được sử dụng để xác định các nút và lưu trữ và truy xuất dữ liệu; trong Kademlia cơ bản, đây là 160, chiều dài của một bản tóm tắt SHA1 (hàm băm)
  • k là số lượng liên lạc tối đa được lưu trữ trong một thùng; bình thường là 20