基于多數據庫的商戶清分負載均衡分片算法研究

張暉

摘? 要：在商戶清分批處理作業中，應用程序的高并發數和單機設備的資源利用率總是有一定上限，數據庫本身的處理能力和通訊帶寬也對批處理作業有一定的約束。根據清分數據商戶原子性特征，設計了一種負載均衡的分片算法，實現清分批處理任務在多應用、多數據庫間分布式、高并發協同完成，集群節點還可以線性擴展。通過實驗測試，對比使用該算法前后的負載均衡性能，分片算法能夠在保證商戶原子性的情況下有效均衡清分流水，顯著提高清分服務器集群的并發讀寫性能，從而證明了該算法的有效性。

關鍵詞：分布式;高并發;商戶原子性;清分

中圖分類號：TP312? ? ?文獻標識碼：A

Research on Load Balancing Partition Algorithm of Merchant

Sorting based on Multi-database

ZHANG Hui

（China UnionPay Merchant Services Co.， Ltd.， Shanghai 201203， China）

hz-job@163.com

Abstract： In the merchant sorting batch tasks， high concurrency of applications and resource utilization of single equipment always have a certain upper limit. Processing capacity and communication bandwidth of the database also have certain constraints on batch jobs. According to the atomicity of merchant sorting data， this paper proposes to design a load balancing partition algorithm to realize the distributed and high-concurrency collaborative completion of sorting batch processing tasks among multiple applications and databases. The cluster nodes can also be linearly expanded. Experimental test is made by comparing the load balancing performance before and after using the algorithm. Results verify that the proposed partition algorithm can effectively balance the sorting pipeline under the condition of ensuring the atomicity of merchants， and significantly improve the concurrent read-write performance of the sorting server cluster， which proves its effectiveness.

Keywords： distributed; high concurrency; merchant atomicity; sorting

1? ?引言（Introduction）

數據清分系統通常要面對龐大的、多方的交易數據，根據一定的業務、勾兌和計算規則對數據進行清洗、拼接和計算等處理，從而得到各利益參與方的資金分配結果，為下游的資金結算和劃付提供依據。以上要求決定了清分系統每次處理的數據量都是千萬級別的，大型支付機構甚至達到億級的流水處理量，并且通常要勾兌三方以上的源流水，業務邏輯復雜，處理時效要求高，處理時間段集中在各方聯機交易系統完成日切之后的幾個小時內，還要為異常情況下重跑批的補救工作留有足夠的冗余時間。在互聯網數據爆炸式增長的大背景下，傳統的應用單機（IBM小型機）高并發已經凸顯出IO和CPU瓶頸，應用和數據庫分離也存在吞吐量[1]和網絡帶寬[2]（千兆網絡交換機）的性能瓶頸。為此，需要借助一定的負載均衡算法將龐大的業務處理均衡地分散到多節點（應用+數據），以便多機（PC服務器）集群[3]并行分布式處理，實現處理能力的線性擴展。這種集群技術可以用最少的投資獲得接近于大型主機的性能，可以滿足不斷增長的負載需求[4]。由于具有橫向擴展性，增加PC機的組合在性價比上已經遠超IBM小型機了，該方案的實施具有較好的經濟效益。

2? 支付公司商戶清分系統一般模型（General model of merchant sorting system of payment company）

商戶清分系統的主要功能是匯聚清算組織（銀聯、網聯）和其他第三方渠道清算流水，再對流水進行預處理，根據商戶/機構結算、分組規則，分潤計算規則，費用收取計算規則等信息，對清算數據進行處理，計算應收發卡轉接機構金額、商戶本金、手續費、分潤、費用等信息，并按要求生成商戶、機構對賬報表、清分結果等文件。清分系統的功能定位決定了系統的模型如圖1所示。

