Сканирование миллиарда строк в сверхбыстрой базе данных

9

Фон

Локальная база данных содержит около 1,3 миллиарда уникальных строк. Каждая строка косвенно связана с определенной широтой и долготой (местоположением). В каждой строке есть отметка даты.

Случай использования

Проблема заключается в следующем:

  1. Пользователь устанавливает дату начала / окончания и диапазон значений (например, от 100 до 105).
  2. Система собирает все строки, соответствующие указанной дате, сгруппированные по местоположению.
  3. Система выполняет определение местоположений, которые в течение этих дат имеют статистическую вероятность попадания в заданный диапазон значений.
  4. Система отображает все соответствующие местоположения для пользователя.

Это проблема скорости и масштаба.

Вопрос

Какова самая дешевая архитектура решения, которую вы можете себе представить, которая позволила бы такой системе получать результаты для пользователей менее чем за пять секунд?

Текущая система

Окружающая среда в настоящее время:

  • PostgreSQL 8.4 (возможно обновление; переключение баз данных невозможно)
  • R и PL / R
  • XFS
  • WD VelociRaptor
  • 8 ГБ оперативной памяти (Corsair G.Skill; 1,3 ГГц)
  • Четырехъядерный процессор GenuineIntel 7 (2,8 ГГц)
  • Ubuntu 10.10

Модернизация оборудования приемлема.

Обновление - структура базы данных

Миллиарды строк в таблице напоминают:

id | taken | location_id | category | value1 | value2 | value3
  • id - первичный ключ
  • взятый - дата, назначенная строке
  • location_id - ссылка на широту / долготу
  • категория - описание данных
  • value1 .. 3 - другие значения, которые пользователь может запросить

В takenстолбце обычно указываются последовательные даты location_id, иногда в каждом местоположении есть данные с 1800 по 2010 год (около 77 000 дат, многие из которых дублируются, поскольку в каждом местоположении есть данные в одном и том же диапазоне дат).

Существует семь категорий, и таблицы уже разделены по категориям (с использованием дочерних таблиц). Каждая категория содержит ~ 190 миллионов строк. В ближайшее время количество строк в категории превысит миллиард.

Есть приблизительно 20 000 мест и 70000 городов. Места соотнесены с городом по широте и долготе. Назначение каждого местоположения определенному городу означает нахождение границ города, что не является тривиальной задачей.

идеи

Вот некоторые идеи, которые у меня есть:

  • Найдите облачный сервис для размещения базы данных.
  • Создайте рейд SSD (отличное видео).
  • Создайте таблицу, которая объединяет все места по городам (предварительный расчет).

Спасибо!

architecture database geospatial Дейв Джарвис
источник
10
«Переключение баз данных - это не вариант», что в значительной степени исключает большинство решений. удачи!
Стивен А. Лоу
1
Трудно сказать без дополнительной информации о том, что именно вы делаете с этими записями. Кроме того, вы ищете на 5 секунд наихудший случай (что, вероятно, означает, что каждая исследованная запись совпадает с нулевым местоположением)?
Гай Сиртон
2
@Dave: Сколько времени занимает текущая система? Использует ли текущая система PostGIS ? Является location_idли geographyили geometry, или относится ко второй таблице? location_idИндексируется ли столбец?
Rwong
1
@ Thorbjørn & @Darknight - В разделе идей я перечисляю предварительный расчет, который сократит данные до одного значения на город в день (на категорию). Расчет может повторяться ежегодно или даже ежемесячно, я полагаю. Это был мой план, если не было других возможностей (расчеты, вероятно, займут недели).
Дейв Джарвис
1
@ Дэйв, много возможностей, но вопрос в том, что для тебя важно. Вы уже исследовали, где сейчас находятся узкие места?

Ответы:

12

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

Если вы выполняете полное сканирование таблицы, вам нужны соответствующие индексы.

Если вы ожидаете ввода-вывода, вам нужно больше памяти для кэширования (недавно Джефф Этвуд упомянул, что в настольных системах доступны системы 24 ГБ).

Если вы ждете на процессоре, вам нужно посмотреть, можно ли оптимизировать ваши расчеты.

Это требует острого DBA-шляпа и операционная система, но оно того стоит, чтобы убедиться, что вы лайте правильное дерево.


источник
Как бы вы ни вырезали и нарезали его - даже если каждая строка занимает всего 100 байтов, 1,3 миллиарда строк = 121 ГБ. Со всеми вашими показателями и т. Д., Я уверен, это будет намного больше. На одной коробке вы будете медленными, если у вас не будет серьезного оборудования вокруг SSD + Тонны оперативной памяти. Более дешевый способ состоит в том, чтобы масштабировать через коробки.
Субу Шанкара Субраманян
4
@ Субу, ты хочешь распространяться? Теперь у вас есть две проблемы ...
Хех - с этим я согласен :) Но это дешевле!
Субу Шанкара Субраманян
@ Thorbjørn: Спасибо за ваше время и всю вашу помощь. Я думаю, что я уменьшу набор данных до 25 миллионов строк на категорию, а затем применю индексы к дате. Это должно уменьшить сканирование до ~ 70000 строк (в день с ограничением в две недели для диапазона), что должно быть довольно быстрым.
Дейв Джарвис
@ Дэйв, тебе все еще нужно знать, где твои узкие места. Учитесь, пока не нужно .
4

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

Если вы видите, что отметка даты слишком сильно меняется, вы можете разбить ее на части по горизонтали. (Надеюсь, они не добавляют больше широт / долгот!)

