はじめに

「ちゃん」というチームでISUCON14に出場していました
本番では昼頃に一桁位に位置付けるなど好調でしたが、結果envcheckによる失格になっていました...
pproteinという便利ツールを入れたサーバをISUCONサーバと同じVPCに立てっぱなしだったことが原因と思われます
このような悔しい結果だったこともあり、用意していただいた感想戦をコツコツ頑張ってみましたので、その進め方を紹介させていただきます
https://github.com/ponyo877/isucon14

感想戦

今回のISUCON14は感想戦と呼ばれるポータルやベンチマークが本番以降も使える機会が与えられました
その期間なんと一ヶ月以上!また、今回の問題はいつにも増して遊び尽くせる問題になっている気配がしたのでやり込んでみました
感想戦のベストスコア獲得時のスコアボード

感想戦での改善

感想戦ではざっくり三つの大きな改善を入れスコアを伸ばすことができました
感想戦で実施した三つの改善

大きな改善1 | 公式解説の改善

以下のISUCON14公式解説にある改善の大部分を入れました

通知のSSE化

takonomuraさんの公開している実装を参考にSSE対応しました
また、SSEでのresponseの書き込みをrideのステータスが変更するタイミングに限定することで負荷を下げるためにrideのステータスが変更するタイミングでGoのchannelにmessageを書き込みnotificationのSSEの無限Loopの中でchannelからのmessageの受け取りを行なっています

実装 | SSE, channel管理

SSEの実装

func chairGetNotification(w http.ResponseWriter, r *http.Request) {
	ctx := r.Context()
	chair := ctx.Value("chair").(*Chair)

	w.Header().Set("X-Accel-Buffering", "no")
	w.Header().Set("Content-Type", "text/event-stream")
	w.Header().Set("Cache-Control", "no-cache")
	w.Header().Set("Connection", "keep-alive")

	clientGone := ctx.Done()
	rc := http.NewResponseController(w)

	chairChan := getChairChan(chair.ID)
	for {
		select {
		case <-clientGone:
			return
		case notif := <-chairChan:
			response, err := getChairNotification(notif.Ride, notif.RideStatus)
			if err != nil {
				return
			}
			resV, err := sonic.Marshal(response.Data)
			if err != nil {
				return
			}
			if _, err := w.Write([]byte("data: ")); err != nil {
				return
			}
			if _, err := w.Write(resV); err != nil {
				return
			}
			if _, err := w.Write([]byte("\n\n")); err != nil {
				return
			}
			if err := rc.Flush(); err != nil {
				return
			}
		}
	}
}

channelへの出し入れ

func getChairChan(chairID string) chan *Notif {
	chairChan, ok := chairNotifChan.Load(chairID)
	if !ok {
		chairNotifChan.Store(chairID, make(chan *Notif, 5))
		chairChan, _ = chairNotifChan.Load(chairID)
	}
	return chairChan.(chan *Notif)
}

func publishAppChan(userID string, notif *Notif) {
	getAppChan(userID) <- notif
}

二部マッチングによる配車マッチング

公式解説にある通り今回の配車マッチングは二部マッチング問題の問題と捉えることができます
そして今回の以下のような重みつき最大二部マッチング問題になります(辺の容量は全て1)
chairとrideの重みつき二部グラフ

重みつき最大二部マッチング問題は最小費用流問題に帰着することが知られているようです

今回は以下の記事からGoの最小費用流を解く実装を拝借しました

決済マイクロサービスのIdempotency-Keyヘッダ対応

こちらは決済マイクロサービスへのリクエスト部分にIdempotency-Keyヘッダの付与処理を追加し、それによりリトライが自動化されることでリトライ処理を丸ごと省けるので省きます

実装 | 決済マイクロサービスのIdempotency-Keyヘッダ対応

