最近遇到了一個(gè)任務(wù)折騰了我一個(gè)周多，終于跑成功了，解決的過(guò)程就是一個(gè)漸漸認(rèn)清大數(shù)據(jù)計(jì)算原理的過(guò)程，希望對(duì)大家有幫助。

一、任務(wù)背景

1.1 資源一：一個(gè)表

現(xiàn)在有一個(gè)表，名為Item 有item_group, item_id, feature 三個(gè)字段，分別代表物品所在的類別，物品ID，物品的特征 如下圖： 

2.2 資源二：相似度函數(shù)

還有一個(gè)函數(shù)F(feature1, feature2) 輸入兩個(gè)物品的feature，返回這兩個(gè)物品的相似度。

2.3 目標(biāo)

現(xiàn)在需要計(jì)算的是在同一個(gè)類別下物品之間兩兩的相似度。

2.4 相關(guān)信息

1.item表總共300萬(wàn)條記錄，parquet格式來(lái)存儲(chǔ)，總大小36G2.總共有1.5萬(wàn)個(gè)item_group，最大的一個(gè)item_group有8000多個(gè)item3.feature是個(gè)json字符串，每個(gè)大概有8萬(wàn)Byte，約80K4.函數(shù)F平均一分鐘處理10000條數(shù)據(jù)

大家可以幫我想想，如果你來(lái)做這個(gè)任務(wù)要怎么進(jìn)行計(jì)算呢。

二、我的嘗試

2.1 方案1：item和item join

上來(lái)就啥都沒(méi)想，item和item用item_group join一下就能得到同一個(gè)item_group下的兩兩組合(這里我們成為item_pair)，就可以計(jì)算相似度了。so easy。

select a.item_id  id1,     b.item_id id2,     F(a.feature, b.feature) score from item a join item b          on a.item_group = b.item_group           and a.item_id>b.item_id  

非常完美清晰，簡(jiǎn)單即有效，所有的數(shù)據(jù)基本都只用計(jì)算一次。然鵝幾個(gè)小時(shí)之后： 

org.apache.spark.shuffle.MetadataFetchFailedException:  Missing an  
output location for shuffle 0  

什么鬼讀取shuffle失敗，再仔細(xì)一看原來(lái)是熟悉的OOM(out of memory)。 

ExecutorLostFailure (executor 20 exited caused by one of the running  
tasks) Reason:   Container killed by YARN for exceeding memory  
limits.    90.4 GB of 88 GB physical memory used.   Consider boosting 
  spark.yarn.executor.memoryOverhead.  

遇到這種狀況加內(nèi)存、加shuffle分區(qū)數(shù)(設(shè)置spark.sql.shuffle.partitions)這是常規(guī)操作

然鵝幾個(gè)小時(shí)之后又掛了，還是一樣的問(wèn)題。難道是feature太大了?后來(lái)我把feature進(jìn)行了壓縮，從80k一下子壓縮到了8K，結(jié)果又雙叒掛了

方案1徹底卒。

2.2 方案2 先生成pair

冷靜!我要冷靜下來(lái)分析。既然是feature占了主要的內(nèi)存，那我前期可以先不帶上feature，先計(jì)算出需要計(jì)算的item_pair，第二步在計(jì)算的時(shí)候join上feature就可以了呀，我真是太聰明了。方案2：

select a.item_id  id1,    b.item_id id2,from item ajoin item b    on a.item_group = b.item_group     and a.item_id>b.item_id 

存為item_pair表然后再join feature 計(jì)算分?jǐn)?shù)

select id1,  id2,  F(a.feature, b.feature) scorefrom item_pairjoin  
item a    on item_pair.id1=a.item_idjoin item b    on  
item_pair.id2=b.item_id 

結(jié)果又雙叒叕過(guò)了好多個(gè)小時(shí)，item_pair表跑出來(lái)了正高興著，結(jié)果第二部分，依舊掛掉，依舊memoryOverhead。懷疑人生了。

三、真正的認(rèn)真分析

多次的失敗終于使我冷靜了下來(lái)，認(rèn)真回憶起了spark相關(guān)的知識(shí)。下面是我認(rèn)真的分析：

3.1 上文方案1的分析：

按照item_group自己和自己join的話，會(huì)如下圖。下游會(huì)按照item_group聚集起來(lái)做join。 

