設計Optaplanner下實時規劃服務的失敗經歷

2019 年 10 月 4 日
筆記

　　其實本文不知道算不算一個知識點分享，過程很美妙，但結果很失敗。我們在利用OptaPlanner的Real-Time planning(實時規則)功能，設計實時在線規劃服務時，遇到一個屬於OptaPlanner7.8.0.Final版本的Bug。在實現實時在線規劃服務的過程中，我做過很多嘗試。因為需要實時在線的服務，因此，需要設計多執行緒並發為外界請求提供響應，需要實現消息隊列來管理並發請求的時序等問題。這些Java方面的並發處理，我們暫時不詳述，這方面的牛的人太多了，我只是新手，站在別人的肩膀上實現的程式碼而已。在本文我著重介紹一下，我在嘗試使用OptaPlanner的Real-Time Planning功能時遇到的問題，最終確認問題出自OptaPlanner引擎自身, 並通過JIRA向OptaPlanner 團隊提交issue過程。 關於OptaPlanner的Real-time planning 　　先看看正常情況下，我們對OptaPlanner的應用場景。平時我們使用OptaPlanner時，不外乎以下幾個，構建Problem對象 + 構建Solver對象-> 啟動引擎 -> 執行規劃 -> 結束規劃 -> 獲得方案-> 獲取結果方案,如下圖。　　這種應用模式下，引擎處於一個非實時狀態，只是一個調用 -> 獲取規劃結果的簡單交互過程。

　　但是有些對規划具的時間性要求較高，或在時間序列上，對規劃的結果具有一定的延續性要求的情況下，這種規劃方式是滿足不了要求的。例如有些實時調度的場景；要求每個新的solution與上一個solution需要具有延續性，不可能每次給出的solution存在過大的差異，若產生過大的差異，這些規划出來的方案對於執行機構來說，是不可能按計劃執行的。例如車輛調度系統(見下圖)，每隔一個時間段，就需要刷新一下車輛情況和環境情況，不可能每次刷新出來的調度方案跟前一次存在千差萬別。每一次產生的方案，它必須盡最大程度上與上一次保持相近。

　　另外一個要求是實時性，如果按常規的規劃步驟，對於實時性有要求，或響應速度較高的場景，例如：車間作業的實時調度系統，可能每隔離10分鐘就需要刷新一次計劃，此時實時規則的作用就反映出來了。如下動圖：

　Real-time planning, 顧名思義就是實時規劃，它與傳統的規劃步驟區別在於，它並沒有一個結束並退出規劃的動作，而是一旦引擎啟動，它將以守護進程的形式一直處於運行狀態，而沒有返回；當它滿足規劃結束條件時（例如找到符合條件的方案，或到達規劃時限）,會進入值守狀態，不佔用CPU資源。待激發事件對它發出重新啟動的指令。因此，它的步驟是: [構建Problem對象] + [構建Solver對象] -> 啟動引擎 -> 規劃 -> 通過BestSolutionChange事件輸出規則方案 -> 休眠 -> 接到重啟指令 -> 規則(重複上述步驟)，如下圖：

　　原來OptaPlanner還有這種神操作，那麼它的作用將進一步大增了，幻想一下大家看科幻或戰爭電影時，那裡的指揮中心必然有一個大螢幕，上面顯示了實時的戰況或各方資源的部署情況，如果這些部署是需要通過規劃來輔助實現的話，OptaPlanner是不是可以作為後台超級電腦上不停運算規劃的控制中樞系統呢？不過好像想多了。沒那麼神，做一下實時作業調度還是可以的。下面就看看我們的項目是如何考慮應用Real-time planning的。　　關於Real-Time Planning的具體開發步驟沒辦法在這裡詳述，在本系列的往後文章中，老農將會有一篇專門的文章介紹。它的基本步驟如下圖。　　這裡提供一下最重要的三個程式碼塊，對應的場景是，當一個新的任務(Task)需要被添加進引擎的Problem中參與規則時，應該如何添加，添加完成之後，如何獲得規劃的結果。這三個程式碼塊的功能分別是bestSolutionChanged事件處理程式，調用引擎Solver對象提交變更請求，和實現ProblemFactChange介面的實現，用於實現變更正在規劃的Planning Entity.

bestSolutionChanged事件處理程式

