System Design (LLD)Ride-Sharing Service

Case Study: Ride-Sharing Service Design

LevelAdvanced

Duration120 mins

TopicRide-Sharing Service

3 / 6

Matching Algorithm Design

The Heart of Ride-Sharing: Matching

The matching algorithm is the intellectual heart of any ride-sharing system. When a rider requests a trip, the system must rapidly answer: Which driver should we offer this ride to? This question involves geospatial queries, multi-criteria ranking, real-time constraints, and handling the accept/decline flow.

Why matching is hard:

Matching isn't just 'find the closest driver.' Real systems must balance multiple objectives: minimize rider wait time, maximize driver utilization, ensure fairness across drivers, handle surge conditions, respect driver preferences, and do all this in under 3 seconds. The elegance of your matching design reveals your understanding of algorithmic thinking applied to real-world constraints.

What You Will Learn

By the end of this page, you will understand how to design a matching system using geospatial indexing for driver proximity, multi-criteria ranking strategies, the offer-accept flow with timeouts, and how to abstract matching logic using the Strategy pattern for extensibility.

Understanding the Matching Problem

Let's formalize what matching actually involves:

Inputs:

A ride request with pickup location, destination, and ride type
A set of available drivers, each with a current location, vehicle type, rating, and acceptance history
A geographic radius for candidate search
Current demand/supply conditions (for surge awareness)

Output:

An ordered list of candidate drivers, ranked by suitability
Or a determination that no suitable drivers exist

Constraints:

Latency: Complete within ~3 seconds
Freshness: Driver locations may be 5-30 seconds stale
Concurrency: Multiple requests matching simultaneously
Fairness: Drivers should receive offers fairly over time

Matching Criteria
Criterion	Weight Factor	Rationale
Distance to pickup	High	Primary factor; affects rider wait time and driver deadhead
Estimated time of arrival (ETA)	High	More accurate than distance; accounts for traffic, one-way streets
Driver rating	Medium	Quality assurance; riders prefer higher-rated drivers
Vehicle type match	Required	Request for Premium cannot match to Standard
Driver acceptance rate	Low-Medium	Prefer drivers likely to accept; avoid offer cascading
Fair distribution	Low	Ensure all drivers get opportunities over time

ETA vs Distance

A driver 2km away through heavy traffic might have a 15-minute ETA, while a driver 3km away on a highway has a 5-minute ETA. Production systems use road-network ETA from mapping services (Google Maps, Mapbox). For LLD interviews, you can abstract to an ETAService interface.

Geospatial Driver Query

The first step in matching is finding drivers near the pickup location. With millions of drivers across a city, we cannot scan all drivers for every request—we need efficient spatial indexing.

Spatial indexing approaches:

Geohash-based grid: Divide the world into cells using geohash strings. Drivers are indexed by their geohash. Query by finding the cell containing the pickup plus adjacent cells.
Quadtree/R-tree: Hierarchical spatial data structures that enable O(log n) range queries. More complex but more accurate.
Database spatial indexes: PostgreSQL with PostGIS, MongoDB with 2dsphere indexes, or specialized geo-databases.

For LLD, we abstract this behind a DriverLocationService interface.

DriverLocationService.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
interface DriverLocationService {
    /**
     * Find available drivers within radius of a location.
     * Returns drivers with fresh location data.
     */
    findNearbyDrivers(
        location: Location,
        radiusKm: number,
        vehicleType?: VehicleType
    ): Promise<DriverWithDistance[]>;
 
    /**
     * Update a driver's current location.
     * Called every few seconds when driver is online.
     */
    updateDriverLocation(driverId: string, location: Location): Promise<void>;
 
    /**
     * Mark driver as unavailable (offline or on trip).
     */
    removeDriver(driverId: string): Promise<void>;
}
 
interface DriverWithDistance {
    driver: Driver;
    distanceKm: number;
    estimatedArrivalSeconds: number;
}
 
