Dùng Postgres như Graph DB: Lạm dụng PgRouting hay tận dụng đúng cách?

• pgRouting là một phần mở rộng của Postgres, chủ yếu được dùng trong hệ thống thông tin địa lý (GIS) để tìm đường đi ngắn nhất giữa hai điểm
• Tuy nhiên, pgRouting cũng có thể được tận dụng để xử lý dữ liệu có nhiều kiểu cấu trúc đồ thị khác ngoài dữ liệu không gian địa lý
• Có thể dùng nó như một giải pháp thay thế gọn nhẹ cho các cơ sở dữ liệu đồ thị chuyên dụng như Apache AGE hoặc Neo4j

Giới thiệu về pgRouting

• pgRouting là một tiện ích mở rộng của PostGIS, cung cấp các tính năng định tuyến không gian địa lý
• Nhờ đó có thể tính toán đường đi ngắn nhất, phân tích mạng lưới và giải các bài toán định tuyến phức tạp
• Nó chủ yếu được dùng trong GIS, chẳng hạn để tìm đường đi ngắn nhất giữa hai vị trí

Liên hệ với đồ thị

• Điểm mạnh của pgRouting là có thể làm việc với mọi loại dữ liệu được cấu trúc theo dạng đồ thị
• Đồ thị được tạo thành từ một mạng lưới các điểm được kết nối với nhau, trong đó:
  • Nút đại diện cho thực thể
  • Cạnh đại diện cho mối quan hệ hoặc đường đi giữa các nút
• Trong bản đồ hay GIS, nút và cạnh lần lượt tương ứng với giao lộ và con đường, nhưng cũng có thể áp dụng cho các hệ thống trừu tượng như mạng xã hội

Các trường hợp dùng pgRouting ngoài GIS

• Lập lịch công việc

  • Trong dự án, giữa các công việc tồn tại quan hệ phụ thuộc, tạo thành một đồ thị có hướng không chu trình (DAG)
    • Nút đại diện cho công việc
    • Cạnh đại diện cho quan hệ phụ thuộc
  • Một trong những bài toán chính của quản lý dự án là tìm ra 'đường găng (critical path)' quyết định tổng thời gian của toàn bộ dự án
  • Có thể dùng pgRouting để mô hình hóa các quan hệ phụ thuộc giữa công việc và tìm đường găng bằng các thuật toán đồ thị

• Định tuyến reverse proxy dựa trên phân bổ tài nguyên

  • Trong hệ thống phân tán, việc phân bổ tài nguyên hiệu quả giữa các nút trong mạng là rất quan trọng
  • Mỗi nút có thể đại diện cho vị trí vật lý hoặc một tiến trình tính toán, còn cạnh biểu thị đường di chuyển dữ liệu giữa các nút
  • Ví dụ, trong hạ tầng đám mây, có thể dùng pgRouting để định tuyến dữ liệu hoặc tác vụ tính toán giữa các máy chủ phân tán theo con đường hiệu quả nhất

• Công cụ gợi ý như YouTube

  • Trong công cụ gợi ý hoặc các thuật toán tìm kiếm dùng knowledge graph, pgRouting có thể được tận dụng để xây dựng quan hệ giữa các thực thể và sự kiện
  • Ví dụ, trong thuật toán gợi ý của YouTube:
    • Nút đại diện cho các thực thể như người dùng, video, danh mục
    • Cạnh đại diện cho các quan hệ như tương tác giữa người dùng và video hoặc việc các video cùng chia sẻ danh mục
  • Cấu trúc đồ thị như vậy có thể dùng để cung cấp gợi ý cá nhân hóa cho người dùng

Thông tin thêm về pgRouting

• pgRouting là một tiện ích mở rộng mạnh mẽ của Postgres, có thể được dùng để giải quyết nhiều bài toán dựa trên đồ thị khác nhau
• Có thể xem thêm chi tiết trong tài liệu chính thức của pgRouting

[curiosityprocessor]

Có ai đã triển khai thực tế apache age hoặc pgRouting chưa?
Công ty đang đưa Graph DB vào sử dụng, và hiện tại đúng là đang dùng Postgres làm RDB,
nhưng nghe nói plugin/extension có thể dùng Postgres “như thể là Graph DB” thôi chứ hiệu năng thực tế không ra gì, nên tôi đang cân nhắc neo4j; mà xem ra ý kiến trên Hacker News cũng có khá nhiều người không hài lòng với neo4j nhỉ

