Pastry (DHT)

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm

3.1 Giới thiệu về Pastry Gần đây các ứng dụng Internet trong mạng ngang hàng đã được phổ biến một cách rộng rãi thông qua các ứng dụng chia sẻ file như Napster, Gnutella và FreeNet. Trong khi khá nhiều sự chú ý đều tập trung vào các vấn đề bản quyền được đưa ra bởi các ứng dụng cụ thể thì các hệ thống P2P lại đưa nhiều khía cạnh về vấn đề kỹ thuật như kiểm soát phân cấp, tự tổ chức và khả năng mở rộng. Các hệ thống P2P được mô tả như một hệ thống phân phối, trong đó tất cả các node đều có nhiệm vụ và năng lực giống nhau, đồng thời tất cả các thông tin truyền thông là đối xứng. Hiện nay có khá nhiều dự án nhằm xây dựng các ứng dụng P2P. Một trog những vấn đề quan trọng trong việc xây dựng này là nhằm cung cấp các thuật toán hiệu quả cho vị trí đối tượng và quá trình định tuyến trong mạng. Pastry là một trong những giải pháp được đưa ra. Pastry có khả năng chống chịu lỗi, khả năng mở rộng và đáng tin cậy. Hơn nữa, Pastry còn có đặc tính định tuyến cục bộ khá tốt. Pastry được thiết kế như một chất nền chung cho việc xây dựng một loạt các ứng dụng mạng ngang hàng trên Internet như chia sẻ file toàn cầu, lưu trữ file, truyền thông nhóm và các hệ thống đặt tên. Một số ứng dụng được xây dựng trên đinh của Pastry cho đến nay bao gồm một tiện ích lưu trữ liên tục chung, được gọi là PAST và một hệ thống có khả năng mở rộng, đó là Scribe. Còn lại các ứng dụng khác đang được phát triển. Pastry cung cấp các khả năng sau đây: đầu tiên mỗi node trong mạng pastry sẽ có một định danh duy nhất (Nodeid) trong một không gian định danh 128 bit vòng tròn. Khi có một thông điệp và một khóa 128 bit dạng số, một node pastry sẽ hiệu quả trong việc định tuyến thông điệp đó tới một node với nodeid có số gần nhất với khóa, trong số tất cả các node pastry hiện đang sống. Số lượng chuyển tiếp các bước trong mạng bao phủ pastry là O (logN), trong khi kích thước của bảng định tuyến được duy trì trong mỗi node Pastry chỉ là O (logN) (trong đó N là số node Pastry sống trong mạng bao phủ). Tại mỗi node Pastry dọc theo đường định tuyến mà một tin nhấn có, ứng dụng sẽ được thông báo và có thể thực hiện các tính toán ứng dụng cụ thể có liên quan đến tin nhắn. Thứ hai, mỗi node Pastry sẽ tiến hành theo dõi L hàng xóm trực tiếp của nó trong không gian nodeid(được gọi là tập lá) và thông báo cho các ứng dụng của các node mới đến, node ra và node phục hồi trong tập lá. Thứ ba, pastry đưa vào tài khoản cục bộ trong Internet cơ bản, nó tìm cách giảm thiểu khoảng cách truyền đi thông điệp, theo một hệ mét xấp xỉ vô hướng giống như độ trễ lệnh ping. Pastry hoàn toàn là phi tập trung, có khả năng mở rộng và tự tổ chức. Bởi vậy nó sẽ tự động thích nghi với sự ra đi, đến và sự thất bại của các node. ứng dụng P2P xây dựng trên pastry có thể sử dụng khả năng của mình bằng nhiều cách, bao gồm: • Ánh xạ đối tượng ứng dụng tới các node Pastry: Các đối tượng ứng dụng cụ thể được phân công thành các định danh ngẫu nhiên đồng đều, duy nhất (các ObjId) và được ánh xạ tới k (k>=1), các node với nodeId có số gần nhất với objId. Đại lượng k phản ánh mức độ mong muốn nhân rộng các ứng dụng cho các đối tượng. • Cách chèn them các đối tượng: Các đối tượng ứng dụng cụ thể có thể được them vào bằng cách đinh tuyến một thong điệp Pastry sử dụng ObjId như là khóa (key). • Quá trình truy cập các đối tượng: Các đối tượng ứng dụng cụ thể có thể được tra cứu, liên lạc hoặc thu hồi bằng cách định tuyến một thông điệp Pastry có sử dụng ObjId như là khóa. Theo định nghĩa, thong điệp này được đảm bảo đến một node có khả năng duy trì một bản sao của đối tượng được yêu cầu, trừ khi tất cả k node với các nodeId gần nhất với ObjId đều thất bại • Tính đa dạng: Việc phân công các nodeId là ngẫu nhiên và không thể bị hỏng bởi một sự tấn công nào đó. Như vậy, với xác suất cao, các node với các nodeId liền kề có tính đa dạng cả về vị trí địa lý, thẩm quyền, quyền sở hữu và việc đính kèm các tập tin trong mạng…Điều này giảm thiểu xác suất thất bại đồng thời của tất cả k node trong việc duy trì một bản sao đối tượng. • Khả năng cân bằng tải: Cả nodeId và ObjId đều được phân bố ngẫu nhiên và đồng đều trong không gian định danh Pastry 128bit. Kết quả này tạo nên một sự cân bằng tốt đầu tiên nhằm lưu trữ các yêu cầu và truy vấn tải trọng giữa các node Pastry cũng như trong mạng Internet cơ bản. • Hiệu quả và khả năng mở rộng việc phổ biến thông tin: Các ứng dụng có thể thực hiện multicast một cách 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 định tuyến từ các client tới node có nodeId gần với ObjId nhất. Tính chất cục bộ của mạng Pastry đảm bảo rằng các kết quả multicast trên cây là khá hiệu quả, tức là dữ liệu có hiệu quả trong việc cung cấp và sử dụng nguồn tài nguyên Internet cơ bản. Pastry là một giao thức phân phối dữ liệu và định tuyến ở lớp ứng dụng trong các ứng dụng mạng ngang hang có cấu trúc. Đúng như định nghĩa của nó, Pastry có 2 nhiệm vụ chính là phân phối dữ liệu trong một mạng ngang hang và tìm kiếm dữ liệu trong mạng dựa vào khóa tìm kiếm. Hệ thống Pastry là một hệ thống phân tán có khả năng tự cấu hình và có tính ổn định cao, khả năng chống chịu lỗi tốt, đồng thời nó cũng có khả năng mở rộng và ứng dụng cho những dịch vụ lớn. Pastry sử dụng giao thức DHT để lấy định danh các node tham gia vào hệ thống mạng. Với dải địa chỉ lớn thì giao thức DHT quả thực rất phù hợp với hệ thống mạng ngang hang, không ngoại trừ đối với Pastry. Tuy nhiên điều thú vị của Pastry nằm ở bảng định tuyến sẽ được mô tả dưới đây.