// Simplified in-memory implementation for demonstration
class InMemoryDriverLocationService implements DriverLocationService {
    private driverLocations: Map<string, { driver: Driver; location: Location; timestamp: Date }>;
    private readonly maxStaleSeconds = 30;
 
    constructor() {
        this.driverLocations = new Map();
    }
 
    async findNearbyDrivers(
        location: Location,
        radiusKm: number,
        vehicleType?: VehicleType
    ): Promise<DriverWithDistance[]> {
        const results: DriverWithDistance[] = [];
        const now = Date.now();
 
        for (const [id, entry] of this.driverLocations) {
            // Skip stale locations
            const ageSeconds = (now - entry.timestamp.getTime()) / 1000;
            if (ageSeconds > this.maxStaleSeconds) continue;
 
            // Skip unavailable drivers
            if (!entry.driver.isAvailableForRide()) continue;
 
            // Filter by vehicle type if specified
            if (vehicleType && entry.driver.getVehicleType() !== vehicleType) continue;
 
            // Calculate distance
            const distanceKm = location.distanceTo(entry.location);
            if (distanceKm <= radiusKm) {
                results.push({
                    driver: entry.driver,
                    distanceKm,
                    // Rough ETA: assume 30 km/h average city speed
                    estimatedArrivalSeconds: (distanceKm / 30) * 3600,
                });
            }
        }
 
        return results;
    }
 
    async updateDriverLocation(driverId: string, location: Location): Promise<void> {
        const existing = this.driverLocations.get(driverId);
        if (existing) {
            existing.location = location;
            existing.timestamp = new Date();
        }
    }
 
    async removeDriver(driverId: string): Promise<void> {
        this.driverLocations.delete(driverId);
    }
}

Production Considerations

In production, this service would be backed by Redis with geospatial commands (GEORADIUS), a dedicated geo-database, or a service like Google S2 geometry library. The abstraction lets us swap implementations without changing matching logic.

Driver Ranking Strategy

Once we have candidate drivers, we must rank them. Different ranking strategies serve different business objectives. This is a perfect application of the Strategy pattern—we can swap ranking algorithms without changing the matching flow.

Common ranking strategies:

Nearest Driver: Pure proximity; minimize rider wait time
Best ETA: Account for traffic; more accurate wait prediction
Quality Weighted: Balance distance with driver rating
Round Robin / Fair Distribution: Ensure drivers get opportunities
Batch Optimal: For pooling; optimize across multiple requests

MatchingStrategy.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
interface MatchingStrategy {
    /**
     * Rank drivers for a given ride request.
     * Returns drivers in order of preference (best first).
     */
    rankDrivers(
        candidates: DriverWithDistance[],
        request: RideRequest
    ): DriverWithDistance[];
}
 
/**
 * Simple strategy: rank by distance (closest first).
 */
class NearestDriverStrategy implements MatchingStrategy {
    rankDrivers(candidates: DriverWithDistance[]): DriverWithDistance[] {
        return [...candidates].sort((a, b) => a.distanceKm - b.distanceKm);
    }
}
 
/**
 * Rank by estimated arrival time (accounts for speed/traffic).
 */
class BestETAStrategy implements MatchingStrategy {
    rankDrivers(candidates: DriverWithDistance[]): DriverWithDistance[] {
        return [...candidates].sort(
            (a, b) => a.estimatedArrivalSeconds - b.estimatedArrivalSeconds
        );
    }
}
 
/**
 * Multi-factor scoring: balance ETA, rating, and acceptance rate.
 */
class WeightedScoreStrategy implements MatchingStrategy {
    private etaWeight: number = 0.5;
    private ratingWeight: number = 0.3;
    private acceptanceWeight: number = 0.2;
 