func requestPaymentGatewayPostPayment(ctx context.Context, paymentGatewayURL string, rideId, token string, param *paymentGatewayPostPaymentRequest) error {
	b, err := sonic.Marshal(param)
	if err != nil {
		return err
	}

	retry := 0
	for {
		err := func() error {
			req, err := http.NewRequestWithContext(ctx, http.MethodPost, paymentGatewayURL+"/payments", bytes.NewBuffer(b))
			if err != nil {
				return err
			}
			req.Header.Set("Content-Type", "application/json")
			req.Header.Set("Authorization", "Bearer "+token)
			req.Header.Set("Idempotency-Key", rideId)

			res, err := http.DefaultClient.Do(req)
			if err != nil {
				return err
			}
			defer res.Body.Close()

			if res.StatusCode != http.StatusNoContent {
				return fmt.Errorf("unexpected status code (%d)", res.StatusCode)
			}
			return nil
		}()
		if err != nil {
			if retry < 5 {
				retry++
				continue
			} else {
				return err
			}
		}
		break
	}

	return nil
}

大きな改善1の際の構成図

この時のボトルネックはMySQLのCPU使用率でした、MySQLサーバは分散できないので以下の様な構成を取っていました
大きな改善1の際の構成図

大きな改善2 | MySQL剥がし

APとMySQLのサーバ分離ではなくMySQLに依存する処理を全て消すという改善になります
具体的には全てのデータ永続化処理部分をGoのスレッドセーフなMapであるsync.Mapに移します
やり方はISUCONの本番でもよく使われるオンメモリキャッシュ戦略と同じですが、キャッシュ登録時のINSERTとキャッシュ取得失敗時のSELECTは一切行いません(ここが別競技たる所以です...)

handlerが求めているものをよく噛み砕いてみるとかなり単純なデータの登録/参照だけが求められることがわかります、そのため難しいデータ構造などは必要なく全て標準packageで実装可能です

MySQL剥がし例1 | ユーザのクーポン

userの登録時に以下の三種類のクーポンが発行されます

新規登録キャンペーン: ¥3,000
知り合い招待（招待する側）: ¥1,500
知り合い招待（招待される側）: ¥1,000

初回実装ではSQLを絡めて複雑に書かれていますが、単純化すると以下の処理のみで従分です

ユーザの登録(POST /api/app/user)

ユーザが登録されたらそのユーザのcoupon queueに3000をpush
(ユーザが招待されていた場合)登録したユーザのcoupon queueに1500をpush
(ユーザが招待されていた場合)招待したユーザのcoupon queueに1000をpush

// ** 初回登録キャンペーンのクーポンを付与 ** 
addUnusedCoupon(userID, 3000)

// 招待コードを使った登録
if req.InvitationCode != nil && *req.InvitationCode != "" {
    // 省略
    // ** 招待する側への招待クーポン付与 **
    addUnusedCoupon(userID, 1500)
    // ** 招待される側への招待クーポン付与 **
    addUnusedCoupon(inviter.ID, 1000)
}

rideの料金計算(GET /api/app/rides, GET /api/app/rides/estimated-fare)

rideに紐づいたユーザのcoupon queueの先頭を取得、その金額をDisccountする
estimateではない場合、coupon queueの先頭をpop

// 一番古いクーポンを取得
discount, ok := getUnusedCoupon(user.ID)
if ok {
    // 直前に取得したクーポンをpop(estimateの時はここは省略)
    useUnusedCoupon(user.ID)
}
meteredFare := farePerDistance * calculateDistance(req.PickupCoordinate.Latitude, req.PickupCoordinate.Longitude, req.DestinationCoordinate.Latitude, req.DestinationCoordinate.Longitude)
discountedMeteredFare := max(meteredFare-discount, 0)

なのでuserIDごとにcoupon queueを持っておけばいいことになります
queueはGoのsliceと先頭の位置を管理する整数をセットで持っておくだけで実現できます

type UnusedCouponAmount struct {
	list []int
	head int
	mu   sync.Mutex
}

func (u *UnusedCouponAmount) Add(amount int) {
	u.mu.Lock()
	defer u.mu.Unlock()
	u.list = append(u.list, amount)
}

func (u *UnusedCouponAmount) Front() int {
	u.mu.Lock()
	defer u.mu.Unlock()
	return u.list[u.head]
}

func (u *UnusedCouponAmount) Remove() {
	u.mu.Lock()
	defer u.mu.Unlock()
	u.head++
}

MySQL剥がし例2 | マッチ可能なchairとマッチ待ちのride

マッチ可能なchairとマッチ待ちのrideはsync.Mapでは表現できないので通常のmapと排他制御のためのmutexで表現しています
通常のmapであれば直接Keyの一覧やValueの一覧を撮ってこれるのでそうしています

