線形ハッシングを実装したので報告する。

前の記事で、線形ハッシングを実装することを課題としていたが、 実装するつもりで詳しく調べてみるとなかなか美しいアルゴリズムで、興味がわいたので一気に２日ほどで実装した。 線形ハッシング一般についてと、おれの実装であるLinHashの工夫について書く。

https://github.com/akiradeveloper/LinHash

線形ハッシングとは

KとVのマッピングを保持するオンディスクハッシュテーブルである。 IOのための一時的なバッファ以外では常駐するオンメモリメタデータはほぼない。

また、クエリはデータベースのサイズによらず１つか２つのページ読み出しで済むので、 理想レベルに高速である。

アルゴリズムの概要

ディスク上に、オープン法によってハッシュテーブルを実装することを考えよう。 すると、バケットという単位（便宜上4KB）を定義してその中にKV列を格納し、 ディスクをバケットの配列と見れば実装出来ることがわかるだろう。

しかし問題がある。リハッシュのオーバーヘッドが大きいことだ。 ちょうどFullGCのような感じで、全体が停止することになる。

そこで、バケットの拡張を倍々ではなく、１つずつ行うことにする。 なぜそのようなことが可能なのかというのが線形ハッシングのアルゴリズムの美しいところなのだが、 線形ハッシングでは、「次にどのバケットを分割するか」というポインタを保持し、 分割するバケットの順序を決定的にすることで、ハッシュテーブルとしての性質を維持し続けることが出来る。

詳しく知りたい人は以下のブログをオススメする。あとはチャッピーと会話してください。

https://samrat.me/2017-11-04-kvstore-linear-hashing/

LinHashの工夫

rkyvによるゼロコピーデシリアライゼーション

Rustではserdeというのがよく使われるが、バケットのデータを仮にこれで実現すると、 バッファを読み出したあとに デシリアライズする際に構築のオーバーヘッドが発生する。

そこでLinHashではrkyvというライブラリを使い、デシリアライズをゼロオーバーヘッドにした。

RWF_ATOMICの利用

ページをディスクに書いた時、torn writeという問題がある。 これは、書き込みをしている途中にたまたま電断などが起こった場合、 永続化された状態が「元の状態」でも「書き込んだ状態」でもない 中途半端な状態になってしまうことであるという問題だ。

この問題に対するアプローチは 怪しいものから、確実ではあるものの死ぬほど重いまで様々あるのだが、 Linuxカーネル6.11でRWF_ATOMICというフラグが導入された。

レッドハットのドキュメントによると、以下のように書かれている。

RHEL 10 では、ファイルシステム、ブロックレイヤー、およびドライバー全体におけるサブシステム間の拡張機能としてアトミック書き込みが導入されています。RWF_ATOMIC フラグは、torn-write 保護を有効にするために使用されます。これにより、システムクラッシュまたは電源障害が発生した後、書き込まれたデータのすべてが安定したストレージに存在するか、まったく存在しないかのいずれかになります。このシナリオでは、部分的なデータ書き込みや書き込み破損は発生しません。

これが本当に正しく実装されているかも怪しいところだが、 方向性としては正しいと考えて利用することにした。 そのため、LinHashは比較的新しいカーネルでしか動作しないが、 実装としてはより先端的なものになっている。

また、RWF_ATOMICを利用する場合はダイレクトIOを強制されるが、 そもそも線形ハッシングにおいてはバケットレベルでの局所性はあり得ないため （そもそもハッシュが散ってることが根拠なので）、 特にデータベースが超大きい場合には、ページキャッシュも効かない。 そのため、そもそもページキャッシュは無効化するのが正しく、 もしキャッシュするならばキーレベルでの局所性を狙って mokaなどを使ってユーザランドでキャッシュするのが良いと思う。

削除なしモードの提供

線形ハッシングにおいて、削除はなかなか鬱陶しい操作である。 というのも、削除をするとバケットに空きが出来るので、 挿入操作においてあるバケットを見た時に、 そこに空きがあったとしても挿入を即断出来なくなるからだ。 そのため、オーバーフローページ まで全部見て、新規挿入ではなく実は更新すべき ということを知る必要が出てくる。 結果として、削除をサポートするしないで、挿入のコストが大きく変わってくる。

この線形ハッシングの実装はもともとSHAMapの実装のために行っているし、 これ以外の場合でも削除は不要という人はふつうに存在すると思うので、 削除なしモードというのをfeature-gateで提供している。

ハッシュしないモードの提供

SHAMapでの利用を考えると、そもそもキーはハッシュ化されており、 再度ハッシュ関数を適用する必要がない。 このようなケースを想定して、ハッシュしないモードをfeature-gateで提供している。

並行性に関する考察

現在、LinHashはinsertやdeleteなどの書き込み系は&mutをとり、getは&をとっている。これによって実装が簡単になるメリットがあるし、大抵の場合は書き込みの方が圧倒的に少ないという性質があるのだから、この設計は大きな問題にはならない。ただ、理想的ではないとは思っている。

線形ハッシングは、各バケットとそこから繋がるオーバーフローページが独立であり、形は歪んでいるものの論理的にはシャーディングに近い。だから、今のようにDB全体のジャイアントロックをとるのではなく、バケット単位に細粒度可能なはずだ。 その場合、線形ハッシングはバケットに局所性がなく十分に散ることが前提となっているのだから、細粒度化は最大限に活かされるはずである。