    rankDrivers(candidates: DriverWithDistance[]): DriverWithDistance[] {
        // Normalize factors to 0-1 scale, then compute weighted score
        const maxEta = Math.max(...candidates.map(c => c.estimatedArrivalSeconds));
        
        const scored = candidates.map(c => {
            const etaScore = 1 - (c.estimatedArrivalSeconds / maxEta);  // Lower ETA = higher score
            const ratingScore = c.driver.getRating() / 5.0;
            const acceptanceScore = c.driver.getAcceptanceRate();
 
            const totalScore = 
                this.etaWeight * etaScore +
                this.ratingWeight * ratingScore +
                this.acceptanceWeight * acceptanceScore;
 
            return { candidate: c, score: totalScore };
        });
 
        return scored
            .sort((a, b) => b.score - a.score)  // Higher score first
            .map(s => s.candidate);
    }
}
 
/**
 * Fair distribution: consider how recently driver received offers.
 * Prevents the same drivers from getting all the good trips.
 */
class FairDistributionStrategy implements MatchingStrategy {
    private lastOfferTime: Map<string, number> = new Map();
    private fairnessWeight: number = 0.3;
    private etaWeight: number = 0.7;
 
    rankDrivers(candidates: DriverWithDistance[]): DriverWithDistance[] {
        const now = Date.now();
        const maxEta = Math.max(...candidates.map(c => c.estimatedArrivalSeconds));
 
        const scored = candidates.map(c => {
            const etaScore = 1 - (c.estimatedArrivalSeconds / maxEta);
            
            // Fairness: time since last offer (longer = higher score)
            const lastOffer = this.lastOfferTime.get(c.driver.getId()) || 0;
            const timeSinceOffer = now - lastOffer;
            const fairnessScore = Math.min(timeSinceOffer / 300000, 1); // Cap at 5 min
 
            const totalScore = 
                this.etaWeight * etaScore +
                this.fairnessWeight * fairnessScore;
 
            return { candidate: c, score: totalScore };
        });
 
        return scored.sort((a, b) => b.score - a.score).map(s => s.candidate);
    }
 
    recordOffer(driverId: string): void {
        this.lastOfferTime.set(driverId, Date.now());
    }
}

Strategy Pattern Benefit

By implementing ranking as a Strategy, we can A/B test different algorithms, switch strategies based on time of day (use fairness during slow hours, pure ETA during rush hour), or let cities configure their preferred approach—all without modifying the matching engine.

The Offer-Accept-Decline Flow

Unlike taxi dispatch where drivers are assigned, ride-sharing typically lets drivers accept or decline offers. This introduces complexity: What if the best driver declines? How long do we wait? When do we cascade to the next driver?

The offer lifecycle:

Send offer to top-ranked driver
Start acceptance timer (e.g., 15 seconds)
Driver accepts → Proceed to trip assignment
Driver declines or times out → Offer to next driver
Repeat until match or exhausted
All drivers exhausted → Notify rider of failure

MatchingEngine.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
interface RideOffer {
    id: string;
    trip: Trip;
    driver: Driver;
    estimatedFare: Fare;
    pickupEtaSeconds: number;
    expiresAt: Date;
    status: 'PENDING' | 'ACCEPTED' | 'DECLINED' | 'EXPIRED';
}
 
class MatchingEngine {
    private locationService: DriverLocationService;
    private matchingStrategy: MatchingStrategy;
    private offerTimeoutSeconds: number = 15;
    private maxSearchRadiusKm: number = 10;
    private maxCascadeAttempts: number = 5;
 
    constructor(
        locationService: DriverLocationService,
        matchingStrategy: MatchingStrategy
    ) {
        this.locationService = locationService;
        this.matchingStrategy = matchingStrategy;
    }
 
    async findMatch(request: RideRequest): Promise<MatchResult> {
        // Step 1: Find nearby candidates
        const candidates = await this.locationService.findNearbyDrivers(
            request.getPickupLocation(),
            this.maxSearchRadiusKm,
            request.getVehicleType()
        );
 
        if (candidates.length === 0) {
            return { success: false, reason: 'NO_DRIVERS_NEARBY' };
        }
 
        // Step 2: Rank by strategy
        const rankedDrivers = this.matchingStrategy.rankDrivers(candidates, request);
 
        // Step 3: Cascade through drivers
        for (let i = 0; i < Math.min(rankedDrivers.length, this.maxCascadeAttempts); i++) {
            const candidate = rankedDrivers[i];
            const offer = this.createOffer(request.getTrip(), candidate);
 
            const response = await this.sendOfferAndWait(offer);
 
            if (response === 'ACCEPTED') {
                return { 
                    success: true, 
                    driver: candidate.driver,
                    estimatedPickupSeconds: candidate.estimatedArrivalSeconds
                };
            }
            // DECLINED or EXPIRED: continue to next driver
        }
 
        return { success: false, reason: 'NO_DRIVER_ACCEPTED' };
    }
 
