W jaki sposób wdrażasz sortowanie i stronicowanie na rozproszonych danych?

Question

Oto problem, który próbuję rozwiązać:

Potrzebuję być w stanie wyświetlić stronicowaną, posortowaną tabelę danych, która jest przechowywana w kilku odłamkach bazy danych.

Przywoływanie i sortowanie to dobrze znane problemy, które większość z nas może rozwiązać na wiele sposobów, gdy dane pochodzą z jednego źródła. Ale jeśli dzielisz dane przez shardy lub używasz DHT lub bazy danych dokumentów rozproszonych lub dowolnego smaku NoSQL, który wolisz, sprawy stają się bardziej skomplikowane.

Oto prosty obraz naprawdę mały zestaw danych:

Shard | Data
1 | A
1 | D
1 | G
2 | B
2 | E
2 | H
3 | C
3 | F
3 | I

sortowane do stron (Page Size = 3):

Strona | Data
1 | A
1 | B
1 | C
2 | D
2 | E
2 | F
3 | G
3 | H
3 | I

A jeśli chcieliśmy pokazać stronę użytkownika 2, wrócilibyśmy:

D
E
F

Jeśli rozmiar tabeli w pytaniu jest coś takiego jak 10 milionów wierszy lub 100 milionów, nie można po prostu ściągnąć wszystkich danych na serwer aplikacji/strony internetowej, aby je posortować i zwrócić poprawną stronę. I oczywiście nie możesz pozwolić, by każdy pojedynczy odłamek sortował i wysyłał własny fragment danych, ponieważ odłamki nie wiedzą o sobie nawzajem.

Dane, które muszę przedstawić, nie mogą być zbyt nieaktualne, dlatego wcześniejsze obliczenie zestawu użytecznych rodzajów i przechowywanie wyników do późniejszego wyszukiwania nie jest praktyczne.

Answer 1

Istnieje kilka rozwiązań, z których niektóre mogą nie być wykonalne dla Ciebie, ale może jeden z nich będzie trzymać:

1. Wykonaj sharding przez wejście wynosi dla tej wartości (np odłamek 1 zawiera AC, fragment 2 DF itp.). Alternatywnie, użyj innej tabeli z kluczami obcymi do tej tabeli jako indeksu i odznacz tabelę indeksu za pomocą tego systemu. W ten sposób możesz łatwo zlokalizować i pobrać określone zakresy. To rozwiązanie jest prawdopodobnie najlepsze pod względem wydajności, jeśli możesz to zrobić (zakłada, że ​​liczba odłamków jest statyczna, a odłamki są niezawodne).
2. Identyfikuj elementy strony za pomocą wyszukiwania binarnego. Na przykład, powiedz, że chcesz pozycji 100 do 110. Dla każdego odłamu, policz liczbę wartości leksykograficznie poniżej "M".Jeśli suma liczb jest powyżej 100, zmniejsz punkt obrotu, w przeciwnym razie zwiększ go (za pomocą wyszukiwania binarnego). Po zidentyfikowaniu setnego przedmiotu (pierwszego przedmiotu na twojej stronie), weź 5 pierwszych (10 - 1) przedmiotów o wartości większej niż ten przedmiot z każdego odłamka, pobierz je, posortuj całą listę, zbierz 9 najlepszych z listy, pierwszy przedmiot i twoja strona! Takie podejście jest trudniejsze do wdrożenia i będzie wymagało zapytań o numer O(log(n)), więc jest wolniejsze niż (1), ale może być stosunkowo szybkie, jeśli obciążenie nie jest zbyt duże.
3. Zapisz numer strony dla każdej wartości. Daje to wam niesamowicie szybkie odczyty, ale okropnie powolne zapisy, więc działa tylko w scenariuszu, w którym jest bardzo niewiele zapisów (lub tylko dołącza pod względem zamówionej zmiennej).