清分處理的關鍵步驟是收集各方清算流水，按照設置的規則勾兌、計算，最終按各方要求出具各類明細和匯總報表。要在規定時間處理千萬甚至上億的流水就需要分布式并發處理，而并發處理的前提是流水的分片，合理的分片能達到良好的負載均衡效果，充分利用每個分布式節點的計算能力。

3? 清分數據分片算法研究（Research on partition algorithm of sorting data）

支付領域中商戶清分系統的業務特點和清分系統的模型構造，天然需要運用分片思想來達到分布式并行處理的效果。分片原理就是要把一個原始問題分成若干子問題，先遞歸求得子問題的解，然后把這些解合并起來，得出原始問題的解。在確保商戶原子性的前提下，商戶清分業務需要分片架構和與之適應的分片算法協同完成。

3.1? ?分片算法思想

分片（Sharding）是指將內存中的數據拆分成不同的塊，分別存儲到不同機器上的過程[5]。本文的分片是將商戶清分數據按一定的算法拆分成不同的子文件，分別發送到不同的機器上的過程。通過分割數據到不同的服務器，讓數據集的不同部分分別由不同的服務器負責，使得單個機器上的請求數減少，系統總負載得到提高，總存儲空間也得到提高[6]。

在商戶清分業務中，支付機構給每個商戶都分配了唯一的商戶編號。對同一個商戶的交易要求在一個清分處理單元內完成，這就是商戶的原子性。商戶原子性是本文負載均衡算法的出發點，同時要解決如下幾個問題：

（1）撤銷交易查找原交易問題、多方文件勾兌問題;

（2）差錯交易查找歷史原交易問題;

（3）聯機退貨交易查找歷史原交易問題;

（4）特殊商戶按照交易匯總金額清算問題;

（5）商戶檔案信息、配置信息共享問題;

（6）結果文件合并過程中非商戶維度問題、部分接口文件存在科目匯總問題;

（7）多庫數據中的唯一性沖突和歸集問題。

相應的解決方式為：通過改良的倒序貪婪平均分配算法[7]解決（1）中的問題，通過差錯交易獨立文件解決（2）中的問題，通過開發跨進程的歷史庫查詢服務解決（3）中的問題，通過特殊商戶分組解決（4）中的問題，通過OGG[8]數據同步方式解決（5）中的問題，（6）、（7）中的問題通過在匯總服務器中二次加工來解決。先快速在流水文件中提取當日當批次發生交易的商戶號及對應的交易筆數，根據清分流水條數和服務器節點數來確定每臺服務器的負荷;接著對數據進行切片，每個切片優先分配筆數多的商戶，達到臨界點時用交易量少的商戶進行微調，確保每個商戶的完整交易都在一個切片中，并且每個節點設備的交易筆數均衡。

該分片方案在確保商戶原子性的基礎上，充分發揮了清分系統分布式高并發的計算效能，在實踐中達到了如下目標：

（1）清分分布式處理可以實現多臺設備交易量的負載均衡，保證商戶記錄的原子性。通過多臺機器的分攤，將總交易量放到多臺數據庫上分布式執行，增加系統的吞吐量;加強了網絡數據處理能力，提升了網絡的靈活性和可用性;同一商戶的交易在同一個切片中處理，可以確保流水之間的關聯不被破壞。

（2）清分分布式處理可以線性擴展處理節點，應對海量數據的處理。隨著交易量的增加，可以線性擴展數據庫和應用服務器的數量;單節點故障可以臨時替補備份機，也可以重新分配執行計劃，具有高容錯性。

（3）清分分布式處理可以提升各類接口、報表的生成時效性。

3.2? ?分片集群架構

批處理作業由于在實時計算過程中要傳輸大批量的流水，如果應用和數據庫分離就會出現網絡傳輸瓶頸;如果應用和數據庫不分離，在高并發下就會出現CPU、IO瓶頸。為了解決這個兩難境地，將源數據分片，每一片數據在一個應用和數據庫共同體節點下計算處理，然后將各節點計算結果進行合并處理，出具商戶和機構要求結果報表。設計分片集群邏輯架構如圖2所示。

