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

Module 5 đã đi qua 10 graph algorithm: graph representation, BFS, DFS, topological sort, Dijkstra, Bellman-Ford, Floyd-Warshall, MST (Kruskal + Prim), Disjoint Set Union, và maze BFS challenge. Mỗi bài giải thích cơ chế, độ phức tạp, và tradeoff lý thuyết. Nhưng nếu hỏi production thực tế dùng đâu — câu trả lời rất cụ thể.

Mỗi khi bạn chạy mvn package, Maven đang chạy topological sort trên DAG dependency của project. Mỗi khi Google Maps tính đường trong chưa đến 10ms trên graph 100 triệu cạnh toàn cầu, nó đang dùng Dijkstra kết hợp Contraction Hierarchy và bidirectional search — không phải Dijkstra naive bài 05 đã dạy.

Bài này dive 2 system: Maven 3.x reactor build với DAG topo sort, Google Maps routing pipeline thực tế. Đọc source thật, hiểu vì sao mỗi quyết định đúng cho scale.

1. Tech profile A — Maven 3.x

Project: Apache Maven 3.x — build automation tool phổ biến nhất trong Java ecosystem.

Source liên quan:

• org.apache.maven.graph.DefaultGraphBuilder — xây DAG từ multi-module project
• org.apache.maven.graph.DefaultProjectDependencyGraph — topo sort + cycle detection
• GitHub: https://github.com/apache/maven

Maven 3 được release năm 2010, đang ở version 3.9.x (2024). Hầu hết Java project enterprise đang dùng Maven 3.x — tức là code reactor build dưới đây đang chạy trên hàng triệu CI pipeline mỗi ngày.

2. Maven reactor build flow

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

Luồng hoạt động:

1. Maven scan toan bo module trong project (reactor scan)
2. Doc moi pom.xml, thu thap <dependency> giua cac module
3. Xay DAG: moi module = vertex, moi <dependency> = directed edge
4. Topo sort DAG -> build order
5. Detect cycle: neu co A -> B -> A, throw CycleException
6. Parallel build (-T 4): cac module o cung "level" (anti-chain trong DAG) build song song

Ví dụ 6-module project:

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

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

DAG (simplified):
  common <-- utils <-- core <-- service <-- api <-- app

Topo order: [common, utils, core, service, api, app]

Parallel groups (anti-chains):
  Group 1: [common]               (no dependency)
  Group 2: [utils]                (depends on common only)
  Group 3: [core]                 (depends on common + utils)
  Group 4: [service]              (depends on core)
  Group 5: [api, ...other]        (depends on service)
  Group 6: [app]                  (depends on api)

Với -T 4 (4 threads), Maven build song song các module trong cùng group — không vi phạm dependency order.

3. Maven source — DefaultGraphBuilder

// Simplified DefaultGraphBuilder (org.apache.maven.graph)
// Source: https://github.com/apache/maven
public Result<ProjectDependencyGraph> build(
        MavenSession session, List<MavenProject> projects) {

    // Step 1: collect dependency edges between modules
    Map<MavenProject, Set<MavenProject>> dependencies =
        collectDependencies(projects);

    // Step 2: topological sort (Kahn BFS-based internally)
    List<MavenProject> sortedProjects =
        topologicalSort(dependencies);

    // Step 3: cycle detection -- if cycle found, topo sort
    // returns partial result; size check reveals it
    if (hasCycle(dependencies)) {
        throw new CycleDetectedException(
            "Build has circular dependency");
    }

    return new ProjectDependencyGraph(sortedProjects, dependencies);
}

topologicalSort bên trong Maven dùng Kahn BFS-based (bài 04): tính in-degree, queue module không có dependency chưa built, poll và decrement neighbor. Kết quả là sortedProjects — thứ tự compile đúng.

Cycle detection: Maven detect cycle bằng cách check order.size() != n sau Kahn (giống lesson 04, section 3). Khi có cycle, Maven ném CycleDetectedException với thông báo rõ ràng — bạn phải phá cycle (thường bằng cách extract module common chứa code chia sẻ) trước khi build được.

4. Maven parallel build — anti-chain trong DAG

