《软件工程》社会实践
分布式系统中排序算法以及应用案例设计报告
学号：  2014107326            姓名：侯明兰
一. 算法需求分析
1. 分布式排序算法的排序过程为：在p台已经赋予序号的计算机C1，C2，……，Cp上，对一组给定的数据分布X={X1，X2，……，Xp}进行全局排序，得到一个新的数据分布Y={Y1，Y2，……，Yp}，使得每个Yi(1≤i≤p)有序，并且Yi的每个元素不大于Yj的任何元素，i≤j。分布式排序必须完成的最小工作是：
1.1 数据传输：把一些效据从它们所在的机器送到它们应放的机器；
1.2 局部排序；
1.3 预处理，以便能正确地把数据重新分布。
因此，根据预处理分类，一个分布式系统中的排序算法有四类操作：
1.3.1 局部排序；
1..3.2 合并；
1.3.3 预处理；
1.3.4 数据交换。
2.算法的分类：根据算法的分析可以分为：单节点排序（序(Single Node Sort，SNS）、多节点归并排序（(Multiple Node Merge Sort，MNMS）和多节点分区排序（(Multiple Partition Sort，MPS）。
2.1 单节点排序（SNS）：假设数据存储在多个节点中，但是负责计算的节点之间没有并行计算的能力，只有当前被连接的节点能够提供计算并对对客户端提供服务．在这样的场景下对进行数据排序，流程的主要是，各节点将数据读入内存，并通过网络传输至排序的节点，在该节点上进行排序。
2.2 多节点归并排序：当存储数据的节点同时也拥有计算能力的时候，可以采用算法是：各
节点先对存储在本地的数据进行排序，待所有的存储节点都对本地的数据排好序之后，再传送至某一个处理节点进行归并排序。
2.3 多节点分区排序：当节点具有并行计算能力，可采用如的算法：将数据按照一定的范围进行划分，每个节点处理一定范围内的数据，当节点获取到属于该范围的所有数据后，对数据进行排序操作。
二. 分布式系统
1. 分布式系统功能作用
分布式系统（distributed system）是建立在网络之上的软件系统。正是因为软件的特性，所以分布式系统具有高度的内聚性和透明性。因此，网络和分布式系统之间的区别更多的在于高层软件（特别是操作系统），而不是硬件。内聚性是指每一个数据库分布节点高度自治，有本地的数据库管理系统。透明性是指每一个数据库分布节点对用户的应用来说都是透明的，看不出是本地还是远程。在分布式数据库系统中，用户感觉不到数据是分布的，即用户不须知道关系是否分割、有无副本、数据存于哪个站点以及事务在哪个站点上执行等。
 
2. 分布式系统在计算机中的应用过程
在一个分布式系统中，一组独立的计算机展现给用户的是一个统一的整体，就好像是一个系统似的。系统拥有多种通用的物理和逻辑资源，可以动态的分配任务，分散的物理和逻辑资源通过计算机网络实现信息交换。系统中存在一个以全局的方式管理计算机资源的分布式操作系统。通常，对用户来说，分布式系统只有一个模型或范型。在操作系统之上有一层软件中间件（middleware）负责实现这个模型。一个著名的分布式系统的例子是万维网（World Wide Web），在万维网中，所有的一切看起来就好像是一个文档（Web页面）一样。
在计算机网络中，这种统一性、模型以及其中的软件都不存在。用户看到的是实际的机器，计算机网络并没有使这些机器看起来是统一的。如果这些机器有不同的硬件或者不同的操作系统，那么，这些差异对于用户来说都是完全可见的。如果一个用户希望在一台远程机器上运行一个程序，那么，他必须登陆到远程机器上，然后在那台机器上运行该程序。
分布式系统和计算机网络系统的共同点是：多数分布式系统是建立在计算机网络之上的，所以分布式系统与计算机网络在物理结构上是基本相同的。
他们的区别在于：分布式操作系统的设计思想和网络操作系统是不同的，这决定了他们在结构、工作方式和功能上也不同。网络操作系统要求网络用户在使用网络资源时首先必须了解网络资源，网络用户必须知道网络中各个计算机的功能与配置、软件资源、网络文件结构等情况，在网络中如果用户要读一个共享文件时，用户必须知道这个文件放在哪一台计算机的哪一个目录下；分布式操作系统是以全局方式管理系统资源的，它可以为用户任意调度网络资源，并且调度过程是“透明”的。当用户提交一个作业时，分布式操作系统能够根据需要在系统中选择最合适的处理器，将用户的作业提交到该处理程序，在处理器完成作业后，将结果传给用户。在这个过程中，用户并不会意识到有多个处理器的存在，这个系统就像是一个处理器一样。
三. 分布式系统中排序算法的应用案例
1. 采用Map／Reduce计算模型应用案例
排序是计算机科学中的基础问题，传统的排序算法研究多关注于集中式环境下算法的性能、资源消耗和稳定性近年来，在很多领域中数据的规模快速增长，已经很难在集中式环境 中进行存储和处理，Hadoop等分布式系统逐渐成为大规模数据处理的主流平台。在分布式环境
中对大规模数据进行排序处理时，不仅需要考虑单节点上排序算法的选择，还需要考虑分布式系统的架构 、数据分布策略和分布式计算模型等因素的影响。在分布式系统中如何提高大规模数据排序处理的性能是一个值得研究的问题。本文关注于分布 式系统 中大规模 数据排序 算法 生活中数据库系统的实际例子的性 能分析 问题，提出了单节点排序(Single Node Sort，SNS)、多节点归并排序(Multiple Node Merge Sort，MNMS)和多节点分区排(Multiple Partition Sort，MPS)3种排序算法。针对每种算法策略，将算法的执行过程细分为磁盘 I／0(Input／0utput，I／O)、网络I／0和排序计算等多个阶段，给出了算法的代价模型，并讨论了数据分布和数据分片大小等 因素对算法 的影响。在实验分析中，我们采用Map／Reduce计算模型分别实现了 3种排序算法，并在 Sorting Benchmark的数据集上验证 了分析的正确性。
2. 实验分析
为了验证分析结论的正确性，我到一个实验案例：通过搭建7个节点的 Hadoop集，节点间通过千兆以太网连接。每个节点的配置为2颗Intel(R)XeonE5—2650CPU、128G内存和SSD存储，软件环境包括 RedHatEnterpriseLinuxServerrelease6．2、Hadoop2．7．2和 JDK 1．7．0—79。实验中使用的数据集由 Sort Benchmark的数据生成器gensort产生，数
据集模分为20GB、40GB和80GB 3种 。实验分为3组：第一组用于对比3种排序算法对不同模数据集的排序性能；第二组测试数据分片大小对排序性能的影响；最后一组实验用于分析影响分布式分区算法性能的因素。在实验通过使用监控工具nmonforLinux来获取排序算法执行过程中各节点的资源使用情况。
3.3组实验性能比较
在排序算法中，由于SNS和MPS最终的排序 只 由一个节点处理，处理节点伴随着大量的网络 i／o，同时计算节点还需要对大量数据进行处所以排序的运行时间要长于分布式分区算法。所以数据量为相同时，运行时间的大小顺序为：单节点排序算法（SNS）、多节点归并排序算法（MNMS）、多节点分区算法（MPS）。在各数据量上，分布式分区算法的运行时间均要小于SNS与MNMS。
由于在 SNS以及 MNMS的模拟实现中，计算节点上也存储着待排序的数据 ，因此其资源 监控图中计算节点也含有数据节点的代价。由实验中得到，无论是 SNS还是 MNMS，它们最终都是在某一个节点上完成所有的排序操作，因此这个节点在总的排序操作开始时，有大量的网络传输来获得待排序数据，以及大量的磁盘 I／O来完成排序后的数据写入操作。而对于
MPS来说，前期由于需要进行采样操作；所以伴随着少量的磁盘I／O，之后无论是磁盘还 是网络的压力，MPS均小于其他两种算法。
4. 数据片大小的影响
在排序数据量为相同场景下 ，数据分片大小分别为64M、128M、256M 时，执行不同排序算法需要的时间，由于实验中集采用SSD硬盘配置，没有硬盘的寻道时间，所以3种排序算法在不同数据分片大小的场景下变化不大。SNS由于主要代价在最终节点的排序上，增大了数据分片的大小，使得网络上有了些许提升，因此在算法运行时间上有所减少。 分布式 归并排序虽然在网络上也得到了优化，但是每个数据分片本地排序的时间也有稍许提升，因此总体没有太大变化。分布式分区排序由于本地需要处理的数据量增多，所以运行时间上有一定的增加。
5. 分布式分区排序算法分析
在实验中使用了随机数据 、正态分布数据 ，以及执行排序操作前就已经是有序的有序数据这3种不同的数据分布 ，测试采样策略为随机采样、头部采样以及等间隔采样3种不同的采
样策略。在实验中，采样效率上由于随机采样需要扫描更多的数据，所以效率最低，头部采样的效率最高。如果待排序数据原本已经是有序的，由于排序计算时间的减少，排序算法的运行时间要少于其他情况。同时在数据有序的场景下，等间隔采样能在较少的时间内对数据进行均匀的划分。
四．心得体会及建议
根据本文中分布式系统中排序算法以及应用案例的算法分析，系统的具体了解和说明，以及举例说明应用范围和案例的实验说明。描述了在分布式场景下3种不同的排序算法，描述了它们与传统的单节点内存排序算法的不同之处，分析了排序算法不同阶段的代价，并结合分布式场景的特点讨论了数据分片大小 、数据 副本 、数据分布等问题对不同算法的影响。通过实验对比验证了分析的正确性。在分布式场景下，为了能够更快地对数据进行处理需要充分考虑系统架构特点、系统参数设置 、各节点的硬件水平等诸多因素，综合评选，选择最适合的排序算法应用于分布式系统中。