同僚が新しい WAF(Webアプリケーションフレームワーク) を作っていて、その中で使うデータクラスの O/Rマッパーを何にするかで迷っているようだったので、こう叫んでおいた (心の中で)。

O/Rマッパーなど、SQLもまともに扱えない軟弱者があみだした不格好な補助輪にすぎない !
Webアプリケーションが重い理由の8割はO/Rマッパーのせいだ !
漢なら SQL 直書きが当たり前 !
そうでなければ時代の流れに沿って key-value store 専用に設計すべき !


まあそんなこと言っても、現実には作業効率とか考えたら使うけどね、O/Rマッパー。

そんなことより、key-value store に特化された設計の WAFってのは面白いんじゃないかと思った。既にそういうのあるんだろうか ?

既存のフレームワークでも、ほとんどの部分は簡単にデータベース部分を key-value store に置き換え可能な気はする。ただ、それしか使わないとなると、更新日時順に一覧表示するとか、ランキングを出す、とかが大変そうだ。

なので key-value store のみで新着順やランキングを効率的に作成/アップデートするにはどうすればいいかを考えてみていた。



例えばページデータを更新日時の新しい順に並べて表示するには ?

一番簡単なのはもちろん、ページデータを (key-value store からひとつずつ) 全件取得して、オンメモリで新着順に並べかえる方法だ。ただ、この方法は全くスケールしない。N個のページデータがあればN回分、1000万個のページデータがあれば1000万回分の retrieval が発生する。

たぶん、key-value store で新着順の配列のようなものを実現するには Cache::Memcached::Managed が使ってたあの方法 (正式な名前があるのかどうか知らない) がスマートで良いのではないかと思う。こういうやつ。

kvs1

連番のキーを用意して、キーの名前をインクリメントしながらデータを保管していく。現在使用中の最小キー値と最大キー値(=次回の挿入位置)も別途覚えておく。
上の例はページid 4, 5, 12, 6 の順に新しく更新されたという状態を表している。さらに新しいページが出てきたら key104 に保存されることになる。

この方法は、最大キー値のインクリメントがアトミックに出来さえすれば、排他ロックが必要ない [*追記注1] ところが利点だ。

キーの名前が無限に増えていくのが気持悪いのであれば、このように、一定の値を超えたら最初に戻るリング構造にしておけば良い.

kvs2



では、ランキングはどうだろう。例えば、ページデータをアクセス数順にランキング表示するには ?
ここでも、ランキング算出のたびに全件取得してオンメモリで並べ替えるという選択肢は除外する。

いろいろ考えてやっと思いついたのが、キー名でバイナリツリーを表現する方法。

キー名がそのままバイナリツリーのノード位置を示していて、各ノードにページデータが保存されているような key-value store を考える。こんな感じ。

kvs3

キー名 "key0" のデータがルートノード。
あるノードの左側の子ノードは、親ノードのキー名に"0"を付け足したキー名を持つ。右側の子ノードは、"1"を付け足したキー名を持つ。左側には親ノードより下位の、右側には上位のデータが保存される。

上の図の例では、ページid 2 が150アクセスでもっとも少なく、ページid 10 が300アクセスで最も多い。
ここにアクセス数 180 (key0 の値より下、key00 の値より上) のページが新しく出てきた場合、そのデータは新たなキー "key001" に保存される。

こうすると、N個のページデータが存在する場合に、最上位(もしくは最下位) のデータには平均 log N 回のアクセスで到達できる。1000万個のページデータがあっても発生するデータアクセスは 23回程度、しかも実データの retrieval ではなく、キーの存在チェックだけで済む。
(ついでに、キー名の長さも最大 log N 程度で収まる。)

アクセス数ランキングなどの場合、教科書通りの実装だとページアクセスがあるたびにツリーの更新が発生して効率が悪いことこの上ないけど、そこはBツリーにしたりとか、部分木をまとめて1つのキーに格納してしまったりとか、実用的なものに改善する方法は色々とある。

また、どこかのページが閲覧されるたびに、毎回 log N プラスαのデータアクセスが必要になることになるけど、それなら更新頻度も 1 / log N にしてしまえば、平均1ページビューあたり1回のデータアクセスで済む計算になる。対象となるページデータが1000万個あるなら、アクセス数が23増える度に一回しかランキングを更新しにいかないようにすれば良い話で、ランキングの更新頻度としてはそれで十分だろう。



と、ここまで考えて、これってRDBのインデックスを自前で実装してるのと変わらんよね、ということにいまさら気付きました。

結局、key-value store 前提で WAF 作るにしても、ランキングとか用には別途普通の RDB を用意しておいてそれ使えばいいだけな気がしてきたところでおしまい。

本当に key-value store だけしか使いたくない場合は、データクラスの他にインデックスクラスがあって、アプリケーション側で必要に応じてインデックスクラスも使うような仕組みになるのかなぁ。




[*追記注1]
next_index をインクリメントし、同時に現在の(もしくはインクリメントする前の) next_indexの値を返り値として取得する、という一連の操作がアトミックにできることを前提としている。それができれば、
(1) next_index をインクリメント
(2) インクリメントする前のnext_index位置に新しい値を保存
という手順をとれば挿入位置が競合することはないはず。
ただ、(1) と (2) の間のタイミングで他の読み出しをしようとすると、あるべきキーがまだ未定義のままになってしまうので、読み出し側は、存在するはずのキーが未定義の場合は読みとばすという処理をいれておかないといけない。