-T 4 là flag "4 threads". Maven tìm anti-chain trong DAG — tập hợp các module không có dependency với nhau — và build song song.

// Simplified parallel scheduling (DefaultProjectDependencyGraph)
// An anti-chain is a set of vertices with no path between any two
public List<MavenProject> getUpstreamProjects(MavenProject project,
                                               boolean transitive) {
    // Returns all modules that must be built before this module
    // Used by scheduler: module is "ready" when all upstream are done
    return upstreamProjects.getOrDefault(project, Collections.emptyList());
}

// Scheduler loop (simplified):
//   ready = modules with no unbuilt upstream dependencies
//   while ready is not empty:
//     pick up to T modules from ready, submit to thread pool
//     when module completes, re-check which new modules become ready

Cơ chế này giống Kahn BFS nhưng "asynchronous": thay vì poll tuần tự, Maven poll nhiều module song song đến giới hạn T thread. Module nào xong trước thì unblock neighbor của nó.

5. Production gotcha — Maven

Gotcha 1: Diamond dependency conflict

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

A depend on B và C. B depend on D v1.0. C depend on D v2.0. Maven chọn version nào cho D?

Maven dùng "nearest definition" rule: version gần root nhất trong dependency tree thắng. Nếu B được khai báo trước C trong pom.xml của A, Maven pick D v1.0 — có thể không phải version mới nhất hay đúng nhất.

Fix: dùng <dependencyManagement> trong parent POM để force version cụ thể:

<!-- parent pom.xml: force D to v2.0 regardless of transitive path -->
<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

provided scope (ví dụ Servlet API) không được transitive — child module không tự kế thừa. Nếu child module dùng HttpServletRequest nhưng quên khai báo provided dependency, code compile OK (parent có) nhưng IDE báo lỗi và runtime trên môi trường thiếu container sẽ crash.

Gotcha 3: Build cache (Maven 3.9+) và Bloom filter

Maven 3.9 giới thiệu build cache: track input hash của mỗi module (source files + dependencies). Nếu hash không đổi so với lần build trước, skip module đó — không compile lại.

Cross-link với Module 3 lesson 09 (Bloom filter): fingerprint check trước khi lookup cache là pattern tương tự — nhanh chóng loại bỏ "chắc chắn không có trong cache" trước khi phải kiểm tra đầy đủ.

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

Gradle dùng cùng DAG topo sort concept nhưng push optimization xa hơn:

Configuration on demand: chỉ load và configure module được yêu cầu cho task hiện tại — không scan toàn bộ project như Maven. Với monorepo nghìn module, đây là tốc độ đáng kể.

Configuration cache (Gradle 6.6+): sau khi tính DAG lần đầu, Gradle serialize toàn bộ task graph ra disk. Lần build sau, nếu build file không đổi, skip hoàn toàn configuration phase — chỉ execute task. Tiết kiệm 20-60% thời gian build cho project lớn.

Incremental compilation: Gradle track output của từng task. Nếu task A output không đổi, task B depend on A không cần re-run dù A được trigger — finer-grained hơn Maven module-level skip.

7. Tech profile B — Google Maps routing

Public paper: "Customizable Route Planning in Road Networks" — Delling, Goldberg, Pajor, Werneck (2017, Microsoft Research).

Open-source equivalent: OSRM (Open Source Routing Machine) — https://github.com/Project-OSRM/osrm-backend — implement Contraction Hierarchy tương tự Google Maps.

Google Maps không public source code, nhưng paper của team và OSRM open-source implementation cho phép hiểu pipeline thực tế. OSRM được dùng trong Mapbox, nhiều ride-sharing app, và academic research.

8. Vì sao Dijkstra naive không scale

Road network toàn cầu có khoảng 100 triệu edge (đường, phố, highway). Dijkstra naive từ lesson 05:

Dijkstra naive:
  - V = 50M vertex (intersection)
  - E = 100M edge
  - Moi query: O((V + E) log V) ~ 150M * 27 ~ 4 ty operation
  - At 10^9 op/s: khoang 4 giay moi query
  - Google Maps target: duoi 10ms

=> Dijkstra naive cham hon target 400x.

