裝箱演演算法的效能測試

　　筆者第一次對演演算法做效能測試，記錄本次測試的過程，方便以後覆盤。

　　專案的背景是新提交了一個需求，在每個b2c出庫訂單入庫時，給訂單一個合適的推薦箱型。訂單的sku屬性中有長寬高，包材管理的表中也有各包材的長寬高。需要推薦一個能裝下的最小包材，並且體積佔比低於90%，剩餘大於等於10%空間留給冷媒和充氣柱。以下是產品提出的初步流程圖：

　　在需求評審階段，我提出了以下問題：

　　1、在訂單入庫的階段就給了推薦箱型，那如果修改了商品或包材的長寬高，可能會導致推薦的包材過大（不是最優解）或者放不下，怎麼處理？

　　2、實際的sku很多是不規則的，怎麼去計算？

　　3、如果所有單個包材都裝不下，應該怎麼推薦？

　　4、包材推薦的優先順序怎麼設定？比如計算得出的最優的包材是包材管理中倉庫所屬的包材，屬於通用包材，而貨主指定了自己的專屬包材，那優先選用哪一個？

　　5、商品和包材的長寬高不是必填欄位，為空怎麼處理？

　　在設計評審階段，開發同事去了解了相關的演演算法之後，向產品同事提出過一些問題。

　　6、使用該演演算法的前提是商品視做長*寬*高規則的長方體。

　　7、商品sku過多，計算超時怎麼處理？

　　8、實際裝箱商品可以斜放，但是選用的演演算法是一種正交擺放的方式，不考慮商品翻轉，只能在一個類似座標軸中正正方方的擺放（從包材的一個角斜插到另一個角不被允許）。

　　在產品同事一一解答並三方確認後，對以上問題做出解答並記錄。

　　1、實際業務中sku和包材的基礎資料幾乎不會修改，因此不考慮後續修改商品或包材引數；

　　2、因為開發的問題6，所以商品視作規則長方體；

　　3、單個包材如果裝不下推薦一欄置空；

　　4、實際業務中，商家有提供包材則倉內通常只提供打包服務，優先考慮所有專屬包材，都不滿足再考慮通用包材；

　　5、長寬高任意為空則跳過，置空；

　　6、使用該演演算法的前提是商品視做長*寬*高規則的長方體；

　　7、sku數量引數這一塊根據具體效能測試結果定；

　　8、只支援正交擺放。

　　有了以上的需求評審和問題評審對一系列問題在開會過程中統一意見後，開發同事開始了編碼，我則開始進行測試用例的設計，依舊是按照等價類、邊界值、場景法和錯誤推定法設計了一些功能的測試用例。在進行用例評審過後，執行功能測試，發現bug提交，驗證功能bug修復後，開始了效能測試。

　　分析整個場景，在高並行場景下，多個b2c訂單同時下發到我們wms系統中，需要能夠快速的給出推薦箱型，並在接下來的出庫流程中的總揀過程中在列印的揀貨單上給到各訂單的推薦箱型。在之前的壓測過程中，已得出系統支援200qps程度的並行。因此本次壓測的期望就是在200qps的情況下，能夠給出推薦箱型，不影響後續出庫流程。

　　與此同時，我去簡單瞭解了下裝箱演演算法。裝箱演演算法是典型的世界難題，屬於演演算法中的NP一HARD問題，從數學家高斯時期開始研究開始到現在已有百餘年的歷史。雖然經過幾代人的努力,但迄今尚無成熟的理論和有效的數值計算方法，由於目前NP完全問題不存在有效時間內求得精確解的演演算法,裝箱問題的求解極為困難,因此,從70~80年代開始,陸續提出的裝箱演演算法都是各種近似演演算法。同事使用的演演算法基本思想是一種將商品視作在座標軸中，以包材的長寬高作為座標軸，以商品（規則長方體）在座標軸中的位置，將裝箱問題轉化為一元三次不等式方程組的求解。

　　在功能測試階段，已經發現有效能問題，在單個訂單的數量超過50個sku後，獲取面單的速度明顯變慢。和開發同事溝通，他為了開發進度考慮，沒有走集團內部資源申請流程，沒申請新的redis資源，而是將裝箱計算的方法寫在了獲取面單號的模組中。為了具體得出每次裝箱推薦的時間，讓開發同事加了列印紀錄檔，觀察到後臺在50個sku以上，推薦箱型的消耗時間會超過3s，對比20個sku只需要0.2s左右（這裡就是演演算法的弱點，每多1個sku，排列組合的方式是呈指數方式增長的，因此計算耗時也大大增加，20到50個sku，增長了1.5倍，但是耗時增長了約15倍），則200個訂單需要多出600s（約10min）的計算時間，而此前200個訂單獲取面單號的時間僅需要耗時30-40s。這種設計方案是嚴重阻礙實際業務場景中，b2c訂單出庫的，因此需要改動。而且測試中發現，單個訂單在300個sku以後，會導致系統崩潰。結合rancher中top命令下伺服器的CPU佔用，發現此時CPU佔用達到207%，推斷是有指數增長情況下，300個sku的計算難度和時間以目前的伺服器cpu效能都不足以完成。再次分析實際業務中，50個以上的sku很大可能單個包材是裝不下的，這部分可以由倉庫人員靈活處理，因此增加判斷條件，sku>50則跳過箱型推薦。為了安全起見，加上了判斷條件，單個訂單的箱型推薦，如果計算超過15s，則終止計算。

　　第一次改動，拆分了兩個佇列，加上了計算上限是sku=50。

　　在申請了單獨的kafka資源作為佇列後，獲取面單號成為了單獨的流程，恢復到了每分鐘350個單號左右的效率。使用jmeter同時推播200個訂單，發現系統再次崩潰，此時觀察到rancher中top命令下伺服器的記憶體，發現此時記憶體佔用達到102%，但是有少量訂單完成了箱型推薦，分析推斷是存在記憶體洩露。在和開發同事溝通後，得知他參照獲取面單介面的操作流程，同樣是每個執行緒每次獲取50個b2c訂單作為一組去執行，但是執行完成後沒有釋放記憶體，仍然進行下一個執行緒的呼叫，存在記憶體洩露，因此要求他修改，於是改為了程序每次呼叫一組訂單前，需要申請伺服器記憶體，完成一組訂單的裝箱推薦計算後，需要釋放伺服器記憶體。這樣的設計在1個訂單1個sku的時候，發現耗時需要0.14s，即每次申請資源和釋放資源需要固定的0.14s時間作為額外的效能開銷，經過和開發同事的討論，這個時間是完全可以接受的。

　　第二次改動，將每個程序調取一組訂單前後，分別申請伺服器記憶體和釋放伺服器記憶體。

　　在經過2次設計的修改後，終於程式支援200qps情況下裝箱推薦了，極限情況下是200單，每單50個sku需要600s獲取箱型推薦，但是並不會影響正常的出庫流程。以當前生產環境wms的日單量判斷和80%的爆品單集中在10個sku以內，可以得出結論，效能滿足當前的業務需求，測試通過，允許釋出。