[發(fā)明專利]基于實(shí)時(shí)計(jì)算的基數(shù)估計(jì)的方法和系統(tǒng)

有效

• 申請(qǐng)?zhí)枺?/td>: 201610292792.3
• 申請(qǐng)日: 2016-05-05
• 公開（公告）號(hào): CN107346270B
• 公開（公告）日: 2020-05-01
• 發(fā)明（設(shè)計(jì)）人: 王向長(zhǎng);邵先凱;李威;張鵬
• 申請(qǐng)（專利權(quán)）人: 北京京東尚科信息技術(shù)有限公司;北京京東世紀(jì)貿(mào)易有限公司
• 主分類號(hào): G06F11/14
• 分類號(hào): G06F11/14;G06F16/27
• 代理公司: 中原信達(dá)知識(shí)產(chǎn)權(quán)代理有限責(zé)任公司 11219
• 代理人: 張一軍;姜?jiǎng)?/td>

本發(fā)明提供一種基于實(shí)時(shí)計(jì)算的基數(shù)估計(jì)的方法和系統(tǒng)，能夠基于概率和統(tǒng)計(jì)理論進(jìn)行高效的基數(shù)估計(jì)計(jì)算，從而滿足大數(shù)據(jù)場(chǎng)景的實(shí)時(shí)基數(shù)計(jì)算需求。該方法包括在Storm系統(tǒng)中的執(zhí)行下列步驟：實(shí)時(shí)獲取日志消息；解析所述日志消息以獲取指標(biāo)信息，所述指標(biāo)信息包括各指標(biāo)的名稱及對(duì)應(yīng)的指標(biāo)值；利用HLL基數(shù)估計(jì)算法對(duì)各指標(biāo)進(jìn)行基數(shù)估計(jì)；輸出各指標(biāo)的基數(shù)。

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

本發(fā)明涉及計(jì)算機(jī)技術(shù)及軟件領(lǐng)域，尤其涉及一種基于實(shí)時(shí)計(jì)算的基數(shù)估計(jì)的方法和系統(tǒng)。

背景技術(shù)

基數(shù)計(jì)數(shù)是對(duì)一個(gè)可重復(fù)集合中不重復(fù)元素個(gè)數(shù)的計(jì)算。例如計(jì)算整個(gè)網(wǎng)站或店鋪的獨(dú)立訪客等。在大數(shù)據(jù)的背景下，傳統(tǒng)的基數(shù)計(jì)算方法遇到一些困難，主要表現(xiàn)在隨著數(shù)據(jù)量和分析維度的增加，所需的計(jì)算資源和存儲(chǔ)資源迅速膨脹。因此需要一種高效的基數(shù)估計(jì)機(jī)制。

基數(shù)估計(jì)算法是一類概率算法，可以在誤差可控的前提下以遠(yuǎn)低于精確計(jì)算的時(shí)間和空間消耗對(duì)基數(shù)進(jìn)行估計(jì)。算法特點(diǎn):1.誤差可控2.時(shí)間和空間復(fù)度僅與估計(jì)值標(biāo)準(zhǔn)差及基數(shù)上限有關(guān)3.可合并。現(xiàn)有的基數(shù)估計(jì)計(jì)算通常采用Redis的HyperLogLogCounting功能，完成對(duì)基數(shù)的估計(jì)計(jì)數(shù)。其中，

但是利用Redis的HyperLogLog Counting進(jìn)行基數(shù)估計(jì)計(jì)算仍然存在如下缺點(diǎn)：Redis并沒有實(shí)現(xiàn)基數(shù)算法的可合并特性，導(dǎo)致大數(shù)據(jù)量下處理能力不可擴(kuò)展；由于將整個(gè)計(jì)算環(huán)節(jié)交給Redis進(jìn)行處理，系統(tǒng)和Redis形成強(qiáng)依賴關(guān)系；此外，搭建Redis集群也產(chǎn)生較大的運(yùn)營(yíng)成本。

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

有鑒于此，本發(fā)明提供一種基于實(shí)時(shí)計(jì)算的基數(shù)估計(jì)的方法和系統(tǒng)，能夠基于概率和統(tǒng)計(jì)理論進(jìn)行高效的基數(shù)估計(jì)計(jì)算，從而滿足大數(shù)據(jù)場(chǎng)景的實(shí)時(shí)基數(shù)計(jì)算需求。

為實(shí)現(xiàn)上述目的，根據(jù)本發(fā)明的一個(gè)方面，提供了一種基于實(shí)時(shí)計(jì)算的基數(shù)估計(jì)的方法。

本發(fā)明的基于實(shí)時(shí)計(jì)算的基數(shù)估計(jì)的方法包括在Storm系統(tǒng)中的執(zhí)行下列步驟：實(shí)時(shí)獲取日志消息；解析所述日志消息以獲取指標(biāo)信息，所述指標(biāo)信息包括各指標(biāo)的名稱及對(duì)應(yīng)的指標(biāo)值；利用HLL基數(shù)估計(jì)算法對(duì)各指標(biāo)進(jìn)行基數(shù)估計(jì)；輸出各指標(biāo)的基數(shù)。

可選地，所述方法還包括：解析所述日志消息之后，對(duì)獲取的指標(biāo)信息進(jìn)行校驗(yàn)，以刪除異常指標(biāo)信息。

可選地，利用HLL基數(shù)估計(jì)算法對(duì)各指標(biāo)進(jìn)行基數(shù)估計(jì)還包括：將所述指標(biāo)信息隨機(jī)分配至基數(shù)計(jì)算層的多個(gè)線程，各線程根據(jù)分配到的指標(biāo)信息，為各指標(biāo)創(chuàng)建HLL對(duì)象，利用HLL基數(shù)估計(jì)算法中的Offer方法將各指標(biāo)的指標(biāo)值加入到對(duì)應(yīng)的HLL對(duì)象中，然后定時(shí)將HLL對(duì)象發(fā)送到基數(shù)集合合并層；以及所述基數(shù)集合合并層接收HLL對(duì)象，并按各HLL對(duì)象的指標(biāo)名稱創(chuàng)建各指標(biāo)的總HLL對(duì)象，然后利用HLL算法中的Merge方法將HLL對(duì)象按照指標(biāo)名稱合并到各自對(duì)應(yīng)的總HLL對(duì)象中，以及定時(shí)利用HLL算法中的Cardinality方法對(duì)各指標(biāo)的總HLL對(duì)象進(jìn)行計(jì)數(shù)，以獲得各指標(biāo)的基數(shù)。

可選地，所述方法還包括：所述HLL對(duì)象及所述總HLL對(duì)象均保存在位于其所在服務(wù)器內(nèi)存中的LRUmap中。

可選地，所述方法還包括：定時(shí)將總HLL對(duì)象保存至外部的數(shù)據(jù)庫(kù)。

可選地，所述方法還包括：定時(shí)將各指標(biāo)的基數(shù)保存到外部的數(shù)據(jù)庫(kù)。

可選地，所述方法中的定時(shí)是指：記錄上次操作的時(shí)間，若當(dāng)前時(shí)刻與上次操作的時(shí)間差小于預(yù)設(shè)閾值，則不進(jìn)行相應(yīng)操作，若當(dāng)前時(shí)刻與上次操作的時(shí)間差大于預(yù)設(shè)閾值，則進(jìn)行相應(yīng)操作。

為實(shí)現(xiàn)上述目的，根據(jù)本發(fā)明的另一個(gè)方面，提供了一種基于實(shí)時(shí)計(jì)算的基數(shù)估計(jì)的系統(tǒng)。