Đề tài Quản lý và khai phá dữ liệu trên lưới

QUẢN LÝ VÀ KHAI PHÁ DỮ LIỆU TRÊN LƯỚI Giới thiệu Ngày nay, các hệ thông thông tin ngày càng lưu trữ một khối lượng lớn dữ liệu về hoạt động hằng ngày của chúng. Từ khối dữ liệu này, các kĩ thuật trong khai phá dữ liệu và máy học có thể dùng để trích xuất những thông tin hữu ích mà chúng ta chưa biết. Các tri thức vừa học được có thể vận dụng để phân tích hoạt động và cải thiện hiện quả của hệ thống thông tin ban đầu. Tuy nhiên, việc áp dụng các giải thuật về khai phá dữ liệu trên khối lượng dữ liệu thực tế lớn sẽ đòi hỏi thời gian xử lý rất dài và không hiệu quả. Đã có một số nỗ lực song song và phân bố hóa các giải thuật để chạy trên các hệ thống tính toán mạnh. Tuy nhiên, nếu dữ liệu cần khai phá là rất lớn thì chúng vẫn đòi hỏi một lượng tài nguyên tính toán lớn và điều này gây ra rất nhiều khó khăn trong việc triển khai và áp dụng các ứng dụng khai phá dữ liệu trong thực tế. Trong khi đó, môi trường tính toán lưới hứa hẹn sẽ giải quyết rất tốt bài toán về tài nguyên tính toán với chi phí thấp. Do đó, cách tiếp cận của chúng tôi là tìm hiểu chọn lọc, và đề xuất giải thuật khai phá dữ liệu có mô hình thích hợp với việc phát triển các phiên bản chạy trên nền tính toán phân bố. Để phù hợp với tính chất của môi trường tính toán lưới, các giải thuật này phải có khả năng thực hiện phân tán trên các nút tính toán không đồng nhất về khả năng tính toán và có kết nối lỏng lẻo. Để hiện thực ý tưởng này trên GRID, hệ thống về cơ bản sẽ cần có hai thành phần quan trọng cần phải nghiên cứu và hiện thực là: (1) Quản lý dữ liệu trên lưới; và (2) Khai phá dữ liệu trên lưới. Phần quản lý dữ liệu trên lưới Nội dung chính của phần này là xây dựng một hệ thống quản lý dữ liệu trên môi trường Grid (Grid Data Management System - GDM) có những chức năng sau: Phân bố, đồng bộ và tích hợp dữ liệu Trên môi trường Grid, dữ liệu được lưu trữ phân bố với nhiều định dạng khác nhau gây khó khăn cho việc truy xuất dữ liệu. Mục tiêu của thư viện là xây dựng các dịch vụ hỗ trợ việc quản lý dữ liệu trên Grid đồng thời cho phép người sử dụng thao tác trên dữ liệu dễ dàng, nhanh chóng và hiệu quả. Từ một khối lượng lớn dữ liệu, ta có thể sử dụng một số dịch vụ của thư viện để lưu trữ phân bố lượng dữ liệu đó dưới nhiều định dạng khác nhau. Ngược lại, khi cần thiết, ta có thể tổng hợp dữ liệu từ nhiều nơi với nhiều định dạng khác nhau để phục vụ cho một yêu cầu nào đó. Bên cạnh đó, giống như một cơ sở dữ liệu thông thường, thư viện cũng cung cấp những chức năng thao tác trên dữ liệu như truy vấn, cập nhật hay thực hiện một thủ tục cho trước. Ngoài ra, thư viện còn hỗ trợ các chức năng thay đổi định dạng và truyền nhận dữ liệu trên môi trường phân bố. Phân bố dữ liệu trên các node cần phải chú ý đến tính tin cậy và tính nhất quán dữ liệu. Tin cậy: nếu một trong các node bị hư thì vẫn đảm bảo được tính đúng đắn của chương trình, nghĩa là cần phải tạo các bản sao dữ liệu (không cần phải sao lưu tòan bộ dữ liệu). Khi đã tạo ra bản sao dữ liệu cần phải có cơ chế cập nhật bản sao để đảm bảo tính nhất quán dữ liệu. Bảo mật dữ liệu Có 2 vấn đề chính: (1) Quyền truy xuất dữ liệu: Ai là người có quyền truy xuất dữ liệu, quyền cập nhật dữ liệu. (2) Bảo mật dữ liệu khi truyền đi: có thể sử dụng những chức năng bảo mật dữ liệu do hạ tầng Grid cung cấp. Hệ thống đã đưa ra giải pháp sử dụng các tickets cho vấn đề (1) và đã hiện thực một prototype cho giải pháp đề nghị. Phân tích và theo dõi hiệu năng truy xuất dữ liệu Vì dữ liệu được lưu trữ phân bố do đó thư viện GDM cung cấp những chức năng giúp theo dõi tần suất sử dụng cũng như thời gian thao tác trên dữ liệu ở các nơi và dự đoán thời gian thao tác trên dữ liệu gắn với từng yêu cầu cụ thể. Từ những thông số đó, ta có thể điều chỉnh lại kế họach sử dụng dữ liệu cho phù hợp, tăng hiệu suất sử dụng và giảm thời gian hoàn thành một nhiệm vụ được giao. Tất cả các chức năng này đều được hiện thực như các dịch vụ trên lưới (grid service). Tính phí sử dụng dữ liệu Dựa trên những kết quả của việc phân tích và theo dõi hiệu năng truy xuất dữ liệu, ta có thể căn cứ vào khối lượng dữ liệu được truy xuất để tính phí sử dụng dữ liệu của ứng dụng. Phần khai phá dữ liệu trên lưới Trong kỹ thuật khai phá dữ liệu, có nhiều nhóm giải thuật và trong mỗi nhóm có hàng trăm giải thuật để phân tích và tìm kiếm các tri thức hữu ích. Chúng tôi tập trung tìm hiểu các giải thuật thuộc nhóm gom cụm (clustering) và đề nghị áp dụng giải thuật Phân nhóm 2 giai đoạn 2-Phase K-Mean vì giải thuật này phù hợp với môi trường tính toán lưới. Bước kế tiếp, chúng tôi hiện thực, triển khai và thử nghiệm giải thuật trên hạ tầng tính toán lưới đã được xây dựng bởi nhóm GDM bên trên. Ứng dụng khai phá dữ liệu sử dụng chức năng tìm kiếm tài nguyên của nhóm hệ thống phát triển hạ tầng tính toán lưới để tìm kiếm các tài nguyên tính toán phù hợp và nhờ môi trường lưới bên dưới để triển khai công việc lên trên tài nguyên tính toán đó. Ngoài ra, do đặc thù của bài toán phải thao tác trên một khối lượng dữ liệu lớn được lưu trữ phân tán ở nhiều định dạng khác nhau, ứng dụng khai phá dữ liệu sử dụng lớp quản lý dữ liệu trên lưới để phân bố dữ liệu lên các nút tính toán và thực hiện tổng hợp dữ liệu kết quả trả về từ các nút tính toán. Chi tiết hơn về hai thành phần trên đây của hệ thống sẽ được trình bày cụ thể trong các mục sau của chương này. Tóm lại, trong dự án này, phần quản lý và khai thác dữ liệu trên lưới đã nghiên cứu, phát triển/xây dựng thành công các sản phẩm/qui trình công nghệ cụ thể được tóm tắt lại như sau: STT Sản phẩm/qui trình công nghệ 1 Bản báo cáo kỹ thuật đặc tả các chức năng, kiến trúc của hệ thống và protocol truy xuất dữ liệu trên Grid cho các ứng dụng 2 Báo cáo kỹ thuật xác định đặc tả giao tiếp giữa các nhóm: ứng dụng khai phá dữ liệu trên lưới, quản lý dữ liệu trên lưới, và quản lý tài nguyên tính toán 3 Phần mềm thư viện dưới dạng grid services thực hiện gói cơ bản các chức năng gọi hàm truy xuất dữ liệu và giao tiếp với Grid để cung cấp cho nhóm ứng dụng khai phá dữ liệu (hoặc bất cứ một ứng dụng nào khác có nhu cầu) sử dụng. Chức năng chính của thư viện gồm: - Quản lý user - Quản lý thông tin về các tài nguyên dữ liệu của hệ thống - Quản lý, cấp phát và thực thi ticket - Cung cấp thông tin theo dõi trạng thái sử dụng dữ liệu của ứng dụng (có thể dùng để đánh giá hiệu xuất, tính chi phí, …) 4 Phần mềm kết nối, thực hiện phần gọi hàm truy xuất dữ liệu cơ bản và giao tiếp với computing grid (phần tài nguyên tính toán) 5 Phần mềm hiện thực trên Grid cho giải thuật 2-Phase K-Mean triển khai trên ProActive, GTK4 6 Phần mềm hiện thực một ứng dụng minh họa (bài toán phân loại đất rừng) cho hoạt động của hệ thống 7 Viết báo cáo kỹ thuật về hướng dẫn sử dụng và cài đặt hệ thống 8 Xuất bản 3 bài báo khoa học trong các hội nghị và tạp chí chuyên ngành trong và ngoài nước 9 Qui trình công nghệ cài đặt OGSA-DAI và GDM trên Grid 10 Qui trình công nghệ xây dựng một grid service 11 Qui trình công nghệ triển khai một ứng dụng khai pha dữ liệu trên lưới với sự hỗ trợ của GDM Kiến trúc hệ thống GDM Hình 1: Kiến trúc hệ thống quản lý dữ liệu trên Grid (GDM) Các thành phần của hệ thống Computing Resource Computing Resource đại diện cho các tài nguyên tính toán trên Grid, bao gồm tất cả các tài nguyên có thể được cấp phát (computing resource) để phục vụ cho việc tính toán trên môi trường Grid. Data Resource Data Resource đại diện cho các tài nguyên dữ liệu trên Grid. Mỗi data resource là một node chứa dữ liệu trên môi trường Grid. Grid Data Management (GDM) Đây là khối chức năng trung tâm trong kiến trúc của hệ thống, quản lý thông tin về các tài nguyên dữ liệu trên Grid. Mọi thao tác trên dữ liệu đều phải thông qua sự kiểm soát của GDM. GDM lưu trữ siêu dữ liệu (metadata) về các tài nguyên dữ liệu trên Grid: các node chứa dữ liệu, vị trí các bản sao dữ liệu, các quyền truy xuất trên dữ liệu, ... GDM đảm nhận các công việc sau: Quản lý thông tin (metadata) về các tài nguyên dữ liệu trên Grid. Cung cấp thông tin về các tài nguyên dữ liệu trên Grid: tên node chứa tài nguyên, một số thông tin về dữ liệu chứa trên node như định dạng dữ liệu, kích thước dữ liệu, vị trí khối dữ liệu này trong khối dữ liệu lớn ban đầu (trước khi nó được phân bổ xuống các node trên Grid), … Thẩm định và cấp phát các quyền khác nhau cho ứng dụng: quyền truy vấn thông tin về các tài nguyên dữ liệu trên Grid, quyền truy vấn và thao tác trên một tài nguyên dữ liệu cụ thể. Cấp phát và quản lý các ticket để một ứng dụng có thể truy vấn và thao tác dữ liệu trên môi trường phân bố. Ticket chứa những thông tin cần thiết như tên tài nguyên, quyền truy xuất, … Hỗ trợ việc truy vấn và thao tác dữ liệu ứng với các ticket đã cấp phát. Business Application Đại diện cho một ứng dụng cần sử dụng dữ liệu chứa trong những tài nguyên dữ liệu trên môi trường phân bố. Các ứng dụng truy vấn và thao tác với những dữ liệu này thông qua các dịch vụ mà GDM cung cấp. Data Store Data Store là nơi chứa toàn bộ dữ liệu ban đầu. Một phần hoặc toàn bộ dữ liệu ở Data Store sẽ được lưu trữ phân bố trên một số node dữ liệu (data resource) trên Grid để thuận tiện cho việc tính toán. Tập hợp các data resource chứa dữ liệu phân bố của cùng một data store được gọi là data source. Các vấn đề chính trong thiết kế hệ thống Quản lý thông tin về các user sử dụng hệ thống Mỗi ứng dụng chạy trên môi trường Grid đều có một định danh (credential) riêng biệt. Thông tin về các ứng dụng có nhu cầu truy xuất dữ liệu (thông tin này nhằm phục vụ cho dịch vụ tính tiền) được lưu trữ trong metadata sau: Application(credential, description, app_role) credential: định danh của ứng dụng description: miêu tả về ứng dụng app_role: các quyền của ứng dụng khi truy vấn metadata lưu trên GDM Một ứng dụng có thể truy vấn và thao tác dữ liệu trên nhiều Data source (xem định nghĩa của data source bên trên). Để truy xuất dữ liệu trên một Data source, ứng dụng phải được cấp một tài khoản (user name, password) với một quyền truy vấn và thao tác dữ liệu nhất định. Ta có thể xem xét việc gắn thông tin tài khoản truy xuất dữ liệu vào credential để giúp cho việc sử dụng dữ liệu của các ứng dụng chạy trên Grid trở nên đơn giản hơn nhưng vẫn đảm bảo tính an toàn và hiệu quả. Có nhiều cơ chế hỗ trợ hiệu quả vấn đề này. LDAP là một thí dụ. Thông tin về các tài khoản đăng ký với các Data source được lưu trữ trong metadata sau: User(user_name, credential, data_source_id, password, role) user_name, password: những thông tin cần thiết để truy xuất vào một Data source. credential: định danh của ứng dụng sử dụng tài khoản này. data_source_id: định danh của Data source mà tài khoản này có thể truy xuất dữ liệu. role: quyền truy vấn và thao tác dữ liệu của tài khoản. Phân bố dữ liệu từ Data Store xuống data resource Để có thể sử dụng được dữ liệu từ Data Store, trước tiên khối dữ liệu này cần được phân bổ vào các tài nguyên dữ liệu trên Grid. Hầu hết hoặc toàn bộ dữ liệu chứa trong Data Store sẽ chứa trên các data resource. Chiến lược phân bố dữ liệu xuống các data resource chỉ hợp lý và có hiệu quả trên cơ sở xem xét đầy đủ các yếu tố sau: Yêu cầu cụ thể của từng bài toán Số lượng các data resource trên Grid Khả năng về dụng lượng và tốc độ của từng data resource Tần suất trao đổi dữ liệu trên các data resource Hiệu năng truy xuất hiện tại của hệ thống Cách phân bố dữ liệu chúng tôi áp dụng ở giai đoạn này là phân bố đều dữ liệu xuống các data resource sẵn có. Khối dữ liệu ban đầu trên Data Store sẽ được phân bố xuống các node dữ liệu (Data resource) khác nhau và mỗi node được xác định thông qua định danh Data_resource_id. Tập hợp các data resource chứa dữ liệu phân bố của cùng một data store được gọi là data source. Những thông tin chính về việc phân bổ dữ liệu trên Grid được GDM lưu trữ trong metadata sau: Data_Source(data_source_id, data_source_name, description) data_source_id: định danh của khối dữ liệu ban đầu trước khi được phân bố xuống các data resource. data_source_name: tên của data source. description: một số đặc tả khác về data source. Data_Resource(data_resource_id, data_source_id) data_resource_id: định danh của mỗi phân mảnh dữ liệu của Data_source. data_source_id: định danh của Data source. Data_Item(data_item_name, data_resource_id) data_item_name: tên của một bảng dữ liệu trên một node dữ liệu data_resource_id: định danh của node dữ liệu. GDM sẽ theo dõi tình hình phân bố dữ liệu trên grid và cập nhật thông tin liên tục. Sau khi quá trình phân bố dữ liệu hoàn tất, mọi thao tác trên dữ liệu (truy vấn, cập nhật…) sẽ tiến hành trên dữ liệu chứa trong các data resource. Các thao tác này cần có sự giám sát và thông tin phải được lưu trữ vào GDM để quản lý về sau. Lấy thông tin về các Data Resource Thông tin về các Data Source, cách phân bố xuống các Data Resource, …đều được GDM quản lý. Khi có một yêu cầu lấy thông tin về các Data Resource từ phía ứng dụng như định danh của các Data Resource, kích thước dữ liệu, index, schema của dữ liệu..., GDM sẽ kiểm tra tính tương thích giữa yêu cầu đưa ra và quyền thực tế của ứng dụng trước khi thực thi yêu cầu. GDM chỉ cần dựa vào thông tin về các user sử dụng hệ thống mà nó quản lý cũng như các thông tin về phân bố dữ liệu trên Grid là có thể thực thi các yêu cầu này một cách dễ dàng. Để có thể tăng tốc độ đáp ứng của hệ thống, GDM có thể lưu giữ trên vùng nhớ tạm một số thông tin chính thường hay được truy xuất của các Data Resource thay vì lúc nào cũng phải truy xuất xuống cơ sở dữ liệu bên dưới. Tuy nhiên cách làm này đòi hỏi phải có sự cập nhật thông tin trên vùng nhớ tạm khi dữ liệu bên dưới bị thay đổi. Cấp phát, quản lý, và thực thi ticket Dưới đây là sơ đồ kiến trúc chi tiết mô tả hoạt động của hệ thống quản lý dữ liệu trên Grid: Hình 2: Minh họa các bước hoạt động của hệ thống GDM Hệ thống quản lý dữ liệu trên Grid (GDM) gồm các khối chức năng ứng với các dịch vụ chính lien quan đến việc quản lý và thực thi ticket như sau: Metadata management service: quản lý các siêu dữ liệu về các data source và data resource. Ticket management service: quản lý và cấp phát các ticket cho bussiness application. Data resource management service: giao tiếp với các data resource thông qua Data accessor service để đưa ra các yêu cầu truy vấn và thao tác dữ liệu. Data accessor service: truy vấn và thao tác dữ liệu trên data resource và gửi kết quả cho computing resource thông qua Client service. Client service: nhận kết quả trả về từ Data accessor service và gửi ack về cho Data resource management service. Quản lý ticket Ticket đại diện cho một yêu cầu cụ thể từ phía ứng dụng, đó có thể là yêu cầu truy xuất dữ liệu trên một bảng dữ liệu của một Data Resource, hay là một yêu cầu cập nhật dữ liệu ( tạo bảng, chèn dữ liệu, xóa dữ liệu, xóa bảng), … Mỗi ticket chứa những thông tin cần thiết để một ứng dụng có thể làm việc (truy xuất, cập nhật…) với Data Resource tương ứng và gồm những thông tin chính như sau: Ticket (ticket_id, ticket_type, valid_time, credential, times_of_use) ticket_id: định danh của ticket valid_time: thời gian ticket có hiệu lực sử dụng ticket_type: quy định loại của ticket credential: định danh của người xin cấp phát ticket times_of_use: số lần ticket còn có thể được sử dụng Tùy vào mục đích sử dụng, có thể phân ticket thành nhiều loại sau đây: Lưu trữ thông tin về các ticket dùng cho việc lấy dữ liệu: Ticket_Data(ticket_id, data_item_name, data_resource_id, startIndex, stopIndex) data_item_name: tên của bảng chứa dữ liệu cần truy xuất data_resource_id: định danh của data resource chứa bảng dữ liệu cần truy xuất. startIndex, stopIndex: khoảng dữ liệu cần truy xuất. Lưu trữ thông tin về các ticket dùng cho việc chèn dữ liệu vào bảng: Ticket_Insert_Record(ticket_id, data_item_name, data_resource_id, column_names) data_item_name: tên của bảng chứa dữ liệu cần tạo. data_resource_id: định danh của data resource chứa bảng dữ liệu cần tạo. column_names :các cột cần chèn dữ liệu vào. Lưu trữ thông tin về các ticket dùng cho việc tạo mới một bảng dữ liệu: Ticket_Create_Table(ticket_id, data_item_name, data_resource_id, schema) data_item_name: tên của bảng chứa dữ liệu cần tạo. data_resource_id: định danh của data resource chứa bảng dữ liệu cần tạo. schema: thông tin về cấu trúc của bảng. Lưu trữ thông tin về các ticket dùng cho việc xóa một bảng dữ liệu: Ticket_Drop_Table(ticket_id, data_item_name, data_resource_id) data_item_name: tên của bảng dữ liệu cần xóa. data_resource_id: định danh của data resource chứa bảng dữ liệu cần xóa. Cấp phát ticket để ứng dụng có thể làm việc với các Data Resource Khi nhận được yêu cầu xin ticket, GDM sẽ kiểm tra tính tương thích giữa yêu cầu đưa ra và quyền của ứng dụng trước khi cấp phát ticket. Nếu hợp lệ, GDM sẽ sinh ra một ticket tương ứng và trả về cho ứng dụng định danh (ticket_id) của ticket này. GDM sẽ lưu trữ thông tin về ticket để phục vụ cho việc thực thi ticket cũng như tính phí sau này. Ứng dụng sẽ sử dụng ticket_id cho việc tương tác với các Data Resource. Ứng dụng xin ticket và ứng dụng xin thực thi ticket có thể khác nhau vì ứng dụng xin ticket có thể sẽ cung cấp cho ứng dụng xin thực thi ticket một thẻ bài (token) chứa các thông tin cần thiết để thực thi ticket. Token sẽ bao gồm ticket_id và định danh của người được cấp token (người sẽ sử dụng ticket) đã được mã hóa bằng khóa bí mật của ứng dụng xin ticket. Nếu như ứng dụng xin ticket cũng là ứng dụng thực thi ticket thì nó cũng vẫn phải tự tạo ra một token cho riêng nó. Thực thi ticket Để thực thi một ticket, thông tin ứng dụng cần gởi đến cho GDM gồm có định danh của ứng dụng và token tương ứng. Khi nhận được thông tin thực thi ticket, dựa vào ticket_id chứa trong token, GDM sẽ lấy được các thông tin về ticket này. Trước hết GDM sẽ kiểm tra hạn sử dụng (valid_time…) của ticket này. Nếu hợp lệ, GDM sẽ kiểm tra quyền hợp pháp của ứng dụng. GDM dùng public key của người đã xin cấp phát ticket giải mã để tìm ra định danh của người được cấp token. Nếu định danh này và định danh do ứng dụng cung cấp trùng nhau thì đây là một yêu cầu hợp lệ. Ticket được thực thi. GDM căn cứ vào nội dung của ticket để yêu cầu Data Resource tương ứng thực thi. Kết quả sẽ được Data Resource gởi thẳng tới ứng dụng. GDM sẽ cập nhật thông tin về ticket để cho biết ticket đã được thực thi. Một số vấn đề liên quan đến việc xin ticket và thực thi ticket: Ticket là vấn đề chính yếu nhất của hệ thống nên có nhiều vấn đề cần xem xét trong thiết kế. Sau đây là một số vấn đề đã được nhận dạng và giải quyết trong GDM. Vấn đề DoS( Denial of Service): Xin ticket không bị tính phí, do đó ứng dụng có thể tấn công hệ thống bằng cách gởi yêu cầu hàng loạt để xin các ticket giống nhau. Vấn đề này có thể được giải quyết theo một số hướng đề nghị sau: Quy định số lần xin ticket tối đa trong một session giao tiếp giữa ứng dụng và hệ thống. Có thể cho phép một ticket được sử dụng nhiều lần. Dựa vào lịch sử sử dụng các ticket của ứng dụng. Quy định ngưỡng tối đa số lượng các ticket ứng dụng đã xin nhưng chưa được sử dụng, nếu vượt quá giới hạn này thì không cấp ticket mới cho ứng dụng nữa. Vấn đề mất ticket: Ứng dụng xin ticket có thể báo với hệ thống về việc làm mất ticket. Nếu như ticket đó đã được thực thi thì hệ thống không chấp nhận yêu cầu từ phía ứng dụng, ngược lại hệ thống sẽ đánh dấu hủy ticket này nhưng vẫn tính một mức phí theo quy định. Vấn đề hủy bỏ ticket: Ta có thể phân ticket làm nhiều lọai: ticket có thể hủy hoặc không. Ticket không thể hủy sẽ được tính mức giá thấp hơn so với loại còn lại. Khi có yêu cầu hủy bỏ ticket từ phía ứng dụng, nếu đó là ticket có thể hủy, GDM sẽ đánh dấu hủy ticket này nhưng vẫn tính một mức phí theo quy định; ngược lại yêu cầu hủy bỏ sẽ không được chấp nhận. Kiểm tra tính hợp lệ của ứng dụng thực thi ticket: Theo cách miêu tả ở trên người xin ticket sẽ cấp token cho người thực thi ticket, trong đó có vấn đề mã hóa định danh của người được cấp token bằng khóa bí mật của người xin ticket. Mỗi lần ticket tương ứng xin được thực thi, GDM phải làm