[發(fā)明專利]一種可擴(kuò)展的分布式查詢方法及裝置

有效

• 申請(qǐng)?zhí)枺?/td>: 201911033551.7
• 申請(qǐng)日: 2019-10-28
• 公開（公告）號(hào): CN110866046B
• 公開（公告）日: 2021-04-27
• 發(fā)明（設(shè)計(jì)）人: 景翔;劉佳皓;黃罡;蔡華謙
• 申請(qǐng)（專利權(quán)）人: 北京大學(xué)
• 主分類號(hào): G06F16/2458
• 分類號(hào): G06F16/2458;H04L29/08
• 代理公司: 北京潤(rùn)澤恒知識(shí)產(chǎn)權(quán)代理有限公司 11319
• 代理人: 莎日娜

1.一種可擴(kuò)展的分布式查詢方法，其特征在于，所述方法應(yīng)用于對(duì)等計(jì)算P2P網(wǎng)絡(luò)系統(tǒng)中，所述P2P網(wǎng)絡(luò)系統(tǒng)包括多個(gè)節(jié)點(diǎn)，所述節(jié)點(diǎn)中包括積極列表Active List，所述ActiveList分為活躍列表Eager List和惰性列表Lazy List；其中，所述節(jié)點(diǎn)的Eager List中存放的是在P2P網(wǎng)絡(luò)系統(tǒng)上和該節(jié)點(diǎn)建立TCP連接的節(jié)點(diǎn)，用于傳遞消息；所述節(jié)點(diǎn)的Lazy List是所述Active List除Eager List中的剩余節(jié)點(diǎn)，用于傳遞消息的摘要或消息的ID，用于P2P網(wǎng)絡(luò)系統(tǒng)的優(yōu)化和容錯(cuò)；所述方法包括：

在所述P2P網(wǎng)絡(luò)系統(tǒng)中，第一節(jié)點(diǎn)獲得其父節(jié)點(diǎn)廣播的查詢請(qǐng)求，所述第一節(jié)點(diǎn)為所述P2P網(wǎng)絡(luò)系統(tǒng)中的任一節(jié)點(diǎn)；

所述第一節(jié)點(diǎn)通過樹形維護(hù)程序?qū)⑺霾樵冋?qǐng)求廣播給自身的孩子節(jié)點(diǎn)；所述孩子節(jié)點(diǎn)用于利用所述P2P網(wǎng)絡(luò)系統(tǒng)的樹形結(jié)構(gòu)，將所述查詢請(qǐng)求再?gòu)V播給自身相應(yīng)的孩子節(jié)點(diǎn)，自身相應(yīng)的孩子節(jié)點(diǎn)重復(fù)上述廣播步驟，直至將所述查詢請(qǐng)求廣播至該P(yáng)2P網(wǎng)絡(luò)系統(tǒng)上的所有節(jié)點(diǎn)；每個(gè)節(jié)點(diǎn)在收到查詢的請(qǐng)求后，檢索本地?cái)?shù)據(jù)庫(kù)，并等待其孩子節(jié)點(diǎn)的結(jié)果返回，當(dāng)收集完所有的孩子節(jié)點(diǎn)返回的數(shù)據(jù)后，做結(jié)算和去重操作，并將結(jié)果返回給其父節(jié)點(diǎn)；經(jīng)過層層反饋，當(dāng)接收到用戶查詢請(qǐng)求的根節(jié)點(diǎn)收到所有孩子節(jié)點(diǎn)的返回結(jié)果時(shí)，做最終的結(jié)算和去重操作，生成最終查詢結(jié)果，并將最終查詢結(jié)果返回給該用戶；

針對(duì)所述樹形維護(hù)程序，所述方法包括：

所述第一節(jié)點(diǎn)在將所述查詢請(qǐng)求廣播給自身的孩子節(jié)點(diǎn)時(shí)，向自身的孩子節(jié)點(diǎn)中的第二節(jié)點(diǎn)發(fā)送IHAVE消息，所述IHAVE消息中包括消息ID；

所述第二節(jié)點(diǎn)檢查自己是否已收到與所述消息ID對(duì)應(yīng)的用于傳遞所述查詢請(qǐng)求的NORMAL消息；

