食べログの予約システムで起きた100bit問題に立ち向かう

はじめに

初めまして。食べログ飲食店システム開発部でマネージャーをしている井本と申します。2016年に入社し、様々なチームを経てから現在はインターネット予約に関連する機能を主管とする予約サービスチームにいます。この記事では2022年にリリースしたオンライン台帳の「食べログノート」で起きた問題と、その解決に至るまでにやってきたことを紹介します。

食べログノートリリース直後に発覚した在庫の100bit問題

食べログノートは2022にリリースしたオンライン予約台帳サービスです。実店舗の座席配置や運用実態により近い形でオンライン管理でき、かつ直感的に操作できるサービスとして日々改良を続けております。現在は利用店舗数も着実に増加しつつありますが、リリース当初に大きな問題が発覚しました。

当時食べログノートをリリースしたばかりで、一部店舗様のご協力を得て数店舗に試験導入している段階でした。リリースが完了して残存していた課題や不具合を取り除きつつあった頃、予約在庫の在庫サマリ計算という処理において特定の店舗の処理が異常に遅いことに気づきました。この遅い処理の原因を調査した結果、この問題を我々は「予約在庫の100bit問題」と呼称することにしました。

ここで出てきた「予約在庫」「在庫サマリ計算」「予約在庫の100bit問題」について次項から順を追って説明していきます。

予約在庫とは

予約在庫とは、店舗が予約できる席を設定している日時のことを指します。予約の在庫は以下の要素で成り立っています。

在庫３要素

営業時間

図の青い丸は営業時間となります。店舗の営業時間をはじめ、定休日やランチとディナーの間の昼休憩もあります。普段の営業時間と違い特別な営業時間や定休の日もあります。これらの設定を組み合わせてできる日時が在庫の要素となります。

コース

図の紫色の丸はコース及び席のみ予約の設定を要素としています。お店は準備に時間を要したり一度に用意できる人数が決まってきます。それらを表現するために利用人数や開始時間を制限する設定が存在しています。

卓

赤の丸はお店に存在する卓です。食べログノートの場合、卓は同じ種類のテーブルが２つあるとしたら卓は合計２卓ということになります。大型の店舗の場合は卓数が３桁になることもあります。

これら３つの要素で予約できる日時を算出し、最終的に論理積で導き出したものが「予約在庫」になります。

ネット予約に関しては以前 @aaknsk さんに、食べログのネット予約システムを紹介いただいているので合わせてご覧ください。 https://tech-blog.tabelog.com/entry/advent-calendar-20221216

在庫サマリ計算とは

在庫サマリ計算とは、前述の予約在庫をサマリー（まとめ）したもので、在庫サマリと呼んでいます。１店舗に対して日ごとに予約できる時間を人数分データとして保持しています。

在庫計算

在庫のデータ構造

食べログでの予約は15分刻みで予約可能です。 15分を1コマとすると、1時間で4コマ。これを1日分の長さで表すと 24×4 = 96コマです。

2進数だと以下のように表すことができます。

# 全部で96桁
"000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"

左端は1日の予約の始まりの時間午前6:00、右端は翌日の5:45 となっています。これを分かりやすく1時間ごとにスペースで区切ってみます。

# 1時間ごとに文字を区切り、横に時間を入れる
"0000(6:00) 0000(7:00) 0000 0000 0000 0000 0000(12:00) 0000 0000 0000 0000 0000 0000(18:00) 0000 0000 0000 0000 0000 0000(24:00) 0000 0000 0000 0000 0000"

より分かりやすく横に時間を添えました。では、17:00〜19:00が予約で埋まっていることを表現してみます。

# 17:00 〜 19:00が埋まっている状態にする
"0000(6:00) 0000(7:00) 0000 0000 0000 0000 0000(12:00) 0000 0000 0000 0000 1111 1111(18:00) 1111 0000 0000 0000 0000 0000(24:00) 0000 0000 0000 0000 0000"

文字列に戻すと以下のようになります。

