talent-plan tidb 部分个人题解-week 2

Week 2 的问题是 map reduce 优化,说实话,这周的示例代码写的不怎么样,不知道为什么都是同一个人的代码,同一个参数的名字还换来换去,读起来会浪费一些时间。一些缩写也让人比较困惑,比如 fs,bs,别人要稍微思考一下才能看懂这是什么东西,用 fileList 或者 bufferList 显然更好啊,可能样例代码的人是写 acm 出身,比较喜欢赶时间。虽然 Go 的 runtime 代码里也经常这么干,汗。

吐槽就到这里。题目是想让你先把 example 补全,能运行,然后再去实现自己的 map reduce 方法。要补两个地方,第一个是 run 函数里的 reduce phase,另一个是 worker 函数的 reduce phase 的具体实现工作。这里提示比较少,不过看着函数名和代码上下文花半个小时可能就猜出来怎么做了,嗯。

run 里的 reduce phase 组装一下参数,并且和上面 map phase 差不多,拼出相应的 task 结构,然后提交任务给worker 就行:

	// reduce phase
	startTime := time.Now()
	tasks = make([]*task, 0, nReduce)
	for i := 0; i < nReduce; i++ {
		t := &task{
			dataDir:    dataDir,
			jobName:    jobName,
			phase:      reducePhase,
			taskNumber: i,
			nReduce:    nReduce,
			nMap:       nMap,
			reduceF:    reduceF,
		}
		t.wg.Add(1)
		tasks = append(tasks, t)
		go func() { c.taskCh <- t }()
	}
    
	// 任务收集阶段,需要把最终 merge 到的 filename 传出
	// 这里稍微有一些疑惑
	notifyList := []string{}
	for _, t := range tasks {
		t.wg.Wait()
		mergefileName := mergeName(t.dataDir, t.jobName, t.taskNumber)
		notifyList = append(notifyList, mergefileName)
	}
	du := time.Now().Sub(startTime)
	fmt.Println("reduce time: ", du)

	notify <- notifyList

这个 notifyList 的操作真是猜的,没有任何描述,外部的 example test 写的也比较奇怪,inputfiles 鬼知道在说什么啊。

然后是 worker 里的代码就参考这个 commit 吧。

补完 example,跑 test 直接超过了 10min,test 被 kill 掉了。。汗,感觉出题人这里还是出的有点问题,example 阶段本意是随便补补,能跑通就算过的。现在在稍微挫一点的电脑上,这个 test 10 分钟根本跑不完。在自己家牛逼的 2018 mbp 上试了一下 4 分钟就跑完了。出题人的电脑果然是好电脑,嗯。

原本 map reduce 两个阶段采用的序列化是标准库中的 encoding/json,用火焰图看 cpuprofile 可以看到基本 40+ 都在 json.Marshal,json.Unmarshal。在不修改序列化方式的前提下,最简单的优化就是换个库,用我们陶师傅写的 jsoniter。

跑跑 benchmark,嗯,快了几分钟。但是 cpu 消耗的大头还是在 json 编码解码上,用最粗暴的简单字符串连接,可以尝试一下这里的性能优化极限,基本可以把原来的整体时间缩短一半。仔细想想 apache 生态下那些大数据计算框架,基本都有特殊的协议(avro、pb 什么的)对数据进行压缩,所以用 json 之类的会慢倒也不奇怪了。到达优化极限之后,比较突出的问题就是 runtime.slicebytetoarray 之类的问题了,这明显是因为 map reduce 框架和 mapF 以及 reduceF 的函数签名中数据类型不匹配导致数据总是要从 string 转成 []byte,从 []byte 转成string 而带来的问题,优化也比较简单,能用 []byte 的地方全用 []byte 就行了,减少数据类型转换。

题目还要求对 mapF 和 reduceF 的实现进行优化,round1 其实没什么好优化的,题目里提到 case 的数据本身可能有倾斜,但实际经过实验,在 round1 加入 map 输出 url 和统计数,确实对数据倾斜有极大的优化,但因为 map 的问题,在倾斜不严重的数据集上跑反而更慢了。汗。所以还是要稍微权衡一下。round2 的运行时间本来也不太长,可以在 map 阶段直接对每个 map 任务提前求 top 10,这样 reduce 阶段需要进行的任务就轻了很多,实际优化效果很好,能把 reduce 从几百毫秒优化到几 ms 甚至几十 us,但没啥用,round2 的 reduce 阶段在全局时间中的占比非常少。

这周的 homework 做完还是有点虚的。。可能是需要做之前先看看 map reduce 的论文,就不会在理解这个框架上有磕绊了?大概吧。

talent-plan tidb 部分个人题解-week 2
Share this

家境贫寒,整理不易,客官如果觉得不错欢迎打赏!我的微信 xargin_buaa,如果想交流也欢迎来加~