国产一级a片免费看高清,亚洲熟女中文字幕在线视频,黄三级高清在线播放,免费黄色视频在线看

打開APP
userphoto
未登錄

開通VIP,暢享免費(fèi)電子書等14項(xiàng)超值服

開通VIP
BitTorrent中的數(shù)據(jù)塊校驗(yàn)方式改進(jìn):Merkle Hashing Tree - NeoRAGEx2002's Weblog - 博客園

大家都知道,目前BT應(yīng)用的發(fā)展具有一個(gè)非常顯著的趨勢(shì),那就是用來(lái)交換電影、游戲、ISO等大尺寸的數(shù)據(jù)文件。然而我們也能夠觀察到另一個(gè)事實(shí),那就是:下載文件所對(duì)應(yīng)的索引文件(.torrent)也越來(lái)越大,越來(lái)越難以下載;這是因?yàn)樵谒饕募斜4媪吮幌螺d文件中所有數(shù)據(jù)塊的20字節(jié)SHA1校驗(yàn)值,而文件越大,數(shù)據(jù)塊越多,則.torrent文件越長(zhǎng)(塊數(shù)=文件長(zhǎng)度/數(shù)據(jù)塊長(zhǎng),BitTorrent標(biāo)準(zhǔn)協(xié)議建議塊長(zhǎng)一般不超過(guò)512KB)。

索引文件長(zhǎng)度的膨脹將直接加重索引服務(wù)器的下載負(fù)擔(dān),因?yàn)樗蠦T用戶均必須從服務(wù)器上下載同一份.torrent文件,而這一下載行為本身是集中式的,因而導(dǎo)致系統(tǒng)的擴(kuò)展性受到較大限制,尤其是用于交換熱門資源時(shí);另一方面,為避免索引文件過(guò)大,人們?cè)诎l(fā)布種子、制作索引文件時(shí)不得不采用增加其基本數(shù)據(jù)塊長(zhǎng)度(比如2MB)的方式來(lái)減少數(shù)據(jù)塊總數(shù),這將有可能對(duì)端對(duì)端數(shù)據(jù)交換性能造成一系列負(fù)面影響:因?yàn)閴K長(zhǎng)越小,越能幫助我們及時(shí)地發(fā)現(xiàn)傳輸錯(cuò)誤,試想在2MB塊長(zhǎng)的情況下,用戶直到下載完整個(gè)數(shù)據(jù)塊時(shí)才通過(guò)校驗(yàn)發(fā)現(xiàn)傳輸有誤,然后不得不再次重傳整個(gè)2MB塊,這顯然較塊長(zhǎng)為512KB時(shí)更加浪費(fèi)帶寬和時(shí)間。歸根到底,導(dǎo)致上述麻煩的根本原因在于這么一個(gè)事實(shí):“.torrent中包含了所有數(shù)據(jù)塊的SHA1校驗(yàn)信息”。

有什么辦法讓我們既能獲得較小的塊長(zhǎng)而又能減少索引文件長(zhǎng)度?Merkle哈希樹校驗(yàn)方式為我們提供了一個(gè)很好的思路,它試圖從校驗(yàn)信息獲取及實(shí)際校驗(yàn)過(guò)程兩個(gè)方面來(lái)改善上述問(wèn)題。先說(shuō)說(shuō)什么是哈希樹,以最簡(jiǎn)單的二叉方式為例,如下圖所示,設(shè)某文件共13個(gè)數(shù)據(jù)塊,我們可以將其padding到16(2的整數(shù)次方)個(gè)塊(注意,padding的空白塊僅用于輔助校驗(yàn),而無(wú)需當(dāng)作數(shù)據(jù)進(jìn)行實(shí)際傳輸),每個(gè)塊均對(duì)應(yīng)一個(gè)SHA1校驗(yàn)值,然后再對(duì)它們進(jìn)行反復(fù)的兩兩哈希,直到得出一個(gè)唯一的根哈希值為止(root hash,H0),這一計(jì)算過(guò)程便構(gòu)成了一棵二元的Merkle哈希樹,樹中最底層的葉子節(jié)點(diǎn)(H15~H30)對(duì)應(yīng)著數(shù)據(jù)塊的實(shí)際哈希值,而那些內(nèi)部節(jié)點(diǎn)(H1~H14)我們則可以將其稱為“路徑哈希值”,它們構(gòu)成了實(shí)際塊哈希值與根哈希值H0之間的“校驗(yàn)路徑”,比如,數(shù)據(jù)塊8所對(duì)應(yīng)的實(shí)際哈希值為H23,則有:SHA1(((SHA1(SHA1(H23,H24),H12),H6),H1)應(yīng)該等于H0。當(dāng)然,我們也可以進(jìn)一步采用n元哈希樹來(lái)進(jìn)行上述校驗(yàn)過(guò)程,其過(guò)程是類似的。

采用Merkle哈希樹校驗(yàn)方式能夠極大地減小.torrent文件的尺寸,這是因?yàn)?,一旦采用這種方式來(lái)校驗(yàn)數(shù)據(jù)塊,那么便沒(méi)有必要在.torrent文件中保存所有數(shù)據(jù)塊的校驗(yàn)值了,其中僅需保存一個(gè)20字節(jié)的SHA1哈希值即可,即整個(gè)下載文件的根哈希值H0。想象一下一個(gè)3、4GB的文件,其對(duì)應(yīng).torrent文件卻只有100-200字節(jié)的樣子?heh