Hình 3.1 Bảng định tuyến của node 10233102 trong Pastry Node và dữ liệu trong mạng Pastry được định danh bởi một giá trị 128bit (nodeId và ObjId). Mỗi dữ liệu lưu trữ trong mạng được băm bởi một hàm băm, từ đó thu được một giá trị gọi là khóa và dữ liệu này được lưu trữ tại node quả lý dãy các khóa có chứa giá trị khóa này (giá trị khóa thu được khi băm dữ liệu). Mỗi node trong mạng sẽ lưu trữ một bảng định tuyến (routing table) một tập các hàng xóm (neighborhood – set) và một tập namespace. Pastry dùng các dữ liệu này để quản lý và duy trì sự ổn định của mạng, đồng thời phục vụ cho việc tìm kiếm dữ liệu. Ở hình 3.1 là bảng định tuyến của nodeId 10233102. Dựa vào bảng định tuyến này, node 10233102 có thể gửi dữ liệu đến cho node khác. Ví dụ 10233102 muốn gửi thông điệp m tới cho node 33321220. Đầu tiên nó sẽ tìm trong các node hàng xóm trong bảng định tuyến, nếu có sẽ gửi đến luôn. Nếu không tìm thấy nó sẽ tìm trong Routing Table và so sánh các ký tự ban đầu của node cần gửi đến 33321220 với các cột trong Routing Table. Cụ thể là node 33321220 có ký tự đầu là 3: nó sẽ tìm trong Routing Table tại hàng 1 cột 3 và tìm được node 31203203. Do ngay từ ký tự đầu của node cần gửi đã khác node gửi nên quá trình tìm kiếm dừng lại. Node 1023312 sẽ gửi đến node 31203203 với yêu cầu sẽ gửi thông điệp m đến node 33321220. Quá trình này tiếp tục xảy ra cho đến khi đến được node cần gửi.

Hình 3.2 Node 10233102 gửi thông điệp m đến node 33321220 Các node định kỳ gửi các gói tin keep-alive cho các node bằng hàng xóm của nó và nếu như một node nào đó không nhận được gói keep-alive của một node bằng xóm trong tập hàng xóm của nó trong một thời gian nhất định thì nó sẽ xem như node hàng xóm đã rời khỏi mạng và tự động update thông tin.