一人ISUCON9やってみた


今年度のイスコンに初参加して、2週間ぐらい経ちましたが、あまり振り返りをしていなかったのと、暇なのでイスコン9をゆるーーーーーーーーーーーくやっていこうと思います。
ちなみに当日の点数は8350点で55位でした。

goでやります。

## 環境

https://github.com/isucon/isucon9-qualify
ここから取得できます。vagrantでやると一瞬でできます。(時間はかかります)

## はじめに

コードを分けましょう。これはめちゃくちゃ大事です。(個人的に
他の言語の実装は見てないのでわかりませんが、goの実装は初期実装で2300行ぐらいありました。適当でもいいので、ファイル分けをすると頭もコードもすっきりとし作業がだいぶ捗ります。

```
(ファイル分け前
.
├── Makefile
├── api.go
├── go.mod
├── go.sum
├── isucari
└── main.go

(ファイル分け後
├── Makefile
├── api.go
├── category.go
├── go.mod
├── go.sum
├── item.go
├── main.go
├── session.go
├── ship.go
├── struct.go
├── transaction.go
├── user.go
└── variables.go
```

5分ほどでささっとこんな感じにしました。

## 初期実装

初期実装時の点数と、alpでの解析結果です。
とりあえずalpの結果に従い `/users/transactions.json` を潰したいと思います。

```
{"pass":true,"score":2010,"campaign":0,"language":"Go","messages":[]}

+-------+--------+----------------------------------------------+-----+-----+-----+-----+-----+-------+-------+---------+-------+-------+-------+-------+--------+------------+------------+-------------+------------+
| COUNT | METHOD |                     URI                      | 1XX | 2XX | 3XX | 4XX | 5XX |  MIN  |  MAX  |   SUM   |  AVG  |  P1   |  P50  |  P99  | STDDEV | MIN(BODY)  | MAX(BODY)  |  SUM(BODY)  | AVG(BODY)  |
+-------+--------+----------------------------------------------+-----+-----+-----+-----+-----+-------+-------+---------+-------+-------+-------+-------+--------+------------+------------+-------------+------------+
|   173 | GET    | /users/transactions.json                     |   0 | 164 |   0 |   9 |   0 | 0.020 | 6.628 | 463.298 | 2.678 | 0.260 | 3.316 | 2.558 |  1.570 |      0.000 |  27221.000 | 3279381.000 |  18955.960 |
|   161 | GET    | /new_items/60.json                           |   0 | 161 |   0 |   0 |   0 | 0.032 | 1.156 |  52.544 | 0.326 | 0.188 | 0.068 | 0.040 |  0.239 |  22699.000 |  23398.000 | 3708692.000 |  23035.354 |
|    54 | POST   | /buy                                         |   0 |  30 |   0 |  24 |   0 | 1.608 | 1.660 |  51.956 | 0.962 | 0.012 | 0.000 | 1.608 |  0.793 |     29.000 |     49.000 |    1962.000 |     36.333 |
|   130 | GET    | /new_items.json                              |   0 | 130 |   0 |   0 |   0 | 0.040 | 1.008 |  42.576 | 0.328 | 0.400 | 0.164 | 0.164 |  0.241 |  22951.000 |  23726.000 | 3040029.000 |  23384.838 |
|   110 | GET    | /new_items/10.json                           |   0 | 110 |   0 |   0 |   0 | 0.060 | 1.112 |  26.480 | 0.241 | 1.112 | 0.132 | 0.076 |  0.176 |  23233.000 |  23983.000 | 2604353.000 |  23675.936 |
|   134 | GET    | /new_items/30.json                           |   0 | 134 |   0 |   0 |   0 | 0.052 | 1.068 |  26.396 | 0.197 | 0.280 | 0.080 | 0.092 |  0.153 |  23353.000 |  24060.000 | 3169184.000 |  23650.627 |
|    44 | POST   | /ship_done                                   |   0 |  22 |   0 |  22 |   0 | 0.436 | 0.816 |  21.746 | 0.494 | 0.012 | 0.812 | 0.666 |  0.378 |      0.000 |     83.000 |    1642.000 |     37.318 |
|    42 | POST   | /ship                                        |   0 |  29 |   0 |  13 |   0 | 0.075 | 0.824 |  21.307 | 0.507 | 0.000 | 0.820 | 0.812 |  0.390 |      0.000 |     61.000 |    2165.000 |     51.548 |
|   101 | GET    | /new_items/20.json                           |   0 | 101 |   0 |   0 |   0 | 0.060 | 0.732 |  19.556 | 0.194 | 0.384 | 0.092 | 0.100 |  0.152 |  23309.000 |  23845.000 | 2378681.000 |  23551.297 |
|    61 | POST   | /login                                       |   0 |  53 |   0 |   8 |   0 | 0.060 | 0.820 |  19.400 | 0.318 | 0.508 | 0.312 | 0.080 |  0.212 |     73.000 |    105.000 |    5791.000 |     94.934 |
|   103 | GET    | /new_items/1.json                            |   0 | 103 |   0 |   0 |   0 | 0.024 | 0.676 |  14.340 | 0.139 | 0.676 | 0.088 | 0.100 |  0.133 |  22966.000 |  23559.000 | 2395534.000 |  23257.612 |

```

# `/users/transactions.json` 

このエンドポイントは、確かユーザの椅子の取引履歴的なやつだった気がします。
下記が該当箇所の一部です。N+1が発生してますね。しかもめちゃくちゃでかい。
繰り返しの中だけで80行ありました。

```go
// 1st page
err := tx.Select(&items,"SELECT * FROM `items` WHERE (`seller_id` = ? OR `buyer_id` = ?) AND `status` IN (?,?,?,?,?) ORDER BY `created_at` DESC, `id` DESC LIMIT ?",...) 
...

for _, item := range items {
    seller, err := getUserSimpleByID(tx, item.SellerID)

    ...

    category, err := getCategoryByID(tx, item.CategoryID)

    ...

    if item.BuyerID != 0 {
        buyer, err := getUserSimpleByID(tx, item.BuyerID)
    }

    ...

    err = tx.Get(&transactionEvidence, "SELECT * FROM `transaction_evidences` WHERE `item_id` = ?", item.ID)

    ...

    if transactionEvidence.ID > 0 {
        shipping := Shipping{}
        err = tx.Get(&shipping, "SELECT * FROM `shippings` WHERE `transaction_evidence_id` = ?", transactionEvidence.ID)
        ...
    }
}

func getUserSimpleByID(q sqlx.Queryer, userID int64) (userSimple UserSimple, err error) {
	user := User{}
	err = sqlx.Get(q, &user, "SELECT * FROM `users` WHERE `id` = ?", userID)
	if err != nil {
		return userSimple, err
	}
	userSimple.ID = user.ID
	userSimple.AccountName = user.AccountName
	userSimple.NumSellItems = user.NumSellItems
	return userSimple, err
}

func getCategoryByID(q sqlx.Queryer, categoryID int) (category Category, err error) {
	err = sqlx.Get(q, &category, "SELECT * FROM `categories` WHERE `id` = ?", categoryID)
	if category.ParentID != 0 {
		parentCategory, err := getCategoryByID(q, category.ParentID)
		if err != nil {
			return category, err
		}
		category.ParentCategoryName = parentCategory.CategoryName
	}
	return category, err
}
```

まず最初のクエリを直します。
itemテーブルのstatusは、こんな感じです。

```sql
`status` enum('on_sale', 'trading', 'sold_out', 'stop', 'cancel') NOT NULL,
```
これ`status IN (?,?,?,?,?)`いりませんね。
※(?, ?, ?, ?, ?)には全てのstatusが入ります。
消します。

```sql
SELECT * FROM `items` WHERE (`seller_id` = ? OR `buyer_id` = ?) ORDER BY `created_at` DESC, `id` DESC LIMIT ?
```

次にここ`(seller_id = ? OR buyer_id = ?)`をなんとかしましょう。
ここは正直カンニングしました。UNIONでやったほうが早いらしいです。
あとは、適当にitemsテーブルの`seller_id`と`buyer_id`にインデックスでも貼っておきましょう。

```sql
SELECT * FROM items WHERE seller_id = ?
UNION
SELECT * FROM items WHERE buyer_id = ? ORDER BY `created_at` DESC, `id` DESC LIMIT ?
```

これでいいでしょう。（ほんとは、joinしてseller_idとbuyer_idうまく取って来たかったけどそんなクエリかけませんでした。

## 続いてNの部分に取り組みたいと思います。

### ユーザの取得部分の解決

該当箇所

```go
seller, err := getUserSimpleByID(tx, item.SellerID)
if item.BuyerID != 0 {
    buyer, err := getUserSimpleByID(tx, item.BuyerID)
}

func getUserSimpleByID(q sqlx.Queryer, userID int64) (userSimple UserSimple, err error) {
    user := User{}
    err = sqlx.Get(q, &user, "SELECT * FROM `users` WHERE `id` = ?", userID)
    if err != nil {
        return userSimple, err
    }
    userSimple.ID = user.ID
    userSimple.AccountName = user.AccountName
    userSimple.NumSellItems = user.NumSellItems
    return userSimple, err
}
```

現在は、`/users/transactions.json`に取り組んでいますが、この`getUserSimpleByID`という関数は他の箇所のN+1の原因にもなってた気がします。
JOINで一つのクエリでとってもいいんですが、僕はそんなクエリかけないんでキャッシュを使用し解決しようと思います。(Redis使用しました)

redisに接続するために今回は[redigo](https://github.com/gomodule/redigo)を使用しました。
redisクライアントは調べたら他にも[go-redis](https://github.com/go-redis/redis)というのもあるらしいですが、どこかの記事でredigoの方が早いって書いてあったのでredigoを使用することにします。
構造体をキャッシュする時は、jsonにしてからredisに挿入するとめちゃくちゃ楽です。
また、redigoをそのまま使ってもいいんですが、redigoをイスコン専用にラップした[redisful](https://github.com/naoto67/ISUCON/blob/master/redis/redisful/redisful.go)こちらのコード使用したいと思います。
本番でアプリ側のredis導入コストを限界まで下げるために、試行錯誤を繰り返し作成しました。
使い方がわかればそのままredigoを使うよりは断然簡単かつ早くコードに落とせると思うので、時間がある方は試してみてください。

Redisにユーザを保存する際は、ハッシュ型を使用します。
理由としては、usersテーブルへのクエリはidで検索していることが多かったので、idで検索しやすいようにというのが大きいです。
一つaccount_nameで検索しているクエリがあるんですが、そちらはMySQLの方から取ってきたいと思います。
ユーザのデータは以下のように格納されます。

```bash
127.0.0.1:6379> keys *
USERS

127.0.0.1:6379> HGETALL USERS
USER-FIELD-663
{"account_name":"mita_kousuke","address":"山梨県秋葉区1-8","created_at":"2019-08-10T01:11:06Z","hashed_password":"JDJhJDEwJFBTdVZoN21QNlhucDRhcW5zMDVjUU8xVzFKWTRaNjVacUZ0VkQ1ZENBTkMyMjhUdkxobFc2","id":663,"last_bump":"2000-01-01T00:00:00Z","num_sell_items":0}
USER-FIELD-2004
{"account_name":"onoda_stmaria","address":"秋田県東山区5-47","created_at":"2019-08-10T01:33:27Z","hashed_password":"JDJhJDEwJGYvRkVYZ2FhVXpoc094eVM5ak90Y2VJNE04YTIzMEtVRzhyY0EzSkxWNlJOUVVtdXZTY04y","id":2004,"last_bump":"2000-01-01T00:00:00Z","num_sell_items":1}
```

Redisへの保存ができると、`getUserSimpleByID`でMySQLから取得している部分をRedisから取ってくるように変更すれば、MySQLの負担がだいぶ減ります。

### カテゴリ取得部分の解決

該当箇所

```go
category, err := getCategoryByID(tx, item.CategoryID)

func getCategoryByID(q sqlx.Queryer, categoryID int) (category Category, err error) {
    err = sqlx.Get(q, &category, "SELECT * FROM `categories` WHERE `id` = ?", categoryID)
    if category.ParentID != 0 {
        parentCategory, err := getCategoryByID(q, category.ParentID)
        if err != nil {
            return category, err
        }
        category.ParentCategoryName = parentCategory.CategoryName
    }
    return category, err
}
```

カテゴリについてですが、こちらもRedisでキャッシュしてもいいんですが、`02_categories.sql`というファイルがあり中身はこんな感じです。

```sql
INSERT INTO categories (`id`,`parent_id`,`category_name`) VALUES
(1,0,"ソファー"),
(2,1,"一人掛けソファー"),
(3,1,"二人掛けソファー"),
(4,1,"コーナーソファー"),
(5,1,"二段ソファー"),
...
(66,60,"空気椅子");
```

アプリケーションコードを見てみると、カテゴリの更新や新規登録はないのがわかるのでこちらは、ハードコーディングしてあげれば良さそうですね。

```go
var (
	categories = map[int]interface{}{
		1:  Category{ID: 1, ParentID: 0, CategoryName: "ソファー"},
		2:  Category{ID: 2, ParentID: 1, CategoryName: "一人掛けソファー", ParentCategoryName: "ソファー"},
		3:  Category{ID: 3, ParentID: 1, CategoryName: "二人掛けソファー", ParentCategoryName: "ソファー"},
        ...
		64: Category{ID: 64, ParentID: 60, CategoryName: "ロッキングチェア", ParentCategoryName: "座椅子"},
		65: Category{ID: 65, ParentID: 60, CategoryName: "座布団", ParentCategoryName: "座椅子"},
		66: Category{ID: 66, ParentID: 60, CategoryName: "空気椅子", ParentCategoryName: "座椅子"},
	}
)

func getCategoryByID(q sqlx.Queryer, categoryID int) (category Category, err error) {
	c := categories[categoryID]
	if c == nil {
		return category, errors.New("not found")
	}
	category = c.(Category)
	return category, nil
}
```
こんな感じでどうでしょうか。これでかなりクエリが減るので結構速くなります。
引数のq sqlx.Queryerを消してないのは、呼び出し側の引数を変えるのがめんどくさいからです。
本来であれば必ず消すべきですが、今回は大目にみてください。

### 取引情報取得部分の解決

該当箇所

```go

    err = tx.Get(&transactionEvidence, "SELECT * FROM `transaction_evidences` WHERE `item_id` = ?", item.ID)

    ...

    if transactionEvidence.ID > 0 {
        shipping := Shipping{}
        err = tx.Get(&shipping, "SELECT * FROM `shippings` WHERE `transaction_evidence_id` = ?", transactionEvidence.ID)
        ...
    }
```

ここは説明が難しい箇所ですね。（疲れてきた
この`transaction_evidences`と`shippings`テーブルは確か必ず1対1が成り立つテーブルだった気がします。
`postBuy`というとこで作成されているんですが、そこを見ればなんとなくわかると思います。

1対1なので、INNER JOINしてあげれば、2回のクエリを実行しなくて大丈夫そうです。
また。`WHERE`句 `item_id`で検索をかけて見つかれば、itemDetailsに値を代入するといった感じでした。
このクエリ繰り返しの外に出すことできそうですね。

```sql
SELECT t.*, s.* FROM `transaction_evidences` t INNER JOIN `shippings` s ON t.`id` = s.transaction_evidence_id WHERE t.`item_id` IN (?)
```

これで外に出すことができます。
この結果を`item_id`が一致する`itemDetail`に入れてあげればおしまいです。

### 解決後のベンチマーク

上記を解決し再度ベンチを回した結果です。4000コイン増えました。
alpの結果も同時に見てみると、sumの秒数が減っているのに対し、COUNTがめっちゃ増えてますね。

```bash
{"pass":true,"score":6650,"campaign":0,"language":"Go","messages":["GET /items/48805.json: リクエストに失敗しました（タイムアウトしました）"]}

+-------+--------+----------------------------------------------+-----+-----+-----+-----+-----+-------+-------+---------+-------+-------+-------+-------+--------+------------+------------+--------------+------------+
| COUNT | METHOD |                     URI                      | 1XX | 2XX | 3XX | 4XX | 5XX |  MIN  |  MAX  |   SUM   |  AVG  |  P1   |  P50  |  P99  | STDDEV | MIN(BODY)  | MAX(BODY)  |  SUM(BODY)   | AVG(BODY)  |
+-------+--------+----------------------------------------------+-----+-----+-----+-----+-----+-------+-------+---------+-------+-------+-------+-------+--------+------------+------------+--------------+------------+
|   660 | GET    | /users/transactions.json                     |   0 | 654 |   0 |   6 |   0 | 0.012 | 0.912 | 317.896 | 0.482 | 0.008 | 0.816 | 0.012 |  0.394 |      0.000 |  31787.000 | 14157082.000 |  21450.124 |
|   102 | POST   | /buy                                         |   0 |  71 |   0 |  31 |   0 | 0.738 | 2.248 | 123.671 | 1.212 | 0.004 | 1.624 | 0.738 |  0.698 |      0.000 |     49.000 |     3513.000 |     34.441 |
|    87 | POST   | /ship_done                                   |   0 |  66 |   0 |  21 |   0 | 0.808 | 0.892 |  56.212 | 0.646 | 0.000 | 0.824 | 0.816 |  0.329 |     29.000 |     83.000 |     3287.000 |     37.782 |
|   254 | GET    | /new_items.json                              |   0 | 254 |   0 |   0 |   0 | 0.032 | 1.196 |  53.432 | 0.210 | 0.108 | 0.036 | 0.116 |  0.143 |  22923.000 |  23924.000 |  5947564.000 |  23415.606 |
|    66 | POST   | /complete                                    |   0 |  66 |   0 |   0 |   0 | 0.008 | 0.920 |  51.608 | 0.782 | 0.132 | 0.864 | 0.804 |  0.161 |     34.000 |     34.000 |     2244.000 |     34.000 |
|    80 | POST   | /ship                                        |   0 |  66 |   0 |  14 |   0 | 0.008 | 0.860 |  51.540 | 0.644 | 0.004 | 0.820 | 0.812 |  0.330 |     29.000 |     61.000 |     4488.000 |     56.100 |
|   320 | GET    | /new_items/30.json                           |   0 | 319 |   0 |   1 |   0 | 0.008 | 0.900 |  31.505 | 0.098 | 0.196 | 0.112 | 0.084 |  0.101 |      0.000 |  24078.000 |  7557199.000 |  23616.247 |
|   232 | GET    | /new_items/40.json                           |   0 | 232 |   0 |   0 |   0 | 0.012 | 1.144 |  27.320 | 0.118 | 0.072 | 0.056 | 0.040 |  0.112 |  23406.000 |  24049.000 |  5517374.000 |  23781.784 |
|   185 | GET    | /new_items/10.json                           |   0 | 185 |   0 |   0 |   0 | 0.016 | 0.940 |  22.652 | 0.122 | 0.940 | 0.076 | 0.020 |  0.101 |  23218.000 |  24021.000 |  4380683.000 |  23679.368 |
|    62 | POST   | /login                                       |   0 |  54 |   0 |   8 |   0 | 0.060 | 0.768 |  20.608 | 0.332 | 0.572 | 0.476 | 0.092 |  0.226 |     73.000 |    105.000 |     5880.000 |     94.839 |
|   157 | GET    | /new_items/60.json                           |   0 | 157 |   0 |   0 |   0 | 0.016 | 0.780 |  19.968 | 0.127 | 0.512 | 0.228 | 0.132 |  0.111 |  22688.000 |  23419.000 |  3619546.000 |  23054.433 |
|   120 | GET    | /new_items/20.json                           |   0 | 120 |   0 |   0 |   0 | 0.016 | 0.680 |  16.352 | 0.136 | 0.680 | 0.092 | 0.016 |  0.108 |  23185.000 |  23894.000 |  2827348.000 |  23561.233 |
|   263 | GET    | /new_items/50.json                           |   0 | 263 |   0 |   0 |   0 | 0.008 | 0.204 |  15.548 | 0.059 | 0.104 | 0.028 | 0.072 |  0.037 |  22929.000 |  23713.000 |  6134922.000 |  23326.700 |

```

### `/users/transactions.json` まとめ

1. OR検索ではなくUNIONを使用して高速化
2. `users`テーブルのデータをRedisでキャッシュ
3. `items`テーブルの`seller_id`と`buyer_id`にindexを貼る
3. ハードコーディングで`categories`テーブルへのクエリを削除
4. `transaction_evidences` と `shipping` テーブルをINNER JOINで取得し、かつ繰り返しの外にクエリを移動
5. ShipmentStatusがdoneのものをキャッシュ

## 最後に

上記のN+1を直した後に色々とやって、8000点まで行きました。
本番は3台構成とはいえ、それを越えることができませんでした...
来週末もおそらく暇なので記事を書くかはわかりませんが、予選突破の1万点を超えられるように頑張りたいと思います.

`users/transactions.json`以外でやったこと

1. `/buy`の中のAPIリクエストを非同期処理に変更
2. `configs`をRDBからRedisに移動
3. usersのid取得をRDBではなく、Redisから取得するように変更
4. transaction_evidencesテーブルとshippingsテーブルを1つのテーブルにマージ(これについては、やらない方がいいと思います。）
5. loginにSleepを入れる

今回使用したリポジトリも載せておきます。
正直人に見せられるほどのコードではないので、次はもっと綺麗に書きたいですね。
https://github.com/naoto67/isucon9

今年初めてイスコンに参加して決勝には行けませんでしたが、自分はとても良い経験になったと思っています。
4月から9月まで約半年間ちょくちょくと過去問で練習はしていました。
練習を始めた頃は、N+1を知らないどころか生SQLすら書けないし、goの構文すら怪しい。
キャッシュ？？なにそれ難しいそう。。。という感じでした。
N+1やキャッシュに関しては、自分にはちょっと扱えなさそうと思っていましたが、やってみると思ったよりも簡単でかつ実装が楽しいものでした。
僕みたいに週末暇な人は、やってみるといいかもしれません。