混合盤散列連接算法設(shè)計(jì)及其應(yīng)用.pdf

1、隨著新一代存儲(chǔ)設(shè)備固態(tài)盤的發(fā)展，由固態(tài)盤和硬盤組成混合存儲(chǔ)系統(tǒng)已成為熱點(diǎn)研究課題。本文利用固態(tài)盤和硬盤的存儲(chǔ)特性，對(duì)傳統(tǒng)散列連接（GHJ、HHJ）進(jìn)行優(yōu)化，得到四個(gè)基于混合存儲(chǔ)系統(tǒng)設(shè)計(jì)的散列連接算法（CGHJ、CHHJ、H-CGHJ和 H-CHHJ，合稱混合盤散列連接），并給出算法的I/O代價(jià)和時(shí)間代價(jià)模型；同時(shí)，設(shè)計(jì)了查詢計(jì)劃選擇器，選擇適應(yīng)當(dāng)前可用資源、性能較優(yōu)的連接算法，實(shí)現(xiàn)性能體面降級(jí)。在工程應(yīng)用方面，設(shè)計(jì)了分布式流量計(jì)算系統(tǒng)處

2、理交通數(shù)據(jù)，將混合盤散列連接算法作為流量計(jì)算系統(tǒng)的核心處理算法，統(tǒng)計(jì)區(qū)域間交通流量信息。本文主要貢獻(xiàn)如下：
　　1.設(shè)計(jì)混合盤散列連接算法。將固態(tài)盤作為中間存儲(chǔ)緩存，設(shè)計(jì)了一組新的連接散列算法（CGHJ，CHHJ，H-CGHJ和H-CHHJ），并給出兩種緩存分配方案，優(yōu)化算法性能。
　　2.連接算法I/O代價(jià)模型和時(shí)間代價(jià)模型。通過分析連接算法執(zhí)行過程中各階段操作行為，給出算法執(zhí)行時(shí)的I/O代價(jià)和時(shí)間代價(jià)的估算模型，并給出算

3、法各階段對(duì)外存進(jìn)行訪問時(shí)的吞吐量估算方法。
　　3.查詢計(jì)劃選擇器與性能降級(jí)機(jī)制。設(shè)計(jì)了查詢計(jì)劃選擇器，在內(nèi)存及固態(tài)盤等計(jì)算資源有限的情況下，選擇性能最優(yōu)的連接算法，實(shí)現(xiàn)系統(tǒng)性能體面降級(jí)。
　　4.將混合盤連接算法應(yīng)用到交通數(shù)據(jù)處理中。混合盤散列連接算法作為系統(tǒng)核心處理算法，實(shí)現(xiàn)交通流量計(jì)算系統(tǒng)，統(tǒng)計(jì)不同區(qū)域之間的交通流量信息。
　　一系列實(shí)驗(yàn)結(jié)果表明本文設(shè)計(jì)的混合盤散列連接算法較傳統(tǒng)散列連接（GHJ，HHJ）有明顯的