はじめに

先日、 Rapidash というGoのためのキャッシュライブラリが公開されました。

このライブラリについて簡単な説明をすると、弊社の負荷対策用ライブラリの一つで、主にデータベースの負荷分散を目的として開発したライブラリとなります。実際に弊社で開発・運用しているスマートフォン向けブラウザゲームでも利用されており、日々負荷分散に貢献しております。

※詳細はメインコミッターである @goccy がこちらの記事に書いております。興味を持ったかたは是非ご一読いただければと思います。

今回は ISUCON8予選の問題へRapidashを適用していく過程と、実際にどれだけ効果があったのかについて書いていこうと思います。

計測環境など

使用したマシン

MacBookPro(15-inch, 2017)
プロセッサ 3.1GHz Intel Core i7
メモリ 16GB 2133 MHz LPDDR3
macOS mojave(バージョン10.14.5)

ミドルウェア

memcached 1.5.8
mysqld  Ver 5.7.22 for osx10.12 on x86_64 (Homebrew)

※普段開発に用いているMacBookProを用いての計測となります。実際に予選で使用されたマシンスペックとは異なります。

ファーストベンチマークを測る

どれくらい効果があるのかを知るためには基準となるベンチマークが必要になるので、まずは何も変更を加えていない状態でベンチマークを計測します。

5回ほど計測してそれぞれ 1545, 1125, 1486, 1715, 1101 でした。
今回は1486 の時のスコアを基準としたいと思います。下記はそのスコアを出した時の詳細になります。

[  info ] [isu8q-bench] 2019/08/23 16:01:03.094018 bench.go:510: get 787
[  info ] [isu8q-bench] 2019/08/23 16:01:03.094352 bench.go:511: post 221
[  info ] [isu8q-bench] 2019/08/23 16:01:03.094371 bench.go:512: delete 29
[  info ] [isu8q-bench] 2019/08/23 16:01:03.094392 bench.go:513: static 616
[  info ] [isu8q-bench] 2019/08/23 16:01:03.094413 bench.go:514: top 44
[  info ] [isu8q-bench] 2019/08/23 16:01:03.094439 bench.go:515: reserve 50
[  info ] [isu8q-bench] 2019/08/23 16:01:03.094452 bench.go:516: cancel 29
[  info ] [isu8q-bench] 2019/08/23 16:01:03.094463 bench.go:517: get_event 43
[  info ] [isu8q-bench] 2019/08/23 16:01:03.094473 bench.go:518: score 1486

問題に使用されているクエリとテーブルを知る

本来であればボトルネックを探すところから始めるべきですが、今回は Rapidash を適用することが目的です。そのため、存在するテーブルとそのテーブルに対して発行されているクエリを洗い出すところから始めます。
下記がその結果です。

Tables

users
reservations
events
sheets
administrators

SELECT

users

SELECT id, nickname FROM users WHERE id = ?

SELECT * FROM users WHERE login_name = ?

reservations

SELECT * FROM reservations WHERE event_id = ? AND sheet_id = ? AND canceled_at IS NULL GROUP BY event_id, sheet_id HAVING reserved_at = MIN(reserved_at)

SELECT r.*, s.rank AS sheet_rank, s.num AS sheet_num FROM reservations r INNER JOIN sheets s ON s.id = r.sheet_id WHERE r.user_id = ? ORDER BY IFNULL(r.canceled_at, r.reserved_at) DESC LIMIT 5

SELECT IFNULL(SUM(e.price + s.price), 0) FROM reservations r INNER JOIN sheets s ON s.id = r.sheet_id INNER JOIN events e ON e.id = r.event_id WHERE r.user_id = ? AND r.canceled_at IS NULL

SELECT event_id FROM reservations WHERE user_id = ? GROUP BY event_id ORDER BY MAX(IFNULL(canceled_at, reserved_at)) DESC LIMIT 5

SELECT * FROM reservations WHERE event_id = ? AND sheet_id = ? AND canceled_at IS NULL GROUP BY event_id HAVING reserved_at = MIN(reserved_at) FOR UPDATE

