0 から 1 までのビジネス並行フレームワークシリーズの設計:
Phoenix は、ビジネス並行フレームワークのための有向非巡回グラフを自動的に構築するためのものであり、開発者が呼び出しの階層と依存関係の順序付けについて心配する必要はありません。アルゴリズムを使用して自動的に構築し、タスクを収集し、ループや依存関係を検出し、最後に並行グループの階層情報を出力します。
この記事では、有向非巡回グラフの設計実装方法と遭遇した問題について説明します。
実装方法#
有向非巡回グラフの構築には、ストラテジーパターンと呼ばれるデザインパターンを使用します。まず、次のように Builder の実装方法を定義します。
/**
* @author debuginn
*/
public interface PhoenixBuilder {
// Phoenix APIで使用されるタスクをフィルタリングする
Map<String, ArrayList<TaskObj>> filterApiUsedTask(ArrayList<TransObj> transObjArrayList);
// APIに基づいて実行する必要のあるトランスを取得する
Map<String, ArrayList<TransObj>> apiTransMap(ArrayList<TransObj> transObjArrayList);
// 依存関係が存在するかどうかを判定する
void isHaveLoop(Map<String, ArrayList<TaskObj>> apiUsedTaskMap);
// 並行グループの分割を処理する
Map<String, ArrayList<ArrayList<TaskObj>>> processConcurrentGroup(Map<String, ArrayList<TaskObj>> apiUsedTaskMap);
// 並行グループの情報を出力する
void printConcurrentGroup(Map<String, ArrayList<ArrayList<TaskObj>>> phoenixApiArrayListMap);
}
PhoenixBuilder は 6 つのメソッドを実装する必要があります:
- まず、収集されたタスクを API ごとにグループ化し、タスクの依存関係を持つものをすべて収集します。
- API ごとにトランスを収集し、後続のトランスはリクエストスレッドを使用して直列に実行されます。
- 各 API で収集されたタスクが相互に依存しているか、または循環依存しているかを判定します。
- 各 API で収集されたタスクを依存関係の順序に従ってグループ分けします。
- 並行グループの情報を出力し、開発者がデバッグや検証に使用できるようにします。
依存関係が存在するため、階層的な設計が必要です。Phoenix フレームワーク:フレームワークの設計方法を参照してください。ただし、各レイヤーの実行順序に関する心配は必要ありません。ここでは、最も単純なデータ構造であるMap<String, ArrayList<ArrayList<TaskObj>>>
を使用して階層情報を保存し、Key はどの API リクエストに属するかを示し、Value は最も単純な 2 次元配列を使用して保存します。各次元は実行する必要のあるタスクを保存します。
遭遇した問題#
環が存在するかどうかの判定方法#
構築するのは有向非巡回グラフですので、依存関係のあるタスクはフレームワークの設計ロジックでは機能しません。相互に依存する場合、どのタスクを先に実行するかはどうすればよいでしょうか?
次の図を見ると、2 つのシナリオがあることがわかります:
- 相互依存関係:TaskB と TaskD は相互に依存しているため、実行順序を決定することはできません。
- 循環依存関係:TaskD、TaskF、TaskG、TaskE は依存関係のループが存在し、実行順序を決定することもできません。
相互依存関係の判定は比較的簡単で、TaskA が TaskB に依存しているかどうかを検索するだけです。
循環依存関係の判定は比較的複雑で、グラフのすべてのパスを走査する必要があります。パスに閉じたループが存在する場合、環が存在することを示し、そうでなければループが存在しないことを示します。これは単方向の依存関係の分岐パスです。
並行グループをどのように分割するか#
並行グループの分割は、依存関係のないタスクを互いに依存する順序に従ってグループ化することです。実際には、グラフの深さ優先探索と同じです。
依存関係があるため、上向きまたは下向きの探索を使用できます。私たちはスタックを使用して次のように処理します:
上向きの探索#
- まず、他のタスクに依存していないタスクを見つけ、それらを 1 つのグループとして配列に保存し、スタックの底にプッシュします。
- スタックの底のタスクから、そのタスクが依存するタスクを収集します。これらの収集されたタスクが他のタスクに依存しているかどうかを判定し、依存している場合は一時的なタスク配列に保存します。最後に残ったタスクは、スタックの底のタスク配列にのみ依存しているタスクであり、このグループをスタックに再度プッシュします。
- ステップ 2 を繰り返し、スタックの底のタスクをスタック内の最上位の配列に置き換え、一時的なタスクを収集されたタスクに追加し、重複を削除して繰り返します。
- 最後に、依存関係のないタスクが残り、これが最後の並行グループです。これをスタックにプッシュします。
プログラムを実行すると、スタックのトップにある並行グループが最初に実行され、スタックから順番に実行されます。
下向きの探索#
- まず、他のタスクに依存していないタスクを見つけ、それらを 1 つのグループとして配列に保存し、スタックの底にプッシュします。
- スタックの底のタスクから、このグループに依存するタスクを収集します。これらの収集されたタスクが他のタスクに依存しているかどうかを判定し、依存している場合は一時的なタスク配列に保存します。最後に、スタックの底のタスク配列にのみ依存するタスクが残り、このグループをスタックにプッシュします。
- ステップ 2 を繰り返し、スタックの底のタスクをスタック内の最上位の配列に置き換え、一時的なタスクを収集されたタスクに追加し、重複を削除して繰り返します。
- 最後に、他のタスクに依存しないタスクが残り、これが最後の並行グループです。これをスタックにプッシュします。
この時点で、スタックには最初に実行されるタスクの並行グループがスタックの底にあり、最後に実行されるタスクがスタックのトップにあります。実行するためにスタックを反転させ、順番に実行します。
なぜ「ストラテジーパターン」を使用する必要があるのか#
プログラムを開発する際、みんながプログラムの水平方向の拡張能力に重点を置いています。重要なタスクを具体的に実行するサブタスクに分割することで、プログラムの可読性が向上し、さまざまなトラバーサルアルゴリズムを拡張することができます。これは、フレームワークの持続的な最適化のために使用できます。
ここでも、Phoenix フレームワークでは可能な限りストラテジーパターンを使用して、コア機能を分割し、モジュール化された設計を実現しています。このような設計は、Phoenix フレームワークの設計の目的であり、持続的なイテレーションを実現しています。
最後に#
この記事では、有向非巡回グラフの自動構築方法と問題について説明しました。実際の開発では、このような依存関係の解決シナリオは他にもたくさんあります。上位のビジネス実装やフレームワークの要件を考慮せずに、基本的なデータ構造、アルゴリズム、グラフのトラバーサルシナリオは、現在の AI シナリオで非常に人気があります。
お読みいただきありがとうございます。良いソリューションやアイデアがあれば、ぜひお互いに交流しましょう。最後に、興味がある場合は公式アカウントをフォローするか、サイトを購読してください。お互いに強くなりましょう~