    private createOffer(trip: Trip, candidate: DriverWithDistance): RideOffer {
        return {
            id: generateUUID(),
            trip,
            driver: candidate.driver,
            estimatedFare: trip.getEstimatedFare(),
            pickupEtaSeconds: candidate.estimatedArrivalSeconds,
            expiresAt: new Date(Date.now() + this.offerTimeoutSeconds * 1000),
            status: 'PENDING',
        };
    }
 
    private async sendOfferAndWait(offer: RideOffer): Promise<'ACCEPTED' | 'DECLINED' | 'EXPIRED'> {
        // In reality: push notification to driver app, await response
        // This is a simplified synchronous representation
        
        // Send notification to driver
        await this.notifyDriver(offer);
 
        // Wait for response with timeout
        return new Promise((resolve) => {
            const timeout = setTimeout(() => {
                offer.status = 'EXPIRED';
                resolve('EXPIRED');
            }, this.offerTimeoutSeconds * 1000);
 
            // Driver response would come through event/callback
            // Simplified: assume external system calls handleDriverResponse
        });
    }
 
    handleDriverResponse(offerId: string, accepted: boolean): void {
        // Called when driver taps Accept or Decline
        // Would resolve the promise in sendOfferAndWait
    }
 
    private async notifyDriver(offer: RideOffer): Promise<void> {
        // Push notification with offer details
        // Includes: pickup address, destination, fare, time to respond
    }
}
 
interface MatchResult {
    success: boolean;
    driver?: Driver;
    estimatedPickupSeconds?: number;
    reason?: string;
}

Concurrency and Race Conditions

Multiple ride requests may target the same drivers simultaneously, creating race conditions. Consider: two riders request rides near the same driver. Both matching processes rank this driver #1. Who gets them?

Concurrency challenges:

Double-booking: Same driver offered to two riders simultaneously
Stale availability: Driver accepted another offer but location service hasn't updated
Cascading delays: Many requests timing out on busy drivers

Common Pitfalls

•Offering same driver to multiple riders
•Not locking driver during offer window
•Stale location/availability data
•Long cascade chains blocking drivers

Solutions

•Optimistic locking on driver state
•Temporary 'OFFERED' status during timeout
•Frequent location/status sync
•Limit cascade attempts; fail fast

ConcurrentMatching.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// Driver status must prevent double-offering
enum DriverStatus {
    OFFLINE = 'OFFLINE',
    AVAILABLE = 'AVAILABLE',
    OFFERED = 'OFFERED',    // Temporarily locked during offer window
    ASSIGNED = 'ASSIGNED',
    IN_TRIP = 'IN_TRIP',
}
 
class DriverRepository {
    /**
     * Atomically try to lock a driver for an offer.
     * Returns true if successful, false if driver no longer available.
     */
    async tryLockForOffer(driverId: string): Promise<boolean> {
        // Atomic compare-and-swap operation
        // UPDATE drivers SET status = 'OFFERED' 
        // WHERE id = driverId AND status = 'AVAILABLE'
        // RETURNING id
        
        // If row returned, lock acquired; else driver was taken
        return true; // Simplified
    }
 
    async releaseLock(driverId: string): Promise<void> {
        // Called when offer expires or is declined
        // Sets status back to AVAILABLE
    }
 
    async assignToTrip(driverId: string): Promise<void> {
        // Called when offer is accepted
        // Sets status to ASSIGNED
    }
}

Optimistic vs Pessimistic Locking

