Dremel – масштабируемая система обработки запросов в режиме близком к режиму реального времени (near-real-time), предназначенная для анализа неизменяемых данных [4].
Авторы research paper [4] (среди которых, судя по всему, и наши соотечественники — Сергей Мельник и Андрей Губарев), в котором описываются базовые принципы и архитектура Dremel, заявляют, что система в силах:
- выполнять агрегирующие запросы над боле чем над триллионом строк за секунды;
- масштабируется на тысячи CPU;
- предназначена для работы с петабайтами данных;
- имеет тысячи пользователей внутри Google (дословно «at Google» [4]).
Dremel является проприетарным продуктом Google, находится в эксплуатации с 2006 года, официально сообществу был представлен на конференции Very Large Data Base (VLDB) Endowment в 2010 году.
Dremel используется в задачах анализа собранных поисковым роботом документов, трекинге данных об установке приложений в Android Market, сервисах Google Books и спам-анализе.
В 2012 году Google открыл доступ к Dremel для разработчиков через сервис Google BigQuery [14].
Модель данных
Как и многие системы такого класса, Dremel обладает возможностью масштабироваться на несколько тысяч узлов, запускается на commodity-оборудовании, обеспечивает надежное хранение данных, отказоустойчивость и репликацию, работает с неизменяемыми данными и имеет собственный SQL-подобный язык запросов.
Dremel для хранения данных использует распределенную файловую систему Google File System, а единицей хранения данных является tablet.
Но, без сомнения, ключевая инновация Google Dremel – модель данных, которая в [4] звучит как «nested columnar storage», или, в переводе, колоночное хранилище вложенных данных.
Основные принципы nested columnar storage: данные, чья схема явно определена, хранятся в хранилище, ориентированном на столбцы (column-striped storage), вместе со связанными с ними данными.
Разберем преимущества и недостатки такого выбора.
Колоночные хранилище позволяет с наибольшей скоростью, по сравнению с хранилищем, ориентированным на построчное хранение данных, читать большие объемы данных, а также эффективно их сжимать (т.к. данные одинаковых типов хранятся в одном месте). С другой стороны, операция записи в колоночных хранилищах является более дорогой по сравнению с row-striped хранилищами, а поддержка транзакционности изменений – нетривиальной задачей.
Хранение данных вместе со связанными (в т.ч. вложенными) данными также, как и колоночная схема хранения, позволяет увеличить скорость чтения данных. Одновременно такой способ хранения подразумевает наличие некоторой избыточности данных и, как следствие, необходимость решения проблемы согласованности разных копий этих данных.
Инженеры Google решили эту задачу следующим образом: Dremel работает с immutable-данными, а проблема избыточности решается за счет введения для каждого столбца двух дополнительных уровней: уровня определения (definition level) и уровня повторения (repetition level).
Источник иллюстрации [4, Figure 2]
Источник иллюстрации [4, Figure 3]
В каждой колонке храниться набор блоков. В свою очередь, каждый блок представляет собой сжатые данные и целочисленные значения уровня определения и уровня повторения. Таким образом, Dremel, зная все о структуре и расположении данных, которые необходимы для выполнения запроса, может получить необходимую информацию «на месте» (в терминологии [4] — «in situ»).
Кодирование каждого блока колонки по схеме <value, repetition_level, definition_level> приводит к тому, что структура хранения уже содержит в себе алгоритм сборки, представляющий собой конечный автомат, где:
- множество состояний – множество столбцов, на которые разделен документ;
- переходы – значения уровней повторений.
Источник иллюстрации [4, Figure 4]
Исполнение запросов
Для исполнения запросов Dremel использует архитектуру многоуровневого дерева обслуживания (multi-level serving tree): root-сервер получает от клиента запрос на выполнение, читает необходимые метаданные tablet'ов и направляет (route) запросы на следующие уровни дерева. И так пока запрос не достигнет листьев дерева обслуживания. Листья дерева взаимодействуют уже непосредственно с GFS для получения необходимых данных.
Так разные запросы на Dremel выполняются одновременно, планировкой запросов на основе их приоритета и наилучшей балансировки нагрузки занимается Query dispatcher. Query dispatcher также ответственен за обработку отказов на уровне tablet'ов, ставших недоступными во время выполнения запроса и «меленных» tablet'ов.
Интересным решением является также то, что результат выполнения запроса вернется не после того, как будут обработаны 100% записей, а раньше – в [4] приводится цифра 98%, как наиболее типичная. С одной стороны это избавляет Dremel от ожидания окончания работы «медленных» листьев дерева выполнения запроса; с другой приводит к некоторой погрешности в конечном результате, что вполне приемлемо для OLAP-систем и вряд ли допустимо в OLTP-системах.
Результаты экспериментов
В результате экспериментов, начальные данные которых — 3К вычислительных узлов, 85 млрд. строк — Dremel выполняет запросы на порядки быстрее, чем алгоритмы MapReduce, запущенные как на record-oriented хранилищах, так и на columnar-oriented хранилищах.
Источник иллюстрации [4]
Кроме того, в [4] заявляется, что в ходе экспериментов некоторые скорость сканирования таблиц на некоторых запросах напрямую приближалась к 100 млрд. записей в секунду.
Влияние на Open Source
К Open Source аналогам Dremel относят Cloudera Impala, Apache Drill, Parquet (Twitter).
Список источников*
[4] Sergey Melnik, Andrey Gubarev, Jing Jing Long, Geoffrey Romer, et al. Dremel: Interactive Analysis of Web-Scale Datasets. Proceedings of the VLDB Endowment, 2010.
[14] Google BigQuery — Google Developers.
* Полный список источников, используемый для подготовки цикла.
Автор: codezombie
