Externes Sortieren

Externes Sortieren beschreibt Sortieralgorithmen, welche auf sehr große Datenmengen ausgelegt sind. Algorithmen, die auf großen Datenmengen arbeiten, die nicht in den Hauptspeicher passen, werden allgemein als External-Memory-Algorithmen bezeichnet. In der Analyse klassischer Sortieralgorithmen (z. B. Quicksort) wird meist keine Speicherhierarchie bzw. der Zugriff auf Daten auf unterschiedlich schnellen Datenträgern berücksichtigt. Allerdings ist der Aufbau und die Hierarchie des Speichers sowie der Umgang der Algorithmen mit diesem für die Performance beim Sortieren von großen Datenmengen entscheidend.

Parallel Disk Model

Ein gebräuchliches Modell zur Betrachtung von External Memory Algorithmen ist das Parallel Disk Model (PDM). Dieses verfügt über einen Hauptspeicher der Größe $M$ und einen oder mehreren externen Speicher unbegrenzter Größe, die sogenannten Disks. Auf diesen finden die zu sortierenden Daten der Größe $N$ Platz. Oftmals wird zur Vereinfachung die Anzahl der Disks $D=1$ angenommen und das vereinfachte Modell als External Memory Model (EMM) bezeichnet. Auch Aggarwal und Vitter stellten das Modell ursprünglich mit einer einzelnen Disk, aber mehreren parallelen Schreib-Lese-Köpfen vor. Der Hauptspeicher wie auch der externen Speicher verfügen über eine Blockgröße $B$. Mit einer IO-Operation, kann ein Block pro Disk in den Hauptspeicher geladen oder in den externen Speicher zurückgeschrieben werden. Zur besseren Übersicht werden außerdem die Eingabegröße $n=N/B$ sowie die Größe des Hauptspeichers $m=M/B$ in Blöcken angegeben. Im Gegensatz zur Analyse klassischer Sortieralgorithmen wird die Performance eines Algorithmus nicht an der Anzahl aller Operationen gemessen, sondern nur durch die Anzahl der IO-Operationen angegeben.

Untere Schranke

Für das Sortieren im PDM kann eine allgemeingültige Schranke für die Anzahl der IO-Operationen angegeben werden. Diese ist im Fall einer einzelnen oder mehrerer Disks ($D\geq 1$) gegeben durch:

$\Theta \left({\frac {N}{DB}}\log _{M/B}{\frac {N}{B}}\right)=\Theta \left({\frac {n}{D}}\log _{m}n\right)$

In der Praxis ist $\log _{m}n$ eine kleine Konstante. Für den untypischen Fall $B\log m=o(\log n)$ gilt diese Schranke lediglich für vergleichsbasierte Verfahren.

Algorithmen

Merge Sort

An den klassischen Merge Sort angelehnt ist der External Memory Merge Sort. Zunächst soll der Algorithmus für $D=1$ betrachtet werden. Es werden nacheinander Datensegmente bestehend aus $m$ Blöcken in den Hauptspeicher geladen, dort sortiert und als sogenannter Run zurück in den externen Speicher geschrieben werden. Die $N/M$ Runs im externen Speicher werden anschließend mittels eines K-Way-Merges auf $\log _{m}n$ Rekursionsebenen zusammengefasst.

Vereinfachte Darstellung des Merge Sorts. Zuerst werden die einzelnen Runs im Hauptspeicher sortiert, anschließend werden die Runs gemerged.

 for j=1 to n/M
     Lade nächstes Datensegment der Größe $M$ in Hauptspeicher
     Sortiere Daten im Hauptspeicher
     Schreibe sortierte Daten als run $r_{1,j}$ auf externen Speicher
 end

 for i=1 to $\lceil \log _{m}n\rceil$
     for j=1 to $\lceil |r_{i}|/(m)\rceil$
         Lade die jeweils ersten Blöcke der runs $r_{i,(j-1)(m)+1}...r_{i,j(m)}$ in Merge-Buffer
         while Merge-Buffer nicht leer
             Merge runs $r_{i,(j-1)(m)+1}...r_{i,j(m)}$
             Schreibe Output-Buffer in externen Speicher falls voll
             Lade nächsten Block in Hauptspeicher falls ein Merge-Buffer bereits komplett gemerged
         end
     end
 end

