Как реализовать сортировку и разбиение на страницы для распределенных данных?

Question

Вот проблема, которую я пытаюсь решить:

Мне нужно иметь возможность отображать разбитую на страницы отсортированную таблицу данных, которая хранится в нескольких сегментах базы данных.

Пейджинг и сортировка - это хорошо известные проблемы, которые большинство из нас может решить разными способами, когда данные поступают из одного источника. Но если вы распределяете свои данные по осколкам, используете DHT или базу данных распределенных документов или любой другой вариант NoSQL, который вы предпочитаете, все становится сложнее.

Вот простая картина действительно небольшого набора данных:

Осколок | Данные
1 | A
1 | D
1 | G
2 | B
2 | E
2 | H
3 | C
3 | F
3 | Я

Сортировка по страницам (размер страницы = 3):

Страница | Данные
1 | A
1 | B
1 | C
2 | D
2 | E
2 | F
3 | G
3 | H
3 | Я

И если бы мы хотели показать страницу пользователя 2, мы бы вернули:

D
E
F

Если размер рассматриваемой таблицы составляет примерно 10 миллионов строк или 100 миллионов, вы не можете просто перенести все данные на сервер веб / приложений, чтобы отсортировать их и вернуть нужную страницу. И вы, очевидно, не можете позволить каждому отдельному фрагменту сортировать и пейджировать свой собственный фрагмент данных, потому что фрагменты не знают друг о друге.

Чтобы усложнить ситуацию, данные, которые мне нужно представить, не могут быть слишком устаревшими, поэтому предварительный расчет набора полезных сортировок заблаговременно и сохранение результатов для последующего извлечения нецелесообразно.

Answer 1

Существует несколько решений, некоторые из которых могут оказаться неосуществимыми для вас, но, возможно, одно из них будет придерживаться:

1. Выполнить сегментирование по диапазонам ввода для этого значения (например, фрагмент 1 содержитAC, осколок 2 DF и т. Д.).В качестве альтернативы используйте другую таблицу с внешними ключами для этой таблицы в качестве индекса и осколите таблицу индексов с помощью этой системы.Таким образом, вы можете легко найти и получить указанные диапазоны.Это решение, вероятно, является лучшим с точки зрения производительности, если вы можете это сделать (предполагается, что количество сегментов является статическим, а фрагменты надежными).
2. Идентификация элементов страницы с помощью бинарного поиска.Например, скажем, вы хотите, чтобы пункты от 100 до 110. Для каждого осколка подсчитайте количество значений, лексикографически ниже «M».Если сумма чисел выше 100, уменьшите опорную точку, иначе увеличьте ее (используя бинарный поиск).После того, как вы определили сотый элемент (первый элемент на вашей странице), возьмите из каждого осколка первые 9 (10 - 1) элементов размером больше этого элемента, выберите их, отсортируйте весь список, возьмите первые 9 из списка, добавьтеПервый пункт и вот ваша страница!Этот подход сложнее реализовать и потребует O(log(n)) запросов, поэтому он медленнее, чем (1), но все же может быть достаточно быстрым, если загрузка не очень большая.
3. Сохранять номер страницы с каждым значением,Это дало бы вам невероятно быстрое чтение, но ужасно медленное запись, поэтому оно работает только в сценарии, в котором очень мало записей (или только в терминах упорядоченной переменной).