在該架構中，清分流水按照一定算法完成分片，每一個分片在一個節點中完成，一個節點的應用和數據庫部署在一臺物理服務器上。計算規則通過公共配置庫實時同步到每個節點數據庫，歷史庫也作為公共庫，為每個節點提供差錯交易查找原交易信息之用。當所有節點計算完成后，接口合并單元匯集每個節點的數據結果進行匯總計算，完成最終的清分報告。本文節點數據庫選用Oracle，也可以選用其他商用數據庫，對于公共庫的訪問通過設計自定義數據庫訪問服務來完成，數據庫之間的信息同步使用OGG方式。日初和日終任務用于系統的監控、資源的分配和回收等。

分片集群架構中，公共庫（配置庫和歷史庫）的數據無法放入每個集群節點中，本文設計了一套高效的訪問機制，如圖3所示。每個清分處理單元對應的PC機上，在需要查詢公共庫信息時，通過調用查詢公共庫client類（DBClient）中的查詢方法來實現歷史庫的查詢。考慮到公共庫中交易數據存放的完整性和原始性，DBClient只支持查詢（select），不支持更新（update）和插入（insert）等更改數據的操作方法。查詢公共庫client類（DBClient）中的方法使用短連接方式訪問數據庫。按照目前清分系統查詢公共庫的要求，DBClient封裝有很多種不同的查詢方法，每次調用DBClient的一個查詢方法，返回一條查詢結果（找到原交易或未找到原交易），若找到原交易，將原交易的查詢結果返回給查詢方法。

公共庫所在服務器上部署訪問數據服務DBServer，它是常駐公共庫系統的守護進程，通過監控指定的訪問端口port，用來響應客戶端類DBClient的各種select查詢數據庫訪問方法，并將查詢結果返回給DBClient。考慮到客戶端類DBClient的并發查詢，該數據服務DBServer需支持多進程訪問數據庫。

各分片節點完成計算后，要進行文件合并、對賬單多維度重構操作。對于后續的結算劃付文件，通過各子機器上傳的接口文件追加合并完成;對于標準化的商戶對賬單明細和匯總文件，也可以追加方式進行合并，多序號文件還要進行壓縮處理;對于個性化的分析報表，需要將子節點結果數據導入中間表，輔助公共庫中的配置信息進行二次加工分析。

3.3? ?關鍵算法分析

首先遍歷清算組織下發的流水，比如銀聯下發的為ACOMN流水文件，統計出總交易條數S，發生交易的商戶數為m及每個商戶對應的交易量Li（1≤i≤m）。如果設備分布式節點的個數為n，a=S/n，則分配給每個節點處理的條數Sj（1≤j≤n）的范圍為[a-d，a+d]，d可根據情況進行調整。在進行分片拆分前，將特殊分組的商戶挑出來先分配到一臺機器上（假設是編號最后的一臺），對剩余的商戶可采用快速排序法，按照商戶交易量進行降序排序，排序后的商戶交易量序列為Li（1≤i≤m），Lm最大，L1最小。為了便于取商戶，設兩個指針變量，尾巴指針x=1，頭部指針y=m，用二維數組Qji（1≤j≤n，1≤i≤m）存儲商戶分配結果，以下是商戶分配算法的偽代碼。

商戶分配完之后，檢查指針x和y的位置，若存在未分配的商戶，需要將剩余商戶分配給Sj最小的節點;然后根據Qji中的商戶，切割拆分各渠道的清算流水，并把拆分的流水推送到對應的機器節點上。通過該算法就將清分系統待處理的數據源按照商戶記錄數切分成多片文件，由每個獨立的清分處理單元完成每個切分文件的數據批處理。批處理完成后將每個單元的批處理結果發送到歸集服務器，經歸集服務器合并和多維重構后，還原成下游結算、劃付需要的各類接口文件、商戶對賬文件和報表分析類文件。

