LIquid: The soul of a new graph database, Part 1

LinkedIn · 2020 · 3. Quy mô lớn · Độ khó: Nâng cao — bài gốc

Bối cảnh

Theo LinkedIn, giá trị của đồ thị nằm chủ yếu ở mạng cấp 2: bạn của bạn, thường ít nhất 50.000 entity (người, trường, công ty). Mạng cấp 1 (vài trăm kết nối) để trong bảng hay KV là đủ; mạng cấp 3 quá lớn và khó hành động.
Mạng cấp 2 không materialize sẵn được: quá lớn, và mỗi lần ghi phải khuếch đại khoảng 250 lần (một lần cho mỗi kết nối cấp 1). Tính lúc cần thì là join cực thưa, khoảng 250 lookup ngẫu nhiên vào B-tree cỡ terabyte.
LinkedIn đã làm một loạt graph service ngày càng tổng quát: đầu tiên chỉ lưu (source, dest, score), sau thêm loại cạnh (việc làm, học vấn) nhưng cạnh chỉ có 2 đầu số nguyên và 64 bit thuộc tính. LIquid (đội làm bốn năm tới 2020) là hệ tổng quát đầu tiên: một service tự động thay các query viết tay từng cộng thêm vài trăm ms vào thời gian tải trang.

Đi từ đồ thị object trong bộ nhớ (cách ứng dụng MVC vẫn làm) và lý do OODB thất bại thập niên 1990: không có ngôn ngữ query khai báo, snapshot nhất quán quá đắt khi vượt một máy, schema theo kế thừa khó tiến hoá.
Cạnh tổng quát là bộ ba chuỗi (subject, predicate, object), ví dụ ("urn:author:1234", "wrote", "urn:book:4567"); định danh bền là chuỗi do người dùng cấp, DB ánh xạ sang số nội bộ. Chỉ có một schema nên không có bài toán tiến hoá schema.
Một writer, cấu trúc wait-free: mọi cạnh được append vào một graph log; offset trong log đóng vai trò thời gian ảo. Mỗi đỉnh trong index là một mini-log các cạnh liên quan, kèm offset. Query chọn một offset rồi đọc lùi, bỏ cạnh mới hơn: nhất quán "tính đến offset X" mà không cần khoá hay compare-and-swap. Xoá là append tombstone.
Theo bài, một writer không phải nút cổ chai vì dữ liệu do con người tạo ra thay đổi ở tốc độ con người.
Kết quả trả về là một subgraph (tập cạnh); ứng dụng tự dựng thành cấu trúc mình cần.

Khi một truy vấn quan trọng (mạng cấp 2) không materialize được vì khuếch đại ghi, phải làm cho việc tính lúc đọc đủ rẻ: index trong RAM, truy cập cạnh với chi phí như chase con trỏ.
Log append-only + offset làm phiên bản là cách lấy snapshot nhất quán rẻ khi chỉ có một writer.