多様な検索と負荷分散を両立するための仮想ノード割り当て方法

摘要

近年，様々な用途において普及している分散DBでは，スケーラビリティや耐障害性の観点から階層化TabletやConsistent Hashingによる分散アルゴリズムが採用されている．特にConsistent Hashingは1hopでデータにアクセス可能であるため，リアルタイム性が要求される通信処理に対しても適用が研究されている．通信処理においては．各処理が低負荷にすることが必要であるが，本手法では範囲検索や条件検索を実施する場合に全件検索が必要であり，検索時間が膨大になるだけでなくシステムにかかる負荷も大きいという問題があった．これに対し，Hash関数に連続性を持たせるという解法も考えられるが，半面，振り分けの均等分散性が失われてしまうという問題があった．この問題に対し，これまで我々は仮想ノードを適用することで，均等性を確保する方式を提案してきたが，検索結果が特定のデータに偏るケースにおいて，充分に仮想ノードが配置されずに均等性の確保ができないという問題が残っていた．そこで本研究では，この仮想ノードの割り当てをアクセス頻度に応じて適切に行うことで，如何なるアクセス分布の場合でも均等性を確保し得る手法の提案を行う．