技術者ブログ

はじめに

JavaのHashMapには特定のbinに要素が集中すること(例えばHashDoS攻撃)によるパフォーマンスの劣化を避ける工夫がされています。このメカニズムはJava7とJava8で大きく変わりました。今回はこの点について詳しく見ていきます。

Java8でHashMapがどう変わったか?

以前こちらのエントリで書いたように、Java7ではHashMapにおいて激しいハッシュの衝突が起こると、ハッシュ計算のロジックそのものが変更されるという機能が実装されていました。これによってオブジェクトに対するハッシュ値自体が変わってくるため衝突は完全に回避され、その後の性能はHashMap本来の高速なものとして保たれます。この機能はデフォルトでは無効で、jdk.map.althashing.thresholdオプションで有効にする形となっていました。

Java8では上記機能は完全に廃止されました。代わりに、HashMap内部のbinにおいて格納される要素の数が増えてきたら、bin内での検索をLinked ListではなくBalanced Treeで行うよう切り替わるようになりました(参照:Oracleのドキュメント/OPENJDKの該当JEP)。この切り替えは自動で行われ、デフォルトで有効になっています。

閾値は8です。つまりあるbinにおいてLinkedListの長さが8になるとリストから木への変更が行われます。ソースコード中ではTREEIFY_THRESHOLDとして定義されています。

Java7では明示的にオプションを指定しないとHashDoS攻撃に対して脆弱でしたが、Java8からはデフォルトでHashDoS攻撃対策がされていると言ってよいでしょう。

閾値の8はどんな値なのか?

閾値である8というのはどの程度のレベルの値なのでしょうか。つまり、リストから木への変更は結構頻繁に発生するものなのか、あるいは殆ど発生しないものなのか、どちらに近いのでしょうか。

HashMapでは1つのbinに多くの要素が格納されてしまう状態を避けるため、自動的に内部のテーブル(binの集合)が要素の数に合わせてどんどん大きくなっていきます。しかしある程度は「1つのbinに複数の要素が格納される状態」が発生します。これは自然な状態です。

閾値の8というのは「ある１つのbinに割り当てられる要素が8個もある状態」を意味します。この規模の要素の混雑は、HashDoS攻撃のようなケースを除いて、自然に発生する可能性はあるのでしょうか。

これを確かめるため、ランダムに生成した長さ80のStringインスタンスをkeyとし、10万要素ほどputしたHashMapで確認してみました。テーブル中の全binについて要素の最大数を調べてみたところ、数回のテストにおいて、ほとんどの場合、5〜6という値になりました。つまり、8は「普通のアプリケーションであれば、ごく稀には発生するかもしれない...」という絶妙な閾値になっていることが確認できました。

ちなみに要素が1つも入っていないbinの割合は全binのうち6〜7割で、要素が1つ以上入っているbinにおける要素の数の平均値は約1.2でした。

