Xây dựng backend cho bản đồ của Uber với Go như thế nào

Xin chào :3. Đây là bài viết đầu tiên của tôi, nó sẽ cho bạn biết làm thế nào chúng tôi xây dựng bộ nhớ cho các chiếc xe hoạt hình trong của Uber. Chúng tôi hiện thị xe mô hình trên màn hình của ứng dụng “Namba Taxi for clients”. Bài viết này là về hoàn thành chặn đường, thuật toán và không liên quan đến Go.

Bắt đầu

Câu chuyện bắt đầu vào năm 2015 với giấy phép kinh doanh của chúng tôi. Chủ đề mà công ty chúng tôi hướng đến là “Ứng dụng điều khiển cho dịch vụ taxi”. Trong ứng dụng, anh mô phỏng xe nó như thế này.

Chúng tôi nghĩ. Tại sao không sử dụng trên màn hình khi khách hàng có thể theo dõi vị trí người lái xe. Và thử thách đầu tiên của chúng tôi là thiếu các dữ liệu. Chúng tôi nhận được vị trí lái xe mới mỗi 15 giây. Chúng tôi không thể chỉ giảm khoảng thời gian Cập Nhật, bởi vì khi ứng dụng của tài xế gửi dữ liệu cho chúng tôi nó được các đơn đặt hàng hiện tại, tiếp theo thứ tự, và nếu có bất kỳ cảnh báo nào mở. Cảnh báo hoạt động giống như nút SOS. Khi tài xế cần tài xế khác đang ở gần để giúp anh ta ngay. Và khi chúng tôi giảm khoảng thời gian Cập Nhật chúng tôi có thể thêm lưu lượng truy cập đến hệ thống của chúng tôi. Nhưng chúng tôi không chắc có thể xử lý được.

Bước một

Lần thử nghiệm đầu tiên của chúng tôi thật đơn giản và ngớ ngẩn:

1. Tạo các yêu cầu và lưu tọa độ.
2. Hãy yêu cầu khác và animate xe.

Nhưng bạn có thể đoán là có vấn đề với nó. Chúng tôi không thể làm xe chuyển động đúng và khi nó di chuyển qua những cánh đồng, rừng, hồ và các khu. Nó trông như thế này.

Giải pháp của vấn đề là, chúng tôi sử dụng OpenStreetMap Routing Machine (OSRM) để xây dựng các tuyến đường và cải thiện thuật toán của chúng tôi. Chúng tôi có thời gian chờ tương tự.

1. Chúng tôi tạo một yêu cầu.
2. Lưu tọa độ.
3. Gửi tọa độ lưu vào backend.
4. Xây dựng tuyến đường qua OSRM.
5. Gửi lại kết quả cho ứng dụng của khách hàng và xe mô phỏng.

Dường như nó hoạt động, nhưng chúng tôi phải đối mặt với vấn đề khác với đường một chiều.

Ví dụ, trình điều khiển được ở giao điểm đầu đỏ điểm. Nhưng điện thoại của mình có độ chính xác tình trạng và vị trí cập nhật trình điều khiển trú ở phía đối diện của ngã tư đường. Tại ứng dụng khách hàng chúng tôi nhận được các tọa độ, tiết kiệm cho họ và gửi cho phụ trợ. OSRM xây dựng một tuyến đường legit và trả lại cho các ứng dụng và nó có vẻ vô lý. Vì đánh dấu di chuyển rất nhanh.

Chúng tôi giải quyết vấn đề này một cách ngây thơ. Chúng tôi kiểm tra khoảng cách ngắn nhất giữa hai điểm và không xây dựng một tuyến đường với khoảng cách ít hơn 20 mét. Với thuật toán mà sau vài ngày thử nghiệm, chúng tôi quyết định phát hành ứng dụng của chúng tôi và nhận được phản hồi từ khách hàng.

Và bạn biết đấy, chúng ta sống trong thế giới không lý tưởng vì vậy chúng tôi quyết định test lại vài lần nữa, bởi vì một vài điều cần cải thiện.

