17 Datenverteilung in Parallelen DBS

17.3 Allokation

Aufgabe der Allokation ist die Zuordnung der Fragmente zu Partitionen und Rechnern. Diese Aufgabe ist nun einfacher lösbar als bei Verteilten DBS, wo aufgrund großer Entfernungen zwischen den Knoten die Unterstützung einer hohen Lokalität ein Hauptziel war. Dazu war es vor allem erforderlich, die Datenzuordnung auf die an den verschiedenen Knoten gestarteten Transaktionstypen abzustimmen (Kap. 5.7). In lokal verteilten Shared-Nothing-DBS können dagegen eintreffende Transaktionen und Anfragen mit gleichem Aufwand an jedem der Rechner gestartet werden. Als Hauptziele sind neben der Begrenzung des Kommunikationsaufwandes vor allem Intra-Transaktionparallelität sowie Lastbalancierung zu unterstützen. Bei der Festlegung des Verteilgrades sowie der Fragmentierung wurde diesen Faktoren bereits Rechnung getragen, wobei jedoch vor allem eine Minimierung von Antwortzeiten angestrebt wurde. Bei der Allokation soll nun die Lastbalancierung unterstützt werden, um ein gutes Durchsatzverhalten zu fördern.

Bei der Allokation einer Relation sind zunächst D Rechner auszuwählen, denen die Fragmente der Relation zugeordnet werden. Dies ist für D=N trivial, anderenfalls erfolgt die Auswahl mit Hinblick auf eine Lastbalancierung, so daß auf jeden Rechner möglichst gleich viele Zugriffe entfallen. Wenn von einer Gleichverteilung der Zugriffe ausgegangen werden kann, genügt es hierzu, jedem Rechner in etwa gleich viele Tupel zuzuweisen. Anderenfalls müssen die Zugriffshäufigkeiten explizit berücksichtigt werden (s. [CABK88]). Bei der Auswahl der Rechner können auch weitere Faktoren eine Rolle spielen, z.B. wenn zur Unterstützung der Join-Verarbeitung zusammengehörige Fragmente verschiedener Relationen derselben Partition zugewiesen werden sollen. Die Zuordnung der M Fragmente unter den D ausgewählten Prozessoren ist für M=D wiederum trivial. Für M>D, was bei einer Bereichsfragmentierung sinnvoll sein kann, genügt i.a. eine Round-Robin-artige Zuordnung (ähnlich wie in Abb. 17-4).

Die Verteilung einer Relation über D Rechner verlangt auch eine analoge Partitionierung von Indexstrukturen. Dabei wird pro Partition ein eigener Teilindex geführt, der alle Schlüsselwerte enthält, die in den Sätzen des jeweiligen Knotens vorkommen. Die Verwendung und Wartung dieser Indexstrukturen ist damit wie für zentralisierte DBS möglich.