Đề tài Giải pháp cân bằng tải sử dụng cấu trúc thư mục cho mạng ngang hàng có cấu trúc

1 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ ĐỖ CAO MINH GIẢI PHÁP CÂN BẰNG TẢI SỬ DỤNG CẤU TRÚC THƯ MỤC CHO MẠNG NGANG HÀNG CÓ CẤU TRÚC LUẬN VĂN THẠC SĨ 2 Hà Nội - 2010 MỤC LỤC……………………………………………………………………. ……... 1 DANH MỤC THUẬT NGỮ………………………………………………….……... 3 DANH MỤC HÌNH VẼ……………………………………………………..……...... 4 MỞ ĐẦU ……………..…………………………….……………………….…………6 CHƯƠNG 1 - TỔNG QUAN VỀ MẠNG NGANG HÀNG………………………...9 1.1 Tổng quan về mạng ngang hàng ......................................................................9 1.1.1 Khái niệm về mạng ngang hàng ..................................................................9 1.1.2 Ưu điểm của mạng ngang hàng .................................................................10 1.1.3 Nhược điểm của mạng ngang hàng............................................................11 1.2 Phân loại mạng ngang hàng............................................................................11 1.2.1 Phân loại theo mức độ tập trung của các node mạng.................................11 1.2.2 Phân loại theo cấu trúc liên kết..................................................................13 1.3 Mạng ngang hàng có cấu trúc dựa trên DHT(Distributed Hash Table) ………………………………….……………………………………………….15 1.3.1 Giới thiệu DHT .........................................................................................15 1.3.2 Mạng chord ...............................................................................................17 a. Mô hình mạng Chord ....................................................................................17 b. Ánh xạ khóa vào một node trong Chord ........................................................19 c. Tìm kiếm trong mạng Chord..........................................................................19 d. Tham gia và ổn định mạng ............................................................................20 1.4 Kết luận............................................................................................................20 CHƯƠNG 2 - CÂN BẰNG TẢI TRÊN MẠNG NGANG HÀNG CÓ CẤU TRÚC…………………………………….…………………………………………..22 2.1 Khái niệm về tải trên mạng ngang hàng ........................................................22 2.1.1 Khái niệm .................................................................................................22 2.1.2 Node quá tải..............................................................................................23 2.1.3 Node có tải cao và Node có tải thấp ..........................................................23 2.2 Các nguyên nhân dẫn đến mất cân bằng tải trên các hệ thống DHT............23 2.2.1 Định danh các node không cân bằng .........................................................23 2.2.2 Định danh dữ liệu không cân bằng ............................................................24 2.2.3 Hot spots...................................................................................................25 2.2.4 Khả năng các node không cân bằng...........................................................26 2.2.5 Nhận xét....................................................................................................26 3 2.3 Các giải pháp cân bằng tải ..............................................................................26 2.3.1 Hướng sử dụng server ảo ..........................................................................27 a. Sử dụng Log(N) Virtual Servers .........................................................................27 b. Phương pháp Proportion ...................................................................................28 c.Phương pháp di chuyển Virtual Server (Transfer)...............................................29 2.3.2 Hướng không sử dụng server ảo ................................................................33 Thuật toán cân bằng tải theo ngưỡng ....................................................................33 2.3.3 Kết luận ....................................................................................................39 CHƯƠNG 3 - ĐỀ XUẤT CẢI TIẾN THUẬT TOÁN CÂN BẰNG TẢI THEO NGƯỠNG ……………………………………...………………………………..40 3.1 Một số khái niệm .............................................................................................41 3.2 Thuật toán ThresholdPlus ..............................................................................41 3.3 Đánh giá:..........................................................................................................46 CHƯƠNG 4 - ĐÁNH GIÁ HIỆU QUẢ CỦA GIẢI PHÁP ĐỀ XUẤT DỰA TRÊN MÔ PHỎNG …………………………………………………...…………………..48 4.1 Ảnh hưởng thời gian sống của một node tới các thuật toán cân bằng tải… .48 4.2 Ảnh hưởng của số lượng các câu truy vấn tới các thuật toán cân bằng tải ..49 4.3 Ảnh hưởng của câu truy vấn dạng Zipf tới các thuật toán cân bằng tải ..…50 4.4 So sánh kết quả thực nghiệm của thuật toán Threshol Plus với các thuật toán đã có: ................................................................................................................51 4.5 Kết luận............................................................................................................52 CHƯƠNG 5 - KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN………………….............54 5.1 Kết luận............................................................................................................54 5.2 Hướng phát triển tiếp theo..............................................................................54 4 THUẬT NGỮ Thuật ngữ Ý nghĩa Based -DHT Dựa trên bảng băm phân tán Broadcast Một thông điệp truyền tới tất cả các trạm Chord Một giao thức dựa trên mang ngang hàng có cấu trúc Client/Server Máy khách/ Máy chủ DHT (Distributed Hash Table ) Bảng băm phân tán Directory Node Thư mục ; Đóng vai trò lưu trữ các thông tin tải của các node Entry Một bản ghi trong bảng dùng để lưu thông tin về các đặc tả tài nguyên tại mỗi node Finger Table Bảng định tuyến Host Ports Node được truy cập với tần số cao Identify Định danh Key Khóa LBM (Load Balancing Matrix) Ma trận cân bằng tải Load Tải Load-balancing Cân bằng tải Node Thực thể có khả năng thực hiện một công việc hữu ích nào đó và trao đổi kết quả với các thực thể khác qua mạng một cách trực tiếp hoặc gián tiếp Overload Quá tải P2P (Peer to Peer network) Mạng ngang hàng Partial query Truy vấn từng phần Predecessor(n) Node đứng liền sau n (Tính theo chiều kim đồng hồ) Query Truy vấn Successor(n) Node đứng liền trước n (Tính theo chiều kim đồng hồ) Target Tải lớn nhất mà một node có thể nhận Unilization Hệ số sử dụng Workload Tải làm việc 5 DANH MỤC HÌNH VẼ Hình 1. Mô hình mạng ngang hàng ............................................................................9 Hình 2. Mô hình mạng ngang hàng thuần tuý............................................................12 Hình 3. Hệ thống mạng ngang hàng lai ghép.............................................................13 Hình 4. Tìm kiếm dữ liệu chia sẻ trong Gnutella.......................................................14 Hình 5. Một mạng Chord với 3 node 0, 1, 3 và các bảng Finger Table ứng với mỗi node. N = 3 bit nên có 3 entry....................................................................................18 Hình 6. Lưu giữ key trong mạng Chord: node 0 lưu key 6, node 1 lưu key 1 và node 3 lưu key 2....................................................................................................................19 Hình 7. Định danh các node không cân bằng ............................................................24 Hình 8. Dữ liệu các node không cân bằng .................................................................24 Hình 9. Kết quả mô phỏng về sự phân bố dữ liệu không đều nhau ............................25 Hình 10. Node Host spots .........................................................................................25 Hình 11.Khả năng các nút không cân bằng ...............................................................26 Hình 12.Cân bằng tải sử dụng Log(N) Virtual Servers ..............................................28 Hình 13. Tạo mới VS (a) và loại bỏ VS (b) ...............................................................29 Hình 14. Node nặng tải di chuyển VS sang node nhẹ tải (nếu chỉ có 1 VS mà vẫn nặng tải thì sẽ chia làm 2 VS để di chuyển)................................................................30 Hình 15. Phương pháp One - to - One.....................................................................31 Hình 16. Phương pháp One - to - Many ..................................................................32 Hình 17. (a) Node A chuyển tải cho node láng riềng B và (b) Chuyển định danh của node C vào giữa A và B. Độ cao của mỗi hình tương ứng là biểu diễn tải của các node. ..................................................................................................................................34 Hình 18. Node A có tải vượt quá ngưỡng. Node B có tải thấp hơn trong hai láng riềng của A. Tải được chuyển từ Node A cho Node B................................................35 Hình 19. Node A có tải vượt quá ngưỡng. Node B có tải thấp hơn trong 2 láng riềng của A. Tải được chuyển cho node B...........................................................................35 Hình 20. Node A có tải vượt quá ngưỡng, node E chuyển tải cho F, E di chuyển vị trí đến giữa A và B để nhận tải .......................................................................................36 Hình 21. Node A có tải vượt quá ngưỡng; Node G là nhẹ tải khi di chuyển không làm cho Successor(G) bị quá tải; di chuyển vị trí của G đến giữa A và B để G chịu tải ..................................................................................................................................38 6 Hình 22. Các node nhẹ tải A và F hỏi successor của nó (các đường mũi tên nét liên) và thông báo tình trạng tải cho thư mục 1 và thư mục 2 (các đường mũi tên nét đứt).43 Hình 23. Node A thực hiện cân bằng tải, node láng riềng B nhận tải hộ node A bằng cách dịch chuyển định danh về phía A .......................................................................44 Hình 24. Node A thực hiện cân bằng tải, node A chia tải cho node láng giềng B bằng cách dịch chuyển định danh của A về phía B. ............................................................44 Hình 25. Node A hỏi thư mục 1 để tìm một node nhẹ tải có thể dịch chuyển được (đường mũi tên nét liên). Định danh của node nhẹ tải E được chuyển đến giữa predecessor(A) và A để nhận tải hộ node A (đường mũi tên nét đứt). ........................45 Hình 26. Thời gian sống trung bình của một node thay đổi, các câu truy vấn thực hiện với phân bố Zipf và Uniform. ....................................................................................49 Hình 27. Số câu truy vấn đặt vào một node thay đổi, truy vấn được phân bố ở dạng Zipf và Uniform.........................................................................................................50 Hình 28. Truy vấn đặt vào các node ở dạng phân bố Zipf với tỷ lệ thay đổi. ............51 Hình 29. So sánh ThresholdPlus với Tranfer và Propotion. ......................................52 7 MỞ ĐẦU Một kiểu kiến trúc mạng mới với tên là mạng ngang hàng (Peer to Peer - P2P) đã phát triển nhanh chóng trên internet. Trong đó hoạt động của mạng chủ yếu dựa vào khả năng tính toán và băng thông của các máy tham gia chứ không tập trung vào một số nhỏ các máy chủ trung tâm như các mạng thông thường. Sự phát triển nhanh chóng của mạng ngang hàng trong những năm gần đây thúc đẩy sự ra đời của nhiều ứng dụng mạng như các hệ thống chia sẻ file, tìm kiếm thông tin, tính toán lưới… Mạng ngang hàng có cấu trúc ra đời đảm bảo cho tính hiệu quả cũng như khả năng mở rộng của các ứng dụng này. Tuy nhiên, để đảm bảo chất lượng dịch vụ cho các ứng dụng xây dựng trên mạng ngang hàng có cấu trúc cần phải giải quyết vấn đề cân bằng tải trong mạng ngang hàng có cấu trúc. Có hai hướng tiếp cận chính cho các thuật toán cân bằng tải đó là: hướng tiếp cận dựa trên server ảo (virtual server) và hướng tiếp cận không dựa trên server ảo. Trong luận văn này tôi tập trung vào hướng tiếp cận không dựa trên server ảo và đưa ra một giải thuật cải tiến của giải thuật cân bằng tải theo ngưỡng. Giải thuật của chúng tôi đưa ra cho phép các node quá tải tìm chính xác và nhanh chóng một node phù hợp để thực hiện việc cân bằng tải. Chúng tôi đã cài đặt và thử nghiệm thuật toán đề xuất trong điều kiện mạng gần với thực tế và thấy rằng thuật toán của chúng tôi giải quyết tốt vấn đề cân bằng tải của các node trong mạng. Nội dung luận văn gồm 5 chương cụ thể cho từng chương như sau: Chương 1: Giới thiệu tổng quan về mạng ngang hàng, những khái niệm cơ bản về mạng ngang hàng đồng thời giới thiệu giao thức Chord, giao thức được sử dụng để triển khai mạng phủ DHT khi xây dựng chương trình mô phỏng. Chương 2: Tìm hiểu về vấn đề cân bằng tải trên mạng ngang hàng, một số nguyên nhân dẫn đến mất cân bằng tải, các giải pháp đã được đề xuất và phân tích về các giải pháp này. 8 Chương 3: Trên cơ sở các vấn đề tìm hiểu được ở chương 2. Chúng tôi đề xuất giải pháp cân bằng trên mạng ngang hàng có cấu trúc theo hướng không sử dụng server ảo. Đó là một giải thuật cải tiến của giải thuật cân bằng tải theo ngưỡng. Chương 4: Trình bày cách thực hiện chương trình mô phỏng đồng thời trình bày kết quả đánh giá giải thuật cân bằng tải dựa trên mô phỏng của chúng tôi. Chương 5: Trình bày các công việc mà chúng tôi đã thực hiện được, những vấn đề còn tồn tại của luận văn và hướng phát triển tiếp theo của chúng tôi. 9 CHƯƠNG 1 - TỔNG QUAN VỀ MẠNG NGANG HÀNG Trong chương này, luận văn sẽ giới thiệu khái quát về mạng ngang hàng, các đặc điểm, các hình thức phân loại của mạng ngang hàng, khái niệm về DHT và mạng hàng có cấu trúc đồng thời giới thiệu về một số mạng ngang hàng đã và đang được ứng dụng có hiệu quả. 1.1 Tổng quan về mạng ngang hàng 1.1.1 Khái niệm về mạng ngang hàng Mạng ngang hàng là một mạng mà kiến trúc của nó được tạo nên bởi các máy tính liên kết với nhau, các máy tính tham gia trong mạng đều bình đẳng như nhau và được gọi là các peer, mỗi máy tính tham gia mạng là một phần và duy trì sự tồn tại của mạng. Các máy tính trong mạng thường xuyên liên lạc với các máy tính khác để ổn định mạng và chia sẻ dữ liệu với nhau. Dữ liệu được chứa trên các máy tính và được chia sẻ trực tiếp với nhau giữa các máy tính tham gia vào mạng. Hình 1. Mô hình mạng ngang hàng 10 Ứng dụng thường xuyên gặp nhất của mạng ngang hàng là chia sẻ tệp tin, tất cả các dạng như: âm thanh, hình ảnh, dữ liệu.. hoặc để truyền dữ liệu thời gian thực… . Việc sử dụng mạng ngang hàng mang lại nhiều ưu điểm cho người dùng . Luận văn xin trình bày một số ưu điểm của mạng ngang hàng. 1.1.2 Ưu điểm của mạng ngang hàng Mục đích quan trọng của mạng ngang hàng là các máy tính tham gia mạng đều đóng góp tài nguyên bao gồm băng thông, lưu trữ, khả năng tính toán. Do đó khi càng nhiều mày tính tham gia mạng thì khả năng tổng thể của mạng càng lớn. Do việc các thông tin lưu trữ không chỉ trên máy chủ mà còn được lưu trữ ở chính các máy tham gia mạng nên mô hình này rất phù hợp với tính phi tập trung của Internet. Xét về khía cạnh sức mạnh xử lý, mạng ngang hàng có khả năng xử lý cao hơn cả những máy chủ lớn hiện nay, do đó sử dụng mạng ngang hàng có thể cải thiện đáng kể hiệu quả của các phương pháp phân tích, xử lý dữ liệu và giải các bài toán phức tạp. Sở dĩ làm được như vậy là vì mạng ngang hàng có thể tận dụng được khả năng xử lý, khả năng lưu trữ còn thừa của các máy tham gia mạng với những thuật toán phân tán hợp lý. Công nghệ này đã chia việc xử lý lớn ra thành nhiều việc xử lý để có thể giao cho các máy tính khác trong mạng cùng thực hiện. Mỗi máy tính sẽ xử lý một phần công việc và trả về kết quả xử lý cho máy tính trung tâm, máy tính trung tâm sẽ ghép nối các kết quả này lại với nhau. Bằng cách như vậy, ta có thể giải quyết các bài toán phức tạp yêu cầu vấn đề xử lý, lưu trữ lớn mà không cần phải nâng cấp khả năng xử lý của hệ thống hiện tại. Tính chất phân tán của mạng ngang hàng cũng giúp cho việc phân tán trách nhiệm cung cấp dịch vụ đến tất cả các node trên mạng, nó sẽ loại bỏ được vấn đề ngừng trệ dịch vụ do nơi cung cấp duy nhất gặp sự cố. Đối với mô hình tập trung, chỉ cần máy chủ gặp sự cố thì cả hệ thống sẽ ngưng trệ. Còn đối với mạng ngang hàng, máy tính có thể tham gia hoặc rời khỏi mạng bất kỳ lúc nào mà mạng vẫn hoạt động bình thường, các máy tính còn lại vẫn có thể trao đổi thông tin và chia sẻ tài nguyên cho nhau. Bên cạnh nhiều ưu điểm đã được nêu ở trên thì mạng ngang hàng cũng còn tồn tại một số nhược điểm 11 1.1.3 Nhược điểm của mạng ngang hàng Do các máy tính trên mạng ngang hàng đều có vai trò như nhau và không tuân theo bất cứ một quy luật định tuyến hay kết nối nào, việc yêu cầu dịch vụ được đáp ứng tuỳ biến nên máy yêu cầu dịch vụ có thể nhận được nhiều kết quả khác nhau, khi nó kết nối đến nhiều máy tính khác nhau cùng cung cấp một dịch vụ. Các yêu cầu gửi đi có thể không nhận được kết quả trả về vì không có gì đảm bảo sẽ tồn tại một máy nào đó có khả năng đáp ứng yêu cầu đó. Do đặc điểm là các node có thể rời mạng bất kì lúc nào nên có thể bị ngắt kết nối tới các node này bất cứ thời điểm nào. 1.2 Phân loại mạng ngang hàng Mạng ngang hàng có nhiều tiêu trí phân loại khác nhau, trong luận văn này xin được trình bày hai tiêu trí phân loại mạng ngang hàng đó là: Phân loại theo mức độ tập trung của các node mạng và phân loại theo cấu trúc liên kết của các node. 1.2.1 Phân loại theo mức độ tập trung của các node mạng Nếu lấy tiêu chí về mức độ tập trung của các node mạng, mạng ngang hàng có thể phân làm 2 loại: mạng ngang hàng thuần tuý và mạng ngang hàng lai a. Mạng ngang hàng thuần tuý Trong mạng ngang hàng thuần tuý thì vai trò của các máy trong mạng là ngang nhau và trong mô hình mạng này đã loại bỏ sự tồn tại của các máy chủ tập trung. Trong mạng này đã khắc phục được vấn đề node nghẽn cổ chai trong mô hình tập trung. Tuy nhiên vấn đề tìm kiếm trong mạng ngang hàng thuần tuý sử dụng cơ chế phát tràn (Flooding), yêu cầu tìm kiếm được gửi tới tất cả các node mạng là láng giềng với nó, điều này làm tăng đáng kể lưu lượng trong mạng. 12 Hình 2. Mô hình mạng ngang hàng thuần tuý b. Mạng ngang hàng lai ghép Trong mô hình này, các peer lưu giữ nội dung chia sẻ với các node khác ở trên mạng. Tất cả các peer đều kết nối tới một server, server này lưu giữ thông tin về: - Bảng thông tin kết nối của người dùng đăng kí (địa chỉ IP, băng thông kết nối…) - Bảng liệt kê danh sách các file mà các peer nắm giữ và chia sẻ ở trên mạng cùng với các thông tin mô tả về các files ( tên file, ngày tạo…) Tất cả các peer muốn kết nối vào mạng đều phải liên lạc với server và thông báo với server các file mà nó có. Một peer mà muốn tìm kiềm một file, yêu cầu tìm kiếm được chuyển cho server, server tìm kiếm trong thông tin chỉ mục của mình và trả lại danh sách các peer có thông tin cần tìm. Peer tìm kiếm sẽ liên lạc trực tiếp với các peer có thông tin theo yêu cầu tìm kiếm để tải thông tin trực tiếp từ các peer này. 13 Hình 3. Hệ thống mạng ngang hàng lai ghép 1.2.2 Phân loại theo cấu trúc liên kết Mạng phủ bao gồm tất cả các node mạng đại diện cho các máy tham gia và các liên kết giữa các node mạng này. Một liên kết tồn tại giữa hai node mạng khi một node mạng biết vị trí của node mạng kia. Dựa vào cấu trúc liên kết trong mạng phủ người ta có thể phân loại mạng ngang hàng thành hai loại: mạng ngang hàng không có cấu trúc và mạng ngang hàng có cấu trúc. a. Mạng ngang hàng