solver.addEventListener(new SolverEventListener<TaskAssignmentSolution>() {      public void bestSolutionChanged(BestSolutionChangedEvent<TaskAssignmentSolution> event) {          if(solver.isEveryProblemFactChangeProcessed()) {              // TODO: 獲取規劃結果          }      }  });

調用引擎Solver對象提交變更

DeleteTaskProblemFactChange taskProblemChange = new DeleteTaskProblemFactChange(task);  if (solver.isSolving()) {      solver.addProblemFactChange(taskProblemChange);  } else {      taskProblemChange.doChange(scoreDirector);      scoreDirector.calculateScore();  }

ProblemFactChange介面的實現

/**   * 添加任務到Workingsolution   * @author ZhangKent   *   */  public class AddTaskProblemChange extends AbstractPersistable implements ProblemFactChange<TaskAssignmentSolution>{      private final Task task;        public AddTaskProblemChange(Task task){          this.task = task;      }        @Override      public void doChange(ScoreDirector<TaskAssignmentSolution> scoreDirector) {            TaskAssignmentSolution taskAssignmentSolution = scoreDirector.getWorkingSolution();            scoreDirector.beforeEntityAdded(this.task);          taskAssignmentSolution.getTaskList().add(this.task);          scoreDirector.afterEntityAdded(this.task);          scoreDirector.triggerVariableListeners();      }  }

場景要求

我們的項目其實挺符合實時作業的要求的，雖然我們也沒有要求達到分鐘級，或秒級的響應；但是如果能夠每隔離10分鐘，通過實時規劃的模式刷新一次計劃，還是更能幫助生產調度人員更準確掌握生產情況的。事實上，我們對新的計劃刷新條件，並不是按固定的時間間隔來進行，而是以觸發事件的方式對進行變更規劃的。　　即當一個新任務產生了，或一個已計劃好的任務被生產完成了，或一個已計劃好的任務無法按時執行生產作業而產生計劃與實際情況存在差異時，或一個機台出現計劃以外的停機等諸如此類對計劃足以產生影響的事件，都將會作為觸發重新規則的條件。因此，我將引擎程式做成Springboot程式，部署到伺服器端，並將程式設計成多執行緒並發的模式，主執行緒負責偵聽Springboot接收到的WebAPI請求，當接收到請求後，就從執行緒池中啟用一個執行緒對請求進行處理，這些處理是更新規劃的請求，並把傳送過來的Planning Enitty, Problem Fact等資訊按要求進行處理，並放入隊列中。所有請求產生的重新規劃資訊，通過隊列依次被送入引擎處理。當有新的solution產生時，將它輸出指定位置，並通知客戶端前往獲取。系統的構件結構如下圖。

遺憾　　古語有云，理想很豐滿，現實很骨感。上述的設計對於OptaPlanner的使用領域來說，是比較先進的（起碼在中國還沒聽說過有人這樣用法）。對業務而言也是非常符合要求的。但是我對上述所有美妙的構想完成了設計，並實現了程式碼，並通過Springboot運行起來之後。程式確實如我意圖那樣運行起來了！啟動引擎 -> 開始規則 -> 找到更佳方案 -> 輸出方案 -> 滿足停止條件 -> 引擎進入守值狀態. 好了，我就通過http發出一個刪除Planning Entity的請求。Springboot的Contoller成功接收，啟動子執行緒處理數據，向引擎對象發送doChange請求，引擎檢測到請求，分出一個執行緒（這個執行緒是引擎分出來處理我那個執行緒請求的）處理成功，並更新Problem對象中的Planning Entity列表；引擎繼續運行。Duang~~~~引擎主執行緒竟然拋出一個異常並停止了！提示那個被請求刪除的Planning Entity未被加入Planning Entity的列表中！這下我蒙了。為什麼還會報出這個Planning Entity未被加進列表的錯誤？回想起OptaPlanner的開發說明書里，關於Planning過程中，每個新的solution都是一個clone的情況，我堅信我的程式是遇到Race condition了，一定是我的程式考慮不周導致資源競爭。OptaPlanner號稱經過大量單元測試，壓力測試，有良好的穩定性，不可能就這樣被我把錯誤試出來的。但切切實實地拋出了這個異常，而我卻沒有任何辦法。錯誤資訊如下圖，下圖是我截取給Optaplanner團隊的：

　　然後，我花了兩天時間，對每一個步驟進行調試分析，對每一個solution的clone進行核對，我確實沒辦法從我的程式中找到任何頭緒。於是我唯有求助於Geoffrey大神。通過郵件討論組我給他留了個貼子。很快Geoffrey大神就回復了（這個得給個贊，比利時跟我們的時區相差不少吧？每次提的問題，他都能及時回復）。回復見下圖，這個回復令了心被潑了一大桶冷水。它竟然確實可能是一個bug! 當然也有可能是程式產生了race condition. 可我都找了兩天了，實在沒辦法，才想到找OptaPlanner團隊。然後我就把這個問題的重現步驟在OptaPlanner項目的JIRA中提交了一個issue,不知道這算不算我給OptaPlanner作出的一點點貢獻呢，期待處理結果呀。　　其實在這兩天時間時，我並不僅僅是檢查我自己的程式碼是否出現資源競爭問題，我還Debug進了OptaPlanner的源程式碼里(7.8.0.Final版),並找到了異常的具體來源。發現確確實實是在我提交了ProblemFactChanged請求後，引擎也進行了處理，但因為引擎在處理了請求後，在新的Solution的clone中，並沒有被成功更新，也就是新的Planning Entity並沒有進入新的solution clone中，而導致處理程式無法識別新的Planning Entity, 就出錯了。

　　現在辦法有兩個，一個是等OptaPlanner團隊在JIRA上對我提交的issue進行處理，看是不是真的在OptaPlanner中存在這麼一個Bug. 另一種辦法是我打算將我的程式進一步簡化，將它與Springboot分離，跟OptaPlanner的事件程式一樣，通過其它方法啟動執行緒來嘗試Real-Time Planning. 　　OptaPlanner引擎程式被包裝成一個Springboot程式，並設置為daemon模式(守衛進程)，Springboot Application啟動後，引擎執行程式被一個執行緒啟動。主執行緒向外提供Restful webservice，當有Web請求到達時，就啟動一個執行緒用於執行OptaPlanner的ProblemFactChange對象中的doChange方法，對現有solution中的Planning Entity列表中的對象進行增刪改操作；並觸發VariableListeners. 引擎在處理這些調用時，會產生新的bestSolution，並觸發BestSolutionChangedEvent事件，在事件處理方法中，將最新的Solution中的Planning Entity列表輸出即可獲得增刪改Planning Entity後的最新solution了。 這又是一篇花費不少精力的東西，儘管最終沒實現實時規劃服務。 創作不易，歡迎轉載，請標明出處。