Case Study: Maven DAG build order + Google Maps shortest path

TL;DR: Hai hệ thống quen thuộc đều chạy thuật toán đồ thị bên dưới. Maven dựng DAG giữa các module trong reactor rồi sắp xếp topo bằng DFS (thư viện plexus-utils) để ra thứ tự build; có cycle thì dừng với lỗi cyclic reference, và các module không phụ thuộc nhau có thể build song song. Với routing trên bản đồ, Dijkstra thuần quá chậm ở quy mô cả châu lục, nên các engine như OSRM tiền xử lý bằng Contraction Hierarchy rồi truy vấn bằng bidirectional search, nhanh hơn Dijkstra hàng chục nghìn lần trong các bài báo học thuật. Google không công bố thuật toán routing của Google Maps, nên phần bản đồ dưới đây dựa trên tài liệu công khai và OSRM.

Module này đã đi qua 10 chủ đề về đồ thị: cách lưu graph, BFS, DFS, topological sort, Dijkstra, Bellman-Ford, Floyd-Warshall, MST (Kruskal + Prim), Disjoint Set Union và bài tập maze BFS. Mỗi bài giải thích cơ chế, độ phức tạp và các đánh đổi về lý thuyết. Còn hệ thống thật dùng chúng ở đâu thì có câu trả lời rất cụ thể.

Mỗi lần bạn chạy mvn package trên project nhiều module, Maven phải sắp xếp topo các module trong reactor. Mỗi lần một app bản đồ tính đường, bên dưới thường là biến thể của Dijkstra có tiền xử lý, chứ không phải Dijkstra thường như bài 05 đã dạy.

Bài này đi sâu vào 2 hệ thống: reactor build của Maven 3.x với topo sort trên DAG, và pipeline routing trên bản đồ. Ta đọc source thật (Maven, OSRM) để hiểu vì sao mỗi quyết định phù hợp với quy mô của nó.

1. Thông tin dự án A: Maven 3.x

Dự án: Apache Maven 3.x, công cụ build tự động phổ biến nhất trong hệ sinh thái Java.

Source liên quan (đã đối chiếu với nhánh maven-3.9.x):

• org.apache.maven.project.ProjectSorter: dựng DAG bằng DAG và TopologicalSorter của plexus-utils, bắt CycleDetectedException
• org.apache.maven.graph.DefaultGraphBuilder: gọi sang đồ thị phụ thuộc, bọc lỗi cycle thành ProjectCycleException
• org.apache.maven.graph.DefaultProjectDependencyGraph: giữ danh sách module đã sắp xếp, cung cấp getUpstreamProjects và getDownstreamProjects
• GitHub: https://github.com/apache/maven

Maven 3 là dòng Maven phổ biến trong hệ sinh thái Java, và nhánh 3.9.x vẫn được dùng rộng rãi.

2. Maven reactor build flow

Khi bạn có project nhiều module, tức một parent POM khai báo N child module, Maven phải quyết định thứ tự build.

Cách nó chạy:

1. Maven scan toàn bộ module trong project (reactor scan)
2. Đọc mọi pom.xml, thu thập dependency giữa các module
3. Xây DAG: mỗi module = đỉnh, mỗi dependency = cạnh có hướng
4. Topo sort DAG -> build order
5. Detect cycle: nếu có A -> B -> A, ném CycleDetectedException (sau đó bị bọc thành ProjectCycleException)
6. Parallel build (-T 4): các module không phụ thuộc nhau (anti-chain trong DAG) build song song

Ví dụ 6-module project:

Modules: common, utils, core, service, api, app

Dependencies:
  utils   --> common
  core    --> common
  service --> core
  service --> utils
  api     --> service
  app     --> api

Topo order hợp lệ: [common, utils, core, service, api, app]

Các nhóm có thể chạy song song:
  Nhóm 1: [common]
  Nhóm 2: [utils, core]    (cùng chỉ phụ thuộc common)
  Nhóm 3: [service]        (chờ core và utils)
  Nhóm 4: [api]
  Nhóm 5: [app]

Với -T 4 (4 thread), Maven build utils và core song song, vì giữa hai module này không có đường phụ thuộc nào.

3. Maven source — ProjectSorter và DefaultGraphBuilder

-- Ý tưởng của ProjectSorter (rút gọn, KHÔNG phải source nguyên văn)
dag <- DAG rỗng
for each module m: dag.addVertex(m)
for each module m, với mỗi module d mà m phụ thuộc:
    dag.addEdge(m, d)    -- nếu cạnh này khép thành cycle: ném CycleDetectedException

