[發(fā)明專利]面向Storm連續(xù)范圍查詢?nèi)重?fù)載均衡的分組方法及查詢方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201710536098.6
• 申請(qǐng)日: 2017-07-04
• 公開(kāi)（公告）號(hào): CN107357659B
• 公開(kāi)（公告）日: 2020-09-29
• 發(fā)明（設(shè)計(jì)）人: 王波濤;王國(guó)仁;周建鵬;張玉圻;王助;鐘漢輝
• 申請(qǐng)（專利權(quán)）人: 東北大學(xué)
• 主分類號(hào): G06F9/50
• 分類號(hào): G06F9/50;G06F16/2453;G06F16/2455
• 代理公司: 北京君泊知識(shí)產(chǎn)權(quán)代理有限公司 11496
• 代理人: 王程遠(yuǎn)

本發(fā)明公開(kāi)了一種面向Storm連續(xù)范圍查詢?nèi)重?fù)載均衡的分組方法及查詢方法，對(duì)網(wǎng)格索引下的連續(xù)范圍查詢，結(jié)合范圍查詢語(yǔ)義，利用Redis存儲(chǔ)并負(fù)責(zé)更新網(wǎng)格內(nèi)移動(dòng)對(duì)象數(shù)量，將查詢范圍內(nèi)的移動(dòng)對(duì)象數(shù)量作為評(píng)估代價(jià)，按照查詢代價(jià)將范圍查詢?nèi)蝿?wù)分到相應(yīng)的組，同一個(gè)組內(nèi)的范圍查詢?nèi)蝿?wù)輪詢地分發(fā)到下游worker，輪詢計(jì)數(shù)器由Redis維護(hù)，實(shí)現(xiàn)全局分組輪詢的分組策略，能夠根據(jù)分組策略有效地提高了系統(tǒng)負(fù)載均衡度，從而提高了系統(tǒng)的資源利用率。

技術(shù)領(lǐng)域

本發(fā)明涉及通信網(wǎng)絡(luò)技術(shù)領(lǐng)域，尤其涉及一種面向Storm連續(xù)范圍查詢?nèi)重?fù)載均衡的分組方法及查詢方法。

背景技術(shù)

隨著定位手段的多樣化、移動(dòng)終端的普及與通訊基礎(chǔ)設(shè)施的完備，以基于位置服務(wù)(Location Based Service，LBS)為代表的移動(dòng)應(yīng)用已經(jīng)步入移動(dòng)大數(shù)據(jù)時(shí)代。移動(dòng)大數(shù)據(jù)環(huán)境下，數(shù)據(jù)規(guī)模更大、傳播速度更快、多樣性更加廣泛，呈現(xiàn)出鮮明的流式特征，傳統(tǒng)LBS技術(shù)面臨多種新的挑戰(zhàn)。基于位置服務(wù)的連續(xù)范圍查詢，具有高并發(fā)、低延遲特點(diǎn)，因此需要更高效的針對(duì)具有流式特征的移動(dòng)大數(shù)據(jù)的處理能力。移動(dòng)大數(shù)據(jù)時(shí)代的數(shù)據(jù)處理不僅需要存儲(chǔ)與處理能力更強(qiáng)更靈活的計(jì)算平臺(tái)，還需依托于計(jì)算平臺(tái)的處理和優(yōu)化技術(shù)。

然而，在分布式系統(tǒng)中普遍存在著著名的“短板理論”，一個(gè)系統(tǒng)如果出現(xiàn)了負(fù)載不均衡問(wèn)題，那么負(fù)載最大的節(jié)點(diǎn)往往將成為影響系統(tǒng)整體表現(xiàn)的瓶頸和短板。由于經(jīng)濟(jì)發(fā)展，地理位置等因素，人口密度在不同區(qū)域是不相同的，相應(yīng)的，和LBS應(yīng)用相對(duì)應(yīng)的移動(dòng)對(duì)象在地理分布上也是不均勻的。ApacheStorm本身作為一個(gè)分布式流處理系統(tǒng)，系統(tǒng)內(nèi)部并沒(méi)有提供有效的負(fù)載均衡機(jī)制，而且Storm自帶的分組策略如Shuffle Grouping、FieldsGrouping都是基于一種通用思想而設(shè)計(jì)的分組策略，而沒(méi)有考慮處理的任務(wù)所包含的語(yǔ)義，如連續(xù)范圍查詢具有查詢范圍、移動(dòng)對(duì)象密度、范圍重疊等時(shí)空語(yǔ)義，移動(dòng)對(duì)象在地理分布上是不均勻的，因而范圍查詢的代價(jià)也不盡相同，這樣很容易導(dǎo)致處理范圍查詢的各計(jì)算單元之間的負(fù)載不均衡，性能下降，所以Storm自帶分組策略也不能滿足系統(tǒng)負(fù)載均衡的需要，這無(wú)疑對(duì)整個(gè)系統(tǒng)的性能表現(xiàn)是一種挑戰(zhàn),針對(duì)云計(jì)算環(huán)境中的在線流處理的負(fù)載均衡研究相對(duì)較少，傳統(tǒng)的和針對(duì)批處理的負(fù)載均衡技術(shù)無(wú)法直接應(yīng)用到流處理系統(tǒng)中。

發(fā)明內(nèi)容

針對(duì)上述問(wèn)題，本發(fā)明的目的在于提供一種面向Storm連續(xù)范圍查詢?nèi)重?fù)載均衡的分組方法及查詢方法。

為了解決背景技術(shù)中所存在的問(wèn)題，本發(fā)明的技術(shù)方案為：

一種面向Storm連續(xù)范圍查詢?nèi)重?fù)載均衡的分組方法，包括：

1)、獲取范圍查詢信息，所述范圍查詢信息包括查詢范圍和網(wǎng)格重疊量；

2)、根據(jù)查詢范圍和網(wǎng)格重疊量，將范圍查詢分為多個(gè)子查詢，每個(gè)子查詢的查詢范圍只和一個(gè)網(wǎng)格重疊；

3)、讀取Redis中存儲(chǔ)的與子查詢查詢范圍重疊網(wǎng)格中移動(dòng)對(duì)象的密度，并根據(jù)子查詢的查詢范圍以及網(wǎng)格中移動(dòng)對(duì)象的密度，計(jì)算子查詢的代價(jià)；

4)、根據(jù)查詢代價(jià)，將子查詢映射到相應(yīng)的組，然后從輪詢計(jì)數(shù)器表中獲取該組計(jì)數(shù)器的值；

5)、根據(jù)計(jì)數(shù)器的值對(duì)下游worker的數(shù)量取模，得到目標(biāo)worker id，并將目標(biāo)worker id下發(fā)到下游。

所述步驟2)中根據(jù)查詢范圍和網(wǎng)格重疊量，將范圍查詢分為多個(gè)子查詢具體包括：

2.1、設(shè)定分組數(shù)量，根據(jù)分組數(shù)量計(jì)算第一次分組粒度；

2.2、設(shè)定二次分組數(shù)量，根據(jù)第一次分組粒度和二次分組的數(shù)量計(jì)算二次分組的粒度，計(jì)算公式為：

minGrain＝grain/minGroup