Subu Sankara Subramanian
источник
Спасибо за идеи. Есть потенциально 77 066 дат, и новые даты будут добавлены в будущем. У меня есть одна машина. Есть 20 000 местоположений, но разделение по местоположению не поможет, потому что данные для анализа охватывают все местоположения.
Дейв Джарвис
и чем отличается использование облака от вышеупомянутого решения?
Чани,
Это то, о чем я думал. Какой-то горизонтальный раздел, так что поиск может происходить параллельно по всем разделам.
davidk01
Разделение по дням, вероятно, будет наиболее полезным, в результате получится 2562 отдельных таблицы (366 дней x 7 категорий).
Дейв Джарвис
4

В худшем случае сценарий охватывает все даты в вашей базе данных.

Вы хотите прочитать 1,3 миллиарда записей и провести какой-то анализ каждой записи по сравнению с введенными значениями на одном физическом компьютере менее чем за 5 секунд. Результатом может быть все локации или нет - вы ничего не знаете заранее.

Учитывая эти параметры, я бы сказал, что это невозможно.

Достаточно взглянуть на свой жесткий диск: максимальная поддерживаемая скорость составляет менее 150 МБ / с. Чтение 1,3 миллиарда записей займет более 5 секунд. С точки зрения использования процессора, вы не сможете выполнять какой-либо статистический анализ 1,3 миллиарда записей за 5 секунд.

Ваша единственная надежда (tm :-)) - найти какую-то функцию поиска, основанную на значениях, введенных пользователем, которая сузит поиск (на несколько порядков). Вы можете рассчитать эту функцию поиска в автономном режиме. Не зная больше о точных критериях соответствия, я не думаю, что кто-то может сказать вам, как это сделать, но пример будет разделить диапазон значений на некоторый дискретный интервал и создать поиск, который даст вам все записи в этом интервале. Пока интервал достаточно мал, вы можете выполнять в нем реальную работу, например, убирая записи, которые не соответствуют введенному пользователем значению. В основном, торговая площадка для времени.

Может быть возможно сохранить все записи (или, по крайней мере, важную часть) в памяти. Вероятно, не в 8 ГБ. Это, по крайней мере, устранит часть дискового ввода-вывода, хотя даже пропускной способности памяти может быть недостаточно для сканирования всего за 5 секунд. В любом случае, это еще один метод ускорения такого рода приложений (в сочетании с моим предыдущим предложением).

Вы упоминаете об использовании облачного сервиса. Да, если вы платите за достаточное количество ресурсов процессора и ввода-вывода и разбиваете базу данных на несколько серверов, вы можете перебить или разделить ее.

Гай Сиртон
источник
Спасибо за ответ. Модернизация оборудования - рассмотрение согласно идеям, которые я перечислил. Идеальное решение на сумму менее 750 долларов США.
Дейв Джарвис
2

Второй комментарий Руонга к вопросу: PostgreSQL предлагает подходящие типы и инструменты индексов (индексы GIST, индексы GIN, Postgis, геометрические типы) таким образом, что геоданные и данные, связанные с датой и временем, должны быть доступны для поиска по этим критериям без особых проблем.

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

Дени де Бернарди
источник
Спасибо. Семь дочерних таблиц сгруппированы по местоположению, дате и категории, используя btree. Я исследовал индексы GIN в прошлом году, и они, насколько я помню, не помогли (или не помогли).
Дейв Джарвис
2
Индексирование местоположения на основе B-Tree не является ни малейшим полезным, учитывая тип поиска, который вы просматриваете. Вам нужен инвертированный индекс, который работает с необходимыми операторами, что в случае с Postgis обычно означает GIST. Вы можете выделить несколько медленных запросов ...
Дени де Бернарди
1

Учитывая, что вы используете PostgreSQL и данные широты / долготы, вы обязательно должны также использовать PostGIS, чтобы вы могли добавить пространственный индекс GiST в свою базу данных, чтобы ускорить процесс.

У меня есть такая таблица (с 350 тыс. Строк), конфигурация которой намного меньше вашей (2 ядра и 2 ГБ ОЗУ), но поиск занимает менее одной секунды.

wildpeaks
источник
0

Может быть, вы можете сломать реляционную модель, как это сделала Essbase с их архитектурой OLAP: Essbase Wikipedia

Я имею в виду создание одной таблицы на город, в результате чего получается более 1000 таблиц. Не один стол, как вы предложили, но много. Индексируйте каждую таблицу по дате и местоположению. Много таблиц, много индексов -> быстрее.

Михаэла
источник
Спасибо за примечание. Существует более 70000 городов, и многие разные значения широты и долготы находятся в пределах определенной городской территории.
Дейв Джарвис
@Dave: можете ли вы построить диаграмму Вороного для городов и классифицировать значения широты / долготы в тесселяции? (т.е. если это звучит бессистемно, пусть будет так.) Затем во время поиска вы будете искать все города, тесселяция которых затрагивает диапазоны широты / долготы запроса. Если вороной тесселяция слишком медленная, возможно, стоит попробовать квадратные квадраты (например, 5 градусов широты и 5 градусов долготы).
Rwong
0

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

Яни
источник
-2

Вы ожидаете, что велосипед будет бежать по шоссе. в настоящее время вы ищете решение для решения этой проблемы, вы не предвидите проблему, что если у вас есть 2 миллиарда записей? масштабируемость должна быть решена. Ответ прост в использовании объектных баз данных. например, кэш-память Intersystems

и поверь мне я не из межсистем ;-)

anerjan
источник