- HOÀNG ANH TUẤN XÂY DỰNG THỬ NGHIỆM GIẢI PHÁP TÌM KIẾM THEO YÊU CẦU NGƯỜI DÙNG, SỬ DỤNG ĐIỆN TOÁN ĐÁM MÂY VÀ THUẬT TOÁN MAPREDUCE LUẬN VĂN THẠC SĨ KHOA HỌC NGƯỜI HƯỚNG DẪN : PGS.TS. - HUỲNH QUYẾT THẮNG HÀ NỘI – 2010 2MỤC LỤC MỤC LỤC DANH MỤC HÌNH VẼ DANH MỤC BẢNG BIỂU CHƯƠNG 1 TỔNG QUAN VỀ ĐIỆN TOÁN ĐÁM MÂY, GIẢI THUẬT MAPREDUCE, HỆ THỐNG TÌM KIẾM Sự phát triển của các mô hình tính toán Tối ưu hóa của quá trình xử lý dữ liệu lớn, giải thuật MAPREDUCE ứng dụng cho các nguồn dữ liệu cực lớn (TB, PB). - Bài toán tìm kiếm theo yêu cầu người sử dụng (Object searching by request. - Nhiệm vụ trong luận văn CHƯƠNG 2 ĐIỆN TOÁN ĐÁM MÂY VÀ GIẢI THUẬT MAPREDUCE Khái niệm về Điện toán đám mây Lịch sử Cloud computing Các đặc tính chính của Cloud Computing Các nhánh chính của điện toán đám mây Phần mềm hoạt động như một dịch vụ (SaaS - Software as a Service Nền tảng như một dịch vụ (PaaS - Platform as a Service Hạ tầng hoạt động như một dịch vụ (IaaS – Infrastructure as a Service) 17 2.3 Các hệ thống Cloud Computing tiêu biểu Google App Engine Microsoft Azune Amazon Elastic Compute Cloud (EC Amazon Simple Storage Service (S Ứng dụng Cloud Computing trong tìm kiếm thông tin Lịch sử phát triển Mapreduce Kỹ thuật lập trình MapReduce Map Function Reduce Function Một số ứng dụng tiêu biểu MapReduce Hệ thống Sort Data của Yahoo, Google Ứng dụng xử lý dữ liệu log Kết chương CHƯƠNG 3 BÀI TOÁN TÌM KIẾM THEO YÊU CẦU NGƯỜI SỬ DỤNG VÀ ĐỀ XUẤT GIẢI PHÁP DỰA TRÊN ĐIỆN TOÁN ĐÁM MÂY VÀ GIẢI THUẬT MAPREDUCE Bài toán tìm kiếm dữ liệu Lịch sử máy tìm kiếm Phân loại máy tìm kiếm trên Internet Mô hình của máy tìm kiếm Thuật toán tìm kiếm Bài toán thu thập, bóc tách dữ liệu (Crawl, parse data Bài toán đánh chỉ mục dữ liệu (Index data Thuật toán tìm kiếm theo độ tương quan (relevance Các giải pháp xây dựng máy tìm kiếm Giải pháp tìm kiếm sử dụng thuật toán MapReduce trên nền điện toán đám mây Sử dụng MapReduce và điện toán đám mây trong việc thu thập, bóc tách dữ liệu Sử dụng MapReduce và điện toán đám mây trong bài toán đánh chỉ mục. - Sử dụng điện toán đám mây trong việc thiết kế module tìm kiếm phân tán Kết chương CHƯƠNG 4 XÂY DỰNG HỆ THỐNG TÌM KIẾM VÀ THỬ NGHIỆM THỰC TẾ Bài toán tìm kiếm tin tức Xây dựng hệ thống tìm kiếm tin tức theo độ tương quan về nội dung, thời gian. - Tổng quan về mô hình hệ thống tìm kiếm Các thành phần của hệ thống Đánh giá kết quả, các hướng cải tiến Các kết quả đạt được Tổng kết luận văn TÀI LIỆU THAM KHẢO DANH MỤC HÌNH VẼ Hình 1.1-1: định luật Moore Hình 2.1-1: Mô hình điện toán đám mây Hình 2.2-1: Các lớp của điện toán đám mây Hình 2.3-1: Giao diện sử dụng EC Hình 2.3-2: Giao diện sử dụng Amazon S Hình 2.6-1: Mô hình MapReduce Hình 2.6-2: Quá trình xử lý MapReduce Hình 3.1-1: Số lượng URL trên thế giới Hình 3.1-2: Thị phần của các máy tìm kiếm tháng 9 năm Hình 3.1-3: Mô hình máy tìm kiếm Hình 3.2-1: Inverted index Hình 3.4-1: Hệ thống tìm kiếm phân tán Hình 4.2-1: Tổ chức hệ thống Hình 4.2-2: Tổ chức module máy tìm kiếm Hình 4.3-1: Tổng số trang web trong hệ thống Hình 4.3-2: Tốc dộ thu thập trang web và đánh chỉ mục DANH MỤC BẢNG BIỂU Bảng 2.7-1: Kết quả sắp xếp dữ liệu của Yahoo Bảng 3.1-1: Số lượng trang web đã được đánh chỉ mục Bảng 4.3-1: Số lượng máy trong các cluster Bảng 4.3-2: Kết quả tìm kiếm CHƯƠNG 1 TỔNG QUAN VỀ ĐIỆN TOÁN ĐÁM MÂY, GIẢI THUẬT MAPREDUCE, HỆ THỐNG TÌM KIẾM 1.1 Sự phát triển của các mô hình tính toán Mô hình tính toán các hệ thống phát triển qua nhiều thời kỳ, ngày càng hiện đại hơn, phát triển cả về chiều rộng (mở rộng về không gian tính toán, thêm các tài nguyên), chiều sâu (cải tiến các thuật toán (từ lập trình cấp thấp, lập trình cấp cao, tính toán song song, tính toán hiệu năng cao. - Phần cứng ngày càng phát triển nhanh, theo định luật Moore [41] :”Số lượng transitor trên mỗi đơn vị inch vuông sẽ tăng gấp đôi sau mỗi hai năm”. - Việc tốc độ các hệ thống tính toán ngày càng được phát triển nhanh, giá thành ngày càng rẻ hơn giúp chúng ta rút ngắn thời gian tính toán cho các đơn vị dữ liệu lớn. - Hình 1.1-1: định luật Moore [42] 8Cùng với việc phát triển của phần cứng, các mô hình lập trình cũng được phát triển với tốc độ chóng mặt. - Ban đầu chỉ là các phương pháp lập trình theo bìa đục lỗ, sau đó phát triển lên thành mô hình lập trình theo ngôn ngữ cấp cao, vào thập niên xuất hiện nhiều ngôn ngữ lập trình cấp cao như FORTRAN, LISP, COBOL. - Từ những năm 1990, kỷ nguyên của Internet bắt đầu, các mô hình lập trình ngày càng phát triển, bao gồm nhiều phương pháp lập trình mới như: lập trình hướng sự kiện, lập trình hướng đối tượng, lập trình logic, lập trình hàm, lập trình đồng thời. - Không chỉ lập trình trên máy tính cá nhân đơn lẻ, nhiều mô hình lập trình đã hướng đến môi trường phân tán, song song, giúp người sử dụng có thể triển khai môi trường lập trình trên nhiều máy tính. - Mục đích của các mô hình lập trình này giúp giải quyết các bài toán dữ liệu lớn, các nhu cầu thực tế của người dùng. - Thử tưởng tượng, nếu không có những mô hình lập trình này, chúng ta sẽ không có những ứng dụng trực tuyến khổng lồ như Google, Facebook hay Yahoo, không thể phát triển những ứng dụng trên Internet như Gmail, Google docs, các hệ thống chia sẻ file, ảnh,… Cùng với sự phát triển nhanh chóng của Internet, các hệ thống tính toán lớn được xây dựng dựa trên sự phát triển về hạ tầng phần cứng và cấu trúc phần mềm trong các chương trình điều khiển. - Với những con số khổng lồ như thế nếu không có đầy đủ hệ thống phần cứng và phần mềm hỗ trợ chúng ta sẽ không thể giải quyết được. - Việc phát triển các hệ thống tính toán mới, dựa trên nền tảng phân tán là đòi hỏi cấp thiết của quá trình giải quyết các vấn đề về tính toán. - Hiện nay một trong những mô hình được quan tâm phát triển nhiều nhất là điện toán đám mây [1]. - Nó vừa giúp giải quyết bài toán về phần cứng khi tối ưu hóa, cung cấp các giải pháp về phần cứng như máy chủ, hệ thống lưu trữ, các nền tảng tính toán, đến các hệ thống phần mềm như khung lập trình đều trở thành dịch vụ. - Điện toán đám mây là mô hình phát triển của các hệ thống trong tương lai, giúp chúng ta giải quyết các vấn đề về mặt hạ tầng, dịch vụ, cung cấp những giải pháp tối ưu cho các hệ thống 9thương mại, phục vụ nhiều người dùng, theo nhiều quy mô từ bé đến lớn, từ đơn giản đến phức tạp, từ phục vụ mục đích riêng tư, đến mục đích công cộng. - 1.2 Tối ưu hóa của quá trình xử lý dữ liệu lớn, giải thuật MAPREDUCE ứng dụng cho các nguồn dữ liệu cực lớn (TB, PB). - Các ứng dụng lớn trên Internet như hệ thống của Google, Yahoo!, Facebook đều cần phải lưu trữ, xử lý và tương tác với lượng dữ liệu cực kỳ lớn. - Lưu trữ có thể giải quyết được khi được cung cấp đủ thiết bị phần cứng và có thuật toán lưu trữ tốt. - Với lượng dữ liệu khổng lồ, chúng ta phải lựa chọn các phương pháp lưu trữ phân tán, tạo thành các hệ thống file phân tán và có cơ chế quản lý chúng. - Khi đã lưu trữ được dữ liệu, chúng ta cần một hệ thống xử lý đủ nhanh cho lượng dữ liệu đó. - Một trong những giải thuật được nhắc đến nhiều nhất trong những năm gần đây phục vụ cho việc xử lý lượng dữ liệu lớn là MapReduce [8]. - Những ưu điểm của giải thuật MapReduce được ứng dụng giải quyết các bài toán dữ liệu lớn. - MapReduce là một giải thuật, được viết lại thành khung lập trình, hỗ trợ lập trình phân tán một cách nhanh chóng. - Giải thuật MapReduce dễ dàng triển khai trên nhiều máy, việc thêm một máy vào để chạy giải thuật rất đơn giản, chỉ thông qua các file cấu hình. - MapReduce có thể đọc và xử lý được hầu hết các dữ liệu cơ bản, như các giải thuật khác, nó có cơ chế để chia nhỏ khối dữ liệu lớn thành các khối dữ liệu nhỏ hơn, chia cho các tác vụ thực hiện và tổng hợp kết quả. - Nó có khả năng tổng hợp các kết quả chạy trên các máy khác nhau tạo ra kết quả cuối cùng đưa lại cho người dùng. - 10- MapReduce xử lý dữ liệu theo cặp giá trị key/value nên có khả năng xử lý nhanh các bài toán cơ bản. - Với những ưu điểm của giải thuật MapReduce như trên, chúng ta có thể xây dựng nhiều ứng dụng thông dụng như [43. - Các bài toán thống kê: thống kê log, xử lý log, thống kê số lượng, thống kê thời tiết. - Các bài toán về khai phá dữ liệu, hệ thống giới thiệu (recommendation engines. - Các bài toán về phân tích dữ liệu, xử lý gian lận - Bài toán về xác định mục tiêu đối tượng quảng cáo, phân phối quảng cáo đến đúng đối tượng, với số lượng đúng mức. - Bài toán về chất lượng tìm kiếm. - Tất cả các bài toán cần xử lý dữ liệu nói chung, đặc biệt là các bài toán dữ liệu lớn đều có thể sử dụng thuật toán MapReduce. - 1.3 Bài toán tìm kiếm theo yêu cầu người sử dụng (Object searching by request) Bài toán tìm kiếm dữ liệu đã tồn tại một thời gian khá lâu. - Khi dữ liệu ít, không có nhiều thì bài toán là khá đơn giản, có thể được thực hiện bằng vài lệnh của hệ điều hành (hệ điều hành Linux). - Tuy nhiên khi dữ liệu lớn lên, tăng trưởng theo từng ngày, từng giờ, mức độ cập nhật thông tin ngày càng tăng lên thì vấn đề tìm kiếm chính xác theo yêu cầu của người dùng càng khó khăn. - Những khó khăn chính của bài toán tìm kiếm [44. - Khả năng bao phủ nội dung: hệ thống tìm kiếm có khả năng bao phủ được những nội dung người dùng cần thiết chưa? Với lượng dữ liệu khổng lồ trên Internet, có chiến thuật hay giải thuật nào để có thể bao phủ được hết số lượng nội dung trên đó. - Khả năng cập nhật nội dung: tương tự như vấn đề bao phủ, thời gian cập nhật nội dung mới sẽ là bao lâu, có đủ cung cấp nội dung mới cho người dùng hay không? 11- Trang thiết bị hoạt động: hệ thống máy móc để hoạt động, lưu trữ dữ liệu, băng thông mạng, các hạ tầng khác. - Thuật toán tìm kiếm, lưu trữ dữ liệu: làm sao để tìm kiếm và cung cấp nội dung đúng như người dùng mong muốn. - Thời gian tìm kiếm: thời gian tìm kiếm phải thỏa mãn người dùng, không được phép quá lâu, thông thường sẽ phải nhỏ hơn 1 giây. - Tại Việt Nam, theo thống kê của VNNIC đến tháng 9 năm 2010 có hơn 25 triệu người sử dụng Internet [30], nhu cầu tìm kiếm và sử dụng các dịch vụ trực tuyến là rất lớn. - Các công cụ tìm kiếm trên thế giới như Google, Yahoo, Bing đã đáp ứng được phần nào nhu cầu sử dụng của những người sử dụng ở Việt Nam. - Tuy nhiên khó khăn lớn nhất của các công cụ tìm kiếm đó là khả năng “hiểu” tiếng Việt, văn hóa Việt Nam. - Khi một người Việt Nam tìm kiếm, họ muốn kết quả tìm kiếm được phải thỏa mãn yêu cầu của họ và mang phong cách Việt Nam và phải “hiểu” được nhu cầu của người dùng Việt Nam. - Đó là một thách thức lớn, nhưng cũng là một cơ hội lớn cho việc phát triển hệ thống tìm kiếm thuần Việt ở Việt Nam. - Một trong những phương pháp là xây dựng hệ thống tìm kiếm dựa trên điện toán đám mây và giải thuật MapReduce. - Việc sử dụng điện toán đám mây, giúp cung cấp nền tảng hệ thống tốt nhất trong phạm vi giới hạn về khả năng quản lý, tài chính để xây dựng ứng dụng. - Sử dụng thuật toán MapReduce giúp giải quyết những vướng mắc về kỹ thuật, giải pháp trong việc xây dựng bài toán tìm kiếm theo yêu cầu người sử dụng. - 1.4 Nhiệm vụ trong luận văn Trong luận văn này, tôi tập trung vào nghiên cứu ba phần chính: 12- Khái niệm về điện toán đám mây, cách thức xây dựng ứng dụng trên mô hình điện toán đám mây. - Cách thức vận hành một hệ thống trên môi trường điện toán đám mây. - Giải thuật MapReduce, cách thức sử dụng và ứng dụng giải thuật trong các bài toán xử lý dữ liệu, ứng dụng giải thuật MapReduce trong bài toán xây dựng máy tìm kiếm. - Phương pháp xây dựng máy tìm kiếm: cách thức xây dựng các thành phần của máy tìm kiếm, hệ thống thu thập nội dung, hệ thống đánh chỉ mục dữ liệu và hệ thống tìm kiếm theo yêu cầu người dùng. - Trong các chương tiếp theo, chúng ta sẽ nghiên cứu các thành phần cấu thành nên hệ thống bao gồm hai phần chính là điện toán đám mây và giải thuật MapReduce để xây dựng nên một hệ thống tìm kiếm hiệu quả. - 13CHƯƠNG 2 ĐIỆN TOÁN ĐÁM MÂY VÀ GIẢI THUẬT MAPREDUCE 2.1 Khái niệm về Điện toán đám mây Điện toán đám mây là một trong những thuật ngữ được nhắc đến nhiều nhất trong thời gian qua. - Điện toán đám mây là mô hình điện toán sử dụng các công nghệ về máy tính và phát triển dựa vào mạng Internet. - Nó là cơ sở để phát triển các ứng dụng hướng dịch vụ, cung cấp các dịch vụ cho khách hàng thông qua một hạ tầng dịch vụ chung. - Theo hệ thống định nghĩa về điện toán đám mây [45], có 3 định nghĩa về điện toán đám mây. - Định nghĩa một: việc lưu trữ và truy cập các ứng dụng và dữ liệu máy tính thường thông qua một trình duyệt Web thay vì chạy các phần mềm cài đặt trên máy tính văn phòng cá nhân hoặc máy chủ. - Định nghĩa hai: điện toán dựa trên Internet, trong đó các thông tin, nguồn lực công nghệ thông tin (CNTT) và ứng dụng phần mềm được cung cấp cho các máy tính và các thiết bị di động theo yêu cầu. - Định nghĩa ba: Sử dụng Internet để truy cập các ứng dụng dựa trên Web, các dịch vụ Web và cơ sở hạ tầng như một dịch vụ. - Như vậy theo các định nghĩa, điện toán đám mây là việc ảo hóa (virtualized) các tài nguyên điện toán và các ứng dụng trên đó. - Theo các định nghĩa đó, mô hình điện toán đám mây có các đặc trưng chính. - Cho phép sử dụng dịch vụ theo yêu cầu (on-deaman serivce. - Cung cấp khả năng truy cập dịch vụ rộng rãi từ các thiết bị đầu cuối như máy tính để bàn, máy tính xách tay, thiết bị di động. - Tài nguyên tính toán động, phục vụ cho nhiều người sử dụng, năng lực tính toán mềm dẻo, đáp ứng nhanh các nhu cầu sử dụng từ thấp đến cao. - 14- Ngoài ra việc sử dụng điện toán đám mây, người sử dụng và nhà cung cấp dịch vụ có thể quản lý, theo dõi việc sử dụng các tài nguyên, giúp nhà cung cấp tối ưu hóa tài nguyên, giúp người sử dụng chỉ phải trả số tiền dựa vào tài nguyên đã sử dụng. - Hình 2.1-1: Mô hình điện toán đám mây Lịch sử Cloud computing Những khái niệm đầu tiên về điện toán đám mây được đưa ra từ những năm 1960 khi John McCarthy cha đẻ của thuật ngữ “Trí tuệ nhân tạo” phát biểu rằng “một ngày nào đó có thể tính toán sẽ được tổ chức lại như là một tiện ích công cộng”. - Thuật ngữ “đám mây” được vay mượn từ ngành viễn thông, khi cung cấp mạng riêng ảo (VPN – Virtual Private Networking). - Amazon đóng vai trò quan trọng trong việc xây dựng điện toán đám mây bằng cách hiện đại hóa trung tâm dữ liệu sau bong bóng dot-com. - Amazon cung cấp điện toán đám mây cho khách hàng, dịch vụ AWS – Amazon Web Service [3] vào năm 2006. - Trong năm 2007, Google, IBM và một số trường đại học cũng bắt tay vào một dự án nghiên cứu quy mô lớn điện toán đám mây. - Eucalyptus [4] trở thành dự án mã mở đầu tiên triển khai điện toán đám mây riêng tư và mạng máy tính. - Google cung cấp 15giải pháp Google App Engine [51], ở đó Google đã cung cấp sẵn hệ thống hạ tầng điện toán đám mây, người lập trình chỉ cần viết ứng dụng của mình lên đó. - 2.1.2 Các đặc tính chính của Cloud Computing Điện toán đám mây mang lại những đặc tính quan trọng, tiện lợi, dễ sử dụng hơn những mô hình tính toán khác. - Những đặc tính chính của điện toán đám mây. - Khả năng mở rộng theo yêu cầu dịch vụ: điện toán đám mây cung cấp các tài nguyên, dịch vụ cho người dùng theo yêu cầu. - Các tài nguyên được mở rộng trên nhiều trung tâm dữ liệu, có thể tập trung hoặc phân tán. - Độc lập về không gian và thiết bị: người dùng có thể truy cập, sử dụng tài nguyên hệ thống ở mọi lúc, mọi nơi thông qua trình duyệt web, bằng nhiều thiết bị, có thể là máy tính cá nhân hay thiết bị di động. - Chỉ cần kết nối Internet, người dùng có thể kết nối ở bất kỳ nơi nào. - Linh hoạt: người sử dụng có thể sử dụng nhanh chóng, không tốn kém các nguồn tài nguyên. - Người dùng có thể được đảm bảo chất lượng dịch vụ về phần cứng, hiệu suất, băng thông, dung lượng bộ nhớ. - Hệ thống tập trung tự động: tất cả các cơ sở hạ tầng đều được tập trung tại các địa điểm với chi phí thấp hơn, dễ dàng quản lý, bảo trì hơn khi các dịch vụ được tập trung, không cài phân tán trên các máy người sử dụng. - Giá thành: việc sử dụng điện toán đám mây, giúp người dùng không phải đầu tư toàn bộ chi phí về hạ tầng, thiết bị. - Ngoài ra không cần thuê thêm chi phí nhân lực bảo trì, bảo dưỡng hệ thống máy móc. - Không bị lãng phí hệ thống khi không cần dùng trong một thời gian, chỉ phải trả tiền cho thời gian sử dụng hệ thống. - 2.2 Các nhánh chính của điện toán đám mây Điện toán đám mây được chia làm 4 lớp chính: 16 Hình 2.2-1: Các lớp của điện toán đám mây Chúng ta sẽ nghiên cứu từng lớp của điện toán đám mây. - 2.2.1 Phần mềm hoạt động như một dịch vụ (SaaS - Software as a Service) Phần mềm hoạt động như một dịch vụ là lớp trên cùng của điện toán đám mây. - Đây là tập hợp các ứng dụng cung cấp cho người dùng theo yêu cầu, nó được cài đặt và chạy trong các hệ thống đám mây, được quản trị, quản lý bởi những nhà cung cấp. - Mục đích của hệ thống là giúp người dùng có thể sử dụng ứng dụng ở mọi lúc, mọi nơi bằng bất kỳ loại thiết bị tương thích nào. - Việc truy cập các ứng dụng chủ yếu qua Internet và phần mềm như là một dịch vụ, phục vụ người dùng khi có yêu cầu. - Người dùng có thể sử dụng các dịch vụ để sử dụng các ứng dụng ở những địa điểm khác nhau, không nhất thiết phải cài đặt lên thiết bị của họ (máy tính cá nhân. - Thông thường người sử dụng chỉ phải sử dụng trình duyệt Web để truy cập các ứng dụng này. - Tất cả ứng dụng đều được lưu trữ và xử lý ở phía đám mây, khách hàng chỉ sử dụng những công cụ đơn giản để truy cập. - Việc này giúp khách hàng dễ dàng sử dụng, không cần thiết phải cài đặt các ứng dụng lên thiết bị, giúp người quản trị, quản lý ứng dụng dễ dàng quản lý, bảo trì, nâng cấp, cải tiến ứng dung. - Ngoài ra, ứng dụng cũng cung cấp những dịch vụ đo lường, giúp người dùng chỉ phải trả tiền cho thời gian sử dụng ứng
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt