Graphhopper

Thử Thách Kỹ Thuật (The Engineering Challenge) Xây dựng một nền tảng logistics hiện đại (như giao đồ ăn, gọi xe, hay quản lý đội xe) đòi hỏi khả năng tính toán khoảng cách và Thời gian Dự kiến Đến nơi (ETA) ở một quy mô khổng lồ. Bài toán $N^2$: Nếu bạn có 1,000 tài xế và 1,000 đơn hàng, việc tính toán khoảng cách giữa mọi tổ hợp (combination) có thể xảy ra sẽ đòi hỏi phải chạy tới 1,000,000 phép tính lộ trình riêng lẻ. Tốc độ: Những phép tính này bắt buộc phải diễn ra trong thời gian thực (dưới 50ms) để đảm bảo trải nghiệm người dùng mượt mà và ngăn không cho các thuật toán phân cuốc (dispatching) bị đứt gánh (timeout). Độ chính xác: Hệ thống phải tính tới các ràng buộc phũ phàng của thế giới thực như đường một chiều, biển cấm rẽ trái, và tình trạng kẹt xe thiên biến vạn hóa (dynamic traffic congestion). Các API điểm-tới-điểm thông thường (như mấy cái request Google Maps API cơ bản) thì quá chậm và quá đắt đỏ để có thể gánh vác việc sản xuất Ma trận Khoảng cách (Distance Matrix) hàng loạt. Bạn cần phải có một Hệ thống Định tuyến (Routing Engine) nội bộ được tối ưu hóa đến tận răng. ...

🇬🇧 Read the English version of this article on tanhdev.com Giới thiệu: Khi Nào Bạn Vượt Ngưỡng Cloud Route APIs? Trong giai đoạn đầu xây dựng hệ thống logistics, giao hàng Last-Mile, hoặc gọi xe (ride-hailing), việc sử dụng các dịch vụ đám mây như Google Maps Directions API, HERE Maps API hay Mapbox là lựa chọn an toàn không thể bàn cãi. Chúng cung cấp dự đoán thời gian đến (ETA) cực kỳ chính xác, tài liệu rõ ràng, và quan trọng nhất là bạn không tốn công sức vận hành hạ tầng (zero infrastructure maintenance). ...

Ngồi đẻ ra một cái thuật toán chạy nhanh như gió mới chỉ đi được nửa quãng đường. Phép thử lửa thực sự (true test) của một Kỹ sư Principal nằm ở chỗ: làm sao vác nguyên một cái Hệ thống Định tuyến có trạng thái (stateful Routing Engine) to tổ chảng đắp lên Cloud mà không làm rớt mạng (downtime) lấy một giây nào mỗi lúc có đợt cập nhật bản đồ hay sập cơ sở hạ tầng. ...

Dựng một cái API cùi bắp để réo gọi Graphhopper qua lệnh http.Get thì dễ ợt. Nhưng để rèn ra một cái API Gateway đẳng cấp Principal dư sức gánh còng lưng 10,000 cuốc xe nã request cùng lúc mà không đột tử, đó đích thực là một khóa masterclass về Hệ thống Phân tán (Distributed Systems). Answer-first: Graphhopper là một con service tuyến dưới (downstream service) lệ thuộc cực nặng vào CPU. Nếu cái API Golang của bạn cứ nhắm mắt hứng đạn (traffic) rồi ném tuốt luốt thẳng xuống dưới, chỉ cần Graphhopper hắt hơi sổ mũi chạy chậm lại một nhịp thôi là bầy Goroutines sẽ dồn ứ lại thành một cục máu đông, vắt kiệt sạch RAM của server và kích hoạt một cú sập dây chuyền (cascading failure). Bạn buộc phải dựng lên một phòng tuyến “Bảo Vệ Đa Lớp” (Defense in Depth) xài tới chiêu Giới hạn Đồng thời (Concurrency Bounding), Cầu dao điện (Circuit Breakers), và trò Bắn tin Bất đồng bộ (Asynchronous Pub/Sub). ...

