大规模数据处理-MapReduce

MPI

MPI编程:n台机器编号,0~n-1

  • send(from. to, msg, sizeof(msg))
  • recv()
  • brodcast(from, Group, O o),
  • gather(Group, to)

没有出错处理

MapReduce

1
2
3
map (in_key, in_value) -> (out_key, intermediate_value) list

reduce (out_key, intermediate_value list) -> out_value list

MAP -》 Shuffle

YARN:

  • ResourceManager: 监控作用,仅一个
  • AppManager: 调度器
  • APPMaster
  • work:

作业

  1. Distribute sort
  2. MxM
  3. 期末考试题目

Key,Value Store

put(key, value)

get(key)

query(key_start, key_stop)

数据结构:

  • Hash
  • Array
  • 平衡树
  • B树
  • B+树

磁盘:

  • log

get操作: 加载到内存,

log+hash,sort,B+ flush 得到index

LSM tree

单机 (key,value) store

分布式环境的(key, value) store

K -> node -> 本机(key,value)

  • hash(key) % N => node
    • load banlance?
    • scability
    • 容错

DHT

distribute hash

K-means算法

选择k个初始点作为k个set的中心,对数据集中的每条数据计算其最近的set, 然后计算每个set的中心,进而计算新的k个set, 重复此算法

但是这太复杂了,因此我们采用canopy算法。首先建立一系列重叠canopy,使得所有数据至少在一个canopy中,然后仿照k-means算法,不需要比较所有数据点,只需要比较其所在canopy的中心点即可。

打赏