ベンチマーカー内に構成された世界では30msを1tickとして次の行動を制御されるようになっていました。そのため、全エンドポイントが30ms以内にレスポンスを返せていることが理想的な状態です。

ライドの満足度

ユーザーがISURIDEアプリを通じて椅子を呼び出し、椅子に乗って移動した後、評価を行うまでの一連の流れのことをライドと呼び、ベンチマーカーはそれを模したリクエストを送るようになっていました。

また、ライドの最後にはそのライドの満足度を評価するようになっており、個人の評価が高いとユーザーによる招待が、地域ごとの評価の平均値が高いと口コミによるユーザー数の増加が起きるようになっていました。

ユーザーの行動は以下のような遷移を辿ります。

ベンチマーカーのログに出力されていたライドの評価内容と実際の改善ポイントは以下のようになっていました。

椅子がマッチングされるまでの時間

ユーザーがライドを作成してから椅子に割り当てられた通知を受け取るまでの時間を見ています。

初期実装では500msごとに1つのライドのマッチングしか行われないので、他のエンドポイントの改善などによりマッチング中のライドが増えると不満が溜まっていくようになっていたと思います。

また、ユーザーが通知を受け取るまでの時間を対象としているので通知エンドポイントをポーリングする頻度や通知エンドポイントのレスポンスタイム自体も影響します。

マッチされた椅子が乗車地点までに掛かる時間

ライドに割り当てられた椅子の割当時点での位置とライドの乗車位置の間の理想的な移動時間（2点間の距離と椅子のモデルの速度について 2点間の距離/速度 <= 10 かどうか）について見ています。一般的な配車アプリでも車両がマッチングされた時に到着予定時刻が出ると思いますが、それが長過ぎるような場合に満足度が下がるようになっています。

これはマッチングアルゴリズムの改善により満足度を上げることができます。単独のライドに関して言えば割り当て可能な椅子の中で最も近いものを割り当てれば良いですが、全体最適を目指そうとすると多少凝ったアルゴリズムを実装する必要がありました。

椅子の実移動時間

マッチされた椅子が実際に乗車位置まで移動し、乗車位置に到着したことをユーザーが通知で受け取るまでの理想的な移動時間（位置情報更新で詰まっていない場合の移動時間）と実際にかかった時間の差を見ています。

椅子は自分の位置情報を更新する

POST /api/chair/coordinate

のリクエストが完了しないと次の移動を開始しないので、このエンドポイントのレスポンスが遅いことも不満の原因となります。

また、通知を受けるまでの時間となっているので通知エンドポイントのポーリング頻度やレスポンスタイムも影響するようになっていました。

スコアの計算

以下の合計がスコアになっていました。

・椅子がライドとマッチした位置から乗車位置までの移動距離の合計 * 0.1

・椅子の乗車位置から目的地までの移動距離の合計

・ライド完了数 * 5

基本的にはライドの回数が重要になります。関連するエンドポイント全体を高速化していくことで、高速にライドを捌いていくことができるようになり、それに合わせてユーザーの満足度・椅子の売上も高くなりライドの数も増えていくようになっていました。

また、椅子の移動についてもスコアがついていますが空車のときと人を乗せているときではスコアに10倍の差があるので、椅子が移動する際にはできるだけ人を乗せている状態、つまり椅子と乗車位置が近いライドに割り当てることも必要になっていました。

解説

ここからは各要素について解説していきます。

序盤

インデックス

今年のデータベースも全くと言っていいほどインデックスが貼られておらず、初期状態ではNginx・アプリ・データベースの負荷のバランスを見てもデータベースが寡占するような状況になっていたと思われます。

データベースのプロファイリングを行ったりテーブル構造やアプリケーションからの使われ方から検討したりして、追加するべきインデックスを決めるのが各チーム初手になったのではないでしょうか。

POST /api/initialize

のハンドラ内でのデータベースのリセット方法は年によって異なり、これまで特定のID以降の削除、テーブルのTRUNCATE、テーブルやデータベース自体の作り直しなどの方法がありましたが、今回はテーブルの作り直しが行われるようになっていました。

