Pastry

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

Pastry cung cấp các khả năng sau đây. Đầu tiên, mỗi nút trong mạng Pastry có một mã định danh ngẫu nhiên, thống nhất (nodeId) duy nhất trong không gian định danh 128 bit tròn. Khi được trình bày với một thông báo và khóa 128 bit, một nút Pastry định tuyến hiệu quả thông điệp đến nút đó với một nútId gần nhất với khóa, trong số tất cả các nút Pastry hiện đang sống. Số bước chuyển tiếp dự kiến ​​trong mạng lớp phủ Pastry là O (log N), trong khi kích thước của bảng định tuyến được duy trì trong mỗi nút Pastry chỉ có kích thước O (log N) (trong đó N là số nút Pastry sống trong mạng lưới lớp phủ). Tại mỗi nút Pastry dọc theo tuyến đường mà một tin nhắn thực hiện, ứng dụng sẽ được thông báo và có thể thực hiện các tính toán dành riêng cho ứng dụng liên quan đến tin nhắn.

Thứ hai, mỗi nút Pastry theo dõi các hàng xóm L ngay lập tức của nó trong không gian của nútId (được gọi là bộ lá) và thông báo cho các ứng dụng của nút đến mới, lỗi nút và phục hồi nút trong bộ lá. Thứ ba, Pastry tính đến địa phương (sự gần gũi) trong Internet cơ bản; nó tìm cách giảm thiểu khoảng cách truyền tin nhắn, theo một số liệu gần đúng vô hướng như độ trễ ping. Pastry hoàn toàn phi tập trung, có thể mở rộng và tự tổ chức; nó tự động thích ứng với sự đến, đi và thất bại của các nút. Các ứng dụng P2p được xây dựng trên Pastry có thể sử dụng các khả năng của nó theo nhiều cách, bao gồm:

  • Ánh xạ các đối tượng ứng dụng vào các nút Pastry: Các đối tượng dành riêng cho ứng dụng được gán các định danh ngẫu nhiên thống nhất (objIds) duy nhất và được ánh xạ tới các nút k, (k> = 1) với nútIds gần nhất với objId. Số k phản ánh mức độ sao chép mong muốn của ứng dụng cho đối tượng.
  • Chèn đối tượng: Các đối tượng dành riêng cho ứng dụng có thể được chèn bằng cách định tuyến tin nhắn Pastry, sử dụng objId làm khóa. Khi thông báo đến một nút có một trong k nút gần nhất với objId, nút đó sẽ sao chép đối tượng trong số các nút k-1 khác với nútIds gần nhất (theo định nghĩa, trong cùng một lá được đặt cho k <= L / 2).
  • Truy cập các đối tượng: Các đối tượng dành riêng cho ứng dụng có thể được tra cứu, liên hệ hoặc truy xuất bằng cách định tuyến một thông báo Pastry, sử dụng objId làm khóa. Theo định nghĩa, thông báo được đảm bảo tiếp cận một nút duy trì một bản sao của đối tượng được yêu cầu trừ khi tất cả các nút k có nodeIds gần nhất với objId đều thất bại.
  • Tính khả dụng và tính bền vững: Các ứng dụng quan tâm đến tính khả dụng và tính bền vững của các đối tượng dành riêng cho ứng dụng duy trì các bất biến sau đây khi các nút tham gia, thất bại và khôi phục: các bản sao đối tượng được duy trì trên các nút k với các nút gần nhất với objId, cho k> rằng Pastry duy trì các bộ lá và thông báo cho các ứng dụng thay đổi trong tư cách thành viên của bộ đơn giản hóa nhiệm vụ duy trì bất biến này.
  • Tính đa dạng: Việc gán nodeIds là ngẫu nhiên và không thể bị kẻ tấn công làm hỏng. Do đó, với xác suất cao, các nút có nútI liền kề rất đa dạng về vị trí địa lý, quyền sở hữu, quyền tài phán, tệp đính kèm mạng, v.v. Do đó, xác suất một tập hợp các nút như vậy là âm mưu hoặc chịu các thất bại tương quan là thấp ngay cả đối với các kích thước đặt khiêm tốn. Điều này giảm thiểu khả năng thất bại đồng thời của tất cả các nút k duy trì một bản sao đối tượng. Tương tự như vậy, các giao thức dựa trên đại biểu có thể được sử dụng để cập nhật và truy vấn an toàn trạng thái của các đối tượng được sao chép, mặc dù có sự hiện diện của một số nút độc hại trong hệ thống.
  • Cân bằng tải: Cả nodeIds và objIds đều được gán ngẫu nhiên và phân phối đồng đều trong không gian định danh Pastry 128 bit. Không yêu cầu bất kỳ sự phối hợp toàn cầu nào, điều này dẫn đến sự cân bằng thứ tự tốt về yêu cầu lưu trữ và tải truy vấn giữa các nút Pastry, cũng như tải mạng trong Internet cơ bản.
  • Bộ nhớ đệm đối tượng: Các ứng dụng có thể lưu trữ các đối tượng trên các nút Pastry gặp phải dọc theo các đường dẫn được thực hiện bằng các thông báo chèn và tra cứu. Các yêu cầu tra cứu tiếp theo có đường dẫn giao nhau được phục vụ bản sao lưu. (Các thuộc tính cục bộ mạng của Pastry làm cho các tin nhắn được định tuyến bằng cùng một khóa từ các nút lân cận sẽ hội tụ sớm, do đó việc tra cứu có khả năng chặn các đối tượng được lưu trong bộ nhớ cache gần đó.) Bộ nhớ đệm phân tán này giảm tải các nút k giữ bản sao chính của một đối tượng và nó giảm thiểu độ trễ của máy khách và lưu lượng truy cập mạng bằng cách lưu động các bản sao lưu gần các máy khách quan tâm.
  • Phổ biến thông tin hiệu quả, có thể mở rộng: Các ứng dụng có thể thực hiện phát đa hướng hiệu quả bằng cách sử dụng chuyển tiếp đường dẫn ngược dọc theo cây được hình thành bởi các tuyến từ máy khách đến nút với nútId gần nhất với một objId nhất định. Các đặc tính địa phương mạng của Pastry đảm bảo rằng các cây phát đa hướng có hiệu quả; tức là, chúng dẫn đến việc cung cấp dữ liệu và sử dụng tài nguyên hiệu quả trong Internet cơ bản.