Khóa luận Xây dựng ứng dụng tính toán phân tán trên nền tảng sức mạnh các máy tính cá nhân

ĐẠI HỌC QUỐC GIA HÀ NÔI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Nguyễn Chí Công XÂY DỰNG ỨNG DỤNG TÍNH TOÁN PHÂN TÁN TRÊN NỀN TẢNG SỨC MẠNH CÁC MÁY TÍNH CÁ NHÂN KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công Nghệ Thông Tin HÀ NỘI -2010 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Nguyễn Chí Công XÂY DỰNG ỨNG DỤNG TÍNH TOÁN PHÂN TÁN TRÊN NỀN TẢNG SỨC MẠNH CÁC MÁY TÍNH CÁ NHÂN KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công Nghệ Thông Tin Cán bộ hướng dẫn: ThS. Đào Minh Thu HÀ NỘI - 2010 Tóm tắt nội dung Tính toán phân tán là một công nghệ mới và rất thiết thực hiên nay. Những hệ thống tính toán phân tán giúp giải quyết những bài toán khoa học lớn mà một máy tính không thể giải quyết được. Ngày nay có khá nhiều middleware phục vụ cho việc xây dựng hệ thống tính toán phân tán. Trong khóa luận này trình bày một số nghiên cứu về tính toán phân tán, những nghiên cứu về kiến trúc, cách thức hoạt động của một số hệ thống tính toán phân tán phổ biến, giới thiệu một số dự án tính toán khoa học đang được thực thi nhờ hệ thống tính toán phân tán. Khóa luận này cũng trình bày bước đầu xây dựng một hệ thống tính toán phân tán, với phần mềm bên phía người dùng được tích hợp vào ứng dụng facebook. Người dùng không cần cài đặt một phần mềm client nào, mà chỉ cần có một trình duyệt web là có thể tham gia vào những dự án tính toán. Việc này sẽ tạo điều kiện mở rộng dự án tính toán được dễ dàng hơn, làm tăng hiệu suất của những hệ thống tính toán phân tán. Mục lục Danh mục các hình vẽ Hình 2.1: Kiến trúc hệ thống BOINC 10 Hình 2.1: Kiến trúc hệ thống Condor 15 Hình 2.3: Kiến trúc hệ thống Globus Toolkit 17 Hình 3.1: Kiến trúc tổng thể hệ thống 22 Hình 3.2: Kiến trúc chi tiết hệ thống 24 Hình 3.3: Mô hình kết nối TCP/IP của hệ thống 26 Hình 4.1: Hình ảnh mô tả phân chia task tới những máy tính Node 47 Hình 4.2: Biểu đồ thời gian thực thi khi có một máy tính 47 Hình 4.3: Biểu đồi thời gian thực thi khi có ba máy tính 48 Chương I – Giới thiệu Đặt vấn đề Khi khoa học phát triển đặt ra nhiều bài toán với khối lượng tính toán lớn, cùng với một lượng lớn dữ liệu cần xử lý. Trong nhiều ngành khoa học khác nhau những bài toán này đang tồn tại và chúng ta luôn muốn xử lý chúng. Trong thiên văn học có một điều mà chúng ta luôn muốn khám phá đó là “liệu có một nền văn minh nào ngoài trái đất không?”, đây là một câu hỏi lớn mà nhiều năm qua con người vẫn chưa tìm được lời giải đáp thỏa đáng. Với khoa học kỹ thuật như hiện nay chúng ta có thể thu được những tín hiệu từ bên ngoài trái đất, chúng ta có thể xử lý những tín hiệu này để hy vọng có thể tìm ra một nền văn minh nào đó bên ngoài trái đất. Nhưng những tín hiệu thu được ngoài trái đất rất nhiều, nếu dùng một máy tính có công suất tính toán lớn cũng phái mất rất nhiều thời gian để xử lý lượng tín hiệu này, như vậy sẽ rất lâu chúng ta mới có thể tìm được câu trả lời cho câu hỏi kia. Trong ngành công nghệ thông tin có một bài toán quen thuộc đó là bài toán phá mã. Một phương pháp phá mã đơn giản nhất là duyệt toàn bộ, ta thử lần lượt tất cả trường hợp có thể của khóa cho đến khi tìm được khóa đúng. Độ dài của khóa sẽ quyết định đến số lượng các phép thử, ví dụ với hệ mã hóa DES sử dụng 56 bit làm khóa, tức là sẽ có 256 = 72x1016 giá trị có thể của khóa. Nếu sử dụng một máy tính bình thường có tốc độ tính toán 1 giải mã /μs sẽ phải mất khoảng 1142 năm, thời gian này là quá lâu so với tuổi thọ của thông tin. Muốn phá mã nhanh có thể dùng một máy tính chuyên dụng (giá khoảng 250.000$) có thể phá mã trong 3 ngày. Nhưng đó là trường hợp sử dụng 56 bit làm khóa, nếu sử dụng khóa với độ dài 128 bit hay 126 bit thì máy tính đó cũng tỏ ra không hiệu quả. Trong y học cũng có nhiều dự án với khối lượng tính toán lớn, dự án “Help Defeat Cancer [10]” là một dự án nghiên cứu khả năng chống căn bệnh ung thư. Với dự án này, các nhà nghiên cứu cần phân tích số lượng lớn mô ung thư cùng một lúc, nếu dùng một máy tính thông thường mất khoảng 168 năm, như vậy là quá lâu vì chúng ta cần tìm ra phương pháp trị bệnh ung thư càng sớm càng tốt. Trong nhiều ngành khoa học khác như toán học, sinh học … cũng có nhiều bài toán lớn được đặt ra, việc giải quyết những bài toàn này giúp phát triển các ngành khoa học phục vụ cuộc sống, Vì vậy nhu cầu giải quyết những bài toán như thế là rất thiết thực Ngày nay mạng máy tính phát triển mạnh, nhất là mạng Internet với hàng triệu máy tính kết nối với nhau. Đối với người dùng bình thường công suất tính toán của máy tính thường không được sử dụng hết. Trong những khoảng thời gian máy tính nhàn rỗi, khả năng tính toán của nó không được tận dụng. Vậy tại sao ta không sử dụng khả năng tính toán đó để giải quyết những bài toán phức tạp trên? Mỗi máy tính khi nhàn rỗi có thể sử dụng để tính toán một phần nhỏ của bài toán, nhiều máy tính cùng tham gia tính toán sẽ tao lên một hệ thống tính toán hết sức mạnh mẽ. Nếu chúng ta có thể kết nối hàng triệu máy tính trên Internet, chúng ta sẽ tạo ra một mạng lưới tính toán khổng lồ, khi đó những bài toán lớn có thể được giải quết trong thời gian ngắn. Để mọi người tham gia tính toán cho một dự án nào đó, họ cần biết về dự án đó, và biết cách để có thể sử dụng máy tính của mình tham gia vào hệ thống tính toán. Vì vậy ta cần quảng bá cho người dùng biết về những dụ án tính toán, và cung cấp cho họ những công cụ để tham gia vào hệ thống tính toán. Mạng xã hội ngày nay rất phát triển, Facebook là một mạng xã hội có lượng người dùng lớn nhất hiên nay. Nó có thể là một nơi lý tưởng để quảng bá thông tin về những dự án tính toán. Trên Facebook bạn có thể giao lưu, liên lạc với bàn bè, với rất nhiều người cùng tham gia Facebook. Khi một người dùng Facebook tham gia vào một dự án tính toán, họ có thể giới thiệu cho bạn bè, người thân hay một ai đó mà họ quen biết trên Facebook. Những dự án tính toán thường là những dự án có ích cho xã hội nên mọi người sẽ rất sẵn lòng tham gia vào dự án tính toán. Một vấn đề có thể khiến mọi người ngại tham gia vào hệ thống tính toán đó là các hệ thống tính toán hiện nay, thường bắt người dùng phải cài một phần mền lên máy của mình để tham gia vào việc tính toán. Bất kỳ một máy tính nào muốn tham gia vào hệ thống tính toán cũng cần cài đặt phần mềm này. Vậy nếu có thể xây dựng một hệ thống tính toán phân tán, mà người dùng không cần cài đặt phần mền vẫn có thể tham gia vao hệ thống sẽ giúp khả năng huy động được lượng người dùng lớn, tình nguyện tham gia vào dự án tính toán. Web là một một công cụ rất hữu ích cho chúng ta, nó thực sự đã thay đổi cuộc sống của chúng ta. Một trang web với một chương trình applet có thể thay thế cho phần mềm tham gia vào hệ thống tính toán. Khi người dùng truy cập vào trang web, chương trình applet sẽ chạy và thực thi việc tính toán. Chúng ta có thể vào web ở bất kỳ máy tính nào có kết nối mạng Internet, và ngay lập tức có thể tham gia vào công việc tính toán. Tích hợp trang web đó vào một ứng dụng Facebook sẽ tạo thành một công cụ tuyệt vời để phát triển các dự án tính toán. Theo thông kê mới nhất của Nielsen (một công ty khảo sát thị trường) cho thấy Facebook là địa chỉ gây tốn thời gian nhất của người dùng trên Web. Người dùng Facebook cũng bỏ thời gian lên mạng gấp 3 lần so với người không tham gia mạng lưới giao tiếp xã hội này. Một ứng dụng Facebook có thể sử dụng như những phần mềm tham gia vào hệ thống tính toán phân tán, đó sẽ là một phướng án tốt để mở rộng hệ thống tính toán phân tán, tăng số người tham gia vào hệ thống, từ đó tăng khả năng tính toán Nội dung khóa luận Trong khóa luận này chúng tôi trình bày một số nghiên cứu về các hệ thống tính toán phân tán, các Middleware phổ biến dùng trong các hệ thống tính toán phân tán. Bước đầu triển khai một hệ thống tính toán phân tán, với một ứng dụng Facebook được sử dụng để người dùng có thể tham gia vào hệ thống tính toán. Nội dung chi tiết khóa luận gồm 5 chương: Chương I: Giới thiệu về khóa luận, đặt ra vấn đề cần giải quyết trong khóa luận. Chương II: Giới thiệu một số hệ thống tính toán phân tán, kiến trúc của hệ thống và đưa ra những so sánh. Ba hệ thống được giới thiệu là BOINC, Condor, Globus đây là 3 hệ thống phổ biến hiện nay. Chương III: Trình bày kiến trúc hệ thống tính toán phân tán sử dụng ứng dụng Facebook thay thế cho phần mềm . Chương IV: Trình bày cách cài đặt chương trình, triển khai một số ứng dụng tính toán phân tán trên hệ thống và kết quả. Chương V: Tổng kết, nhận xét về hệ thống, những thành quả đã đạt được và những kế hoạch phát triển của dự án. Chương II: Các hệ thống tính toán phân tán 2.1 BOINC 2.1.1: Giới thiệu BOINC [8] viết tắt của Berkeley Open Infrastructure for Network Computing (Cơ sở hạ tầng mã nguồn mở cho tính toán mạng) là một phần mềm trung gian cho việc tính toán tình nguyện và tính toán lưới. Ban đầu BOINC được xây dựng để phục vụ dự án SETI@home, một dự án tìm kiếm tín hiệu ngoài trái đất. Sau đó nó trở lên phổ biến và được sử dụng cho nhiều dự án tính toán khác nhau trong nhiều lĩnh vực như toán học, y học, sinh hoc… BOINC là một phần mềm mã nguồn mở, vì vậy những nhà phát triển có thể tải mã ngồn về để cấu hình và cài đặt theo ý muốn. 2.1.2: Kiến trúc BOINC Hệ thống BOINC gồm có 2 thành phần chính là hệ thống Server và phần mềm (Hình 2.1) Server Thành phần chính của BOINC là Backend Server, server có thể chạy trên một hoặc nhiều máy tính khác nhau, điều này giúp cho hệ thống BOINC dễ dàng mở rộng quy mô của dự án. BOINC Server chạy trên nền tàng hệ điều hành Linux và sử dụng APACHE, PHP và MySQL làm nền tảng cho hệ thống web và cơ sở dữ liệu. Các ứng dụng tính toán chạy trên máy tính thành viên, kết quả được gưi lên cơ sở dữ liệu của ứng dụng tính toán, tại đây nó sẽ được xử lý. Trước khi kết quả được gửi lên cơ sở dữ liệu của ứng dụng tính toán, nó được kiểm tra tính đúng đắn bởi Server Backend. Server Backend kiểm tra tính đúng đắn của kết quả bằng cách gửi các workunit tới nhiều máy khác nhau, và so sánh kết quả nhận được của một workunit khác nhau. Workunit là một khối lượng tính toán nhỏ của bài toán, được thực hiện trên máy tính . Một workunit gồm nhiều Task, Result là kết quả của một task, Server sẽ tự động tạo ra những tập kết quả tương ứng với các workunit khi workunit được tạo (không phải là result thật, mà chỉ là một thể hiện của kết quả), các result này được lưu vào cơ sở dữ liệu, khi một task hoàn thành và gửi kết quả lên server, result tương ứng trong cơ sở dữ liệu của server sẽ được đánh đấu là đã hoàn thành. Khi tập tất cả result của một workunit được đánh dấu, workunit đó được báo là đã hoàn thành BOINC server cung cấp một vài tính năng như: + Validator: Chức năng này kiểm tra kết quả gửi về từ có chính xác hay không. Một workunit được gửi tới nhiều máy cùng thực thi, kết quả gửi về từ những máy đó được server so sánh, kết quả có tỉ lệ cao nhất được coi là kết quả đúng. + Homogeneous redundancy: Chức năng này sẽ chỉ gửi một workunit tới những máy tính có cùng cùng một platform (cùng hệ điều hành…), điều này sẽ giúp quá trình validator được dễ dàng và chính xác hơn. +  Workunit trickling: Gửi các thông tin tới server trước khi các workunit hoàn thành, điều này giúp cho việc đánh giá để có thể gủi một workunit mới kịp thời, giúp cho việc tính toán nhanh hơn, giảm tối thiểu thời gian nhàn rỗi của máy . + Locality Scheduling: Chỉ gủi các workunit(không gửi các file cần thiết) tới các máy đã có các file cần thiết để nhanh chóng thực thi workunit. + Phân phối các workunit dựa vào các tham số của máy : Chức năng này đảm bảo việc gửi workunit tới những máy tính có khả năng thực thi workunit đó. BOINC server bao gồm 2 chương trình CGI và thường có 5 deamons. - Một chương trình CGI lập lịch xử lý các yêu cầu từ phía , nhận các workunit đã hoàn thành và gửi đi những workunit mới. - Một chương trình CGI xử lý việc upload file. - 5 deamons: + Feeder + Validator + Assimilator + File_deleter + Transitioner Sheduling Server DATA Server Web interfaces BOINC DB Core Client Project back end BOINC Server Complex Application Client Client API Server Client Project Specific component BOINC components Hình 2.1 Kiến trúc hệ thống BOINC Một workunit được chia thành nhiều task, mỗi task tương ứng với một result trong cơ sở dữ liệu, khi task hoàn thành gửi về server, result tương ứng được đánh dấu đã hoàn thành. Một deamons Feeder có trách nhiệm đọc các task trong cơ sở dữ liệu và lưu chúng trong các khối nhớ, bộ lập lịch sẽ đọc các task trong khối nhớ và gửi chúng tới , Feeder sẽ định kỳ là rỗng các khe trong khối nhớ sau khi task được gửi đi. Khi các result của một workunit được thực hiện xong và gửi về server, deamon Validator sẽ tiến hành so sánh chúng, Validator có thể được viết bởi người phát triển ứng dụng để đặt ra những thuật toán so sánh, hay những hàm đánh giá các kết quả, hoặc đơn giản là so sánh các bit. Nếu các kết quả trùng nhau nó sẽ được coi là hợp lệ và được sử dụng làm kết quả của workunit. Tiếp đó deamon Assimilator thực hiện việc xử lý các kết quả hợp lệ dựa trên code của dự án, việc xử lý này là phụ thuộc vào từng dự án, có dự án cần phân tích các file kết quả và lưu chúng vào cơ sở dữ liệu, hoắc đơn giản chỉ là copy từ nới này sang nơi khác. Deamon File_deleter có nhiệm vụ xóa những output đã được xử lý bởi Assimilator và các file input không cần thiết. Deamon Transitioner xử lý việc chuyển trạng thái của workunit và result, nó cũng tạo ra các result từ workunit khi chúng được tạo ra, hay tạo thêm những result nếu cần thiết(cho những trường hợp result không thoa mãn trong quá trình validator hoặc không gửi được lên server). BOINC Client BOINC Client là một kết cấu gồm một số ứng dụng độc lập, chúng sử dụng cơ chế BOINC remote procedure call (thủ tục gọi điều khiển từ xa của BOINC) để liên lạc với nhau. Những thành phần ứng dụng gồm có: + Chương trình BOINC , đây là một chương trình đóng vai trò là lõi của , nó có những tính năng và thực hiện những nhiệm vụ sau: Tạo và duy trì kết nối giữa và server Tải về những ứng dụng khoa học, cung cấp một cơ chế đăng nhập thống nhất để đảm nảo rằng các ứng dụng khoa học được cập nhật, lập lịch sử dụng tài nguyên CPU của các ứng dụng khoa học. BOINC chạy trên Unix như một chương trình deamon. Trên Windows, ban đầu BOINC không phải là một dịch vụ danh cho Windows mà chỉ là một ứng dụng bình thường. sau này có một vài phiên bản dành cho windows và nó là một tùy chọn trong quá trình cài đặt. Phụ thuộc vào cách cài đăt BOINC nó có thể là một chương trình chạy nền hoặc được chạy khi người dùng khởi động máy. + Một hoặc một vài ứng dụng khoa học: Những ứng dụng khoa học này thực hiện việc tính toán các bài toán khoa học, những ứng dụng này là đặc trưng cho từng dự án tính toán phân tán. Những ứng dụng khoa học sử dụng BOINC deamon để tải về và gửi đi những workunit, hay để trao đổi những thông tin thống kê với server. + Một boincmgr (boincmgr.exe): là một giao diện tương tác với lõi của ứng dụng(core ) sử dụng remote procedure call. Mặc định core chỉ cho phép kết nối từ cùng một máy tính, nhưng nó có thể cấu hình để có thể kết nối từ những máy tính khác. + BOINC screensaver: cung cấp một framework nhờ đó các ứng dụng khoa học có thể hiển thị hình ảnh trên cửa sổ screensaver của người dùng. Thông thường BOINC screensaver hiển thị những hoạt ảnh thể hiện chi tiết của ứng dụng khoa học, hoặc những biểu đồ hay những đồ thị thể hiện việc tính toán. 2.1.3 Một số dự án đang thực hiện bởi BOINC SETI@Home: SETI@Home [8] là một thí nghiệm khoa học, sử dụng những máy tính kết nối trên Internet để tìm kiếm nền văn minh ngoài trái đất. Đây là một phần của dự án SERENDIP (Search for Extraterrestrial Radio Emissions from Nearby Developed Intelligent Populations) của đại học California, Berkeley. Đài thiên văn Arecibo thu thập những tin hiệu trên không trung, sau đó những tín hiệu này được gửi tới những máy tính tham gia vào dự án để tính toán và phân tích. Các kết quả được trả lại server của dự án. Để tham gia vào dự án, người dùng phải tải về và cài đặt phần mềm tính toán trên máy của mình, mỗi khi máy tính rỗi, phần mềm sẽ tự động tải về một lượng dữ liệu (khoảng 300KB) và tiến hành tính toán. Thông tin chi tiết về dự án có tại trang chủ của dự án ABC@Home: ABC@Home [7] là một dự án toán học nhằm tìm ra bộ 3 số a,b và c để chứng minh cho giả thuyết về bộ 3 số ABC (ABC conjecture), giả thuyết 3 số ABC nêu lên rằng, chỉ tồn tại duy nhất 3 số a,b và c sao cho log(c) / log(rad(a * b * c)) > h với h là một số thực lớn hơn 1. Ba số a,b,c thỏa mãn điều kiện trên khi nó thỏa mãn những điều kiện sau + a + b = c + a<b<c + a,b,c không có ước số chung + c > rad(a * b * c) Việc chứng minh được giả thuyết ABC sẽ giúp giải đáp nhiều câu hỏi trong toán học. dự án đang được thực hiện bởi trường đại học Leiden, thông tin về dự án có trên trang chủ 2.2: Condor 2.2.1 Giới thiệu Condor là kết quả của một dự án nghiên cứu trong trường đại học Wisconsin-Mandison, Condor là một hệ thống quản lý, lập lịch cho những công việc cần tính toán lớn, người dùng gửi công việc của họ lên Condor, Condor lưu chúng trong hàng đợi của nó, lựa chon nơi nào, khi nào sẽ thực thi công việc đó, và báo cho người dùng kết quả khi hoàn thành. Khác với những hệ thống cổ điển, Condor không đòi hỏi cần có những máy móc chuyên dụng, Condor sẽ gửi những công việc (jobs) tới những máy phù hợp với yêu cầu của công việc đó. 2.2.2 Kiến trúc Hệ thống Condor [1] gồm 3 thành phần chính: Central Manager, Submit Machine, Execution Machine (Hinh 2.2). Central Manager Central Manger có nhiệm vụ thu thập những nguồn tài nguyên, và những thông tin về tất cả các máy tính tham gia vào mạng lưới tính toán, và đưa ra những chính sánh hoạt động chung cho cả mạng lưới, Dựa vào những thông tin này, một job sẽ được gửi tới những máy có tài nguyên phù hợp với yếu cầu tính toán của nó. Những deamon chính chạy trên Central Manager. Condor_collector: Deamon này chịu trách nhiệm thu thập thông tin về trạng thái của những máy tính tham gia vào Condor Pool(một tập hợp máy tính tham gia vào hệ thống phân tán). Tất cả những deamons khác định kỳ gửi ClassAd tới collector. ClassAd là những bản ghi về tài nguyên cần thiết của một job cũng như tài nguyên có của những máy tham gia vào mạng lưới, điều này giúp cho việc gửi job tới đúng những máy có thể thực thi chúng. Condor_collector có thể coi như một cơ sở dữ liệu động của ClassAd. Lệnh condor_status có thể dùng để truy vấn tới collector về những thông tin của hệ thống Condor. Những deamon khác cũng có thể truy vấn tới collector để lấy những thông tin quan trọng như địa chỉ sử dụng để gửi lệnh tới những máy tính ở xa. Condor_negotiator: Deamon này chịu trách nhiệm tạo ra tất cả những kết nối trong hệ thống Condor. Nó cũng có trách nhiệm quản lý quyền ưu tiên của những người dùng trong hệ thống. Submit Machine Submit Machine cho phép người dùng gửi những job tới một hàng đợi ảo ở trên máy cục bộ (scheduler). Scheduler sẽ đàm phán với Central Manage để yêu cầu Central Manager cấp cho những tài nguyên cần thiết cho việc thực thi job. Khi có một tài nguyên được cấp cho job, Scheduler sẽ gọi chương trình deamon Shadow, chương trình này chịu trách nhiệm quản lý việc thực thi job đó, đồng thời thực thi những công việc như: kiểm tra trạng thái hoàn thành, lập lịch lại trong các trường hợp job bị lỗi, hay thực thi những lệnh gọi hệ thống của những máy tính đang chạy job. Condor_collector Condor_negotiator Submit Machine Controlling Deamons schedd Condor_shadow Controlling Deamons startd/starter User’s job User’s code Condor_Syscall_Lib Checkpoint file and saved to disk System call performed Central Manager Execution Machine Hình 2.2 Kiến trúc hệ thống Condor Những deamon chính chạy trên Submit Machine Condor_schedd: Deamon này có nhiệm vụ miêu tả job trong Condor Pool, người dùng có thể gửi những job tới một condor_schedd đang chạy, những job này được lưu trong job queue, những demons khác có nhiệm vụ xem và thao tác tới job queue như: condor_submit, condor_q, condor_rm sẽ kết nối tới condor_schedd để thực thi công việc