Pessimistic locking (lock driver during entire offer window) is simpler but reduces matching throughput. Optimistic locking (check at assignment time) allows parallel offers but requires handling 'driver already taken' gracefully. Production systems often use a hybrid: short pessimistic locks with quick timeout.

Matching Algorithm Summary

Key Takeaways

•Matching is a geospatial + ranking problem — First find nearby drivers efficiently, then rank by multiple criteria.
•Abstract location queries behind a service — DriverLocationService encapsulates spatial indexing implementation details.
•Use Strategy pattern for ranking — Enables swapping algorithms (nearest, best ETA, weighted score, fair distribution) without changing core logic.
•Handle the offer cascade gracefully — Drivers may decline; cascade to next candidate with proper timeouts.
•Manage concurrency with driver locking — Prevent double-booking through atomic status transitions.

What's next:

With matching covered, we'll design the pricing system—calculating fares based on distance, time, vehicle type, and surge multipliers. We'll also dive deeper into the Trip state machine and how it orchestrates the entire ride lifecycle.

Page Complete

You now understand how to design a ride-sharing matching algorithm: geospatial queries for candidate discovery, Strategy pattern for flexible ranking, offer-accept flow with timeouts and cascading, and concurrency handling to prevent double-booking. Next, we tackle pricing and state management.

3 / 6

Loading learning content...

System Design (LLD)Ride-Sharing Service

Case Study: Ride-Sharing Service Design

LevelAdvanced

Duration120 mins

TopicRide-Sharing Service

3 / 6

Matching Algorithm Design

The Heart of Ride-Sharing: Matching

Why matching is hard:

What You Will Learn

Understanding the Matching Problem

Let's formalize what matching actually involves:

Inputs:

A ride request with pickup location, destination, and ride type
A set of available drivers, each with a current location, vehicle type, rating, and acceptance history
A geographic radius for candidate search
Current demand/supply conditions (for surge awareness)

Output:

An ordered list of candidate drivers, ranked by suitability
Or a determination that no suitable drivers exist

Constraints:

Latency: Complete within ~3 seconds
Freshness: Driver locations may be 5-30 seconds stale
Concurrency: Multiple requests matching simultaneously
Fairness: Drivers should receive offers fairly over time

Matching Criteria
Criterion	Weight Factor	Rationale
Distance to pickup	High	Primary factor; affects rider wait time and driver deadhead
Estimated time of arrival (ETA)	High	More accurate than distance; accounts for traffic, one-way streets
Driver rating	Medium	Quality assurance; riders prefer higher-rated drivers
Vehicle type match	Required	Request for Premium cannot match to Standard
Driver acceptance rate	Low-Medium	Prefer drivers likely to accept; avoid offer cascading
Fair distribution	Low	Ensure all drivers get opportunities over time

ETA vs Distance

Geospatial Driver Query

The first step in matching is finding drivers near the pickup location. With millions of drivers across a city, we cannot scan all drivers for every request—we need efficient spatial indexing.

Spatial indexing approaches:

Geohash-based grid: Divide the world into cells using geohash strings. Drivers are indexed by their geohash. Query by finding the cell containing the pickup plus adjacent cells.
Quadtree/R-tree: Hierarchical spatial data structures that enable O(log n) range queries. More complex but more accurate.
Database spatial indexes: PostgreSQL with PostGIS, MongoDB with 2dsphere indexes, or specialized geo-databases.

For LLD, we abstract this behind a DriverLocationService interface.

DriverLocationService.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
interface DriverLocationService {
    /**
     * Find available drivers within radius of a location.
     * Returns drivers with fresh location data.
     */
    findNearbyDrivers(
        location: Location,
        radiusKm: number,
        vehicleType?: VehicleType
    ): Promise<DriverWithDistance[]>;
 
    /**
     * Update a driver's current location.
     * Called every few seconds when driver is online.
     */
    updateDriverLocation(driverId: string, location: Location): Promise<void>;
 
