Japan 公式ブログ
Google の企業向けソリューションに関する公式な情報やユーザーの事例などを、いち早く皆さんにお届けします。
Cloud Datastore を用い、大規模ゲームでのランキング処理を 1 時間から 5 秒に短縮
2014年9月8日月曜日
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
#GoogleCloudSummit
#GoogleNext18
#GoogleNext19
77 min Lunch
add on
admin
Advanced Solutions Lab
AI
AI Hub
AI Platform
Android
Anthos
API
App Engine
App Maker
apps
Apps script
ASL
atmosphere
Atmosphere Tokyo
AutoML
AutoML Natural Language
AutoML Translation
bigquery
Box
Calendar
Case Study
Chorme OS
Chrome
Chrome Enterprise
Chrome Enterprise 導入事例
Chrome for Work
Chrome ウェブストア
chromebook
chromebooks
Chromebooks for Education
Chromebooks for meeting
Chromebooks for Work
Chromebox
Chromebox for digital signage
Chromebox for meetings
Chronicle
Cisco
Cloud
Cloud Armor
Cloud AutoML
Cloud AutoML Natural Language
Cloud AutoML Translation
Cloud AutoML Vision
cloud connect
Cloud Dataflow
Cloud Identity
Cloud IoT Core
Cloud Load Balancing
Cloud Memorystore for Redis
Cloud monitoring
Cloud OnAir
Cloud Pub/Sub
Cloud Ranking
Cloud Services Platform
Cloud Storage
Cloud TPU
compliance
compute engine
Contact Center AI
Container Engine
Coursera
Deloitte
developers
Dialogflow Enterprise Edition
Drive for Work
Dropbox
earth api
Education
enterprise
Enterprise Japan
event
Evernote
Expo
Firebase
FISC
Forrester
G Suite
G Suite Business
G Suite for Education
G Suite 事例
G Suite 導入事例
G+
gadget
GAE
GCE
GCP
GCP 導入事例
GCP 認定資格チャレンジ
GDPR
GEO
GEP
GfWtips
GKE
gmail
Gmail、新機能
Gone Google
GoneGoogle
Google App Engine
Google Apps
Google Apps Blog
Google Apps for Education
Google Apps for Work
Google Apps Script
Google Apps ユーザー事例
Google Apps 導入事例
Google atmosphere
Google calendar
Google calender
Google classroom
Google Cloud
Google Cloud Certification
Google Cloud Next '18 in Tokyo
Google Cloud Next '19 in Tokyo
google cloud platform
Google Cloud Search
Google Cloud Summit '18
Google Cloud 認定資格チャレンジ
Google Commerce Search
Google Derive
Google Docs
Google Docs API
google drive
Google Drive for Work
Google Earth
google enterprise
Google Enterprise Day
Google for Education
Google for Work
Google form
Google hang-out
Google hung-out
google map
Google maps
google maps api
google maps api premier
Google Maps APIs
Google Maps for Work
Google Maps Platform
Google Message Continuity
google search appliance
Google Shopping
Google Sites
Google Springboard
Google Storage for Developers
Google Video
Google Wave
Google スライド
Google ドキュメント
Google ドライブ
Google フォーム
Google マップ
Google+
GoogleApps
GoogleApps、新機能、spreadsheets
groups
gsa
Hangouts Meet
healthcare
Hybrid Cloud Platform for Google Cloud
Inbox
INSIDE
iOS
iphone
ISAE 3402 Type II
ISO 27018
IT
Jamboard
japan
Kubeflow Pipelines
Looker
Lotus Notes
Machine learning
map
maps api
Maps 導入事例
Maps-sensei
Mapsコーナー
media
microsoft office
migration
mobile
new features
Next
Next Tokyo
OAuth
Office 365
Office of the CTO
Osaka
partner
Partner Interconnect
partner program
Partner Summit
postini
pricing
Qwiklabs
region
research
RSA
SAP
SAS70
search
Security
Security Key
seminar
Shizuoka
Signage
Sites
SMB
SSAE 16 Type II
startup
Status Dashboard
TensorFlow
Trial
Upload any files
vault
Veolia
Viacom
Virtual Conference
VMware
あっぷす先生
あっぷす先生 誤解をとく!
あっぷす先生会社訪問
イベント
インフラストラクチャ
おしえて!あっぷす先生
おしえて!くらうど先生
オフライン
クラウド
くらうど先生
サイネージ
サポート
セキュリティ
チームドライブ
チェンジマネジメント
デジタル トランスフォーメーション
テレワーク
パートナー
ハングアウト
プライバシー
まっぷす先生
ランキング
リージョン
ワークインサイト
円周率
海底ケーブル
企業検索
機械学習
互換性
事例
小売
新機能
働き方
認定資格
Archive
2019
8月
7月
6月
5月
4月
3月
2月
1月
2018
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
1月
2017
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
1月
2016
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
1月
2015
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
1月
2014
12月
11月
10月
9月
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月
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 @googlecloud_jp
Useful Links
G Suite
Google Cloud Platform
Google 検索アプライアンス
Google Maps
G Suite 公式アップデート情報
0 件のコメント :
コメントを投稿