Wie implementieren Sie Sortierung und Paging auf verteilten Daten?

Question

Hier ist das Problem, das ich versuche zu lösen:

Ich muss in der Lage sein, eine ausgelagerte, sortierte Tabelle der Daten anzuzeigen, die über mehrere Datenbank-Shards gespeichert ist.

Paging und Sortierung sind wohlbekannte Probleme, die die meisten von uns lösen können, wenn die Daten aus einer einzigen Quelle stammen. Aber wenn Sie Ihre Daten über Shards aufteilen oder eine DHT- oder verteilte Dokumentendatenbank verwenden oder was auch immer Sie für NoSQL bevorzugen, werden die Dinge komplizierter.

Hier ist ein einfaches Bild von einem wirklich kleinen Datensatz:

Splitter | Daten
1 | A
1 | D
1 | G
2 | B
2 | E
2 | H
3 | C
3 | F
3 | I

Sortiert in Seiten (Page Size = 3):

Seite | Daten
1 | A
1 | B
1 | C
2 | D
2 | E
2 | F
3 | G
3 | H
3 | Ich

Und wenn wir die Benutzerseite 2, wir würden zurückkehren zeigen wollte:

D
E
F

Wenn die Größe der Tabelle in Frage ist so etwas wie 10 Millionen Zeilen , oder 100 Millionen, können Sie nicht einfach alle Daten auf einen Web-/Anwendungsserver ziehen, um sie zu sortieren und die richtige Seite zurückzugeben. Und Sie können natürlich nicht jeden einzelnen Shard sortieren und sein eigenes Stück der Daten pagen lassen, weil die Shards nichts voneinander wissen.

Um die Dinge zu komplizieren, können die Daten, die ich präsentieren muss, nicht zu weit veraltet sein, so dass die Vorausberechnung einer Menge nützlicher Sortierungen im Voraus und das Speichern der Ergebnisse für späteren Abruf nicht praktikabel ist.

Answer 1

Es gibt mehrere Lösungen, von denen einige nicht für Sie möglich sein, aber vielleicht einer von ihnen wird bleiben:

1. die sharding Sie durch Eingabe für diesen Wertebereiche (zB Scherbe 1 enthält AC, Scherbe 2 DF usw.). Alternativ können Sie eine andere Tabelle mit Fremdschlüsseln für diese Tabelle als Index verwenden und die Indextabelle mit diesem System zerlegen. Auf diese Weise können Sie bestimmte Bereiche einfach finden und abrufen. Diese Lösung ist wahrscheinlich die beste in Bezug auf die Leistung, wenn Sie es tun können (es geht davon aus, dass die Anzahl der Shards statisch ist und die Shards zuverlässig sind).
2. Identifizieren Sie die Seitenelemente durch binäre Suche. Angenommen, Sie möchten die Elemente 100 bis 110 haben. Zählen Sie für jeden Shard die Anzahl der lexikografischen Werte unter "M".Wenn die Summe der Zahlen über 100 liegt, reduzieren Sie den Drehpunkt, andernfalls erhöhen Sie ihn (mit der Binärsuche). Nachdem Sie den 100. Gegenstand (den ersten Gegenstand auf Ihrer Seite) identifiziert haben, nehmen Sie die obersten 9 (10 - 1) Gegenstände, die größer als dieser Gegenstand sind, aus allen Scherben, holen Sie sie, sortieren Sie die gesamte Liste, nehmen Sie die obersten 9 aus der Liste erster Artikel und da ist deine Seite! Dieser Ansatz ist schwieriger zu implementieren und erfordert O(log(n)) Abfragen, so dass es langsamer als (1) ist, aber immer noch ziemlich schnell sein kann, wenn die Last nicht sehr schwer ist.
3. Speichern Sie die Seitennummer mit jedem Wert. Dies würde Ihnen blitzschnell schnelle Lesevorgänge, aber furchtbar langsame Schreibvorgänge bescheren, so dass es nur in dem Szenario funktioniert, in dem es nur sehr wenig Schreibvorgänge gibt (oder nur an die geordnete Variable anfügt).