Хорошо, многообещающий этот титул, что именно возможно с S3? Оказывается, совсем немного. Фактически, в этой статье описывается, как искать n-мерные данные с помощью S3.
S3 для хранения
S3 - это практически неограниченное хранилище Amazon. Вы можете хранить файлы любого размера в S3 Buckets, и они будут храниться с избыточностью на нескольких устройствах в нескольких объектах в регионе. Для файлов, с которыми вы хотите часто взаимодействовать, стандартные затраты на хранение составляют около 3 центов (США) за ГБ в месяц. Если вы помечаете свои данные для хранения в S3 Glacier, тогда стоимость составит 0,4 цента за ГБ в месяц, и вы можете вернуть их в стандартный статус через несколько часов, если это необходимо.
Я храню данные о движении судов с большой части земной поверхности в S3, и я настраиваю старые данные для автоматического перемещения в Glacier. В один день может быть до 27 миллионов записей, а в формате CSV (значения, разделенные запятыми) - 2,4 ГБ. Фактически, я храню необработанные данные (AIS NMEA) в S3, а триггер Java Lambda создает версию CSV.
Произвольный доступ к S3
Одна из вещей, которые мне нравятся в облачных сервисах, - это обнаружение слабых мест с точки зрения стоимости и возможностей, и я подумал, смогу ли я быстро и дешево запросить этот набор данных в S3.
Оказывается, файлы в S3 доступны случайным образом. Я могу указать диапазон байтов с помощью заголовка HTTP-запроса Range, и это все, что будет возвращено (без штрафа за задержку).
Произвольный доступ позволяет выполнять поиск по индексу. Если я приблизительно знаю, где в файле находятся мои записи, используя индекс, я могу захватить только этот фрагмент файла и извлечь нужную мне информацию.
Как ГИС-системы выполняют пространственные запросы?
Запрос окна в 2, 3 или более измерениях - это поиск данных в поле с таким же количеством измерений. Например, если у меня есть пространственно-временные данные для всех США, то оконный запрос может заключаться в поиске записей в определенном пригороде Чикаго в обеденное время в определенный день.
Как ГИС-системы выполняют оконные запросы к двумерным пространственным и пространственно-временным данным?
Пространственные запросы обычно выполняются с помощью R-Trees, которые представляют собой достаточно сложную структуру данных. Поиск древовидной структуры, представленной в плоских файлах, может означать выполнение ряда операций чтения с произвольным доступом по мере обхода дерева. Что еще более важно, чтения носят серийный характер, так как я не знаю следующего места чтения, пока не завершу предыдущее чтение. Более дискретное последовательное чтение означает больше задержек, особенно если я читаю плоский файл в S3 и испытываю задержку при каждом чтении.
Отображение трех или более измерений на кривую Гильберта
В 3 или более измерениях популярным методом индексации является сопоставление многомерной области с одним измерением с помощью кривой заполнения пространства. Хорошим выбором для этой кривой заполнения пространства является кривая Гильберта. Разрежьте вашу трехмерную область на регулярную сетку из 1024x1024x1024 ячеек, тогда кривая Гильберта, состоящая из одной волнистой линии, посетит все 1-метровые точки.
В качестве интерлюдии, вот пара двухмерных примеров этой волнистой линии, называемой кривой Гильберта.
Вот трехмерная анимация кривой Гильберта:
Кривая Гильберта имеет несколько хороших свойств локальности, потому что она не делает больших скачков, следующее значение на кривой всегда на расстоянии одной единицы. Это означает, что если две точки имеют близкие индексы, то они также будут геометрически близки друг к другу. Обратное не гарантируется.
Редкий индекс
Теперь, когда все точки данных сопоставлены с одним измерением, я могу отсортировать их по этому измерению, а затем использовать простые методы поиска по одномерному индексу в базе данных. Когда вы индексируете столбец в таблице базы данных, вы получаете возможность найти точные строки в каждой таблице, соответствующие значению в этом столбце. Однако в индексе может быть столько записей, сколько строк в таблице. Если вы используете так называемый разреженный индекс, тогда у вас есть позиции некоторых строк, но вам, возможно, придется выполнить дополнительное чтение после них, чтобы найти другие. разреженный индекс может быть намного меньше полного индекса, например 0,1% от размера полного индекса.
Я тут обхожусь, так что давайте перейдем к изюминке. Если я отсортирую свои 27 миллионов записей (2,4 ГБ CSV) по возрастанию индекса Гильберта с одним миллионом точек (10 бит), а затем создаю небольшой разреженный индексный файл (440 КБ), у меня появится возможность выполнять быстрые оконные запросы через произвольный доступ к моим данным. Я даже могу вести поиск параллельно, потому что заранее знаю, где находятся мои записи (приблизительно). В идеале у меня есть запросы, которые довольно малы по пространству и времени, хотя я обнаружил, что запросы, не ограниченные по времени, тоже могут работать довольно хорошо.
Библиотека в помощь
Здесь есть несколько фигурных проблем, связанных с переводом поля поиска в диапазоны на кривой Гильберта (возможно, с укрупнением диапазонов, если их слишком много), а оттуда для доступа к диапазонам байтов, на которые указывает индекс. К счастью, эти проблемы решаются с помощью библиотеки java под названием sparse-hilbert-index, которую я собрал и опубликовал на GitHub.
Давайте попробуем пример. Мои входные данные CSV выглядят так:
mmsi,messageId,time,lat,lon,speedKnots,heading,course,navigationStatus,rateOfTurn,source,specialManoevreIndicator,timeSecondsOnly,isUsingRAIM,class 4124607775,18,1543283257000,-66.97455333333333,33.95234833333333,8.7,67.3,67,,,NORAIS2,,35,N,N, 4124607775,18,1543283257000,-66.97455333333333,33.95234833333333,8.7,67.3,67,,,NORAIS2,,35,N,N, 538006789,1,1543283259000,-39.57300333333333,33.18371833333333,12.7,85.1,84,UNDER_WAY_USING_ENGINE,-13,NORAIS2,0,39,Y,N,A ...
Я создаю отсортированный файл данных и индекс Гильберта, запустив этот код (с благодарностью commons-csv):
13 минут спустя на ноутбуке i5 сортировка 27 миллионов записей CSV завершена, и индексный файл создан.
Затем я развертываю input-sorted.csv (2,4 ГБ) и input-sorted.csv.idx в корзину S3 и пытаюсь запросить данные, как показано ниже. Сначала я подсчитаю количество записей в районе Сиднея за час. Я собираюсь упростить задачу и предположить, что данные находятся в общедоступной корзине, поэтому мне не нужно проходить аутентификацию (но сделайте это только в том случае, если ваши данные не конфиденциальны).
Загрузите индексный файл (который вы можете кэшировать локально, если хотите):
Выполните поиск:
Загрузка индексного файла (440 КБ) заняла 500 мс.
Вышеупомянутый поиск обнаружил 2389 записей в 169 мс через не очень быстрое корпоративное подключение к Интернету. Было прочитано 3347 записей (коэффициент совпадения 0,71). Некоторый уровень напрасных усилий является следствием разреженного индекса, но, конечно, нам не нужна ГИС-система на сервере!
Интересно, что если мы запросим набор данных для региона Сидней (Австралия) для всего временного измерения (24 часа), то производительность все равно будет разумной: 6720 мсек для возврата 36940 записей с коэффициентом совпадения 0,55. 37 фрагментов (разделы объекта S3, на которые указывают записи индекса) были прочитаны (частично) со средним временем до первого байта (TTFB) 114 мс (таким образом, задержка нашего интернет-соединения составляет 4200 мсек. истекшего времени). Ближе к S3 (скажем, в EC2 или Lambda) можно значительно сэкономить время, но еще один трюк в рукаве - одновременное чтение с S3.
Используйте параллелизм!
В приведенной выше команде поиска вы увидите, что для параметра concurrency установлено значение 1. Я обнаружил, что оптимальное число при посредственном подключении к Интернету для этого набора данных на S3 - 8; то есть 8 блоков извлекаются одновременно, анализируются, фильтруются и объединяются. Запрос, который занял 6720 мс (в основном из-за неограниченного измерения времени), теперь занимает 839 мс!
Искать в AWS
Я также выполнил тестовые прогоны из EC2 (t2.large), и, как и ожидалось, время до первого байта уменьшилось примерно до 50 мс. Благодаря параллелизму продолжительность дневного запроса снизилась до 380 мс. Я полагаю, что с уменьшением задержки время поиска начинает играть более важную роль, и золотая середина для уровня параллелизма, кажется, составляет около 4.
Потоковый API
API, используемый для извлечения записей из результатов поиска, предлагает функции потоковой передачи через библиотеку RxJava.
Другие форматы
Имейте в виду, что CSV - не самый эффективный метод хранения и извлечения данных. Более целевые двоичные форматы могут сделать ваши запросы во много раз быстрее.
Тюнинг
Количество записей в разреженном индексе имеет большое влияние на коэффициент попадания (показатель того, сколько записей вы прочитали, чтобы найти то, что вы запросили). Если вы можете кэшировать файлы индекса локально или поместить их в более быстрое хранилище, вы можете использовать большее количество записей в каждом файле индекса. Экспериментирование - это лучший способ. Создайте несколько индексов для одного и того же файла разного размера и посмотрите, что лучше всего подходит для ваших шаблонов запросов.
Вообще говоря, если ваши запросы настроены так, что они не возвращают много записей, тогда ваше время ответа должно быть указанного выше порядка. Поиск с неограниченными размерами (например, время в предыдущем запросе) может работать, но я бы посоветовал ограничить только одно измерение.
Просмотр статистики поиска
При выполнении поиска вы можете указать параметр withStats для просмотра различных показателей поиска:
index .search(bounds) .withStats() .concurrency(1) .url(url) .last() .forEach(System.out::println);
Производит:
WithStats [elapsedMs=169, recordsFound=2389, recordsRead=3347, hitRatio=0.7138, bytesRead=392261, timeToFirstByteMsTotal=94, timeToFirstByteMsAverage=94.0000, chunksRead=1]
А как насчет двух измерений?
Я рассмотрел пример с 3-мя измерениями, но разреженный индекс Гильберта будет хорошо работать и для 2-х измерений. Таким образом, S3 также может стать вашей двухмерной пространственной базой данных.
Не только S3
Обратите внимание, что хранилище BLOB-объектов Azure и облачное хранилище Google также предлагают произвольный доступ через заголовок диапазона HTTP. Эти параметры хранения также можно использовать с библиотекой sparse-hilbert-index.
А как насчет Афины?
Это хороший вопрос! Тем более, что AWS предлагает Athena для файлов CSV (и других форматов) в сегментах S3, которые могут выполнить полное сканирование CSV-файла размером 2 ГБ за 1,5 секунды!
Подход sparse-hilbert-index может понравиться, если учесть затраты на выполнение большого количества проиндексированных поисков по большому количеству данных по сравнению с полным сканированием. Затраты на Athena невысоки (5 долларов США за ТБ данных, проверенных на предмет запросов), но в некоторых масштабах они могут стать значительными. В некоторых случаях соответствующее потребление энергии при выполнении большого количества полных поисков также может быть этически сложным (а также довольно трудным для расчета). Я думаю, что трудно конкурировать с Athena в поиске больших файлов, но могут быть некоторые крайние случаи, когда предпочтение отдается sparse-hilbert-index!
Чтобы подлить масла в огонь, Athena поддерживает формат Parquet, который можно индексировать так, чтобы на каждой странице была статистика min-max. Если вы сортируете данные в поле, которое хотите запросить (в нашем случае мы добавили бы столбец рассчитанного индекса Гильберта), то Athena может теоретически самостоятельно выполнять индексированный поиск (непроверенный). Афине по-прежнему необходимо просматривать статистику для каждой страницы (по умолчанию 1 МБ), поэтому теоретически она не так эффективна, как sparse-hilbert-index, который точно знает, на каких страницах искать. Обратите внимание, что по состоянию на июнь 2019 года Athena не поддерживает индексированные форматы Parquet для более быстрого доступа (1). Когда или если придет поддержка, стоит поэкспериментировать!
Забрать домой
- эффективные пространственные, пространственно-временные и даже n-мерные запросы возможны из плоских файлов или сервисов хранения, таких как S3!
- перейдите к sparse-hilbert-index для поддержки простой в использовании библиотеки для этого варианта использования
- оцените Афину также для ваших запросов
