分散式排序算法是指在p台已經斌於序號的計算機C1，C2，……，Cp上，對一組給定的數據分布X={X1，X2，……，Xp}進行全局排序，得到一個新的數據分布Y={Y1，Y2，……，Yp}，使得每個Yi(1≤i≤p)有序，並且Yi的每個元素不大於Yj的任何元素，i≤j。
基本介紹
- 中文名：分散式排序算法
定義,分類,單節點排序（SNS）,多節點歸併排序（MNMS）,多節點分區排序（MPS）,算法性能影響因素,並行程度,待排序數據集的分布,副本使用,數據分片大小,硬體配置,
定義
分散式排序是指，在p台已經斌於序號的計算機C1，C2，……，Cp上，對一組給定的數據分布X={X1，X2，……，Xp}進行全局排序，得到一個新的數據分布Y={Y1，Y2，……，Yp}，使得每個Yi(1≤i≤p)有序，並且Yi的每個元素不大於Yj的任何元素，i≤j。分散式排序必須完成的最小工作是：
- 數據傳輸：把一些效據從它們所在的機器送到它們應放的機器；
- 局部排序；
- 預處理，以便能正確地把數據重新分布。
因此，很據L吐分類，一個分散式排序算法有四類操作：
- 局部排序；
- 合併；
- 預處理；
- 數據交換。
分類
單節點排序（SNS）
假設數據存儲在多個節點中，但是負責計算的節點之間沒有並行計算的能力，只有當前被連線的節點能夠提供計算並對對客戶端提供服務．在這樣的場景下對進行數據排序，流程的主要是，各節點將數據讀入記憶體，並通過網路傳輸至排序的節點，在該節點上進行排序。
多節點歸併排序（MNMS）
當存儲數據的節點同時也擁有計算能力的時候，可以採用算法是：各節點先對存儲在本地的數據進行排序，待所有的存儲節點都對本地的數據排好序之後，再傳送至某一個處理節點進行歸併排序。
多節點分區排序（MPS）
當節點具有並行計算能力，可採用如的算法：將數據按照一定的範圍進行劃分，每個節點處理一定範圍內的數據，當節點獲取到屬於該範圍的所有數據後，對數據進行排序操作。
算法性能影響因素
在分散式系統中，排序算法效率不僅僅取決於記憶體排序算法的實現，系統中其他因素對排序算法的效率也起著至關重要的作用。
並行程度
這裡的並行程度主要指兩個方面：一方面是計算節點是否需要從存儲節點獲取到所有的數據分片才可以開始進行排序操作；另一方面是是否可以有多個計算節點協同進行排序操作．當節點需要獲取到所有的數據分片才可以進行計算時，往往會伴隨大量的網路等待時間，這樣顯然會降低排序的性能．而多個節點的協同計算往往需要有一個主控節點來負責整體的調度，可能會出現負載不均等問題。
待排序數據集的分布
當需要多個節點共同完成本次排序操作時，往往需要對數據按照一定的規則來重新劃分．如果事先無法知曉待排序數據分布，一般需要通過採樣來獲取數據的分布，並以此作為劃分任務的依據．劃分策略是否能均勻劃分數據對排序效率的影響主要體現在兩個方面：首先，合理的劃分可以使得各個節點之間的運算負載大致相同，不會出現大量數據被分配至同一節點，使得少數節點負載過高的情況；其次，可以通過改變數據劃分的策略來減少數據在節點間的傳輸量，從而起到提升效率的作用．如果在排序之前就已經知曉待排序的數據範圍，以及待排序數據的分布，那么就可以對數據進行更加合理的劃分以提升排序的效率。
副本使用
如前所述，分散式系統常常通過冗餘存儲數據分片的方式來保證系統的可靠性．在多個節點參與運算的情況下，計算的過程中可以讀取數據分片副本的形式來減少網路的傳輸，以此來最佳化排序的性能．考慮如下場景，數據分片木的主副本存儲在節點中的第二副本存儲在節點中．當節點AT2計算需要使用到數據分片也時，如果不能使用副本，則需要到節點中獲取數據分片但是如果可以使用副本，則僅需要在本地讀取數據分片4的副本即可．通過這樣的方式來減少網路間的傳輸，以此來提升效率。
數據分片大小
在分散式場景下，如果設定較大的數據分片大小，那么在讀取數據時，以最小化磁碟尋道時間的代價，來提升系統的性能．同時數據在網路中傳輸時，能夠最小化網路建立連線的代價，幫助進一步提升系統性能．但是如果數據分片的大小設定得過大，又會導致單個子任務需要處理的任務過多，進而降低系統的性能。
硬體配置
硬體配置主要分為節點間的網路配置和節點內的硬體配置．節點間的網路配置方面，如今，機房普遍能夠配置千兆交換機，且PC（Personal Computer，個人計算機）也能夠配置千兆網卡．在千兆網的環境下，極限頻寬為125M/s．當網路傳輸速度成為瓶頸時，可以使用更高性能的硬體來提升性能，如萬兆網、InfiniBand等．節點內的硬體配置主要指的是節點計算機的體系結構，例如CPU（Central Processing Unit，中央處理器）架構中使用CMP（Chip Multiprocessor 單片多核架構）、SMP（Symmetrical Multi-Processing，對稱多處理架構）等，通過執行緒的並行，使得同一時間內，節點能夠進行更多的運算．此外還有SSD（Solid State Drives，固態硬碟）等的套用，由於沒有了傳統磁碟尋道時間的消耗，可以大大提升系統隨機讀寫的性能。