SELECT r.*, s.rank AS sheet_rank, s.num AS sheet_num, s.price AS sheet_price, e.price AS event_price FROM reservations r INNER JOIN sheets s ON s.id = r.sheet_id INNER JOIN events e ON e.id = r.event_id WHERE r.event_id = ? ORDER BY reserved_at ASC FOR UPDATE

events

SELECT * FROM events ORDER BY id ASC

SELECT * FROM events WHERE id = ?

sheets

SELECT * FROM sheets ORDER BY `rank`, num

SELECT COUNT(*) FROM sheets WHERE `rank` = ?

SELECT * FROM sheets WHERE id NOT IN (SELECT sheet_id FROM reservations WHERE event_id = ? AND canceled_at IS NULL FOR UPDATE) AND `rank` = ? ORDER BY RAND() LIMIT 1

SELECT * FROM sheets WHERE `rank` = ? AND num = ?

administrators

SELECT id, nickname FROM administrators WHERE id = ?

SELECT * FROM administrators WHERE login_name = ?

others

SELECT SHA2(?, 256)

INSERT

users

INSERT INTO users (login_name, pass_hash, nickname) VALUES (?, SHA2(?, 256), ?)

reservations

INSERT INTO reservations (event_id, sheet_id, user_id, reserved_at) VALUES (?, ?, ?, ?)

events

INSERT INTO events (title, public_fg, closed_fg, price) VALUES (?, ?, 0, ?)

UPDATE

reservations

UPDATE reservations SET canceled_at = ? WHERE id = ?

events

UPDATE events SET public_fg = ?, closed_fg = ? WHERE id = ?

DELETE

None

どのコンポーネントにキャッシュするのか決定する

Rapidash には下記の3つのコンポーネントが用意されています

ReadOnlyなテーブルのための FirstLevelCache(FLC)
Read/Writeなテーブルのための SecondLevelCache(SLC)
単純なキャッシュのset/getのためのLastLevelCache(LLC)

先ほどの結果から、各テーブルをどのコンポーネントにキャッシュしていくのかを決定していきます。

FirstLevelCache(FLC)

events
sheets
administrators

SecondLevelCache(SLC)

reservations
users

基本的にReadOnlyなテーブルをFLC へ、 Read/WriteなテーブルをSLC へ割り振っていくだけですが、今回はWriteが走る events を特別に FLC へ割り振ることにしました。
これは events へのWrite処理が全てadmin経由でのみ発生し書き込み頻度が高くなく、かつWebサーバを一台構成にしたためです。書き込みが発生した場合はキャッシュを改めて作成し直す方が良いという判断になります。

もし複数台になる場合は書き込みが発生した際のキャッシュ整合性の担保を別途考慮する必要があります。

Rapidashを適用する

キャッシュ戦略が決まりましたので、実際にRapidash を導入するための変更をアプリケーションコードへ加えていきます。
今回は下記のような流れで Rapidash を使用できるようにすることをゴールとして変更を加えていきます。

アプリケーション起動時に Rapidashのオブジェクトを作成する
作成した Rapidash オブジェクトに対して各テーブルをいずれかのコンポーネント(FLC/SLC)へ登録していく
作成した Rapidash オブジェクトを経由してトランザクションを発行し各テーブルへのCRUD操作をしていく

1. Indexをはる

Rapidash 経由でキャッシュを効かせた状態でCRUDするには適切にIndexがはられている必要があります。

まずは、使用されているクエリを見ながら、過不足なく各テーブルへIndexを貼っていきます。
万が一不足があった場合は、 Rapidash が実行時にエラーやWarningを吐くので随時修正していきましょう。
今回は下記のように Index を貼りました。db/schema.sql に記述されています。

