分布式归并排序的实现

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了分布式归并排序的实现，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2418字，纯文字阅读大概需要4分钟。

内容图文

语言工具：golang
基本思路：
1.通过协程模仿多个机器节点。每一个协程代表一个机子。
2.每台机器对自己内存中的数据进行排序，此处用的库函数

nums []int
sort.Ints(nums)

3.每个机器都将排好序的数据发送到channel中，在此期间是利用开启协程来实现每个节点并行执行。
4.多个channel产物，产物里保存着各个节点排好序的数据，服务器保存节点IP地址和端口号，并并行的接收每个服务器传入channel中的数据。
5.并行进行对N个channel中的数据的归并排序，并边归并边返回归并有序的数据的channel。
比如说这里有四个节点将自己机器内的数据排好序，master节点读取数据时利用归并的思想，先将N个channel分离成一个个单独的channel，然后实现Merge，Merge中是用开启协程的方式并发的进行归并。
实现方式：

//放入内存并排序，然后发送到out管道中给别的goroutine
func InMemSort(in <-chan int)<-chan int{
	out := make(chan int,1024)
	go func(){
		//read in memory
		a := make([]int,0)
		for v := range in{
			a = append(a,v)
		}
		fmt.Println("read done used",time.Now().Sub(StartTime))
		//sort memory
		sort.Ints(a)
		fmt.Println("sort done used",time.Now().Sub(StartTime))
		//发送到管道
		for _,v := range a{
			out <- v
		}
		close(out)
	}()
	return out
}

//两个节点的输入进行归并，得到结果输出
func Merge(in1,in2 <-chan int)<-chan int{
	out := make(chan int,1024)
	go func() {
		num1,ok1 := <-in1
		num2,ok2 := <-in2

		for ok1 && ok2{
			if num1 > num2{
				out <- num2
				num2,ok2 = <-in2
			}else{
				out <- num1
				num1,ok1 = <-in1
			}
		}
		//有一个结束
		for ok1 {
			out <- num1
			num1,ok1 = <-in1
		}
		for ok2 {
			out <- num2
			num1,ok2 = <-in2
		}
		close(out)
		fmt.Println("merge done used",time.Now().Sub(StartTime))
	}()
	return out
}

//MergeN
func MergeN(in []<-chan int)<-chan int{
	if len(in) ==1{
		return in[0]
	}
	mid := len(in)/2
	left := MergeN(in[:mid])
	right := MergeN(in[mid:])
	out := Merge(left,right)
	return out
}

6.master节点将得到的channel中的数据写入到本地文件中。由于并行发送和接收的原因，很大几率master当前读取的数据量较小，写入文件时较少的占用了内存空间。

性能分析
相对于单机排序：

• 将负载分发到多个节点中，主节点只负责对多个节点发来的数据进行归并和写入文件。单机模式下，首先需要读取整个文件的数据然后进行归并排序，可能800M，内存够用，那800G呢？总结：省CPU资源（排序）和内存资源（数据存入内存）；另一种单机解决方案：模拟分布式，文件中的数据用多个协程进行读取，每个协程读取完毕之后交给CPU执行InmemerySort()对数据进行排序后发送到新的输出管道。
• 单机排序不开启协程不会用到多核优势；另一种单机解决方案：可以利用到多核优势。
• 分布式情况下，如果机器非常多，归并的时候master会启动多个协程，此时多协程抢占CPU资源的问题就会加重，可能导致相对于单机来说一部分资源的消耗；另一种单机解决方案：也会造成抢占CPU。

内容总结

以上是互联网集市为您收集整理的分布式归并排序的实现全部内容，希望文章能够帮你解决分布式归并排序的实现所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---