データ分散アルゴリズムASURAの実装

最近、仕事がピリっとしないからか、趣味で分散ストレージでも作ってみようかなぁと思って色々と思考を巡らしている。

分散ストレージには大きく分けて２つの実装がある（と思う）。

１つは、どのデータがどこにあるかなどのメタデータを持つメタデータサーバを保持し、そのメタデータサーバを参照・更新しながらレプリケーションや、ピースの分散を行うというタイプのもの。もしこれをやるのであれば、メタデータはTiKVを使おうかなと考えていた。 TiKVはRustで実装された分散KVSだが、レプリケーションを行う単位をRaftグループとして、これを複数持つMulti-Raftという構成をとっている。外にはプレースメントドライバというプロセスがデータや負荷の分散具合を監視し、必要に応じてマイグレーションを行っているらしい。 Raftを使っていれば、マイグレーションは簡単だろうと想像する。

もう１つは、そもそもそんな糞メタデータサーバは持たないというタイプのものだ。スケールアウト型分散ストレージというと、こちらのことを指しているという理解をしている。これは例えばCephの分散オブジェクトストアであるRADOSや、Cassandraなどがこのタイプに属する。メタデータサーバを持たずにどのようにデータを分散するのかというと、これはデータから一意に配置ノードを計算出来るようなアルゴリズムを使う。有名なものではConsistent-Hashingがあるが、 CephはCRUSHアルゴリズムというのを使っていて、他にもランデブーハッシュとか、色々ある。

おれは、どうせ作るならば後者だろうと決めた。前者は面白くないからだ。

Consistent-Hashingというのは教科書に書いてあるとても有名なアルゴリズムだが、ノードがハッシュリングの上に偏って配置されてしまい、結果としてデータが容量をうまく反映出来ないという欠陥がある。これに対して、仮想ノードを大量に作ってごまかすという手段が一般的にとられるが、これもいくつ仮想ノードを作るのが最善なんですか？という問いに答えることが出来ない。ランデブーハッシュのように、ハッシュリングを持たず、計算によって配置ノードを決めるという Consistent-Hashingの裏の顔のようなアルゴリズムもあるが、今度は計算コストがかさむという問題がある。いずれにしろ、ピリっとしないのだ。

あーどれもこれも知的障害アルゴリズムだ。もう自殺するかと思っていた昨晩、攻殻機動隊二期を見ながらポチポチググっていると面白い論文を見つけた。 ASURAというアルゴリズムで、具体的にどう発音するのかわからない（やっぱ阿修羅ですか？）が、とにかくざっと読んで見ると、具体的な解析はともかくアイデアだけは面白いと思えたので実装してみることにした。こういうのは実装してみないと何もわからんだろう。恒例のベッディン後、布団の中で二時間ほどスマホで論文を読んで理解し、今日実装した。

https://github.com/akiradeveloper/ASURA

基本的なアイデアは超簡単だ。円周率をコンピュータによって求める方法として、適当に針を落としまくってみて、それが円に入った本数によって円周率を決めるという方法がある。これをモンテカルロ法というのだが、これと似たような考え方だ。

Consistent-Hashingでは、ノードのハッシュ値が馬鹿なので、リング上で偏って配置されてしまうのだが、仮にこのノードの位置を、ノードの容量などを反映して恣意的に配置し、あとはそのリングをダーツボードと見立ててダーツを投げる（おれは陰キャなのでダーツはやったことないけど）。そして当たったノードを採用する。ダーツがどこに飛んでいくかは、データ自体をハッシュ生成器のシードとすれば再現性があるから、データから配置ノードが再現可能な形で計算出来るというわけだ。

これでは大変胡散臭く感じるだろう。その直感は正しく、こんなわけのわからないことをするためにはもう一工夫必要になる。実際、ASURAのアルゴリズムの肝は、ASURA乱数の生成アルゴリズムにある。これも非常に面白い。これ「が」と言ってもよい。この乱数生成アルゴリズムによって、ノードを追加・削除したとしても、以前に配置したノードが影響を受けにくいように出来る。追加・削除したノード分の容量しかデータの移動が起きないことが保証出来る。

実装してみて思ったことだが、このアルゴリズムは他のアルゴリズムに比べて使い方が難しい。アルゴリズムの実行のためには、ノードをセグメントにマップしたデータ構造を作る必要があるのだが、この管理が難しくなると思う。使う側にも影響が大きいので、選択にストレスがある。

今後は、ベンチマークを書いてみて、実際にConsistent-Hashingとの比較などもする予定だ。 PR待ってます。