    /**
     * Mark driver as unavailable (offline or on trip).
     */
    removeDriver(driverId: string): Promise<void>;
}
 
interface DriverWithDistance {
    driver: Driver;
    distanceKm: number;
    estimatedArrivalSeconds: number;
}
 
// Simplified in-memory implementation for demonstration
class InMemoryDriverLocationService implements DriverLocationService {
    private driverLocations: Map<string, { driver: Driver; location: Location; timestamp: Date }>;
    private readonly maxStaleSeconds = 30;
 
    constructor() {
        this.driverLocations = new Map();
    }
 
    async findNearbyDrivers(
        location: Location,
        radiusKm: number,
        vehicleType?: VehicleType
    ): Promise<DriverWithDistance[]> {
        const results: DriverWithDistance[] = [];
        const now = Date.now();
 
        for (const [id, entry] of this.driverLocations) {
            // Skip stale locations
            const ageSeconds = (now - entry.timestamp.getTime()) / 1000;
            if (ageSeconds > this.maxStaleSeconds) continue;
 
            // Skip unavailable drivers
            if (!entry.driver.isAvailableForRide()) continue;
 
            // Filter by vehicle type if specified
            if (vehicleType && entry.driver.getVehicleType() !== vehicleType) continue;
 
            // Calculate distance
            const distanceKm = location.distanceTo(entry.location);
            if (distanceKm <= radiusKm) {
                results.push({
                    driver: entry.driver,
                    distanceKm,
                    // Rough ETA: assume 30 km/h average city speed
                    estimatedArrivalSeconds: (distanceKm / 30) * 3600,
                });
            }
        }
 
        return results;
    }
 
    async updateDriverLocation(driverId: string, location: Location): Promise<void> {
        const existing = this.driverLocations.get(driverId);
        if (existing) {
            existing.location = location;
            existing.timestamp = new Date();
        }
    }
 
    async removeDriver(driverId: string): Promise<void> {
        this.driverLocations.delete(driverId);
    }
}

Production Considerations

Driver Ranking Strategy

Common ranking strategies:

Nearest Driver: Pure proximity; minimize rider wait time
Best ETA: Account for traffic; more accurate wait prediction
Quality Weighted: Balance distance with driver rating
Round Robin / Fair Distribution: Ensure drivers get opportunities
Batch Optimal: For pooling; optimize across multiple requests

MatchingStrategy.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
interface MatchingStrategy {
    /**
     * Rank drivers for a given ride request.
     * Returns drivers in order of preference (best first).
     */
    rankDrivers(
        candidates: DriverWithDistance[],
        request: RideRequest
    ): DriverWithDistance[];
}
 
/**
 * Simple strategy: rank by distance (closest first).
 */
class NearestDriverStrategy implements MatchingStrategy {
    rankDrivers(candidates: DriverWithDistance[]): DriverWithDistance[] {
        return [...candidates].sort((a, b) => a.distanceKm - b.distanceKm);
    }
}
 
/**
 * Rank by estimated arrival time (accounts for speed/traffic).
 */
class BestETAStrategy implements MatchingStrategy {
    rankDrivers(candidates: DriverWithDistance[]): DriverWithDistance[] {
        return [...candidates].sort(
            (a, b) => a.estimatedArrivalSeconds - b.estimatedArrivalSeconds
        );
    }
}
 
/**
 * Multi-factor scoring: balance ETA, rating, and acceptance rate.
 */
class WeightedScoreStrategy implements MatchingStrategy {
    private etaWeight: number = 0.5;
    private ratingWeight: number = 0.3;
    private acceptanceWeight: number = 0.2;
 
    rankDrivers(candidates: DriverWithDistance[]): DriverWithDistance[] {
        // Normalize factors to 0-1 scale, then compute weighted score
        const maxEta = Math.max(...candidates.map(c => c.estimatedArrivalSeconds));
        
        const scored = candidates.map(c => {
            const etaScore = 1 - (c.estimatedArrivalSeconds / maxEta);  // Lower ETA = higher score
            const ratingScore = c.driver.getRating() / 5.0;
            const acceptanceScore = c.driver.getAcceptanceRate();
 
            const totalScore = 
                this.etaWeight * etaScore +
                this.ratingWeight * ratingScore +
                this.acceptanceWeight * acceptanceScore;
 
            return { candidate: c, score: totalScore };
        });
 
        return scored
            .sort((a, b) => b.score - a.score)  // Higher score first
            .map(s => s.candidate);
    }
}
 