CREATE TABLE IF NOT EXISTS users (
    id          INTEGER UNSIGNED PRIMARY KEY AUTO_INCREMENT,
    nickname    VARCHAR(128) NOT NULL,
    login_name  VARCHAR(128) NOT NULL,
    pass_hash   VARCHAR(128) NOT NULL,
    UNIQUE KEY login_name_uniq (login_name)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

CREATE TABLE IF NOT EXISTS events (
    id          INTEGER UNSIGNED PRIMARY KEY AUTO_INCREMENT,
    title       VARCHAR(128)     NOT NULL,
    public_fg   TINYINT(1)       NOT NULL,
    closed_fg   TINYINT(1)       NOT NULL,
    price       INTEGER UNSIGNED NOT NULL
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

CREATE TABLE IF NOT EXISTS sheets (
    id          INTEGER UNSIGNED PRIMARY KEY AUTO_INCREMENT,
    `rank`      VARCHAR(128)     NOT NULL,
    num         INTEGER UNSIGNED NOT NULL,
    price       INTEGER UNSIGNED NOT NULL,
    UNIQUE KEY rank_num_uniq (`rank`, num)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

CREATE TABLE IF NOT EXISTS reservations (
    id          INTEGER UNSIGNED PRIMARY KEY AUTO_INCREMENT,
    event_id    INTEGER UNSIGNED NOT NULL,
    sheet_id    INTEGER UNSIGNED NOT NULL,
    user_id     INTEGER UNSIGNED NOT NULL,
    reserved_at DATETIME(6)      NOT NULL,
    canceled_at DATETIME(6)      DEFAULT NULL,
    KEY user_id_and_canceled_at_idx (user_id, canceled_at),
    KEY event_id_and_sheet_id_idx (event_id, canceled_at, sheet_id)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

CREATE TABLE IF NOT EXISTS administrators (
    id          INTEGER UNSIGNED PRIMARY KEY AUTO_INCREMENT,
    nickname    VARCHAR(128) NOT NULL,
    login_name  VARCHAR(128) NOT NULL,
    pass_hash   VARCHAR(128) NOT NULL,
    UNIQUE KEY login_name_uniq (login_name)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

2. Marshaler/Unmarshaler/Struct を実装する

次に、 Rapidash が提供しているAPIを呼び出すのに必要な関数を各テーブルの構造体へ実装していきます。

下記は https://github.com/knocknote/rapidash.go から一部抜粋したコードになります。

rapidash.go

type Marshaler interface {
    EncodeRapidash(Encoder) error
}

type Unmarshaler interface {
    DecodeRapidash(Decoder) error
}

func (tx *Tx) CreateByTable(tableName string, marshaler Marshaler) (int64, error) {}

func (tx *Tx) FindByQueryBuilder(builder *QueryBuilder, unmarshaler Unmarshaler) error {}

上記のコードの通り、Rapidash 経由でテーブルに対してRead/Writeをするには、それぞれUnmarshaler/Marshaler の実装が必要であることがわかります。

またRapidash オブジェクトに対してテーブルを登録するためにWarmUpを呼び出す必要がありますが、その際にあらかじめテーブル構造を知らせる必要があるため、Strcut の実装も必要になります。
これらを実装することで、はじめてRapidash を経由してのCRUD操作が可能になります。

実際に events や reservations に対して実装すると下記のようになります。

type Event struct {
    ID       int64  `json:"id,omitempty"`
    Title    string `json:"title,omitempty"`
    PublicFg bool   `json:"public,omitempty"`
    ClosedFg bool   `json:"closed,omitempty"`
    Price    int64  `json:"price,omitempty"`

    Total   int                `json:"total"`
    Remains int                `json:"remains"`
    Sheets  map[string]*Sheets `json:"sheets,omitempty"`
}

func (e *Event) DecodeRapidash(decoder rapidash.Decoder) error {
    e.ID = decoder.Int64("id")
    e.Title = decoder.String("title")
    e.PublicFg = decoder.Bool("public_fg")
    e.ClosedFg = decoder.Bool("closed_fg")
    e.Price = decoder.Int64("price")
    return decoder.Error()
}

func (e Event) RapidashStruct() *rapidash.Struct {
    return rapidash.NewStruct("events").
        FieldInt64("id").
        FieldString("title").
        FieldBool("public_fg").
        FieldBool("closed_fg").
        FieldInt64("price")
}

type EventSlice []*Event

func (e *EventSlice) DecodeRapidash(decoder rapidash.Decoder) error {
    *e = make(EventSlice, decoder.Len())
    for i := 0; i < decoder.Len(); i++ {
        var event Event
        if err := event.DecodeRapidash(decoder.At(i)); err != nil {
            return err
        }
        (*e)[i] = &event
    }
    return decoder.Error()
}

type Reservation struct {
    ID         int64      `json:"id"`
    EventID    int64      `json:"-"`
    SheetID    int64      `json:"-"`
    UserID     int64      `json:"-"`
    ReservedAt *time.Time `json:"-"`
    CanceledAt *time.Time `json:"-"`

    Event          *Event `json:"event,omitempty"`
    SheetRank      string `json:"sheet_rank,omitempty"`
    SheetNum       int64  `json:"sheet_num,omitempty"`
    Price          int64  `json:"price,omitempty"`
    ReservedAtUnix int64  `json:"reserved_at,omitempty"`
    CanceledAtUnix int64  `json:"canceled_at,omitempty"`
}

func (r *Reservation) EncodeRapidash(encoder rapidash.Encoder) error {
    if r.ID != 0 {
        encoder.Int64("id", r.ID)
    }
    encoder.Int64("event_id", r.EventID)
    encoder.Int64("sheet_id", r.SheetID)
    encoder.Int64("user_id", r.UserID)
    encoder.TimePtr("reserved_at", r.ReservedAt)
    encoder.TimePtr("canceled_at", r.CanceledAt)
    return encoder.Error()
}

func (r *Reservation) DecodeRapidash(decoder rapidash.Decoder) error {
    r.ID = decoder.Int64("id")
    r.EventID = decoder.Int64("event_id")
    r.SheetID = decoder.Int64("sheet_id")
    r.UserID = decoder.Int64("user_id")
    r.ReservedAt = decoder.TimePtr("reserved_at")
    r.CanceledAt = decoder.TimePtr("canceled_at")

    return decoder.Error()
}

func (r Reservation) RapidashStruct() *rapidash.Struct {
    return rapidash.NewStruct("reservations").
        FieldInt64("id").
        FieldInt64("event_id").
        FieldInt64("sheet_id").
        FieldInt64("user_id").
        FieldTime("reserved_at").
        FieldTime("canceled_at")
}

type ReservationSlice []*Reservation

func (r *ReservationSlice) DecodeRapidash(decoder rapidash.Decoder) error {
    *r = make(ReservationSlice, decoder.Len())
    for i := 0; i < decoder.Len(); i++ {
        decoder := decoder.At(i)
        (*r)[i] = &Reservation{
            ID:         decoder.Int64("id"),
            EventID:    decoder.Int64("event_id"),
            SheetID:    decoder.Int64("sheet_id"),
            UserID:     decoder.Int64("user_id"),
            ReservedAt: decoder.TimePtr("reserved_at"),
            CanceledAt: decoder.TimePtr("canceled_at"),
        }
    }
    return decoder.Error()
}

3.CRUD操作をRapidash経由で行う

Marshaler などを実装したのでRapidash経由でCRUD操作を行うことができるようになりました。ここからはクエリを叩いている箇所をRapidash 経由で行うように変更を加えていきます。

3.1 複雑なクエリをシンプルにする

Rapidash は Eq や In を使ったシンプルなクエリのみをキャッシュ対象としています。

そのため、JOIN や GROUP BY といったクエリをシンプルなクエリへ置き換えた上で、アプリケーションコード側で同様の処理を実装する必要があります。

e.x

// original query
SELECT r.*, s.rank AS sheet_rank, s.num AS sheet_num, s.price AS sheet_price, e.price AS event_price FROM reservations r INNER JOIN sheets s ON s.id = r.sheet_id INNER JOIN events e ON e.id = r.event_id WHERE r.event_id = ? ORDER BY reserved_at ASC

// replace simple query
SELECT * FROM reservations WHERE event_id = ? ORDER BY reserved_at ASC
SELECT * FROM events WHERE id = ?
SELECT * FROM sheets WHERE sheet_id IN (?,?......)

3.2 該当コードを置き換える

ここまで行えば、あとはCRUD操作を行なっているコードを実際に置き換えていくのみになります。
Rapidash 経由でのCRUD操作は次のような流れになります。

Begin して Tx を作成する
QueryBuilderを用いてQueryを作成する
Tx と Queryを用いてCRUD操作を行う
Commit(もしくはRollback)する

トランザクションを発行したい場合は、あらかじめ DB 用のコネクション側でトランザクションを発行する必要があります。
たとえば package database/sql を用いる場合は db.Begin() で手に入る *Tx を rapidash.Begin(tx) のように渡すようにしてください。

下記は/admin/api/reports/events/:id/sales というAPI で行なっていたRead 処理を置き換えたコードになります

before

rows, err := db.Query("SELECT r.*, s.rank AS sheet_rank, s.num AS sheet_num, s.price AS sheet_price, e.price AS event_price FROM reservations r INNER JOIN sheets s ON s.id = r.sheet_id INNER JOIN events e ON e.id = r.event_id WHERE r.event_id = ? ORDER BY reserved_at ASC FOR UPDATE", event.ID)
if err != nil {
    return err
}
defer rows.Close()

var reports []Report
for rows.Next() {
    var reservation Reservation
    var sheet Sheet
    if err := rows.Scan(&reservation.ID, &reservation.EventID, &reservation.SheetID, &reservation.UserID, &reservation.ReservedAt, &reservation.CanceledAt, &sheet.Rank, &sheet.Num, &sheet.Price, &event.Price); err != nil {
        return err
    }
    report := Report{
        ReservationID: reservation.ID,
        EventID:       event.ID,
        Rank:          sheet.Rank,
        Num:           sheet.Num,
        UserID:        reservation.UserID,
        SoldAt:        reservation.ReservedAt.Format("2006-01-02T15:04:05.000000Z"),
        Price:         event.Price + sheet.Price,
    }
    if reservation.CanceledAt != nil {
        report.CanceledAt = reservation.CanceledAt.Format("2006-01-02T15:04:05.000000Z")
    }
    reports = append(reports, report)
}

after

// CRUD操作するためのTxオブジェクトの発行
cacheTx, err := cache.Begin(db)
if err != nil {
    return err
}
/** ※トランザクションを扱いたい場合
tx, err := db.Begin()
if err != nil {
    return err
}
cacheTx, err := cache.Begin(tx)
if err != nil {
    return err
}
*/
defer func() {
    if err := cacheTx.RollbackUnlessCommitted(); err != nil {
        log.Println(err)
    }
}()
var reservations ReservationSlice
// QueryBuilderを用いてクエリを作成し、Tx経由でreservationsへFindする
if err := cacheTx.FindByQueryBuilder(rapidash.NewQueryBuilder("reservations").Eq("event_id", event.ID).OrderAsc("reserved_at"), &reservations); err != nil {
    return err
}

var sheets SheetSlice
if err := cacheTx.FindByQueryBuilder(rapidash.NewQueryBuilder("sheets").In("id", reservations.SheetIDs()), &sheets); err != nil {
    return err
}
sheetMap := sheets.GroupByID()

var reports []Report
for _, reservation := range reservations {
    sheet := sheetMap[reservation.SheetID]
    report := Report{
        ReservationID: reservation.ID,
        EventID:       event.ID,
        Rank:          sheet.Rank,
        Num:           sheet.Num,
        UserID:        reservation.UserID,
        SoldAt:        reservation.ReservedAt.Format("2006-01-02T15:04:05.000000Z"),
        Price:         event.Price + sheet.Price,
    }
    if reservation.CanceledAt != nil {
        report.CanceledAt = reservation.CanceledAt.Format("2006-01-02T15:04:05.000000Z")
    }
    reports = append(reports, report)
}
// Commitしてキャッシュを更新する
// この時, rapidash.Begin(tx)のように*sql.Tx を渡していた場合は,
// TransactionのCommitも行われる(Rollbackも同様にRapidashが管理する)
if err := cacheTx.Commit(); err != nil {
    return err
}

4. 事前キャッシュを作るようにする

より効果的にキャッシュを用いるために、SLCに乗せるテーブルに対してアプリケーション上で使用されているクエリを叩いて事前にキャッシュを作るようにします。
これによってAPIが叩かれる際にはすでにキャッシュがある状態になるため、たとえ最初のAPIアクセスでもキャッシュが効くようになります。

本来は全てのSLCにのるテーブルに対して行う方が効果的なはずですが、 /initialize の制約上、一旦ここでは users に対して行うようにしました。

下のコードは、 users に対して事前にキャッシュを作るようなコードの一例です。

cacheTx, err := cache.Begin(db)
if err != nil {
    return err
}
defer func() {
    cacheTx.RollbackUnlessCommitted()
}()
warmUpUser := func() error {
    rows, err := db.Query("SELECT id, login_name FROM users")
    if err != nil {
        return err
    }
    defer rows.Close()
    for rows.Next() {
        var user User
        if err := rows.Scan(&user.ID, &user.LoginName); err != nil {
            return err
        }
        if err := cacheTx.FindByQueryBuilder(rapidash.NewQueryBuilder("users").Eq("id", user.ID), &user); err != nil {
            return err
        }
        if err := cacheTx.FindByQueryBuilder(rapidash.NewQueryBuilder("users").Eq("login_name", user.LoginName), &user); err != nil {
            return err
        }
    }
    return nil
if err := warmUpUser(); err != nil {
    return err
}
if err := cacheTx.Commit(); err != nil {
    return err
}

もう一度ベンチマークを測る

Rapidash を適用した状態になりました。もう一度ベンチマークを計測し、最初に計測した基準値と比較します。
5回ほど計測してそれぞれ 7027, 6645, 7380, 6489, 6951 でした。

今回は6951 の時のスコアの詳細を見てみます。
全体的にスコアは良くなっていますが、特に get のスコアが大きく伸びていることがわかります。

[  info ] [isu8q-bench] 2019/08/26 17:56:03.539927 bench.go:510: get 5380
[  info ] [isu8q-bench] 2019/08/26 17:56:03.540841 bench.go:511: post 1440
[  info ] [isu8q-bench] 2019/08/26 17:56:03.540861 bench.go:512: delete 71
[  info ] [isu8q-bench] 2019/08/26 17:56:03.540872 bench.go:513: static 4180
[  info ] [isu8q-bench] 2019/08/26 17:56:03.540881 bench.go:514: top 279
[  info ] [isu8q-bench] 2019/08/26 17:56:03.540890 bench.go:515: reserve 124
[  info ] [isu8q-bench] 2019/08/26 17:56:03.540898 bench.go:516: cancel 71
[  info ] [isu8q-bench] 2019/08/26 17:56:03.540906 bench.go:517: get_event 332
[  info ] [isu8q-bench] 2019/08/26 17:56:03.540915 bench.go:518: score 6951

さいごに

今回は、ISUCON8 予選で出題された課題を用いて、 Rapidash の適用とベンチマーク測定を行いました。

やはりボトルネックに対して修正を適切に行わなければいけないことを実感しつつ、それでもボトルネックを解消せずに Rapidash を適用するだけである程度のスコアの上昇がみられました。

実際に予選開催時に使用された計測マシンとはスペックは違うため単純な予選の結果とは比較はできませんが、get が大きく上昇したということで負荷分散に対してポジティブな結果になりました。

またキャッシュを使用するということは負荷などに対して効果的な反面、非常にバグを起こしやすい部分でもあります。
キャッシュを使用するために Rapidash がユーザに求めることは、あらかじめ定められた振る舞いを実装するのみと非常にシンプルです。ボイラープレートの記述で手軽にキャッシュを扱えるようになる点も大きなメリットだと考えています。

今回の改修を加えたアプリケーションコードはこちらにあります。
この記事が皆様のRapidash を使用するモチベーションや実装の足がかりになれば幸いです。

GoのキャッシュライブラリRapidashをISUCON問題で試す

はじめに

計測環境など

使用したマシン

ミドルウェア

ファーストベンチマークを測る

問題に使用されているクエリとテーブルを知る

Tables

SELECT

users

reservations

events

sheets

administrators

others

INSERT

users

reservations

events

UPDATE

reservations

events

DELETE

どのコンポーネントにキャッシュするのか決定する

FirstLevelCache(FLC)

SecondLevelCache(SLC)

Rapidashを適用する

1. Indexをはる

2. Marshaler/Unmarshaler/Struct を実装する

3.CRUD操作をRapidash経由で行う

3.1 複雑なクエリをシンプルにする

3.2 該当コードを置き換える

before

after

4. 事前キャッシュを作るようにする

もう一度ベンチマークを測る

さいごに