Thiết kế hàng đợi ưu tiên (Priority Queue) cho hệ thống gọi xe công nghệ (Ride Hailing)

Bài toán ghép cuốc xe trong giờ cao điểm trời mưa#

Vào lúc 18h trời mưa to tại trung tâm thành phố, có 5.000 khách hàng cùng bấm đặt xe trên ứng dụng Grab / Be, nhưng trong bán kính 2km chỉ có 300 tài xế đang hoạt động.

Nếu hệ thống dùng hàng đợi thông thường (First-In-First-Out - FIFO): Khách nào bấm trước được phục vụ trước. Tuy nhiên trong thực tế kinh doanh, hệ thống cần ưu tiên:

• Khách hàng hạng Bạch Kim (Platinum Members).
• Chuyến đi có quãng đường dài mang lại doanh thu cao.
• Chuyến xe cấp cứu y tế khẩn cấp.

Cấu trúc dữ liệu nào giúp hệ thống ghép cặp tài xế và khách hàng tối ưu nhất?

Cấu trúc dữ liệu: Nhị phân Heap (Binary Min/Max-Heap)#

Hàng đợi ưu tiên (Priority Queue) cho phép:

• Thêm một cuốc xe mới vào hàng đợi với độ phức tạp $O(\log N)$.
• Lấy ra cuốc xe có độ ưu tiên cao nhất ngay lập tức trong $O(1)$ (hoặc $O(\log N)$ khi cân bằng lại Heap).

interface RideRequest {
  bookingId: string;
  userId: string;
  score: number; // Điểm ưu tiên tổng hợp
}

// Hàm tính điểm ưu tiên dựa trên nhiều trọng số
function calculatePriorityScore(userTier: string, tripDistanceKm: number, waitTimeMinutes: number): number {
  let score = 0;
  if (userTier === 'PLATINUM') score += 50;
  if (userTier === 'GOLD') score += 30;
  
  score += tripDistanceKm * 2;       // Ưu tiên chuyến đi xa
  score += waitTimeMinutes * 5;      // Chờ càng lâu điểm càng cao (tránh starvation)
  return score;
}

Tránh hiện tượng "Bỏ đói" (Starvation)#

Nếu chỉ ưu tiên khách VIP, một khách hàng hạng thường có thể phải đứng chờ dưới mưa suốt 2 tiếng mà không bao giờ được phục vụ.

• Giải pháp: Cơ chế Aging (Gia tăng điểm theo thời gian). Cứ mỗi phút khách hàng phải chờ đợi, điểm ưu tiên của họ sẽ được cộng thêm 5 điểm, đảm bảo sau một khoảng thời gian nhất định họ sẽ vươn lên đầu hàng đợi!

Góc thảo luận#

Trong hệ thống thực tế phân tán, anh em triển khai Priority Queue bằng Redis Sorted Sets (ZADD với score) hay dùng module hàng đợi chuyên dụng?

Xem thêm nội dung liên quan:

• Thiết kế Hệ thống Thực chiến
• Bộ câu hỏi trắc nghiệm Cấu trúc Dữ liệu