Hadoop學(xué)習(xí)之路（一）理論基礎(chǔ)和邏輯思維

HK123COM 2019-02-14

展開全文

三個(gè)題目

正文

回到頂部

三個(gè)題目

第一題

問題描述

統(tǒng)計(jì)出當(dāng)前這個(gè)一行一個(gè)IP的文件中，到底哪個(gè)IP出現(xiàn)的次數(shù)最多

解決思路

//必須要能讀取這個(gè)內(nèi)容  

        BufferedReader br = new BuffedReader(new FileInputStream(new File("c:/big.txt")));
          // 每次讀取一行
        String line = null;
        while( (line=br.readLine()) != null){
            // 處理這讀取到的一行內(nèi)容的代碼
        }

        //最簡(jiǎn)單的一種思路：  初始化一個(gè)hashmap

        //hashmap中存儲(chǔ)的鍵值對(duì)的  key ： IP      value : 次數(shù)

        int count = 0;  // 就是用來(lái)進(jìn)行存儲(chǔ)當(dāng)前出現(xiàn)次數(shù)最多的那個(gè)IP的次數(shù)
        String maxip = null;
        Set<String> ips = hashmap.keySet();
        for(String ip :  ips){
            int ipcount = hashmap.get(ip)
            if(ipcount > count){
                count = ipcount
                maxip = ip;
            }
        }
        System.out.println(maxip + " : " +count);

問題難點(diǎn)

1、當(dāng)讀取的文件的大小超過內(nèi)存的大小時(shí)，以上的解決方案是不可行的。

2、假如說你的內(nèi)存足夠大，能裝下這個(gè)文件中的所有ip，整個(gè)任務(wù)的執(zhí)行效率會(huì)非常低，消耗的時(shí)間會(huì)非常的長(zhǎng)。

　　1GB -- 5分

　　1TB --- 1024 * 5 分

3、最終整個(gè)任務(wù)就使用一臺(tái)機(jī)器，那么最終整個(gè)任務(wù)執(zhí)行完成所消耗的時(shí)間是和數(shù)據(jù)的大小成正比。提升服務(wù)器的執(zhí)行性能來(lái)提高數(shù)據(jù)的處理速度。

　　　　當(dāng)前這一臺(tái)機(jī)器的執(zhí)行性能：　　　　 5分鐘/GB

　　　　提升服務(wù)器的執(zhí)行性能： CPU ：i3 ---> i7 1分鐘/GB

在最開始的服務(wù)器領(lǐng)域：提升服務(wù)器對(duì)外提供服務(wù)的效率手段就是縱向提升服務(wù)器性能。理想是豐滿的，現(xiàn)實(shí)是骨感的，但是服務(wù)器性能提升有瓶頸。

摩爾定律：每隔18-24個(gè)月，服務(wù)器的性能提升一倍。

如果說數(shù)據(jù)的增長(zhǎng)是每隔18-24個(gè)月就增長(zhǎng)一倍,工作量增加了一倍。工作效率也增加了一倍，那么最終完成同一個(gè)任務(wù)所花費(fèi)的時(shí)間是一樣的。

但是數(shù)據(jù)的增長(zhǎng)速度是遠(yuǎn)遠(yuǎn)超過服務(wù)器性能的提升。在數(shù)據(jù)不斷增長(zhǎng)的情況下，單位時(shí)間內(nèi)，服務(wù)器所需要處理的數(shù)據(jù)量是越來(lái)越大。

假如：

服務(wù)器的性能提升速率和數(shù)據(jù)的增長(zhǎng)速率一樣：在18-24個(gè)月
10GB --- 性能： 1分鐘/GB --- 10分鐘
20GB --- 性能： 1分鐘/2GB --- 10分鐘

假如：

服務(wù)器的性能提升速率和數(shù)據(jù)的增長(zhǎng)速率不一樣：在18-24個(gè)月
10GB --- 性能： 1分鐘/GB --- 10分鐘
100GB --- 性能： 1分鐘/2GB --- 50分鐘

最終的結(jié)論：靠縱向提升服務(wù)器性能的手段在理論上有瓶頸的。

最終解決方案：縱向不可取，所以采取橫向擴(kuò)展。

所謂的橫向擴(kuò)展：就是增加服務(wù)器的數(shù)量。

