Đây là phần đầu tiên trong series bài viết giới thiệu về cơ sở dữ liệu dạng đồ thị (Graph SQL), một trong bốn phân nhánh chính của NoSQL, cụ thể ở đây mình sẽ dùng Neo4j, một graph database được sử dụng phổ biến rộng rãi và tương đối dễ học vì được viết Document khá đầy đủ.
1. Một số vấn đề của RDBMS và sự cần thiết của cơ sở dữ liệu đồ thị
2. Hướng dẫn làm quen với việc tạo và truy vấn đồ thị trong Neo4j
3. Lập trình Neo4j trong Laravel Framework của PHP
4. Viết một ứng dụng Recommendation bằng Neo4j và Laravel
Trong phần đầu tiên này, mình sẽ nói về một số vấn đề của cơ sở dữ liệu quan hệ và sự cần thiết của Graph SQL, phần này phải giải thích nhiều lý thuyết, nên tương đối dài dòng nhiều chữ, các bạn có thể chuyển ngay sang phần 2 để xem cách sử dụng Neo4j hoặc chuyển sang phần 3 để xem hướng dẫn tương tác Neo4j với thư viện Laravel 5.3 của PHP, nhưng nếu bạn là người mới với Graph SQL thì bạn nên xem qua để có thể hình dung được vấn đề từ đầu.
Một số vấn đề của RDBMS và sự cần thiết của cơ sở dữ liệu đồ thị
1. Định nghĩa đồ thị
Như chúng ta đều biết, khoa học máy tính có liên quan rất chặt chẽ với toán học. Rất nhiều khái niệm trong lập trình đến từ toán học. Và một trong số những topic quan trọng nhất, ứng dụng nhiều nhất trong số đó chính là lý thuyết đồ thị. Định nghĩa đơn giản nhất về đồ thị là một cấu trúc gồm các đỉnh và các cạnh nối các đỉnh đó lại với nhau. Một đồ thị đơn giản nhất sẽ như hình vẽ sau:
Ở hình trên là dạng đồ thị phổ biến khi chúng ta được học ở các trường đại học, nhưng nó chỉ là một dạng tối giản nhất của một đồ thị. Nhìn chung, một đồ thị thực tế thì các đỉnh và các cạnh sẽ chứa đựng nhiều thông tin hơn, nó chứa đựng rất nhiều thông tin rời rạc mà không nhất thiết lúc nào cũng phải đồng nhất định dạng. Hình sau là một ví dụ:
Như hình trên, các đỉnh (hình tròn) cùng mô tả đối tượng “người” nhưng có tên các thuộc tính khác nhau “age” vs “company” (chú ý không nhầm với giá trị thuộc tính). Do vậy đồ thị phản ánh một cách khách quan nhất về thế giới tự nhiên, không phải thông tin của bất kì đối tượng nào cũng nhất thiết phải đồng dạng mặc dù có thể chúng có cùng chủng loại. Đồ thị chỉ cần thể hiện:
- Có bao nhiêu đối tượng?
- Mỗi đối tượng có những thuộc tính và giá trị gì
- Mối quan hệ của chúng với các đối tượng khác như thế nào.
Một ví dụ về đồ thị gần gũi hơn trong lĩnh vực công nghệ phần mềm, chính nhưng bản thiết kế phần mềm của chúng ta cũng đã sử dụng rất nhiều dạng đồ thị khác nhau.
Mặc dù đồ thị được sử dụng rộng rãi trong các quá trình phát triển phần mềm nhưng các nhà phát triển thường quên rằng chúng cũng được sử dụng trong việc lưu trữ dữ liệu. Chúng ta thường cố gắng mô tả các đối tượng của bài toán thành các bảng (table) với các thuộc tính (columns) sau đó tạo ra các mối quan hệ giữa các bảng, đôi khi cần thêm các bảng mới để mô tả các mối quan hệ đó. Khi chúng ta làm điều đó thì vô hình chung chúng ta đang làm mất đi tính tự nhiên của bài toán. Trong phần tới chúng ta sẽ tìm hiểu kĩ hơn về vấn đề này.
2. Vấn đề với cơ sở dữ liệu quan hệ
Một ví dụ điển hình có trong hầu hết các hệ thống CMS đó là “Bảng kiểm soát truy cập – Access Control List”. Như thông thường khi thiết kế với RDBMS chúng ta sẽ có các bảng:
usersrolesresourceshas_rolesđể map users với rolesaccessibleđể maprolesvớiresources.
Vậy ta cần ít nhất 5 bảng để mô hình hóa bài toán này mà thực chất trong tự nhiên nó chỉ có 3 loại đối tượng với 2 mối quan hệ has_roles (user X có role Y ) hoặc accessible (role Y có thể truy cập resource Z), đó chính là một dạng đồ thị. Sau đó chúng ta lại dùng các ORM Framework để map databases này thành các object model (các class) trong code. Tuy nhiên lần này 2 bảng vừa được thêm mới là has_roles và accessible lại bị lược bỏ, không được khai báo tường minh như một lớp cụ thể.
Ví dụ ORM với Hibernate framework trong Java:
public class User {
@ManyToMany(mappedBy="users")
public Set<User> getRoles() {
return this.roles;
}
}
public class Role {
@JoinTable(name="has_role", joinColumns=@JoinColumn(name="role_id"), inverseJoinColumns=@JoinColumn(name="user_id"))
public Set<User> getUsers() {
return this.users;
}
}
}
Ví dụ ORM với Eloquent của Laravel PHP Framework:
class User extends Model {
public function roles() {
return $this->morphToMany('App\Role', 'has_roles');
}
}
class Role extends Model {
public function users() {
return $this->morphedByMany('App\User', 'has_roles');
}
}
Các object models này lại là một dạng đồ thị khác vì các object model sẽ có thể thể hiện các quan hệ kế thừa (inheritance), cấu thành (composition) trong khai báo của mình (các quan hệ này sẽ có thể vẽ lại thành đồ thị).
Vậy là từ một bài toán đơn giản. Chúng ta biến một dạng dữ liệu đồ thị (3 đối tượng, 2 quan hệ) thành dạng bảng không phải thực sự là đồ thị (vì có những bảng không phải đối tượng thực) rồi lại chuyển lại về dạng đồ thị với ORM.
Chúng ta đã bắt đầu nhận ra tính dư thừa khi thao tác với RDBMS. Hơn nữa ORM chỉ là ẩn đi độ phức tạp bề ngoài khi lập trình, còn bản chất khi truy vấn chúng vẫn cần phải truy vấn vào các bảng liên hợp để lấy thông tin các đối tượng khi người dùng có yêu cầu, chẳng hạn để tìm “Các roles của userX“ với dòng code roles = userX.getRoles(); thì ORM vẫn phải JOIN 3 bảng users, has_roles và roles để tìm các role như sau:
SELECT roles.*
FROM users INNER JOIN has_roles ON users.id = has_roles.user_id
INNER JOIN roles ON has_roles.role_id = roles.id
WHERE users.name = 'X'
Do cần rât nhiều lệnh JOIN nên sẽ có vấn đề thực sự với hiệu năng đối với một số bài toán cụ thể. Sau đây chúng ta sẽ nhìn thấy một ví dụ mà việc sử dụng RDBMS cho hiệu năng rất thấp và gần như là không thể sử dụng với dữ liệu tương đối lớn. Bài toán chúng ta sẽ nghiên cứu đó là bài toán điển hình trong một social network, “Tìm bạn của bạn”.
3. Một bài toán nên dùng cơ sở dữ liệu đồ thị
Ta có một đồ thị mô phỏng mạng xã hội như sau:
Chú ý: Ở đây để đúng ngữ nghĩa và tiện cho viết query trong CSDL quan hệ thì chúng ta coi một mối quan hệ bạn bè là quan hệ song hướng, nghĩa là A và B là bạn của nhau thì phải có 2 mũi tên ngược chiều nối A và B trong CSDL. Để đồ thị dễ nhìn thì chúng ta chỉ để 1 mũi tên. Với bài toán này ta sẽ có CSDL quan hệ tương ứng như sau:
- Với yêu cầu “Tìm số lượng bạn của bạn của user có id = 2” thì truy vấn của chúng ta là như sau:
SELECT COUNT(distinct uf_2.user1_id)
FROM user_friends uf_1
INNER JOIN user_friends uf_2 ON uf_1.user1_id = uf_2.user2_id WHERE uf_1.user1_id = 2
- Tăng thêm độ khó lên một chút, lần này chúng ta tìm: “Số lượng bạn của bạn của bạn của user có id = 2”.
SELECT COUNT(distinct uf_3.user1_id)
FROM user_friends uf_1
INNER JOIN user_friends uf_2 ON uf1.user1_id = uf_2.user2_id
INNER JOIN user_friends uf_3 ON uf2.user1_id = uf_3.user2_id WHERE uf_1.user1_id = 2
Tương tự với các độ sâu khác của truy vấn (mỗi lần có xuất hiện cụm từ “bạn của” là 1 level) mỗi lần ta sẽ phải thêm một lần JOIN. Thực nghiệm:
- Số lượng bản ghi là
1.000users - Mỗi users có
50người bạn - Vậy bảng user_friends sẽ có
1.000x50=50.000bản ghi - Chú ý: mối quan hệ là song hướng nên A là bạn B khác B là bạn A, do đó bảng user_friends chỉ cần nhân tuyến tính 1.000 x 50
Kết quả khi thử nghiệm với MySQL và Neo4j là như sau:
Bản thân Neo4j như tên nó chỉ ra được cài đặt bằng Java (4j = For Java) không thể nhanh bằng C hay C++ như của MySQL, nhưng sự khác biệt về tốc độ ở đây chính là chiến lược trong việc xử lý truy vấn.
Với RDBMS thì quy trình xử lý truy vấn sẽ là:
- Nhân tích Descartes các bảng (user_friends) rồi duyệt lần lượt (có thể không theo thứ tự, nhưng phải hết danh sách) nên ta sẽ có cần 50.000 x 50.000 = 2,5 tỉ phép duyệt với độ sâu 2 và 125.000 tỉ với độ sâu 3, v.v...
- Mỗi phép duyệt sẽ thực hiện so sánh trên mệnh đề ON,WHERE) chỉ để đưa ra khoảng 900 kết quả với bài toán độ sâu là 2.
Trong khi đó thì Neo4j sẽ duyệt theo:
- Lần lượt các đỉnh của đồ thị (mỗi đỉnh tương ứng với một User).
- Tại mỗi đỉnh tìm tiếp đỉnh gần nhất có quan hệ là bạn của đỉnh đang xét và duyệt sâu xuống theo đỉnh đó (Giả sử theo chiến lược đơn giản nhất là DFS – Depth First Search). Khi đạt được độ sâu mong muốn (giả sử 2) tiếp tục với đỉnh gần thứ nhì có quan hệ là bạn của đỉnh đang xét này, v.v...
- Khi gặp đỉnh không thỏa mãn điều kiện (IS_FRIEND_OF đỉnh trước đó) thì nó sẽ không duyệt sâu xuống tiếp nên loại bỏ được rất nhiều phân nhánh dư thừa dẫn đến bỏ qua được hàng triệu những phép duyệt không cần thiết nên tốc độ vẫn được đảm bảo dù ta có tăng độ sâu hoặc tăng số lượng bản ghi lên chăng nữa.
Ở đây ta chú ý là khi ở độ sâu 4 và 5 tốc độ Neo4j vẫn không đổi do:
- Số lượng bản ghi tương đối thấp là 1000 Users nên nó sẽ chỉ tìm được tối đa 999 kết quả.
- Gần như ở mức độ sâu 3 đã ra 999 nên dù có tăng độ sâu lên 4,5,6... đi chăng nữa thì vẫn chỉ tìm được từng đấy kết quả.
- Do là duyệt theo kiểu đồ thị nên nó ảnh hưởng rất nhiều vào số lượng kết quả trả về vì số các nhánh phải tìm tỉ lệ thuận với số lượng kết quả đó.
- => Nên nếu độ sâu càng cao, lẽ ra càng phải ra nhiều kết quả, càng phải tốn thời gian hơn thì không được phản ánh đầy đủ ở đây. Nếu số lượng bản ghi lên đến hàng triệu Users thì con số sẽ phản ánh chính xác hơn.
Kết luận
Tóm lại qua phần đầu tiên này mình muốn thể hiện một vài ý tưởng cơ bản để các bạn có thể hiểu được phần nào CSDL dạng đồ thị có tác dụng gì và ứng dụng trong bài toán nào để khắc phục nhược điểm của RDBMS. Nói như vậy không có nghĩa là nó mạnh mẽ vượt trội và thay thế hoàn toàn RDBMS, RDBMS chắc chắn vẫn sẽ có những chỗ đứng riêng của mình trong thế giới công nghệ dù có thêm bao nhiêu loại NoSQL ra đời đi chăng nữa.
Để biết thêm về cách sử dụng, khi nào thì sử dụng, cách tối ưu truy vấn và thiết kế cũng như các best practise thì mời các bạn đón xem các phần kế tiếp. Trong phần tiếp theo mình sẽ giới thiệu các cú pháp truy vấn cơ bản của Neo4j trước khi hướng dẫn sử dụng nó trong một ngôn ngữ cụ thể (ở đây là PHP) và viết 1 ứng dụng thực tế về 1 Recommendation App sử dụng Neo4j.
