起源
了解到天池程序設(shè)計大賽還是去年在網(wǎng)上逛博客的時候，看到有人分享了自己的參賽經(jīng)歷，和在參賽過程中一步步完善思路提高成績的過程（附上鏈接）。就暗暗記下了這個比賽想要有朝一日自己也親自操刀嘗試一下。
賽題——自適應負載均衡的設(shè)計實現(xiàn)
題目的內(nèi)容是基于Dubbo的負載均衡算法實現(xiàn)，如上圖所示，測評時提供三個配置和性能不同的provider節(jié)點。同時可以通過官方提供的輔助接口進行想過性能數(shù)據(jù)的采集。
可以通過provider的Callback獲取provider的基本信息，包括最大線程數(shù)，內(nèi)存使用信息等；提供了comsumer和provider端的Fliter可以進行請求情況的采集；provider端還提供了限流器TestRequestLimiter 來進行限流操作。
算法設(shè)計
本次和隊友各設(shè)計實現(xiàn)了一種負載均衡算法，答題思路都是通過固定時間窗口進行統(tǒng)計，根據(jù)統(tǒng)計值進行權(quán)重計算，來更新下一輪次的權(quán)重，同時根據(jù)權(quán)重選擇節(jié)點采用了平滑加權(quán)輪訓算法，來保證請求分配按照權(quán)重比例進行分配。算法一采用統(tǒng)計成功次數(shù)占比的方式來計算下個周期的權(quán)重，算法二采用統(tǒng)計平均rt的方式，在計算下一周期的各個節(jié)點的分配權(quán)重。整體流程如下圖
優(yōu)化點
引入平滑加權(quán)輪詢算法
接下來主要說一說成功占比這一實現(xiàn)的優(yōu)化過程，起初版本大概在113W左右徘徊。這個版本對于節(jié)點的選擇，是通過生成一個隨機數(shù)，然后看隨機數(shù)落在哪個節(jié)點區(qū)間，進行隨機節(jié)點選擇。這種方式會有很大的隨機性，導致出現(xiàn)15-20%的限流請求。后來和隊友討論，將隨機選擇算法換成了平滑加權(quán)輪詢算法，來進行節(jié)點的選擇，跟換算法后，錯誤請求數(shù)大幅下降，基本達到了99.99的成功率。成績也有了大幅提升，大概來到了117W左右。
引入rt和并發(fā)量統(tǒng)計
由于最大并發(fā)是1024而三個節(jié)點的總線程數(shù)為1300(200+450+650),所以會出現(xiàn)全部測評過程中權(quán)重不發(fā)生任何變化的情況。就想到了根據(jù)統(tǒng)計固定窗口期的rt來進行權(quán)重便宜調(diào)整，但是計算出周期內(nèi)平均rt并不能很好的和當前使用的權(quán)重進行關(guān)聯(lián)，后來通過rt計算出本窗口期的最大并發(fā)，在結(jié)合題目中每個周期內(nèi)每節(jié)點最大并發(fā)數(shù)變化的。根軍統(tǒng)計結(jié)果計算出本窗口期的并發(fā)量，然后根據(jù)情況修改權(quán)重。修改完成的版本成績有了一定提升，當然也和賽會方提高了上限乏味有一定關(guān)系，這一階段成績在122-125W之間浮動，浮動區(qū)間比較大。
亂七八糟的參數(shù)調(diào)優(yōu)
進一步優(yōu)化就是修改部分參數(shù)，同時部分區(qū)間的rt偏大的情況，引入了根據(jù)rt情況微調(diào)權(quán)重的計算邏輯，但是這部分的優(yōu)化并沒有帶來成績的提升，但是增加了成績的穩(wěn)定性，成績基本穩(wěn)定在124-125W之間，這也是最后的成績。未能突破初賽，賽后在進行總結(jié)，準備明年再戰(zhàn)。
未能提交的思路
昨天晚上臨睡前在突然想到一種新的方式來進行負載均衡，大體的思路是根據(jù)provider的請求數(shù)和其最大線程數(shù)進行統(tǒng)計計算權(quán)重，摒棄之前使用的固定時間窗口統(tǒng)計的方式，改為實時統(tǒng)計。大體流程為在consumer的filter每次invoke前生成一條消息，對應invoker的權(quán)重-1，在response中如果成功，則對應invoker的權(quán)重+1，如果有異常則對應invoker的權(quán)重置為0。
但是由于錯看了截止時間，想要今天在實現(xiàn)，當實現(xiàn)了最初版的時候，發(fā)現(xiàn)初賽提交已經(jīng)結(jié)束，所以這個思路的結(jié)果不得而知。
寫在最后
剛剛?cè)豪镉信琶壳暗拇罄泄_了初賽代碼，學習了下他們的思路和代碼，發(fā)現(xiàn)差距還是比較大的。接下來好好學習，多看多想，來年再戰(zhàn)。