我們來(lái)計(jì)算一下：

• 表中最大一個(gè)group有8000個(gè)item。
• 生成不重復(fù)的pair也會(huì)有組合數(shù)C(n,2)=n×(n-1)/2=31996000，3千萬(wàn)個(gè)pair。
• 每個(gè)feature優(yōu)化之后占8K，一個(gè)pair就是16K，3千萬(wàn)就是480G，也就是一個(gè)group就要占480G，何況shuffle時(shí)一個(gè)task里不止一個(gè)group。

經(jīng)過(guò)計(jì)算內(nèi)存不爆那是不可能的。

3.2 方案2的分析：

生成item_pair 基本不耗什么內(nèi)存，最終生成20億條item_pair。到了第二步的時(shí)候我們來(lái)看看，數(shù)據(jù)是怎么流動(dòng)的。如下圖： 

第一階段item_pair按照id1去分組，分發(fā)到下游的節(jié)點(diǎn)，我們按最做多那個(gè)ID計(jì)算的話有至少有8000條數(shù)據(jù)會(huì)被分到一個(gè)分區(qū)結(jié)合上feature字段，也就是會(huì)生成64M的數(shù)據(jù)。

這還是單個(gè)item_id，總共有300萬(wàn)個(gè)item_id，不可能shuffle的時(shí)候用300萬(wàn)個(gè)分區(qū)每個(gè)分區(qū)一個(gè)item_id吧，就算每個(gè)分區(qū)放1000個(gè)題目需要占64個(gè)G，要3000個(gè)分區(qū)。

第二階段數(shù)據(jù)加上id2的feature，數(shù)據(jù)量會(huì)擴(kuò)大一倍變成128G，3000個(gè)分區(qū)。看樣子能行，但是實(shí)際操作起來(lái)耗費(fèi)的內(nèi)存可比這個(gè)大很多，而且分區(qū)太多出現(xiàn)各種奇怪的問(wèn)題，比如shuffle文件丟失啥的，而且之后group下面的題目增多就只能不斷擴(kuò)大內(nèi)存了，實(shí)在不是個(gè)好辦法。得考慮其他的方案了。

四、最后的解決方案

4.1 在item_group總切分成多個(gè)組合數(shù)的子任務(wù)

item_group總共就1.5萬(wàn)個(gè)，最多的一個(gè)有8000個(gè)feature，也就64M，麻煩的點(diǎn)就在于要在item_group里求組合數(shù)(兩兩配對(duì))。

能不能把求組合數(shù)這一步切分成不同的子任務(wù)，再在每個(gè)子任務(wù)里去求組合數(shù)，這樣不但能減少內(nèi)存消耗，還能增加并行度。

我們來(lái)畫(huà)個(gè)組合數(shù)的圖。 

上圖我們可以按照閾值為3進(jìn)行分割，就可以把整個(gè)圖切分成幾個(gè)小子圖進(jìn)行計(jì)算了。

實(shí)際進(jìn)行的時(shí)候如果我們按500進(jìn)行分割的話，8000個(gè)item的group可以分成136個(gè)子任務(wù)，子任務(wù)中最大的一個(gè)會(huì)有500×500=250000個(gè)pair，但數(shù)據(jù)的話就只需要傳最多1000個(gè)feature也就是8M的數(shù)據(jù)，子任務(wù)數(shù)就算在原有不切割的15000個(gè)group上擴(kuò)增1.5倍也就是15000×1.5=22500個(gè)，設(shè)置2000個(gè)分區(qū)，每個(gè)分區(qū)11個(gè)子任務(wù)，內(nèi)存耗費(fèi)11×8M=88M，共計(jì)算250000×11次，每1萬(wàn)次一分鐘，也就是一個(gè)分區(qū)得跑4個(gè)小時(shí)左右，實(shí)際上也差不多。 

五、總結(jié)和問(wèn)題

總結(jié)起來(lái)就是最開(kāi)始太自信了。

1. 沒(méi)有仔細(xì)的思考
2. 沒(méi)有認(rèn)真調(diào)查數(shù)據(jù)的規(guī)模
3. 沒(méi)有認(rèn)真考慮在每個(gè)方案數(shù)據(jù)是怎么在spark中流動(dòng)
4. 沒(méi)有認(rèn)真做計(jì)算。