一個(gè)龐大的復(fù)雜任務(wù)就應(yīng)該 平均分配給所有的服務(wù)器做處理

10GB 一臺(tái)服務(wù)器 10分鐘

100GB 一臺(tái)服務(wù)器 100分鐘

100GB 10臺(tái)服務(wù)器 10分鐘

10000GB 1000臺(tái) 10分鐘

在理論上 有上限么？？沒有

兩種情況下：
1、在數(shù)據(jù)量比較小的情況下，單臺(tái)服務(wù)器就可以再用戶可接受的時(shí)限范圍內(nèi)完成任務(wù)。
2、當(dāng)數(shù)據(jù)量變大時(shí)，如果用戶也想在可接受的時(shí)限范圍內(nèi)完成任務(wù)，那么可行的方案就是進(jìn)行服務(wù)器的橫向擴(kuò)展。

核心思想：大事化小分而治之
終極解決方案：
1、先把文件切碎成很多的小文件。
2、每一個(gè)服務(wù)器節(jié)點(diǎn)去處理一個(gè)小文件。
3、再把所有服務(wù)器的處理結(jié)果匯總到一起。
4、再把所有的數(shù)據(jù)合并到一起求出出現(xiàn)次數(shù)最多的那個(gè)ip。

只要是通過網(wǎng)絡(luò)傳輸數(shù)據(jù)，就一定存在丟失數(shù)據(jù)的可能。

第二題

問題描述

在兩個(gè)龐大文件中，文件也都是存儲(chǔ)的URL地址（每行一個(gè)），比如文件名叫做file1和file2, 找出這兩個(gè)文件中的交集（相同的URL）？

以上問題等同于SQL：select url from file1 a join file2 b on a.url = b.url

問題分析

概念：出現(xiàn)在在file1中的元素也出現(xiàn)在file2中。這些元素的集合就是交集

需求：求2個(gè)文件的交集

文件中的元素：URL

解決方案

1.當(dāng)2個(gè)文件都比較小的時(shí)候

　　步驟：

　　　　1.　編寫一個(gè)程序可以去讀文件的內(nèi)容，把文件中的所有元素都放置在一個(gè)set1中

　　　　　　　　編寫一個(gè)流處理取讀取文件內(nèi)容，逐行讀取，每次讀取到的一行放入set1中

　　　　2.　運(yùn)行相同的程序處理另外一個(gè)文件的內(nèi)容，把文件中的所有元素都放置在一個(gè)set2中

　　　　3.　先遍歷一個(gè)集合，每次遍歷出來(lái)的元素都去另外一個(gè)集合中判斷存在不存在。如果存在，就是共同元素，這個(gè)共同元素就存儲(chǔ)在某個(gè)集合中resultSet；如果不存在，就不是共同元素。

　　　　4.　結(jié)果集：集合resultSet

2.當(dāng)2個(gè)文件都比較大的時(shí)候

　　第一種思路：采取跟第一個(gè)題目一樣的大事化小的策略

　　第二種思路：改良第一種思路。避免第一種思路中的很多無(wú)效匹配　a1 * a2

　　　　　　　　必須做到合理的數(shù)據(jù)分區(qū)，數(shù)據(jù)分區(qū)的兩種最基本的思路：

　　　　　　　　　　1.先排序，然后分段==分區(qū)

　　　　　　　　　　2.hash散列　　--　　求hash值，然后利用hash值求和分區(qū)個(gè)數(shù)的余數(shù)，如果余數(shù)相同，就證明這些元素在同一個(gè)分區(qū)中

　　　　　　　　改良了實(shí)現(xiàn)思路之后，可以讓原來(lái)應(yīng)該執(zhí)行16個(gè)小任務(wù)的大任務(wù)。只需要執(zhí)行4個(gè)小任務(wù)即可。

終極解決方案：

1.先指定一個(gè)分區(qū)策略：hash散列

2.預(yù)估預(yù)估一下數(shù)據(jù)要被切分成多少個(gè)塊，一定要保證兩個(gè)文件切分出來(lái)的小文件個(gè)數(shù)成倍數(shù)

3.根據(jù)hash散列的策略，對(duì)兩份文件分別進(jìn)行操作