Cần optimization triệt để — không phải tweak constant, mà là thay đổi cơ bản search space.

9. Google Maps routing pipeline — 4 layer

Layer 1: Raw road graph

Vertex = intersection (ngã tư, điểm rẽ)
Edge   = road segment (đoạn đường giữa 2 intersection)
Weight = expected travel time (giây)

Ví dụ: Hà Nội nội đô
  Vertex: Hoan Kiem Lake intersection
  Edge:   Trang Tien → Hang Khay (weight = 45s rush hour)
          Hang Khay → Dinh Tien Hoang (weight = 30s)

Layer 2: Pre-processing — Contraction Hierarchy

Contraction Hierarchy (CH) là kỹ thuật pre-processing key của Google Maps. Ý tưởng: "contract" (loại bỏ) các vertex "không quan trọng" và thêm shortcut edge thay thế.

Truoc khi contract vertex B:
  A --5--> B --3--> C
  (A den C di qua B, tong cost = 8)

Sau khi contract B:
  A --8--> C  (shortcut edge, bo qua B)
  B van ton tai nhung khong nam trong search path chinh

Vertex "không quan trọng" là vertex mà việc đi qua nó không tạo thêm shortcut nhiều — thường là intersection nhỏ trong khu dân cư. Vertex "quan trọng" là highway interchange, quốc lộ chính — giữ lại.

Sau khi contract toàn bộ vertex theo thứ tự tầm quan trọng tăng dần:

• Tạo ra "highway hierarchy" — lớp trên là major road, shortcut bỏ qua street nhỏ
• Search space giảm 100-1000x so với raw graph
• Pre-processing: vài giờ offline. Query: dưới 10ms.

Layer 3: Query — Bidirectional + A*

Bidirectional Dijkstra: chạy hai Dijkstra đồng thời — một từ source đi forward, một từ destination đi backward. Hai search "gặp nhau" ở giữa.

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

Ket hop: shortest path = forward_dist[m] + backward_dist[m]
         voi m la meeting vertex toi uu

Tại sao nhanh hơn? Dijkstra naive expand "vòng tròn" bán kính R xung quanh source cho đến khi đến destination. Bidirectional expand hai vòng tròn bán kính R/2 — diện tích mỗi vòng = pi*(R/2)^2, tổng = pi*R^2/2 — giảm một nửa search space.

A với heuristic Euclidean:*

// A* heuristic: lower bound on remaining distance
// h(v) = straight-line distance from v to destination / max_road_speed
// Guaranteed admissible: never overestimate actual travel time
double heuristic(Vertex v, Vertex destination) {
    double euclideanDist = haversine(v.lat, v.lng,
                                     destination.lat, destination.lng);
    // max road speed ~ 120 km/h = 33.3 m/s
    return euclideanDist / MAX_ROAD_SPEED_MS;
}

A* ưu tiên expand vertex có dist[v] + h(v) nhỏ nhất — vertex vừa gần source vừa hướng về destination. Ít expand vertex "sai hướng" hơn Dijkstra thuần.

Kết hợp: CH + Bidirectional + A* cho query time dưới 10ms trên graph toàn cầu:

Dijkstra naive:        ~4 ty operation / query
Bidirectional:         ~2 ty operation / query   (2x speedup)
+ A* heuristic:        ~500M operation / query   (4x speedup)
+ CH (shortcut):       ~100K operation / query   (5000x speedup)

Tong: ~40000x nhanh hon Dijkstra naive

Layer 4: Real-time traffic update

Edge weight không cố định — rush hour làm tăng travel time đáng kể. Google Maps nhận traffic data realtime (từ user GPS, sensor, historical pattern) và adjust edge weight.

Pre-compute: Google Maps build nhiều "profile" khác nhau cho các thời điểm — morning rush (7-9h), evening rush (17-19h), weekend, midnight. Khi query, chọn profile phù hợp với departure time.

10. Production gotcha — Google Maps

Gotcha 1: Edge weight time-varying

Rush hour có thể làm travel time tăng 3-5x so với night. Pre-compute nhiều profile: morning/evening/weekend/holiday. Query phải chỉ định departure time để pick đúng profile — "đườ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