order <- TopologicalSorter.sort(dag)   -- DFS, module được phụ thuộc đứng trước

TopologicalSorter của plexus-utils là DFS với ba trạng thái (chưa thăm, đang thăm, đã thăm), đúng kiểu tô ba màu ở bài 03: module được ghi vào danh sách lúc rời khỏi đỉnh (postorder), nên module được phụ thuộc đứng trước module phụ thuộc vào nó. Đây là bản DFS của bài 04, không phải Kahn.

Phát hiện cycle: theo code của ProjectSorter, việc bắt CycleDetectedException nằm ngay chỗ thêm cạnh vào DAG, tức cycle bị phát hiện sớm, trước cả bước sắp xếp. DefaultGraphBuilder bọc lỗi này thành ProjectCycleException với thông báo bắt đầu bằng "The projects in the reactor contain a cyclic reference". Bạn phải phá cycle (thường bằng cách tách code dùng chung ra module common) rồi mới build được.

4. Maven parallel build — anti-chain trong DAG

-T 4 là flag "4 thread". Maven chỉ build song song những module không phụ thuộc nhau (anti-chain trong DAG).

-- Ý tưởng lập lịch cho -T (rút gọn). Phần bộ lập lịch nằm ở package multithreaded
-- của lifecycle.internal.builder; DefaultProjectDependencyGraph chỉ cung cấp
-- getUpstreamProjects(project, transitive) để biết module nào phải xong trước.

-- Anti-chain là tập đỉnh không có đường đi giữa bất kỳ hai đỉnh nào
--   ready = các module không còn upstream chưa build
--   while ready không rỗng:
--     lấy tối đa T module từ ready, submit vào thread pool
--     khi module xong, kiểm tra lại module nào trở thành ready

Về ý tưởng, vòng lặp này giống phần "lấy các đỉnh in-degree 0" của Kahn, nhưng chạy bất đồng bộ: Maven lấy nhiều module cùng lúc, tối đa T thread, và module nào xong trước thì mở khoá các module đang chờ nó.

Thử ngẫmlập lịch theo anti-chain giống phần lấy đỉnh in-degree 0 của Kahn nhưng bất đồng bộ: module xong trước mở khoá các module sau ngay, không đợi cả lô. Với -T 4 và một module build lâu gấp 10 lần các module khác, 3 thread còn lại có phải ngồi chờ không, và chờ cái gì?

5. Production gotcha — Maven

Gotcha 1: Diamond dependency conflict

         A
        / \
       B   C
        \ /
         D (v1.0 qua B, v2.0 qua C)

A phụ thuộc B và C. B phụ thuộc D v1.0. C phụ thuộc D v2.0. Maven chọn version nào cho D?

Maven dùng quy tắc "nearest definition" (định nghĩa gần nhất): version nằm gần root nhất trong cây dependency thắng. Nếu B được khai báo trước C trong pom.xml của A, Maven chọn D v1.0, có thể không phải version mới nhất hay đúng nhất.

Cách sửa: dùng <dependencyManagement> trong parent POM để ép một version cụ thể:

<!-- parent pom.xml: ép D về v2.0 bất kể path transitive nào -->
<dependencyManagement>
  <dependencies>
    <dependency>
      <groupId>com.example</groupId>
      <artifactId>D</artifactId>
      <version>2.0</version>  <!-- explicit override -->
    </dependency>
  </dependencies>
</dependencyManagement>

Gotcha 2: Provided scope bị bỏ sót

Scope provided (ví dụ Servlet API) không truyền gián tiếp (transitive). Nếu module service khai báo servlet-api là provided, module api chỉ phụ thuộc vào service sẽ không có servlet-api trên classpath. Muốn dùng HttpServletRequest, api phải tự khai báo dependency đó, nếu không sẽ lỗi compile.

Gotcha 3: Build cache (Maven 3.9+) dựa vào hash nội dung

Build cache là extension của Maven (maven-build-cache-extension, dùng được với Maven 3.9+). Nó tính hash nội dung đầu vào của từng module (file source cộng dependency). Nếu hash giống lần build trước thì input không đổi, Maven lấy kết quả đã lưu và bỏ qua module đó thay vì compile lại.