[GN⁺]

Ý kiến trên Hacker News

• Năm năm trước, đã thất vọng với các cơ sở dữ liệu và thư viện Graph nên đã thử đặt nhiều DBMS không phải Graph phía sau một giao diện Python tương tự NetworkX

  • Neo4J bị lỗi trên mọi đồ thị, còn SQLite và Postgres là những lựa chọn phù hợp hơn cho tác vụ xử lý mạng
  • Tò mò liệu có đáng làm mới dự án khi khả năng tương thích với Postgres đã tăng lên hay không
  • Nhiều Graph DB hơn như MemGraph hiện tương thích với CYPHER và có thể hoạt động tốt hơn Neo4J
  • Mục tiêu là tìm hiểu xem pgrouting có phải công cụ tốt để xây dựng lớp bộ nhớ cho AI/agent hay không
  • Kết quả ban đầu khá hứa hẹn và dự định sớm theo dõi bằng một bài viết khác
  • Có những extension thú vị như onesparse dựa trên SuiteSparse

• Supabase liên tục cung cấp nội dung rất hay liên quan đến PostGIS

  • Có nội dung về việc tự phục vụ tile hoặc (lạm) dụng các tính năng trong ngữ cảnh địa lý của PG
  • Không mang tính đột phá hay quá phức tạp, nhưng vui và kích thích tư duy
  • Đáng khen vì thường xuyên đăng nội dung khơi gợi hứng thú khi làm việc với cơ sở dữ liệu

• Luôn thắc mắc vì sao không có "SQLite cho đồ thị"

  • Tò mò liệu có cách lưu trữ nào cản trở một giải pháp in-process với lưu trữ trên đĩa hay không

• Đang làm một dự án graph DB đơn giản trên Postgres

  • Query và cấu trúc bảng đơn giản hơn nhiều cho cùng một công việc

• Muốn nghe ý kiến về việc lưu roaring bitmap trong cột bytea của Postgres để biểu diễn ma trận kề

  • Vì RDS hỗ trợ plrust và SPI của PostgreSQL, có vẻ có thể xây dựng bằng croaring-rs
  • Có thể biểu diễn nhiều đồ thị, mỗi đồ thị được gán cho một tenant (trường hợp công ty/B2B SaaS)
  • Có thể dùng plrust để lưu roaring bitmap vào bytea trên máy chủ DB và dùng SPI để giảm thiểu overhead mạng
  • PostgreSQL cung cấp tính an toàn giao dịch, đồng thời hỗ trợ dữ liệu dạng cột khác như JSONB để truy vấn cột ID tenant và metadata quan hệ
  • Cần hỗ trợ nhiều đồ thị tenant và đã dùng citus nên có vẻ cũng khả thi ở quy mô lớn
  • Có lẽ sẽ cần tạo một số operator class để lập chỉ mục quan hệ tốt hơn
  • Có biết pg_roaringbitmap nhưng nó dùng int64 và thích bắt đầu trên RDS hơn
  • Đang sử dụng PostgreSQL rất sâu thay vì Neo4J (ví dụ làm việc với các bảng ~20+ TB)
  • Gửi lời cảm ơn lớn tới tác giả bài blog
  • Có vẻ có thể dùng pgRouting như một graph DB nên sẽ thêm vào danh sách thử nghiệm

• Tò mò không biết có ai có ý kiến về "Apache AGE" không

  • Apache AGE™ là PostgreSQL cung cấp chức năng cơ sở dữ liệu đồ thị

• Tò mò liệu chỉ xét riêng mô hình dữ liệu (ví dụ không tính ngôn ngữ truy vấn) thì có khác biệt thực sự nào giữa cơ sở dữ liệu "đồ thị" và cơ sở dữ liệu "SQL thông thường" hay không

• Tò mò không biết có ai có kinh nghiệm dùng PgRouting để tạo isochrone không

  • Có use case tạo bản đồ isochrone cho đi bộ, đạp xe, v.v.
  • Nếu có thể thì muốn chỉ dùng Postgres và tránh các hạ tầng khác như Valhalla, OpenTripPlanner, OpenRouteService

• Postgres luôn có các extension mở ra những cơ hội mô hình hóa dữ liệu mới

  • Tò mò nó xếp như thế nào nếu so với tính năng graph của CedarDB (tương thích Postgres)