type FreeChairs struct {
	cache map[string]*Chair
	mu    sync.Mutex
}

マッチ可能なchair

追加: chairがActiveに更新されたタイミング+担当していたrideが完了したタイミング
削除: マッチングが成立したタイミング

マッチ待ちのride

追加: rideが新規作成されたタイミング
削除: マッチングが成立したタイミング

MySQL剥がし例3 | TotalDistance

GET /api/owner/chairsで指定されたownerが所有している全chairの総走行距離の合計が求められます
この時chairの位置が更新されたタイミングで併せて総走行距離も求めておくと効率的と考えました

func createChairTotalDistance(chairID string, distance int, now time.Time) {
	current := &TotalDistance{}
	if tmp, ok := getChairTotalDistance(chairID); ok {
		current = tmp
	}
	chairTotalDistance.Store(chairID, &TotalDistance{
		TotalDistance: current.TotalDistance + distance,
		UpdatedAt:     now,
	})
}

再起動試験対策(未実装)

MySQLを剥がしてしまったのでデータが永続化されなくなってしまいました
これにより再起動などでアプリケーションが停止された場合、過去のリクエストで生成されたデータが取得できなくなります、これでは本番の再起動試験で失格となるので、本番仕様では対策が必要です

感想戦ではスコアを上げることに夢中でこの対策は未実装なのですが、以下の様な構想を練っていました、サービス停止起因による超遅延書き込みです(これが成功するかも不明です)
Goではencoding/gobというデータ構造のシリアライズのパッケージがあり、mapや任意の構造体をファイル化することができます
このパッケージを使い「キャッシュ変数のファイル化」と「キャッシュファイルの変数の書き戻し」をAPI化できればEC2の停止・起動のタイミングで各APIを実行できれば再起動試験を通すことができるのではないかと考えています(たとえこれが成功してもISUCONでしか通用しない様なやり方です...)

EC2の停止・起動のタイミングでの処理の実行は以下の記事に記載のsystemdのExecStartとExecStopで実現できそうです

例

[Service]
ExecStart=${キャッシュの書き戻し}
ExecStop=${キャッシュのファイル書き出し}

大きな改善2の際の構成図

この時のnginxのCPU使用率でした、nginxは分散できない(とこの時は思っていたので)、以下の様な構成でした
大きな改善2の際の構成図

大きな改善3 | nginx(L7)の分散

MySQLを剥がしたことでボトルネックがnginxのCPUに移行しました
これを解消しようと考えたのがnginxの分散です、今回の初期実装ではnginxがURL, Cookie, HTTP ヘッダーを見てどのサーバのどのPortへ振り分けるかを管理するL7 LoadBalancerとしての役割を担っていました
この役割を複数のサーバでの分担をnginxのL4 LoadBalancer機能、ポートとIPを見て振り分ける役割を前段におくことで実現しました
以下の様にL4とL7の両方の設定を一つのnginx.confに書くことができます、L4の設定をベンチマーカーのアクセスを受けるサーバのみに載せ、L7の設定は3台全てに載せることでnginx(L7)を3台全てのサーバで分散することができます
L4とL7を兼任するサーバ、L7だけ処理するサーバ、L7とアプリケーションを兼任するサーバとそれぞれL7を担当できる重みが違うのでupstreamのweightで各サーバにどれだけリクエストを流すかを制御し書くサーバの処理負荷を均一化しています

nginx.conf

# L4の設定
stream {
    upstream backend {
        server 127.0.0.1:8443 weight=2;
        server 192.168.0.12:8443 weight=5;
        server 192.168.0.13:8443 weight=1;
    }
    server {
        listen 443;
        proxy_pass backend;
    }
}

# L7の設定
http {
    upstream app {
        server 192.168.0.13:8080;
        keepalive_requests 1000000;
    	keepalive 1024;
    }
    server {
        listen 8443 ssl http2;    
        location / {
            try_files $uri /index.html;
        }
        location /api/ {
            proxy_set_header Host $host;
            proxy_pass http://app;
        }
    }
}

この設定によりBESTスコア記録時には全てのサーバのCPU使用率が80%以上90%以下くらいの使用率にコントロールすることができました
各サーバのCPU使用率

大きな改善3の際の構成図