/**
 * Fair distribution: consider how recently driver received offers.
 * Prevents the same drivers from getting all the good trips.
 */
class FairDistributionStrategy implements MatchingStrategy {
    private lastOfferTime: Map<string, number> = new Map();
    private fairnessWeight: number = 0.3;
    private etaWeight: number = 0.7;
 
    rankDrivers(candidates: DriverWithDistance[]): DriverWithDistance[] {
        const now = Date.now();
        const maxEta = Math.max(...candidates.map(c => c.estimatedArrivalSeconds));
 
        const scored = candidates.map(c => {
            const etaScore = 1 - (c.estimatedArrivalSeconds / maxEta);
            
            // Fairness: time since last offer (longer = higher score)
            const lastOffer = this.lastOfferTime.get(c.driver.getId()) || 0;
            const timeSinceOffer = now - lastOffer;
            const fairnessScore = Math.min(timeSinceOffer / 300000, 1); // Cap at 5 min
 
            const totalScore = 
                this.etaWeight * etaScore +
                this.fairnessWeight * fairnessScore;
 
            return { candidate: c, score: totalScore };
        });
 
        return scored.sort((a, b) => b.score - a.score).map(s => s.candidate);
    }
 
    recordOffer(driverId: string): void {
        this.lastOfferTime.set(driverId, Date.now());
    }
}

Strategy Pattern Benefit

The Offer-Accept-Decline Flow

The offer lifecycle:

Send offer to top-ranked driver
Start acceptance timer (e.g., 15 seconds)
Driver accepts → Proceed to trip assignment
Driver declines or times out → Offer to next driver
Repeat until match or exhausted
All drivers exhausted → Notify rider of failure

MatchingEngine.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
interface RideOffer {
    id: string;
    trip: Trip;
    driver: Driver;
    estimatedFare: Fare;
    pickupEtaSeconds: number;
    expiresAt: Date;
    status: 'PENDING' | 'ACCEPTED' | 'DECLINED' | 'EXPIRED';
}
 
class MatchingEngine {
    private locationService: DriverLocationService;
    private matchingStrategy: MatchingStrategy;
    private offerTimeoutSeconds: number = 15;
    private maxSearchRadiusKm: number = 10;
    private maxCascadeAttempts: number = 5;
 
    constructor(
        locationService: DriverLocationService,
        matchingStrategy: MatchingStrategy
    ) {
        this.locationService = locationService;
        this.matchingStrategy = matchingStrategy;
    }
 
    async findMatch(request: RideRequest): Promise<MatchResult> {
        // Step 1: Find nearby candidates
        const candidates = await this.locationService.findNearbyDrivers(
            request.getPickupLocation(),
            this.maxSearchRadiusKm,
            request.getVehicleType()
        );
 
        if (candidates.length === 0) {
            return { success: false, reason: 'NO_DRIVERS_NEARBY' };
        }
 
        // Step 2: Rank by strategy
        const rankedDrivers = this.matchingStrategy.rankDrivers(candidates, request);
 
        // Step 3: Cascade through drivers
        for (let i = 0; i < Math.min(rankedDrivers.length, this.maxCascadeAttempts); i++) {
            const candidate = rankedDrivers[i];
            const offer = this.createOffer(request.getTrip(), candidate);
 
            const response = await this.sendOfferAndWait(offer);
 
            if (response === 'ACCEPTED') {
                return { 
                    success: true, 
                    driver: candidate.driver,
                    estimatedPickupSeconds: candidate.estimatedArrivalSeconds
                };
            }
            // DECLINED or EXPIRED: continue to next driver
        }
 
        return { success: false, reason: 'NO_DRIVER_ACCEPTED' };
    }
 
