はじめに
フューチャーアーキテクト Advent Calendar 2016のテーマを考える時期になりました。大規模データの分散処理に興味があるので、「分散処理」をキーワードにテーマを探していました。
- 大規模分散処理と言えば、スケールアウトアーキテクチャ
- スケールアウト構成というとAmazon Dynamoを使いたいという人がいたな…。調べてみるか。
- 巨大なKey-Valueを管理するためには分散ハッシュテーブル(Distributed Hash Table)がコア技術 参考資料
- ハッシュ関数自体はMD5アルゴリズム使っていて、2^128個(128bit)のハッシュ値が扱えると。衝突（別のインプットに対して同じハッシュ値を利用してしまう）は実務的にはあり得ないと。ゼロではないのでセキュリティ目的では脆弱性として扱われている。参考資料:wiki
- とりあえずMD5の適用例をいろいろ検索していたら、OracleにあるSQLIDについてもMD5を利用しているのが分かりました。そういえば、OracleにはSQLIDというSQL識別文字があったけど、あれも衝突しないのかちょっと疑問に思っていたんだよね…。
というわけで、当初の思いから大きく外れてテーマをOracleのSQLIDとしました。
別にOracleに興味がない方もアルゴリズムの解説として読んでいただければと思います。
OracleにおけるSQLIDとは
Oracleは実行されたSQL文を13桁の「文字列」で管理しています。この文字列のことをSQLID（要するにSQL識別するIDです)と呼ばれています。SQL実行統計の確認、パフォーマンス確認、実行されたSQL全文の確認などあらゆるところでSQLIDは利用されます。
SQLがキャシュされる共有プール内のSQLIDは以下のようにV$SQLを利用して確認できます。
SQL> select a.SQL_ID,substr(a.SQL_TEXT,1,40) from v$sql a where rownum < 5;
SQL_ID SUBSTR(A.SQL_TEXT,1,40)
------------- ----------------------------------------
7h35uxf5uhmm1 select sysdate from dual
a4krtprr5b6fm select * from dba_users a order by a.USE
f6p0p23pz3h4v select A.* from DBA_USERS A where 1 =
656rwmhbk7h4w select SQL_TEXT, SQL_FULLTE
SQLID(SQL_ID)がSQLごとに付与されているのが分かります。
1行目のSQLを具体的な例として以降、使用していきますのでSQLIDを覚えておいてください。
SQLテキスト：select sysdate from dual
SQLID：7h35uxf5uhmm1
SQLIDについて、今のところ言えるのは以下です。（コレが結論ではないので最後まで読んでください）
- 13ケタの文字列である。
- [0-9]と[a-z]の組み合わせからなっている。10+26=36種類の文字列からなっている。
- 組み合わせとしては、13^36個ありそう。
SQLIDはどのように求めることができるのか
MD5関数でハッシュ値を求める
前から疑問だったのですが、ググると素晴らしい解説ページがありました。神解説です。
All These Oracle SQL Statement
まず、SQLIDはMD5を利用しているのが分かりますが、そこから具体的にどのようにSQLIDを求めるのかを上記サイトを参考にしつつ、わかりやすいようにコメントを加えて解き進めていきます。
まずSQL文をmd5sumコマンドを利用してハッシュ値を求めます。shellコマンドで実施していますので、SQL文の末尾にはNULL終端を付加しています。md5sumの戻り値の128bitは16進文字列([0-9][a-f])を使うと4bitを表記できるので32文字となります。
$ cat /etc/redhat-release
Red Hat Enterprise Linux Server release 6.6 (Santiago)
$ echo -en 'select sysdate from dual\x00'>a.txt
$ md5sum a.txt
abd4dbb3096b15f1ebba0c78614ea88b a.txt
Oracle 9iまで利用されていたHASH_VALUE
SQLIDの話をする前に、「HASH_VALUE」というSQL識別IDについてみていきます。HASH_IDはOracle 9iまで利用されていました。「SQLID」は10gから利用されています。なぜHASH_VALUEからSQLIDに切り替わったのかをウォーミングアップとしてみていきます。参考サイトには以下のように書かれています。
HASH_VALUEはMD5の末尾4バイトを利用する。
なんでこんなの知ってるんだよと思いますが、これはマニアの間では既に知られた話のようです。実際にOracleで使われているHASH_VALUEと合わせて、16進表記の値を求めておきます。
select a.SQL_ID,a.HASH_VALUE,to_char(HASH_VALUE,'FMXXXXXXXX') HASH_HEX,substr(a.SQL_TEXT,1,40) from v$sql a where a.SQL_ID ='7h35uxf5uhmm1';
SQL_ID HASH_VALUE HASH_HEX SUBSTR(A.SQL_TEXT,1,40)
------------- ---------- --------- ----------------------------------------
7h35uxf5uhmm1 2343063137 8BA84E61 select sysdate from dual
この結果と、md5sumの戻り値を比較していきます。
- md5sum戻り値の末尾4バイト →[614ea88b]
- HASH_VALUEの16進表記(HASH_HEX) →[8BA84E61]
md5アルゴリズムではエンディアンで扱われるためリトルエンディアン(Linux)では(32bit=4byte)のワード長ごとに反転させる必要があります。参考
[8B A8 4E 61]これを反転させると[61 4E A8 8B]となり、md5sumの値と一致しました。
ここでのポイントはHASH_VALUEは4バイトです。つまり、2^32=4,294,967,296個存在することになるのですが、**40億という数値だとまったく異なるSQL文が同一のHASH_VALUEとなってしまう（衝突）という可能性があるのではないかという点で問題がありました。**そのためOracle 10gからSQLIDを利用するように変更になりました。
実際問題になったのでしょうか…。当時を知る人に聞いてみたいものです。
Oracle 10gから利用されているSQLID
次にもともとやりたかったSQLIDについてみていきます。参考サイトには以下のように書かれています。
SQLIDはMD5の末尾8バイトを利用する。
なんでこんなの知ってるのですかね。これもマニアの中では知られた話なのでしょうか。
さておきmd5sumの値からSQLIDを作成していきます。
- md5sum戻り値の末尾8バイトを取得 → [ebba0c78 614ea88b] ※4バイトで区切ります。
- エンディアンを考慮して反転 →[780cbaeb 8ba84e61] ※先ほどと同じく4バイト単位反転させです。
ここで求めた値をビット変換(2進数)します。
0x780cbaeb8ba84e61 =
0b111100000001100101110101110101110001011101010000100111001100001
この2進値を右から5ビットごとに区切っていきます。最後（一番左）は4ビットになります。
全部で13個のに分割できます（SQLIDが13文字なのはここから来ています）
5ビットなので、32種類の値を取りうることになります。
0111 10000 00011 00101 11010 11101 01110 00101 11010 10000 10011 10011 00001
後で詳細を補足しますが、32種類のマッピングテーブルは以下になります。
**なんでこんなの知ってるのでしょうか？**output(SQLID)が分かるので推測できなくはないのですが…。
[0-9][a-z]だと本来36文字ですが5ビット32文字のため4文字分多いため「e, i, l, o」が無いです。なぜこれを選んだかは謎ですね。
| 2進数 | 10進数 | 文字列 | 2進数 | 10進数 | 文字列 | 2進数 | 10進数 | 文字列 |
|---|---|---|---|---|---|---|---|---|
| 00000 | 0 | 0 | 01011 | 11 | b | 10110 | 22 | q |
| 00001 | 1 | 1 | 01100 | 12 | c | 10111 | 23 | r |
| 00010 | 2 | 2 | 01101 | 13 | d | 11000 | 24 | s |
| 00011 | 3 | 3 | 01110 | 14 | f | 11001 | 25 | t |
| 00100 | 4 | 4 | 01111 | 15 | g | 11010 | 26 | u |
| 00101 | 5 | 5 | 10000 | 16 | h | 11011 | 27 | v |
| 00110 | 6 | 6 | 10001 | 17 | j | 11100 | 28 | w |
| 00111 | 7 | 7 | 10010 | 18 | k | 11101 | 29 | x |
| 01000 | 8 | 8 | 10011 | 19 | m | 11110 | 30 | y |
| 01001 | 9 | 9 | 10100 | 20 | n | 11111 | 31 | z |
| 01010 | 10 | a | 10101 | 21 | p | - | - | - |
上記のマッピングテーブルを利用して先ほど区切った13個の２進数を順番に並べて13個の文字列を組み立てます。
| md5sumで求めた2進数 | 10進数 | 文字列 |
|---|---|---|
| 0111 | 7 | 7 |
| 10000 | 16 | h |
| 00011 | 3 | 3 |
| 00101 | 5 | 5 |
| 11010 | 26 | u |
| 11101 | 29 | x |
| 01110 | 14 | f |
| 00101 | 5 | 5 |
| 11010 | 26 | u |
| 10000 | 16 | h |
| 10011 | 19 | m |
| 10011 | 19 | m |
| 00001 | 1 | 1 |
組み立てた文字列：7h35uxf5uhmm1
この文字列は、OracleでSQLIDと一致しているのが分かります。すなわちSQLIDはMD5関数を利用しているのが分かりました。
ここまでで、SQLIDがどのように作成されるかを見ていくことが出来ました。
SQLIDは衝突が発生する可能性はあるのか
ここでようやく当初の目的であるOracleのSQLIDは全く別のSQL文で同一のIDをとる可能性があるのかというのを検討できることになります。
今まで見てきたように「SQLIDはMD5の末尾8バイトを利用する」というロジックで作成されていました。8バイトの取りうる範囲は2^64となります。
この数値が現実的には衝突の発生しない必要十分な値であることが分かります。参考
64ビット（英: 64-bit）は、連続した64個（桁）のビット（8オクテット）であり、バイナリで最大18,446,744,073,709,551,616(16E)までの数を表現できる。
おまけ
先ほどSQLIDを作成する際に利用するマッピングテーブルに「e, i, l, o」は存在していませんでした。約800,000個のSQLが保存されていた実際に業務で利用されている環境を見てみたのが以下の結果になります。
select b."character",count(*)
from
(
select distinct a."keta",a."character"
from (
select '01' "keta" ,substr(sql_id,1,1) "character" from dba_hist_sqltext
union all
select '02' "keta" ,substr(sql_id,2,1) "character" from dba_hist_sqltext
union all
select '03' "keta" ,substr(sql_id,3,1) "character" from dba_hist_sqltext
union all
select '04' "keta" ,substr(sql_id,4,1) "character" from dba_hist_sqltext
union all
select '05' "keta" ,substr(sql_id,5,1) "character" from dba_hist_sqltext
union all
select '06' "keta" ,substr(sql_id,6,1) "character" from dba_hist_sqltext
union all
select '07' "keta" ,substr(sql_id,7,1) "character" from dba_hist_sqltext
union all
select '08' "keta" ,substr(sql_id,8,1) "character" from dba_hist_sqltext
union all
select '09' "keta" ,substr(sql_id,9,1) "character" from dba_hist_sqltext
union all
select '10' "keta" ,substr(sql_id,10,1) "character" from dba_hist_sqltext
union all
select '11' "keta" ,substr(sql_id,11,1) "character" from dba_hist_sqltext
union all
select '12' "keta" ,substr(sql_id,12,1) "character" from dba_hist_sqltext
union all
select '13' "keta" ,substr(sql_id,13,1) "character" from dba_hist_sqltext) a
) b
group by b."character"
order by 1;
char COUNT(*)
---- ----------
0 13
1 13
2 13
3 13
4 13
5 13
6 13
7 13
8 13
9 13
a 13
b 13
c 13
d 13 ←「e」がない
f 13
g 13
h 12
j 12 ←「i」がない
k 12
m 12 ←「l」がない
n 12
p 12 ←「o」がない
q 12
r 12
s 12
t 12
u 12
v 12
w 12
x 12
y 12
z 12
この結果から以下が分かります。
- 「e, i, l, o」は確かに使われていない。
- 1番先頭の文字だけ4ビットのため、文字の範囲が[0-9][a-g]となっている。
終わりに
OracleのSQLIDを求めるアルゴリズムについてみていきました。こういうちょっとしたところを少し興味を持って調べるだけで知識の幅が広がります。当記事がその助けになればと思います。
あと、もしわかる方がいたら以下について誰か教えていただけると嬉しいです！
- 本来であればMD5は128bitの値を戻すのですが、SQLIDはMD5の末尾8バイト(64bit)を利用しています。この範囲で本当に一様に分布されているのでしょうか？
- 「e, i, l, o」が使われていないのはなぜ。
それではまた！