# 17:00 〜 19:00が埋まっている状態にする
"00000000000000000000000000000000000000000000111111111111000000000000000000000000 0000000000000000"

営業時間、コース、卓の全ての条件を入れ、最終的に出てきたものを「予約在庫サマリ」と呼んでいます。予約在庫サマリは１店舗に対して3ヶ月分を保持しています。この予約在庫の計算が当社の予約システムのコア機能となります。設定項目が複雑であることやドメイン知識が必要なため、改修難易度が高い機能になっています。

100bit問題とは

前置きが長くなりましたが、今回の主題である100bit問題について話を進めていきます。

問題となった機能卓グループ機能

問題となった箇所は在庫の設定の1つ、卓グループという機能です。卓グループ機能は以下のような仕様を持っています。

複数の卓を接続しグルーピングできる。
宴会などの大人数席を作るなどの用途に利用できる。
予約が入った場合、設定した卓が全て抑えられるのではなく、予約人数に適した卓の組み合わせが埋まる。
卓同士の位置関係は考慮にいれない。
なるべく最小の卓数で収まるようにする（他の予約のために空ける）

特に３番目の仕様が重要です。

それでは例として下の画像の卓を卓グループにします。最大人数は受付人数の最大人数設定を加算した数となります。この場合、１つの卓の最大人数は4名なので 4×6=24名が最大人数となります。

卓グループ

ではこの卓グループで5名の予約を取ったとします。そうすると例としてこのような席のパターンが生まれます。

卓グループパターン１

卓グループパターン2

あくまでも２例ですが、このように組み合わせが卓の数分存在します。計算式にすると 6C2 となります。

[1,2,3,4,5,6].combination(2).size
=> 15

9名〜12名の３卓を選択する場合は２０通りです。

[1,2,3,4,5,6].combination(3).size
=> 20

6卓全ての組み合わせは63通りとなります。

total = 0
(1..10).to_a.each do |time|
  total += [1,2,3,4,5,6,7,8,9,10].combination(time).size
end

total
=> 63

このパターンの組み合わせと次の項目で説明する構造と重なり問題が発生します。

問題の原因となった構造

問題が発生したシステムの挙動

上記の仕様を見て「やばいな」と感じていただけたでしょうか。では、この状態でどのようにまずくなるのか見てみます。

先程の例では、６卓を接続するとパターンが全部で63通りになりました。

では10卓ではどうでしょうか？全てのパターンは 10の組み合わせ通り分存在します。

(1..10).to_a.each do |time|
  total += [1,2,3,4,5,6,7,8,9,10].combination(time).size
end

total
=> 1023

1023通りです。前述した様に、卓グループの登録時、あらかじめ組み合わせを保存しようとします。つまり卓グループの登録操作の際に1023行ものレコードがINSERTされます。問題はそのレコード数です。卓数を増やすごとにあっという間に増え続けます。

11卓 => 2047
12卓 => 4095
20卓 => 1048575

これは数値のビットパターン分あるということになります。 rubyで現すと以下の様になります。

(2**20).to_i - 1
=> 1048575

そしてこれを100卓で計算すると…

(2**100).to_i - 1
=> 1267650600228229401496703205375

126穣という途方もない数になってしまいます。この組み合わせINSERTを100ビットパターン分してしまう設計になっていた問題を 100bit問題 と呼称することにした、というのが経緯です。

発生した影響

タイムアウトの発生

まずMySQLサーバーのtransactionのタイムアウトが発生しました。確認すると、今回の卓グループのサブルールテーブルが対象ということが分かりました。

現象の再現性を確認

画面の操作がタイムアウトを起こす
- 卓を12卓以上にして卓グループを操作するとレスポンスが全く返らずにタイムアウトを起こすことがわかりました。この時DBでは何千行というレコードがINSERTやDELETEをしようとしていたためです。
バッチが詰まる
- バッチで定期的に動作させている前述の在庫サマリの更新処理が終わらなくなりました。通常遅くとも１時間で終わっていたものが６時間以上かかるようになりました。

