分布式系统设计自学整理

厉害了 66666666666666  谢谢楼主总结

amcw7777 发表于 2018-11-10 03:03
我觉得，可以为master 建立一个private database来写入 log，如果shadow有lag的话，可以从log中读取。
...

以我微不足道的经验，private database就管用，master写入log的I/O不会成为一个bottleneck，因为log比actual data小很多，事实上Cassandra的commit log就采用类似的设计。

Cassandra的重点远远不止Consistent hashing, 还有CAP Theorem, Gossip Protocol都是。如果时间紧，至少看下这篇：https://docs.datastax.com/en/cas ... a/dml/dmlIntro.html

wawa哇哇哇哇， 赞赞赞

MapReduce

这里主要描述的是MapReduce 系统的构建，因为我简历里面写了MapReduce，之前在网上也看了挺多比如如何用mapreduce解决排序这样的问题，后来一次面试的时候挂在了讨论如何设计MapReduce系统中的master，然后就意识到了，还是要了解系统构建的，毕竟以后的工作可能是自己给MapReduce写client方或者Server方的API这样的工作，而不是用MapReduce跑数据。

在这之前先看一下我们（或者面试官）可能关注的点：

1.Implement： 如何用多线程和Remote procedure call 来实现功能

2.Performance：如何衡量并提高系统的performance，比如scaling，问题的关键是要找出系统的bottleneck在哪里

3.Fault Tolerance： 如果某个机器挂了怎么办, 如果数据挂了怎么办

4.Consistency：如何保证replica都是一样的，如何保证log和内存和disk是一样的。很难保证100%的consistency，那样performance会很差，但是可以满足weak consistency。

然后来看MapReduce：

MapReduce想要做的事情，就是用distribute的思想来处理大数据，举个例子：

input: 一个文件，100行，文件可以是NoSQL的key-value形式

key  value

a      1

b      2

c      3

a      31

…     …

output：一个按照key排好序的文件

key  value

a     1

a     2

a     31

…    …

如果我的计算机内存只能读取10行，但是有无限个计算机，怎么做？

最简单的distributed思想是，先把文件分成10个，每个文件10行，然后用10个计算机排序（每个计算机时间是O(10log10)）然后输出10个排序好的文件，最后用第11个计算机，来一个10路归并（时间 O(100log(10))），同时输出成最后的output。所以在这个算法里，bottleneck是最后那个10路归并。

MapReduce的处理方法是这样的：

首先分成10个文件，然后输出的不是10个文件，而是260个，比如第一个计算机输出的26个文件是xxx_1_a.txt,xxx_1_b.txt … 分别对应key开头字母为a, b,c ..

最后merge的时候，用26台计算机，比如第一个台专门处理key开头字母为a的那些file：xxx_1_a.txt,xxx_2_a.txt …这样以来bottleneck就被解决了

MapReduce工作流

1.把数据分成M个小文件(每块大概16M-64M),然后把map-reduce的程序copy给workers和 master

2.Master管理workers来执行map，reduce。以map为例子，master有一个map workers pool，还有一个map taskspool，workers pool里找到worker，来执行map task，worker完成任务之后回收到pool里等待被分配下一个task

3.Map worker 收到一个文件还有map function， 开始执行mapfunction，比如sort，然后把结果存在bufferedmemory中，每隔一段时间，再按照reduce的key 分类规则写入到local disk（比如abcd字母开头，这是一种规则）。完成之后，把这些文件的地址返回给master

4.Master确认所有map tasks pool中任务都被执行了之后，建立reducetasks pool，从reduce workers pool中分配机器来完成reduce任务

5.Reduce worker 通过RPC收到file list，还有 reduce function， 根据intermeidatekey排序这些files （外排序），并且写入到最终文件

6.当所有的Reduce tasks被完成之后，Master向user 汇报完成任务

然后我们按照之前说过的点一个一个看：

Implement： MapReduce系统实现

Master:

数据结构：

-Mutex 进程锁

-string workers[]: workers RPC address

-string files[]: input files

-int nReduce: reduce的数量

-int stats[]

functions:

+Register: worker call  register来汇报自己状态，同时存储这个worker到worker pool

+newMaster: initial 一个 master

+killWorker

+run:从worker pool里选择worker来执行task

Worker：

数据结构：

+map

+reduce

-name

-nTasks

-nConcurrent

functions:

+run

+register

+shutdown

Performance：

提高performance最重要的是找到系统的bottleneck，对于mapreduce，bottleneck就是 RPC的网速带宽。intermediatedata是存放在local disk，但是input 和 output是在GFS上进行的。这里的解决办法是，因为GFS上每个file都有3份replica，所以Master会根据3份replica的地址选择map worker，理想情况下，map worker处理的这个input正好在这个disk上，相当于从local读取数据

Faulttolerance：

Master挂了：换个master整个重新做

Worker挂了： master每隔一段时间就ping一下works，如果一段时间没回应就是挂了

Mapworker：可能是replica出了问题，也可能是worker出了问题，所以换一个replica，同时换一个worker重新执行

Reduceworker：如果任务已经finish了，重启就行了；如果任务没有finish，那么把挂掉的worker设置成idle，重新选一个worker执行这个任务

Consistency：

Itis a deterministic system. So the consistency should be good.

如果两个worker同时做一个map，会生成两个file，reduce只读其中一个

如果两个worker同时做一个reduce，在GFS中只会有一个可见

总结：

MapReduce适用于离线大数据分析

不适合iterative任务，因为每次要写入读出到GFS

不适合小数据，以及低延迟的系统

关注关注，希望楼主继续更新

樓主加油！

謝謝樓主總結!

楼主能推荐下分布式系统的好书吗

yiyiyaya 发表于 2018-11-15 02:50
楼主能推荐下分布式系统的好书吗

我学的不是很深入，目前都是看paper和publication，没有看什么教材呢

mapreduce 好像就是看的论文和6.8234的lecture。