シングルSQLクエリ -> MSA APIへの変換における性能低下

最近、モノリシックアーキテクチャ構造のレガシーシステムをMSA構造に移行するリプラットフォームを実施しました。既存のレガシーシステムは、複数のサブドメインに該当するテーブルが単一のクエリで多数のJoinによって結合されており、「たった一つのクエリ」で結果を得ることができたため、性能は非常に優れていましたが、再利用性および保守性においては最悪の構造でした。予約、決済、精算、商品など、各サブドメインをサービスに分け、「多数のAPI呼び出し」でリクエストを処理するように変換した結果、再利用性および保守性は向上しました。しかし、SQL Joinを使用していたものを多数のAPIに置き換えたことで、処理の断片化およびネットワーク時間により性能が低下し、この解決が新たなリプラットフォームの課題点となりました。

Java Stream -> ParallelStreamによる性能改善

単一クエリでは、Join一つだけで複数のテーブルに分散された情報を一つのDtoに集めて返却できます。しかし、各テーブルをドメインベースで予約サービス、アカウントサービスなどに分けた場合、単純だったJoin文は、それぞれテーブルに該当する多数のAPIを呼び出した後、一つのDtoにIDベースで結合する作業が必要になります。このような作業でIDベースのJoinをプログラムで実装する際、私は個人的に性能のためにハッシュジョイン戦略と類似して記述することがありますが、これは各API結果のHashMapを必要とすることを意味します。

ListからHashMapへの変換は簡単ですが、Listのデータ量が非常に膨大である場合、各ドメインに該当するテーブルごとにHashMap変換を行うだけでも数秒の時間を消費するため、この時間を短縮するためにStreamからParallelStreamへの変換作業を行いました。正直に言うと、速いという事実一つだけで、ジュニアだった私には「なぜ使わない手があるのか？」と思うほどの存在でした。性能は非常に速くなり、長い間問題なく動作しているように見えましたが、予期せぬいくつかの問題に直面することになります。

ParallelStream

ParallelStreamはJava 8で導入された、マルチスレッドプログラミングを非常に簡単に活用できるようにするツールです。大学時代もマルチスレッドが最も複雑で難しかったのですが、これをたった一つのコードで簡単に使えるようにしてくれるというのは、スレッド管理が不便だった私にとって非常に魅力的でした。また、他のウェブページで従来のfor-each、Stream、ParallelStreamの性能比較を見ると、当然のことながら、信じられないほど高速な性能を提供していることがわかります。

ForkJoinPool: ParallelStreamのスレッド管理

スレッド管理が簡単になった理由は、既存のJavaで使用されていたスレッド管理方式を拡張したForkJoinPoolという管理方式を使用しているためです。名前の通りFork + Joinを通じて、どのような複雑な作業も小さな単位に細分化し、複数のスレッドが分担して作業した後、完了した結果を一つの結果に結合します。これがParallelStreamの方式でもあります。

ExecutorService (従来)

• 1つのキュー (1: メインキュー)
• スレッドプールで待機しているスレッドに、メインキューの作業(Job)を割り当て

ForkJoinPool (新規, Fork + Join)

• 2つのキュー (1: メインキュー, 2: ExecutorServiceキュー (ワーカーキューまたはローカルキュー))
  • ForkJoinPool = キューが追加されたExecutorService実装体
• スレッドプールで待機しているスレッドにメインキューの作業(Job)を割り当て、さらに追加のプロセスが存在
  • Fork: 該当スレッドは、割り当てられた作業(Job)を実行可能な小さな単位の作業に分割
  • Steal: 一つのスレッドが多数の作業(Job)負担を抱えることになった場合、他のスレッドがその作業を分担して実行
  • Join: 細分化され、複数のスレッドで実行完了した作業結果は、分割されたスレッドで再び結合されて返却

ParallelStreamは、SpliteratorとForkJoinPoolに基づいてFork + Joinを通じて作業を小さな単位に分割した後、リアルタイムでいずれかのスレッドに作業負担（Workload）が集中しないように、複数のスレッドが小さな単位の作業を互いに分担して効率的にリソースを使用します。結果として、より速く結果を返却するようになり、ParallelStream == 性能と認識される理由です。

HashMap & ParallelStream使用時の無限ループ問題

リハッシュ (Rehashing)