これは卓グループの組み合わせを利用して在庫の計算処理をしていたため計算量も膨れ上がっていたためでした。バッチの更新に関しては卓グループとは関係ない店舗に影響を及ぼすため、早急な対応が必要となりました。

なぜ100bit問題が起きたか

普段の設計レビューの観点

普段テーブル設計のレビューでは以下の内容を確認しています。

新規テーブルがある場合、要件や仕様が合ったものになっているか
運用状態を考えた造りになっているか
拡張性やシステム全体での位置を考え、追加や改変することが適切か

当時の設計時、何を考えていたか

この当時に議論されていたことを振り返ってみました。

テーブル設計にフォーカスが当たりすぎた

既存のテーブルの仕組みに対し、どのように卓グループの構造を乗せるかの議論が中心に行われていました。運用状態のチェックについてはさほど行われていない状態でした。

設計のネガティブチェックよりも実現性に着目がいっていた

残っている資料を確認する限り、様々な角度から設計の正しさについて確認する時間よりもテーブルが存在することでのメリットの確認がされている状態でした。

何が問題だったか

状態を飛躍させてみることが必要だった

当初を振り返ると一番の理由はこちらにあると考えています。運用に適しているか考察する際、極端にデータが増えた場合や何年も運用した場合などを想像してチェックをしていくことが必要でした。普段の設計レビューで実施していることが、今回では足りていませんでした。

利用パターンをあらかじめ複数用意しておく必要があった

当時の資料では考えていた利用パターンが１パターンのみだったのも抜けた原因です。これが20卓30卓の場合はどうか、最大卓数の99卓ではどうかなどのパターン考慮が必要でした。

どう解決をしたか

タスクフォースチームの結成

チーム結成

運用を開始したばかりで既に対応する余力は残されておらず、手をこまねいていた状態でした。
そこに当時の部長が各方面に回って臨時ヘルプしてもらえる人を連れてきてくれました。
その人数は5人。こちらとしてはアベンジャーズか何かが駆けつけてきてくれた気分でした。
既存メンバー1名が入り計6名でのタスクフォースチーム結成です。
結成出来たのは立ち回ってもらったお陰ではありますが、ピンチの時に人的リソースを移動できる食べログエンジニア組織の強さも感じました。

チーム立ち上げ

チームを立ち上げる上で、まずは解決しなければならない課題を整理しました。

問題となった構造の解消
画面のレスポンス遅延解消
在庫計算の更新が全体的に詰まる部分の解消

そして出来たチーム編成は以下になります。

暫定対応チーム
- 既存のアルゴリズムや動きを読み解き、非効率な箇所を解消していくチーム
  - アルゴリズムを利用するアプリ部分の知識を有している必要があるので、すでに知見を持ったメンバーを配置した。
- メンバー: 1名
根本改善チーム
- IFを変えずに構造・アルゴリズムを変える対応をするチーム。データ設計から対応する。
- メンバー: 3名
並列化チーム
- 在庫サマリ更新を並列化する機構を作る。
  - 在庫サマリ並列化については 2022/12に公開された食べログのネット予約システムを支える技術要素のピックアップ技術の項目を参照してください
- メンバー: 2名

以下のことを考えながらチーム編成しました。

メンバーが元のプロジェクトに戻る時期を考慮
プロジェクトが進むと根本改善チームは一定の役目を終えると考え、統合することを予め予定に入れておく
事前にメンバーの上長などから聞いたメンバーのスキルセットなどから配置を考慮

タスクフォースチームで行った活動

チーム結成当初

チーム結成当初、通常のチーム受け入れで行う作業までは実施しておいてもらい、課題とその前後の知識のインプットを中心に行いました。課題はチーム毎に分け、それぞれのやることに集中してもらうような活動に限定しました。

デイリーでポイント毎に議論