例えば、 webapp/sql/1-schema.sqlの末尾に以下のように追記をしてインデックスを貼ることで、Go言語では4000点程度までスコアを伸ばせることを確認しています。(初期実装では使われないインデックスも含まれています）

 CREATE INDEX idx_chairs_access_token ON chairs (access_token);
 
 CREATE INDEX idx_users_access_token ON users (access_token);
 CREATE INDEX idx_users_invitation_code ON users (invitation_code);
 
 CREATE INDEX idx_rides_chair_id_updated_at_desc ON rides (chair_id, updated_at DESC);
 CREATE INDEX idx_rides_user_id_created_at_desc ON rides (user_id, created_at DESC);
 CREATE INDEX idx_rides_chair_id_created_at_desc ON rides (chair_id, created_at DESC);
 CREATE INDEX idx_rides_chair_id_created_at_asc ON rides (chair_id, created_at);
 
 CREATE INDEX idx_ride_statuses_ride_id_app_sent_at_created_at ON ride_statuses (ride_id, app_sent_at, created_at);
 CREATE INDEX idx_ride_statuses_ride_id_created_at_desc ON ride_statuses (ride_id, created_at DESC);
 CREATE INDEX idx_ride_statuses_ride_id_created_at ON ride_statuses (ride_id, created_at);
 
 CREATE INDEX idx_coupons_used_by ON coupons (used_by);
 CREATE INDEX idx_coupons_code ON coupons (code);
 
 CREATE INDEX idx_chair_locations_chair_id_created_at_desc ON chair_locations (chair_id, created_at DESC);

GET /api/app/nearby-chairs

ChairWithLatLon

 type ChairWithLatLon struct {
 	ID          string    `db:"id"`
 	OwnerID     string    `db:"owner_id"`
 	Name        string    `db:"name"`
 	Model       string    `db:"model"`
 	IsActive    bool      `db:"is_active"`
 	AccessToken string    `db:"access_token"`
 	CreatedAt   time.Time `db:"created_at"`
 	UpdatedAt   time.Time `db:"updated_at"`
 
 	Latitude  int `db:"latitude"`
 	Longitude int `db:"longitude"`
 }

 	chairs := []ChairWithLatLon{}
 	err = tx.Select(
 		&chairs,
 		`
 -- 近くに存在している椅子一覧
 WITH near_chairs AS (
 	SELECT cl.*
 	FROM (
 	    SELECT cl.*, row_number() over (partition BY chair_id ORDER BY created_at DESC) AS rn
 	    FROM chair_locations cl
 	) cl
 	WHERE cl.rn = 1 AND abs(cl.latitude - ?) + abs(cl.longitude - ?) < ?
 ),
 -- すべての椅子の最新のステータス
 chair_latest_status AS (
 	SELECT *
 	FROM (
 		SELECT rides.*, ride_statuses.status AS ride_status, row_number() over (partition BY chair_id ORDER BY ride_statuses.created_at DESC) AS rn
 		FROM rides LEFT JOIN ride_statuses ON rides.id = ride_statuses.ride_id		
 	) r 
 	WHERE r.rn = 1 AND r.ride_status = 'COMPLETED'
 )
 
 SELECT
 	chairs.*, near_chairs.latitude, near_chairs.longitude
 FROM 
 	chairs
 -- ここのINNER JOINで近くに存在している椅子に絞り込まれる
 INNER JOIN near_chairs ON chairs.id = near_chairs.chair_id
 LEFT JOIN chair_latest_status ON chairs.id = chair_latest_status.chair_id
 WHERE
 -- 最新のライドが完了しているか1度もライドに割り当てられていなくて現在アクティブな椅子を取得する
 	(chair_latest_status.ride_status = 'COMPLETED' OR chair_latest_status.ride_status IS NULL) AND chairs.is_active`,
 		lat, lon, distance,
 	)
 	if err != nil {
 		writeError(w, http.StatusInternalServerError, err)
 		return
 	}
 
 	nearbyChairs := make([]appGetNearbyChairsResponseChair, 0, len(chairs))
 	for _, chair := range chairs {
 		nearbyChairs = append(nearbyChairs, appGetNearbyChairsResponseChair{
 			ID:    chair.ID,
 			Name:  chair.Name,
 			Model: chair.Model,
 			CurrentCoordinate: Coordinate{
 				Latitude:  chair.Latitude,
 				Longitude: chair.Longitude,
 			},
 		})
 	}

chair_latest_status

COMPLETED

evaluation

ride_statuses

 WITH near_chairs AS (
 	SELECT cl.*
 	FROM (
 	    SELECT cl.*, row_number() over (partition BY chair_id ORDER BY created_at DESC) AS rn
 	    FROM chair_locations cl
 	) cl
 	WHERE cl.rn = 1 AND abs(cl.latitude - ?) + abs(cl.longitude - ?) < ?
 )
 SELECT
 	chairs.*, near_chairs.latitude, near_chairs.longitude
 FROM 
 	chairs
 INNER JOIN near_chairs ON chairs.id = near_chairs.chair_id
 LEFT JOIN rides ON chairs.id = rides.chair_id AND rides.evaluation IS NULL
 WHERE
 	rides.id IS NULL AND chairs.is_active

 WITH filtered_chairs AS (
     SELECT id
     FROM chairs
     WHERE owner_id = ?
 )
 SELECT c.id,
        c.owner_id,
        c.name,
        c.access_token,
        c.model,
        c.is_active,
        c.created_at,
        c.updated_at,
        ifnull(dt.total_distance, 0) AS total_distance,
        dt.total_distance_updated_at
 FROM filtered_chairs fc
 JOIN chairs c ON fc.id = c.id
 LEFT JOIN (
     SELECT chair_id,
            SUM(distance) AS total_distance,
            MAX(created_at) AS total_distance_updated_at
     FROM (
         SELECT cl.chair_id,
                cl.created_at,
                abs(cl.latitude - lag(cl.latitude) OVER (PARTITION BY cl.chair_id ORDER BY cl.created_at)) +
                abs(cl.longitude - lag(cl.longitude) OVER (PARTITION BY cl.chair_id ORDER BY cl.created_at)) AS distance
         FROM chair_locations cl
         JOIN filtered_chairs fc ON cl.chair_id = fc.id
     ) sub
     WHERE distance IS NOT NULL
     GROUP BY chair_id
 ) dt ON dt.chair_id = c.id
 

chair_locations

total_distance

total_distance

total_distance

GET /api/owner/chairs

改善案としては椅子割当待ちのride全てと空いている椅子すべてをマッチングさせるようにする・乗車位置に近い椅子を割り当てるなどがありました。更にISURIDEは2地域で展開されており各ユーザーは地域内でしか移動しないという記載がマニュアルにあることより、一定距離より遠い椅子とライドはマッチングするのを見送った方が効率が良くなります。ランダム性を除いたマッチングアルゴリズムに変更すると、それまでかなりぶれていたベンチマークスコアもかなり安定したのではないでしょうか。

図 : ベンチマーク走行後のridesテーブルをChatGPTでプロット

それらを取り込んだ実装例が以下になります。

func internalGetMatching(w http.ResponseWriter, r *http.Request) {
	// 決まっていないライドと空いている椅子を全て取得
	rides := []Ride{}
	if err := db.Select(&rides, `SELECT * FROM rides WHERE chair_id IS NULL ORDER BY created_at ASC`); err != nil {
		w.WriteHeader(http.StatusNoContent)
		return
	}
	if len(rides) <= 0 {
		return
	}

	chairs := []ChairWithLatLon{}
	if err := db.Select(&chairs, `
 WITH chair_latest_location AS (
 	SELECT *
 	FROM (
 		SELECT chair_locations.*, ROW_NUMBER() OVER (PARTITION BY chair_id ORDER BY created_at DESC) AS rn
 		FROM chair_locations
 	) c
 	WHERE c.rn = 1
 ),
 chair_latest_status AS (
 	SELECT *
 	FROM (
 		SELECT rides.*, ride_statuses.status AS ride_status, ROW_NUMBER() OVER (PARTITION BY chair_id ORDER BY ride_statuses.created_at DESC) AS rn
 		FROM rides INNER JOIN ride_statuses ON rides.id = ride_statuses.ride_id AND ride_statuses.chair_sent_at IS NOT NULL -- この条件は椅子の通知エンドポイントの実装で、未送信の状態がある2つ以上の異なるライドが割り当てられていても正しく順番に送るように修正していれば不要
 	) r
 	WHERE r.rn = 1
 )
 SELECT
 	chairs.*, chair_latest_location.latitude, chair_latest_location.longitude
 FROM chairs
 LEFT JOIN chair_latest_status ON chairs.id = chair_latest_status.chair_id
 LEFT JOIN chair_latest_location ON chairs.id = chair_latest_location.chair_id
 WHERE
 	(chair_latest_status.ride_status = 'COMPLETED' OR chair_latest_status.ride_status IS NULL) AND chairs.is_active`); err != nil {
		writeError(w, http.StatusInternalServerError, err)
		return
	}

	for _, ride := range rides {
		minDistance := 400
		var minChair *ChairWithLatLon
		var minChairIdx int
		for idx, chair := range chairs {
			distance := calculateDistance(chair.Latitude, chair.Longitude, ride.PickupLatitude, ride.PickupLongitude)
			if distance < minDistance {
				minDistance = distance
				minChair = &chair
				minChairIdx = idx
			}
		}
		if minChair != nil {
			// 複数のmatcherが動く場合には、複数の椅子が同じライドに割り当てられないようトランザクションなどで排他制御を行う必要がある
			if _, err := db.Exec("UPDATE rides SET chair_id = ? WHERE id = ?", minChair.ID, ride.ID); err != nil {
				writeError(w, http.StatusInternalServerError, err)
				return
			}

			chairs = append(chairs[:minChairIdx], chairs[minChairIdx+1:]...)
		}
	}

	w.WriteHeader(http.StatusNoContent)
}

GET /api/app/notification

GET /api/chair/notification

retry_after_ms

chairs

POST /api/chair/coordinate

POST /api/chair/coordinate

POST /api/chair/coordinate

retry_after_ms