Combine driving + walking + transit (bus, metro) trong một query. Mỗi mode là một lớp graph riêng. Edge "mode switch" (đi bộ từ xe buýt đến điểm đón taxi) có weight = thời gian chờ + thời gian đi bộ.

Layered graph: G_drive ∪ G_walk ∪ G_transit với mode-switch edge nối giữa các lớp. Dijkstra trên layered graph cho đường đi tối ưu kết hợp nhiều phương tiện.

Gotcha 3: Turn restrictions

"No left turn from X to Y" không thể model đơn giản bằng edge weight — đó là ràng buộc về cặp edge liên tiếp. Cần model với edge state: state của search là (current_vertex, last_edge_taken), không chỉ current_vertex. Graph state space tăng lên O(V * E) trong worst case.

Gotcha 4: Toll roads và multi-objective optimization

Người dùng có thể chọn "tránh đường thu phí". Đây là multi-objective: tối ưu (time, cost) đồng thời. Kỹ thuật: Pareto-optimal path (đường không bị dominated về cả time lẫn cost), hoặc weighted sum với user preference weight.

11. Bảng decision matrix — Module 5 algorithms vs production

12. Applied to tech

Bazel (Google) / Buck (Meta): DAG tương tự Maven nhưng scale tới millions of targets. Fine-grained caching ở mức file output — nếu một file .o không đổi, Bazel không recompile nó dù module cha được rebuild. Remote cache chia sẻ giữa toàn bộ team: một dev compile xong, dev khác pull cache thay vì compile lại. Topo sort + distributed cache = hàng giờ CI tiết kiệm mỗi ngày ở Google/Meta scale.

CMake / Make: Unix tradition, DAG topo sort cho parallel build qua make -j 8. Makefile target là vertex, phụ thuộc là edge. make tính topo order, sau đó schedule target song song tối đa J worker. Đơn giản hơn Maven nhiều nhưng cùng graph algorithm core.

Apache Airflow / Argo Workflows: task DAG cho data pipelines. Mỗi task trong Airflow DAG là một vertex; dependency là edge. Airflow scheduler tính topo order, execute task theo dependency order, retry failed task, track state. Khác Maven ở chỗ: task có thể chạy nhiều lần (scheduled), DAG được execute theo schedule — nhưng graph algorithm core giống hệt.

GitHub Actions workflows: job dependency DAG, khai báo qua needs: keyword. GitHub Actions tính topo sort để quyết định job nào chạy song song, job nào phải đợi. Failed job block downstream job. Cycle trong needs: bị reject khi push — validate lúc parse, không phải lúc run.

13. Deep Dive tài liệu gốc

14. Tóm tắt

• Maven reactor xây DAG từ <dependency> trong pom.xml, chạy Kahn topo sort để quyết định thứ tự build. Cycle → CycleDetectedException, không thể build cho đến khi phá cycle.
• Parallel build (-T N) schedule các module trong cùng anti-chain (không phụ thuộc nhau) chạy song song — maximize throughput mà không vi phạm dependency order.
• Diamond dependency (A → B,C → D) gây conflict version: Maven "nearest definition" có thể pick sai; dùng <dependencyManagement> để force version explicit.
• Gradle push xa hơn với configuration cache (skip tính DAG lần sau), incremental compilation (task-level output tracking), và configuration-on-demand (chỉ load module cần thiết).
• Dijkstra naive không scale cho road network 100M edge: một query tốn ~4 tỷ operation, quá chậm cho target 10ms của Google Maps.
• Contraction Hierarchy pre-process graph offline: contract vertex "không quan trọng", thêm shortcut qua highway. Giảm search space 1000x so với raw graph.
• Bidirectional Dijkstra + A* kết hợp với CH: tổng speedup ~40000x so với Dijkstra naive — đủ để query toàn cầu dưới 10ms.
• Time-varying edge weight, turn restriction, và multi-modal routing là production complication mà algorithm lý thuyết không cover — mỗi cái đòi hỏi graph model extension riêng.

15. Tự kiểm tra

Bài tiếp theo: DP framework — overlapping subproblems + optimal substructure