CHƯƠNG I. Giới thiệu vấn đề cần nghiên cứu Một truy vấn k láng giềng gần nhất (kNN) là một loại truy vấn cơ bản trong dữ liệu không gian, cho phép xác định được k điểm gần nhất của một điểm trong tập dữ liệu cho trước. Một truy vấn tất cả k láng giềng gần nhất (AkNN) là một dạng mở rộng của truy vấn kNN, thay vì chỉ tìm k điểm gần nhất cho một điểm được yêu cầu thì ở đây nó sẽ xác định k điểm gần nhất cho mỗi điểm trong tập dữ liệu. Bài toán AkNN đã được ứng dụng rất nhiều trong thực tế.
Điện thoại thông minh ngày nay được trang bị rất nhiều cảm biến như là wifi, GPS … và những chức năng này cho phép người dùng dễ dàng xác định vị trí của họ ở bất cứ nơi nào. Điều này tạo nên một sự đột phá trong lĩnh vực ứng dụng và dịch vụ di dộng dựa trên địa điểm. Một ví dụ điển hình là một dịch vụ dựa trên địa điểm ứng với mỗi người dùng sẽ đề xuất cho họ những người dùng gần nhất mà họ có thể kết bạn. Dựa vào thông tin địa điểm được lưu trữ trong cơ sở dữ liệu, chúng ta có thể đưa ra danh sách những đề xuất bằng cách sử dụng một truy vấn AkNN trên cơ sở dữ liệu đó.
Dịch vụ Nearby của Facebook là một tính năng cho biết bạn bè của bạn đang ở đâu và vào lúc nào. Nếu bạn đang ở một điểm mà có bạn bè của bạn ở gần, ứng dụng sẽ tự động gửi thông báo cho bạn biết để bạn có thể gửi tin nhắn hoặc gặp gỡ… Mỗi người sử dụng dịch vụ này được xem như là một đối tượng cần tìm kNN trong bài toán AkNN và cùng một thời điểm ứng dụng sẽ trả về cho mỗi người dùng danh sách bạn bè gần họ nhất mà cũng đang sử dụng dịch vụ này. Với số lượng người dùng sử dụng Facebook rất lớn trên toàn thế giới, bài toán AkNN có thể áp dụng hiệu quả trong trường hợp này. Bên cạnh đó, ngày nay với sự phát triển ngày càng cao về mặt dân số đi kèm với tốc độ phát triển các dịch vụ và cơ sở hạ tầng thì việc áp dụng bài toán AkNN trong phân bổ tài nguyên và quy hoạch đô thị, ví dụ như xác định kho hàng gần nhất cho mỗi siêu thị hoặc tìm những bãi đậu xe gần nhất cho mỗi trạm tàu điện ngầm… sẽ giúp tối ưu hơn về chi phí tính toán cũng như nguồn nhân lực.
Ở đây mỗi đối tượng cần được quy hoạch như siêu thị, trạm tàu điện ngầm có thể xem như là mỗi đối tượng cần tìm kNN trong bài toán AkNN. Trong lĩnh vực thiết kế kiến trúc máy tính, khả năng hoạt động và tốc độ của những mạch lớn phụ thuộc vào khoảng cách tương đối giữa các thành phần khác nhau trong CAO HỮU VŨ LAM 1 LUẬN VĂN CAO HỌC chúng. Bài toán AkNN được áp dụng để phát hiện ra những điểm bất thường và hướng dẫn bố trí lại vị trí của chúng. Một cách tiếp cận đơn giản nhất của bài toán AkNN là với mỗi điểm trên tập dữ liệu đang xét, lần lượt áp dụng truy vấn kNN cho chúng.
Độ phức tạp của bài toán trong trường hợp này sẽ là O(n2) với n là tổng số điểm trong tập dữ liệu. Cách giải quyết này thì khá đơn giản và dễ hiện thực. Tuy nhiên dễ dàng nhận thấy trong trường hợp tập dữ liệu có khối lượng lớn thì chi phí tính toán sẽ rất cao. Vấn đề được đặt ra ở đây là làm thế nào chúng ta có thể xử lý hiệu quả bài toán AkNN trên tập dữ liệu có khối lượng lớn.
Trong thực tế đã có nhiều thuật toán rất hiệu quả cho AkNN trong việc xử lý dữ liệu tập trung. Tuy nhiên ở đây chúng ta chỉ tập trung giải quyết bài toán AkNN trên tập dữ liệu có khối lượng lớn và được phân tán trên nhiều máy chủ, cũng là một xu hướng đang rất được quan tâm ngày nay. Trong ví dụ đã nêu trên, số lượng người dùng có thể rất lớn và thông tin người dùng có thế sẽ được lưu trữ phân tán trong nhiều máy chủ. Trong những trường hợp như vậy, chúng ta cần xem xét lựa chọn những công nghệ và kỹ thuật hỗ trợ thực thi câu truy vấn hiệu quả.
Trong đó MapReduce là một nền tảng cơ bản hứa hẹn cho việc xử lý dữ liệu có khối lượng lớn trong môi trường phân tán và song song. Mục tiêu, giới hạn và đối tượng nghiên cứu I. Mục tiêu Mục tiêu chính cần đạt được của đề tài nghiên cứu cụ thể như sau: - Xây dựng một công cụ xử lý truy vấn cho phép trả về k láng giềng gần nhất của tất cả các đối tượng dạng điểm trên tập dữ liệu nhiều chiều. - Công cụ có khả năng xử lý dữ liệu có khối lượng lớn dựa trên kỹ thuật xử lý phân tán và song song.
- Cải tiến để tối ưu tài nguyên sử dụng trong quá trình thực thi về mặt thời gian và không gian. Giới hạn Phạm vi của bài toán AkNN rất đa dạng, từ việc có thể không cần quan tâm đến khối lượng dữ liệu cho đến việc dữ liệu có kích thước rất lớn, từ môi trường lưu trữ của dữ liệu là tập trung cho đến việc phân tán dữ liệu… CAO HỮU VŨ LAM 2 LUẬN VĂN CAO HỌC Trong nghiên cứu này, chúng ta giới hạn lại phạm vi ở các nội dung sau: - Kiểu dữ liệu là dữ liệu không gian, cụ thể là các đối tượng dạng điểm được lưu trữ theo tọa độ. - Dữ liệu có khối lượng lớn. - Dữ liệu có thể được lưu trữ phân tán và xử lý song song.
Đối tượng nghiên cứu Đối tượng chính cần nghiên cứu cụ thể như sau: - Các phương pháp xử lý truy vấn AkNN, đặc biệt tập trung tới các phương pháp có khả năng hiện thực trên tập dữ liệu có khối lượng lớn đa chiều, môi trường dữ liệu được lưu trữ phân tán và xử lý song song. - Cơ sở dữ liệu không gian, một loại cơ sở dữ liệu hỗ trợ tốt cho việc lưu trữ và truy xuất dữ liệu mà đối tượng được định nghĩa ở dạng không gian tọa độ. Hầu hết các cơ sở dữ liệu không gian cho phép chúng ta lưu trữ và biểu diễn dễ dàng những đối tượng ở dạng điểm. - Các kỹ thuật và công nghệ cung cấp những công cụ, cơ sở hạ tầng để tạo ra những giải pháp quản lý dữ liệu phân tán giữa nhiều máy chủ và hỗ trợ việc tính toán song song.
Trong đó tập trung nghiên cứu để hiện thực bài toán trên MapReduce, một nền tảng cơ bản cho việc xử lý dữ liệu có khối lượng lớn trong môi trường phân tán và song song. CAO HỮU VŨ LAM 3 LUẬN VĂN CAO HỌC CHƯƠNG II. CƠ SỞ LÝ THUYẾT II. Nền tảng Hadoop MapReduce II.
MapReduce MapReduce là một nền tảng hỗ trợ xử lý song song các tập dữ liệu lớn. MapReduce sử dụng một số lượng lớn các máy tính (node), được gọi là cụm (cluster) nếu tất cả các node ở trong cùng một mạng và sử dụng phần cứng giống nhau hoặc grid nếu các node nằm trên hệ thống phân tán và sử dụng nhiều phần cứng khác nhau. Quá trình xử lý có thể diễn ra trên dữ liệu được chứa trong hệ thống file (không cấu trúc) hoặc trong cơ sở dữ liệu (có cấu trúc). MapReduce có thể tận dụng vị trí của dữ liệu, xử lý nó trên bộ chứa ở gần để giảm khoảng cách truyền nhận.
- Bước "Map": Mỗi node sẽ thực thi hàm “map()” trên dữ liệu cục bộ, và ghi đầu ra vào bộ chứa tạm thời. - Bước "Shuffle": Dữ liệu được phân phối dựa trên key của đầu ra (tạo bởi hàm map()), sao cho tất cả các dữ liệu có cùng key được đặt cùng một node. - Bước "Reduce": Mỗi node xử lý mỗi nhóm của dữ liệu song song cùng lúc. Hình 1: Mô hình xử lý MapReduce MapReduce cho phép xử lý phân tán các hoạt động map và reduce.
Mỗi hoạt động map là độc lập với những map khác, tất cả các map có thể được thực hiện song song. Mặc dù trong thực tế, nó sẽ bị giới hạn bởi số lượng nguồn dữ liệu và số lượng CPU gần nguồn. Tương tự, một tập các reducer sẽ thực hiện bước reduce, tất cả các đầu ra CAO HỮU VŨ LAM 4 LUẬN VĂN CAO HỌC có cùng key được thực hiện ở cùng reducer. Vì vậy, MapReduce có thể được ứng dụng cho dữ liệu lớn.
Cơ chế song song cũng cho phép khả năng phục hồi những lỗi cục bộ của server hoặc bộ chứa suốt quá trình hoạt động: nếu một map hay reducer bị lỗi, công việc có thể được thực hiện lại trong khi dữ liệu đầu vào vẫn còn. Theo môt cách nhìn khác, MapReduce là một tính toán song song và phân tán gồm năm bước: - Chuẩn bị đầu vào cho Map() – Hệ thống MapReduce chỉ định số lượng bộ xử lý, gán dữ liệu đầu vào cho mỗi bộ xử lý. - Thực thi hàm Map() của người dùng – Map() được chạy một lần cho mỗi K1 key-value, sinh ra đầu ra bởi K2 key-value. - Shuffle đầu ra của Map tới Reducer – Hệ thống MapReduce chỉ định số lượng bộ xử lý cho Recude, gán K2 key-value cho mỗi bộ xử lý.
- Thực thi hàm Reduce() của người dùng – Reduce() được chạy một lần cho mỗi K2 key-value, được tạo ra bởi bước Map. - Tạo đầu ra cuối cùng – Hệ thống MapReduce tập hợp tất cả các đầu ra của Reduce, sắp xếp chúng theo K2 để tạo ra kết quả cuối cùng. Các bước này có thể được xem như chạy tuần tự, mỗi bước bắt đầu chỉ sau khi bước trước đó hoàn thành, mặc dù trong thực tế chúng có thể xen kẽ mà không ảnh hưởng kết quả cuối cùng. Những thành phần của nền tảng MapReduce bao gồm: - Input reader: Chia đầu vào thành những phần thích hợp và hệ thống gán mỗi phần tới mỗi Map.
Input reader đọc dữ liệu từ bộ chứa ổn định, thường là hệ thống phân tán và sinh ra các cặp key-value. - Map: Chức năng Map nhận một chuỗi các cặp key-value, xử lý từng cặp và sinh ra các cặp key-value đầu ra. Loại đầu vào và đầu ra có thể khác nhau. - Partition: Mỗi đầu ra của Map được đặt vào một reducer nào đó bởi hàm partition.
Hàm partition sẽ nhận key và số lượng reducer và trả về index của reducer mong đợi. Hàm partiton phải tạo ra phân phối xấp xỉ chuẩn của dữ liệu để cân bằng tải, nếu không hoạt động của MapReduce có thể bị treo để chờ những reducer chậm kết thúc.