この辺についてはソースコードの上の方にコメントで(ポアソン分布に従う等）説明が書いてあるので、興味がある人はぜひ読んでみてください。

Java8とJava7の性能差はあるか?

前回のエントリに書いたように、私たちはCPU使用率の異常に気づき、その原因を突き止めたところそれはハッシュの衝突によるHashMapの性能劣化でした。これはJava8での運用中に起こりました。

先に書いたようにJava8ではbinへの要素の集中が起こると自然にデータ構造が変化し性能劣化を防ぐはずですが、これはあくまでLinkedList(最悪に遅い)がBalanced Tree(LinkedListよりは速いが、HashMapに比べると遅い)になったということであり、HashMapに本来期待される性能に比べると遅いです。そのため目に見えるレベルのCPU使用率の異常が起こっていました。

実はJava7の対策の方が、パフォーマンス的には優秀になる可能性があります。ハッシュ計算のロジックが変わるだけで、性能としてはあくまでHashMapのレベルが保たれるからです。

こちらのJavaの検証コードをJava7と8それぞれで実行してみると、実行速度の差を確認することができます。手元ではJava7で234ms、Java8では1759msかかりました。また、メモリ使用量もJava7の方が優秀で、実行可能となる最低メモリ指定はJava7では-Xmx1300Kですが、Java8では-Xmx6200Kとなりました。

Java8ではこのようにJava7よりも少し性能が劣化していますが、Java7の対策はkeyがStringインスタンスである場合のみであったのに対し、Java8ではすべてのクラスに対応したというのが主な仕様変更の理由のようです。

異常を検知できるか?

ハッシュ値が想定通りにランダムで散らばってくれていれば、あるbinに要素が集中するようなことはなく、HashMapの性能は保たれます。しかしHashDoS攻撃やハッシュ値の計算に偏りが生じてしまう使い方をしている場合、特定のbinに要素が集中し、HashMapの性能が劣化することになります。このような異常な状態を、アプリケーション内で検知することはできるのでしょうか。

HashMapもデータを格納する先であるので、小規模なデータベースだとみなすことができます。SQLを使ってアクセスするようなRDBや、MongoDBなどのNoSQLなど、一般的にデータベースには管理機能が搭載されています。これを利用することで、パフォーマンスの異常を発見したり、全体の状態を把握するための統計情報にアクセスすることができます。

しかし残念ながらJavaのHashMapにはほとんど管理機能らしきものは存在せず、内部のテーブルや各binの状態がどのようになっているか、といった情報について、外部のクラスからはアクセスできません。そのため、普通に考えるとHashMapはブラックボックスとして使用するしかなく、(私たちが経験したように)パフォーマンスの劣化などを引き金に調査が行われることになりそうです。

それではイヤな場合、次の方法を使うと、とりあえず異常な状態を検知するという目的は達成できそうです。(他にもっと良い方法があるかもしれません。)

フィールドに強引にアクセスする方法

リフレクションを利用して通常だとアクセスできないHashMapのtableフィールドにアクセスすることができます。例えば次のようなコードでtableというフィールドにアクセスすることができます。

public static void seeMap( final HashMap map )
{
	try
	{
		Object object = map;
		String fieldName = "table";
		Field field = null;
		Method method = null;
		Class clazz;

		clazz = Class.forName( "java.util.HashMap" );
		field = clazz.getDeclaredField( fieldName );
		field.setAccessible( true );
		object = field.get( object );
		Map.Entry[] table = ( Map.Entry[] )object;
		for( int i = 0; i < table.length; ++i )
		{
			Map.Entry entry = table[ i ];
			if( entry != null )
			{
				if( entry.getClass().toString().indexOf( "TreeNode" ) > -1 )
				{
					System.out.println( "異常を発見" );
				}
			}
		}
	}
	catch( Exception e )
	{
		e.printStackTrace();
	}
}

tableの各要素はbinです。もしbinがnullであれば、そのbinは空であることを意味します。

nullでない場合、そこにあるオブジェクトのクラスがHashMap$Nodeであれば、そのbinはLinked Listとして管理されていることを意味します。この場合はさらにそのオブジェクトのnextフィールドを辿っていけば、binにいくつの要素が格納されているかを調べることができます。

クラスがHashMap$NodeではなくHashMap$TreeNodeの場合、そのbinはBalanced Treeとして管理されています。つまりこれは先に述べた閾値8を超えたことを意味しており、一般的な使い方では起こらない、異常な状態が発生している可能性があります。

この方法は特定のHashMapインスタンスに注目し、そのインスタンスを健全であるかのチェック対象とするような使い方しかできません。そのため、アプリケーション全体で多くのHashMapインスタンスが存在する場合、その中のどれが異常な状態になっているのかを知るには多くのコード変更が必要となり、手間がかかるでしょう。

ヒープダンプからHashMap$TreeNodeを探す方法

他に考えられるのは稼働中のアプリケーションのヒープダンプを取得し、HashMap$TreeNodeのインスタンスが生成されているかどうか、また生成されている場合にはどのくらいの数かを見る方法です。ヒープダンプの取得自体が重い場合もあるため、使いづらい面もありそうですが、アプリケーションを改変せずに、また特定のタイミングで調査するには良い方法かもしれません。

HashDoS攻撃された場合のメモリの状態

HashDoS攻撃を受けると特定のbinだけに要素が集中し、そのbinが木になります。このときでもテーブルは要素の全数に合わせて成長し、binの数は増えます。それらのbinのうち殆どはまったく要素を含まない空のbinとなりますが、1つのbinだけは木としてどんどん成長します。そのため概念としては次のような非常に間の抜けたデータ構造になります。

ひたすら空のbinが無駄に確保される一方、1つのbinからは大きな木が育ちます。

このとき(Java7と8の比較の項で示したように)当然ながらメモリが無駄に使われますが、攻撃として成立するようなレベルではないので、それほど大きな問題はなさそうです。

まとめ

今回はJava8以降のHashMapがハッシュの激しい衝突の際にどのような挙動を示すのかについて調査しました。普段何気なく使っている基本的なクラスも、なかなかに奥が深いようです。