Chào mừng các bạn đến với series “Thanh tra ma giáo” – chuỗi bài viết chuyên về điều tra và đánh giá các công nghệ trên thị trường hiện nay: liệu chúng có thật sự được như lời quảng cáo hay không? Hay đó chỉ là các chiêu trò ma giáo, bánh vẽ marketing nhằm đánh lừa người dùng. Mở đầu cho series lần này, tôi xin được trân trọng giới thiệu ứng viên đầu tiên: Dgraph – đang nằm trong top 10 Graph Database của bảng xếp hạng DB-Engine tính tới thời điểm hiện tại của bài viết.

Các chi tiết kỹ thuật được tôi trích dẫn từ chính Whitepaper gốc của DGraph, chứ không hề hóng hớt từ bất kỳ các nguồn fake news nào khác. Chi tiết Whitepaper anh em có thể xem tại đây (hoặc link dự phòng).

1. Điểm khác biệt của Dgraph:

Dgraph solves the join depth problem with a unique sharding mechanism. Instead of sharding by entities, as most systems do, Dgraph shards by relationships. Dgraph’s unique way of sharding data is inspired by research at Google, which shows that the overall latency of a query is greater than the latency of the slowest component. The more servers a query touches to execute, the slower the query latency would be. ^[1] By doing relationship based sharding, Dgraph can execute a join or traversal in a single network call (with a backup network call to replica if the first is slow), irrespective of the size of the cluster or the input set of entities. ^[2] Dgraph executes arbitrary-depth joins without network broadcasts or collecting data in a central place.
…
For a query which asks for [people who live in SF and eat Sushi], Dgraph would execute one network call to server containing lives in and do a single lookup for all the people who live in SF. In the second step, it would take those results and send them over to server containing eats, do a single lookup to get all the people who eat Sushi, and intersect with the previous step’s result set to generate the final list of people from SF who eat Sushi. In a similar fashion, this result set can then be further filtered/joined, each join executing in one network call.

Tôi sẽ giải thích một chút cho đoạn trên: Dữ liệu trong Graph thông thường sẽ được biểu diễn dưới dạng triplet Subject -> Predicate -> Object, hay còn gọi là [S P O] .

Graph Database truyền thống sẽ hash partition theo entity (tức là S và O). Khi cần truy vấn [? P O], server sẽ broadcast (fanout) request tới tất cả các node, rồi gather lại kết quả danh sách [S]. Điều này dẫn tới tỉ lệ P99 cao vì thời gian response phụ thuộc vào tốc độ của node chậm nhất.

Trong khi đó, Dgraph hash partition theo relation (tức là P). Khi truy vấn [? P O] , server chỉ cần call tới 1 partition duy nhất để lấy ra danh sách kết quả.

Hãy lưu ý ở trích dẫn ^[1]:

By doing relationship based sharding, Dgraph can execute a join or traversal in a single network call...

Ưu điểm và nhược điểm:

Ưu điểm:

• Truy vấn theo predicate về lý thuyết là nhanh hơn so với các Graph Database truyền thống. Ví dụ câu lệnh minh họa:

Liệt kê danh sách các user đang sống tại Hà Nội.

Nhược điểm:

• Ngược với Graph Database truyền thống: Dữ liệu Entity của Dgraph bị rải rác trên nhiều partition, dẫn tới truy vấn thông tin của 1 Entity bị chậm do vấn đề fanout request. Ví dụ như sau:

Liệt kê toàn bộ các thông tin hiện đang có của user_123

+ Node 0: [user_123 - sống tại - Hà Nội], [user_123 - quê - Hải Dương]
+ Node 1: [user_123 - giới tính - nam]
+ Node 2: [user_123 - độ tuổi - 25_35]
+ …

Dgraph executes arbitrary-depth joins without … collecting data in a central place... each join executing in one network call.

Liệt kê danh sách các user là nữ, quê ở Hải Dương và đang sống tại Hà Nội.
Cách Dgraph đang sử dụng:
→ Node 1: […? - giới tính - nữ] = danh sách các user là nữ
→ Node 0: 
     → […? - quê - Hải Dương] = danh sách các user là nữ, quê ở Hải Dương
     → […? - sống tại - Hà Nội] = danh sách các user là nữ, quê ở Hải Dương và đang sống tại Hà Nội

2. Consistency and Availability

Dgraph automatically shards data into machines, as the amount of data or the number of servers change, and automatically reshards data to move it across servers to balance the load.
…
While this process sounds pretty straighforward, there are many race and edge conditions here which can cause transactional correctness to be violated as shown by Jepsen tests.
…
Future work here is to allow writes during the shard move, which depending upon the size of the shard can take some time.

Ưu điểm và nhược điểm:

Ưu điểm:

• Automatically reshard giúp giảm bớt nhân công cho việc giám sát và maintance DB.

Nhược điểm:

• Dgraph follow CP (trong lý thuyết CAP): trong quá trình rebalance, Dgraph sẽ đánh dấu shard là read-only, chấp nhận bỏ qua hỗ trợ high availability.
• Trong trường hợp 1 node đang có nguy cơ bị quá tải, việc auto reshard khiến cho tình trạng của nó càng trở nên tệ hơn.
• Không đạt tiêu chí ACID như quảng cáo (được đánh giá bởi tổ chức Jepsen – chi tiết của báo cáo có thể xem tại đây). Dưới đây là những điều cần lưu ý:
  • Rất nhiều vi phạm tiêu chuẩn ACID cũng như cả lỗi deadlock xuất hiện trong quá trình rebalance shard của Dgraph.
  • Dữ liệu có thể bị mất mát, trong vài trường hợp khác thì lại xảy ra duplicate, nhìn chung là rất thiếu tính tin cậy.
  • Dgraph sử dụng thuật toán Snapshot Isolation (không phải mức cao nhất là Serializable): vẫn có thể bị mắc phải các vấn đề như Write Skew, Lost Update,… (tham khảo bài Transaction Isolation (Part 1): Concurrency Control Problem và Transaction Isolation (Part 2): Isolation Level để hiểu rõ hơn)

3. Storage Engine – Badger:

Dgraph data is stored in an embeddable key-value database called Badger for data input-output on disk. Badger is an LSM-tree based design, but differs from others in how it can optionally store values separately from keys to generate a much smaller LSM tree, which results in both lower write and read amplification. Various benchmarks run by the team show Badger to provide equivalent or faster writes than other LSM based DBs, while providing equivalent read latencies compared to B+-tree based DBs (which tend to provide much faster reads than LSM trees).

Dựa theo tài liệu về Badger được giới thiệu tại đây, tôi sẽ tóm tắt qua một số điểm chính như sau:

• Badger là 1 Embeddable key-value database, lấy cảm hứng từ mô hình hoạt động của RocksDB (đã lọc bỏ đi các yếu tố không quan trọng như transaction, versioning, snapshot để tập trung vào performance).
  • RocksDB được viết bằng C++
  • Badger được viết lại bằng Golang, với mục đích để Dgraph (Golang) có thể tương tác trực tiếp bằng Native Go, không cần thông qua Cgo.
• Giống với các Database khác cũng sử dụng LSM-Tree index, bản ghi <Key, Value> vẫn được lưu lại trong file WAL (Write-ahead Log), tuy nhiên Badger không ghi Value vào trong Database, nó chỉ lưu <Key, Pointer> (trong đó Pointer là địa chỉ offset file WAL đang chứa Value).
• Cách Dgraph ứng dụng Badger cho việc lưu trữ triplet [S P O]:
  • Truy vấn [S P ?] sử dụng hàm Get.
  • Truy vấn [? P O] sử dụng hàm Iterate.
  • Ví dụ minh họa:

<0x01> <follower> <0xab> .
<0x01> <follower> <0xbc> .
<0x01> <follower> <0xcd> .
...
key = <follower, 0x01>
value = <0xab, 0xbc, 0xcd, ...>

Ưu điểm và nhược điểm:

Ưu điểm:

• Kích thước của Key và Pointer thực tế nhỏ hơn kích thước của Value rất nhiều, giúp hạn chế việc liên tục phải chạy compaction (có thể gây Disk IO cao).
• Nhờ kích thước file nhỏ nên số lượng LSM Tree Level ít:
  • Read Amplification thấp.
  • Write Amplication thấp.

Nhược điểm:

• Chỉ lấy Pointer trong Database rồi đọc giá trị từ WAL: Sử dụng Random Read gây Disk IO cao.
  • Điều này được khắc phục nếu sử dụng SSD.
• Tốc độ Iterate chậm do chỉ scan được Key từ Database, còn Value phải móc từ WAL.

Thực tế, benchmark mà tác giả Badger thực hiện đều đang sử dụng SSD. Nhờ Read Amplication thấp và loại bỏ đi các thứ như transaction, versioning, snapshot nên cũng dễ hiểu vì sao Badger lại nhanh hơn RocksDB trên môi trường SSD.

4. Cache

We had removed data caching from Dgraph due to heavy read-write contention, and built a new, contention-free Go cache library to aid our reads. Work is underway in integrating that with Dgraph. Dgraph does not have any query or response caching — such a cache would be difficult to maintain in an MVCC environment where each read can have different results, based on its timestamp.

Nhược điểm:

• Dgraph hiện đang không có cache

Đánh giá

Dù mới chỉ đánh giá dựa trên những yếu tố được coi là thiết yếu nhất của 1 Database, chưa khám phá thực sự sâu về các chi tiết bên trong, chẳng hạn Multiple Version Concurrency Control (MVCC) hay Lock-free Transaction,…. Tuy vậy, Dgraph đã bộc lộ ra quá nhiều nhược điểm và lỗi (theo như tác giả nói thì hiện vẫn chưa có phương án khắc phục).

Việc Dgraph có quá nhiều bug như này, theo tôi nhận định nguồn gốc là do nhà phát triển đã quá tham lam, vừa cố gắng tối ưu hiệu suất (lock-free, parallel), lại vừa tìm cách triển khai distributed transaction. Ngoài ra, họ cũng tự “reinvent the wheel” và customize lại rất nhiều thứ, thay vì dùng engine có sẵn đã được kiểm chứng như ZooKeeper, RocksDB,… Tôi xin phép dừng đi sâu hơn tại đây và đưa ra kết luận luôn:

• Xếp loại: Ma giáo
• Điểm: 4/10

Ngoài ra, các bạn có thể đón đọc thêm những bài viết khác cùng chuyên mục tại đây nhé!