データ分散とインデックス最適化のためのハッシュ関数の利用

はじめに

こんにちは、piarra です。みなさん、意識は高まっていますか？私は上々です。
という書き出しをやめたくてやめられなかったのが心残りです。

昨年までは、Casual Trackで寄稿させていただいていましたが、今年はYAPCで話したこともあり、Hacker Trackに初挑戦させていただきます。得意のMD5暗算法とその習得法について解説したいと思っていたところですが、より日常に役立つ方がよいかと思い、MD5やその他のハッシュ関数の活用法について少し触れてみたいと思います。

データサンプル

DBMSを考慮せず、以下のようなデータサンプルがあったと考えてみましょう。

+----+-----------------------+
| id | url                   |
+----+-----------------------+
|  1 | http://www.google.com |
|  2 | http://www.yahoo.com  |
|  3 | http://www.bing.com   |
|  4 | http://www.baido.com  |
|  5 | http://www.blekko.com |
|  6 | http://www.naver.com  |
+----+-----------------------+

上のデータはどこにでもありそうなURLの一覧です。データ管理上、通常なんら問題を感じることはありませんが、インデックスの立場から考えると、「http：//www.」までの11文字が全データで共通しており、前方からのインデックス作成が不効率であることが考えられます。100万から億単位の大規模なデータを扱う時代においては、あまりにも不効率でDBMSによってはインデックスに偏りができてしまったり、インデックスがほとんど機能しない可能性が推測されます。

インデックス最適化のためのハッシュ関数の利用

MySQLにも標準で実装されているMD5関数を利用すると、このデータをもう少しインデックス効率のよいデータに変えることができます。
SQLで書くと以下のような形です。

INSERT INTO urls (url, digest) 
VALUES ('http://www.google.com', LEFT(MD5('http://www.google.com'), 8));

こうすることで、インデックス効率のよいデータに変わりました。

+----+-----------------------+----------+
| id | url                   | digest   |
+----+-----------------------+----------+
|  1 | http://www.google.com | ed646a33 |
|  2 | http://www.yahoo.com  | c5f7ac7a |
|  3 | http://www.bing.com   | 9cbc5ee4 |
|  4 | http://www.baido.com  | 05c3f985 |
|  5 | http://www.blekko.com | 39ce0427 |
|  6 | http://www.naver.com  | 52b9e317 |
+----+-----------------------+----------+

検索する際には以下のようなSQLを書くとよいですね。

SELECT * FROM urls 
 WHERE digest = LEFT(MD5('http://www.google.com'), 8) AND url = 'http://www.google.com';

urlではなく、digestにインデックスをはることで、効率よく分散しデータ量的にもコンパクトなインデックスを生成することができます。
※MD5は安全ではないので、SHA1を使うべきだということをおっしゃる方がいるかもしれません。しかしながら、ここで重要なのはハッシュ関数のセキュリティではなく、ハッシュ関数の計算コストと一様性(ハッシュ関数の出力が出力範囲全体に渡り一様に分布するという性質)であり、よりパフォーマンスのよいMD5がチョイスとしては適切と考えています。

より効率よくインデックスするために

インデックスデータはメモリ効率が重要ですから、データ件数が増えてくると、上記のようなchar(8byte)のインデックスは少しメモリ効率が悪いように感じるケースがでてきます。そういった場合は、int型(4byte)に変換して入れるのが望ましいです。
※binary型も考えられますが、メンテナンス効率の面で、ここではint型を推奨します。

INSERT INTO urls (url, digest)
VALUES ('http://www.google.com', CONV(LEFT(MD5('http://www.google.com'), 8), 16, 10));

検索する際には以下のようなSQLを書くとよいですね。

SELECT * FROM urls 
 WHERE digest = CONV(LEFT(MD5('http://www.google.com'), 8), 16, 10) AND url = 'http://www.google.com';

しかしながら、ここまで来ると、ちょっとSQLにアレルギーを感じる人も増えてくるでしょう。ここまでの演算をDBサーバーに委ねてしまってよいのかと少し心配にもなりますし、perlハッカーやcasualなperlerならperlでなんとかしたいとも感じるはずです。

use Digest::MurmurHash

Austin Appleby氏により考案されたMurmurHashは、衝突困難性と一様性に優れ、かつ計算コストがMD5等よりも圧倒的に優れたハッシュ関数でその出力範囲はint型の範囲に限定されています。
MurmurHashはToru Maesaka氏によりPerlのXSモジュールDigest::MurmurHashとして公開されており、カジュアルに利用することができます。
上記のようなINSERTをPerlを用いて行うと以下のような形になります。すっきりしますね。

use DBI;
use Digest::MurmurHash qw(murmur_hash);
my $url = 'http://www.google.com';
my $dbh = DBI->connect('dbi:mysql:test');
my $sth = $dbh->prepare("INSERT INTO urls (url, digest) VALUES (?, ?)");
$sth->execute($url, murmur_hash($url));

まとめ

今回は特にインデックス効率の悪いデータを例にとって、効率の良いインデックスについて考えました。実際には、インデックス効率の良いデータの方がむしろ少ないものです。大規模データを効率よく管理するためには、ハッシュ関数を用いたdigest値を使うのは定石と言えるかもしれません。
また、ハッシュ関数は、MD5という基本的なものから、MurmurHashといった特殊なものまで様々です。インデックスをint型に収めたいだけであれば、MD5の部分データでも十分に事足りる可能性があります。MySQL等のDBMS単体で利用できるというメリットも大きいでしょう。データの分散性や計算コストを優先するのであれば、MurmurHashやより簡易的な独自のハッシュ関数を用いるのもありかと思います。この記事を通して、ハッシュ関数の可能性について、少しでも感じてもらえたら嬉しいです。