Vụ setup một cái hệ thống định tuyến local (local routing engine) nổi tiếng là khoai lang. Mấy bài tutorial chung chung toàn quang đại cho một cái lệnh Docker cơ bản, chạy xong nó lăn quay ra chết im ỉm (crashes silently) làm dân dev ngơ ngác chả hiểu gì. Trong bài hướng dẫn này, chúng ta sẽ bỏ qua mấy cái setup “Hello World” con nít. Chúng ta sẽ xắn tay dựng một môi trường chuẩn production (production-grade) xịn xò, nhào nặn chung dữ liệu OpenStreetMap (OSM), một cái container Docker Graphhopper (Java) được tinh chỉnh đàng hoàng, và một cái API Gateway Golang gánh tải song song (high-concurrency) cực khỏe. ...

Khi xây dựng một hệ thống giao nhận hay logistics ép tải cao (high-scale), những bài hướng dẫn thuật toán chung chung trên mạng thường hay dắt mũi lập trình viên đi sai đường. Bọn họ cứ ra rả rằng A* lúc nào cũng ngon hơn Dijkstra. Thế nhưng, bước ra ngoài đời thực, trong thế giới của Hệ thống Định tuyến (Routing Engines) và Ma trận Khoảng cách (Distance Matrices), sự thật lại phũ phàng và phức tạp hơn rất nhiều. ...

🇬🇧 Read the English version of this article on tanhdev.com GraphHopper Distance Matrix Là Cái Gì? Answer-first: GraphHopper distance matrix chính là điểm kết nối /matrix API trực thuộc thư viện tìm đường mã nguồn mở (open-source routing engine) GraphHopper. Nó sẽ thu nạp thông tin tọa độ của N điểm trạm và ói trả về nguyên một ma trận kết quả kích cỡ N×N chứa toàn bộ dữ liệu thời gian di chuyển (tính theo giây) cộng thêm độ dài lộ trình khoảng cách (tính theo mét) rạch ròi bám dựa trên lưới đường xá giao thông thực tế được cung cấp bởi bản đồ OpenStreetMap — tuyệt vời nhất là mọi thứ này sẽ tính phí zero (hoàn toàn miễn phí) khi bạn chọn cách tự mang về nhà cắm điện xài (self-hosted). Thử thách với lượng chạm mốc 100 điểm dừng giao hàng (delivery stops), cỗ máy này dễ dàng xử lý phay vèo toàn vẹn 10,000 cặp lộ trình đôi chỉ trong ngưỡng chớp mắt dưới 50 mili-giây (50ms) dẫu cho chạy tàng tàng trên một con máy chủ ảo VPS hạng bèo. ...

🇬🇧 Read the English version of this article on tanhdev.com GraphHopper có lẽ là cỗ máy định tuyến (routing engine) mã nguồn mở xịn xò bậc nhất lúc này — nó nhồi đầy đủ mảng Rút Ngọn Thứ Bậc (Contraction Hierarchies - CH) cho những câu truy vấn đáp trả mượt dưới cả độ tính mili giây, nặn hồ sơ bóp nắn khuôn xe (custom vehicle profiles), khắt khe rẽ cấm góc (turn restrictions), lại kẹp nguyên bộ sậu cấu trúc hạ tầng đường sá OpenStreetMap dầy cộm. Cục sạn mà hầu hết đội nhóm cắn phải chẳng phải mảng thuật toán; nó nằm rúc ở khúc thao tác khó khăn (operational challenge) vận nó bò lết lên nổi Kubernetes: nuốt chửng một file to đùng OSM PBF vào, đẽo gọt cắt cân khối size dung lượng của JVM, xoay xở gánh qua kỳ sơ chế nhào nặn ngốn cả đóng thì giờ của mảng CH (CH pre-processing), lẫn chiêu đổi nạp dữ liệu map khỏi phải lịm tắt cúp đèn hệ thống (without downtime). ...