Ride-sharing with Redis part II

Simulating some of Uber's ride-sharing features with Redis

This post is a continuation of the previous one. The last feature we discussed was the application finding the driver closest to the passenger.

Moving drivers across pools

The next important feature is to make sure that drivers are in the appropriate pool. Here are the transitions:

• A driver checks in at the beginning of his shift. He becomes available.

• When a driver accepts a ride he becomes on hold.

• When he picks up the passenger he becomes unavailable.

• When he drops off the passenger he becomes available again.

• At the end of his shift, he checks out and he becomes “out of the pool.”

These are implemented as simple API endpoints and a `DriverPoolService` class takes care of the Redis logic.

When a driver checks in we move him into the available pool:

public function moveToAvailable(Driver $driver): void
{
    Redis::sadd(RedisKey::DriverPoolAvailable->value, $driver->id);

    Redis::zrem(RedisKey::DriverPoolUnavailable->value, $driver->id);

    Redis::zrem(RedisKey::DriverPoolOnHold->value, $driver->id);
}

When moving a driver to the available pool it’s important to remove him from other pools as well.

The `SADD` command adds a new member to a set while the `ZREM` removes a member from a sorted set.

When a driver accepts a ride we move him into the on-hold pool:

public function moveToOnHold(Driver $driver, ?Carbon $eta = null): void
{
    if (!$eta) {
        $eta = now()->addMinutes(15);
    }

    Redis::zadd(
        RedisKey::DriverPoolOnHold->value,
        $eta->timestamp,
        $driver->id,
    );

    Redis::srem(RedisKey::DriverPoolAvailable->value, $driver->id);

    Redis::zrem(RedisKey::DriverPoolUnavailable->value, $driver->id);
}

This method takes an additional `$eta` argument. In a real-world app, you can calculate the estimated time of arrival using an API (such as Google Maps). Here I just used a hardcoded value.

The `ZADD` commanfód adds the driver ID to the sorted set using the ETA timestamp as its score.

When a driver picks up the passenger he becomes unavailable:

public function moveToUnavailable(
    Driver $driver,
    ?Car $eta = null,
): void {
    if (!$eta) {
        $eta = now()->addMinutes(15);
    }

    Redis::zadd(
        RedisKey::DriverPoolUnavailable->value, 
        $eta->timestamp,
        $driver->id
    );

    Redis::srem(RedisKey::DriverPoolAvailable->value, $driver->id);

    Redis::zrem(RedisKey::DriverPoolOnHold->value, $driver->id);
}

The unavailable pool is also a sorted set with ETA scores.

When a driver drops off his passenger he becomes available again:

public function moveToAvailable(Driver $driver): void
{
    Redis::sadd(RedisKey::DriverPoolAvailable->value, $driver->id);

    Redis::zrem(RedisKey::DriverPoolUnavailable->value, $driver->id);

    Redis::zrem(RedisKey::DriverPoolOnHold->value, $driver->id);
}

And finally, when a driver checks out we need to remove him from every pool:

public function remove(Driver $driver): void
{
    Redis::zrem(RedisKey::DriverPoolOnHold->value, $driver->id);

    Redis::srem(RedisKey::DriverPoolAvailable->value, $driver->id);

    Redis::zrem(RedisKey::DriverPoolUnavailable->value, $driver->id);

    Redis::zrem(RedisKey::DriverCurrentLocations->value, $driver->id);
}

Here’s a quick question for you:

Ride state machine

The application of course uses MySQL as well. Redis is used for managing driver pools and running geometry queries. One of the most important models is `Ride` which represents a ride with a driver and passenger.

This is what the table looks like:

The status and the corresponding dates are very important. Here are the possible statuses for a ride:

• Waiting means a passenger requested a ride, but no driver accepted it yet.

• Accepted means that a driver has already accepted it and is on the way to the pickup location.

• In progress means that the driver picked up the passenger and they are on the way to the destination.

• Finished means that the ride is finished and the driver dropped off the passenger at the destination.

These states are important. The transitions between are also very important. For example, a waiting ride cannot be marked as finished. If something like that happens it messes up the driver pools.

Because of that, it’s a good idea to use a state machine that enforces the right transitions and cannot let something like waiting → in-progress.