Um mehrere parallele Disks möglichst effizient zu nutzen und die oben beschriebene Schranke einzuhalten, müssen in jedem IO-Schritt möglichst $D$ Blöcke bewegt werden. Zum effizienten Schreiben der Blöcke zurück auf die Disks wird daher die Größe des internen Buffers im Hauptspeicher, der die gemergten Elemente enthält, auf $D$ Blöcke erweitert. Um auch beim Lesen einen höheren Durchsatz zu gewährleisten, wird außerdem ein Prefetching-Buffer hinzugefügt. Wurden die Elemente in den vorherigen Schritten geschickt auf den einzelnen Disks verteilt und eine geeignete Prefetching-Strategie gewählt, genügt eine Buffergröße von $\Theta (D)$ Blöcken.

Distribution Sort

Analog zum Merge Sort ist auch der Distribution Sort ein rekursiver Algorithmus. Die Daten sollen nach $S-1$ Partitionierungs­elementen in $S$ Buckets eingeteilt werden. Dabei gilt, dass alle Elemente innerhalb eines Buckets kleiner sind als jedes Element im darauf Folgenden. Diese Partitionierung wird dann rekursiv für die einzelnen Buckets wiederholt. Sind die Buckets klein genug um jeweils komplett in den Hauptspeicher geladen werden zu können, werden sie dort sortiert. Die Konkatenation der sortierten Buckets bildet somit die sortierte Reihenfolge der gesamten Daten.

Die Wahl der Partitionierungselemente ist entscheidend um möglichst gleich große Buckets zu erhalten und somit eine gute Performance zu gewährleisten. Dies kann beispielsweise auf probabilistische Art und Weise erfolgen. Eine kleine, zufällige Menge an Elementen wird sortiert und die Partitionierungs­elemente aus dieser ausgewählt. Die Größe der Menge wird so gewählt, dass die Sortierung dieser für die Anzahl an IO-Operationen vernachlässigbar ist und keinen Einfluss auf die Schranke hat. Bei guter Partitionierung beträgt die Rekursionstiefe $O(\log _{S}n)$. Da für jedes Bucket ein Buffer im Hauptspeicher benötigt wird, kann $S$ durch $\Theta (m)$ nach oben abgeschätzt werden.

Um die oben gegebene Schranke zu erfüllen, dürfen somit auf jeder Rekursionsebene lediglich $\Theta (n/D)$ IO-Operationen ausgeführt werden. Um ein Bucket effizient in den Hauptspeicher zu laden, müssen dessen Blöcke zuvor gleichmäßig auf die verschiedenen Disks verteilt worden sein. Die zu den verschiedenen Buckets gehörenden Blöcke werden entweder gemeinsam als ein Stripe aus dem Output-Buffer im Hauptspeicher auf den externen Speicher geschrieben oder es wird ein Stripe pro Bucket erstellt. Im Falle eines Stripes pro Bucket kann mit Hilfe von Randomized Cycling dafür gesorgt werden, dass die nächsten Blöcke der verschiedenen Buckets auf möglichst unterschiedliche Disks geschrieben werden müssen. Diese Variante wird auch Randomized Cycling Distribution Sort genannt.

Anwendungen

Grundsätzlich nehmen Operationen zur Sortierung einen großen Teil des Rechenaufwands ein. In den letzten Jahren sind die Datenmengen, auf denen gerechnet wird, stetig größer geworden. Zur Bewältigung dieser Datenmengen sind External-Memory-Algorithmen nötig. Effizientes Externes Sortieren hat dabei eine besondere Bedeutung, da viele External-Memory-Algorithmen auf Sortierverfahren beruhen.