ISUCON10に向けて、isucon9を行う

講評などを見ながら理解したものを備忘録的に残していきます。
（都度更新します）
参考:
http://isucon.net/archives/53916974.html

新着・カテゴリ新着・ユーザごと新着商品

私の担当がSQL/アプリですので、こちらのインデックス問題、N+1問題に対して残して行きます

インデックス不足

こちらはSQLでよく検索する場所に対して、インデックスを追加することで高速化にできます。
インデックス名の指定が必要ですが、インデックス名で実際に検索するわけではなく、SQLのカラム名で検索するときに有効です。

INDEX "index名" (`"カラム名"`)

で追加できます。
isucon9では、
webapp/sql/01_schema.sqlの場所に

webapp/sql/01_schema.sql

CREATE TABLE `items` (
  `id` bigint NOT NULL AUTO_INCREMENT PRIMARY KEY,
  `seller_id` bigint NOT NULL,
  `buyer_id` bigint NOT NULL DEFAULT 0,
  `status` enum('on_sale', 'trading', 'sold_out', 'stop', 'cancel') NOT NULL,
  `name` varchar(191) NOT NULL,
  `price` int unsigned NOT NULL,
  `description` text NOT NULL,
  `image_name` varchar(191) NOT NULL,
  `category_id` int unsigned NOT NULL,
  `created_at` datetime NOT NULL DEFAULT CURRENT_TIMESTAMP,
  `updated_at` datetime NOT NULL DEFAULT CURRENT_TIMESTAMP,
  INDEX idx_category_id (`category_id`),
  INDEX idx_created_at (`created_at`),
  INDEX idx_name (`name`),
  INDEX idx_seller_id (`seller_id`),
  INDEX idx_buyer_id (`buyer_id`),
  INDEX idx_status (`status`),
  INDEX idx_price (`price`)
) ENGINE=InnoDB DEFAULT CHARACTER SET utf8mb4;

と既存に追加されていたidx_category_idのように、INDEXを追加することでスコアがローカル実行時、
3110 から4500ほどまで平均してのびました。

N+1問題

参考記事:
https://qiita.com/muroya2355/items/d4eecbe722a8ddb2568b
https://qiita.com/rihofujino/items/b69e6a23e7cef1d692c4

こちらは、例えばisucon9予選問題、getNewItems内で、itemのsellerIDによって、
userテーブルから、N+1の検索が毎回実行され、
O(item数 * N+1)の計算時間が実行されてしまう問題だと思います。
方針としてはjoin句などでくっつけるか、itemのsellerIDによってO(1)で持ってくるかしなければいけません。

mapを使った解法

webapp/go/main.go

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
}

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

isucon9のgetNewItemsのgetUserSimpleByIDに注目します。
元々items(以下n)回*users(以下m)回を探してuserを返しています。
計算量はざっとO(nm)とします
ここでO(N+M)を目指します
私が書いたコードをまず載せます

webapp/go/main.go

users := map[int64]UserSimple{}
	rows,_ := dbx.Queryx("SELECT * FROM users")
	for rows.Next() {
		var user User
		var userSimple UserSimple
		rows.StructScan(&user)
		userSimple.ID = user.ID
		userSimple.AccountName = user.AccountName
		userSimple.NumSellItems = user.NumSellItems
		users[user.ID] = userSimple
	}
	// fmt.Println(users,"users")
	// sqlx.Get(q, &user, "SELECT * FROM `users` WHERE `id` = ?", userID)
	itemSimples := []ItemSimple{}
for _, item := range items {
	seller, ok := users[item.SellerID]
        .
        .
}

このようにして、userを前処理として、全て持ってきて、userIDで格納し、
それを、O(1)アクセスでfor item時に読み込ませる...
という処理でO(N+M)としたのですが、スコア的にはほぼ変化なしとなりました。
原因として考えられるのは、

・元々のsqlx.getの時点とやってる計算量がほんとは変わらない
・N+1問題の適用箇所が少なく、もっと増やせばスコア的に伸びる
・この前処理のどこかでエラーを吐いてて早くなってる反面エラーが発生しスコア的に変化がない
・ボトルネックがこれ以前にたくさんあり、そこを解消しなければここのスコアの変化は見れない

だと考えています

購入

参考記事:
https://www.takono.io/posts/2019/09/isucon/
https://github.com/takonomura
https://qiita.com/TsuyoshiUshio@github/items/c3234f3705949d8cf413

webapp/go/main.go

	scr, err := APIShipmentCreate(getShipmentServiceURL(), &APIShipmentCreateReq{
		ToAddress:   buyer.Address,
		ToName:      buyer.AccountName,
		FromAddress: seller.Address,
		FromName:    seller.AccountName,
	})
	if err != nil {
		log.Print(err)
		outputErrorMsg(w, http.StatusInternalServerError, "failed to request to shipment service")
		tx.Rollback()

		return
	}

	pstr, err := APIPaymentToken(getPaymentServiceURL(), &APIPaymentServiceTokenReq{

元々、APIShipmentCreate / APIPaymentToken
で外部APIを呼び出し時間を食ってました。
ここを、

webapp/go/main.go

var scr *APIShipmentCreateRes
	var scrErr error
	var wg sync.WaitGroup
	var mu sync.Mutex
	wg.Add(1)
	go func() {
		mu.Lock()
		defer mu.Unlock()
		defer wg.Done()
		scr, scrErr = APIShipmentCreate(context.Background(), getShipmentServiceURL(context.Background()), &APIShipmentCreateReq{
			ToAddress:   buyer.Address,
			ToName:      buyer.AccountName,
			FromAddress: seller.Address,
			FromName:    seller.AccountName,
		})
	}()

	pstr, err := APIPaymentToken(context.Background(),getPaymentServiceURL(context.Background()), &APIPaymentServiceTokenReq{
		ShopID: PaymentServiceIsucariShopID,
		Token:  rb.Token,
		APIKey: PaymentServiceIsucariAPIKey,
		Price:  targetItem.Price,
	})
	if err != nil {
		log.Print(err)

		outputErrorMsg(w, http.StatusInternalServerError, "payment service is failed")
		tx.Rollback()
		return
	}
	wg.Wait()
 if scrErr != nil {
		log.Print(err)
		outputErrorMsg(w, http.StatusInternalServerError, "failed to request to shipment service")
		tx.Rollback()

		return
	}

nilさんのを参考にし、
とすることで、APIShipmentCreateをwaitに回すことで多少早くなると思われます。
(contextは別件での処理です)
これでスコア(contextを入れている処理)3300 ~ 3500　から　3700 ~ 4220あたりまで伸びました。