1. Điều đầu tiên là một máy tính chi phí chuyến đi. Mọi tính toán đều ở phía bên tài xế. Trong trường hợp này, để tiết kiệm tài nguyên máy chủ chúng tôi không gửi yêu cầu vô ích. Mặt khác chúng ta cần có một thứ tin tưởng. Đó là ứng dụng di động của người lái xe. Vì vậy, chúng ta cần chạy dữ liệu song song và lưu nó về máy chủ.
2. Hơn nữa, chúng tôi nhận ra rằng mỗi lần thu thập track là tốn 15s đó là rất ít, người dùng có thể bỏ lỡ việc quan sát chuyến đi. Tôi biết không ai có thể nhìn một màn hình trong 15s khi không có gì xảy ra.
3. Hơn nữa, chúng tôi có rất nhiều vấn đề với module GPS ở phía bên tài xế. GPS xung đột với ứng dụng của tài xế.
4. Và cuối cùng, chúng tôi muốn hình ảnh xe mô phỏng trên màn hình chính.

Bây giờ một vài vấn đề cần giải quyết là:

1. Thu thập nhiều track hơn từ tài xế.
2. Hiển thị xe mô phỏng trên màn hình chính.
3. Lưu trữ chi phí của chuyến đi trên server.
4. Lưu dữ liệu từ thiết bị di động.
5. Thu thập track từng giây

Tôi muốn nói một vài lời về tiết kiệm dữ liệu di động. Chúng ta cần nó vì ở đất nước của chúng tôi, giá taxi rất rẻ. Chúng tôi sử dụng xe taxi như giao thông công cộng. Ví dụ, bạn có thể từ thành phố này đến thành phố khác chỉ tốn 2 Euro. Nó cũng giống như tàu điện ngầm ở Paris. Tuy nhiên internet của điện thoại thì chi phí rất cao. Nếu chúng tôi tiết kiệm 100 byte / giây, là chúng tôi sẽ tiết kiệm 2000$ cho công ty.

Có dữ liệu gì trong track ?

1. Vị trí của tài xế (Vĩ độ, kinh độ)
2. Phiên làm việc của tài xế sau khi đăng nhập
3. Thông tin đơn hàng (Mã đơn hàng và chi phí)

Chúng tôi quyết định rằng một track nên ít hơn 100 byte. Và chúng tôi bắt đầu để tìm giao thức để giải quyết vấn đề này.

Như bạn thấy chúng tôi có một số giao thức:

1. HTTP
2. WebSockets
3. TCP
4. UDP

Và lựa chọn lý tưởng cho chúng tôi là UDP, vì:

1. Chúng tôi chỉ gửi datagrams
2. Chúng tôi không cần đảm bảo
3. Tối giản
4. Tiết kiệm rất nhiều dữ liệu
5. Chúng tôi chỉ sử dụng 20byte/s
6. Không bị chặn trên mạng di động trong nước

Theo số liệu, chúng tôi xem xét:

1. JSON
2. MsgPack
3. Protobuff

Chúng sử dụng Protobuf vì nó rất hiệu quả cho dữ liệu nhỏ.

Và như bạn thấy các đối thủ khác nặng hơn gấp 2,3 lần.

Tổng kết chúng tôi có những gì ?

1. Chúng ta có 42 byte của payload
2. Và 20 byte của IP headers
3. Suy ra 62 byte mỗi track
4. LỢI NHUẬN

Nhưng khi bạn nhận được dữ liệu thì bạn cũng cần phải lưu trữ, đúng không?

Lưu trữ dữ liệu

Chúng tôi cần lưu trữ những dữ liệu:

1. Phiên làm việc của tài xế để xác định được tài xế.
2. Số xe để thực hiện việc tìm kiếm xe cho khách hàng qua ứng dụng
3. Mã đơn hàng và chi phí để lưu trữ dữ liệu chuyến đi từ tài xế lên máy chủ
4. Vị trí cuối cùng để thực hiện việc tìm kiếm
5. Tất cả vị trí cuối cùng để xây dựng tuyến đường

Các kho lưu trữ:

1. Percona — để lưu trữ tất cả dữ liệu. Chúng tôi lưu trữ các tài xế, đơn đặt hàng, chi phí và tất cả mọi thứ.
2. Redis như lưu trữ key-value cho bộ nhớ đệm
3. Elasticsearch cho geocoding

Như đã đề cập ở trên, chúng ta có 600 tài xế trực tuyến và cách sử dụng các kho lưu trữ để lưu dữ liệu có vẻ không thiết thực. Vì vậy, chúng tôi cần geo index

Chúng tôi đang xem xét hai geo index:

1. KD-tree
2. R-tree.

Chúng tôi đã yêu cầu cho geo index:

1. Chúng tôi cần phải tìm một lúc nhiều điểm gần đây nhất.
2. Chúng tôi cần B-tree cho phép tìm kiếm tốt nhất trong tình huống xấu nhất.

KD-tree

Và KD-cây không phù hợp với nhu cầu của chúng tôi bởi vì nó không cân bằng và chỉ có thể tìm kiếm một điểm gần nhất. Chúng tôi có thể thực hiện với nếu chỉnh sửa lại KD-Tree, nhưng chúng tôi sẽ không sửa lại vì R-Tree đã giải quyết vấn đề này.

R-tree

Nó trông như thế này.Chúng tôi có thể thực hiện tìm kiếm điểm gần đây nhất và nó B-tree tốt nhất. Chúng tôi đã chọn cái này.

Bạn có thể sở hữu nó tại đây

Cũng, chúng ta cần một cơ chế giới hạn vì chúng ta cần để làm vô hiệu các tài xế và hiển thị thông tin thực tế để vận hành. Ví dụ, loại bỏ các driver không hoạt động trong 900 giây .Và cũng cần LRU cấu trúc dữ liệu để lưu trữ các vị trí cuối cùng. Bởi vì chúng ta tạo lưu trữ cho rất nhiều mặt hàng. Khi chúng tôi cố gắng để thêm một mục, khi lưu trữ đã đầy. Chúng tôi loại bỏ các mục ít được sử dụng gần đây và chúng tôi thêm một cái mới. Vì vậy, ở đây là kiến trúc lưu trữ của chúng tôi.

1. Chúng tôi lưu trữ tất cả dữ liệu trong bộ nhớ.
2. Chúng tôi sử dụng R-cây để thực hiện một tìm kiếm các driver gần nhất.
3. Ngoài ra chúng tôi sử dụng hai bản đồ để lưu trữ các driver và thực hiện tìm kiếm bằng xe số hoặc phiên làm việc.

Tổng kết các thuật toán

Đây là các thuật toán trên backend:

1. Lấy dữ liệu bằng UDP
2. Lấy dữ liệu từ các driver
3. Nếu không tồn tại – nhận dữ liệu từ Redis
4. Kiểm tra và xác nhận dữ liệu
5. Thiết lập driver để lưu trữ
6. Nếu không tồn tại – khởi tạo LRU
7. Cập nhật R-tree

Điểm chốt HTTP

Chúng tôi thực hiện những điểm mấu chốt để tích hợp vào hệ thống của chúng tôi.

1. Trả lại driver gần nhất
2. Xoá driver khỏi kho lưu trữ (bằng số xe hoặc phiên làm việc)
3. Nhận thông tin về chuyến đi
4. Nhận thông tin về driver

Kết luận

Cuối cùng, chúng tôi muốn đưa ra kết luận mà chúng tôi sử dụng trong hệ thống backend của chúng tôi:

1. UDP + Protobuf để tiết kiếm dữ liệu
2. Bộ nhớ lưu trữ
3. R-tree cho driver gần nhất
4. LRU-bộ nhớ cache để lữu trữ các địa điểm cuối cùng
5. OSRM phù hợp với bản đồ và xây dựng các tuyến đường

Như ví dụ, bạn có thể xem qua nó tại đây. Nó có thể đơn giản nhưng thực hiện được rất nhiều tính năng được miêu tả trong bài viết.

Techtalk via blog.maddevs.io