下面,讓我們來(lái)看看其數(shù)據(jù)塊交換及校驗(yàn)的詳細(xì)過(guò)程:

  1. 以下載某大文件F為例,為啟動(dòng)BT交換,每一個(gè)client均必須從索引服務(wù)器中下載F所相應(yīng)的.torrent文件,從而得到文件長(zhǎng)度、數(shù)據(jù)塊長(zhǎng)及根哈希值H0等必要信息;
  2. 任一client均可通過(guò)輪詢Tracking服務(wù)器或者是DHT方式來(lái)定位其他參與交換F數(shù)據(jù)的peer,進(jìn)而與之建立TCP連接進(jìn)行P2P文件交換,其定位peer的方式基本上沒(méi)有什么改變。
  3. 當(dāng)client從某一peer下載一個(gè)數(shù)據(jù)塊時(shí),它將事先向peer發(fā)出相應(yīng)的校驗(yàn)查詢請(qǐng)求,要求對(duì)方提供校驗(yàn)當(dāng)前下載塊所需的路徑哈 希值,這一過(guò)程可以很方便地通過(guò)擴(kuò)展標(biāo)準(zhǔn)的Peer Wire Protocol實(shí)現(xiàn)。以上圖為例,當(dāng)client下載的是數(shù)據(jù)塊8時(shí),在下載開始之前,它將要求peer提供校驗(yàn)塊8所需的全部路徑哈希值:H24、 H12、H6和H1;
  4. 當(dāng)client下載完某數(shù)據(jù)塊之后,它將對(duì)其進(jìn)行哈希樹校驗(yàn);仍以校驗(yàn)塊8為例,client將首先計(jì)算出塊8的哈希值H23',然后 再根據(jù)peer所提供的信息依次計(jì)算各層路徑哈希值,直至求得一個(gè)唯一的根校驗(yàn)值H0',如果H0'等于.torrent文件中的H0,則數(shù)據(jù)塊下載無(wú) 誤,校驗(yàn)通過(guò);反之則校驗(yàn)失敗。
  5. 一旦某數(shù)據(jù)塊校驗(yàn)通過(guò),與其哈希樹校驗(yàn)過(guò)程相關(guān)的所有路徑哈希值均可以作為cache緩存下來(lái),而不管其究竟是從peer查詢所得的, 還是由client自身計(jì)算所得的;但值得注意的是,如果該數(shù)據(jù)塊的校驗(yàn)未通過(guò),則其所有相關(guān)的路徑哈希值均不能被cache,而只能被廢棄,因?yàn)榇藭r(shí)我 們無(wú)法保證peer所提供的路徑哈希值的正確性(不能排除peer故意提供錯(cuò)誤路徑哈希值和哈希值傳輸出錯(cuò)的可能)。例如,所有與塊8校驗(yàn)相關(guān)的路徑哈希 包括:H24、H12、H6、H1、H11、H5、H2,其中前面4個(gè)經(jīng)查詢peer所得,而后面3個(gè)則由client自己計(jì)算所得。塊8驗(yàn)證的結(jié)果將決 定這7個(gè)路徑哈希是否可信及是否能被cache。
  6. 當(dāng)一定數(shù)量的路徑哈希值被緩存之后,后繼數(shù)據(jù)塊的校驗(yàn)過(guò)程將被極大簡(jiǎn)化。此時(shí)我們可以直接利用校驗(yàn)路徑上層次最低的已知路徑哈希值來(lái)對(duì) 數(shù)據(jù)塊進(jìn)行部分校驗(yàn),而無(wú)需每次都校驗(yàn)至根哈希值H0,這主要是因?yàn)椋耗骋宦窂焦V当籧ache這一事實(shí)本身便能夠證明其是可信的;例如,在塊8校驗(yàn)完 成之后,client無(wú)需進(jìn)行額外的peer查詢便可以直接對(duì)塊9進(jìn)行校驗(yàn),因此它已經(jīng)知道了H24的值,并且通過(guò)塊8的校驗(yàn)過(guò)程驗(yàn)證了H24的正確性; 而當(dāng)client需要對(duì)塊10進(jìn)行校驗(yàn)時(shí),它僅需向peer查詢H26一個(gè)校驗(yàn)值即可,由于我們已經(jīng)知道了H12值,因此對(duì)塊10的校驗(yàn)僅需2次SHA1 哈希即可:一次是計(jì)算塊哈希H25,一次是計(jì)算SHA1(H25,H26),并比較其等不等于H12。同理,當(dāng)需要驗(yàn)證塊12時(shí),由于已知 H6,client僅需查詢2個(gè)路徑哈希(H28和H14)和3次SHA1計(jì)算(H27、SHA1(H27,H28)和SHA1(H13,H14))即 可。緩存的路徑哈希值越多,則后繼數(shù)據(jù)塊校驗(yàn)越容易,速度也越快。
  7. 為了進(jìn)一步提高校驗(yàn)效率,可以考慮在.torrent文件上再做做文章:令其保存整個(gè)哈希樹中最上面的若干層路徑哈希值,而不僅僅只是 一個(gè)根哈希值H0,底層的路徑哈希值則仍然依靠詢問(wèn)peer或client自身計(jì)算所得,從而實(shí)現(xiàn).torrent文件尺寸與校驗(yàn)效率的有效折衷。

