0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

ISUCON10に向けて、isucon9を行う

Last updated at Posted at 2020-08-30

講評などを見ながら理解したものを備忘録的に残していきます。
(都度更新します)
参考:
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あたりまで伸びました。

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?