A finite state machine (FSM) is a model used to represent and control the behavior of a system or object based on its current state and the inputs it receives. It has predefined states and transitions with rules.

I’m going to use this package which is pretty simple but effective.

First of all, the `Ride` model needs to implement the `StatefulInterface` interface that defines two methods:

class Ride extends Model implements StatefulInterface
{
    public function getFiniteState()
    {
        return $this->status?->value;
    }

    public function setFiniteState($state)
    {
        $this->status = RideStatus::from($state);
    }
}

It’s a simple getter and setter that returns/sets the current status of a ride.

Next, the `StateMachine` can be used to define states and transitions. This snippet is just a simplified example:

$sm = new StateMachine();

$sm->addState(new State('waiting', StateInterface::TYPE_INITIAL));
$sm->addState(new State('accepted'));
$sm->addState(new State('finished', StateInterface::TYPE_FINAL));

$sm->addTransition('transition1', 'waiting', 'accepted');
$sm->addTransition('transition2', 'accepted', 'finished');

$sm->setObject($ride);
$sm->initialize();

$sm->can('transition1');

States are added via the `addState` method. There are three types of states:

• `TYPE_INITIAL` is the first, initial state

• `TYPE_FINAL` is the last, final state

• `TYPE_NORMAL` is an intermediate state between the initial and the final ones. It is the default type so it’s omitted in the example.

Transitions are configured via the `addTransition` method. They have a name, a starting state, and a destination state.

After everything is set up we can use the `can` method to determine if a transition is allowed on a given object or not:

$ride = Ride::find(1);
$ride->status = 'waiting';

// true
echo $sm->can('transition1');

// false
echo $sm->can('transition2');

It’s a very simple concept but helps encapsulate the states and transitions which is a pretty good thing.

In order to use it easily I created a new `RideStateMachine` class that contains a `StateMachine` and encapsulates all statuses and transitions:

namespace App\Services;

class RideStateMachine
{
    private StateMachine $stateMachine;

    public function __construct(Ride $ride)
    {
        $this->stateMachine = new StateMachine();

        $this->stateMachine->addState(
            new State(
                RideStatus::Waiting->value,
                StateInterface::TYPE_INITIAL,
            ),
        );

        $this->stateMachine->addState(
            new State(RideStatus::Accepted->value)
        );
        $this->stateMachine->addState(
            new State(RideStatus::InProgress->value)
        );
        $this->stateMachine->addState(
            new State(RideStatus::Abandoned->value)
        );

        $this->stateMachine->addState(
            new State(
                RideStatus::Finished->value,
                StateInterface::TYPE_FINAL,
            ),
        );

        $this->stateMachine->addTransition(
            'accept', 
            RideStatus::Waiting->value, 
            RideStatus::Accepted->value,
        );

        $this->stateMachine->addTransition(
            'progress', 
            RideStatus::Accepted->value, 
            RideStatus::InProgress->value,
        );

        $this->stateMachine->addTransition(
            'finish', 
            RideStatus::InProgress->value, 
            RideStatus::Finished->value,
        );

        $this->stateMachine->addTransition(
            'abandon-from-waiting', 
            RideStatus::Waiting->value, 
            RideStatus::Abandoned->value,
        );

        $this->stateMachine->addTransition(
            'abandon-from-accepted', 
            RideStatus::Accepted->value, 
            RideStatus::Abandoned->value,
        );

        $this->stateMachine->setObject($ride);

        $this->stateMachine->initialize();
    }

    public function can(string $transition): bool
    {
        return $this->stateMachine->can($transition);
    }
}

I also added a new attribute to the `Ride` model:

class Ride extends Model implements StatefulInterface
{
    public function stateMachine(): Attribute
    {
        return Attribute::make(
            get: fn () => new RideStateMachine($this),
        );
    }
}

Of course, it’s not necessary, but this way it can be used such as this:

class RideController extends Controller
{
    public function accept(Ride $ride, AcceptRideRequest $request)
    {
        $driver = $request->getDriver();

        if ($ride->state_machine->can('accept')) {
            $ride->accepted($driver, $request->getCar());
        }

        $this->driverPool->moveToOnHold($driver);

        return response('', Response::HTTP_NO_CONTENT);
    }
}

