Современные процессоры претерпели значительное развитие. Но как MonetDB использует это развитие, чтобы максимизировать свою производительность?

Компьютерные процессоры значительно развились за последние три десятилетия. Это развитие связано не только с увеличением количества содержащихся в нем транзисторов, но и с развитием архитектуры. Следовательно, приложение должно адаптироваться к тому, как работает ЦП, чтобы максимизировать свой потенциал. Такие же старые, как и сам ЦП, системы баз данных были основой современной индустрии. Но удалось ли сообществам баз данных ограничить возможности ЦП?

Несмотря на положительное развитие ЦП, существующие системы баз данных не могут воспользоваться преимуществами, поскольку они могут достичь только низкой эффективности выполнения инструкций за цикл (IPC). В основном они используют модель выполнения запросов вулкан, которая является причиной такой неэффективности. Модель вулкана использует модель обработки, называемую «кортеж за раз», которая выполняет один кортеж за один цикл ЦП. Следовательно, это приводит к накладным расходам на интерпретацию и ограничивает способность ЦП выполнять параллельное выполнение за счет конвейерной обработки цикла. Наблюдение за системой баз данных MySQL показывает, что фактические вычисления составляют только 10% от общего времени выполнения [2]. Остальные 90% - это накладные расходы на интерпретацию, такие как создание и просмотр хеш-таблицы, получение n-го поля данных MySQL и копирование данных для обработки.

Устранение этих недостатков

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

Мудрое исполнение по столбцам

MonetDB представляет столбцовую структуру данных, называемую двоичной ассоциативной таблицей (BAT). Один массив BAT содержит все значения в одном столбце базы данных. Таким образом, теперь мы можем применять операторы к этому массиву BAT, а не индивидуально к каждому элементу данных. Кроме того, имея ту же операцию, выполняемую с массивом данных, ЦП теперь может применять конвейерную обработку цикла.

В этом посте мы много говорили о конвейерной обработке петель. Но что такое конвейерная обработка петли? Взгляните на следующую иллюстрацию.

В упрощенном определении мы видим, что инструкция ЦП состоит из трех фаз: ЧТЕНИЕ, ВЫЧИСЛЕНИЕ и ЗАПИСЬ (см. Эту страницу Википедии для подробного объяснения цикла ЦП). Как мы видим, конвейерная обработка цикла позволяет ЦП начать выполнение следующей итерации, не дожидаясь завершения предыдущей итерации. Чтобы поместить в контекст обработки данных, конвейерная обработка цикла позволит ЦП начать чтение следующего элемента данных, продолжая вычислять результат для текущих данных. В результате у всего цикла будет меньшая задержка.

Когда мы используем массив BAT, такая конвейерная обработка цикла возможна, поскольку у нас есть понятие массива для цикла. Однако это будет невозможно, если мы будем выполнять вычисление кортежа за раз, поскольку не имеет смысла выполнять цикл для одного кортежа! В этом случае выполнение будет выполняться последовательно, при этом кортеж должен будет дождаться завершения предыдущего кортежа, прежде чем даже будет выполнен.

MIL Алгебра

MonetDB представляет алгебру MIL (язык инструкций MonetDB) для своего языка запросов. Хотя это может быть как реляционная алгебра в терминах СУБД. Однако, в отличие от реляционной алгебры, алгебра MIL не имеет степени свободы. В алгебре MIL операторы имеют фиксированные параметры и структуру данных для обработки данных. Операторы на MIL будут отображать функцию этого оператора на весь элемент данных в BAT.

Двигатель X100

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

Чтобы справиться с этим, для MonetDB создан улучшенный движок под названием X100. Он представляет сбалансированный подход, который позволяет избежать обработки кортежей за раз, но управляет материализацией, чтобы она не превышала пропускную способность памяти. Это делается путем материализации только в терминах вектора, а не всего столбца. Векторы - это срезы всего элемента столбца. Размер вектора должен быть установлен так, чтобы он помещался в кеш-память процессора. Таким образом, ограничение пропускной способности памяти не будет препятствовать реализации высокой эффективности ЦП.

Анализ производительности

Чтобы проанализировать выигрыш в производительности от векторизованной обработки запросов, мы собираемся увидеть результаты экспериментов на тесте TPC-H Benchmark, выполненном на MonetDB / X100 для MonetDB / MIL и MySQL.

Первое наблюдение, которое мы можем получить в результате эксперимента, - это способность MonetDB / X100 запускать все примитивы за небольшое количество циклов ЦП на кортеж. Например, примитив умножения выполняется только 2,2 цикла на кортеж, по сравнению с 49 циклами на кортеж в MySQL. Меньшее количество циклов, необходимых для каждого примитива выполнения, приводит к повышению общей производительности.

Второе замечание касается предела производительности памяти. Поскольку MonetDB / X100 материализуется только в терминах вектора, данные, которые будут обрабатываться примитивом, извлекаются из кеша ЦП, а не из основной памяти. Это позволяет MonetDB / X100 достичь полосы пропускания 7,5 ГБ / с. С другой стороны, MonetDB / MIL достигает предела пропускной способности памяти всего 500 МБ / с, поскольку примитивы должны извлекать данные из основной памяти. Авторы также упоминают, что MonetDB / X100 должен работать с кэшированными данными, а реализация векторной разметки по столбцам не предназначена для оптимизации разметки памяти.

Наконец, авторы указывают на влияние размера вектора на общую производительность. Размер вектора должен быть относительно небольшим, чтобы он мог поместиться внутри кеша. Однако, если мы установим его слишком маленьким, мы потеряем параллелизм ЦП и увеличим накладные расходы на интерпретацию. На крайнем уровне установка размера вектора на 1 приведет к одновременной работе с кортежем. С другой стороны, авторы также сообщают о снижении производительности, когда размер вектора слишком велик, то есть больше не может поместиться в кеш-память ЦП.

Заключение

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

MonetDB был предметом долгих исследований. Если вам интересно узнать больше о MonetDB, вы можете проверить их публикацию в google scholar. Вы также можете проверить домашнюю страницу, чтобы увидеть ее текущий статус. Это также проект с открытым исходным кодом, в который вы также можете внести свой вклад. Вы можете посетить их зеркальное хранилище на этой странице Github.

Ссылки:

[1] Питер Александр Бонц и др. 2002. Monet: ядро ​​СУБД нового поколения для приложений с интенсивными запросами. Амстердамский университет [Хозяин].

[2] Питер Бонц, Марцин Жуковски и Нильс Нес. 2005. MonetDB / X100: Hyper-Pipelining Query Execution .. In Cidr, Vol. 5. 225–237.