Cải tiến thuật toán xử lý truy vấn trên cơ sở dữ liệu đồ thị Neo4j phân tán

Kỷ yếu Hội nghị KHCN Quốc gia lần thứ XII về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR); Huế, ngày 07-08/6/2019 DOI: 10.15625/vap.2019.00010 CẢI TIẾN THUẬT TOÁN XỬ LÝ TRUY VẤN TRÊN CƠ SỞ DỮ LIỆU ĐỒ THỊ NEO4J PHÂN TÁN Phạm Hữu Mão, Ngô Thanh Hùng Trƣờng Đại học Công nghệ Thông tin, Đại học Quốc gia Thành phố Hồ Chí Minh phamhuumaoit@gmail.com, hungnt@uit.edu.vn TÓM TẮT: Cơ sở dữ liệu đồ thị Neo4j được tạo được sự quan tâm lớn trong những năm gần đây nhờ khả năng giải quyết các bài toán liên quan đến mạng ngữ nghĩa và mạng xã hội với kích thước lớn. Một trong những giải pháp để xử lý dữ liệu lớn thường được áp dụng là lưu trữ và xử lý phân tán. Một số nghiên cứu về phân mảnh ngang cơ sở dữ liệu Neo4j đã được đề xuất. Tuy nhiên chưa có nghiên cứu về phân tán cơ sở dữ liệu Neo4j (phân tán cơ sở dữ liệu quan hệ là phân chia tập hợp các node và quan hệ thành các tập con, mỗi tập con sẽ đặt tại một nút mạng, các tập con có thể có giao) và module xử lý truy vấn trên Neo4j phân tán ở mức độ trong suốt cao nhất. Nghĩa là người dùng không cần phải thay đổi ứng dụng (câu truy vấn trong ứng dụng) mà vẫn có thể truy vấn đến cơ sở dữ liệu phân tán giống như trước khi phân tán. Kiến trúc phân tán và thuật toán xử lý truy vấn Cypher trên cơ sở dữ liệu phân tán Neo4j đã được trình bày ở [1]. Thuật toán truy vấn này chỉ xử lý được ba mẫu câu truy vấn cơ bản trong Neo4j, nhưng đáp ứng được hầu hết các nhu cầu của các ứng dụng thực tế. Trong nghiên cứu này chúng tôi đề xuất cải tiến kiến trúc phân tán, và cải tiến hiệu năng của thuật toán xử lý truy vấn Cypher nói trên. Thuật toán cải tiến cho thấy hiệu năng đều cao hơn hoặc bằng so với thuật toán gốc trong tất cả các trường hợp thử nghiệm. Từ khóa: Neo4j, vertical partitioning model on Neo4j, Cypher query proccessing on vertical partitioning Neo4j, Phân tán Neo4j, Xử lý truy vấn Cypher trên Neo4j phân tán. I. GIỚI THIỆU Trong những năm gần đây, nghiên cứu về cơ sở dữ liệu đồ thị Neo4j đã giải quyết đƣợc rất nhiều vấn đề về lƣu trữ và xử lý dữ liệu, trở thành vấn đề đƣợc chú trọng của các nhà nghiên cứu. [2] Khẳng định ƣu thế của cơ sở dữ liệu đồ thị trong các ứng dụng liên quan đến mạng ngữ nghĩa và phân tích mạng xã hội.. [3] Nghiên cứu sử dụng cơ sở dữ liệu đồ thị thay cho cơ sở dữ liệu quan hệ trong việc biểu diễn ontology đa ngành trong lĩnh vực lọc hóa dầu. [4] Sử dụng hệ quản trị cơ sở dữ liệu đồ thị Neo4j để lƣu trữ dữ liệu về việc làm và các thông tin liên quan của sinh viên tốt nghiệp. [5] Đề xuất một mô hình mạng xã hội thời gian thực (time-varying social network model) để mô tả và truy vấn thông tin về con ngƣời và các hoạt động có liên quan trong thời gian thực. Tác giả đã sử dụng hệ quản trị cơ sở dữ liệu đồ thị Neo4j để thực nghiệm mô hình và chứng minh rằng nó hiệu quả hơn nhiều so với sử dụng hệ quản trị cơ sở dữ liệu quan hệ. Bên cạnh đó, việc nghiên cứu các kỹ thuật phân mảnh cơ sở dữ liệu đồ thị cũng đƣợc triển khai. [6] Đề xuất một giải thuật phân mảnh ngang động để giải quyết bài toán hiệu năng truy vấn đối với cơ sở dữ liệu đồ thị kích thƣớc lớn với hàm mục tiêu là tăng độ liên quan giữa các node trong cùng phân mảnh và giảm số lƣợng các cạnh bị cắt edge-cut (là các cạnh mà một node nằm ở phân mảnh này và node ở đầu kia thì nằm ở một phân mảnh khác). Thuật toán đƣợc thử nghiệm trên một hệ thống gồm nhiều hệ quản trị cơ sở dữ liệu đồ thị Neo4j kết nối với nhau qua hệ thống mạng truyền thông. Mỗi hệ quản trị chứa đựng một phân mảnh ngang của cơ sở dữ liệu gốc, đƣợc tính toán nhờ vào thuật toán đề xuất. Ƣu điểm của thuật toán là tự thích ứng với sự thay đổi của dữ liệu cũng nhƣ truy vấn của ngƣời dùng và giúp tăng tính cục bộ của các truy vấn duyệt đồ thị (duyệt trong một phân mảnh) từ đó tăng tốc hiệu năng thực thi và hiệu quả sử dụng bộ nhớ. Bài báo [1] đề xuất một kiến trúc phân tán cho cơ sở dữ liệu đồ thị Neo4j phân tán và xây dựng một module xử lý truy vấn trên kiến trúc đó. Module xử lý truy vấn phân tán đạt mức độ trong suốt cao nhất – trong suốt phân mảnh, nghĩa là ngƣời dùng không cần phải thay đổi ứng dụng (câu truy vấn trong ứng dụng) mặc dù cơ sở dữ liệu đã bị phân mảnh và phân tán trên một hệ thống các hệ quản trị Neo4j độc lập. Qua đó cho thấy ứng dụng cơ sở dữ liệu đồ thị Neo4j cũng nhƣ hệ quản trị cơ sở dữ liệu Neo4j phân tán hiện đƣợc quan tâm nghiên cứu. Tuy nhiên liên quan đến Neo4j phân tán hiện có ít các nghiên cứu xây dựng hệ xử lý truy vấn phân tán ứng với mức trong suốt phân mảnh còn rất ít (chỉ có [1]). Trong nghiên cứu này chúng tôi phân tích để cải tiến kiến trúc phân mảnh dọc và cải tiến thuật toán xử lý truy vấn Cypher trên hệ quản trị cơ sở dữ liệu Neo4j phân tán đƣợc đề xuất ở [1]. II. KIẾN TRÚC PHÂN TÁN CƠ SỞ DỮ LIỆU ĐỒ THỊ NEO4J II.1. Khái niệm phân tán cơ sở dữ liệu đồ thị Phân tán cơ sở dữ liệu đồ thị không phải là phân mảnh các thuộc tính của node hoặc quan hệ mà là phân chia tập hợp các node và quan hệ thành các tập con, mỗi tập con là một phân mảnh. 74 CẢI TIẾN THUẬT TOÁN XỬ LÝ TRUY VẤN TRÊN CƠ SỞ DỮ LIỆU ĐỒ THỊ NEO4J PHÂN TÁN II.2. Kiến trúc hệ quản trị cơ sở dữ liệu phân tán Neo4j Hệ quản trị cơ sở dữ liệu Neo4j phân tán bao gồm nhiều hệ quản trị cơ sở dữ liệu Neo4j hoạt động độc lập liên kết với nhau và với một module xử lý truy vấn phân tán thông qua một mạng truyền thông. Hình 1. Hệ quản trị CSDL Neo4j phân tán Mỗi một hệ quản trị Neo4j trong hệ thống sẽ chứa một phân mảnh của cơ sở dữ liệu gốc (trƣớc khi phân tán). Mỗi mảnh sẽ chứa tất cả các node và một tập con của tập tất cả các quan hệ của cơ sở dữ liệu gốc. Các tập quan hệ con có thể có giao tùy theo nhu cầu thực tế. Đối với cơ sở dữ liệu đồ thị chƣa phân tán thì tất cả các quan hệ nằm trên cùng một máy chủ cùng với thông tin về các nút làm ảnh hƣởng đến việc quản lý tính riêng tƣ và bảo mật dữ liệu. Do đó việc phân tán dữ liệu đi kèm ra các phân mảnh riêng biệt sẽ thuận tiện hơn trong việc quản lý dữ liệu. Bên cạnh đó, việc phân tán cơ sở dữ liệu cũng có thể giúp nâng cao tính sẵn sàng của hệ thống nhờ tránh đƣợc trƣờng hợp “đơn điểm gây lỗi” và trong một số trƣờng hợp còn có thể giảm thời gian truy vấn nhờ giảm dung lƣợng của phân mảnh. Ƣu điểm của thiết kế này chính là: - Phân chia để phân quyền quản lý: mỗi đơn vị quản lý một số quan hệ nào đó thuộc phạm vi quản lý của mình; - Phân chia tải ra các site để tăng hiệu năng: mỗi site quản lý một tập dữ liệu nhỏ hơn và chỉ phục vụ các truy vấn liên quan đến tập các quan hệ này; - Tăng tính sẵn sàng của dữ liệu. Nhƣợc điểm của thiết kế này là: - Trong trƣờng hợp các truy vấn phải sử dụng dữ liệu từ nhiều site thì diễn ra quá trình truyền dữ liệu qua lại giữa các site có liên quan, điều này trong đa số các trƣờng hợp sẽ dẫn đến làm tăng thời gian xử lý so với truy vấn trên cơ sở dữ liệu toàn cục. Đây là nhƣợc điểm chung của thiết kế phân tán. Vì vậy khi thiết kế cơ sở dữ liệu phân tán, nhà thiết kế phải lựa chọn phƣơng án phân mảnh/phân tán sao cho giảm đƣợc tần suất thực hiện các truy vấn liên mảnh/liên site. - Tuy nhiên, trong một số trƣờng hợp, cũng nhờ xử lý song song trên nhiều site mà việc thực hiện truy vấn liên site có thể cho hiệu năng cao hơn (thời gian thực thi ngắn hơn) so với truy vấn trên cơ sở dữ liệu toàn cục. Trong phần thực nghiệm ở nghiên cứu này, chúng tôi cũng quan sát thấy một số trƣờng hợp nhƣ vậy. III. MODULE XỬ LÝ TRUY VẤN CYPHER TRÊN HỆ CƠ SỞ DỮ LIỆU PHÂN TÁN NEO4J III.1. Phát biểu bài toán Cho biết: - Lƣợc đồ phân tán các phân mảnh dữ liệu trên các site nhƣ sau: Phân mảnh 1; Phân mảnh 2; Phân mảnh 3;...; Phân mảnh n: trên các phân mảnh chứa 1 hoặc nhiều quan hệ cùng các node tƣơng ứng. Yêu cầu: - Thực hiện truy vấn Cypher từ ngƣời dùng, trả kết quả cho truy vấn sao cho quá trình thực hiện trên hệ quản trị CSDL phân tán hoàn toàn trong suốt với ngƣời dùng. Phạm Hữu Mão, Ngô Thanh Hùng 75 III.2. Thiết kế các bước xử lý truy vấn Cypher trên cơ sở dữ liệu phân tán Neo4j Các bƣớc xử lý đƣợc thiết kế nhƣ ở hình 2. Trong đó các bƣớc nối truy vấn và tìm tập tối thiểu chính là phần cải tiến đƣợc đề xuất trong nghiên cứu này. Các bƣớc còn lại là kế thừa từ [1]. Hình 2. Sơ đồ thuật toán Mô tả chi tiết các bƣớc xử lý: Bước 1: Phân tích câu truy vấn gốc thành một tập các truy vấn đơn, trong đó mỗi truy vấn đơn chỉ chứa một quan hệ duy nhất, mỗi truy vấn đơn bao gồm tất cả các điều kiện liên quan đến quan hệ đó. Gọi T(r1, r2,, rm) là truy vấn gốc liên quan đến m quan hệ khác nhau từng đôi một r1, r2,, rm, với các R(r1, r2,..., rm) thuộc tập tất cả các quan hệ của cơ sở dữ liệu đồ thị đang xét. Truy vấn T sẽ đƣợc tách thành n truy vấn con: T1, T2,, Tm, mỗi truy vấn con chỉ chứa {r1}, {r2},..., {rm} quan hệ là tập con của R. Bước 2: Xem xét khả năng nối các câu truy vấn đơn thu đƣợc từ bƣớc 1, nếu chúng có chứa quan hệ thuộc cùng một phân mảnh. Tìm tập các câu truy vấn đơn tối thiểu, chọn 1 tập ít nhất chứa đầy đủ các quan hệ trong câu truy vấn gốc. Tập hợp danh sách các quan hệ trên các phân mảnh thu đƣợc ở bƣớc 1, tiến hành xác định các quan hệ trên các câu đơn thuộc phân mảnh nào, mỗi phân mảnh ta sẻ thu đƣợc một tập hợp các câu đơn. Tìm tập tối thiểu từ các tập các câu đơn ở mỗi phân mảnh. Bước 3: Nối các câu đơn chứa trong mỗi tập tối thiểu ở bƣớc 2. Gọi G (T1, T2,, Tm) là tập tối thiểu chứa các câu truy vấn đơn có các quan hệ tƣơng ứng r1, r2,, rm, với các R(r1, r2,..., rm) thuộc tập tất cả các quan hệ của một phân mảnh. Truy vấn T’ đƣợc tạo thành bằng cách nối các câu đơn T1+T2+...+Tm. Bước 4: Gửi tập các câu truy vấn con đến các phân mảnh đích chứa các quan hệ tƣơng ứng, gọi thực thi thông qua GraphDatabaseService API của Neo4j trên từng phân mảnh đó. Tổng hợp kết quả cuối cùng dựa vào phép toán đại số quan hệ có đƣợc khi phân rã truy vấn ban đầu. Mỗi truy vấn con Ti sẽ trả về một kết quả O(Ti). Tổng hợp các kết quả O(Ti) theo các phép toán thu đƣợc từ việc phân rã truy vấn ban đầu, tạo ra kết quả O(T) cho truy vấn gốc T. IV. THỰC NGHIỆM IV.1. Cài đặt hệ cơ sở dữ liệu Neo4j phân tán trên môi trường đám mây Chƣơng trình xử lý truy vấn đƣợc xây dựng dƣới dạng một ứng dụng web. Nền tảng lập trình Java. Giao diện chƣơng trình gồm một hộp thoại cho phép ngƣời dùng nhập truy vấn, nút “Execute” để thực thi chƣơng trình, nút “Remove” dùng để xóa truy vấn hiện tại và các kết quả liên quan. Thành phần bên dƣới có 3 tab: 76 CẢI TIẾN THUẬT TOÁN XỬ LÝ TRUY VẤN TRÊN CƠ SỞ DỮ LIỆU ĐỒ THỊ NEO4J PHÂN TÁN Tab “Result of distributed Neo4j”: Hiển thị kết quả truy vấn trên cơ sở dữ liệu đồ thị phân tán khi nhấn nút “Execute” bao gồm các thông tin nhƣ: số dòng trả về, thời gian thực thi truy vấn và kết quả truy vấn. Tab “Step Execute”: Thể hiện các bƣớc thực thi truy vấn gồm danh sách các tập tối thiểu, danh sách các câu truy vấn sau khi đã nối, danh sách phân mảnh thực hiện truy vấn, các phép toán đại số quan hệ giữa từng cặp câu truy vấn sẽ đƣợc hiển thị một cách cụ thể, và cuối cùng là xuất kết quả cho ngƣời dùng. Tab “Result of undistributed Neo4j”: Hiển thị kết quả truy vấn trên cơ sở dữ liệu không phân tán. Nội dung tab này bao gồm: số dòng trả về, thời gian thực thi truy vấn và kết quả thực thi của câu truy vấn. Hệ thống cơ sở dữ liệu Neo4j phân tán đƣợc cài đặt trên nền tảng điện toán đám mây với cấu hình nhƣ sau: - Có 4 máy chủ ảo. Trên mỗi máy có cài hệ quản trị Neo4j hoạt động độc lập. Mỗi máy có cấu hình: + Nhà cung cấp: Google Cloud + Machine Type: 2 vCPUs, 8 GB memory + OS: Ubuntu 16.04 LTS + Disk Type: Standard persistent disk + Disk Size: 15G Để so sánh kết quả và hiệu năng của hệ cơ sở dữ liệu Neo4j phân tán so với cơ sở dữ liệu Neo4j toàn cục, một máy chủ ảo chứa 1 hệ quản trị cơ sở dữ liệu Neo4j khác cũng đƣợc tạo ra. IV.2. Dữ liệu thử nghiệm Cơ sở dữ liệu Neo4j toàn cục là cơ sở dữ liệu đồ thị Movie gồm các thông tin sau: Nút: - Nút Person có 50179 đỉnh; - Thuộc tính nút Person: id, birthday, birthplace, name, biographsy; - Nút Movie có 12862 đỉnh; - Thuộc tính nút Movie: id, studio, releaseDate, description, language, title, trailer, imageUrl, genre; Quan hệ: - Quan hệ ACTS_IN liên kết nút Person và Movie. - Quan hệ DIRECTED liên kết nút Person và Movie. - Quan hệ FRIEND liên kết nút Person và Person. - Quan hệ RATED liên kết nút Person và Movie. Thông tin quan hệ: - ACTS_IN: liên kết nút Person và Movie. Dùng để chỉ định diễn viên trong một bộ phim nào đó. Đây là quan hệ có hƣớng với đỉnh đầu là nút Person, đỉnh cuối là nút Movie. - DIRECTED: liên kết nút Person và Movie. Dùng để chỉ định đạo diễn của một bộ phim nào đó. Đây là quan hệ có hƣớng với đỉnh đầu là nút Person, và đỉnh cuối là nút Movie. - FRIEND: liên kết nút Person và Person. Dùng để chỉ định mối quan hệ bạn bè giữa hai ngƣời. Đây là quan hệ có hƣớng với đỉnh đầu là nút Person, và đỉnh cuối là nút Person. - RATE: liên kết nút Person và Movie. Dùng để chỉ định ngƣời bình chọn cho một bộ phim nào đó. Đây là quan hệ có hƣớng với đỉnh đầu là nút Person, và đỉnh cuối là nút Movie. Để thực hiện thử nghiệm cơ sở dữ liệu này đƣợc đặt trên hệ quản trị Neo4j tập trung. Đồng thời một bản copy các phân mảnh của nó đƣợc đặt trên các Neo4j phân tán nhƣ sau: Cơ sở dữ liệu này sẽ đƣợc phân tán trên 3 phân mảnh: - Phân mảnh 1: (Movie1) chứa toàn bộ quan hệ ACTS_IN và toàn bộ nút Person, nút Movie. - Phân mảnh 2: (Movie2) chứa toàn bộ quan hệ ACTS_IN, FRIEND và toàn bộ nút Person, nút Movie. - Phân mảnh 3: (Movie3) chứa toàn bộ quan hệ FRIEND, RATE, DIRECTED và toàn bộ nút Person, Movie. Tập các câu truy vấn Cypher sử dụng để thử nghiệm đƣợc tổng hợp từ nhiều trang web khác nhau, một số câu truy vấn đƣợc tạo ra bởi chính tác giả nhằm thể hiện đƣợc ƣu điểm hoặc nhƣợc điểm của hệ thống phân tán so với tập trung. IV.3. Kết quả và đánh giá Kết quả thực nghiệm 10 câu truy vấn trong tổng 70 câu truy vấn: Phạm Hữu Mão, Ngô Thanh Hùng 77 Bảng 1. Kết quả thực nghiệm Stt Thời gian xử lý trên Neo4j tập trung (s) Thời gian xử lý trên Neo4j phân tán [1] (s) Thời gian xử lý trên Neo4j phân tán cải tiến (s) 1 4.876) 8.481 4.992 2 6.064 8.972 5.939 3 3.241 5.728 2.925 4 15.499 22.036 12.775 5 3.229 6.073 2.370 6 3.081 16.003 9.183 7 3.239 5.102 2.957 8 2.791 2.526 2.795 9 4.333 4.467 3.902 10 4.333 4.467 3.902 V. KẾT LUẬN Nghiên cứu đã đề xuất một cải tiến đối với thuật toán xử lý truy vấn Cypher trên cơ sở dữ liệu Neo4j phân tán và cài đặt một hệ cơ sở dữ liệu đồ thị Neo4j phân tán. Khả năng xử lý truy vấn phân tán của hệ thống hỗ trợ mức trong suốt ở mức cao nhất giúp ngƣời dùng không tốn công sức viết lại ứng dụng sau khi thiết kế phân tán cơ sở dữ liệu. Hệ cơ sở dữ liệu đồ thị Neo4j phân tán đã đƣợc kiểm nghiệm với dữ liệu mẫu Movie và cho thấy kết quả rất khả quan. Đa phần các câu truy vấn không kém nhiều so với khi truy vấn tập trung và trong một số trƣờng hợp, nhờ có xử lý phân tán mà hệ thống phân tán đã cho kết quả tốt hơn cả hệ tập trung. Mặc dù vậy thuật toán vẫn có thể đƣợc cải thiện hơn ở khâu tìm tập nhỏ nhất của các tập nối, cũng nhƣ tính tới đặc trƣng của dữ liệu hiện có để tăng hiệu năng hơn nữa. Đó là những hƣớng cải tiến thuật toán tiềm năng. TÀI LIỆU THAM KHẢO [1] Nguyễn Duy Tân, Ngô Thanh Hùng “Xây dựng module xử lý truy vấn phân tán trên hệ quản trị cơ sở dữ liệu đồ thị Neo4j ” Kỉ Yếu Hội Nghị Quốc Gia Lần Thứ X Về Nghiên Cứu Cơ Bản và Ứng Dụng Công Nghệ Thông Tin (FAIR), Đà Nẵng 17-18/08/2017. [2] Guia, J., Soares, V. G., & Bernardino, J. (2017). Graph Databases: Neo4j Analysis. In ICEIS (1) (pp. 351-356). [3] Gong, F., Ma, Y., Gong, W., Li, X., Li, C., & Yuan, X. (2018). Neo4j graph database realizes efficient storage performance of oilfield ontology. PloS one, 13(11), e0207595. [4] Constantinov, C., Iordache, L., Georgescu, A., Popescu, P. S., & Mocanu, M. (2018, October). Performing Social Data Analysis with Neo4j: Workforce Trends & Corporate Information Leakage. In 2018 22nd International Conference on System Theory, Control and Computing (ICSTCC) (pp. 403-406). IEEE. [5] Cattuto, C., Quaggiotto, M., Panisson, A., & Averbuch, A. (2013, June). Time-varying social networks in a graph database: a Neo4j use case. In First international workshop on graph data management experiences and systems (p. 11). ACM. [6] Nicoara, D., Kamali, S., Daudjee, K., & Chen, L. (2015, March). Hermes: Dynamic Partitioning for Distributed Social Network Graph Databases. In EDBT (pp. 25-36). IMPROVE QUERY ALGORITHMS ON A DISTRIBUTED GRAPH DATABASE Pham Huu Mao, Ngo Thanh Hung ABSTRACT - Neo4j graph database has created great interest in recent years with the ability to solve problems related to semantic networks and social networks with large size. One of the solutions to large data processing is commonly applied is distributed storage and processing. A number of studies on horizontal fragmentation of Neo4j database have been proposed. However, there has not been any research on dispersion of Neo4j database (dispersion of relational database is to divide the set of nodes and relations into subsets, each subset will be located at a node, the set children can be delivered) and the query processing module on Neo4j disperses at the highest transparency level. This means that the user does not need to change the application (the query in the application) but can still query the distributed database just like before it is distributed. Distributed architecture and Cypher query processing algorithm on Neo4j distributed data are presented in [1]. This query algorithm only handles three basic query patterns in Neo4j, but meets most of the needs of actual applications. In this study we propose to improve the distributed architecture, and improve the performance of the above mentioned Cypher query processing algorithm. The improved algorithm shows that the performance is higher or equal to the original algorithm in all test cases.