Dremel. Как Google считает в real-time?

    Dremelмасштабируемая система обработки запросов в режиме близком к режиму реального времени (near-real-time), предназначенная для анализа неизменяемых данных [4].

    Авторы research paper [4] (среди которых, судя по всему, и наши соотечественники — Сергей Мельник и Андрей Губарев), в котором описываются базовые принципы и архитектура Dremel, заявляют, что система в силах:
    • выполнять агрегирующие запросы над боле чем над триллионом строк за секунды;
    • масштабируется на тысячи CPU;
    • предназначена для работы с петабайтами данных;
    • имеет тысячи пользователей внутри Google (дословно «at Google» [4]).

    UPD1: ниже картинка-дежавю для внимательных читателей.


    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.
    * Полный список источников, используемый для подготовки цикла.

    Дмитрий Петухов,
    MCP, PhD Student, IT-зомби,
    человек с кофеином вместо эритроцитов.
    • +22
    • 13,7k
    • 9
    Поделиться публикацией

    Комментарии 9

      +3
      Dremel уже не тот… )
        +5
        Последние несколько дней меня не покидает чувство дежавю. Такое ощущение, что я видел эту новость вчера, и позавчера, и позапозавчера. Или может быть дело в изображении...?
        Если серьезно, то был бы признателен, если бы их меняли для разнообразия, либо не ставили вовсе. А то когда листаешь хабр на наличие новых постов, натыкаясь на такой с ранее виденной картинкой мучаешься мыслью, пролистал ли все новое или же еще нет.
          +3
          Я так и знал, что разные заголовки не помогают) Буду исправляться.
          0
          Просто поражает как они до этого додумались!
          Спасибо за статьи.
            –1
            Мне Стьюи напоминает, то что в Гриффинах убили пса Брайана. Они были такой хорошей командой :(
              +1
              заспойлерить?
              +2
              К Open Source аналогам Dremel относят Cloudera Impala, Apache Drill, Parquet (Twitter)

              Parquet — это формат хранения данных. Он поколоночный, но ничего общего с иерархической организацией данных не имеет. С таким же успехом аналогом Dremel можно назвать любую СУБД, поддерживающую поколоночную организацию данных
              Impala — решение класса SQL-on-Hadoop и в большей степени является аналогом Google F1, нежели Dremel, так как иерархическую организацию данных опять же не поддерживает
                –1
                Про Parquet Вы совершенно точно отметили. А Impala еще также поддерживает объединение таблиц и распространяется под Apache лицензией, в то время как Dremel поддерживает только single-table queries (что нивелируется поддержкой запросов по вложенным данным) и является проприетарным продуктом.
                Но все же я бы не делал из слов 'аналог' (как это указано в статье) и 'копия' синонимы.
                0
                Отличная статья, спасибо большое!
                Мне только не удалось найти в оригинальной работе по Dremel каких-либо упомянаний о Parquet. Вы не могли бы поподробнее рассказать об этом?

                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                Самое читаемое