Japan 公式ブログ
Google の企業向けソリューションに関する公式な情報やユーザーの事例などを、いち早く皆さんにお届けします。
Cloud Datastore を用い、大規模ゲームでのランキング処理を 1 時間から 5 秒に短縮
2014年9月7日日曜日
Google for Work、 Cloud Platform GBU ソリューションアーキテクト 佐藤一憲
本記事は
Google Cloud Platform サイト
向けのソリューション ペーパーとして筆者が執筆し先日公開された「
Fast and Reliable Ranking in Datastore
」を要約したものです。ジョブ アグリゲーションやタスク キューのシャーディングなどの設計パターンを適用して、Google App Engine におけるランキング処理時間を大幅に短縮する方法を紹介しています。
ランキング処理の難しさ
株式会社アプリボット
でリード エンジニアを務める鈴木智明氏は、多くの大規模なゲームサービスで直面する問題であるランキング処理に取り組んでいました。
株式会社アプリボットで App Engine リード エンジニアを務める鈴木氏
アプリボット制作の Legend of Cryptids は、2012 年 10 月にアップル社の北米
App Store ゲーム部門ランキング#1を記録
このケースでのランキング処理の要件は、以下の通りシンプルです。
ゲームには数 10 万のプレイヤーが参加している
プレイヤーが敵を倒すたびにスコアが増える。ピークで毎秒 300 件程度の更新が発生する
トップページ上に常に最新のプレイヤーランキングを表示したい
スケーラビリティやレスポンスの速さが求められないのであれば、ランキングの取得は難しくはありません。たとえば Cloud Datastore 上で以下のようなクエリを実行します。
SELECT count(*) FROM Players WHERE Score > プレイヤーのスコア
このクエリは、特定のプレイヤーよりスコアの高いプレイヤーをすべてカウントします。しかし、プレイヤーが数 10 万人を超える規模のゲームで、プレイヤーがトップページにアクセスするたびにこのようなクエリを毎回実行するのは現実的でしょうか? 鈴木氏はまずこの方法を試しましたが、レスポンスを得るのに数秒かかってしまいました。これでは遅すぎる上、実行コストも高く、プレイヤー数が増えるほど性能が落ちてしまいます。
もっとも簡単な方法は、全プレイヤーをスキャンすること
鈴木氏は Google App Engine の
Memcache
サービス(メモリ キャッシュ)でランキングデータを保持する方法も検討しました。しかし Memcache サービスはレスポンスはきわめて速いものの、あくまでキャッシュである以上データの永続性がなく、万が一の障害時やメンテナンス時にはデータが失われる可能性がつきまといます。
結局、鈴木氏はすべてのプレイヤーのスコアをスキャンしてランキングを算出するバッチ処理を 1 時間に 1 回実行する方法を選択しました。この方法では、表示されるランキングは最大で 1 時間前の内容となってしまいます。
O(log n) アルゴリズムを探す
上述のような単純なクエリを使う方法では、プレイヤーより高いスコアを持つすべてのプレイヤーをスキャンしなければなりません。このアルゴリズムの計算量は O(n) です。すなわち、クエリの実行時間はプレイヤー数の増加に比例して増加するため、スケーラビリティの高い方法とは言えません。今回の要件を満たすには、計算量が O(log n) になるような、プレイヤー数の増加が処理時間にあまり影響を及ぼさないアルゴリズムを探す必要があります。
コンピュータサイエンスの授業を受けたことがある方なら、二分木、赤黒木、B 木などのツリー アルゴリズムを用いることでデータの探索を O(log n) 時間で実行できること覚えているでしょう。ツリー アルゴリズムは、集約した値を個々のブランチ ノードに置くことにより、ノードの数や最大値/最小値、平均値などの様々な集計にも応用できます。
この特性を利用して Google のエンジニアが Cloud Datastore 向けに実装したオープンソースのランキング処理ライブラリが、Google Code Jam Ranking Library です。Google Cloud Platform が提供する
プラチナサポートプログラム
に基づいて鈴木氏からの相談を受けた筆者は、鈴木氏のランキング問題を解決する手段としてこのライブラリの評価を行いました。
Google Code Jam Ranking Library を活用し、探索木でスコアランキングを取得
整合性確保と更新スループットのトレードオフ
しかし負荷テストを行う中で、筆者は
Google Code Jam Ranking Library
の問題点を発見しました。同ライブラリは、ツリーからランキング情報を取得する処理のレスポンスはたいへん速いものの、ツリーに対する更新処理のスループットがかなり低いことがわかったのです。負荷テストによる更新処理を毎秒 3 件より上げると、ライブラリはリトライ エラーを返すようになりました。この状況では、アプリボットの要件である毎秒 300 件の更新をこのライブラリで実現できないことは明らかでした。
なぜ毎秒 3 件程度の更新でリトライ エラーが発生するのでしょうか? その理由は、ツリーの整合性を維持するためにあります。Datastore では、複数行を更新するトランザクションにおいて強整合性(Strong Consistency)を確保する仕組みとして、エンティティ グループとよばれるメカニズムを提供しています(エンティティ グループについて詳しくはドキュメント「
Balancing Strong and Eventual Consistency with Google Cloud Datastore
」を参照してください)。Code Jam Ranking Library ではツリー全体を 1 つのエンティティ グループに収めることで、ツリーの整合性を確保する設計になっています。
しかし、エンティティ グループには性能に限界があります。Datastore ではすべてのデータを必ず 3 台以上のサーバーに同期書き込みして高い可用性と永続性を提供するため、加えて強整合性も保証するエンティティ グループについては、1 つにつき毎秒 1 件のトランザクションしか処理できません。もしこの 1 秒の間に同じエンティティ グループに対して他のトランザクションによる書き込みの競合が発生すると、後者の処理はキャンセルされてリトライエラーが発生します。この楽観的排他制御(optimistic concurrency)により、整合性を確保する仕組みです。
つまり Code Jam Ranking Library は、Datastore 上でツリーアルゴリズムを実装することで優れたレスポンスと高い整合性、可用性、永続性を提供するものの、更新処理のスループットはあまり高くないライブラリであることがわかりました。
Datastore チームの解決法:ジョブ アグリゲーション
こうした課題を背景に筆者が米国本社の Datastore チームに問題の解決方法についてアドバイスを求めたところ、同 チームからは「ジョブ アグリゲーション」パターン利用の提案がありました。
ジョブ アグリゲーションでは、多数の更新処理をひとつのトランザクションに集約し、単一のバッチ処理スレッドで実行します。エンティティ グループに同時アクセスするスレッドが 1 つしかないため、トランザクションの同時実行にともなうリトライ エラーやロック待ちは発生しません。そのため、データ構造の整合性を確保しながら高い更新スループットが得られます。ただしトレードオフとしてスレッド数が 1 つに制限されるため、スケーラビリティを際限なく高めることはできません。これと同様のアイデアは VoltDb や Redis のような他のストレージ製品にも見られます。
Datastore チームからのアドバイスに基づき、筆者はジョブ アグリゲーション パターンと Code Jam Ranking Library を組み合わせたサンプル コードを作成しました。App Engine の分散キューサービスである
Task Queue
を使用して複数の更新処理をタスクとしてキューに保存します。一方、バックエンドでは単一のスレッドで一回あたり最大 1000 件までのタスクをキューから取り出すバッチ処理を実行します。この複数の更新内容を Code Jam Ranking Library にまとめて渡し、全体を 1 つのトランザクションとして実行します。この仕組みにより、上述のようなリトライエラーは一切発生せずに、毎秒 1 件をケタ違いに上回る更新処理が可能になります。
下記のグラフは、サンプルコードを用いた負荷テストの結果です。今回はキューのスループットの変動を最小限に抑えるため、キューのシャーディング(分散化)も組み込みました。最終的にアプリボットに提案したソリューションでは、数時間にわたり毎秒 300 件の更新を処理できることを確認しました。個々の更新内容は、リクエストを受けてから 5 秒程度で Datastore に反映されます。
サンプルコードの性能グラフ
結果的にこのソリューションでは、数 10 万人のプレイヤーを有するゲームサイト上で、毎秒 300 件ほどのスコア更新処理を扱いながら、高い整合性と可用性、永続性を備えたランキング処理を 5 秒ほどの遅延で実行するという要件に応える実装を提案できました。またここで紹介したジョブ アグリゲーション パターン以外にも、線形補間等のアプローチによるいくつかのソリューションも合わせて提案しています。その詳細については「Fast and Reliable Ranking in Datastore」をご覧ください。
注記
本記事で公開されている性能数値は参考用のサンプル値であり、App Engine、Datastore、または他のサービスの絶対性能を保証するものではありません。
0 件のコメント :
コメントを投稿
Labels
77 min Lunch
add on
admin
Android
API
App Engine
apps
atmosphere
Atmosphere Tokyo
bigquery
Case Study
Chorme OS
Chrome for Work
Chrome ウェブストア
chromebook
chromebooks
Chromebooks for Education
Chromebooks for meeting
Chromebooks for Work
Chromebox for digital signage
Chromebox for meetings
Cloud
cloud connect
Cloud monitoring
Cloud Ranking
compliance
compute engine
Deloitte
developers
Drive for Work
earth api
Education
enterprise
Enterprise Japan
event
Firebase
G+
gadget
GAE
GCE
GCP
GEO
GEP
GfWtips
GKE
gmail
Gmail、新機能
Gone Google
GoneGoogle
Google App Engine
Google Apps
Google Apps Blog
Google Apps for Work
Google Apps Script
Google Apps ユーザー事例
Google atmosphere
Google calendar
Google calender
Google classroom
google cloud platform
Google Commerce Search
Google Derive
Google Docs
google drive
Google Drive for Work
google enterprise
Google Enterprise Day
Google for Work
Google form
Google hang-out
Google hung-out
google map
Google maps
google maps api
google maps api premier
Google Message Continuity
google search appliance
Google Shopping
Google Sites
Google Storage for Developers
Google Video
Google Wave
Google スライド
Google ドキュメント
Google フォーム
GoogleApps
GoogleApps、ユーザ事例
GoogleApps、新機能、spreadsheets
groups
gsa
healthcare
iOS
iphone
ISAE 3402 Type II
ISO 27018
IT
japan
Lotus Notes
map
maps api
media
microsoft office
migration
mobile
new features
Office 365
partner
partner program
postini
pricing
research
RSA
SAS70
search
Security
seminar
Shizuoka
Signage
Sites
SMB
SSAE 16 Type II
SSO
startup
Status Dashboard
Trial
Upload any files
vault
Virtual Conference
VMware
あっぷす先生
あっぷす先生 誤解をとく!
あっぷす先生会社訪問
イベント
おしえて!あっぷす先生
オフライン
クラウド
サイネージ
サポート
テレワーク
ハングアウト
プライバシー
ランキング
企業検索
互換性
事例
新機能
働き方
Archive
2016
2月
1月
2015
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
1月
2014
12月
11月
10月
9月
Google Drive for Education 発表!21世紀は、重い鞄のかわりに Drive を
#77minLunch 株式会社TIME VIZ
長谷川ホールディングスもGoogleへ Google Apps for Work を採用し、フランチ...
株式会社トップゲート、日本国内のサードベンダーで初めて Google Cloud Platform ...
「 Google for Work マル秘活用術」 スケジュール調整を効率化
国分も Google へ! 営業力の強化とスピード経営をめざし Google Apps for Wo...
#77minLunch freee 株式会社
Sony Music、 Google Cloud Platform を用い、YouTube 至上最...
#77minLunch 株式会社AOI Pro.
Google Apps Marketplace 管理者そして一般ユーザも設定可能に
「 Google for Work マル秘活用術」 本当に「使える」議事録作成
Google for Work キャンペーン第二弾、Google for Work の活用術をご紹介...
Google for Work キャンペーン第一弾、ちょっとゆったりしたランチ 77 min Lun...
iPhone, iPad 用の新しいアプリで、Google ドキュメント、 スプレッドシート 、プレ...
Cloud Datastore を用い、大規模ゲームでのランキング処理を 1 時間から 5 秒に短縮
ワークスタイル・イノベーションが始まっています。
Google Enterprise から Google for Work へ
Google BigQuery を使って歴史事象パターンの関連を探しだす
Google Compute Engine がアップデートされました!
8月
7月
6月
5月
4月
3月
2月
1月
2013
12月
11月
10月
9月
7月
6月
5月
4月
3月
1月
2012
12月
11月
10月
9月
8月
7月
6月
5月
4月
2月
2011
12月
10月
9月
8月
7月
5月
4月
2月
1月
2010
12月
11月
10月
9月
7月
6月
5月
3月
2月
1月
2009
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
1月
2008
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
2007
12月
Feed
Follow @GoogleforWorkJa
Useful Links
Google Apps for Work
Google Cloud Platform
Google 検索アプライアンス
Google Maps for Work
企業向けソリューション
Google Apps公式アップデート情報
0 件のコメント :
コメントを投稿