講評などを見ながら理解したものを備忘録的に残していきます。
(都度更新します)
参考:
http://isucon.net/archives/53916974.html
#新着・カテゴリ新着・ユーザごと新着商品
私の担当がSQL/アプリですので、こちらのインデックス問題、N+1問題に対して残して行きます
##インデックス不足
こちらはSQLでよく検索する場所に対して、インデックスを追加することで高速化にできます。
インデックス名の指定が必要ですが、インデックス名で実際に検索するわけではなく、SQLのカラム名で検索するときに有効です。
INDEX "index名" (`"カラム名"`)
で追加できます。
isucon9では、
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を使った解法
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)を目指します
私が書いたコードをまず載せます
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
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を呼び出し時間を食ってました。
ここを、
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あたりまで伸びました。