4.根據(jù)原來(lái)指定的策略，尋找對(duì)應(yīng)的兩個(gè)大文件中的對(duì)應(yīng)小文件進(jìn)行求交集操作

5.所有的結(jié)果，根本就不用再進(jìn)行去重了。直接進(jìn)行拼接即可。

學(xué)到的東西：

　　整個(gè)大數(shù)據(jù)生態(tài)系統(tǒng)中的很多技術(shù)軟件的底層處理數(shù)據(jù)的分區(qū)時(shí)，默認(rèn)的策略都是hash散列。

第三題

問題描述

現(xiàn)在有一個(gè)非常龐大的URL庫(kù)（10000E），然后現(xiàn)在還有一個(gè)URL，（迅速）判斷這個(gè)URL是否在這個(gè)URL庫(kù)中？

問題分析

需求：判斷一個(gè)元素在不在某個(gè)集合中

解決方案

1、計(jì)數(shù)排序

1、初始化一個(gè)數(shù)組數(shù)組的長(zhǎng)度就是集合中元素的區(qū)間長(zhǎng)度

2、遍歷集合，把每個(gè)元素放入數(shù)組中尋找對(duì)應(yīng)的下標(biāo)位置，找出值，然后重新設(shè)置成+1的值

3、按序遍歷即可

array[0] = 1, array[1] = 2, array[2] = 0, array[3] = 3,

0 1 1 3 3 3

2、改進(jìn)需求：

求出某個(gè)元素在不在這個(gè)數(shù)組（數(shù)據(jù)結(jié)構(gòu)改良之前的集合）中

array[5] = count if count > 0

3、既然是判斷存在不存在。

所以結(jié)果其實(shí)就是一個(gè)狀態(tài) ：要么存在要么不存在

存在： 1
不存在： 0

把int數(shù)組進(jìn)化成為位數(shù)組

優(yōu)勢(shì)：把數(shù)組所要消耗的內(nèi)存降低到原來(lái)的 1/32

改良了之后這種數(shù)據(jù)結(jié)構(gòu)： BitMap

真正的結(jié)構(gòu)：一個(gè)位數(shù)組 + 一個(gè)hash函數(shù)

4、BitMap再次進(jìn)行進(jìn)化

解決的問題： BitMap 中非常容易出現(xiàn) hash碰撞的問題

咱們可以結(jié)合使用多個(gè)hash函數(shù)來(lái)搞定

缺點(diǎn)：存在一定的誤判率

1、如果這種數(shù)據(jù)結(jié)構(gòu)（BloomFilter）告訴你說你要驗(yàn)證的那個(gè)元素不在這個(gè) BloomFilter 中
那就表示這個(gè)元素一定不在這個(gè) BloomFilter 中

2、如果它告訴你這個(gè)元素存在，它告訴你的這個(gè)存在的結(jié)果有可能是假的

真正的組成：

一個(gè)位數(shù)組 + 一組hash函數(shù)

如果要做工程實(shí)現(xiàn)：不管是什么變種的BloomFilter，都一定要實(shí)現(xiàn)兩個(gè)方法：

1、第一個(gè)方法是往BloomFilter中存入一個(gè)元素

2、第二個(gè)方法是驗(yàn)證一個(gè)元素是否在這個(gè)BloomFilter 中

誤判率的估計(jì)：

1、位數(shù)組的長(zhǎng)度 m

2、總元素的個(gè)數(shù) n

3、hash函數(shù)的個(gè)數(shù) k

hash函數(shù)的個(gè)數(shù) 并不是越多越好

在誤判率最低的情況下。這三個(gè)參數(shù)應(yīng)該滿足的一個(gè)公式： k = 0.7 * m / n

本站是提供個(gè)人知識(shí)管理的網(wǎng)絡(luò)存儲(chǔ)空間，所有內(nèi)容均由用戶發(fā)布，不代表本站觀點(diǎn)。請(qǐng)注意甄別內(nèi)容中的聯(lián)系方式、誘導(dǎo)購(gòu)買等信息，謹(jǐn)防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請(qǐng)點(diǎn)擊一鍵舉報(bào)。

轉(zhuǎn)藏 分享

QQ空間 QQ好友新浪微博微信

獻(xiàn)花（0） +1

來(lái)自： HK123COM > 《hadoop》

舉報(bào)/認(rèn)領(lǐng)