Distributed Java 1 - Map-Reduce

Map-Reduce

distributed programming主要是應用在big data，以key-value pair的結構來處理。要用k-v結構是因為，這樣才能在不同的節點把同樣的key的value combine起來，所以稱為reduce (借用functional programming中的reduce operation）。

一個例子，有四個kv組合如下。mapping function把value根據乘法因子分成不同的kv pairs:

如果最後reduce是一個sum function，則在每個節點對同一個key的value就進行summation:

注意map-reduce 是functional programming paradigm（有保證之前學過的functional parallelism)，所以所有key/value都是immutable，這也提供極好的scalability和fault tolerance。

Hadoop

hadoop是一個distributed map-reduce implementation，假設運作在網路連結的不同節點群：

hadoop scheduler自動把map tasks和schedule tasks分配給節點，programmer不用操心這些事情，只要implement好map function和reduce function即可。

有其他更high-level的framework，例如Hive/Pig ，可以讓programmer不用知道map-reduce paradigm，但是會產生map-reduce program的semantics。

由於data 可能分散在數千個storage節點中:
1. mapping先把分散的data建立kv pair
2. framework shuffle 同樣的key 的kv pair到不同的processing nodes
3. reduce
4. flush back to storage

只有1. 3. 是programmer需要設計的，其他都是framework做掉了。

Spark Framework (more modern Hadoop XD)

Spark創作原因是每個節點的記憶體(caching)要能充分利用，這在Hadoop是比較弱的（hadoop會被計算結果都存入storage)。
Spark的data structure是RDD (resilient distributed dataset)，kv pair可以是其中一種選項。

Hadoop的map-reduce operation被generalized:
intermediate transforms: 可以是map / filter / join / ...
terminal actions: 可以是reduce / collect / ...

舉例來說以下五個步驟是可能的Spark處理word count的過程：

1. 創造一個spark context sc
2. 使用此sc從storage讀取data INPUT
3. INPUT 被map成可以處理的單位，可能透過words = INPUT.flatmap { }
4. 把words這個collection去做成kv pair 或是tuple ：pairs = words.mapToPair{ }
5. reduce階段，pairs.reduceByKey{ }

TF-IDF Weight

簡單來說就是要比對documents之間的相似性。

Term Frequency:
利用把documents簡化成某些terms的集合，看這些terms出現在candidates中的頻率，可以做成一個frequency table: (每個entry意思是term在此doc的出現次數）

Inverse Document -Frequency: 
定義DF：是某個term出現在幾個candidate documents中。
則IDF : inverse document frequency，為 N/DF，N是所有candidate documents的數目，這是用來加重少出現但是可能要緊的字。

舉來來說 “the”可能出現在全部N個documents中，所以DF = N，但是其IDF = N/N =1
而"qqq"可能出現在2個documents中，DF = 2，IDF = N/2，所以給予了較高的權重！

研究出來的適合weight:

不過根本課程無關 XDDD，但是跟map-reduce有關。

首先documents可能幾十億個分散在不同storage nodes中，要計算某個term frequency TFij:

有上面input也可以直接算出DF:

Page Rank

簡單來說page B的rank，是所有指向他的page As的contribution：

iteration {

1. contribution(B) = RANK(A) / A網頁發出的links數目
分母的意義是B對A的重要性的權重。

2. RANK(B) = 0.15 + 0.85*contribution(B) //這是經驗公式

}

Spark怎麼實現page rank?
1.

2.

rank的計算就比較straightforward。