Hash ở đây dùng để so sánh "input có đổi không", và phải chính xác tuyệt đối: hash trùng nhầm đồng nghĩa với việc dùng lại kết quả build cũ cho code đã đổi.

6. Gradle — cùng DAG, aggressive hơn

Gradle cũng dùng topo sort trên DAG nhưng tối ưu đi xa hơn:

Configuration on demand: chỉ nạp và cấu hình những module mà task hiện tại cần, không quét toàn bộ project như Maven. Với monorepo hàng nghìn module, khác biệt về tốc độ là đáng kể.

Configuration cache (Gradle 6.6+): sau khi tính DAG lần đầu, Gradle lưu toàn bộ task graph ra disk. Lần build sau, nếu build file không đổi, Gradle bỏ qua hẳn giai đoạn configuration và chỉ chạy task. Với project lớn, phần thời gian tiết kiệm được là đáng kể.

Bỏ qua task không đổi: Gradle theo dõi đầu vào và đầu ra của từng task; đầu vào không đổi thì task được coi là up-to-date và bỏ qua, mịn hơn việc bỏ qua cả module.

Thử ngẫmGradle theo dõi output của từng task riêng, nên A không đổi thì B phụ thuộc A không phải chạy lại dù A đã chạy. Maven bỏ qua theo từng module: nó làm được việc này ở mức từng file, hay chỉ ở mức cả module?

7. Thông tin dự án B: Google Maps routing

Bài báo công khai: "Customizable Route Planning in Road Networks" của Delling, Goldberg, Pajor, Werneck (2017, Microsoft Research).

Bản mã nguồn mở: OSRM (Open Source Routing Machine), https://github.com/Project-OSRM/osrm-backend, có cài đặt Contraction Hierarchy (và một thuật toán thứ hai theo hướng Customizable Route Planning).

Google không công khai source hay thuật toán routing của Google Maps. Các mục dưới đây mô tả pipeline tiêu biểu của routing quy mô bản đồ theo tài liệu công khai và OSRM; tên "Google Maps" ở các tiêu đề chỉ lớp hệ thống này, không khẳng định chi tiết nội bộ của Google.

8. Vì sao Dijkstra naive không scale

Mạng đường cỡ châu lục đến toàn cầu có hàng chục triệu đỉnh và cỡ trăm triệu cạnh trở lên. Dijkstra thường từ bài 05:

Dijkstra naive (ước lượng thô):
  V = 50 triệu đỉnh, E = 100 triệu cạnh
  Mỗi query: O((V + E) log V) ~ 150 triệu * 26 ~ vài tỷ thao tác heap
  Thực tế trên mạng cỡ châu lục, các bài báo báo cáo cỡ vài giây mỗi query
  Mục tiêu của dẫn đường thời gian thực: vài chục mili-giây trở xuống

Cần một cách tối ưu triệt để: không phải chỉnh hằng số, mà phải thu hẹp hẳn vùng cần tìm.

9. Google Maps routing pipeline — 4 layer

Bốn lớp dưới đây là pipeline tiêu biểu theo tài liệu công khai (bài báo CH, bài báo CRP, OSRM).

Layer 1: Raw road graph

Đỉnh = nút giao thông (ngã tư, điểm rẽ)
Cạnh = đoạn đường giữa 2 nút
Trọng số = thời gian di chuyển dự kiến (giây)

Ví dụ minh hoạ (số giả định): Hà Nội nội đô
  Đỉnh: nút giao Hồ Hoàn Kiếm
  Cạnh: Tràng Tiền → Hàng Khay (trọng số = 45s giờ cao điểm)
        Hàng Khay → Đinh Tiên Hoàng (trọng số = 30s)

Layer 2: Pre-processing — Contraction Hierarchy

Contraction Hierarchy (CH) là kỹ thuật tiền xử lý then chốt của nhiều engine routing (OSRM chẳng hạn). Ý tưởng: "co" (contract, tức loại bỏ) các đỉnh "không quan trọng" và thêm cạnh tắt (shortcut edge) thay thế.

Trước khi contract đỉnh B:
  A --5--> B --3--> C
  (A đến C đi qua B, tổng cost = 8)

Sau khi contract B:
  A --8--> C    (shortcut edge, bỏ qua B)
  B vẫn tồn tại nhưng không nằm trong search path chính
  (cạnh tắt chỉ được thêm nếu không có đường khác ngắn không kém đi vòng qua A và C)

