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

第一周是给定了函数签名实现多路归并排序。这里

为啥要考这个问题呢?个人认为多路归并在分布式数据库、分布式搜索引擎领域是挺常见的算法。用我相对熟悉的 es 来举例,在搜索数据时,我们会指定 bool 表达式来对数据进行筛选,同时需要指定每个查询 sort by 字段以及 size,但分布式环境下,我们没有办法确定这 size 个元素要在每个 shard 里取几个元素。所以最基本的思路:

  1. 每个 shard 里都取出 size 个元素
  2. 拉到中心节点来进行多路归并,输出前 size 个元素
  3. 每个 shard 返回的 size 条数据可以预先排序好。

参考上面的三条,先做局部排序,再做全局归并,思路也不难,先把大 slice 区分成 N 个 slice,然后对每个 slice 进行排序,这个过程用 N 个 g 并发进行。然后建立一个小顶堆,比较依据为每个 slice 的头部元素。

建立好堆之后,每次从堆顶取元素,将堆顶 slice 的 idx++,如果已经取完了该 slice 的元素,则对堆进行 pop。如果没取完,则需要对小顶堆进行再平衡。

基本思路就是这样,剩下的就是各种调试了。。。

我的代码在:这里

有时间应该对 style 进行一些优化。

这里比较麻烦的是,对任务进行切分,并且对局部数组并发排序时,这个拷贝操作怎么都避免不了,否则因为 cpu 的多级 cache 机制导致整体的数组数组被排乱掉。其实就是有 race。

相比标准的 sort.Slice 原地排序,有大量的内存拷贝操作。。没想到有什么好办的优化方法。

~/t/t/mergesort ❯❯❯ make bench                                       master ✱ ◼
go test -bench Benchmark -run xx -count 5 -benchmem
goos: darwin
goarch: amd64
pkg: pingcap/talentplan/tidb/mergesort
BenchmarkMergeSort-8    	       1	1039028165 ns/op	134228352 B/op	      57 allocs/op
BenchmarkMergeSort-8    	       1	1065523444 ns/op	134222144 B/op	      43 allocs/op
BenchmarkMergeSort-8    	       1	1064337935 ns/op	134222688 B/op	      44 allocs/op
BenchmarkMergeSort-8    	       1	1051075587 ns/op	134221984 B/op	      41 allocs/op
BenchmarkMergeSort-8    	       1	1047990178 ns/op	134221888 B/op	      40 allocs/op
BenchmarkNormalSort-8   	       1	3277904168 ns/op	      64 B/op	       2 allocs/op
BenchmarkNormalSort-8   	       1	3256987462 ns/op	      64 B/op	       2 allocs/op
BenchmarkNormalSort-8   	       1	3259074652 ns/op	      64 B/op	       2 allocs/op
BenchmarkNormalSort-8   	       1	3327195388 ns/op	      64 B/op	       2 allocs/op
BenchmarkNormalSort-8   	       1	3356915213 ns/op	      64 B/op	       2 allocs/op
PASS
ok  	pingcap/talentplan/tidb/mergesort	25.773s