如果所述第二節(jié)點(diǎn)在超時(shí)時(shí)間內(nèi)未收到與所述消息ID對(duì)應(yīng)的NORMAL消息，則執(zhí)行以下步驟：

所述第二節(jié)點(diǎn)生成用于修復(fù)所述P2P網(wǎng)絡(luò)系統(tǒng)的GRAFT消息；所述GRAFT消息包括所述消息ID和接收所述IHAVE消息的請(qǐng)求；

所述第二節(jié)點(diǎn)將所述GRAFT消息發(fā)送給所述第一節(jié)點(diǎn)，并將所述第一節(jié)點(diǎn)從自身的Lazy List中移動(dòng)到Eager List中，使所述第一節(jié)點(diǎn)對(duì)所述P2P網(wǎng)絡(luò)系統(tǒng)進(jìn)行修復(fù)；

如果所述第二節(jié)點(diǎn)在超時(shí)時(shí)間內(nèi)已收到與所述消息ID對(duì)應(yīng)的NORMAL消息，則執(zhí)行以下步驟：

所述第二節(jié)點(diǎn)計(jì)算IHAVE消息的接收跳數(shù)與NORMAL消息的接收跳數(shù)差；

所述第二節(jié)點(diǎn)判斷所述跳數(shù)差是否超過跳數(shù)閾值；

若所述跳數(shù)差超過跳數(shù)閾值，所述第二節(jié)點(diǎn)對(duì)所述P2P網(wǎng)絡(luò)系統(tǒng)進(jìn)行修復(fù)。

2.根據(jù)權(quán)利要求1所述的方法，其特征在于，所述P2P網(wǎng)絡(luò)系統(tǒng)包括BroadcastTree協(xié)議、MsgTransferProt協(xié)議和PartialView協(xié)議，所述BroadcastTree協(xié)議負(fù)責(zé)P2P網(wǎng)絡(luò)系統(tǒng)的維護(hù)工作；所述MsgTransferProt協(xié)議負(fù)責(zé)查詢消息的廣播和查詢結(jié)果的驗(yàn)證傳遞；所述PartialView協(xié)議負(fù)責(zé)管理每個(gè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)，所述鄰居節(jié)點(diǎn)包括父節(jié)點(diǎn)和孩子節(jié)點(diǎn)；其中，所述Active List位于P2P網(wǎng)絡(luò)系統(tǒng)的PartialView協(xié)議中，所述PartialView協(xié)議還包括消極列表Passive List，所述Passive List中存放的是隨機(jī)節(jié)點(diǎn)，用于替換Active List中斷開連接的節(jié)點(diǎn)，保證節(jié)點(diǎn)和所述P2P網(wǎng)絡(luò)系統(tǒng)的連接。

3.根據(jù)權(quán)利要求1或2所述的方法，其特征在于，每個(gè)節(jié)點(diǎn)中包括第一Map緩存、第二Map緩存以及第三Map緩存，第一Map緩存是ReceivedMsgMap，存放的是消息ID和消息的映射，用來緩存當(dāng)前已經(jīng)收到的消息，以便于響應(yīng)其他尚未收到該消息的節(jié)點(diǎn)對(duì)該消息的請(qǐng)求；

所述第二Map緩存是NotReceivedMsgMap，緩存的是消息ID和發(fā)送該消息的節(jié)點(diǎn)的映射；當(dāng)達(dá)到指定的時(shí)長(zhǎng)時(shí)，仍未收到Eager List中的節(jié)點(diǎn)發(fā)送的該消息，觸發(fā)Timer定時(shí)器，用于向發(fā)送該消息的節(jié)點(diǎn)請(qǐng)求該消息，并修復(fù)所述P2P網(wǎng)絡(luò)系統(tǒng)；

所述第三Map緩存是TimingCacheMsgMap，負(fù)責(zé)緩存當(dāng)前收到的消息，如果在指定的時(shí)間范圍內(nèi)收到Lazy List中的節(jié)點(diǎn)發(fā)送的消息，比較兩者的跳數(shù)來決定是否優(yōu)化所述P2P網(wǎng)絡(luò)系統(tǒng)。