Đồ thị có hướng không chu trình (DAG) và sắp xếp tô-pô
1. Tổng quan
A. Khái niệm DAG
Đồ thị có hướng không chu trình (DAG, Directed Acyclic Graph) là đồ thị có cạnh mang hướng (directed) và không có chu trình (cycle) xuất phát từ một đỉnh rồi quay trở lại chính nó. Đây là cấu trúc dữ liệu phù hợp để biểu diễn quan hệ thứ tự trước sau và phụ thuộc giữa các công việc mà không mâu thuẫn.
Lý do căn bản khiến DAG được dùng rộng rãi trong mọi lĩnh vực khoa học máy tính là vì nó 'vừa khít để biểu diễn các công việc có thứ tự và quan hệ phụ thuộc'. Cạnh có hướng nghĩa là quan hệ trước sau (precedence) kiểu "A rồi đến B", còn không có chu trình nghĩa là "không có mâu thuẫn logic xoay vòng". Nếu có chu trình, sẽ nảy sinh mâu thuẫn là A phải đi trước B đồng thời B cũng phải đi trước A, và không thể xác định thứ tự thực thi. DAG về mặt cấu trúc loại trừ mâu thuẫn này nên luôn bảo đảm tồn tại một thứ tự thực thi hợp lệ.
Nhờ tính chất này, vô số 'quan hệ phụ thuộc có thứ tự' trong thực tế được mô hình hóa bằng DAG. Quan hệ môn tiên quyết ở đại học, phụ thuộc biên dịch của hệ thống build (ví dụ: main.o được liên kết sau khi main.c được biên dịch), quản lý tiến độ dự án (mạng công việc của PERT/CPM), pipeline dữ liệu (định nghĩa workflow của Apache Airflow), thứ tự tính lại công thức trong bảng tính, thậm chí blockchain và lịch sử commit của Git (đồ thị có hướng trỏ đến commit cha) đều là DAG. Tức là DAG gần với ngôn ngữ chung biểu diễn miền vấn đề gọi là sự phụ thuộc hơn là một thuật toán cụ thể.
Thủ tục thực sự tính ra 'phải xử lý theo thứ tự nào để thỏa mãn mọi phụ thuộc' trên DAG đã biểu diễn như vậy chính là sắp xếp tô-pô (Topological Sort). Do đó, có thể hiểu DAG là mô hình biểu diễn vấn đề, còn sắp xếp tô-pô là thuật toán tiêu biểu để giải mô hình đó.
B. Bối cảnh ra đời và sự cần thiết
Việc build phần mềm hay lập lịch công việc ban đầu do con người liệt kê thứ tự thủ công, nhưng khi các thành phần tăng lên hàng trăm đến hàng nghìn, các quan hệ phụ thuộc bắt đầu đan xen phức tạp. Chẳng hạn, trong một dự án có hàng trăm tệp nguồn, việc con người mỗi lần đều tính "phải biên dịch cái gì trước" gần như bất khả thi, và nếu có phụ thuộc vòng ẩn thì ngay cả phát hiện cũng khó. Để tự động hóa vấn đề này, cách biểu diễn quan hệ phụ thuộc bằng đồ thị và suy ra thứ tự thực thi một cách máy móc trở nên cần thiết, và DAG cùng sắp xếp tô-pô đã trở thành nền tảng lý thuyết và thực tiễn cho điều đó.
Ngoài ra, sự lan rộng của xử lý song song và phân tán cũng làm tăng tầm quan trọng của DAG. Các công việc không phụ thuộc lẫn nhau có thể chạy đồng thời, và phân tích cấu trúc DAG giúp nắm chính xác "những công việc nào độc lập với nhau nên có thể song song". Tức là DAG không chỉ xác định thứ tự đơn thuần mà còn cung cấp căn cứ để tìm mức song song hóa tối đa nhằm tối đa hóa việc sử dụng tài nguyên.
C. Đặc điểm
| Đặc điểm | Nội dung | Hàm ý thực tiễn |
|---|---|---|
| Có hướng (Directed) | Cạnh biểu diễn quan hệ trước sau·phụ thuộc | Nêu rõ "A rồi đến B" |
| Không chu trình (Acyclic) | Không có chu trình → tồn tại thứ tự không mâu thuẫn | Loại trừ bế tắc·phụ thuộc vòng |
| Có thể sắp xếp tô-pô | Luôn liệt kê được theo thứ tự tuyến tính | Tự động suy ra thứ tự thực thi |
| Thứ tự bộ phận (Partial Order) | Thứ tự giữa các đỉnh độc lập là tự do | Nắm được dư địa thực thi song song |
2. Khái niệm và cấu trúc của sắp xếp tô-pô
Sắp xếp tô-pô là việc liệt kê thành một hàng mọi đỉnh của DAG sao cho mọi cạnh đều hướng từ trước ra sau (đỉnh đi trước đứng trước đỉnh đi sau). Tức là phép toán mở rộng thứ tự bộ phận (partial order) thành thứ tự toàn phần (total order) mà không mâu thuẫn.
Dưới đây là sơ đồ cấu trúc tổng thể thể hiện một DAG và ý nghĩa của sắp xếp tô-pô trên nó.
flowchart LR
A["A(bắt đầu)"] --> B["B"]
A --> C["C"]
B --> D["D"]
C --> D
C --> E["E"]
style A fill:#e8f0fe,stroke:#2f6fed,stroke-width:2px
style D fill:#fef7e8,stroke:#e0a800
Trong DAG trên, sắp xếp tô-pô là công việc xếp hàng các đỉnh "sao cho mọi mũi tên đều hướng từ trái sang phải". Ví dụ, có thể có nhiều lời giải như A → B → C → D → E hoặc A → C → B → E → D. Điểm cốt lõi là trước khi một đỉnh được liệt kê, mọi đỉnh đi trước trỏ đến đỉnh đó phải xuất hiện trước. D chỉ có thể xuất hiện sau khi cả B và C đã được xử lý, còn E có thể xuất hiện sau khi C được xử lý.
Điểm đáng chú ý ở đây là giữa B và C không có cạnh. Giữa hai đỉnh không có ràng buộc trước sau, nên dù B xuất hiện trước hay C xuất hiện trước thì đều là sắp xếp tô-pô hợp lệ. Như vậy, vì thứ tự của các cặp đỉnh không có ràng buộc là tự do nên kết quả sắp xếp tô-pô không duy nhất, và mức tự do này chính là cơ hội thực thi song song. Từ góc độ engine thực thi, B và C là các ứng viên có thể xử lý đồng thời.
A. Thuật toán Kahn (dựa trên bậc vào)
Thuật toán sắp xếp tô-pô tiêu biểu là thuật toán Kahn, lặp đi lặp lại việc tìm và loại bỏ các đỉnh có bậc vào (in-degree, số cạnh đi vào) bằng 0. Bậc vào bằng 0 nghĩa là "không còn công việc đi trước nào phải thực hiện trước đỉnh đó", tức là đỉnh có thể thực thi ngay lập tức.
flowchart TB
S["① Tính bậc vào của mọi đỉnh"] --> Q["② Đưa các đỉnh có bậc vào 0 vào hàng đợi"]
Q --> P["③ Lấy một đỉnh ra khỏi hàng đợi, thêm vào kết quả"]
P --> R["④ Loại bỏ đỉnh đó, bậc vào của đỉnh kề -1"]
R --> C{"⑤ Có đỉnh mới đạt bậc vào 0?"}
C -->|"Có"| Q
C -->|"Không, hàng đợi rỗng"| F{"⑥ Kết quả chứa mọi đỉnh?"}
F -->|"Có"| OK["Hoàn tất sắp xếp tô-pô"]
F -->|"Không"| CYC["Tồn tại chu trình → không thể sắp xếp"]
style S fill:#e8f0fe,stroke:#2f6fed
style CYC fill:#fdecec,stroke:#d64545
Hãy áp dụng thủ tục này cho DAG ví dụ ở trên. Ban đầu, đỉnh có bậc vào 0 chỉ có A (không ai trỏ đến A). Đưa A vào kết quả và loại bỏ thì bậc vào của B và C đều trở thành 0. Bây giờ B và C trở thành ứng viên thực thi, và kết quả khác nhau tùy thứ tự lấy ra khỏi hàng đợi. Xử lý B, C thì bậc vào của D thành 0 (cạnh từ cả B và C đều bị loại bỏ), còn E cũng thành 0 tại thời điểm xử lý C. Cuối cùng thu được thứ tự chẳng hạn A, B, C, D, E.
Hệ quả phụ quan trọng của thuật toán Kahn là phát hiện chu trình. Nếu thủ tục kết thúc mà số đỉnh trong kết quả ít hơn tổng số đỉnh, thì các đỉnh còn lại đang trỏ vòng lẫn nhau nên bậc vào không bao giờ về 0. Tức là "sắp xếp tô-pô thất bại = đồ thị có chu trình" được thiết lập. Độ phức tạp thời gian với số đỉnh V và số cạnh E là O(V + E), vì mỗi đỉnh và cạnh chỉ được thăm hằng số lần nên hiệu quả ngay cả với đồ thị quy mô lớn.
B. Sắp xếp tô-pô dựa trên DFS
Một cách khác là dùng tìm kiếm theo chiều sâu (DFS). Thực hiện DFS từ mỗi đỉnh, và tại thời điểm việc duyệt mọi con (đỉnh đi sau) của một đỉnh kết thúc (post-order, lúc quay lui ra), đẩy đỉnh đó vào ngăn xếp. Sau khi mọi tìm kiếm kết thúc, lấy ngăn xếp ra theo thứ tự đảo ngược sẽ được kết quả sắp xếp tô-pô.
Lý do cách này đúng rất trực quan. Nếu có cạnh từ đỉnh u đến v, DFS nhất định kết thúc việc duyệt v trước khi kết thúc việc duyệt u (vì v là hậu duệ của u). Do đó v được đẩy vào ngăn xếp trước u, và đọc ngăn xếp theo thứ tự đảo ngược thì u đứng trước v, tự động thỏa điều kiện sắp xếp tô-pô "đi trước thì đứng trước". Cách DFS cũng thăm mỗi đỉnh và cạnh một lần nên độ phức tạp thời gian như nhau là O(V + E), và nếu trong quá trình tìm kiếm gặp cạnh ngược (back edge) hướng tới đỉnh chưa duyệt xong (đỉnh màu xám) thì phán định có chu trình.
Hai thuật toán có hiệu năng như nhau nhưng tính chất khác nhau. Thuật toán Kahn được hiện thực lặp (iterative) bằng hàng đợi nên không có rủi ro tràn ngăn xếp, và có ưu điểm tự nhiên làm lộ ra các ứng viên thực thi song song khi có nhiều đỉnh bậc vào 0, nên phù hợp cho bộ lập lịch workflow. Ngược lại, cách DFS được hiện thực gọn gàng bằng đệ quy và dễ kết hợp với các phân tích đồ thị khác như phân rã thành phần liên thông mạnh (SCC).
3. Ví dụ ứng dụng
Sắp xếp tô-pô không dừng ở lý thuyết mà vận hành bên trong engine của các công cụ chúng ta dùng hằng ngày. Các ví dụ dưới đây đều chia sẻ cùng một nguyên lý: "biểu diễn quan hệ phụ thuộc bằng DAG và suy ra thứ tự thực thi bằng sắp xếp tô-pô".
| Lĩnh vực | Ứng dụng | Ví dụ cụ thể |
|---|---|---|
| Build·biên dịch | Xác định thứ tự phụ thuộc mã nguồn | Đồ thị target của Make, Bazel |
| Lập lịch công việc | Thứ tự công việc trước sau·đường găng | PERT/CPM, MS Project |
| Pipeline dữ liệu | Thực thi phụ thuộc tác vụ·song song hóa | Apache Airflow, Dagster |
| Quản lý gói | Thứ tự cài đặt·giải quyết phụ thuộc | apt, npm, Maven |
| Môn tiên quyết·chương trình học | Xác định thứ tự học | Hệ thống đăng ký môn học đại học |
Ví dụ tiêu biểu nhất là điều phối (orchestration) pipeline dữ liệu. Apache Airflow gọi workflow đúng theo nghĩa đen là 'DAG', định nghĩa mỗi tác vụ (ví dụ: trích xuất dữ liệu → làm sạch → tổng hợp → nạp) là đỉnh và quan hệ phụ thuộc là cạnh. Bộ lập lịch sắp xếp tô-pô DAG này để xác định thứ tự thực thi, đồng thời chạy song song các tác vụ không phụ thuộc lẫn nhau (ví dụ: trích xuất từ hai nguồn khác nhau) để rút ngắn thời gian xử lý. Nếu trong pipeline gồm hàng trăm tác vụ vô tình định nghĩa phụ thuộc vòng, Airflow sẽ từ chối ngay ở giai đoạn đăng ký DAG, và đây chính là ứng dụng thực tế của việc phát hiện chu trình thông qua thất bại sắp xếp tô-pô.
Ví dụ thứ hai là hệ thống build. Bazel của Google hay Make truyền thống cấu thành quan hệ phụ thuộc giữa mã nguồn, header, thư viện thành DAG và biên dịch theo thứ tự sắp xếp tô-pô. Khi đó, nếu cache kết quả của các đỉnh không thay đổi (build tăng dần), ngay cả trong codebase lớn quy mô hàng chục nghìn tệp cũng chỉ cần build lại phần thay đổi và phần phụ thuộc vào nó, rút ngắn thời gian build từ đơn vị phút xuống đơn vị giây. Ở đây, các target không có phụ thuộc cũng được phân tán ra nhiều nhân CPU để biên dịch song song.
Ví dụ thứ ba là quản lý tiến độ dự án (PERT/CPM). Trên DAG lấy công việc (activity) làm đỉnh và quan hệ trước sau làm cạnh, tính thời điểm bắt đầu sớm nhất và muộn nhất của mỗi công việc theo thứ tự sắp xếp tô-pô thì tìm được đường găng (Critical Path) quyết định tổng thời gian dự án. Chẳng hạn, trong dự án gồm 20 công việc, nếu một công việc trên đường găng trễ một ngày thì toàn bộ dự án trễ một ngày, nên người quản lý tập trung nguồn lực vào đường này.
4. Chuyên sâu: Lập lịch song song và chiến lược xử lý chu trình
Trong các hệ thống hiện đại, giá trị của sắp xếp tô-pô nằm ở tối ưu hóa thực thi song song hơn là xác định thứ tự đơn thuần. Biến thể thuật toán Kahn để ở mỗi vòng xử lý đồng thời các đỉnh có bậc vào 0 như 'một nhóm (mức)' thì có thể chia DAG thành nhiều mức. Các đỉnh trong mỗi mức độc lập với nhau nên có thể thực thi song song, và số mức chính là số bước tối thiểu khi thực thi song song. Khái niệm này được dùng nguyên vẹn trong lập lịch đồ thị tính toán GPU, xử lý lô phân tán, phân tích độ trễ logic tổ hợp của mạch phần cứng, v.v.
Mặt khác, trong thực tế thường phát sinh vấn đề "lẽ ra phải là DAG nhưng lại xuất hiện chu trình". Ví dụ như phụ thuộc gọi vòng giữa các microservice, mô-đun có tham chiếu vòng, công thức tham chiếu vòng trong bảng tính. Khi đó dùng các chiến lược: (1) phát hiện và cảnh báo chu trình bằng sắp xếp tô-pô, (2) thu gọn thành phần liên thông mạnh (SCC) thành một siêu đỉnh (đồ thị cô đặc, condensation) để ít nhất phần còn lại được xử lý như DAG, hoặc (3) loại bỏ chính chu trình bằng tái cấu trúc cắt đứt phụ thuộc (tách interface, bất đồng bộ hóa dựa trên sự kiện). Đồ thị tính toán của framework học sâu cũng vậy: lan truyền xuôi là DAG, còn mạng nơ-ron hồi quy (RNN) được trải ra theo trục thời gian (unrolling) để chuyển thành DAG rồi mới thực hiện lan truyền ngược.
Trong lĩnh vực dữ liệu lớn và AI, DAG cũng là trừu tượng cốt lõi. Apache Spark cấu thành các phép biến đổi của người dùng thành DAG rồi chia thành nhiều stage để tối ưu kế hoạch thực thi, và tự động vi phân của TensorFlow, PyTorch cũng duyệt ngược đồ thị tính toán lan truyền xuôi (DAG) để lan truyền gradient. Như vậy, mẫu "biểu diễn phép toán bằng DAG và thực thi, vi phân theo thứ tự tô-pô" đã trở thành nguyên lý thiết kế chung xuyên suốt ngăn xếp dữ liệu và AI hiện đại.
5. Các điểm cần cân nhắc và hàm ý
Dùng như công cụ phát hiện chu trình và phòng ngừa bế tắc. Việc có thể sắp xếp tô-pô hay không chính là phán định tính không chu trình của đồ thị, nên có thể dùng làm phương tiện kiểm chứng để sớm phát hiện vòng phụ thuộc, bế tắc tài nguyên (deadlock), tham chiếu vòng. Khi thiết kế hệ thống quy mô lớn, chiến lược định kỳ sắp xếp tô-pô đồ thị phụ thuộc và quản lý phụ thuộc vòng như một chỉ số chất lượng kiến trúc là hiệu quả.
Nắm định lượng dư địa song song hóa để tối ưu hóa sử dụng tài nguyên. Tính chất thứ tự bộ phận của sắp xếp tô-pô làm lộ ra những công việc nào độc lập, nên thông qua chia mức có thể tính mức song song tối đa và độ dài đường găng. Đây trở thành căn cứ định lượng cho lập lịch, phân bổ tài nguyên và dự báo hiệu năng.
Cần chiến lược kiểm soát tính không duy nhất của kết quả. Lời giải sắp xếp tô-pô có nhiều, nên khi cần build có thể tái lập hoặc thực thi tất định, phải gán tiêu chí thứ cấp như tên đỉnh, ưu tiên, chi phí để buộc thứ tự tất định (deterministic order). Ngược lại, nếu mục đích là tối ưu hóa thì tận dụng mức tự do này cho tối ưu lập lịch.
Cân nhắc xử lý tăng dần trước thay đổi động. DAG trong hệ thống thực tế thường xuyên được thêm, xóa đỉnh và cạnh, nên thay vì mỗi lần sắp xếp lại toàn bộ, cần sắp xếp tô-pô tăng dần (incremental topological ordering) chỉ tính lại phạm vi bị ảnh hưởng bởi thay đổi. Đây là điểm thiết kế cốt lõi quyết định khả năng phản hồi của build tăng dần và pipeline thời gian thực.
Hiểu cùng với các cấu trúc dữ liệu và thuật toán liên quan. Sắp xếp tô-pô liên kết chặt chẽ với biểu diễn đồ thị (danh sách kề/ma trận kề), hàng đợi và ngăn xếp ([[stack-queue-list]]), DFS/BFS, tính đường ngắn nhất và đường găng. Từ góc độ Kỹ sư chuyên nghiệp (Professional Engineer), điều quan trọng hơn việc học thuộc từng thuật toán là thấm nhuần mô thức giải quyết vấn đề "mô hình hóa vấn đề phụ thuộc bằng DAG và giải bằng sắp xếp tô-pô".
Tài liệu tham khảo
- Wikipedia, "Topological sorting" — https://en.wikipedia.org/wiki/Topological_sorting
- Wikipedia, "Directed acyclic graph" — https://en.wikipedia.org/wiki/Directed_acyclic_graph
- Apache Airflow Documentation, "DAGs" — https://airflow.apache.org/docs/apache-airflow/stable/core-concepts/dags.html
Tóm tắt một câu: DAG là đồ thị có hướng và không có chu trình biểu diễn quan hệ trước sau và phụ thuộc mà không mâu thuẫn, còn sắp xếp tô-pô liệt kê các đỉnh sao cho mọi cạnh đều hướng từ trước ra sau (Kahn: loại bỏ dần từ đỉnh bậc vào 0, hoặc đảo ngược thứ tự post-order của DFS, đều O(V+E)) để xác định thứ tự thực thi cho build, lập lịch, pipeline dữ liệu, đồng thời làm lộ ra dư địa song song hóa và chu trình.