最后再來(lái)看看上述算法的時(shí)空效率如何。假設(shè)某文件的總塊數(shù)為M,將其padding至N個(gè)塊(N=2^p),塊長(zhǎng)為K,不難看出:

  1. 為了校驗(yàn)整個(gè)文件,共需緩存Sum(2^i):i=0 to p,即2N-1個(gè)20字節(jié)的SHA1哈希值(包括根哈希值、所有路徑哈希值和塊哈希值)。以512KB為塊長(zhǎng)的一個(gè)4GB的文件為例,M=8000,則 N=8192,p=13,所需存儲(chǔ)空間為(2*8192-1)*20=327660 Bytes=319KB,其緩沖區(qū)較普通校驗(yàn)方式翻倍,但即便如此,校驗(yàn)所需的數(shù)據(jù)量仍完全可以接受,即使在最糟糕的情況下:完全不用cache、全部依 賴peer查詢來(lái)獲得這些校驗(yàn)值,也無(wú)非總共增加了1個(gè)基本塊不到的流量而已,而且這些流量還是通過(guò)P2P方式得到的。
  2. 在無(wú)校驗(yàn)失敗的理想情況下,校驗(yàn)整個(gè)文件共需M次塊長(zhǎng)為K的SHA1計(jì)算,和N-1次長(zhǎng)度為20字節(jié)的SHA1運(yùn)算。即,以哈希樹方式 校驗(yàn)塊長(zhǎng)512KB的4GB文件,共需進(jìn)行8000次長(zhǎng)度為512KB的SHA1計(jì)算,同時(shí)外加8191次長(zhǎng)為2*20字節(jié)的路徑哈希計(jì)算,與普通校驗(yàn)方 式相比,后者是哈希樹額外引入的開銷,但由于每次路徑哈希的計(jì)算量非常小,其影響幾可忽略。

綜上所述,通過(guò)采用哈希樹校驗(yàn)方式,我們可以將諸多校驗(yàn)所需哈希值的獲取工作分散在P2P數(shù)據(jù)交換時(shí)捎帶進(jìn)行,而不是從.torrent文件中集中獲取,從而有利于緩解索引服務(wù)器集中下載瓶頸,優(yōu)化Peer toPeer數(shù)據(jù)傳輸性能;在實(shí)現(xiàn)上述目的的同時(shí),哈希樹校驗(yàn)機(jī)制仍能保證以P2P方式獲取的校驗(yàn)信息的可靠性,在小塊長(zhǎng)的情況下,惡意peer幾乎無(wú)法通過(guò)故意提供錯(cuò)誤路徑哈希值的方式來(lái)實(shí)現(xiàn)有效的服務(wù)拒絕攻擊。采用這種方式,我們所需付出的額外代價(jià)主要包括幾近1倍的校驗(yàn)緩存空間及其SHA1計(jì)算量的增長(zhǎng),但是經(jīng)過(guò)簡(jiǎn)要分析不難看出其實(shí)際影響不甚明顯,這對(duì)于換取較小的塊長(zhǎng)、提高大文件P2P交換效率而言是值得的。Merkle哈希樹校驗(yàn)方式與分布式哈希表技術(shù)勢(shì)必能夠幫助BitTorrent協(xié)議進(jìn)一步克服自身的非結(jié)構(gòu)化缺陷,取得更大的應(yīng)用發(fā)展。

本站僅提供存儲(chǔ)服務(wù),所有內(nèi)容均由用戶發(fā)布,如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容,請(qǐng)點(diǎn)擊舉報(bào)。
打開APP,閱讀全文并永久保存 查看更多類似文章
猜你喜歡
類似文章
防黑手 文件校驗(yàn)這幾招就夠了
威聯(lián)通Transmission設(shè)置
HashTab 5.1.0.23
修改md5是什么意思?一分鐘幫你科普
GlusterFs集群、卷的創(chuàng)建使用與管理
115非VIP禮包碼轉(zhuǎn)存技術(shù)貼
更多類似文章 >>
生活服務(wù)
分享 收藏 導(dǎo)長(zhǎng)圖 關(guān)注 下載文章
綁定賬號(hào)成功
后續(xù)可登錄賬號(hào)暢享VIP特權(quán)!
如果VIP功能使用有故障,
可點(diǎn)擊這里聯(lián)系客服!

聯(lián)系客服