こんにちは。サーバーサイドエンジニアの佐藤です。
普段は長期運用タイトルにおいて、機能開発や開発の効率化を促進するツールやモジュールの開発を行っております。
今回は、担当するタイトルで行なった、Where句からキャッシュキーを生成、管理を可能とするモジュール開発についてお話させていただきます。
結論を先に申し上げますと、Where句をグラフ理論におけるN部グラフに置き換えることでモジュールの開発を容易にすることができました。
このモジュールによって、データベースのデータをキャッシュを利用して効率的かつ安全に取得できるようになっています。
背景
ゲームにおいて、マスターデータという全ユーザ共通のゲームの構成要素に関するデータが存在します。例えばキャラや武器、敵、アイテム、クエストといったもののデータになります。オンラインゲームにおいて、マスターデータは膨大で頻繁に利用されます。
多くの場合、マスターデータはデータベース（以下DB）に保存され、サーバーロジックのいたるところで取得されます。このデータを都度クエリを発行し取得することになるとDBへのアクセスは膨大となってしまいます。
コロプラでは、このようなデータ取得による負荷を抑えるため、DBから一度取得したデータはキャッシュに保存し、以降はキャッシュから取得することにより、DBアクセスの軽減と高速化を行っています。
このキャッシュにはサーバー単位でのキャッシュ機構であるAPC User キャッシュ（以下APCuキャッシュ）を用いており、DataMapperから利用しています。
DataMapperとは、データベースとデータのオブジェクト（以下データモデル）を分離するためのソフトウェアレイヤで、データ操作を実装するクラスになります。DataMapperの基底クラスからテーブルごとに派生クラスを作成し、クエリに対応するデータ取得メソッドを実装していました。
データ取得メソッド内でのキャッシュ処理もエンジニアが都度実装しておりましたが、これにより複数の問題が起きていました。
問題と方策
キャッシュを利用するデータ取得処理の実装に関連する問題は４つあります。これらについて整理し、あるべき姿について考えます。
キャッシュキー生成のヒューマンエラー
都度のキャッシュ処理実装により、ヒューマンエラーが多発していました。
イメージしやすいように具体例を紹介いたします。
まず「異なるテーブルにおいて同一のキーを使ってしまうケース」がありました。以下がそのクエリとキーの例です。
テーブルA
クエリ：SELECT * FROM テーブルA WHERE id = ?
キー：id_?テーブルB
クエリ：SELECT * FROM テーブルB WHERE id = ?
キー：id_?
この場合、キーにテーブル名が含まれていないためどちらかのテーブルのデータがキャッシュされてしまうと、もう一方のテーブルの同一idのデータは正しく取得できなくなります。
また、「Where句に含まれるパラメータがキーに含まれていないケース」もありました。
クエリ：SELECT * FROM テーブルA WHERE type = ? and value in (?)
キー：type_?
こちらの場合には、キャッシュ時のクエリにおけるvalueと異なるもので取得しようとした場合に正しいデータが得られません（このクエリに対して正しいキャッシュキーを作るのは少し難しいかもしれません）。
これらは非常に簡単な例ですが、安全なキャッシュ処理を書くことは難しい上に、デバッグやテストで発見されないケースも多々あります。
誰が書いてもバグが発生しない仕組みを導入する、もしくはそもそも書かなくてよい状態にするというのが理想です。
実装コスト
キャッシュを利用するコードを都度実装するのは単純に手間がかかります。
基底クラスによくテストされ実績のあるキャッシュ処理を置き、自身で書かずに済むようになれば、実装のみならずテストやデバッグの手間も省かれます。
レガシーなDataMapper基底クラス
対象となるプロジェクトにおいて、DataMapperの基底クラスはリリース時からほぼ手をつけられておらず、現状の開発運用において不都合なことも増えてきました。
それに加えて、当時の開発者がチームを離れてしまっており、完全に仕組みを理解できている人がおらず修正も困難な状況でした。
不安定な土台の上に新たな機能を積み上げることは困難です。不安定な挙動を無くすことで、新しい機能を積み上げることができる強固な土台とすることを目指しました。
Staticキャッシュ不具合
ユーザデータをキャッシュするのにAPCuキャッシュは向いていません。それは、ユーザデータの更新頻度が高いことやAPCuキャッシュがサーバー単位でのキャッシュでありリクエスト時にキャッシュされたサーバーに当たるとは限らないことなどが理由になります。
１リクエストにおいて複数回データを取得する必要があることでパフォーマンスに影響する場合には、Static変数を利用したキャッシュ（以下Staticキャッシュ）を利用していました。
APCuキャッシュの継続時間（ライフタイム）は半永続的です。一方、Staticキャッシュではリクエスト単位になります。*1
Staticキャッシュにおいても同様のヒューマンエラーが発生していました。特にユーザデータはリクエスト処理の途中で更新される可能性があり、それを考慮した処理実装の難易度は高くなります。
問題に対する方策
問題を全て列挙することができましたので、これらをどうすれば解決できるのかについて考えていきます。
データ取得メソッドの実装者が必ず書かなくてはならないものは対象のクエリのWhere句、つまりどのデータを取得するのかということです。
このWhere句から対応するキャッシュキーが自動で生成できれば、キャッシュ処理を書かずに済むようにできる可能性があります。
ではどうすればWhere句からキャッシュキーを生成できるでしょうか？
Where句とそれに含まれるパラメータの関係性について考えた際に、これをN部グラフに置き換えることが可能であり、キーの生成と管理が容易になることがわかりました。
N部グラフをご存じない方もいるかと思いますので、まずこちらについて説明します。
N部グラフ
このN部グラフというのは数学における理論の１つであるグラフ理論における概念です。
また、グラフ理論とは頂点の集合と辺の集合により構成されるグラフに関する数学の理論です。
具体的にはグラフとは以下のようなものです。
この図における円が頂点、円の間に引かれた線が辺となります。
このようなグラフにおける性質を探求するのがグラフ理論です。
また、頂点集合を２つに分割して各集合の頂点は互いに繋がらないようにできるグラフを２部グラフといいます。
なかなか言葉の説明では難しいと思いますので、以下の２部グラフの具体例を用いてよりわかりやすく説明します。
頂点集合Aの頂点同士は辺で繋がれていません。Bの頂点同士もまた辺で繋がれていません。しかし、AとBの頂点は辺で繋がれています。こういったグラフを２部グラフといいます。
N部グラフはこれをN個の頂点集合に拡張したものです。今回はある頂点集合に関して隣接する頂点集合が最大2つである以下のようなグラフを用いていきます。
では、実際にN部グラフにWhere句を当てはめて考えていきます。
N部グラフを使ったWhere句パラメータの表現
今回の対応では、Where句において使える演算子を「=」、「IN」、「AND」、「OR」の４種類に絞ります。これは、この４つの演算子で大抵のケースに対応できるためです。
まずは「=」と「IN」の２つの演算子におけるWhere句のグラフ化を考えます。先程のN部グラフにおける頂点集合をWhere句におけるカラム、頂点をパラメータと考えます。
つまり「where id = 1」におけるidが頂点集合に対応し、その集合に頂点「1」が含まれることになります。
「IN」の場合には頂点数をパラメータ数だけ増やします。「where id in (1,2,3)」の場合には頂点が「1」、「2」、「3」の３つになります。
ここでより難しい「AND」について考えてみましょう。例として「where a = 1 and b in (1,2,3)」のグラフ化を試みます。前述のようにカラムとパラメータは頂点集合と頂点に対応します。
ここでWhere句において隣接するカラム（図の場合aとb）のパラメータ間に辺を加えます。ここでは「a:1,b:1」、「a:1,b:2」、「a:1,b:3」に辺を加えることになります。
「AND」が2つ以上の場合も同様です。「where a = 1 and b in (1,2,3) and c in (1,2)」の場合には以下のようになります。
このように、ANDで繋がれたカラムの数がいくつに増えたとしてもN部グラフで表現できます。
残った「OR」演算子ですが、これはグラフを分割することで表現できます。つまり「 a = 1 and b = 2 or c = 3 and d in (4,5)」といった場合には2つの2部グラフが存在することになります。
このグラフにおける各頂点集合における辺で繋がれた頂点の組み合わせ（頂点集合が１つの場合は頂点）がキャッシュキーに対応しています。
つまり、以下のグラフにおいては「a:1,b:1,c:1」、「a:1,b:1,c:2」、「a:1,b:2,c:1」、「a:1,b:2,c:2」、「a:1,b:3,c:1」、「a:1,b:3,c:2」をキャッシュキーとして用いることができます。
「OR」によってグラフが複数になる場合には、各グラフにおいて列挙したものを足し合わせればよいだけです。
例えば「where a = 1 and b = 2 or c = 3 and d in (4,5)」といったWhere句のグラフではキーは「a:1,b:2」、「c:3,d:4」、「c:3,d:5」の３つになります。
Where句の再構築
Where句をN部グラフに置き換えて対応するキャッシュキーを生成することができましたが、実際にロジックに組み込むにあたって解決すべき問題があります。
それは、キーに対応するキャッシュに乗っていなかった場合にデータ取得をどう行うかということです。
この場合に元のWhere句のまま実行してしまうとキャッシュから取得可能なデータも余計に取得することになります。
余分な取得を抑えつつも１回のクエリ実行でキャッシュに乗っていないデータを取得するクエリが必要で、元のWhere句をこの条件を満たすものに変換する必要性が出てきます。
N部グラフに置き換えたことにより、これについても簡単に考えることができます。
手順は以下の通りです。
- キャッシュが見つからなかったキーだけを取り出す
- N部グラフの辺が全く無い状態からキーに対応する辺を加える
- 辺で繋がれていない頂点を取り除く
- 残った頂点をパラメータとするWhere句を生成
では実際の例を用いて、流れを具体的に見ていきましょう。まず「where a = 1 and b in (1,2,3) and c in (1,2)」について考えます。
また、キャッシュキーは「a:1,b:1;c:1」、「a:1,b:1;c:2」、「a:1,b:2;c:1」、「a:1,b:2;c:2」、「a:1,b:3;c:1」、「a:1,b:3;c:1」になります。
この際に「a:1,b:1;c:1」、「a:1,b:1;c:2」に対応するキャッシュが乗っていたとします。
キャッシュに乗っていないキーは「a:1,b:2;c:1」、「a:1,b:2;c:2」、「a:1,b:3;c:1」、「a:1,b:3;c:1」になりますので、一旦グラフから全ての辺を除いた上で、このキャッシュに乗っていないキーに対応する辺を全て加えます。
このグラフから辺で繋がれていない頂点を取り除きます。この場合はb:1のみが辺で繋がれていない頂点となります。
残った頂点からWhere句をグラフ化するのと逆の手順でWhere句を再構成します。このグラフの場合には、「where a = 1 and b in (2,3) and c in (1,2)」が得られます。
このように再構成されたWhere句によりキャッシュに乗っていないデータを取得することができます。
キャッシュの状態によっては再構築されたWhere句でキャッシュ済みのデータを取得することがあります。このグラフでの例としては「a:1,b:1;c:1」だけがキャッシュに乗っていた場合にはWhere句は元と同じ「where a = 1 and b in (1,2,3) and c in (1,2)」となり、余計にデータを取得します。
このようなケースは実際は発生しにくく、発生した場合においてもキャッシュに蓄積されていくため大きな問題はないと考えています。
Where句データクラス
実装に必要なことについて考え終えたので、キャッシュキーを管理するWhere句データクラスを実装します。
Where句データクラスには比較演算子「=」、「IN」と論理演算子「AND」、「OR」の組み合わせに対応するメソッドwhereEqual、whereIn、orWhereEqual、orWhereInを用意しました。
whereEqual、whereInでは頂点と頂点集合を追加し、追加する頂点と直前の頂点集合の全ての頂点とを辺で繋ぎます。orWhereEqual、orWhereInでは、新たにグラフを作り、頂点集合と頂点を加えます。
「where a = 1 and b in (2,3) or c = 4」に対応するWhere句データクラスは以下のように書くことができます。
$whereClauseData = (new WhereClauseData) ->whereEqual(‘a’, 1) ->whereIn(‘b’, [1,2]) ->orWhereEqual(‘c’, 4);
また、データ取得メソッドを作るためには以下の機能が必要となります
- createKeys：Where句からキーを生成
- deleteKeys：指定したキーを削除
- addWhereClause：Where句を生成（SelectオブジェクトへのWhere句付与）
- createKeysByModel：クエリで取得したデータからWhere句に対応するキーを生成
キーの生成、削除、Where句の生成に関しては先程図解いたしました。
これまで特に説明をしていませんでしたが、クエリによって取得したデータをキャッシュするためにデータから対応するキーを生成できる必要があります。
Where句データが頂点集合としてカラムの情報を持っているため、こちらから対象のキャッシュキーを生成することが可能です。生成するキーはWhere句データが持っているキーに限定する必要があります。
データ取得メソッドの再実装
Where句データクラスを引数にとるデータ取得メソッドをDataMapperの基底クラスに実装します。このデータ取得メソッドのコード例は以下のようになっております。
<?php final protected function findAllByWhereClauseData( WhereClauseData $whereClauseData ): array { // Where句からのキー生成 $keys = $whereClauseData->createKeys(); $cachedModels = []; // キャッシュ済みデータ $cachedKeys = []; // キャッシュ済みキー // APCuキャッシュからモデル取得 foreach (array_diff($keys, $cachedKeys) as $key) { // キャッシュからデータ取得 if (($models = $this->cacheLoad($this->convertToCacheKey($key))) === false) { // キャッシュにない場合は次のキーへ continue; } $cachedKeys[] = $key; $cachedModels = [...$cachedModels, ...$models]; } // キャッシュから全て取れている場合 if (empty(array_diff($keys, $cachedKeys))) { // OR句などによりデータが重複するためプライマリーキーでユニーク化 return $this->uniqueByPrimaryKey($cachedModels); } // キャッシュがあったキーに該当するWhere句のパラメータを削除 $whereClauseData->deleteKeys($cachedKeys); // 未キャッシュデータを取得するWhere句をselectオブジェクトに付与してDBからデータ取得 $fetchedModels = $whereClauseData->addWhereClause($this->select())->fetchAll(); // APCuキャッシュに保存 $modelListMapForSave = []; foreach ($fetchedModels as $model) { // 取得データからWhere句に対応するキーを生成 foreach ($whereClauseData->createKeysFromModel($model) as $key) { $modelListMapForSave[$key][] = $model; } } foreach (array_diff($keys, $cachedKeys) as $keyForSave) { $modelList = $modelListMapForSave[$keyForSave] ?? []; // キーに対応するデータをAPCuキャッシュに保存 $this->cacheSave($modelList, $this->convertToCacheKey($keyForSave)); } // キャッシュから取得したデータとクエリから取得したデータをマージして返却 return $this->uniqueByPrimaryKey([...$cachedModels, ...$fetchedModels]); }
Where句から生成されるキーにはテーブルの情報は含まれていませんので、convertToCacheKey()によってテーブル名をプレフィックスとして付与することでテーブルごとのキーの独立性を保ちます。
このメソッドを用いることで、マスターデータのDataMapperの基底クラスにあるプライマリーキーを指定してデータを取得するメソッド等を書き直すことができました。
Staticキャッシュ利用メソッドの実装
ユーザデータ用のStaticキャッシュを使用したデータ取得メソッドも実装しました。
おおよそはデータ取得メソッドと同じで、違いはAPCuキャッシュではなくStaticキャッシュを用いることです。また、データに更新がかかっていた際にStaticキャッシュを消去するようにし、キャッシュを用いた安全なデータ取得を可能にします。
<?php final protected function findAllByWhereClauseDataUsingStaticCache( WhereClauseData $whereClauseData ): array { $keys = $whereClauseData->createKeys(); static $staticCachedModelMap = []; // テーブルに更新があるかチェックして、更新があった場合にはキャッシュをクリア $this->checkStaticCacheAvailability($staticCachedModelMap); // Staticキャッシュからデータ取得 $cachedModels = []; $cachedKeys = []; foreach (array_diff($keys, $cachedKeys) as $key) { if (array_key_exists($this->convertToCacheKey($key), $staticCachedModelMap)) { $modelList = array_map(static function ($model) { return clone $model; }, $staticCachedModelMap[$this->convertToCacheKey($key)]); $cachedKeys[] = $key; $cachedModels = [...$cachedModels, ...$modelList]; } } // キャッシュから全て取れている場合 if (empty(array_diff($keys, $cachedKeys))) { return $this->uniqueByPrimaryKey($cachedModels); } // キャッシュがあったキーに該当するデータを削除 $whereClauseData->deleteKeys($cachedKeys); // DBからデータ取得 $fetchedModels = $whereClauseData->addWhereClause($this->select())->fetchAll(); // Staticキャッシュに保存 $modelListMapForSave = []; foreach ($fetchedModels as $model) { foreach ($whereClauseData->createKeysFromModel($model) as $key) { $modelListMapForSave[$key][] = $model; } } foreach (array_diff($keys, $cachedKeys) as $keyForSave) { $modelList = $modelListMapForSave[$keyForSave] ?? []; $staticCachedModelMap[$this->convertToCacheKey($keyForSave)] = array_map(static function ($model) { return clone $model; }, $modelList); } return $this->uniqueByPrimaryKey([...$cachedModels, ...$fetchedModels]); }
という感じでWhere句データクラスを用いたデータ取得メソッドを実装することができました。また、プライマリーキーやユニークキーでのデータ取得用に単一のデータを取得するメソッドをこのメソッドを用い実装しています。
各テーブルのDataMapperにデータ取得メソッドを実装する場合には、対応するWhere句データの生成し、これらのWhere句データを引数とするメソッドを呼び出すだけとなります。
まとめ
N部グラフの概念を利用してWhere句からキャッシュキーの生成、管理を行うモジュールを開発することができました。
このモジュールにより、マスターデータやユーザデータのキャッシュを利用したデータ取得に関連する問題を解消しています。
個々のテーブルにおけるデータ取得メソッドの実装もWhere句データクラスのインスタンス生成とメソッドの呼び出しのみになり、今では簡単に素早く安全な実装を行えています。
また、具体的には説明いたしませんが、簡単にStaticキャッシュを用いることができるようになったため、遅延的に一括でデータを取得する機能など今までに追加できなかった処理も追加できるようになりました。
とは言えども、本機能はまだまだできたばかりでより発展的な機能が入る余地があります。例えば、あるWhere句に対して上位集合となるWhere句でキャッシュされている場合、そちらを利用するようにするとキャッシュ効率が上がることでしょう。*2
以上でデータ取得メソッド再実装のお話とさせていただきます。最後までお読みいただきありがとうございました。