Do you like this post so far? If yes, please share it with your friends. It would be a huge help for the newsletter! Thanks.

The “business logic” behind a state change is implemented in the model:

public function accepted(Driver $driver, Car $car): void
{
    $this->update([
        'status' => RideStatus::Accepted,
        'driver_id' => $driver->id,
        'car_id' => $car->id,
        'accepted_at' => now(),
    ]);
}

It is very simple in every case. However, transitions and the logic behind them can be extracted into `Transition` objects. In the Finite package, a transition has the following interface:

interface TransitionInterface
{
    public function getInitialStates();

    public function getState();

    /**
     * This is where the actual transition should happen
     */
    public function process(StateMachineInterface $stateMachine);

    public function getName();

    public function getGuard();
}

So if you don’t like the fact that the transition logic is implemented in the models, you can move them into dedicated transition objects in your own project.

Testing

This application has lots of “moving parts.” Different driver pools, statuses in Redis, state machines, etc. But the business logic is not too “deep.” Meaning it doesn’t have too many use cases and edge cases. A software such as Excel has an infinite number of use cases and probably thousands of edge cases. Just think about parsing expressions. It basically has a built-in compiler.

This application doesn’t have a built-in compiler. My go-to approach to testing features/apps such as this one is feature tests. Meaning, I usually don’t test individual functions but API endpoints or service classes, etc. I do the same in my tests as users do on the website.

For example, this is how I’d test finding the closest driver:

class GetClosestDriversTest extends TestCase
{
    use RefreshDatabase;

    private DriverPoolService $driverPool;

    private LocationService $locationService;

    protected function setUp(): void
    {
        parent::setUp();

        $this->driverPool = app(DriverPoolService::class);

        $this->locationService = app(LocationService::class);
    }

    protected function tearDown(): void
    {
        Redis::flushall();

        parent::tearDown();
    }

    #[Test]
    public function it_should_return_the_closest_driver()
    {
        $user = User::factory()->create();

        $ride = Ride::factory()->create([
            'user_id' => $user->id,
            // Budapest, Szechenyi Rakpart
            'pick_up_location' => Location::create(
                47.5097778,
                19.0460277,
            ),
        ]);

        $closestDriver = Driver::factory()->create();

        // Budapest, Antall Jozsef Rakpart
        $closestDriverLocation = Location::create(47.513951, 19.046571);

        $this->driverAvailableAt(
            $closestDriver, 
            $closestDriverLocation,
        );

        $otherDriver = Driver::factory()->create();

        // Budapest, Robert Karoly krt.
        $otherDriverLocation = Location::create(47.520875, 19.085512);

        $this->driverAvailableAt($otherDriver, $otherDriverLocation);

        $driver = $this->locationService->getClosestDrivers(
            $ride->pick_up_location, 
            DriverStatus::Available
        )->first();

        $this->assertSame($closestDriver->id, $driver->id);
    }
}

The test does the following things:

• It creates a user and orders a drive

• It creates a driver called $closestDriver at a specific location that is close to the user. In a minute I’ll show you the driverAvailableAt function.

• It creates another driver called $otherDriver who is further away from the user.

• It calls the LocationService to get the closest driver.

• Then it asserts that the returned driver is equal to the $closestDriver

The driverAvailableAt function uses the API to check in and update the current location of a driver:

protected function driverAvailableAt(
    Driver $driver, 
    Location $location
): void {
    $car = Car::factory()->create();

    $this->patchJson(
        route('drivers.check-in', ['driver' => $driver->id]),
        [
            'car_id' => $car->id,
        ],
    )
        ->assertStatus(Response::HTTP_NO_CONTENT);

    $this->patchJson(
        route(
            'drivers.update-current-location', 
            [
                'driver' => $driver->id
            ],
        ),
        [
            'car_id' => $car->id,
            'longitude' => $location->longitude,
            'latitude' => $location->latitude,
        ],
    )
        ->assertStatus(Response::HTTP_NO_CONTENT);
}

This way the test makes sure that the Driver APIs and the LocationService can work hand-in-hand. Just as expected.

Don’t forget to clone the repository.

If you have a question or feedback don’t forget to leave a comment!