大数据存储与理-第二讲.ppt

Google三大法宝之一：MapReduce 矩阵乘法串行实现 1: for i=1;i=N;i++ 2: for j=1;j=N;j++ 3: 4: 5: 6: for k=1;k=N;k++ C[i][j] += A[i][k]*B[k][j] end for end for 7: end for ? 算法复杂度：O(N3) ? 以1次乘法需要1个时钟周期，计算10亿维度矩阵为 例，使用1G的CPU，需要的计算时间为： t = 10亿×10亿×10亿 / 10亿 = 317年！ 是否OK？ 想办法解决大规模矩阵相乘问题：我拆 ? Cm = Am ⅹ B ? M台服务器并行计算，时间降低为1/M C A B C1 Cm CM A1 Am AM = ⅹ 想办法解决大规模矩阵相乘问题：我再拆 ? Cm,n = Am ⅹ Bn ? M ⅹM台服务器并行计算，时间降低为1/M2 C A B A1 Am AM = ⅹ C1,1 Cm,1 CM,1 B1 Bn BM 子任务 子任务 子任务 … 拆的本质－ 分而治之 ? 分而治之 – Divide and Conquer – 一个大的计算任务分解为若干小计算任务 – 子任务计算结果合并后获得最终结果 计算任务 Divide Conquer 计算结果 MapReduce的来源 ? 编程模型： – 1956年John McCarthy（图灵奖获得者）提出的Lisp语言中的 Map/Reduce方法 – Map输入是一个函数和n个列表，输出是一个新的列表，列表中的元素是 将输入函数作用在n个输入列表中每个对应元素获得的计算结果。 – Reduce输入是一个函数和一个列表，输出是将函数依次作用于列表的每 个元素后获得的计算结果 (map vector #* #(1 2 3 4 5) #(5 4 3 2 1) - #(5 8 9 8 5) (reduce #+ #(5 8 9 8 5)) - 35 Lisp中的Map和Reduce操作 MapReduce原理 Source：sun.fim.uni-passau.de/cl/MapReduceFoundation/ MapReduce机制 ? 主控程序（Master）：将Map和Reduce分配到合适的工作机上 ? 工作机（Worker）：执行Map或Reduce任务 MapReduce不仅仅是编程模型! ? 让程序员在使用MapReduce时面对以下细节问题？ – 大数据如何分割为小数据块？ – 如何调度计算任务并分配和调度map和reduce任务节点？ – 如何在任务节点间交换数据？ – 如何同步任务？ – 相互依赖的任务是否执行完成？ – 任务节点失效时该如何处理？ ? Google的MapReduce是一个完整的计算框架 – 程序员只需要编写少量的程序实现应用层逻辑 程序示例：WordCount #include mapreduce/mapreduce.h class WordCounter : public Mapper { public: virtual void Map(const MapInput input) { const string text = input.value(); const int n = text.size(); for (int i = 0; i n; ) { while ((i n) isspace(text[i])) i++; int start = i; while ((i n) !isspace(text[i])) i++; if (start i) Emit(text.substr(start,i-start),1); }}}; REGISTER_MAPPER(WordCounter); class Adder : public Reducer { virtual void Reduce(ReduceInput* input) { int64 value = 0; while (!input-done()) { value += StringToInt(input-value()); input-NextValue(); } Emit(IntToString(value)); }}; REGISTER_REDUCER(Adder); int main(int argc, char