從0到1設計業務並發框架的Phoenix框架自動構建有向無循環圖設計

從 0 到 1 設計業務並發框架系列：

Phoenix 自動構建有向無環圖的業務並發框架，核心就在於不需要開發人員關心調用分層和依賴互斥的排序問題，通過算法進行自動構建、收集 Task 任務、檢測環或者依賴，最後打印並發組分層信息。

本篇文章就講解下如何構建有向無環圖的設計實現方案及遇到的問題。

實現方案#

有向無環圖的構建採用的是設計模式中的策略模式，首先定義好 Builder 的實現方式，如下：

/**  
 * @author debuginn  
 */
public interface PhoenixBuilder {  
  
    // 過濾 Phoenix API 使用到的 Task 任務  
    Map<String, ArrayList<TaskObj>> filterApiUsedTask(ArrayList<TransObj> transObjArrayList);  
  
    // 根據 api 獲取需要執行的 trans    
    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 種方法：

首先，將收集上來的 Task，按照 API 進行分組，Task 存在依賴調用的都進行收集；
按照 API 進行收集 Trans，後續 Trans 使用請求線程進行串行執行；
判定每個 API 收集上來的 Task 是否存在相互依賴或循環依賴；
將每個 API 收集上來的 Task 按照先後依賴關係進行分組劃分；
打印並發分組信息，用來給開發者調試及校驗使用；

由於存在依賴關係，需要進行分層設計，這裡可以結合 Phoenix 框架怎麼組織設計一個框架來看，然而每一層並不需要關係執行的順序問題，這裡採用了最簡單的數據結構存儲分層信息，Map<String, ArrayList<ArrayList<TaskObj>>> Key 用來標識屬於哪個 API 請求的並發分組，Value 則採用最簡單的二維數組進行存儲，每一維分別存儲需要進行執行的 Task 任務。

遇到的問題#

怎麼判定存在環#

由於我們要進行構建的是有向無環圖，那麼存在相互依賴的 Task，在框架設計邏輯中是行不通的，若存在相互依賴，那麼究竟該先執行哪個 Task 呢？

可以看到上圖，只要有兩個場景：

相互依賴關係：TaskB 與 TaskD 存在相互依賴，那麼就不能確定執行順序；
環狀依賴關係：TaskD、TaskF、TaskG 和 TaskE 存在依賴環，也無法確定執行順序；

相互依賴關係判定比較簡單，就是檢索一個 TaskA 依賴的 TaskB 是不是也依賴這個 TaskA，
循環依賴判定相對來說比較複雜，需要遍歷圖的所有路徑，若路徑存在閉環，則代表著存在環，反之，就是不存在環路，代表就是單向依賴的分支路徑。

怎麼劃分並發分組#

劃分並發分組，就是將彼此沒有依賴關係的 Task 按照依賴的先後順序進行分組，其實就是按照圖的深度遍歷。

這裡的遍歷，由於有依賴關係，可以採用向上遍歷或者向下遍歷的方式，我們採用了壓棧的方式處理：

向上遍歷#

首先找到沒有被依賴的 Task，這是一組，之後存入數組壓入棧底；
之後棧底的 Task 收集出來需要依賴的 Task，這些收集上來的 Task 需要再判定是不是被其他 Task 依賴，若是依賴的話，則保存在臨時的 Task 數組中，最後將剩下 Task 就是只被棧底 Task 數組依賴的 Task，那麼將這個分組繼續壓入棧內；
重複第 2 步，把棧底的 Task 換成棧內最上層的數組，之後再把臨時 Task 追加到收集出來需要依賴的 Task 上，去重，之後重複執行；
最後執行到剩下的 Task 沒有依賴的 Task，這就是最後一個並發組，之後壓入棧內；

最後程序執行的時候，就是先執行棧頂部的並發組，之後一次出棧執行。

向下遍歷#

首先找到不依賴其他 Task 的 Task，這是一組，之後存入數組壓入棧底；
之後棧底的 Task 收集出來依賴這個分組的 Task，這些收集上來的 Task 判定是不是被其他 Task 依賴，若是依賴，也是保存在臨時的 Task 數組中，最後就只剩下只依賴棧底的 Task 數組的 Task，之後將這個數組壓入棧內；
重複第 2 步，把棧底的 Task 換成棧內最上層的數組，之後再把臨時 Task 追加到收集出來需要依賴的 Task 上，去重，之後重複執行；
最後執行到剩下的 Task 沒有任何 Task 依賴，這就是最後一個並發組，之後壓入棧內；

此時，這個堆棧存儲的是最先執行的 Task 並發分組在棧底，最後執行的在棧頂，需要進行反轉操作，之後再依次進行執行。

為何要使用 "策略模式"#

在開發程序的時候，大家都不約而同地講究程序的橫向擴展能力，將核心的關鍵的任務拆分成具體執行的子任務，這樣不僅可以提高程序的可閱讀性，而且還可以擴展不同的遍歷算法，用來後續框架的持續優化。

不僅這裡，Phoenix 框架盡可能的採用策略模式實現，將核心功能點都進行拆分，做到模塊化設計，這樣的設計正是 Phoenix 框架的設計初衷，生生不息，持續迭代。

寫在最後#

本篇文章主要講了如何進行自動構建有向無循環圖的思路及遇到的問題，其實在開發中，這種解決依賴關係的場景還有很多，其實抛開上層的業務實現或者框架需求來看，底層就是最基本的數據結構，算法，圖的遍歷場景在當今比較火的 AI 場景下也是如此。

感謝你的閱讀，你要是有好的方案或者好的 idea 可以與我一起交流，最後，如果你感興趣，推薦關注公眾號或訂閱本站，歡迎互動與交流，讓我們一起變得更強～