著者

森島 信 松谷 宏紀

出版者

The Institute of Electronics, Information and Communication Engineers

雑誌

電子情報通信学会論文誌 D (ISSN:18804535)

巻号頁・発行日

vol.J100-D, no.12, pp.949-963, 2017-12-01

---

ドキュメント指向型データベースは,ユーザがスキーマレスにドキュメントを保存し,それに対する探索クエリを実行できるデータベースである.その利用用途として,高い拡張性や豊富な機能が要求されるウェブアプリケーションやオンラインゲームが挙げられる.ドキュメント指向型データベースの主な機能の一つは,ドキュメントに対する文字列探索であり,その計算量はドキュメント数に比例して増加するため,多くのドキュメントを扱う場合,計算量が非常に大きくなる.この計算量を削減するため,ドキュメント指向型データベースでは,データベースインデックスが使われている.しかし,インデックスは全てのクエリに適用できるわけではなく,例えば,正規表現探索等のクエリに適用するのは困難である.これらのインデックスを適用できないクエリをGPUを用いて高速化するために,本論文では,DDBキャッシュ(Document-oriented DataBaseキャッシュ)というGPUでの文字列探索処理に適した構造のキャッシュを提案する.GPUとDDBキャッシュを用いることで,ドキュメント指向型データベースの文字列探索処理をインデックスを使わずに高速化できる.更に,ハッシュ機構を用いてDDBキャッシュを分割し,複数台のGPUに分散する手法を提案し,GPUを用いた手法の水平拡張も可能にする.評価では,代表的なドキュメント指向型データベースであるMongoDBを対象にDDBキャッシュを実装し,性能を評価した.その結果,インデックスの適用できない正規表現探索クエリにおいて,GPUを用いた提案手法はMongoDBを大幅に上回るスループットを達成した.また,GPUの数を1台から3台に増やしたことで,2.7倍のスループットの向上を達成し,GPU数を増やすことで水平拡張ができることを示した.