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

栏目: 数据库 · 发布时间: 5年前

内容简介:第一周是给定了函数签名实现多路归并排序。为啥要考这个问题呢?个人认为多路归并在分布式数据库、分布式搜索引擎领域是挺常见的算法。用我相对熟悉的 es 来举例,在搜索数据时,我们会指定 bool 表达式来对数据进行筛选,同时需要指定每个查询 sort by 字段以及 size,但分布式环境下,我们没有办法确定这 size 个元素要在每个 shard 里取几个元素。所以最基本的思路:参考上面的三条,先做局部排序,再做全局归并,思路也不难,先把大 slice 区分成 N 个 slice,然后对每个 slice 进行

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

为啥要考这个问题呢?个人认为多路归并在分布式数据库、分布式搜索引擎领域是挺常见的算法。用我相对熟悉的 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

以上所述就是小编给大家介绍的《talent-plan tidb 部分个人题解-week 1》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Ruby Cookbook

Ruby Cookbook

Lucas Carlson、Leonard Richardson / O'Reilly Media / 2006-7-29 / USD 49.99

Do you want to push Ruby to its limits? The "Ruby Cookbook" is the most comprehensive problem-solving guide to today's hottest programming language. It gives you hundreds of solutions to real-world pr......一起来看看 《Ruby Cookbook》 这本书的介绍吧!

JSON 在线解析
JSON 在线解析

在线 JSON 格式化工具

SHA 加密
SHA 加密

SHA 加密工具

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具