はじめに

DBに変更を加え、それを別DBに移行するような場合、簡単な方法としてはdumpして流し込むことで反映されられます。
ただし、元々のデータ量が多くて差分が少ない場合には、全て入れ直そうとすると時間がかかるので、差分のあるテーブルやデータに対してのみ変更をかけると良さそうです。

差分のあるデータの特定にあたって、軽量なハッシュ関数が使えるとより処理が早くなると思われる箇所があったので、この記事では標準関数にないFNVのハッシュ関数をUDF(ユーザー定義関数)として組み込んで使えるようにしてみます。

差分のある箇所の特定

テーブル単位でのハッシュは以下のようにして取れるので、DB間でハッシュ値が違うテーブルのみをdumpの対象にすれば処理が少なくて済みます。

CHECKSUM TABLE table_1, table_2, ... , table_n;

行単位でのハッシュは例えば以下のようにして取れるので、DB間でidなどのプライマリキーに対してハッシュ値が違う行のみを変更対象にすれば処理が少なくて済みます。
特に、行単位でのデータ量が大きい場合には、元のデータを全件そのまま取得して比較するよりもDBとの通信にかかるリソースが少なくて済みます。

SELECT id, MD5(CONCAT_WS(",", col1, col2, ... , coln)) hash FROM table_name;

改善ポイント

この行単位のハッシュ化の方法について、

md5より軽量なハッシュ関数が使えないか
わざわざ文字列結合せずに直接引数として渡せないか

という点が気になりました。

前者に関しては、より出力される桁数が少ない・処理が少ないアルゴリズムに置き換えられるならそちらを使った方が効率が良さそうです。
後者に関しては、一度全てを連結した文字列を作ってからmd5関数に渡しているので、この文字列連結の手順がなければより効率的に処理できそうです。

ただし、標準で実装されている関数にはmd5より軽量そうなハッシュ関数や可変長の引数をまとめて受け取ってくれる関数が実装されていないようすなので、今回はFNVというハッシュ関数をMySQLのUDF(ユーザー定義関数)として追加してどのくらい効果があるか見てみます。

FNVを選んだ理由は、phpでの速度比較記事で速度面で優位そうだったのと、擬似コードがやたら短くてよさそうという雑な理由です。

FNV関数の導入

MySQLでのFNVの実装について調べると以下のような内容が見つかりました。

特に2つ目の内容に関しては、引数を複数扱えるように実装しているようで自分が出した２つの要件を両方とも満たせるため、今回は2つ目の内容をやってみることにしました。

UDFの追加でやることはざっくり

https://dev.mysql.com/doc/refman/5.6/ja/adding-udf.html に従って実装する
- 関数 xxx を実装するとき、C言語にて xxx xxx_init (xxx_deinit) を実装する
- MySQL公式のLOOKUP関数実装サンプルを見るとわかりやすいかも
MySQLのプログラムをリンクしてコンパイル、出来上がったsoファイルを指定ディレクトリに入れる
MySQLでsoファイルを指定して関数を登録する

の3ステップです。

今回は上記記事の内容にある通り、Maatkitというツール内で実装されているものを利用しました。
以下はMacでの手順です。brewでインストールしたMySQLに組み込んでいるので、各自のマシンに合わせてバージョンやパスを適宜置き換えてください。

# DL&解凍
curl -0 https://storage.googleapis.com/google-code-archive-downloads/v2/code.google.com/maatkit/maatkit-7540.tar.gz > maatkit-7540.tar.gz
tar -zxvf maatkit-7540.tar.gz
cp maatkit-7540/udf/fnv_udf.cc ./
# コンパイル&配置
gcc -fPIC -Wall -I/usr/local/Cellar/mysql@5.6/5.6.43/include/mysql -dynamiclib -o fnv_udf.so fnv_udf.cc -lstdc++
cp fnv_udf.so /usr/local/Cellar/mysql@5.6/5.6.43/lib/plugin/
# 関数の読み込み
mysql mysql -e "CREATE FUNCTION fnv_64 RETURNS INTEGER SONAME 'fnv_udf.so'"