大きな改善3の際の構成図

その他の改善

goのversion up(1.23→1.24rc1)

# go1.24rc1のインストール
go install golang.org/dl/go1.24rc1@latest
go1.24rc1 download
export GOROOT=/Users/ponyo877/sdk/go1.24rc1
export PATH=$GOROOT/bin:$PATH

# アプリケーションへの反映(go.modとgo.sumを削除した後に)
go mod tidy

pgoの活用

pproteinというNuruseJunチームさんの監視ツールを使っており、ここでpprof自体は取得できていたのであとはそれをローカルにDownloadしてきて、buildの際に参照できるようにMakefileを編集

# pprof取得shell
pprof_file=$(ssh isucon@54.65.138.220 ls -tr /home/isucon/data/*.pb.gz | tail -1)
scp isucon@${ISUCONサーバのIP}:$pprof_file profile.pb.gz
gzip -d profile.pb.gz
mv profile.pb pprof/profile.pprof

// Makefile
build:
-   CGO_ENABLED=0 $(LINUX_TARGET_ENV) $(BUILD) -o $(DESTDIR)/isuride -ldflags "-s -w"
+   CGO_ENABLED=0 $(LINUX_TARGET_ENV) $(BUILD) -o $(DESTDIR)/isuride -pgo ./pprof/profile.pprof -ldflags "-s -w"

GOCGの調整

これはよく分からずに他のISUCONのリポジトリを参考に調整しました...

// Makefile
build:
-   CGO_ENABLED=0 $(LINUX_TARGET_ENV) $(BUILD) -o $(DESTDIR)/isuride -pgo ./pprof/profile.pprof -ldflags "-s -w"
+   CGO_ENABLED=0 GOGC=500 $(LINUX_TARGET_ENV) $(BUILD) -o $(DESTDIR)/isuride -pgo ./pprof/profile.pprof -ldflags "-s -w"

fiberへの移行(SSE以外)

httpフレームワークを初期実装go-chiからGoで最速のと噂されているfiberへ移行しました
ただし、fiberでのSSEの実装は不具合があり解消されていない様だったのでSSE部分のみgo-chiで動かしています(issues#429: CLOSEDだけどまだ解決していない気がする)

実装 | fiberへの移行(SSE以外)

func main() {
	mux := setup()
	muxNotification := setupNotification()
	// go-chiサーバ
	go http.ListenAndServe(":8081", muxNotification)
	listenAddr := net.JoinHostPort("", strconv.Itoa(8080))
	// fiberサーバ
	if err := mux.Listen(listenAddr); err != nil {
		fmt.Printf("failed to listen: %v", err)
	}
}

// handler
func setupNotification() http.Handler {
	mux := chi.NewRouter()
	mux.With(appAuthMiddleware).HandleFunc("GET /api/app/notification", appGetNotification)
	mux.With(chairAuthMiddleware).HandleFunc("GET /api/chair/notification", chairGetNotification)
	return mux
}

func setup() *fiber.App {
	// 省略
	mux := fiber.New()
	mux.Post("/api/initialize", postInitialize)
	mux.Post("/api/app/users", appPostUsers)
	mux.Post("/api/owner/owners", ownerPostOwners)
	mux.Post("/api/chair/chairs", chairPostChairs)

	// app handlers
	{
		authedMuxApp := mux.Group("/api/app")
		authedMuxApp.Use(appAuthMiddlewareFiber)
		authedMuxApp.Post("/payment-methods", appPostPaymentMethods)
        // 省略
	}
	// owner handlersとchair handlersは省略
	return mux
}

handlerの中身は以下のように少しずつ変更

二部マッチング部分だけ別サーバで処理(gRPC)

以下の様に二部マッチング用のprotoを定義しbufでGoのコードを自動生成、アプリケーションが動いているサーバとは別のサーバでgrpcサーバを起動して

実装 | 二部マッチング部分だけ別サーバで処理(gRPC)

syntax = "proto3";

option go_package = "pkg/grpc";

package isuride;

service SubService {
  rpc MinCostFlow(MinCostFlowRequest) returns (MinCostFlowResponse);
}

message MinCostFlowRequest {
  repeated MatchableChair chairs = 1;
  repeated MatchableRide rides = 2;
}

message MinCostFlowResponse { repeated RideChair rideChairs = 1; }

message MatchableChair {
  string id = 1;
  string model = 2;
  Coordinate coordinate = 3;
  int64 createdAt = 4;
}

message MatchableRide {
  string id = 1;
  Coordinate coordinate = 2;
}

message Coordinate {
  int32 latitude = 1;
  int32 longitude = 2;
}

message RideChair {
  string rideID = 1;
  string chairID = 2;
}

// gRPCクライアント | 接続
subAddress := "192.168.0.12:8081"
conn, err := grpc.NewClient(subAddress, grpc.WithTransportCredentials(insecure.NewCredentials()))
if err != nil {
	panic(err)
}
client = pb.NewSubServiceClient(conn)

// gRPCクライアント | リクエスト
pair, err := client.MinCostFlow(context.Background(),
	&pb.MinCostFlowRequest{
		Chairs: matchableChair,
		Rides:  matchableRide,
	},
)

// gRPCサーバ | 起動
s := grpc.NewServer()
pb.RegisterSubServiceServer(s, NewServer())
reflection.Register(s)
s.Serve(listener)

JSONパースの一部自力化

最も多くのリクエストを受けるPOST /api/chair/coordinateを少しでも高速化するためJSONのUnmarshalとMarshalを自力で行いました

実装 | JSONパースの一部自力化

// JSON Unmarshal
func posComma(b []byte) int {
	if b[13] == 44 {
		return 13
	}
	if b[14] == 44 {
		return 14
	}
	if b[15] == 44 {
		return 15
	}
	return -1
}

func byteToInt(b []byte) int {
	sign := 1
	if b[0] == 45 {
		b = b[1:]
		sign = -1
	}
	n := 0
	for _, ch := range b {
		ch -= '0'
		n = n*10 + int(ch)
	}
	return sign * n
}

func chairPostCoordinateBindJSON(body []byte, req *Coordinate) {
	len := len(body)
	pos := posComma(body)
	req.Latitude = byteToInt(body[12:pos])
	req.Longitude = byteToInt(body[pos+13 : len-1])
}

// JSON Marshal
	c.Response().Header.SetContentType("application/json;charset=utf-8")
	c.Response().SetBodyRaw([]byte(`{"recorded_at":` + strconv.FormatInt(now.UnixMilli(), 10) + `}`))
	return c.SendStatus(http.StatusOK)

JSONパースのsonic化

POST /api/chair/coordinate以外の処理はJSONのMarshal/Unmarshalの操作を行うpackageで現時点で最速(と思われる)bytedance/sonicに移行します
https://github.com/bytedance/sonic

実装 | JSONパースのsonic化

上で切り替えたfiberでは以下のようにmuxの初期化時に以下のように指定します

// fiberでのjSONパースの入れ替え
-	mux := fiber.New()
+	mux := fiber.New(fiber.Config{
+		JSONEncoder:  sonic.Marshal,
+		JSONDecoder:  sonic.Unmarshal,
+		ErrorHandler: errorResponseHandler,
+	})

fiberではなく初期実装のまま書き換えるにはbindJSONとwriteJSONを書き換えれば良さそうです

import(
-   "encoding/json"
+   "github.com/bytedance/sonic"
)


func bindJSON(r *http.Request, v interface{}) error {
-   return json.NewDecoder(r.Body).Decode(v)
+   return sonic.ConfigFastest.NewDecoder(r.Body).Decode(v)
}

func writeJSON(w http.ResponseWriter, statusCode int, v interface{}) {
	w.Header().Set("Content-Type", "application/json;charset=utf-8")
	w.WriteHeader(statusCode)
-   buf, err := json.Marshal(v)
+   w.WriteHeader(statusCode)
+   err := sonic.ConfigFastest.NewEncoder(w).Encode(v)
	if err != nil {
		w.WriteHeader(http.StatusInternalServerError)
		return
	}
-   w.WriteHeader(statusCode)
-   w.Write(buf)
}

感想戦の感想

感想戦は本番にはない面白さがあり勉強になりました
特にほぼ同じ点数で最上川チームさんと競流ことができたのは個人的にワクワクしました

運営の皆様この様に機会をいただきありがとうございました!とても楽しかったです

ISUCON14の公式反省会でも以下のスライドで発表させていただきました!

Discussion