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

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

Bối cảnh

• Đồ thị biểu diễn bằng một bảng cạnh (adjacency list) là đúng mô hình quan hệ: không NULL, dạng chuẩn 5, dễ chuyển dữ liệu. Nhưng DB quan hệ truyền thống chạy rất tệ với schema này, và SQL khó dùng để dựng ứng dụng.
• Workload của LinkedIn là browsing: một trang cần một subgraph nhỏ nhưng phức tạp, tức query có hàng chục tới hàng trăm ràng buộc cạnh, toàn là self-join và lookup ngẫu nhiên.

Thay đổi chính

• Index băm thay vì B-tree: ở quy mô terabyte, một lần dò B-tree tốn hàng chục L3 cache miss; index băm + VList của LIquid tốn 2–3 miss. Kích thước tập (fan-out) lưu sẵn ở bảng băm cấp trên, đọc được trong 1 miss, nên phát hiện skew (đỉnh có fan-out cực lớn) trước khi trả giá.
• Không dùng đại số quan hệ để thực thi: kết quả dạng bảng sinh tích Descartes giả (cặp (Java, Oracle) lặp nhiều lần dù chỉ có một cạnh); với query có chu trình (tam giác) thì plan select-project-join chậm hơn tối ưu về tiệm cận (worst-case optimal join).
• Query planner động dựa trên thoả mãn ràng buộc: plan không cố định từ đầu, mỗi bước thoả ràng buộc rẻ nhất còn lại, dựa vào kích thước tập tra được trong thời gian hằng.
• Ngôn ngữ là Datalog, chỉ cho khẳng định quan hệ Edge, mọi rule quy về Edge; ghép được (composable). Kết quả là bảng như SQL hoặc subgraph.
• Schema tự mô tả trong đồ thị: predicate khởi tạo liquid/type, liquid/cardinality khai kiểu vô hướng và số cạnh tối đa ở mỗi đầu, để ánh xạ được về bảng chuẩn hoá.
• Compound edge cho quan hệ n-ngôi (ví dụ diễn viên–vai–phim, hay nhiệm kỳ làm việc người–công ty–ngày bắt đầu): DB tự sinh định danh tương đối cho đỉnh trung tâm, nên compound có ngữ nghĩa duy nhất như một cạnh và truy cập nhanh như cạnh. Có được sức biểu đạt của property graph mà không cần schema thuộc tính riêng.
• Định nghĩa graph DB theo LinkedIn: mọi quan hệ ngang hàng, duyệt cạnh thời gian hằng, kết quả là subgraph, thêm predicate tốn thời gian hằng. So với RDF/SPARQL, property graph (Neo4j, TAO, Gremlin) và SQL graph extension.

Bài học cho SWE

• Planner tĩnh dựa trên thống kê cấp bảng chịu thua self-join trên dữ liệu skew; cần biết kích thước tập thật lúc chạy.
• Trả kết quả dạng đồ thị thay vì bảng là cách tránh object-relational impedance mismatch và tích Descartes thừa.

Liên quan

• LinkedIn 2020 · LinkedIn 2023
• Chọn database theo workload · Query planner và hiệu năng truy vấn