細かすぎて伝わらないmdbm

こんにちは、匿名希望の社員Mでございます。

Yahoo! INCが、NoSQLのmdbmをオープンソースとして公開しました。Yahoo! JAPANでも10年以上もお世話になっているものです。

https://github.com/yahoo/mdbm

さて、この場面ではライトなユーザードキュメントや紹介を期待されているところですが、そんな空気感は一切無視して進行したいと思います。

個人的にどうしても言っておきたい見所を一方的に紹介してみたいと思います。よろしくお願いします！

剰余の演算処理は遅い

KVSの基本的な処理は、keyからハッシュ値を算出しハッシュ値の剰余を用いて、valueを格納するデータ領域（page）を決定するアプローチとなります。

この処理を忠実に実装すると次のような実装イメージとなります。

pagenum = hash(key) % pagesize;

しかしながら剰余は非常に遅い処理ですので、仕様に一定の制限を加えることでマスク値を利用したAND演算で実装されています。

pagenum = hash(key) & mask;

おまけ話として、mdbmはLinear Hashingと呼ばれるハッシュアルゴリズムの影響を強く受けています。

Linear Hashingの詳細はwikipediaをご覧ください。

http://en.wikipedia.org/wiki/Linear_hashing

このアルゴリズムによりmdbmは、扱うデータサイズが大きくなれば、動的にHashTableを拡大することができる非常に便利な特性を持っています。

しかし、冷静になって考えてみてみましょう。このLinear Hasingの管理用のテーブルを走査する計算コストは可能なら避けるべきです。

mdbmをはじめ、多くのKVSでは最終的なデータのサイズの予想がつくのであれば、あらかじめ大きめのサイズでデータベースファイルを作成する方が好ましいでしょう。

この辺の話に興味がありましたら、コードの「hashval_to_pagenum()」という関数から追いかけ、処理コスト削減を努力を見ていただければ幸いです。

rdtsc（Read Time Stamp Counter）

タイムスタンプを取得する方法にrdtsc命令を使用する一部の方々が大喜びするテクニックがあり、その一部を垣間見ることができます。

これはIntel x86系のCPU（AMDの一部を含む）のCPU上に実装されている、CPUクロックごとにタイムスタンプカウンタを利用しています。

この実装はgettimeofday()がシステムコールとして実装されていてオーバヘッドが非常に大きかったときに大活躍だったテクニックです。

CentOS6.x/RHEL6.xでは、gettimeofday()はユーザースペース（vsyscall/vdso）で実装されているためオーバヘッドは大幅に低減しています。

CentOS5.x/RHEL5.xでも、次のパラメータをチューニングすることでgettimeofday()のオーバヘッドを改善できます。

sudo sysctl kernel.vsyscall64=1

ちなみに、clock_gettime(CLOCK_MONOTONIC)を利用してしまえば良いじゃん。というツッコミは全くもってその通りでございます。

インラインアセンブラを駆使した組み込み系の爽やかな風をウェブ業界にいながら感じることができるところがYahoo!の楽しいところでございます。

いつか私もインラインアセンブラーマスターになりたいものです。

この辺の話に興味がありましたら、コードの「rdtsc()」という関数から追いかけていただければ幸いです。

HUGETLBFSのサポート

Linux環境では、mmapの性能を生かすためにメモリーファイルシステムのtmpfs/ramfsを利用できます。

メモリーファイルシステムは非常に高速ですが、大容量のメモリーを使うケースではTLB(Transaction Lookaside Buffer) の CPU キャッシュのミスヒットによるコストも課題となります。

このソリューションの1つがhugepageメモリーの利用であり、mdbmではこのファイルシステムに対する実装がされています。

おわりに

いかがでしたでしょうか。

そして、ロックの実装が気になって仕方のない卒業生のエンジニアの皆様懐かしく思っていただけましたでしょうか。

この投稿が一人でも多くのエンジニアの心に響き、Yahoo! JAPANと一緒に仕事をしていただけるエンジニアが増れば幸いでございます。

ここまで読んでいただきありがとうございました。