在整個清分批處理的過程中，切片和合并的處理是單節點，各個切片的清分計算在多節點分布式集群下處理。由于本切片算法和合并處理都是基于文件操作，可以在處理前將文件導入內存，因為很少涉及對數據庫的訪問，因而切片和合并沒有IO的瓶頸障礙，可以通過應用高并發和擴展CPU數量來提升性能。

4 算法性能評估（Algorithm performance evaluation）

測試環境使用1 臺分片服務器，1 臺報表合并服務器，8 臺分布式計算服務器，每臺服務器內存256 GB，CPU為Intel Xeon E5-2680 v4 14C ，千兆網口。操作系統是Suce Unix，數據庫使用Oracle 11g。分別測試了在應用本分片算法前后清分跑批的時間消耗，如表1所示。

沒有使用該算法前，由于商戶的原子性，應用是8 個計算節點，數據庫只能是一個節點。這種情況下數據庫的CPU和IO利用率最高只能到達75%，應用和數據庫間帶寬上、下限的流量都達到800 Mbs時，加大應用并發量也不能提升了，此時帶寬成了性能瓶頸。而使用本文的分片算法保證商戶原子性后，既能分布式處理，又能把應用和數據庫放在一個物理節點，不存在網絡傳輸瓶頸，每臺服務器的CPU和IO利用率可以壓測到95%以上，充分使用設備資源。

通過測試數據比對也發現，設備資源得到充分釋放后，性能提升20%以上，并且隨著數據量的增加，性能提升效果更加明顯。這是由于分片算法克服了清分業務商戶原子性的問題，又能根據設備節點數負載均衡地分配任務，將來計算節點可以橫向擴展，應對億級的清分流水量。

5? ?結論（Conclusion）

商戶清分系統作為支付機構的核心業務系統，是一種典型的批處理系統，既不同于實時響應的聯機交易系統，也不同于高挖掘價值的大數據分析系統。公有云PASS層雖能提供各種分布式工具，但金融數據安全性存疑，搭建私有云又具有較高的成本。本文提供的負載均衡分片算法能夠靈活自主地實現商戶清分高效分布式處理，保證了商戶原子性，兼顧了安全性和實時性，為業界千萬級以上交易量的清分提供了一種思路。由于篇幅所限，本文對多節點的調度管理和個別節點異常情況下的恢復措施不再詳細探討。

參考文獻（References）

[1] DONG H， SI H， ZONG H， et al. Unstructured mesh generation based on Parallel Virtual Machine in cyber-physical system[J]. EURASIP Journal on Wireless Communications and Networking， 2019（1）：1-11.

[2] ZHE S J. Cloud-computing load-balancing mechanism dependent on marine environmental information[J]. Journal of Coastal Research， 2019， 98（sp1）：137-140.

[3] SHARMA D. Response time based balancing of load in web server clusters[C]// 2018 International Conference on Reliability. Infocom Technologies and Optimization （Trends and Future Directions） （ICRITO）. Noida， India： IEEE， 2018：471-476.

[4] 周瑩蓮，劉甫.服務器負載均衡技術研究[J].計算機與數字工程，2010，38（4）：11-14，35.

[5] 陳敬靜，馬明棟，王得玉.MongoDB負載均衡算法優化研究[J].計算機技術與發展，2020，30（03）：88-92.

[6] 李朝奎，嚴雯英，楊武，等.三維城市模型數據劃分及分布式存儲方法[J].地球信息科學學報，2015，17（12）：1442-1449.

[7] 黃景修，劉清堂，吳林靜.一種面向多終端服務的學術會議管理系統設計與實現[J].計算機應用與軟件，2016，33（07）：68-71，101.

[8] 賈海軍.一種基于OGG方式進行數據遷移的研究[J].軟件，2015（05）：140-144.

作者簡介：

張? 暉（1981-），男，碩士，高級工程師/經濟師.研究領域：軟件工程.