Tài liệu Nâng cao hiệu năng của vài hệ thống mạng ngang hàng phi cấu trúc

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN BẠCH LÊ NÂNG CAO HIỆU NĂNG CỦA MỘT SỐ HỆ THỐNG MẠNG NGANG HÀNG PHI CẤU TRÚC LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN HÀ NỘI - 2008 MỤC LỤC Bảng ký hiệu các chữ viết tắt ....................................................................................... 4 Tóm tắt luận văn .......................................................................................................... 5 Chƣơng 1. TỔNG QUAN VỀ CÁC HỆ THỐNG P2P ................................................. 5 1.1. Khái quát về các hệ thống P2P .......................................................................... 5 1.2. Phân loại các hệ thống P2P ............................................................................... 6 1.3. Vấn đề hiệu năng của các hệ thống P2P phi cấu trúc ......................................... 8 Chƣơng 2. HỆ THỐNG MẠNG FREENET VÀ MÔ HÌNH THẾ GIỚI NHỎ ........... 13 2.1. Hệ thống mạng Freenet ................................................................................... 13 2.2. Mô hình thế giới nhỏ ...................................................................................... 19 2.3. Liên hệ Freenet và mô hình thế giới nhỏ ......................................................... 25 Chƣơng 3. PHƢƠNG PHÁP LƢU TRỮ NÂNG CAO NHÓM ................................. 29 3.1. Các độ đo hiệu năng ....................................................................................... 29 3.2. Hiệu năng Freenet khi tải mạng tăng ............................................................... 30 3.3. Phƣơng pháp lƣu trữ nâng cao nhóm............................................................... 35 Chƣơng 4. PHƢƠNG PHÁP LƢU TRỮ NÂNG CAO NHÓM THÍCH NGHI .......... 42 4.1. Một số vấn đề tồn tại của phƣơng pháp nâng cao nhóm .................................. 42 4.2. Phƣơng pháp nâng cao nhóm khi mối quan tâm của mạng thay đổi ................ 44 4.3. Phƣơng pháp nâng cao nhóm thích nghi.......................................................... 48 Kết luận ..................................................................................................................... 59 Tài liệu tham khảo ..................................................................................................... 60 2 BẢNG KÝ HIỆU CÁC CHỮ VIẾT TẮT KÝ HIỆU P2P LRU EC CỤM TỪ ĐƢỢC VIẾT TẮT GIẢI NGHĨA Peer-to-Peer Mạng ngang hàng Least Recently Used Phƣơng pháp quản lý lƣu trữ cơ sở của Freenet. Enhanced-Clustering Replacement Scheme Phƣơng pháp quản lý lƣu trữ nâng cao nhóm Nâng cao hiệu năng của một số hệ thống mạng ngang hàng phi cấu trúc 3 TÓM TẮT LUẬN VĂN Ngày nay, xu hƣớng của thế giới thông tin là trải rộng toàn cầu, phân tán mọi nơi, mỗi thiết bị dù ở nơi đâu nếu có kết nối mạng đều có thể truy cập thông tin đƣợc cung cấp bởi những nơi rất xa. Xuất hiện và phát triển cùng với môi trƣờng phân tán từ lúc sơ khai là các hệ thống theo mô hình client/server, nhằm đƣa ra một cơ chế để hỗ trợ cung cấp các dịch vụ qua mạng. Trong những môi trƣờng phân tán nhỏ, mô hình client/server đã thể hiện hiệu quả rất lớn và đã mang lại nhiều tiện ích. Tuy nhiên, trong môi trƣờng phân tán rộng lớn, đa dạng, hỗn tạp ngày nay và trong tƣơng lai, mô hình client/server đã thể hiện nhiều nhƣợc điểm khó khắc phục. Đây chính là động cơ thúc đẩy để phát triển một mô hình hệ thống phân tán mới phù hợp hơn. Mô hình mạng ngang hàng (Peer-to-Peer hay gọi tắt là P2P) đang là xu hƣớng phát triển mới trong lĩnh vực nghiên cứu xây dựng các hệ thống mạng phân tán hiện nay. Đặc tính của các hệ thống mạng ngang hàng cho phép các phần tử hỗn tạp tham gia vào hệ thống, chỉ cần tuân theo một số giao thức giao tiếp nhất định. Các hệ thống này phù hợp với môi trƣờng phân tán rộng lớn, đa dạng thành phần, hoạt động linh hoạt và ổn định đối với tác động của lỗi. Trong các loại hệ thống mạng ngang hàng, các hệ thống phi cấu trúc rất đƣợc quan tâm do tính đơn giản mà linh hoạt của nó cả trong yêu cầu đối với các phần tử tham gia và giao thức giao tiếp cũng nhƣ cơ chế hoạt động của mạng, nhờ đó hệ thống có tính ứng dụng rất cao trong thực tế. Tuy nhiên, vấn đề lớn nhất mà các hệ thống mạng ngang hàng phi cấu trúc gặp phải xuất phát chính từ tính đơn giản của hệ thống, đó là hiệu năng thấp. Nguyên nhân của vấn đề này là các hệ thống P2P phi cấu trúc không có những cơ chế điều khiển chặt chẽ, trong đó các phần tử hoạt động không có nhiều thông tin để ra quyết định, dẫn đến hiệu năng của mạng thấp. Bài toán nâng cao hiệu năng của các hệ thống mạng ngang hàng phi cấu trúc đã thu hút nhiều nghiên cứu theo nhiều hƣớng khác nhau nhằm mục đích chung là cải tiến các hệ thống này để chúng hoạt động hiệu quả hơn. Trong nghiên cứu này, tác giả lựa chọn nghiên cứu về vấn đề hiệu năng của các hệ thống P2P phi cấu trúc nói chung và các biện pháp nâng cao hiệu năng của Freenet - một hệ thống lƣu trữ ẩn danh phân tán đƣợc xây dựng nhƣ là một hệ thống mạng ngang hàng đã đƣợc áp dụng rộng rãi. Freenet là một trong những hệ thống mạng P2P phi cấu trúc đặc trƣng trong việc thay thế phƣơng pháp định tuyến phát tràn kém hiệu quả thông thƣờng của các hệ thống P2P phi cấu trúc bằng một phƣơng pháp thông minh hơn, có lựa chọn tốt hơn. Tuy nhiên, hệ thống Freenet ban đầu chỉ hoạt động hiệu quả khi số lƣợng file dữ liệu lƣu trữ trên mạng là nhỏ. Nghiên cứu này xuất phát từ phƣơng pháp lƣu trữ nâng cao nhóm sử dụng mô hình thế giới nhỏ để nâng cao hiệu năng của Freenet khi số lƣợng Nâng cao hiệu năng của một số hệ thống mạng ngang hàng phi cấu trúc 4 file lƣu trữ trên mạng lớn mà không làm ảnh hƣởng đến mục đích thiết kế của hệ thống Freenet ban đầu. Tƣ tƣởng về mô hình thế giới nhỏ đã tồn tại rất phổ biến trong đời sống xã hội, tự nhiên, kỹ thuật. Những tƣ tƣởng này đã đƣợc mô hình hoá và áp dụng rất nhiều trong các hệ thống phân tán. Tƣ tƣởng này cũng đã đƣợc áp dụng hiệu quả để nâng cao hiệu năng của các hệ thống mạng ngang hàng nói chung và Freenet nói riêng. Xuất phát từ phƣơng pháp trên, tác giả đề tài đã có một số đánh giá chỉ ra những yếu tố chƣa đƣợc đề cập tới, dẫn tới hiệu năng của Freenet khi áp dụng phƣơng pháp lƣu trữ nâng cao nhóm không giữ đƣợc nhƣ kết quả tốt nhƣ kết quả đã đƣợc đƣa ra. Yếu tố quan trọng là nghiên cứu đó chỉ đánh giá hiệu năng của Freenet khi tải mạng tăng cao mà chƣa xem xét trƣờng hợp xu hƣớng truy cập chính trên mạng thay đổi theo thời gian. Từ những đánh giá cơ sở, tác giả đề tài đề xuất một phƣơng pháp lƣu trữ nâng cao nhóm thích nghi, trong đó có những cải tiến phù hợp để tăng tính thích nghi của mạng Freenet, giúp cho Freenet hoạt động hiệu quả cả khi tải mạng tăng cao và cả khi xu hƣớng quan tâm của ngƣời dùng thay đổi. Kết quả luận văn đạt đƣợc đã góp phần vào đƣa ra và bƣớc đầu giải quyết một số vấn đề liên quan đến bài toán nâng cao hiệu năng của Freenet. Những vấn đề này sẽ tiếp tục đƣợc nghiên cứu sâu rộng hơn để phù hợp hơn và có thể áp dụng trên thực tế. Trong tài liệu này, chƣơng 1 sẽ xem xét tổng quát về các hệ thống mạng ngang hàng, trong đó có các hệ thống không có cấu trúc và một số nghiên cứu nâng cao hiệu năng có liên quan. Chƣơng 2 tìm hiểu sâu hơn về hệ thống mạng Freenet, đồng thời tìm hiểu về mô hình thế giới nhỏ và liên hệ của nó với Freenet. Chƣơng 3 trình bày phƣơng pháp lƣu trữ nâng cao nhóm cải thiện hiệu năng Freenet khi tải mạng lớn dựa trên tƣ tƣởng mô hình thế giới nhỏ của Hui Zhang và nhóm nghiên cứu. Chƣơng 4 đánh giá lại những vấn đề còn tồn tại của phƣơng pháp của Hui Zhang, sau đó đề xuất một phƣơng pháp lƣu trữ nâng cao nhóm thích nghi với một số thay đổi cần thiết nhằm mục đích tăng tính thích nghi của các nút mạng Freenet, để đảm bảo Freenet hoạt động hiệu quả cả khi tải mạng lớn và xu hƣớng quan tâm trên mạng thay đổi. Nâng cao hiệu năng của một số hệ thống mạng ngang hàng phi cấu trúc 5 Chƣơng 1. TỔNG QUAN VỀ CÁC HỆ THỐNG P2P 1.1. Khái quát về các hệ thống P2P Trong mô hình hệ thống phân tán truyền thống client/server, các tài nguyên đƣợc đặt trên một hoặc một số nút mạng, đƣợc gọi là server. Các nút khác trên mạng, đƣợc gọi là client, truy vấn các server để lấy thông tin mong muốn. Các server là điểm trung tâm trên mạng, đóng vai trò quan trọng chủ yếu trong việc cung cấp dịch vụ mạng. Kiến trúc client/server có ƣu điểm là dễ bảo trì khi có thể thay thế, sửa chữa, nâng cấp server mà không làm ảnh hƣởng đến client. Ngoài ra có thể dễ dàng cập nhật dữ liệu và đảm bảo an ninh mạng do dữ liệu đƣợc lƣu trữ tập trung. Tuy nhiên cũng do dữ liệu tập trung nên tồn tại các điểm tập trung lỗi tại các server này, kéo theo hệ thống có khả năng chịu lỗi kém. Khi server lỗi, dịch vụ mạng sẽ bị gián đoạn và các yêu cầu từ client không đƣợc đáp ứng. Dù mô hình client/server cho phép các client truy cập dữ liệu trên server với thời gian đáp ứng chấp nhận đƣợc bằng nhiều thuật toán cân bằng tải và chịu lỗi rắc rối nhƣng giới hạn về băng thông làm tăng nguy cơ vấn đề nút cổ chai tại các server, làm giảm khả năng mở rộng. Chính những vấn đề này đã thúc đẩy các nhà nghiên cứu tiếp cận theo hƣớng xây dựng một hệ thống phân tán trong đó phân tán tải xử lý và băng thông ra cho mọi nút tham gia trên mạng. Kết quả của sự thúc đẩy này là sự ra đời của các hệ thống mạng ngang hàng, hay còn gọi là các hệ thống P2P. Các hệ thống mạng P2P đã khắc phục đƣợc rất nhiều khiếm khuyết của kiến trúc client/server truyền thống. Khái niệm P2P đã phát triển các mối liên hệ động trên mạng phân tán, không chỉ giữa máy tính và máy tính mà còn giữa con ngƣời và con ngƣời. Những hệ thống này đã chứng minh hiệu quả đối với nhiều mục đích khác nhau nhƣ chia sẻ các file dữ liệu số với nhiều định dạng khác nhau cũng nhƣ dữ liệu thời gian thực. Nhìn chung, một hệ thống mạng P2P bao gồm một số lƣợng lớn các điểm nút phân tán, hỗn tạp, tự trị và có tính động cao, gọi là các peer. Các điểm nút đóng vai trò tƣơng đƣơng nhau và đƣợc kết nối qua những liên kết đặc biệt, không phụ thuộc vào mạng vật lý bên dƣới. Trong cùng một thời điểm, mỗi nút mạng có thể hoạt động đồng thời vừa là một server và vừa là một client, vừa cung cấp dịch vụ cho mạng và vừa sử dụng dịch vụ mạng do các các nút khác cung cấp. Mỗi nút tham gia vào hệ thống mạng P2P là một thành phần tích cực và có năng lực đáng kể. Chúng tham gia vào hệ thống P2P để chia sẻ một phần tài nguyên của bản thân chúng nhƣ khả năng xử lý, dung lƣợng lƣu trữ, phần mềm, và nội dung file… Các Nâng cao hiệu năng của một số hệ thống mạng ngang hàng phi cấu trúc 6 điểm nút có thể truy cập trực tiếp đến nút khác mà không qua các thực thể trung gian, nhờ đó có thể phân tán tải xử lý và băng thông mạng. Việc một hay một số nút mạng lỗi không gây ảnh hƣởng nhiều đến mạng toàn cục do phần còn lại của mạng vẫn đầy đủ khả năng cung cấp các dịch vụ mạng theo yêu cầu. Do vậy, các hệ thống P2P có khả năng chịu lỗi cao và giải quyết đƣợc bài toán nút cổ chai. Chức năng của các hệ thống P2P đƣợc xây dựng rất đa dạng, trong đó có thể chia thành các nhóm ứng dụng nhƣ truyền thông thông tin, chia sẻ dịch vụ và chia sẻ tài nguyên. Để cài đặt các chức năng này, các hệ thống P2P cần mang một số đặc điểm đặc trƣng [19]. Thứ nhất, các hệ thống P2P cần hoạt động phi tập trung, nghĩa là không có điểm tập trung lƣu trữ mọi thông tin về hệ thống, dữ liệu và ngƣời dùng. Mỗi nút trong hệ thống cần có một số chức năng tích hợp gắn liền để nó có khả năng thực hiện thao tác gia nhập vào hệ thống, có thông tin định tuyến và có khả năng tạo yêu cầu, chuyển tiếp yêu cầu và nhận đáp ứng. Một số hệ thống P2P có sử dụng cấu trúc client/server, tuy nhiên chỉ áp dụng cho một số tác vụ trên mạng và hoạt động đồng thời với các tác vụ phi tập trung theo cấu trúc P2P. Thứ hai, các hệ thống P2P cần có cấu trúc theo một cách nào đó để thao tác định tuyến đƣợc dễ dàng và cải thiện đƣợc chức năng tìm kiếm, nhằm hỗ trợ hiệu quả cho việc chia sẻ dữ liệu và các tài nguyên khác. Thứ ba, các hệ thống P2P cần có độ tin cậy dù môi trƣờng ứng dụng mang tính động. Gần nhƣ hoạt động của của mọi hệ thống P2P đều bao gồm việc các nút gia nhập vào hệ thống, rời khỏi hệ thống, và một số nút tạm thời không hoạt động. Do vậy, các hệ thống này cần phải có các cơ chế để ổn định đƣợc những thuộc tính quan trọng của hệ thống nhƣ đƣờng kính mạng và mức độ kết nối của hệ thống. Thứ tƣ, các hệ thống P2P cần có khả năng mở rộng. Một tác động của tính phi tập trung là số nút trên mạng có thể lớn tuỳ ý. Dù vậy, hệ thống vẫn phải có khả năng phục vụ yêu cầu của tất cả các nút theo một cách hiệu quả và nhanh chóng. 1.2. Phân loại các hệ thống P2P Dù P2P có những nguyên tắc chung về thiết kế nhƣng các hệ thống mạng ngang hàng P2P khác nhau cũng mang nhiều đặc điểm kiến trúc khác nhau. Dựa vào các tiêu chí khác nhau ngƣời ta có thể đƣa ra các loại hệ thống P2P khác nhau. Ở đây, ta xem xét cách phân loại phổ biến nhất. Theo đó, các hệ thống mạng ngang hàng P2P đƣợc chia thành hai nhóm chính: tập trung và phi tập trung. Một hệ thống P2P tập trung có một thƣ mục tập trung đặt ở vị trí trung tâm, thƣờng đặt trên một server. Các server trong hệ thống P2P tập trung không chứa mọi tài nguyên để cung cấp cho các client nhƣ trong mô hình client/server mà chỉ chứa Nâng cao hiệu năng của một số hệ thống mạng ngang hàng phi cấu trúc 7 thông tin về tài nguyên nào đƣợc nút nào cung cấp để hỗ trợ các điểm nút trong mạng định tuyến yêu cầu. Thƣ mục này liên tục đƣợc cập nhật và server chứa thƣ mục đóng vai trò là nơi nhận các yêu cầu tìm kiếm của ngƣời dùng. Khi các nút trong mạng có yêu cầu tìm kiếm, chúng gửi yêu cầu đến server thƣ mục tập trung này để tìm kiếm tài nguyên mong muồn. Các server tập trung chỉ đƣợc sử dụng trong thao tác định tuyến yêu cầu tìm kiếm còn các tác vụ còn lại theo kiến trúc P2P. Tuy nhiên việc sử dụng các server vẫn không khắc phục đƣợc nhƣợc điểm khó mở rộng và gây ra điểm tập trung lỗi nhƣ kiến trúc client/server [4] [14]. Ngƣợc lại, hệ thống P2P phi tập trung không có server thƣ mục tập trung. Các nút trong hệ thống P2P phi tập trung tự thu thập thông tin về mạng và gửi yêu cầu tới nút tiềm năng. Các hệ thống mạng ngang hàng phi tập trung lại đƣợc chia thành hai loại: có cấu trúc và phi cấu trúc [14], dựa vào mối liên quan giữa topo mạng và cơ chế bố trí dữ liệu trên các nút trong hệ thống. Một hệ thống P2P đƣợc coi là có cấu trúc khi cơ chế bố trí dữ liệu có mối liên hệ mật thiết với topo mạng. Topo mạng đƣợc điều khiển một cách chặt chẽ và dữ liệu không đƣợc đặt ở các nút ngẫu nhiên mà đƣợc sắp đặt ở những vị trí cụ thể, chính xác dựa trên topo, hay hệ thống có cơ chế ánh xạ mỗi tài nguyên tới một số nút xác định. Cơ chế này giúp cho các hệ thông P2P có cấu trúc hoạt động hiệu quả, giảm thiểu số thông báo cần truyền qua mạng, tuy nhiên lại kém linh hoạt. CAN [15], Chord [20], Tapestry [24] là những hệ thống nhƣ vậy. Một hệ thống P2P đƣợc coi là phi cấu trúc khi không thƣ mục tập trung nào, cũng nhƣ không có mối liên hệ nào giữa cơ chế bố trí dữ liệu và topo mạng. Kiến trúc này rất linh động cho các nút tham gia vào mạng hoặc rời khỏi mạng. Việc sắp đặt dữ liệu không dựa trên bất kỳ thông tin nào về topo mạng, do vậy các file dữ liệu đƣợc bố trí trên những nút ngẫu nhiên. Khi nút mạng muốn tìm kiếm dữ liệu, trƣớc tiên nó phải định vị dữ liệu sau đó mới thực hiện tải dữ liệu về, trong đó cơ chế định vị dữ liệu là một phần rất quan trọng. Trong quá trình tìm kiếm, nút mạng gửi yêu cầu tới láng giềng của nó dựa trên một số tiêu chí lựa chọn [9], do vậy tập các nút nhận đƣợc yêu cầu tìm kiếm không liên quan đến nội dung dữ liệu cần tìm kiếm nhƣ trong các hệ thống có cấu trúc [4]. Cơ chế tìm kiếm nhƣ vậy trong các hệ thống không cấu trúc kém hiệu quả hơn do khó hạn chế đƣợc lƣợng thông báo truyền trên mạng nhƣng lại linh hoạt hơn so với các hệ thống có cấu trúc, cho phép các nút tự tổ chức để tạo topo mạng mới. Ví dụ điển hình cho các hệ thống P2P không cấu trúc là Gnutella [26], Freenet [3]. Ngoài ra các hệ thống P2P cũng có thể phân biệt bằng hai nhóm thuần và lai. Trong hệ thống thuần, mọi nút có vai trò tƣơng đƣơng nhƣ nhau. Với các hệ thống lai, tồn tại các server giúp cho các điểm nút liên lạc với nhau [1]. Ta có thể nhận thấy cách phân loại này cũng tƣơng tự nhƣ các hệ thống tập trung và phi tập trung. Nâng cao hiệu năng của một số hệ thống mạng ngang hàng phi cấu trúc 8 Mỗi kiến trúc P2P đều có ƣu và nhƣợc điểm riêng và tuỳ theo yêu cầu xây dựng mạng mà ngƣời ta lựa chọn kiến trúc nào. Hiện nay trong môi trƣờng Internet, các hệ thống P2P phi cấu trúc đƣợc sử dụng rộng rãi nhất nhờ đặc tính tự tổ chức của các nút và phù hợp với môi trƣờng mạng hỗn tạp và động nhƣ hiện nay. Bên cạnh những ƣu điểm, một vấn đề lớn với các hệ thống P2P phi cấu trúc là hiệu năng của mạng. Nghiên cứu này sẽ tập trung vào vấn đề đánh giá hiệu năng của các hệ thống mạng P2P phi cấu trúc nói chung và cải thiện hiệu năng của Freenet nói riêng - một trong những hệ thống P2P phi cấu trúc đƣợc triển khai rộng rãi. 1.3. Vấn đề hiệu năng của các hệ thống P2P phi cấu trúc Các hệ thống mạng mang hàng mới xuất hiện gần đây và đang trong quá trình phát triển. Do tính mới mẻ này, quá trình phát triển các hệ thống này đã và đang đặt ra nhiều vấn đề cần nghiên cứu giải quyết. Lĩnh vực nghiên cứu về các hệ thống mạng ngang hàng nói chung và các hệ thống mạng ngang hàng phi cấu trúc nói riêng hiện nay đang rất rộng mở và cần nhiều đóng góp hơn nữa để giải quyết các vấn đề phát sinh và phát triển các hệ thống này ngày càng hoàn thiện hơn, đáp ứng đƣợc những yêu cầu thực tế. Với các hệ thống P2P có cấu trúc, dữ liệu đƣợc xác định ở một hoặc một số nút mạng xác định nên cơ chế quan trọng là cơ chế sắp đặt dữ liệu, còn thao tác tìm kiếm lại trở nên đơn giản do dữ liệu đã đƣợc ánh xạ tới nút tƣơng ứng. Khi phát sinh dữ liệu cần lƣu trữ lên mạng, cơ chế sắp đặt dữ liệu của P2P có cấu trúc sẽ điều khiển chặt chẽ để lƣu dữ liệu đó ở một nút chính xác nào đó. Sau khi dữ liệu đã đƣợc lƣu trữ, thao tác tìm kiếm không phải định vị dữ liệu mà chỉ cần gửi yêu cầu đến nút tƣơng ứng đang chứa dữ liệu đó. Chính cơ chế này làm cho các hệ thống P2P có cấu trúc định tuyến rất hiệu quả. Tuy nhiên, thao tác tìm kiếm trên các hệ thống P2P phi cấu trúc lại không hề đơn giản nhƣ vậy. Trong các hệ thống P2P phi cấu trúc, đặc tính nổi bật là cơ chế sắp đặt dữ liệu không rõ ràng và tính ngẫu nhiên cao. Dữ liệu đƣợc đƣa lên mạng không dựa trên bất kỳ thông tin nào về topo mạng nên đƣợc bố trí trên những nút ngẫu nhiên. Giữa dữ liệu và nút lƣu trữ dữ liệu đó không có mối liên hệ nào cả. Vì thế, vấn đề phức tạp chính với các hệ thống này là cơ chế tìm kiếm. Nguyên tắc tìm kiếm chung trong các hệ thống phi cấu trúc là các nút mạng chuyển tiếp các thông báo chứa thông tin về dữ liệu cần tìm qua nhiều bƣớc, từ nút này sang nút khác, cho đến khi thông báo tìm kiếm tới đƣợc nút có dữ liệu cần tìm hoặc thông báo đó hết hạn. Tại mỗi nút nhận đƣợc thông báo tìm kiếm, nếu nó không chứa dữ liệu cần tìm, nút đó sẽ tự quyết định lựa chọn một hoặc một số nút kế tiếp để chuyển tiếp thông báo mà không theo điều khiển toàn cục nào. Cơ chế tìm kiếm nhƣ vậy rất khó khăn và không có đảm bảo nào rằng yêu cầu tìm kiếm sẽ đƣợc đáp ứng, Nâng cao hiệu năng của một số hệ thống mạng ngang hàng phi cấu trúc 9 dẫn đến hiệu năng của mạng thấp với tỷ lệ thành công thấp và số chặng trung bình cho một tìm kiếm tăng cao. Từ nguyên tắc tìm kiếm chung, các hệ thống P2P phi cấu trúc thƣờng áp dụng các thuật toán tìm kiếm đơn giản, đa số dựa trên phát tràn (flood-based-technique) [17]. Gnutella [26] là một trong những mạng P2P không cấu trúc phát triển sớm nhất và sử dụng quảng bá phát tràn. Khi một nút cần tìm kiếm dữ liệu, nó gửi thông báo yêu cầu tới mọi nút láng giềng. Đến lƣợt các nút nhận đƣợc thông báo yêu cầu, nếu nó không có dữ liệu cần tìm, các nút này lại gửi thông báo yêu cầu đến mọi nút láng giềng trừ nút vừa gửi thông báo cho nó. Quá trình cứ tiếp tục đến khi yêu cầu tìm kiếm tới đƣợc nút chứa dữ liệu cần tìm hoặc thông báo hết hạn. Cách tìm kiếm này chỉ hiệu quả trong một mạng nhỏ. Với một hệ thống mạng lớn với nhiều nút tham gia, cơ chế tìm kiếm đó có thể dẫn tới lƣợng thông báo lƣu thông trên mạng là rất lớn làm cho khả năng mở rộng của hệ thống rất thấp. Các hệ thống P2P phi cấu trúc phát triển sau này vẫn sử dụng nguyên tắc tìm kiếm chung, tuy nhiên đã áp dụng các thuật toán thông minh hơn để giải quyết vấn đề về hiệu năng, nhƣ nghiên cứu [16] và Freenet [3]. Ngoài ra, các nhà nghiên cứu cũng đồng thời đề xuất nhiều biện pháp giải quyết bài toán cải thiện hiệu năng cho các hệ thống P2P phi cấu trúc đã có. Đa số các kỹ thuật đó đều tập trung cải tiến thuật toán định tuyến yêu cầu trên mạng để nâng cao hiệu năng của toàn hệ thống. 1.3.1. Một số nghiên cứu nâng cao hiệu năng Freenet Nhƣ ta đã thảo luận, bài toán cải tiến hiệu năng của các mạng P2P không cấu trúc nói chung là một bài toán phổ biến và thu hút nhiều nghiên cứu. Nghiên cứu này sẽ tập trung thảo luận về hiệu năng của các hệ thống mạng ngang hàng phi cấu trúc nói chung và hệ thống mạng Freenet nói riêng. Trong phần này, chúng ta xem xét sơ lƣợc về một số nghiên cứu trong đó đƣa ra các biện pháp để nâng cao hiệu năng của hệ thống mạng Freenet. Trong nghiên cứu [2] tác giả đã đánh giá về hiệu năng của một số mạng P2P không cấu trúc, trong đó có Freenet. Tác giả chỉ ra việc sử dụng các thuật toán tìm kiếm dựa trên phát tràn dẫn đến hiệu năng của mạng thấp. Tác giả đã đề xuất một số thuật toán mới dựa trên ý tƣởng ƣu tiên những nút có mức độ quan tâm đến dữ liệu cao để nâng cao hiệu năng của Gnutella và Freenet. Các thuật toán mới tổ chức các điểm nút trên mạng thành các cộng đồng có chung mối quan tâm. Hai nút mạng đƣợc gọi là có chung mối quan tâm nếu chúng có một vài file lƣu trữ cục bộ giống nhau. Khi nút mạng muốn tìm dữ liệu, đầu tiên nó liên lạc với một số nút khác - đƣợc sắp xếp theo mức độ quan tâm chung với dữ liệu cần tìm. Nếu các nút đó không tìm thấy dữ liệu, thuật toán lại sử dụng giao thức cơ sở của mạng tƣơng ứng là Gnutella hoặc Freenet. Tác giả đã sử dụng các mô phỏng để đánh giá hiệu năng của các thuật toán đó, trong đó đƣa vào nhiều đặc điểm của hệ thống thực. Kết quả là các thuật toán mới cải thiện Nâng cao hiệu năng của một số hệ thống mạng ngang hàng phi cấu trúc 10 hiệu năng của hệ thống Gnutella khoảng 30%, trong khi đó giảm độ dài đƣờng đi trung bình hơn 30%. Tuy nhiên phƣơng pháp này gặp một số vấn đề xác định mức độ quan tâm chung giữa các nút [2]. Nghiên cứu [10] đánh giá trƣờng hợp thuật toán định tuyến cơ sở của Freenet có thể làm thao tác yêu cầu lún sâu vào vùng mạng không đem lại kết quả, trong khi một nút gần kề lại đang giữ file cần tìm. Từ đó, tác giả đề xuất cải tiến thuật toán định tuyến của Freenet để giảm khả năng đi sai hƣớng, nhờ đó giảm độ dài đƣờng đi tìm kiếm. Tƣ tƣởng tổng quát là thêm vào cơ chế trƣớc tiên kiểm tra các nút xung quanh nút hiện tại. Theo đó, mỗi khi nút nhận đƣợc yêu cầu tìm kiếm, nó tìm kiếm mọi nút có kết nối trực tiếp với nó (1-lookahead) hoặc mọi nút cách xa nó N chặng (N-lookahead) theo thuật toán tìm kiếm theo chiều rộng (BFS). Nếu sau thao tác trên, nút đó tìm thấy dữ liệu thì nó trả về nút phía trên. Nếu không tìm thấy, nút lại sử dụng thuật toán cơ sở của Freenet thực hiện tìm kiếm nhƣ bình thƣờng. Phƣơng pháp này cho tỷ lệ % yêu cầu thành công cao hơn mạng Freenet cơ sở đối với cùng số chặng, tuy nhiên nghiên cứu lại không đánh giá hiệu năng khi tải mạng tăng. Nhƣ ta đã biết, sau khi yêu cầu tới đƣợc nút có dữ liệu thoả mãn, dữ liệu này và thông tin về nút đáp ứng đó sẽ đƣợc sao lặp dọc đƣờng đi từ nút đáp ứng đến nút yêu cầu đầu tiên. Nghiên cứu [11] xuất phát từ đánh giá rằng khi tỷ lệ yêu cầu tìm kiếm so với chèn file mới là 99/1 thì hiệu năng của Freenet không giữ đƣợc nhƣ trƣờng hợp tỷ lệ này là 50/50. Phƣơng pháp [11] đề xuất dựa trên ý tƣởng sau mỗi yêu cầu thành công, thực hiện chèn thêm thông tin về nút đáp ứng đƣợc dữ liệu cần tìm vào các nút khác ngoài đƣờng đi của yêu cầu để tạo thêm các cạnh trên mạng phủ. Nghiên cứu [11] đã chỉ ra rằng hiệu năng của Freenet chịu ảnh hƣởng của hai yếu tố: (1) thêm các cạnh vào đâu và (2) bao nhiêu cạnh là hợp lý đối với mỗi yêu cầu thành công. Kết quả mô phỏng cho thấy ra phƣơng pháp chèn từ nút đáp ứng ngẫu nhiên theo chiều sâu (Depth-Fulfiller-Random) mang lại hiệu quả tốt nhất, có khả năng giảm độ dài đƣờng đi trung bình với hệ số 22.37. Theo đó nút đáp ứng gửi thông tin rằng khoá vừa tìm thấy do nó đang giữ tới một dãy nút không thuộc đƣờng đi của yêu cầu vừa thành công. Tại mỗi bƣớc đi, nút tiếp theo đƣợc chọn một cách ngẫu nhiên. Tuy nhiên nghiên cứu này lại chƣa trả lời đƣợc câu hỏi liệu mỗi lần chèn với số lƣợng bao nhiêu là hợp lý để mang lại hiệu quả tốt nhất. Nghiên cứu [5] đánh giá hiệu năng của Freenet về tốc độ download và tỷ lệ thành công và nhận thấy hiệu năng của Freenet không thực sự tốt. Tác giả đã đề xuất hai thay đổi với mạng Freenet để cải tiến tốc độ download và tỷ lệ yêu cầu thành công cho mọi nút tham gia vào mạng. Để cải tiến tốc độ download, tác giả đề xuất phƣơng pháp phân chia mạng có ƣu tiên (Precedencial Network Partitioning), bằng cách chia các láng giềng thành các nhóm theo băng thông và khả năng của nút để hỗ trợ định tuyến. Tác giả đã sử dụng mô phỏng mạng Freenet và giới hạn băng thông giữa các nút Nâng cao hiệu năng của một số hệ thống mạng ngang hàng phi cấu trúc 11 cũng nhƣ đƣa vào tính chất phân tán của ngƣời dùng trên mạng. Kết quả đã chỉ ra những tác động của yếu tố đó với mạng. Để cải tiến tỷ lệ yêu cầu thành công trong mạng Freenet, tác giả [5] đề xuất phƣơng pháp truyền thông tin về lƣới file trong đó mỗi nút gửi cho các nút khác một số thông tin cơ bản về những dữ liệu nào nó có thể cung cấp. Theo phƣơng pháp này, mỗi nút sử dụng 1 mảng N bit (đƣợc gọi là File Mesh) và không gian khoá cũng đƣợc phân chia thành N khoảng. Nếu nút có giữ file mà khoá tƣơng ứng thuộc khoảng i của không gian khoá, nó thiết lập giá trị bit thứ i là 1 để thể hiện sự xuất hiện của khoá đó trong phần không gian khoá tƣơng ứng. Các nút trao đổi File Mesh với nhau để mỗi nút biết nhiều hơn về các láng giềng, nhờ đó định tuyến hiệu quả hơn. Kết quả đã chỉ ra rằng phƣơng pháp đó đã tăng đáng kể tỷ lệ yêu cầu thành công. Tuy nhiên, nghiên cứu đó chƣa xem xét đến độ phức tạp của phƣơng pháp đƣa ra và đánh giá những độ đo khác của hiệu năng nhƣ độ dài đƣờng đi trung bình, đồng thời cũng chƣa đánh giá đƣợc hiệu năng của Freenet khi tải mạng tăng cao. Trong các nghiên cứu nâng cao hiệu năng của Freenet, [23] là một trong số ít nghiên cứu sử dụng tƣ tƣởng về mô hình thế giới nhỏ. Hui Zhang và các tác giả đã thực hiện mô phỏng và đã xác nhận mối quan hệ logarit giữa số chặng trung bình trên một yêu cầu và kích thƣớc mạng trong Freenet. Tuy nhiên những mô phỏng này đƣợc bố trí với tải thấp. Trong mô phỏng 1000 nút, số file trung bình đƣợc chèn vào mạng bởi một node chỉ là 2.5. [23] đã chỉ ra rằng khi tải mạng lớn, hiệu năng của Freenet suy giảm đáng kể. Khi sử dụng trực giác từ mô hình thế giới nhỏ, nhóm tác giả [23] đã thiết kế một phƣơng pháp thay thế lƣu trữ nâng cao nhóm thay cho phƣơng pháp thay thế bộ nhớ cục bộ cơ bản của Freenet là LRU. Sau khi áp dụng phƣơng pháp mới này, hiệu năng của Freenet đã đƣợc nâng cao đáng kể thậm chí trong trƣờng hợp tải lớn. Chúng ta sẽ xem xét cụ thể về phƣơng pháp này và kết quả đạt đƣợc trong chƣơng 3 của nghiên cứu này. Dù những kết quả Hui Zhang chỉ ra là rất thuyết phục, nhƣng những giả thiết của bài toán chƣa đƣợc linh động. Nghiên cứu trong luận văn này sẽ chỉ ra rằng khi mối quan tâm đến dữ liệu của ngƣời dùng trên mạng Freenet thay đổi, hiệu quả khi áp dụng phƣơng pháp lƣu trữ nâng cao nhóm trong [23] sẽ giảm đáng kể do phƣơng pháp này đã làm mất đi tính thích nghi vốn có của Freenet. Nghiên cứu này sẽ đề xuất phƣơng pháp lƣu trữ nâng cao nhóm thích nghi, trong đó thực hiện một số thay đổi cần thiết đối với phƣơng pháp lƣu trữ của Hui Zhang để tăng tính thích nghi với tình trạng mạng thay đổi trong khi vẫn giữ đƣợc những đặc tính của mô hình thế giới nhỏ để nâng cao hiệu năng của Freenet. Kết quả mô phỏng sẽ cho thấy việc áp dụng mô hình thế giới nhỏ để thực hiện một số thay đổi nhỏ đối với việc xử lý cục bộ tại các điểm nút không làm thay đổi mục đích thiết kế ban đầu của hệ thống, trong khi có thể nâng cao hiệu năng của Freenet một cách đáng Nâng cao hiệu năng của một số hệ thống mạng ngang hàng phi cấu trúc 12 kể khi tải mạng lớn và tăng tính thích nghi của các nút mạng khi xu hƣớng truy cập quan tâm của ngƣời dùng trên mạng có xu hƣớng thay đổi. Phƣơng pháp lƣu trữ nâng cao nhóm thích nghi này sẽ đƣợc trình bày trong chƣơng 4. Nâng cao hiệu năng của một số hệ thống mạng ngang hàng phi cấu trúc 13 Chƣơng 2. HỆ THỐNG MẠNG FREENET VÀ MÔ HÌNH THẾ GIỚI NHỎ Freenet là một hệ thống mạng ngang hàng phi cấu trúc đƣợc đƣa ra từ năm 2000, sau đó đã đƣợc phát triển và áp dụng rộng rãi cho tới nay nhờ chứng minh đƣợc những ƣu điểm lớn so với nhiều hệ thống mạng ngang hàng phi cấu trúc khác. Trong chƣơng này, đầu tiên ta tìm hiểu về hệ thống mạng Freenet với một số cơ chế hoạt động chính của mạng. Ta cũng sẽ tìm hiểu về mô hình thế giới nhỏ và liên hệ của Freenet với mô hình này, đặt nền tảng cho những phƣơng pháp nâng cao hiệu năng của Freenet sẽ đƣợc xem xét ở những chƣơng sau. 2.1. Hệ thống mạng Freenet 2.1.1. Sơ lược về mạng Freenet Freenet [3] là một mạng ngang hàng phi cấu trúc đƣợc xây dựng với mục đích cung cấp một hệ thống lƣu trữ và tìm kiếm thông tin ẩn danh phân tán. Mỗi nút mạng Freenet đều tham gia vào quá trình chia sẻ tài nguyên không gian lƣu trữ, vừa là một phần của không gian nhớ toàn cục, vừa tham gia tạo bản sao dữ liệu trên mạng, tìm kiếm dữ liệu trong khi vẫn đảm bảo tính ẩn danh của cả ngƣời dùng sở hữu dữ liệu gốc và ngƣời sử dụng dữ liệu. Từ khi lần đầu đƣợc Ian Clarke giới thiệu năm 2000 [3], Freenet đã liên tục đƣợc phát triển và cải tiến. Kiến trúc mức cao của Freenet tƣơng tự nhƣ Gnutella, hoàn toàn phi tập trung. Freenet hoạt động nhƣ một mạng các nút giống nhau tập hợp không gian lƣu trữ lại để lƣu trữ dữ liệu mà mỗi nút chia sẻ và định tuyến các yêu cầu tới vị trí vật lý của dữ liệu cần tìm. Các nút mạng Freenet đƣợc kết nối qua giao thức TCP/IP. Do không có điều khiển tập trung nào, khi nút bắt đầu tham gia vào mạng, nó phải tìm ra một hoặc một số nút mà nó biết để tạo kết nối. Mỗi nút chỉ biết và kết nối tới các láng giềng trực tiếp của nó mà không xác định vị trí của các nút khác và thực tế dữ liệu nào đó đƣợc lƣu trữ ở đâu trên mạng bên ngoài. Không nút nào có quyền điều khiển các nút khác nên không tạo ra cấu trúc cây, nhờ đó tránh đƣợc điểm tập trung lỗi - một nhƣợc điểm của các hệ thống tập trung. Freenet đƣợc coi là một hệ thống file phân tán đƣợc tổ chức độc lập vị trí và đƣợc tái tạo trong suốt, cho phép ngƣời dùng chia sẻ không gian đĩa của mình và sử dụng không gian đĩa của các ngƣời dùng khác cùng tham gia nhƣ là phần mở rộng không gian đĩa của chính họ. Ngƣời dùng tham gia vào mạng Freenet khi có một lƣợng không gian đĩa trống cụ thể. Sau một thời gian hoạt động, không gian lƣu trữ đó sẽ đƣợc sử dụng để lƣu trữ dữ liệu do nút đó tạo ra và một số dữ liệu do mạng gửi đến. Nâng cao hiệu năng của một số hệ thống mạng ngang hàng phi cấu trúc 14 Tất cả file trao đổi trên mạng Freenet và lƣu trữ tại các nút mạng đều đƣợc mã hoá và mô tả bằng các khoá (key) tạo ra khi áp dụng một hàm băm đối với file. Các thao tác tạo vận chuyển, tạo bản sao và xoá dữ liệu là hoàn toàn trong suốt đối với ngƣời dùng. Freenet không có đảm bảo nào về sự tồn tại của các file do khi không đủ không gian nhớ, các file dữ liệu có thể bị xoá bỏ. Điều này sẽ đƣợc khắc phục khi số nút tham gia vào mạng đủ lớn, khi đó sẽ đủ không gian nhớ để lƣu trữ vĩnh viễn mọi file. Hệ thống Freenet hoạt động ở mức ứng dụng, không sử dụng bất kỳ server chỉ mục vị trí tập trung nào, cũng nhƣ không áp dụng cơ chế tìm kiếm quảng bá phát tràn nhƣ Gnutella. Các file dữ liệu đƣợc sắp xếp ngẫu nhiên, độc lập vị trí và tự động đƣợc tạo bản sao gần những nút có yêu cầu dữ liệu, đồng thời đƣợc xoá khỏi những vị trí không quan tâm đến dữ liệu đó. Trong Freenet, việc phát hiện vị trí nguồn hoặc đích của file truyền qua mạng là không thể, và rất khó để ngƣời dùng có thể xác định và điều khiển đƣợc dữ liệu thực tế đƣợc lƣu trữ trong bộ nhớ cục bộ tại nút của họ do các file dữ liệu đƣợc mã hoá. Mỗi nút tham gia vào mạng Freenet duy trì hai thành phần chủ yếu. Thành phần thứ nhất là một bộ nhớ lưu trữ cục bộ dùng để đọc ghi dữ liệu. Bộ nhớ cục bộ chính là một phần trong toàn bộ không gian nhớ của nút mà nút đƣa ra dùng chung, nơi mà nút dùng để lƣu trữ các file mà bản thân nó chia sẻ và các file do các nút khác đƣa lên mạng. Mọi file lƣu trữ tại một nút đều đƣợc mã hoá và mỗi file đƣợc lƣu trữ cùng với một khoá tƣơng ứng với nó để hỗ trợ tìm kiếm. Thành phần thứ hai là một bảng định tuyến động, trong đó lƣu trữ các khoản mục có dạng . Mỗi khoản mục định tuyến dạng này lƣu trữ một khoá và con trỏ chứa địa chỉ của nút mà nút đó nghĩ là nút đó đang giữ khoá tƣơng ứng. Bảng định tuyến tại mỗi nút đƣợc sử dụng khi nút đó thực hiện thao tác lƣu trữ file phân tán hay chia sẻ file của bản thân nó hoặc tham gia một yêu cầu tìm kiếm nào đó. Các cơ chế lƣu trữ file phân tán hay thực hiện yêu cầu tại mỗi nút sẽ dựa vào thông tin trong bảng định tuyến của nút để lựa chọn nút tiếp theo để chuyển tiếp thông báo. Do các nút không biết về các thông tin toàn cục nên mỗi nút chỉ đƣa ra đƣợc quyết định định tuyến cục bộ dựa vào các khoản mục này. Freenet sử dụng cơ chế định tuyến dựa trên khoá (key – based routing) và thực hiện tìm kiếm chính xác theo khoá chứ không hỗ trợ tìm kiếm từ khoá (keyword searching) hay tìm kiếm tƣơng tự. Đây là một bƣớc cơ bản trong quá trình hình thành và phát triển của các hệ thống dùng bảng băm phân tán DHT (Distributed Hash Table) [15][20][24]. Dƣới đây ta sẽ thảo luận kỹ lƣỡng hơn về các cơ chế hoạt động chủ yếu của mạng Freenet, bao gồm thủ tục gia nhập mạng của nút mới, thủ tục tìm kiếm dữ liệu và thủ tục lƣu trữ file phân tán hay nút đƣa file mới lên mạng. Đây là những thủ tục cơ bản của Freenet, đƣợc thực hiện bởi một loạt các nút cung tham gia và có quyết định quan trọng tới hiệu năng của hệ thống. Nâng cao hiệu năng của một số hệ thống mạng ngang hàng phi cấu trúc 15 2.1.2. Các thủ tục chính của Freenet Trên thực tế, giao thức của Freenet đã đƣợc [3] mô tả cụ thể và rõ ràng. Để có thể hiểu về mạng Freenet một cách khái quát, phần này chúng ta xem xét những cơ chế quan trọng trong mạng Freenet có liên quan chính đến hiệu năng của hệ thống. Thuật toán gia nhập vào mạng Việc gia nhập vào mạng phát sinh khi có nút mới muốn tham gia vào mạng Freenet. Khi một nút mới muốn gia nhập mạng, nút đó bắt đầu quá trình gia nhập bằng cách gửi một thông cáo tới một số nút mà nó biết. Khi các nút kia nhận đƣợc thông báo, mỗi nút thống nhất với nút mới này về một khoá cụ thể. Khoá đó đƣợc cả hai bên đƣa vào bảng định tuyến tƣơng ứng với nút mới. Lúc đó nút mới đã đƣợc kết nối vào mạng qua một số khoản mục vừa tạo trong bảng định tuyến chứa các khoá đã thống nhất với nút tƣơng ứng. Khi đó thuật toán gia nhập kết thúc. Trong cơ chế gia nhập mạng, một nút mới không có khả năng tự chọn khoá đầu tiên. Lý do của điều này là nếu cho phép tự chọn khoá sẽ tạo điều kiện cho các nút mới tạo ra một khoá hoặc nhiều khoá gần với một khoá cụ thể, làm giảm khả năng tìm đƣợc khoá cụ thể đó và ảnh hƣởng đến toàn hệ thống. Để giảm bớt khả năng một nút mới gia nhập vào mạng gây ảnh hƣởng xấu, thuật toán gia nhập mạng của Freenet chọn cách thống nhất với một nút đã có về một khoá cụ thể nhƣ trên. Cơ chế cho các nút mới gia nhập vào mạng là một một phần rất phức tạp trong giao thức của Freenet. Ngay cả trong [3] – tài liệu cơ sở về mạng Freenet – cũng đề cập chƣa cụ thể về cơ chế này. Trong nghiên cứu này, chúng ta cũng không đi sâu vào vấn đề này mà chỉ nắm bắt nguyên tắc gia nhập mạng của các nút mới để làm cơ sở cho những cải tiến hiệu năng của Freenet. Thủ tục tìm kiếm dữ liệu Khi một nút cần tìm kiếm dữ liệu, nút đó bắt đầu thao tác Request. Để dễ hiểu hơn về thủ tục tìm kiếm của Freenet, dƣới đây ta xem xét một ví dụ minh họa đơn giản trong hình 1. Trong ví dụ này, yêu cầu xuất phát từ nút A với khoá cần tìm là 8. Node A chỉ kết nối với nút B nên (1) A chuyển tiếp yêu cầu tới B. Khi B nhận đƣợc yêu cầu, đầu tiên nó tìm kiếm trong bộ nhớ cục bộ. Khi không thấy khoá cần tìm, B kiểm tra trong bảng định tuyến thấy có khoá 7 gần với khoá 8 nhất và con trỏ tƣơng ứng trỏ tới nút C, (2) nút B chuyển tiếp yêu cầu tới C. Khi C nhận đƣợc yêu cầu, nó tìm trong bộ nhớ cục bộ không có, do vậy (3) C trả về một thông báo quay lui có nội dung không tìm thấy tới B. Khi nút B nhận đƣợc phản hồi không tìm thấy từ C, (4) nút B thử với lựa chọn thứ hai là nút D chứa khoá 10. Đến lƣợt D nhận đƣợc yêu cầu, nó lại tìm trong bộ nhớ Nâng cao hiệu năng của một số hệ thống mạng ngang hàng phi cấu trúc 16 cục bộ nhƣng không thấy nên D kiểm tra bảng định tuyến, thấy khoá 8 cần tìm đang đƣợc lƣu ở nút E. (5) D chuyển tiếp yêu cầu tới E. Nút E nhận đƣợc yêu cầu và thấy nó đang giữ khoá cần tìm nên (6) E trả về dữ liệu cần tìm tới nút D. Nút D chuyển tiếp dữ liệu cho nút B, rồi nút B chuyển tới nút A. Mỗi nút D, B, A đều lƣu lại dữ liệu đã tìm thấy và tạo một khoản mục trong bảng định tuyến tƣơng ứng với khoá 8. Hình 1. Thủ tục tìm kiếm dữ liệu của Freenet Trên đây là một tìm kiếm đơn giản trong mạng Freenet. Để có thể hiểu đầy đủ và toàn diện hơn, sau đây ta xem xét chi tiết về thủ tục định tuyến yêu cầu tìm kiếm trên mạng Freenet. Khi ngƣời dùng cần tìm kiếm một file dữ liệu trên mạng Freenet, ngƣời dùng gửi một yêu cầu tới nút mạng cục bộ của họ, trong đó chứa khoá của file cần tìm. Đầu tiên, nút cục bộ kiểm tra bộ nhớ lƣu trữ cục bộ, nếu tìm thấy, nút đó trả về dữ liệu và kèm theo thông tin nó là nguồn dữ liệu. Nếu bộ nhớ cục bộ không lƣu trữ file, nút đó tìm trong bảng định tuyến một khoá gần nhất với khoá cần tìm về mặt từ điển và gửi một thông báo yêu cầu tới nút tƣơng ứng mà nó nghĩ đang chứa khoá đó với một giá trị Hop To Live (HTL) nhất định. Giá trị này quyết định xem thông báo yêu cầu sẽ đi qua bao nhiêu nút cho đến khi tìm thấy dữ liệu cần tìm. Mỗi nút khi nhận đƣợc một thông báo yêu cầu, nó cũng thực hiện tƣơng tự nhƣ nút xuất phát yêu cầu. Đầu tiên nút đó cũng kiểm tra bộ nhớ cục bộ, nếu không thấy khoá cần tìm, nút đó giảm giá trị HTL của thông báo và lại gửi yêu cầu tới nút có khoá gần nhất trong bảng định tuyến. Nếu cuối cùng, một nút nhận đƣợc thông báo yêu cầu vẫn còn giá trị HTL hợp lệ và tìm thấy file có khoá tƣơng ứng trong bộ nhớ cục bộ của nó, nút đó gửi thông báo chứa dữ liệu ngƣợc về hƣớng nút vừa gửi yêu cầu đến nó. Nâng cao hiệu năng của một số hệ thống mạng ngang hàng phi cấu trúc 17 Mỗi nút trung gian tham gia thao tác tìm kiếm khi nhận đƣợc thông báo chứa dữ liệu sẽ lƣu trữ file vào bộ nhớ cục bộ, đồng thời tạo một khoản mục mới trong bảng định tuyến tƣơng ứng với nguồn dữ liệu thực tế của khoá đƣợc yêu cầu, sau đó lại gửi dữ liệu lên nút trƣớc đó đã gửi yêu cầu, cứ nhƣ vậy đến khi nút đầu tiên tạo ra yêu cầu khoá đó nhận đƣợc dữ liệu. Nút này cũng lƣu file vào bộ nhớ cục bộ và tạo khoản mục tƣơng tự trong bảng định tuyến nhƣng không tiếp tục gửi dữ liệu nữa. Khi đó yêu cầu kết thúc thành công. Nhờ cơ chế sao lặp dữ liệu suốt đƣờng đi từ nút đáp ứng đến nút yêu cầu nên mạng Freenet có tính dƣ thừa rất lớn, do vậy tăng khả năng chịu lỗi. Nếu một nút nhận đƣợc một thông báo yêu cầu mà nó không có dữ liệu cần tìm và hoặc không kết nối với nút nào khác nút mà nó vừa nhận đƣợc thông báo hoặc nếu gửi tiếp sẽ tạo nên vòng lặp, nó sẽ trả về thông báo không còn lựa chọn tìm kiếm. Nút phía trƣớc nhận đƣợc thông báo này sẽ thử gửi thông báo tới nút có khoá gần thứ hai, rồi thứ ba… trong bảng định tuyến. Nếu đã hết khả năng trong bảng định tuyến để thử mà vẫn chƣa tìm thấy, nút đó lại gửi thông báo không còn lựa chọn tìm kiếm đến nút trên của nó. Đến lƣợt nút trên này lại thử các khả năng tiếp theo, cứ nhƣ vậy chừng nào giá trị HTL chƣa tới hạn. Nhƣ vậy Freenet hoạt động theo kiểu tìm kiếm leo đồi chỗ dốc nhất có quay lui (steepest – ascent hill – climbing search with backtracking). Nếu một nút nhận đƣợc thông báo yêu cầu có giá trị HTL đã tới hạn, nó tạo một thông báo thất bại, rồi gửi về nút đã gửi yêu cầu và không thử thêm các nút khác nữa. Để giảm tải mạng trong tình huống có nguy cơ, các nút nhận đƣợc thông báo có thể giảm HTL nhiều hơn mức đƣợc phép hoặc nút có thể huỷ bỏ các yêu cầu sau một thời gian giữ không gian nhớ cho thông báo. Ngoài ra, để phát hiện vòng lặp, mỗi thông báo trên mạng Freenet đƣợc gắn một giá trị định danh giả duy nhất để các nút có thể phát hiện những thông báo nó đã nhận đƣợc trƣớc đó. Trong Freenet ngƣời dùng không truy cập thực tế cục bộ vào bất kỳ dữ liệu nào đã đƣợc mã hoá, điều này khác với mạng Gnutella. Ngƣời dùng cũng không thể yêu cầu thông tin từ các nút cụ thể. Tất cả những gì họ có thể làm là gửi yêu cầu tới các nút láng giềng và đợi phản hồi từ các nút này. Một thao tác tìm kiếm sẽ tạo ra một chuỗi yêu cầu từ nút này qua nút khác theo kiểu proxy. Mỗi nút sẽ tự đƣa ra quyết định định tuyến cục bộ để xác định nút tiếp theo để chuyển tiếp yêu cầu dựa theo các thông tin trong bảng định tuyến của nó. Thủ tục lƣu trữ phân tán Một mục đích quan trọng của Freenet là cho phép các nút lƣu trữ dữ liệu lên mạng. Quá trình lƣu trữ phân tán này đƣợc thực hiện song song với quá trình yêu cầu tìm kiếm dữ liệu, đƣợc hiểu đơn giản là nút đƣa file mới trên mạng với một khoá cụ thể. Để chia sẻ một file hay lƣu trữ file phân tán trên mạng, nút bắt đầu một thao tác Insert và thực hiện yêu cầu lƣu trữ file. Nâng cao hiệu năng của một số hệ thống mạng ngang hàng phi cấu trúc 18 Khi ngƣời dùng muốn lƣu trữ một file lên mạng, đầu tiên họ áp dụng một hàm băm đối với file để tạo ra khoá tƣơng ứng cho file. Sau đó ngƣời dùng gửi một thông báo yêu cầu lƣu trữ phân tán tới nút cục bộ, trong đó chứa khoá và một giá trị HTL. Giá trị HTL trong trƣờng hợp này sẽ xác định số nút sẽ lƣu trữ file với khoá đó. Khi một nút nhận đƣợc thông báo yêu cầu lƣu trữ phân tán với một khoá nhất định, nút đó kiểm tra bộ nhớ lƣu trữ cục bộ xem có khoá đó chƣa. Nếu khoá chƣa đƣợc lƣu trữ, nút đó sẽ tìm trong bảng định tuyến khoản mục chứa khoá gần nhất gửi thông báo yêu cầu lƣu trữ phân tán tới nút tƣơng ứng. Quá trình cứ tiếp tục nhƣ vậy cho đến khi HTL tới hạn hoặc một nút nào đó thấy khoá đã đƣợc lƣu trữ. Nếu một nút nào đó nhận thấy khoá mới trong yêu cầu lƣu trữ đã lƣu trữ tại nó, nút đó gửi thông báo trả lời rằng khoá đã tồn tại trở lại theo đƣờng đi của thông báo yêu cầu lƣu trữ phân tán. Khác với thủ tục yêu cầu, đây là kết quả yêu cầulƣu trữ thất bại. Nút ban đầu yêu cầu lƣu trữ sẽ hiểu là có xung đột với khoá đã đƣa ra. Nếu nút này vẫn muốn lƣu trữ file lên mạng, nó có thể thực hiện lại hàm băm để tạo một khoá khác và thực hiện lại thao tác yêu cầu lƣu trữ phân tán với khoá vừa tạo. Nếu một nút nhận đƣợc thông báo yêu cầu lƣu trữ phân tán có giá trị HTL tới hạn, nút này gửi thông báo không có xung đột dọc theo đƣờng đi của yêu cầu trở lại nút ban đầu. Khi nút ban đầu đề nghị lƣu trữ nhận đƣợc thông báo này, nó hiểu rằng thao tác lƣu trữ với khoá đã chọn có thể đƣợc thực hiện và gửi dữ liệu đi để lƣu trữ. Dữ liệu sẽ đƣợc sao lặp trên đƣờng đi và mỗi nút nhận đƣợc khoá đó sẽ tạo một khoản mục trong bảng định tuyến tƣơng ứng với nút ban đầu đề nghị lƣu trữ là nguồn dữ liệu của khoá mới. Để an toàn hơn, bất kỳ nút nào dọc đƣờng đi đều có thể tự quyết định thay đổi thông báo để đƣa vào rằng nó chính là nguồn dữ liệu. Khi đó yêu cầu lƣu trữ phân tán đƣợc coi là thực hiện thành công. Tƣơng tự thủ tục tìm kiếm, nếu chuyển tiếp tới nút chứa khoá gần nhất không thành công mà giá trị HTL vẫn hợp lệ, nút hiện tại có thể thử các khả năng tiếp theo với các nút tƣơng ứng với khoá gần thứ hai, thứ ba… tƣơng tự nhƣ thủ tục tìm kiếm dữ liệu. Nếu thông báo trở về nút ban đầu mà HTL chƣa tới hạn, nghĩa là số nút liên lạc đƣợc ít hơn so với dự định. Khi đó, nút ban đầu có thể giảm HTL và tạm thời ngƣng chuyển các thông báo yêu cầu lƣu trữ phân tán, và sau một khoảng thời gian nhất định sẽ tiếp tục thực hiện. Cơ chế quản lý không gian nhớ Trong Freenet, mỗi nút có thể cấu hình lƣợng không gian nhớ nhất định dành cho bộ nhớ lƣu trữ cục bộ tham gia vào mạng. Kích thƣớc bộ nhớ này là hữu hạn và tuỳ thuộc vào tài nguyên và quyết định chia sẻ của từng nút. Câu hỏi đặt ra là khi nút nhận đƣợc file mới trong một thao tác tìm kiếm hoặc thao tác lƣu trữ phân tán mà bộ nhớ lƣu trữ cục bộ đầy, nó lựa chọn lƣu trữ hay loại bỏ file mới này? Nâng cao hiệu năng của một số hệ thống mạng ngang hàng phi cấu trúc 19 Trả lời câu hỏi này, Freenet đã đƣa ra cơ chế quản lý không gian nhớ, đƣợc gọi là phƣơng pháp loại bỏ những khoá ít đƣợc sử dụng gần thời điểm đó nhất (gọi tắt là LRU – Least Recently Used). Theo cơ chế LRU, bộ nhớ cục bộ của mỗi nút lƣu trữ các khoản mục dữ liệu theo thứ tự giảm dần thời gian truy cập gần nhất (có thể là thời gian file đƣợc yêu cầu gần nhất hoặc thời gian đƣa vào lƣu trữ mới). Khi một file mới tới trong một thao tác tìm kiếm hoặc lƣu trữ phân tán mà bộ nhớ cục bộ của nút đã đạt kích thƣớc giới hạn, nút đó sẽ xoá các file ít đƣợc sử dụng gần thời điểm đó nhất cho đến khi đủ không gian để lƣu file mới. Sau đó file mới đƣợc lƣu lại và ghi lại thời điểm thao tác để sử dụng trong những lần thay thế lƣu trữ sau. Cơ chế LRU cũng đƣợc áp dụng đối với bảng định tuyến khi bảng định tuyến đầy. Tƣơng tự, khi có khoản mục mới cần đƣa vào bảng định tuyến mà bảng đầy, khoản mục ít sử dụng gần thời điểm đó nhất cũng bị loại bỏ để ghi khoản mục mới. Kích thƣớc của bảng định tuyến đƣợc chọn sao cho khoản mục cho một file sẽ đƣợc lƣu giữ lại lâu hơn thời gian tồn tại của bản thân file trong bộ nhớ lƣu trữ cục bộ. Dù việc thay thế các file lƣu trữ trong bộ nhớ cục bộ và việc thay thế các khoản mục trong bảng định tuyến là những cơ chế tách biệt về logic nhƣng cả hai cơ chế đó đều góp phần quyết định nội dung trong bảng định tuyến. Chính sách thay thế lƣu trữ quyết định các cặp nào đƣợc đƣa vào bảng định tuyến theo cách việc chọn file đƣợc lƣu trữ đi đôi với việc tạo ra các cặp tƣơng ứng với khoá file đó [23]. Mỗi thao tác ghi nhận một khoản mục mới chính là tạo ra một liên kết mới giữa các nút trên mạng, dần dần thay đổi topo của mạng Freenet. Cơ chế lƣu trữ trong bộ nhớ cục bộ và xây dựng bảng định tuyến đóng vai trò quan trọng trong việc cải thiện hiệu quả của các yêu cầu về sau. Đây là mấu chốt quan trọng trong việc áp dụng tƣ tƣởng mô hình thế giới nhỏ để cải thiện hiệu năng của Freenet qua việc thay đổi cơ chế lƣu trữ LRU bằng một cơ chế hiệu quả hơn. Vấn đề này sẽ đƣợc chúng ta thảo luận ở những phần sau của nghiên cứu này. 2.2. Mô hình thế giới nhỏ Nhƣ ta đã biết, để các hệ thống P2P có thể thực hiện đƣợc các chức năng nhƣ truyền thông thông tin, chia sẻ dịch vụ và chia sẻ tài nguyên, chúng phải bằng cách nào đó thoả mãn bốn điều kiện, bao gồm tính phi tập trung, có cấu trúc, tin cậy và có khả năng mở rộng. Tính có cấu trúc ở đây theo ý nghĩa là hệ thống cần có cấu trúc theo một cách nào đó để có thể hỗ trợ tìm kiếm và định tuyến. Các nhà nghiên cứu thấy rằng, bốn điều kiện trên của các hệ thống P2P là những đặc điểm tƣơng tự với các mạng xã hội. Một mạng xã hội vốn đã có phân tán và tính tự tổ chức nhƣng vẫn có cấu trúc. Dù con ngƣời vẫn sinh ra và chết đi, nhiều thuộc tính tổ chức toàn cục của mạng xã hội vẫn ổn định. Hơn nữa, dƣờng nhƣ không có giới hạn về số ngƣời có thể tham gia vào mạng xã hội toàn cầu của chúng ta - tất nhiên chỉ về khía Nâng cao hiệu năng của một số hệ thống mạng ngang hàng phi cấu trúc