    private createOffer(trip: Trip, candidate: DriverWithDistance): RideOffer {
        return {
            id: generateUUID(),
            trip,
            driver: candidate.driver,
            estimatedFare: trip.getEstimatedFare(),
            pickupEtaSeconds: candidate.estimatedArrivalSeconds,
            expiresAt: new Date(Date.now() + this.offerTimeoutSeconds * 1000),
            status: 'PENDING',
        };
    }
 
    private async sendOfferAndWait(offer: RideOffer): Promise<'ACCEPTED' | 'DECLINED' | 'EXPIRED'> {
        // In reality: push notification to driver app, await response
        // This is a simplified synchronous representation
        
        // Send notification to driver
        await this.notifyDriver(offer);
 
        // Wait for response with timeout
        return new Promise((resolve) => {
            const timeout = setTimeout(() => {
                offer.status = 'EXPIRED';
                resolve('EXPIRED');
            }, this.offerTimeoutSeconds * 1000);
 
            // Driver response would come through event/callback
            // Simplified: assume external system calls handleDriverResponse
        });
    }
 
    handleDriverResponse(offerId: string, accepted: boolean): void {
        // Called when driver taps Accept or Decline
        // Would resolve the promise in sendOfferAndWait
    }
 
    private async notifyDriver(offer: RideOffer): Promise<void> {
        // Push notification with offer details
        // Includes: pickup address, destination, fare, time to respond
    }
}
 
interface MatchResult {
    success: boolean;
    driver?: Driver;
    estimatedPickupSeconds?: number;
    reason?: string;
}

Concurrency and Race Conditions

Concurrency challenges:

Double-booking: Same driver offered to two riders simultaneously
Stale availability: Driver accepted another offer but location service hasn't updated
Cascading delays: Many requests timing out on busy drivers

Common Pitfalls

•Offering same driver to multiple riders
•Not locking driver during offer window
•Stale location/availability data
•Long cascade chains blocking drivers

Solutions

•Optimistic locking on driver state
•Temporary 'OFFERED' status during timeout
•Frequent location/status sync
•Limit cascade attempts; fail fast

ConcurrentMatching.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// Driver status must prevent double-offering
enum DriverStatus {
    OFFLINE = 'OFFLINE',
    AVAILABLE = 'AVAILABLE',
    OFFERED = 'OFFERED',    // Temporarily locked during offer window
    ASSIGNED = 'ASSIGNED',
    IN_TRIP = 'IN_TRIP',
}
 
class DriverRepository {
    /**
     * Atomically try to lock a driver for an offer.
     * Returns true if successful, false if driver no longer available.
     */
    async tryLockForOffer(driverId: string): Promise<boolean> {
        // Atomic compare-and-swap operation
        // UPDATE drivers SET status = 'OFFERED' 
        // WHERE id = driverId AND status = 'AVAILABLE'
        // RETURNING id
        
        // If row returned, lock acquired; else driver was taken
        return true; // Simplified
    }
 
    async releaseLock(driverId: string): Promise<void> {
        // Called when offer expires or is declined
        // Sets status back to AVAILABLE
    }
 
    async assignToTrip(driverId: string): Promise<void> {
        // Called when offer is accepted
        // Sets status to ASSIGNED
    }
}

Optimistic vs Pessimistic Locking

Matching Algorithm Summary

Key Takeaways

•Matching is a geospatial + ranking problem — First find nearby drivers efficiently, then rank by multiple criteria.
•Abstract location queries behind a service — DriverLocationService encapsulates spatial indexing implementation details.
•Use Strategy pattern for ranking — Enables swapping algorithms (nearest, best ETA, weighted score, fair distribution) without changing core logic.
•Handle the offer cascade gracefully — Drivers may decline; cascade to next candidate with proper timeouts.
•Manage concurrency with driver locking — Prevent double-booking through atomic status transitions.

What's next:

Page Complete

3 / 6