Đỉnh "không quan trọng" là đỉnh mà việc co nó không đẻ ra nhiều cạnh tắt, thường là nút giao nhỏ trong khu dân cư. Đỉnh "quan trọng" là nút giao cao tốc, quốc lộ chính, và được giữ lại.

Sau khi co toàn bộ đỉnh theo thứ tự tầm quan trọng tăng dần, mỗi đỉnh có một "thứ hạng", và ta được một "tầng cao tốc": đường lớn nằm ở thứ hạng cao, cạnh tắt bỏ qua các phố nhỏ. Tiền xử lý chạy offline một lần (cỡ vài chục phút đến dưới một giờ cho mạng đường Tây Âu trong bài báo gốc), còn mỗi truy vấn chỉ tốn cỡ trăm micro-giây đến vài mili-giây.

Layer 3: Query — Bidirectional search

Bidirectional Dijkstra: chạy hai Dijkstra cùng lúc, một từ nơi xuất phát đi tới, một từ đích đi lùi. Hai lượt tìm "gặp nhau" ở giữa.

Forward search:  source -> ... -> meeting point
Backward search: destination -> ... -> meeting point

Kết hợp: shortest path = dist_forward[m] + dist_backward[m]
         với m là meeting vertex tối ưu

Vì sao nhanh hơn? Dijkstra thường mở rộng thành "vòng tròn" bán kính R quanh nơi xuất phát cho đến khi chạm đích. Bidirectional mở rộng hai vòng tròn bán kính R/2, diện tích mỗi vòng là π×(R/2)², tổng là π×R²/2, tức vùng cần tìm giảm một nửa. Đó là mức giảm khiêm tốn.

Truy vấn CH là bidirectional search trên graph đã có cạnh tắt, với một luật thêm: mỗi chiều chỉ được đi tới đỉnh có thứ hạng cao hơn. Nhờ vậy mỗi chiều chỉ thăm một vùng rất nhỏ (cỡ vài trăm đến vài nghìn đỉnh trên mạng đường lớn), vì chúng nhanh chóng "leo" lên các tuyến lớn rồi gặp nhau. Đây mới là nguồn của mức tăng tốc cỡ hàng chục nghìn lần so với Dijkstra thường trong các bài báo.

A* với heuristic Euclidean là một kỹ thuật riêng, có thể dùng ở các engine không dựa trên CH:

-- A* heuristic: lower bound trên khoảng cách còn lại
-- h(v) = khoảng cách đường thẳng từ v đến destination / tốc độ tối đa
-- Đảm bảo admissible: không bao giờ overestimate travel time thực tế

heuristic(v, destination):
    euclideanDist <- haversine(v.lat, v.lng, destination.lat, destination.lng)
    -- tốc độ tối đa ~ 120 km/h = 33.3 m/s
    return euclideanDist / MAX_ROAD_SPEED

A* ưu tiên mở rộng đỉnh có dist[v] + h(v) nhỏ nhất. Vì cận dưới theo tốc độ tối đa khá lỏng, mức giảm trên mạng đường thực tế chỉ ở mức vừa phải.

Layer 4: Real-time traffic update

Weight của cạnh không cố định: giờ cao điểm làm thời gian đi tăng đáng kể. Vấn đề là CH tiền xử lý gắn chặt với weight: weight đổi thì cạnh tắt có thể sai. Hai hướng giải trong tài liệu công khai:

• Dựng sẵn nhiều profile (giờ cao điểm sáng, chiều, cuối tuần, ban đêm), mỗi profile một lần tiền xử lý. Truy vấn chọn profile khớp giờ khởi hành.
• Customizable Route Planning (CRP) của Delling, Goldberg, Pajor, Werneck: tách cấu trúc graph (tiền xử lý một lần, nặng) khỏi weight (cập nhật lại nhanh khi weight đổi). Mục tiêu là phản ánh giao thông gần thời gian thực mà không phải tiền xử lý lại từ đầu.

Thử ngẫmdựng sẵn profile theo khung giờ thay vì tính lại CH cho mỗi truy vấn, và đánh đổi bằng độ chính xác so với giao thông thật. Nếu có một tai nạn bất ngờ giữa giờ thấp điểm, profile tính sẵn còn phản ánh đúng không?

10. Production gotcha — Google Maps

Gotcha 1: Weight của cạnh thay đổi theo thời gian

