Google Cloud Platform Japan Blog
最新情報や使い方、チュートリアル、国内外の事例やイベントについてお伝えします。
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 件のコメント :
コメントを投稿
12 か月間のトライアル
300 ドル相当が無料になるトライアルで、あらゆる GCP プロダクトをお試しいただけます。
Labels
.NET
.NET Core
.NET Core ランタイム
.NET Foundation
#gc_inside
#gc-inside
#GoogleCloudSummit
#GoogleNext18
#GoogleNext19
#inevitableja
Access Management
Access Transparency
Advanced Solutions Lab
AI
AI Hub
AlphaGo
Ansible
Anthos
Anvato
Apache Beam
Apache Maven
Apache Spark
API
Apigee
APIs Explore
App Engine
App Engine Flex
App Engine flexible
AppArmor
AppEngine
AppScale
AprilFool
AR
Artifactory
ASL
ASP.NET
ASP.NET Core
Attunity
AutoML Vision
AWS
Big Data
Big Data NoSQL
BigQuery
BigQuery Data Transfer Service
BigQuery GIS
Billing Alerts
Bime by Zendesk
Bitbucket
Borg
BOSH Google CPI
Bower
bq_sushi
BreezoMeter
BYOSL
Capacitor
Chromium OS
Client Libraries
Cloud API
Cloud Armor
Cloud Audit Logging
Cloud AutoML
Cloud Bigtable
Cloud Billing Catalog API
Cloud Billing reports
Cloud CDN
Cloud Client Libraries
Cloud Console
Cloud Consoleアプリ
Cloud Container Builder
Cloud Dataflow
Cloud Dataflow SDK
Cloud Datalab
Cloud Dataprep
Cloud Dataproc
Cloud Datastore
Cloud Debugger
Cloud Deployment Manager
Cloud Endpoints
Cloud Firestore
Cloud Foundry
Cloud Foundry Foundation
Cloud Functions
Cloud Healthcare API
Cloud HSM
Cloud IAM
Cloud IAP
Cloud Identity
Cloud IoT Core
Cloud Jobs API
Cloud KMS
Cloud Launcher
Cloud Load Balancing
Cloud Machine Learning
Cloud Memorystore
Cloud Memorystore for Redis
Cloud monitoring
Cloud NAT
Cloud Natural Language API
Cloud Networking
Cloud OnAir
Cloud OnBoard
cloud Pub/Sub
Cloud Resource Manager
Cloud Resource Manager API
Cloud SCC
Cloud SDK
Cloud SDK for Windows
Cloud Security Command Center
Cloud Services Platform
Cloud Source Repositories
Cloud Spanner
Cloud Speech API
Cloud Speech-to-Text
Cloud SQL
Cloud Storage
Cloud Storage FUSE
Cloud Tools for PowerShell
Cloud Tools PowerShell
Cloud TPU
Cloud Translation
Cloud Translation API
Cloud Virtual Network
Cloud Vision
Cloud VPC
CloudBerry Backup
CloudBerry Lab
CloudConnect
CloudEndure
Cloudflare
Cloudian
CloudML
Cluster Federation
Codefresh
Codelabs
Cohesity
Coldline
Colossus
Compute Engine
Compute user Accounts
Container Engine
Container Registry
Container-Optimized OS
Container-VM Image
Couchbase
Coursera
CRE
CSEK
Customer Reliability Engineering
Data Studio
Databases
Dbvisit
DDoS
Debugger
Dedicated Interconnect
deep learning
Deployment Manager
Developer Console
Developers
DevOps
Dialogflow
Disney
DLP API
Docker
Dockerfile
Drain
Dreamel
Eclipse
Eclipse Orion
Education Grants
Elasticsearch
Elastifile
Energy Sciences Network
Error Reporting
ESNet
Evernote
FASTER
Fastly
Firebase
Firebase Analytics
Firebase Authentication
Flexible Environment
Forseti Security
G Suite
Gartner
gcloud
GCP
GCP Census
GCP 移行ガイド
GCP 認定資格チャレンジ
GCPUG
GCP導入事例
gcsfuse
GEO
GitHub
GitLab
GKE
Go
Go 言語
Google App Engine
Google Apps
Google Certified Professional - Data Engineer
Google Cloud
Google Cloud Certification Program
Google Cloud Client Libraries
Google Cloud Console
Google Cloud Dataflow
Google Cloud Datalab
Google Cloud Datastore
Google Cloud Endpoints
Google Cloud Explorer
Google Cloud Identity and Access Management
Google Cloud INSIDE
Google Cloud INSIDE Digital
Google Cloud INSIDE FinTech
Google Cloud Interconnect
Google Cloud Launcher
Google Cloud Logging
Google Cloud Next '18 in Tokyo
Google Cloud Next '19 in Tokyo
Google Cloud Platform
Google Cloud Resource Manager
Google Cloud Security Scanner
Google Cloud Shell
Google Cloud SQL
Google Cloud Storage
Google Cloud Storage Nearline
Google Cloud Summit '18
Google Cloud Summit ’18
Google Cloud Tools for IntelliJ
Google Code
Google Compute Engine
Google Container Engine
Google Data Analytics
Google Data Studio
Google Date Studio
Google Deployment Manager
Google Drive
Google Earth Engine
Google Genomics
Google Kubernetes Engine
Google maps
google maps api
Google Maps APIs
Google Maps Platform
Google SafeSearch
Google Service Control
Google Sheets
Google Slides
Google Translate
Google Trust Services
Google VPC
Google マップ
Google 公認プロフェッショナル
GoogleNext18
GPU
Gradle
Grafeas
GroupBy
gRPC
HA / DR
Haskell
HEPCloud
HIPAA
Horizon
HTCondor
IaaS
IAM
IBM
IBM POWER9
icon
IERS
Improbable
INEVITABLE ja night
inevitableja
InShorts
Intel
IntelliJ
Internal Load Balancing
Internet2
IoT
Issue Tracker
Java
Jenkins
JFrog
JFrog Artifactory SaaS
Jupiter
Jupyter
Kaggle
Kayenta
Khan Academy
Knative
Komprise
kubefed
Kubeflow Pipelines
Kubernetes
KVM
Landsat
load shedding
Local SSD
Logging
Looker
Machine Learning
Magenta
Managed Instance Group
Managed Instance Group Updater
Maps API
Maps-sensei
Mapsコーナー
Maven
Maxon Cinema 4D
MightyTV
Mission Control
MongoDB
MQTT
Multiplay
MySQL
Nearline
Network Time Protocol
Networking
neural networks
Next
Node
NoSQL
NTP
NuGet パッケージ
OCP
OLDISM
Open Compute Project
OpenCAPI
OpenCAPI Consortium
OpenShift Dedicated
Orbitera
Organization
Orion
Osaka
Paas
Panda
Particle
Partner Interconnect
Percona
Pete's Dragon
Pivotal
Pivotal Cloud Foundry
PLCN
Podcast
Pokemon GO
Pokémon GO
Poseidon
Postgre
PowerPoint
PowerShell
Professional Cloud Network Engineer
Protocol Buffers
Puppet
Pythian
Python
Qwiklabs
Rails
Raspberry Pi
Red Hat
Redis
Regional Managed Instance Groups
Ruby
Rust
SAP
SAP Cloud Platform
SC16
ScaleArc
Secure LDAP
Security & Identity
Sentinel-2
Service Broker
Serving Websites
Shared VPC
SideFX Houdini
SIGOPS Hall of Fame Award
Sinatra
Site Reliability Engineering
Skaffold
SLA
Slack
SLI
SLO
Slurm
Snap
Spaceknow
SpatialOS
Spinnaker
Spring
SQL Server
SRE
SSL policies
Stack Overflow
Stackdriver
Stackdriver Agent
Stackdriver APM
Stackdriver Debugger
Stackdriver Diagnostics
Stackdriver Error Reporting
Stackdriver Logging
Stackdriver Monitoring
Stackdriver Trace
Stanford
Startups
StatefulSets
Storage & Databases
StorReduce
Streak
Sureline
Sysbench
Tableau
Talend
Tensor Flow
Tensor Processing Unit
TensorFlow
Terraform
The Carousel
TPU
Trace
Transfer Appliance
Transfer Service
Translate API
Uber
Velostrata
Veritas
Video Intelligence API
Vision API
Visual Studio
Visualization
Vitess
VM
VM Image
VPC Flow Logs
VR
VSS
Waze
Weave Cloud
Web Risk AP
Webyog
Wide and Deep
Windows Server
Windows ワークロード
Wix
Worlds Adrift
Xplenty
Yellowfin
YouTube
Zaius
Zaius P9 Server
Zipkin
ZYNC Render
アーキテクチャ図
イベント
エラーバジェット
エンティティ
オンライン教育
クラウド アーキテクト
クラウド移行
グローバル ネットワーク
ゲーム
コードラボ
コミュニティ
コンテスト
コンピューティング
サーバーレス
サービス アカウント
サポート
ジッター
ショート動画シリーズ
スタートガイド
ストレージ
セキュリティ
セミナー
ソリューション ガイド
ソリューション: メディア
データ エンジニア
データセンター
デベロッパー
パートナーシップ
ビッグデータ
ファジング
プリエンプティブル GPU
プリエンプティブル VM
フルマネージド
ヘルスケア
ホワイトペーパー
マイクロサービス
まっぷす先生
マルチクラウド
リージョン
ロード シェディング
運用管理
可用性
海底ケーブル
機械学習
金融
継続的デリバリ
月刊ニュース
資格、認定
新機能、アップデート
深層学習
深層強化学習
人気記事ランキング
内部負荷分散
認定試験
認定資格
料金
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月
6月
5月
4月
3月
2月
Feed
月刊ニュースレターに
登録
新着ポストをメールで受け取る
Follow @GoogleCloud_jp
0 件のコメント :
コメントを投稿