各チーム毎にデイリーでMTGを開きました。進捗確認だけでなく、その時間を使って今現在考えていることをメンバーに展開してもらい議論を進めるようにしました。特に根本改善チームでは、構造やアルゴリズムの変更についての議論を重ねていたのでメンバーそれぞれで考えてきた結果をデイリーでマネージャー(自分) や部長を含めてマージしていく作業をしました。

同じ議題についてそれぞれ考える

同じ議題についてそれぞれ持ち帰って別々に考えて来てもらうことを多く行いました。共通の議題でもそれぞれ考え方のアプローチや結論が違っていたため、それをデイリーで集約してまた議題を作ることを繰り返しました。

コードチェック体系をチームで分散

コードチェックは大人数を加えて議論するより、今回はタスクフォースの各チーム内＋マネージャーのみで完結することにしました。

問題の卓グループ構造に対する解決の糸口の発見

既存の構造に置き換えるアルゴリズムを考える上で重要になったのは、「基本に立ち返る」ということでした。山の様に書かれたプログラムや問題のデータ構造から離れて考えついたキーワードは

飲み屋のお兄さんはなぜサクッと席を見つけられるのか？

でした。

このキーワードを元に議論を展開していきました。

飲み屋のお兄さんは席を見つける時に空いていない席は見ていない
入る人数にあった席を最初に決めている
- 8名なら一番近い5名様席から組み立ている
空いてる席以外のことは考えない
- 空いてる席を中心にアルゴリズムを組み立てれば工夫の余地がありそう

回を進めるごとになんとなく全員の頭の中でアルゴリズムのイメージを共有が合致してきたように感じました。

設計までの流れ

サンプルとなる「飲み屋のお兄さん」を基準に考えることで今のアルゴリズムの問題点が見えてきます。その後設計までに以下のような流れで進んできました。

飲み屋のお兄さんの動きを言語化しアルゴリズムを読み解く
既存のアルゴリズムとの比較
基準となるアルゴリズムの選定
様々なユースケースでのアルゴリズムの検証
データモデル設計
ライブラリ設計

この作業の流れの中では以下の点が良かった点です。

バラバラに考えてきた内容を集まってからマージしていくスピードが早かった
クラス設計の概念を決める上で「飲み屋のお兄さん」キーワードは迷った時に何度も立ち戻れる指標となった

修正計画と実行の実績

修正計画は以下のように設定しました。

本番ですでに稼働しているということから、慎重に修正を適用していくため並行稼働期間や部分リリースを設けることにした
メンバーが途中で育休に入る予定だったので8月以降チームを２つに統合した
最終的にチームに所属していたメンバーが最後の本番リリースまで面倒を見てもらう計画とした

スケジュール

問題解決の結果

並行稼働期間を長く取っていたため、実に７ヶ月間の時間を経て全ての工程が終了しました。今回のプロジェクトで得たことは次の通りです。

前提のドメイン知識が全くないメンバーでも問題の一部分にフォーカスを当てて考えてもらえば進めることができる
同じ内容を別々に考える時間を取っても照らし合わせる間隔を短くすれば知識や発見を共有できる
３ライン同時に動かしている際、お互いのラインの動向を共有するのが大変だった
メンバーがそれぞれこまめに情報をまとめてくれていたためそれが共有に役立った

大きく問題が起きたことで対処も大きなコストをかけることになりましたが、とてもいい教訓となりました。この場を借りて参加していただいた方、助言をいただいた方に感謝いたします。ありがとうございました。

今後の予約の世界

今後もインターネット予約事業は拡大していくと予想されるため、より多くの店舗でも在庫サマリ更新のような計算が耐えられる造りとより改変しやすい造りが必要となります。当社の予約システムは現在の状態を変えずに運用し続けるのではなく、可能な限り大きく改変させていこうと考えています。今回の記事を通して予約システムの複雑さを読み解きながら改修していく面白さが伝われば幸いです。少しでも興味を持っていただけたら、ぜひ以下の採用情報ページをたどってみてください。

WEBエンジニア (サービス開発担当)【食べログ】 | 株式会社カカクコム

https://hrmos.co