ParallelStreamを通じてサービス性能改善を達成した後、かなりの時間が経過してから突然、当該サーバーインスタンスのCPUが75%を超え、長時間下がり続けないというオンコールが発生しました。占有率が長時間75%から下がらないため、無限ループに陥ったと見て、スレッドダンプを分析したところ、parallelStreamから割り当てられたスレッドがブロック状態で停止しているのを発見しました。

問題のロジックは、ParallelStream内部でHashMapのput関数を使用した部分でした。

Map<Integer, Boolean> result = new HashMap<>();
sampleList.parallelStream().forEach(each ->
  result.put(each.getId(), isSample)
);

簡単に考えると、ListではなくMapであるため、注入される順序も関係なく、値がうまく入るように思えます。しかし、HashMapにはリハッシュがあるという、本当に基本的なことを見落としていました。 HashMapはKey-Valueペアを注入(put)する際に、以下の過程を経て行われます。

1. 新たに追加するKeyに対するハッシュを生成し、
2. ハッシュテーブルインデックスでfor-loopを通じて存在有無を判断した後、
3. 該当ハッシュKeyにポインターを通じてValueを格納します。
4. 特定のハッシュKeyにポインターで接続されたValueの数が一定数を超えると、リハッシュを実行し、
   • ハッシュインデックスを分割し、Valueを再格納します。

リハッシュ: 競合状態 (Race Condition)

上記プロセス中の3. 新しいValueをポインターで接続する部分と4. リハッシュの2つの部分ではポインターを変更しますが、標準のHashMapの場合、このポインター変更部分がスレッドセーフではありません。したがって、複数のスレッドが3番と4番を同時に実行しようとすると、つまり、同じハッシュインデックスのポインターを変更しようとすると問題が発生する可能性があります。2つのスレッドが同じハッシュKeyに対するポインターを再設定する過程で互いに絡み合い、ポインター間にサイクルが発生します。3番、4番ともにput実行時に行われるロジックであり、ここで生じたポインターサイクルにハッシュテーブルインデックスに対するfor-loopの存在有無の検索が入り込むことで、無限ループに陥ったのです。

HashMapとParallelStreamを同時に使用した場合、このような競合状態（Race Condition）による無限ループ問題だけでなく、実際に正常に実行されたとしても、HashMapにはいくつかのKeyが失われるケースも発生します。これもまた、多数のスレッドがハッシュKeyにポインターでValueを同時に注入する際に、一部のポインターのみが正常に割り当てられ、残りは無視される問題で発生します。これにより、新しいKeyを10000個putで注入したのに、実際にHashMapに保存されたKeyは10000個より少ない、という驚くべき状況も発生します。

結論

JavaのParallelStream内部でスレッドセーフではない何らかの操作（本記事ではHashMapのput）を実行すると、競合状態（Race Condition）が発生し、いくつかのスレッド操作が他のスレッドによって無視され、予期せぬ結果を生じます。HashMapの場合、以下の問題が発生します。

• ハッシュKeyに接続されたValue間でポインターサイクルが発生し、for-loopによる存在有無の確認時に無限ループに陥る。
• 10000回のput操作を実行しても、いくつかのValueポインターの注入が無視され、結果のHashMapサイズが10000未満になる。

当時までParallelStreamに起因する問題が多かったため、オンコール解決のためにサービス全体のロジックでParallelStreamが使用されている部分をすべて排除しました。上記の問題を解決するには、HashMapをConcurrentHashMapに置き換えるだけでも可能です。もちろん、ParallelStreamの動作原理はSpliteratorとForkJoinPoolに基づいているため、分割統治（Divide-and-Conquer）という基本原則である分割（split）と結合（merge）の作業にメモリ、CPUリソースの消費割合が大きくなる可能性があります。したがって、ループ回数が数十万、数百万件にも及ぶユースケースが存在する場合は、必ずストレステストが必要となるでしょう。

• https://hamait.tistory.com/612
• https://blog.naver.com/tmondev/220945933678
• http://www.h-online.com/developer/features/The-fork-join-framework-in-Java-7-1762357.html
• https://medium.com/@itugs/custom-forkjoinpool-in-java-8-parallel-stream-9090882472db
• https://java-8-tips.readthedocs.io/en/stable/parallelization.html#conclusion