MacとLinuxでビルドオプションが違うので、例えばMySQLの公式dockerイメージ内でビルドする場合は以下のようにします。

gcc -fPIC -Wall -I/usr/include/mysql -shared -o fnv_udf.so fnv_udf.cc
cp fnv_udc.so /usr/lib/mysql/plugin/

MySQLでの読み込みが完了すると、 FNV_64 関数が使用可能になります。

mysql> select fnv_64();
ERROR 1123 (HY000): Can't initialize function 'fnv_64'; FNV_64 requires at least one argument
mysql> select fnv_64(1);
+----------------------+
| fnv_64(1)            |
+----------------------+
| -6320923009900088257 |
+----------------------+
1 row in set (0.01 sec)

mysql> select fnv_64(null);
+----------------------+
| fnv_64(null)         |
+----------------------+
| -5259373969131113000 |
+----------------------+
1 row in set (0.00 sec)

mysql> select fnv_64("hoge", "fuga");
+------------------------+
| fnv_64("hoge", "fuga") |
+------------------------+
|     540658518371715184 |
+------------------------+
1 row in set (0.01 sec)

今回使わせてもらった実装の特徴として、複数引数が扱えることだけでなく、 NULL 値も扱えるようになっています。
記事冒頭に書いたような CONCAT_WS 関数を使用した場合、NULLが無視される挙動になるため、場合によっては空文字と被らない別の文字として扱うように回避する必要があります。このUDFではNULLの代わりとして 0x0a0b0c0d という値が指定されています。

#define HASH_NULL_DEFAULT 0x0a0b0c0d

ちなみに、引数を何も指定しなかった場合に表示されている FNV_64 requires at least one argument という文字列も、UDFを作る上での必須実装関数の fnv_64_init にて指定されている文字列です。組み込んだものがちゃんと実装通りになっている実感があっていいですね。

my_bool
fnv_64_init( UDF_INIT* initid, UDF_ARGS* args, char* message ) {
   if (args->arg_count == 0 ) {
      strcpy(message,"FNV_64 requires at least one argument");
      return 1;
   }
   initid->maybe_null = 0;      /* The result will never be NULL */
   return 0;
}

速度比較

MySQLのサンプルデータの sakila (レンタルビデオ店風のデータ)から良さげなテーブルを使って、よさげな件数の実験用テーブルを作って実験してみました。 film_text というテーブルが多少バラツキのある文字数が入っていて1000レコードあったので、このテーブル自身を CROSS JOIN して 1,000,000 レコードのテーブルを用意しました。

mysql> select table_name, table_rows, avg_row_length from information_schema.tables where table_schema = "sakila" and table_type = 'BASE TABLE';
+---------------+------------+----------------+
| table_name    | table_rows | avg_row_length |
+---------------+------------+----------------+
| actor         |        200 |             81 |
| address       |        603 |            163 |
| category      |         16 |           1024 |
| city          |        600 |             81 |
| country       |        109 |            150 |
| customer      |        599 |            136 |
| film          |       1000 |            196 |
| film_actor    |       5462 |             35 |
| film_category |       1000 |             65 |
| film_text     |       1000 |            180 |
| inventory     |       4581 |             39 |
| language      |          6 |           2730 |
| payment       |      16086 |             98 |
| rental        |      16005 |             99 |
| staff         |          2 |          32768 |
| store         |          2 |           8192 |
+---------------+------------+----------------+

