A Study on Optimization of Concurrency Control for Distributed B-trees on Parallel and Distributed Systems

 近年のITシステムは，多数のCPUコア，ストレージデバイス，主記憶から成るサーバとサーバ間ネットワークによって構成されている．主流CPUであるマルチコアCPUの性能向上は鈍化し，CPUベンダは1チップで60コアを超える「メニーコア」CPUを開発してきている．CPU間をつなぐネットワークとしてイーサネットが主流であるが，イーサネットの価格と性能は上がりづらい．高速なストレージデバイスであるSSDと巨大な主記憶がストレージデバイスのボトルネックを解消してきており，ネットワーク，CPUコアを有効活用する最適化が重要である．

 そのITシステムでは，RDBMS，key-value store，グラフDB，ファイルシステムなどさまざまなアプリケーションが動作している．これらのいずれのアプリケーションの性能にとっても，データに対するインデクスとインデクスへのアクセスは重要であり，性能向上するために分散インデクスを用いた並列分散処理を行っている．分散ストレージシステムや並列データベースは上記アプリケーションにおけるキーコンポーネントであり，それらのインデクスとして主に分散B-treeが用いられる．インデクスである分散B-treeを並列アクセスするための排他制御である並行性制御は，インデクスへのアクセス性能に大きな影響を与え，上記アプリケーション性能にも大きな影響を与える．近年のハードウェアのキーコンポーネントであるメニーコアやネットワークの特徴を考慮した並行性制御の最適化が重要になる．

 分散B-treeの並行性制御は，並列分散処理の1つである．並列分散処理の性能向上のための重要な課題は，並列分散処理間の①「通信処理」，②「負荷偏り制御の最適化」である．並列分散処理の性能を，並列数に対して性能をスケールするためには，楽観的なアプローチが主に用いられ，楽観的処理に伴う③「リトライ処理」の最適化も重要な課題である．また，ITシステム上の多くのアプリケーションは，性能面だけでなく，信頼性，可用性のためにも，複数のサーバに冗長データを分散し管理する．④「冗長データへのアクセス」の最適化も重要な課題である．

 本研究では，分散B-treeの並行性制御に関して上記①〜④の課題に取り組んだ．①通信処理の最適化に関して，排他制御に伴う通信回数を削減する最適化を行う並行性制御手法を提案した．②負荷偏り制御の最適化に関して，負荷偏りが起きづらいように処理振り分けを行うとともに，排他制御による衝突を削減する技法を組み合わせる並行性制御手法を提案した．③リトライ処理の最適化に関して，ツリーにヒント情報をマーキングすることにより不必要なトラバースを削減する並行性制御手法を提案した．④冗長データへのアクセスの最適化に関して，冗長データを保持するサーバやデータを保持していないサーバを有効活用する分散B-treeおよびその並行性制御を提案した．サーバクラスタやメニーコアサーバ上の実験を通して，提案手法を既存手法と比較し，各提案手法によりスループットがそれぞれ2倍以上向上する等の実測による優位性を示した．