Giờ cao điểm có thể làm thời gian đi tăng gấp nhiều lần so với đêm khuya. Vì vậy hệ thống có thể tính sẵn nhiều profile: sáng, chiều, cuối tuần, ngày lễ. Truy vấn phải nói rõ giờ khởi hành để chọn đúng profile, vì "đường ngắn nhất lúc 8h sáng" khác "đường ngắn nhất lúc 2h đêm".

Gotcha 2: Multi-modal routing

Kết hợp lái xe, đi bộ và phương tiện công cộng (xe buýt, metro) trong một truy vấn. Mỗi phương tiện là một lớp graph riêng. Cạnh "đổi phương tiện" (ví dụ đi bộ từ xe buýt đến điểm đón taxi) có weight bằng thời gian chờ cộng thời gian đi bộ.

Graph nhiều lớp: G_drive ∪ G_walk ∪ G_transit, với các cạnh đổi phương tiện nối giữa các lớp. Chạy Dijkstra trên graph nhiều lớp này cho ra đường đi tối ưu kết hợp nhiều phương tiện.

Gotcha 3: Turn restrictions

"Cấm rẽ trái từ X sang Y" không biểu diễn đơn giản bằng weight của cạnh được, vì đó là ràng buộc về cặp cạnh liên tiếp. Phải mô hình hoá trạng thái theo cạnh: trạng thái của lượt tìm là (current_vertex, last_edge_taken), không chỉ current_vertex. Số trạng thái bằng số cạnh có hướng E thay vì V (đồ thị này là đồ thị cạnh), tức tăng cỡ vài lần trên mạng đường.

Gotcha 4: Toll roads và multi-objective optimization

Người dùng có thể chọn "tránh đường thu phí". Đây là bài toán tối ưu nhiều mục tiêu cùng lúc: vừa thời gian vừa chi phí. Có hai cách: tìm các đường Pareto-optimal (không đường nào khác vừa nhanh hơn vừa rẻ hơn), hoặc cộng các mục tiêu lại với hệ số theo ý người dùng.

11. Bảng decision matrix — thuật toán của module vs production

12. Dùng ở đâu trong thực tế

Bazel / Buck: DAG tương tự Maven nhưng chạy ở quy mô monorepo rất lớn. Cache được lưu theo từng action (đầu vào không đổi thì dùng lại đầu ra), và remote cache cho cả team dùng chung: một dev build xong, dev khác tải kết quả về thay vì build lại.

Apache Airflow / Argo Workflows: DAG task cho data pipeline. Mỗi task trong DAG của Airflow là một đỉnh, dependency là cạnh. Scheduler của Airflow chạy task theo thứ tự dependency, chạy lại task lỗi và theo dõi trạng thái. Khác Maven ở chỗ task có thể chạy nhiều lần theo lịch, nhưng lõi thuật toán đồ thị giống hệt.

GitHub Actions workflow: các job tạo thành một DAG, khai báo bằng từ khoá needs:. Các job không phụ thuộc nhau chạy song song, job nào có needs: phải đợi. Job lỗi sẽ chặn các job phía sau. Cycle trong needs: làm workflow bị báo không hợp lệ.

13. Đào sâu tài liệu gốc

14. Tóm tắt

• Maven reactor dựng DAG giữa các module, rồi sắp xếp topo bằng DFS (TopologicalSorter của plexus-utils). Cycle bị phát hiện khi thêm cạnh (CycleDetectedException), Maven dừng với lỗi cyclic reference.
• Build song song (-T N) chạy các module không phụ thuộc nhau cùng lúc, module nào xong thì mở khoá các module đang chờ.
• Diamond dependency gây xung đột version: quy tắc "nearest definition" có thể chọn không như bạn muốn; dùng <dependencyManagement> để ghim version.
• Dijkstra thường quá chậm cho mạng đường cỡ châu lục. Contraction Hierarchy tiền xử lý offline (co đỉnh, thêm cạnh tắt, gán thứ hạng), rồi truy vấn bằng bidirectional search chỉ đi lên theo thứ hạng; trong các bài báo, nhanh hơn Dijkstra hàng chục nghìn lần.
• Weight đổi theo thời gian, turn restriction và nhiều phương tiện là những phức tạp của hệ thống thật, mỗi cái cần mở rộng mô hình graph riêng. Google không công bố chi tiết routing của Google Maps nên phần này dựa trên tài liệu công khai và OSRM.

15. Tự kiểm tra

Bài tiếp theo: Module Đồ thị — Tổng kết & cheat sheet