mysql> select * from film_text limit 5;
+---------+------------------+-----------------------------------------------------------------------------------------------------------------------+
| film_id | title            | description                                                                                                           |
+---------+------------------+-----------------------------------------------------------------------------------------------------------------------+
|       1 | ACADEMY DINOSAUR | A Epic Drama of a Feminist And a Mad Scientist who must Battle a Teacher in The Canadian Rockies                      |
|       2 | ACE GOLDFINGER   | A Astounding Epistle of a Database Administrator And a Explorer who must Find a Car in Ancient China                  |
|       3 | ADAPTATION HOLES | A Astounding Reflection of a Lumberjack And a Car who must Sink a Lumberjack in A Baloon Factory                      |
|       4 | AFFAIR PREJUDICE | A Fanciful Documentary of a Frisbee And a Lumberjack who must Chase a Monkey in A Shark Tank                          |
|       5 | AFRICAN EGG      | A Fast-Paced Documentary of a Pastry Chef And a Dentist who must Pursue a Forensic Psychologist in The Gulf of Mexico |
+---------+------------------+-----------------------------------------------------------------------------------------------------------------------+
5 rows in set (0.01 sec)

mysql> show create table film_text;
+-----------+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| Table     | Create Table                                                                                                                                                                                                                                          |
+-----------+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| film_text | CREATE TABLE `film_text` (
  `film_id` smallint(6) NOT NULL,
  `title` varchar(255) NOT NULL,
  `description` text,
  PRIMARY KEY (`film_id`),
  FULLTEXT KEY `idx_title_description` (`title`,`description`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 |
+-----------+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
1 row in set (0.00 sec)

mysql> CREATE TABLE `film_text_cross` (
    ->   `film_id1` smallint(6) NOT NULL,
    ->   `title1` varchar(255) NOT NULL,
    ->   `description1` text,
    ->   `film_id2` smallint(6) NOT NULL,
    ->   `title2` varchar(255) NOT NULL,
    ->   `description2` text,
    ->   PRIMARY KEY (`film_id1`,`film_id2`)
    -> ) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4
    -> ;
Query OK, 0 rows affected (0.09 sec)

mysql> insert into film_text_cross (select t1.film_id film_id1, t1.title title1, t1.description description1, t2.film_id film_id2, t2.title title2, t2.description description2 from film_text t1 cross join film_text t2);
Query OK, 1000000 rows affected (42.75 sec)
Records: 1000000  Duplicates: 0  Warnings: 0

それなりのデータが準備できたので、以下の3種類のクエリを投げてみます。

# md5 + concat_ws
select film_id1, film_id2, md5(concat_ws(",", film_id1, title1, description1, film_id2, title2, description2)) hash from film_text_cross;
# fnv_64 + concat_ws
select film_id1, film_id2, fnv_64(concat_ws(",", film_id1, title1, description1, film_id2, title2, description2)) from film_text_cross;
# fnv_64
select film_id1, film_id2, fnv_64(film_id1, title1, description1, film_id2, title2, description2) hash from film_text_cross;

結果はこのようになりました。

クエリ	実行時間
md5 + concat_ws	1.64 sec
fnv_64 + concat_ws	1.97 sec
fnv_64	1.85 sec

予想に反してUDF使った方が若干遅くなってしまいました...。

拡張の関数の呼び出しが遅いのか、最適化不足なのかもしれないと思い、
とりあえす最適化オプション -O2 をつけてコンパイルし直してもう一度やってみました。

クエリ	実行時間
md5 + concat_ws	1.62 sec
fnv_64 + concat_ws	1.44 sec
fnv_64	1.32 sec

期待していた通りに、UDFをうまく使った方がより実行時間が短くなるようになりました。
最適化については、md5のようなアルゴリズムは同じビット演算を数十回繰り返し行ったりしている箇所もあったりするんですが、
いつしかマイニングツールのハッシュ値計算の処理を覗いた時に #pragma unroll みたいな記述を見たことがあり、最適化をかけられるポイントがあるみたいです。
FNVみたいに処理自体が少ないものでも最適化かけないとそれより遅くなることもあるんだなと思いました。

さいごに

より軽量な関数を組み込むことで高速化が図れそうなことがわかりました。
自作関数の実装は、簡単な処理の関数１つ追加する程度なら 100 行ほどで実装できるようで、意外と敷居が低いのかなという印象を持ちました。
実際に運用することを考えると素人のポインタ操作によって影響が出るかもしれないのでそこの考慮は必要ですが...。

MySQLでFNVハッシュ関数を組み込んで使う