Schism управляемый рабочей нагрузкой подход к репликации и разделению баз данных

A. Аппаратно-программная конфигурация

Эксперименты, описанные в разд. 3 и подразделе 6.3, выполнялись на восьми серверах с MySQL, соединенных через один коммутатор Gigabit Ethernet. Более мощная машина использовалась для генерации трафика и выполнения экспериментов с производительностью времени выполнения, описанных в подразделе 6.2. Подробности о составе аппаратных и программных средств собраны в табл. 2.
Табл. 2. Экспериментальные системы.

Алгоритм разделения

Чтобы оценить качество разделения, обеспечиваемого нашим алгоритмом, мы экспериментировали с различными рабочими нагрузками из искусствено созданных и реальных приложений, описываемых ниже. Мы сравниваем качество разделений по числу получаемых распределенных транзакций. Краткая сводка результатов приведена на рис. 4. Диаграмма в верхней части рисунка позволяет сравнить число распределенных транзакций, получаемое вследствие применения алгоритма разделения графов в системе Schism, с соответствующим показателем 1) наилучшего разделения вручную, какое только нам удалось придумать (manual), 2) репликации всех таблиц replication) и 3) хэш-разделения по первичному ключу или идентификаторам кортежей (hashing). Таблицы в нижней части рисунка показывают число использованных разделов, долю базы данных, которая была отобрана в "образцы", и рекомендацию схемы валидации Schism.
Ниже мы описываем каждый из девяти экспериментов. Все эксперименты заключались в сборе больших трасс транзакций, разделении этих трасс на обучающую и тестовую выборки и применении методов взятия образцов и сокращения рабочей нагрузки, описанных в разд. 5. Наборы данных подробно обсуждаются в Приложении D.

Аннотация

Мы представляем Schism – новый, основанный на учете рабочей нагрузки подход к разделению и репликации, который разработан с целью повышения уровня масштабирования распределенных систем баз данных с архитектурой без совместно используемых ресурсов (shared-nothing). Поскольку в среде OLTP распределенные транзакции являются дорогостоящими (что мы демонстрируем с использованием ряда экспериментов), механизм разделения (partitioner) пытается минимизировать число распределенных транзакций, производя при этом сбалансированные разделы. Schism состоит из двух фаз: i) управляемая нагрузкой, основанная на использовании графов фаза репликации/разделения и ii) фаза толкования и валидации. На первой фазе создается граф, вершины которого соответствуют кортежам (или группам кортежей), а дуги соединяют вершины-кортежи, к которым обращается одна и та же транзакция. После этого механизм разделения расщепляет этот граф на k сбалансированных разделов, минимизируя число транзакций, обращающихся к данным из разных разделов (многораздельных транзакций). На второй фазе используются методы машинного обучения (machine learning) для нахождения основанного на предикатах толкования стратегии разделения (т.е. набора предикатов диапазонов значений (range predicate), представляющего такую же схему репликации/разделения, что и выданная механизмом разделения).
Достоинствами Schism являются: i) независимость от вида схемы базы данных; ii) эффективность при работе со связями типа n-к-n, типичными в базах данных социальных сетей; iii) унифицированный и мелкоструктурный (fine-grained) подход к репликации и разделению. Мы реализовали прототип Schism и протестировали его с использованием широкого спектра тестовых наборов, от классических рабочих нагрузок OLTP (например, TPC-C и TPC-E) до более сложных сценариев, полученных с Web-сайтов социальных сетей (например, Epinions.com). В последнем случае в схеме базы данных имеется несколько связей n-к-n, которые, как известно, трудно поддаются разделению. Schism обеспечивает производительность, существенно превосходящую ту, которую можно достичь с использованием простых схем разделения, и в некоторых случаях обеспечивает более совершенные результаты, чем при использовании наилучших известных методов ручного разделения, что позволяет снизить стоимость выполнения распределенных транзакций на 30%.

B. Гиперграфы

Вместо того, чтобы представлять транзакции в виде набора дуг, соединяющих вершины, мы использовали их представление в виде одной гипердуги, соединяющей все вершины, к которым обращается данная транзакция. Это представление является несколько более естественным, поскольку число разрезов гипердуг в точности совпадает с числом распределенных транзакций. Кроме того, мы расчитывали, что разделение гиперграфа позволит обеспечить более высокое качество, основываясь на результатах, которые описаны в литературе о разделении графов , и предыдущих статьях сообщества баз данных, которые посвящены использованию такого подхода . Однако после выполнения активного тестирования с применением наиболее популярных библиотек разделения гиперграфов (hMETIS и Zoltan-PHG) мы установили, что разделение графов выполняется быстрее и обеспечивает лучшие результаты. Мы полагаем, что это объясняется более широким использованием и изучением методов разделения графов, в результате чего соответствующие инструментальные средства обладают большей зрелостью.
В результате нам пришлось аппроксимировать гиперграф набором дуг в графе. Известно, что это трудная задача. После пропуска многочисленных тестов мы решили использовать для представления транзакций полные подграфы (clique), а для репликации – звездообразное представление (меньше дуг для кортежей, доступ к которым происходит очень часто). Эта комбинация представлений обеспечила получение хороших результатов и приемлемые размеры графов.

Благодарности

Эта работа частично поддерживалась Quanta Computer как часть проекта T-Party.

C.1 Поисковые таблицы

Как описывалось в подразделе 4.2, поисковые таблицы оказываются полезными в тех случаях, когда в данных имеется некоторая локальность, не очевидная по схеме базы данных. Чтобы получить наилучшее разделение для данных этого типа, необходимо поддерживать информацию о разделении для каждого отдельного кортежа. На логическом уровне это представляет собой отображение между кортежами и идентификаторами разделов. Поддерживать это отображение для всех атрибутов кортежей невозможно. Однако во многих приложениях доступ к данным, в основном, производится по первичному ключу, значения которого обычно образуют плотное множество целых чисел, генерируемых системой. Для приложений такого типа хранение и поддержка поисковых таблиц могут быть очень эффективными. К этой информации можно относиться как к "мягкому состоянию" ("soft state"), потому что в случае отказа системы ее легко можно восстановить путем сканирования базы данных.
На физическом уровне мы экспериментировали с тремя разными реализациями поисковых таблиц: традиционные индексы, битовые массивы и фильтры Блюма. Наиболее общим решением являются традиционные индексы, которые можно использоваться для любого(ых) типа(ов) данных столбца(ов) разделения. Кроме того, эти структуры данных эффективны и хорошо изучены. Однако для поддержки индексов требуется больше всего ресурсов. Битовые массивы пригодны для поддержки (почти) плотного множества целочисленных ключей, если каждому ключу сопоставить смещение в массиве идентификаторов разделов. Это очень компактный и быстрый способ хранения поисковых таблиц, естественным образом пригодный для многих приложений, в которых используются автоинкрементные целые первичные ключи. При наличии нескольких гигабайт основной памяти, в массиве можно сохранять идентификаторы разделов для миллиардов кортежей.
Наконец, мы произвели прадварительное тестирование с использованием фильтров Блюма, которые обеспечивают более компактное представление, но иногда срабатывают ложным образом (false positive). Эти ложные срабатывания приводят к снижению производительности, но не влияют на корректность. При маршрутизации запросов ложное срабатывание означает, что некоторый раздел вовлекается в выполнение некоторого оператора, хотя это не требуется. Реальная экономия памяти зависит от многих параметров, таких как число кортежей, число разделов и интенсивность ложных срабатываний.
В настоящее время мы изучаем возможности (i) наилучшей реализации поисковых таблиц для распределенных баз данных, (ii) определения того, когда лучше использовать поисковые таблицы, а не традиционные хэш-разделение и разделение по диапозонам значений, а также (iii) выбора наилучшей реализации для каждого сценария.

C.2 Маршрутизация запросов и операций обновления

Еще одной важной проблемой, которую требуется решить внутри слоя промежуточного программного обеспечения, является выбор способа маршрутизации запроса или операции обновления, при котором гарантируется корректное выполнение и минимизируется число участников, вовлекаемых в выполнение оператора.
Наша система предоставляет приложениям для задания операторов интерфейс JDBC. Получив такой оператор, наш компонент маршрутизации выполняет следующие шаги: i) разбирает этот оператор, ii) извлекает из раздела WHERE предикаты над атрибутами таблицы, iii) сопоставляет атрибуты со схемой разделения для получения списка целевых разделов. Затем координатор распределенных транзакций управляет выполнением оператора на нескольких машинах.
Операторы, обращающиеся к кортежам с использованием атрибута(ов) разделения, посылаются только в раздел(ы), в котором(ых) хранятся требуемые кортежи. Операторы, обращающиеся к единственной таблице с использованием других атрибутов, обрабатываются путем их широковещательной рассылки во все разделы соответствующей таблицы с последующим объединением частичных результатов. Более сложные запросы, обращающиеся к нескольким таблицам с использованием атрибутов, которые не являются атрибутами разделения, в настоящее время не обрабатываются, поскольку для этого требуется пересылка промежуточных результатов для вычисления соединений.
Разделение работает наиболее эффективно, если в разделе WHERE большинства запросов используются атрибуты разделения. Именно поэтому на фазе толкования Schism пытается использовать атрибуты, наиболее часто используемые в разделах WHERE.

C. Разделение и маршрутизация

В этом приложении мы обсудим две проблемы маршрутизации запросов: i) как можно работать с поисковыми таблицами, и ii) как следует использовать схемы разделения (поисковые таблицы, предикаты диапазонов, хэширование) для маршрутизации запросов и операций обновления на правильные машины.

Цена распределенности

Прежде, чем описывать детали своего подхода к разделению, мы представим серию экспериментов, которые мы выполнили для измерения стоимости распределенных транзакций. Эти результаты показывают, что распределенные транзакции являются дорогостоящими, и что нахождение правильного разделения критически важно для достижения хорошей производительности распределенной системы баз данных OLTP.
В распределенной системе баз данных без общих ресурсов транзакции, обращающиеся к данным только одного узла, выполняются без дополнительных накладных расходов. Операторы этой транзакции обрабатываются над одной базой данных, а в завершение выполняются команды фиксации (commit) или аварийного завершения (abort). Однако если операторы распределяются по нескольким узлам, то для обеспечения атомарности и сериализуемости транзакций требуется использование двухфазной фиксации (two-phase commit) или какого-либо аналогичного распределенного протокола согласования. Это приводит к появлению дополнительных сетевых сообщений, снижению пропускной способности, увеличению задержки и потенциальному появлению распределенных тупиковых ситуаций. Поэтому мы хотим избегать распределенных транзакций.
Для количественной оценки влияния распределенных транзакций мы выполнили простой эксперимент с использованием MySQL. Мы создали таблицу simplecount с двумя столбцами целого типа: id и counter. Клиенты в одной транзакции читают две строки, выдавая два запроса вида SELECT * FROM simplecount WHERE id = ?. Каждый запрос возвращает одну строку. Мы исследовали производительность двух стратегий: (i) каждая транзакция выполняется на одном сервере и (ii) каждая транзакция распределяется между несколькими машинами с использованием поддерживаемой MySQL двухфазной фиксации (XA-транзакции) и нашего собственного координатора распределенных транзакций.
Каждый клиент выбирал строки случайным образом в соответствии с одной из этих стратегий и после получения ответа немедленно посылал следующий запрос. Мы тестировали эту рабочую нагрузку на вычислительном комплексе, включавшем до пяти серверов.
См. подробное описание нашей экспериментальной конфигурации в Приложении A. Мы использовали 150 одновременно функционирующих клиентов, чего было достаточно для насыщения процессоров всех пяти серверов. Таблица simplecount содержала 150000 строк (по тысяче на каждого клиента), так что база данных полностью помещалась в буферных пулах наших серверов (128 мегабайт). Это имитировало рабочую нагрузку над базой данных, располагаемой в основной памяти, что не является редкой ситуацией для OLTP.

Рис. 1. Пропускная способность распределенных транзакций.

В идеальном мире локальные и распределенные транзакции в этом тесте достигали бы схожей производительности, поскольку они обращаются к одному и тому же числу записей с использованием одного и того же числа операторов. Однако результаты эксперимента, показанные на рис. 1, показывают, что распределенные транзакции оказывают большое влияние на пропускную способность, снижая ее почти в два раза. Поскольку фиксация распределенной транзакции задевает всех ее участников, возрастает и задержка. В этом эксперименте для распределенных транзакций средняя величина задержки примерно в два раза больше, чем у одноузловых транзакций. Например, при наличии пяти серверов задержка одноузловой транзакции составляет 3,5 микросекунды, а распределенной транзакции – 6,7 микросекунд. Мы выполняли аналогичные эксперименты с другими сценариями, включая обновляющие транзакции и транзакции, обращающиеся к большему числу кортежей, и результаты были аналогичными.

Реальные приложения OLTP намного сложнее этого простого эксперимента, потенциально включая: (i) конкуренцию транзакций за одновременный доступ с блокировкой к одним и тем же строкам – как мы увидим в TPC-C подразделе 6.3, (ii) распределенные тупиковые ситуации и (iii) сложные операторы, для выполнения которых требуются данные с нескольких серверов, например, распределенные соединения. Все это еще больше снижает пропускную способность системы при выполнении распределенных транзакций.С другой стороны, при выполнении более дорогостоящих транзакций меньше ощущается влияние распределенности, поскольку большой объем работы, выполняемой локально, затмевает стоимость обработки дополнительных сообщений двухфазной фиксации.

Schism разрабатывается в расчете на приложения OLTP и Web-приложения. Для таких рабочих нагрузок вывод состоит в том, что минимизация числа распределенных транзакций при балансировке нагрузки между узлами способствует значительному повышению транзакционной пропускной способности.

D.1 Yahoo! Cloud Serving Benchmark

Yahoo! Cloud Serving Benchmark (YCSB) – это коллекция простых тестовых микронаборов, разработанных с целью представления приложений управления данными, являющихся простыми, но требующими высокого уровня масштабируемости . Этот тестовый набор ориентирован на оценку распределенных систем хранения данных "ключ-значение", подобных тем, которые созданы компаниями Yahoo, Google и в различных проектах категории open source. В нашей работе этот стандартизованный и простой тестовый набор использовался для получения представления о некоторых возможностях нашего инструментального средства, например, о его возможности прибегать к использованию более дешевых стратегий разделения в случае совпадения ожидаемых результатов.
Из пяти основных рабочих нагрузок YCSB мы выбрали рабочие нагрузки A и E. Рабочая нагрузка является смесью 50/50 операций чтения и записи одного кортежа, выбираемого случайным образом по распределению Зипфа. Если игнорировать потенциальные трудности достижения хорошей производильности при работе с данными масштаба Internet, для разделения эта проблема является очень простой. На самом деле, за исключением случая полной репликации, любая стратегия разделения обладает нулевой стоимостью, поскольку транзакции обращаются только к одному кортежу. Поэтому целью пропуска этого теста являлась демонстрация способности нашей системы выбирать более дешевую стратегию разделения (например, хэш-разделения), если она существует.
Рабочая нагрузка E является смесью 95/5 операций чтения и записи, причем при чтении производится короткое сканирование (длина сканирования выбирается равномерным случайным образом в диапазоне от 1 до 100 кортежей), а запись затрагивает один кортеж. Начальная точка сканирования и кортеж для записи выбирались случайным образом по распределению Зипфа. Эта рабочая нагрузка показывает непригодность схемы хэш-разделения для запросов по диапазонам значений, а также то, что наше средство может автоматически выбирать точки расщепления по предикатам диапазонов, что приводит к близкой к оптимальной стратегии разделения.

D.2 TPC-C

Тестовый набор TPC-C разработан для имитации рабочей нагрузки OLTP системы обработки заказов. В своей реализации мы не следовали строго требованиям спецификации TPC-C. В частности, для генерации высокой пропускной способности при малых размерах наборов данных в симуляторах клиентов не используется указанное в спецификации TPC-C "время на размышление", и следующая транзакция запрашивается сразу после получения ответа от предыдущей транзакции. Поэтому наши результаты, представленные в подразделе 6.3, не предназначаются для сравнения с другими системами, а лишь показывают относительную производительность конфигураций, в которых производилось тестирование.
Схема базы данных TPC-C включает 9 таблиц с 92 столбцами (в общей сложности), 8 первичными ключами и 9 внешними ключами. В рабочую нагрузку TPC-C входят транзакции пяти типов.

D.3 TPC-D

Тестовый набор TPC-D – это тестовый набор OLTP, более сложный, чем TPC-C. Он моделирует брокерскую компанию, которая выполняет сделки от имени клиентов. И в этом случае наша реализация не полностью соответствует спецификации, но мы старались генерировать корректные данные и транзакции. Схема базы данных TPC-D включает 33 таблицы со 188 столбцами (в общей сложности), 33 первичными ключами, 50 внешними ключами и 22 ограничениями целостности. В рабочую нагрузку TPC-C входят транзакции десяти типов.

D.4 Epinions.com

Целью эксперимента с Epinions.com являлось испытание нашей системы на сценарии, который трудно поддается разделению. Выявлялась эффективность системы при обнаружении важных корреляций между данными, которые не видны на уровне схемы или запросов. Наша схема базы данных Epinions.com включает четыре отношения: users, items, reviews и trust. Отношение reviews представляет связи n-к-n между пользователями (users) и товарами (items) (связываются отзывы пользователей и рейтинги товаров). Отношение trust представляет связи n-к-n между парами пользователей, указывая, что они другу другу доверяют. Данные были предоставлены Паоло Масса (Paolo Massa) из группы разработчиков Epinions.com. Поскольку рабочую нагрузку нам не предоставили, мы создали запросы, примерно соответствующие функциональности этого Web-сайта:

Q1:	для заданных пользователя и товара выбрать рейтинги, заданные пользователями, которым он доверяет;
Q2:	выбрать список пользователей, которым доверяет данный пользователь;
Q3:	для заданного товара выбрать взвешенное среднее всех рейтингов;
Q4:	для заданного товара выбрать 10 наиболее популярных отзывов;
Q5:	выдать 10 наиболее популярных отзывов данного пользователя;
Q6:	вставить/изменить профиль пользователя;
Q7:	вставить/изменить метаданные товара;
Q8:	вставить/изменить отзыв;
Q9:	обновить информацию о доверии пары пользователей друг к другу.

Для получения разделения вручную были привлечены студенты, действовавшие в качестве администраторов базы данных. Найти хорошее разделение оказалось непросто, поскольку запросы опирались на связи n-к-n с конфликтующими требованиями к группировке таблиц и кортежей. Например, при выполнении запроса Q1 будут производиться обращения к одному разделу, если данные разделены по товарам, а рейтинги и доверительные отношения сохраняются вместе с товарами. В то же время при выполнении запроса Q2 будут производиться обращения к одному разделу, если данные разделены по пользователями, и доверительные отношения сохраняются вместе с пользователями. Предложенное студентами решение заключалось в оптимизации запросов, наиболее часто встречавшихся в рабочей нагрузке (Q1 и Q4), путем разделения таблиц items и reviews на основе одной и той же хэш-функции, и репликации таблиц users и trust в каждом узле.

D.5 Random

Заключительный тестовый набор разрабатывался с целью сделать "невозможным" разделение рабочей нагрузки. В каждом операторе обновлялась пара кортежей, выбираемых равномерным случайным образом из всей таблицы. Как и в примере подраздела D.1, цель состояла в том, чтобы показать, что при наличии одинаково пригодных схем разделения система выбирает самую дешевую и надежную стратегию – в данном случае, хэш-разделение.

D. Наборы данных

В этом разделе приводятся дополнительные подробности относительно тестовых наборов, упоминавшихся в разд. 6.

Epinions.com, десять разделов

– тот же набор данных, что и в предыдущем эксперименте, но число разделов увеличено до 10. Результаты Schism (6% распределенных транзакций) лучше, чем у хэш-разделения (75,7%), у полной репликации (8%) и у разделения вручную (6,5%).

Epinions.com, два раздела

– набор данных основан на данных соответствующего Web-сайта социальной сети . Искусственным образом был сгенерирован набор из девяти транзакций, моделирующий наиболее популярные функциональные возможности Web-сайта – подробности см. в Приложении D. Чтобы получить возможность сравнить свои результатами с результатами разделения вручную, мы попросили заняться этим двух студентов магистратуры MIT. Они обнаружили, что наличие в схеме базы данных нескольких связей n-к-n (в которых фиксируются пользовательские рейтинги товаров и доверительные отношения между пользователями), а также существование нескольких паттернов доступа к данным в транзакциях делают эту задачу достаточно сложной. После нескольких часов анализа базы данных и рабочей нагрузки они нашли смешанную стратегию разделения и репликации, приводящую к 6% распределенных транзакций.

При наличии той же информации система Schism получила схему разделения на основе поисковой таблицы, обеспечивающую всего 4,5% распределенных транзакций. Это оказалось возможно, потому что система смогла обследовать социальный граф на уровне кортежей и обнаружила кластеры пользователей и товаров, к которым часто происходят совместные обращения, а обращения к кортежам за пределами этих кластеров редки. Поскольку в этой рабочей нагрузке в основном содержатся только читающие транзакции, кортежи, не присутствующие в исходной поисковой таблице (т.е. не затронутые транзакциями из обучающей выборки), реплицировались во всех разделах. Хэш-разделение и разделение по диапазонам значений привели к получению значительно худших результатов и не были выбраны Schism на фазе окончательной валидации.

Фаза толкования

На фазе толкования система пытается найти компактную модель, в которой фиксируется отображение (tuple, partition), полученное на фазе разделения. Для выполнения этой задачи мы используем деревья решений (классификаторы в машинном обучении) поскольку они производят доступные для понимания основанные на правилах результаты, которые можно сразу применять для разделения по предикатам диапазонов. Классификатор на основе дерева решений на входе принимает набор пар (value, label), а в качестве результата производит дерево предикатов над значениями, ведущими к листовым вершинам с заданными метками. Для непомеченного значения метку можно обнаружить путем спуска по дереву и применения предикатов в каждом узле до тех пор, пока не будет достигнут помеченный лист.
В Schism значения – это кортежи базы данных, а метки – разделы, назначенные кортежам алгоритмом разделения графов. Реплицируемые кортежи помечаются специальным идентификатором репликации, обозначающим набор разделов, в котором должен храниться данный кортеж (например, набор разделов {1, 3, 4} можно представить меткой R1).
В случае удачи классификатор обнаруживает простой набор правил, в котором в компактной форме фиксируется суть разделения, полученного алогоритмом разделения графов. Для примера с рис. 2 и 3 классификатор на основе дерева решений выводит следующие правила:
(id = 1 ) → partitions = {0, 1}
(2 ≤ id < 4) → partition = 0
(id ≥ 4) → partition = 1
Не всегда возможно получить толкование разделения, и не всякое толкование полезно. Толкование оказывается полезным только при выполнении следующих условий:

оно основывается на атрибутах, часто используемых в запросах (например, в нашем примере, атрибут id используется в разделе WHERE половины запросов), – это требуется для того, чтобы можно было направлять транзакции в один узел и избегать дорогостоящей широковещательной рассылки;

оно не слишком снижает качество разделения за счет неправильной классифкации кортежей;

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

Для достижения этих целей мы:

ограничиваем дерево решений таким образом, чтобы оно работало на атрибутах, часто используемых в запросах;

измеряем стоимость как число распределенных транзакций и не допускаем толкований, ухудшающих графовое решение и

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

В разд. 5.2 реализация процесса толкования описывается более подробно.

Экспериментальная оценка

В этом разделе мы представим результаты экспериментальной оценки Schism.

Рис. 4. Эффективность разделения баз данных с использованием Schism.

Литература

S. Agrawal, V. Narasayya, and B. Yang. Integrating vertical and horizontal partitioning into automated physical database design. In SIGMOD, 2004.

F. Chang, J. Dean, S. Ghemawat, W. Hsieh, D. Wallach, M. Burrows, T. Chandra, A. Fikes, and R. Gruber. Bigtable: A distributed storage system for structured data. In OSDI, 2006.

B. F. Cooper, R. Ramakrishnan, U. Srivastava, A. Silberstein, P. Bohannon, H.-A. Jacobsen, N. Puz, D. Weaver, and R. Yerneni. PNUTS: Yahoo!’s hosted data serving platform. PVLDB, 1(2), 2008.

B. F. Cooper, A. Silberstein, E. Tam, R. Ramakrishnan, and R. Sears. Benchmarking cloud serving systems with ycsb. SoCC, 2010.

C. Curino, E. Jones, Y. Zhang, E. Wu, and S. Madden. Relationalcloud: The case for a database service. New England Database Summit, 2010.

D. DeWitt and J. Gray. Parallel database systems: the future of high performance database systems. Comm. ACM, 1992.

Перевод на русский язык: Дэвид Девитт, Джим Грей. Параллельные системы баз данных: будущее высоко эффективных систем баз данных, 2009.

R. Freeman. Oracle Database 11g New Features. McGraw-Hill, Inc., New York, NY, USA, 2008.

S. Ghandeharizadeh and D. J. DeWitt. Hybrid-range partitioning strategy: a new declustering strategy for multiprocessor databases machines. In VLDB, 1990.

M. Hall, E. Frank, G. Holmes, B. Pfahringer, P. Reutemann, and I. H. Witten. The weka data mining software: An update. SIGKDD Explorations, 11, 2009.

G. Karypis and V. Kumar. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput., 20(1), 1998.

G. Karypis and V. Kumar. METIS - Family of Multilevel Partitioning Algorithms, 2010.

B. W. Kernighan and S. Lin. An efficient heuristic procedure for partitioning graphs. Bell Systems Technical Journal 49, pages 291–307, 1970.

R. Khandekar, S. Rao, and U. Vazirani. Graph partitioning using single commodity flows. J. ACM, 56(4):1–15, 2009.

M. Koyutürk and C. Aykanat. Iterative-improvement-based declustering heuristics for multi-disk databases.
Journal of Information Systems, 30(1):47–70, 2005.

P. Massa and P. Avesani. Controversial users demand local trust metrics: an experimental study on epinions.com community. In AAAI’05, 2005.

J. M. Pujol, G. Siganos, V. Erramilli, and P. Rodriguez. Scaling online social networks without pains. NetDB, 2009.

J. R. Quinlan. C4.5: Programs for machine learning. Morgan Kaufmann Series in Machine Learning, 1993.

J. Rao, C. Zhang, N. Megiddo, and G. Lohman. Automating physical database design in a parallel database. In SIGMOD, 2002.

D. ren Liu and S. Shekhar. Partitioning similarity graphs: A framework for declustering problems. ISJ, 21, 1996.

N. Selvakkumaran and G. Karypis. Multi-objective hypergraph partitioning algorithms for cut and maximum subdomain degree minimization. In ICCAD, 2003.

M. Stonebraker, S. Madden, D. Abadi, S. Harizopoulos, N. Hachem, and P. Helland. The end of an architectural era: (it’s time for a complete rewrite). In VLDB, 2007.

Перевод на русский язык: Майкл Стоунбрейкер, Сэмюэль Мэдден, Дэниэль Абади, Ставрос Харизопулос, Набил Хачем, Пат Хеллэнд. Конец архитектурной эпохи, или Наступило время полностью переписывать системы управления данными, 2007.

M. M. Tsangaris and J. F. Naughton. A stochastic approach for clustering in object bases. SIGMOD Rec., 20(2), 1991.

D. C. Zilio. Physical database design decision algorithms and concurrent reorganization for parallel database systems. In PhD thesis, 1998.

Масштабируемость и устойчивость

Чтобы продемонстрировать масштабируемость своего подхода, мы исследовали влияние на производительность системы (i) увеличения числа разделов и (ii) роста размера и сложности базы данных.
Табл. 1. Размеры графов.

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

Рис. 5. Масштабируемость реализации разделения графов METIS при росте числа разделов и размеров графа.
На рис. 5 показано время работы последовательной реализации алгоритма разделения графов kmetis при возрастании числа разделов (детали экспериментальной установки см. в Приложении A). Стоимость разделения немного повышается при возрастании числа разделов. Рост размера графа оказывает гораздо более сильное воздействие на время выполнения (оно увеличивается почти линейно в зависимости от роста числа дуг), что оправдывает наши усилия на сокращение размеров графов на основе эвристик, представленных в подразделе 5.1.
Наиболее важной эвристикой для сокращения размеров графов является взятие образцов (sampling). Трудно точно сказать, до какого уровня можно довести взятие образцов при построении графа, чтобы с его помощью все еще можно было получать хорошую схему разделения базы данных. Однако наши эксперименты свидетельствуют о том, что Schism производит хорошие результаты даже при работе с небольшим образцом базы данных. Например, для TPC-C с двумя складами образца, состоящего из одного процента вершин и дуг полного графа, нам хватило для того, чтобы произвести такой же результат, что и при разделении вручную. Качественный анализ наших экспериментов показывает, что минимально требуемый размер графа возрастает по мере роста сложности рабочей нагрузки, размера базы данных и числа разделов.
Интуитивно ясно, что для более сложной рабочей нагрузки требуется тщательно моделировать большее число транзакций (и тем самым дуг). Для базы данных большего размера в графе требуется больше вершин (кортежей). Требуется и больше дуг (т.е. больше транзакций), чтобы в графе правильно отражалось то, как производится доступ к данным. Наконец, чем больше разделов, тем более плотным должен быть граф (больше дуг). К сожалению, для формализации всего этого в виде количественной модели требуется более полный набор примеров, и такая работа находится за рамками данной статьи. Простая стратегия выбора степени сэмплинга состоит в том, чтобы пропускать нашу систему над образцами увеличивающегося размера до тех пор, пока качество разделения не перестанет повышаться. В наших простых примерах эта стратегия привела к хорошим результатам.

Рис. 6. Масштабируемость пропускной способности TPC-C.

Миграция данных и маршрутизация запросов

Осталось рассмотреть еще два аспекта реализации. Первый состоит в том, каким образом мы перемещаем данные из одного раздела в другой. Для этого в Schism генерируются SQL-скрипты миграции данных. Текущая версия системы разработана с целью разбиения на разделы одной базы данных. Мы расширяем эту возможность для решения более общей проблемы динамического переразделения данных. В качестве альтернативы выходные данные нашего инструментального средства могут подаваться на вход СУБД, поддерживающих разделение данных (например, DB2 или Oracle), которые могут производить перемещение данных.
Второй важный аспект – это то, каким образом репликация и разделение, обеспечиваемые Schism, используются во время выполнения для маршрутизации запросов. Мы разработали маршрутизатор и координатор распределенных транзакций, которые обеспечивают следование стратегии репликации и разделения . Поддерживаются хэш-разделение, разделение на основе предикатов и поисковые таблицы. Маршрутизатор является компонентом промежуточного программного обеспечения, разбирающим SQL-операторы и определяющим, какие разделы требуются для их выполнения. Для запросов только по чтению над реплицированными кортежами Schism пытается выбрать реплики в разделе, к которому данная транзакция уже обращалась. Эта стратегия позволяет сократить число распределенных транзакций. Другие подробности относительно маршрутизации см. в Приложении C.

Обеспечение масштабируемости

Практическое инструментальное средство разделения должно обладать способностью к обработке очень больших баз данных. С ростом размера базы данных и числа кортежей, к которым обращается каждая транзакция, растет и графовое представление. Чем больше разных транзакций содержится в рабочей нагрузке, тем больших размеров трасса рабочей нагрузки требуется для фиксации типичного поведения. С ростом числа разделов требуется обнаруживать больше разрезов в графе. Эти факторы могли бы ограничить размеры баз данных, с обработкой которых справляется наша система.
Как мы покажем в разд. 6, средства разбиения графов хорошо масштабируются по отношению к числу разделов, но с ростом размера графа время их работы существенно возрастает. Поэтому мы сосредоточили усилия на уменьшении размеров графов. Интуитивно кажется, что это поможет уменьшить время работы алгоритма разделения, но ухудшит качество результата, поскольку входной граф меньшего размера содержит меньше информации. Однако мы разработали ряд эвристик, которые позволяют сократить размер графа с умеренным воздействием на качество разделения. Более точно, мы реализовали следующие эвристики:

Взятие образцов на уровне транзакций (transaction-level sampling), что позволяет ограничить объем рабочей нагрузки, представляемой в графе, т.е. уменьшить число дуг.

Взятие образцов на уровне кортежей (tuple-level sampling), что позволяет сократить число кортежей (узлов), представляемых в графе.

Отбрасывание "ковровых" запросов (blanket statement filtering), что позволяет не учитывать редко встречающиеся запросы, приводящие к сканированию больших частей таблицы. Эта эвристика оправдывается тем, что (i) наличие таких запросов приводит к образованию в графе многих дуг, несущих мало информации, и (ii) выполнение подобных запросов эффективно распаллеливается по разделам, поскольку накладные расходы распределенных транзакций менее значительны, чем расходы на выполнение частей запроса в разных узлах.

Фильтрация по релевантности (relevance filtering), когда удаляются кортежи, к которым обращения производятся очень редко (предельным случаем являются кортежи, к которым в рассматриваемой рабочей нагрузке вообще отсутствуют обращения).
Соответствующие вершины графа мало информативны.

Звездообразная репликация (star-shaped replication), когда вершины-реплики связываются в звездообразную конфигурацию, а не в полный подграф (clique), что ограничивает число дуг.

Склеивание кортежей (tuple-coalescing), что позволяет представлять одной вершиной графа группу кортежей, к которым доступ всегда производится ко всем сразу. Это не вызывает потери информации и в некоторых случаях приводит к существенному сокращению размера графа.

Эти эвристики обеспечили эффективное сокращение размеров графов для наших тестовых наборов, сохранив при этом высокое качество результатов. Например, в подразделе 6.2 мы показываем, что (при наличии нескольких тысяч транзакций) в покрытии графа, включающем всего 0,5% от числа кортежей базы данных, остается достаточно информации, чтобы получить разделение, качество которого сопоставимо с наилучшим разделением базы данных, выполненным вручную.

Общие сведения

На входе наша система получает базу данных, некоторое представление рабочей нагрузки (например, трассу SQL) и число требуемых разделов. На выходе получается стратегия разделения и репликации, балансирующая размеры разделов и минимизирующая общие ожидаемые расходы на выполнение рабочей нагрузки. Как мы увидим в следующем разделе, для рабочих нагрузок OLTP ожидаемые расходы прямо связаны с числом распределенных транзакций в рабочей нагрузке. Основной подход состоит из следующих пяти шагов.

Окончательная валидация

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

Оптимизация и реализация

В этом разделе мы представим некоторые проблемы и проектные решения, с которыми нам пришлось встретиться при разработке Schism.

От переводчика: как хорошо разделить транзакционные данные?

Известно, что производительность параллельных систем баз данных, основанных на архитектуре sharing-nothing (без использования общих ресурсов между узлами), критически зависит от качества разделения данных между разными узлами. В аналитических параллельных СУБД критериями разделения являются балансировка нагрузки между узлами и оптимизация выполнения наиболее важных операций соединения.
А как разделять данные в транзакционных параллельных базах данных? В данном случае транзакции обычно короткие и включают смесь простых операций выборки и обновления данных. И в качестве критерия разделения авторы статьи выбирают минимизацию числа транзакций, затрагивающих данные, которые хранятся в разных узлах системы, т.е. являющихся распределенными. Авторы убедительно показывают, что накладные расходы на фиксацию распределенных транзакций значительно увеличивают время их выполнения (и тем больше, чем короче и проще транзакции).
В описываемом подходе полагается известной рабочая нагрузка транзакционной системы баз данных. Опираясь на знание рабочей нагрузки и традиционных характеристик используемой базы данных, авторы находят схему разделения (на основе графового представления рабочей нагрузки и базы данных), действительно минимизирующего число распределенных транзакций. Более того, по этой схеме строится набор таких условий вхождения атрибутов таблиц в диапазоны значения, что разделение базы данных на основе этих условий хорошо аппроксимирует схему, полученную путем разделения графа.
Хотя работа ориентирована на базы данных, хранящиеся в дисковой памяти, мне кажется, что она будет особенно полезна для транзакционных параллельных СУБД типа H-Store, в которых все разделы базы данных сохраняются в основной памяти узлов. Возможно, в этом случае придется несколько пересмотреть критерии репликации, поскольку в системах типа H-Store репликация требуется не только для повышения пропускной способности, но и для обеспечения высокого уровня доступности.
Сергей Кузнецов

Получение трасс

Для создания графового представления для каждой транзакции нам требуется получить наборы кортежей, к которым она обращается. Мы разработали инструментальное средство, которое применяется к некоторому журналу операторов SQL (например, к general log MySQL) и позволяет получить множества чтения и записи транзакций. Прежде всего, операторы SQL, содержащиеся в трассе, переписываются в операторы SELECT, извлекающие идентификаторы (т.е. первичные ключи) всех кортежей, к котором происходит обращение. Эти запросы выполняются, и производится список пар (tuple id, transaction), используемый для построения графа. Этот механизм может использоваться либо в режиме онлайн, когда идентификаторы кортежей извлекаются сразу после выполнения исходного оператора, либо в режиме офлайн. Извлечение идентификаторов кортежей намного позже выполнения исходных операторов все равно приводит к порождению хороших стратегий разделения наших экспериментальных данных, из чего следует, что наш подход не слишком чувствителен к тому, какие в точности кортежи используются. Мы полагаем, что за счет комбинирования этого свойства устойчивости к устаревшим данным со взятием образцов можно извлекать наборы чтения и записи в производственных системах с незначительным воздействием на их производительность.

Представление графов

Мы описываем свое представление графов с использованием простого примера. Хотя в этом примере применяется всего одна таблица, наш подход работает с любой схемой и не зависит от сложности операторов SQL, присутствующих в рабочей нагрузке. Предположим, что имеются банковская база данных, состоящая из одной таблицы account с пятью кортежами, и рабочая нагрузка из четырех транзакций, как показано на рис. 2. Каждому кортежу соответствует вершина графа; дуги связывают кортежи, используемые в одной и той же транзакции. Вес дуги – это число транзакций, обращающихся к соответствующей паре кортежей. На рис. 2 веса дуг не показаны, поскольку к каждой паре кортежей обращается не более чем одна транзакция.

Рис. 3. Граф с репликацией.
На рис. 3 показано расширение основного представления графов, отражающее возможность репликации на уровне кортежей. Репликация представляется путем "развертывания" вершины, представляющей некоторый кортеж, в звездообразную конфигурацию из n+1 вершин, где n – число транзакций, обращающихся к соответствующему кортежу.
В качестве примера рассмотрим кортеж (1, carlo, 80k) с рис. 2. К этому кортежу обращаются три транзакции, и поэтому на рис. 3 он представляется четырьмя вершинами. Веса дуг репликации, соединяющих каждую реплику с центральным узлом, представляют стоимость репликации данного кортежа. Эта стоимость определяется как число транзакций в рабочей нагрузке, обновляющих данный кортеж (для кортежа, используемого в примере, их две). При репликции кортежа каждая операция чтения может выполняться локально, но каждое обновление становится распределенной транзакцией. Эта графовая структура позволяет алгоритму разбиения соблюдать баланс между стоимостью репликации и выгодой от ее использования.
Мы экспериментировали с другими представлениями графов, включая гиперграфы, но обнаружили, что для наших целей они недостаточно пригодны (дальнейшие подробности относительно нашего графового представления см. в Приложении B).
Стратегия разделения графов, обсуждаемая в следующем подразделе, эвристическим образом минимизирует стоимость разрезания графа, балансируя при этом веса каждого раздела (более точно, соблюдая ограничение допустимого перекоса). Вес раздела определяется как сумма весов вершин, отнесенных к этому разделу. Следовательно, путем назначения вершинам разных весов мы можем по-разному балансировать разделы. Мы экспериментировали с двумя важными показателями разбиения баз данных: (i) балансировка по размеру базы данных, когда вес вершины равен размеру соответствующего кортежа в байтах, и (ii) балансировка по рабочей нагрузке, когда вес вершины равен числу обращений к соответствующему кортежу.

Предварительная обработка данных:

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

Random

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

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

Разделение графа:

Алгоритм разделения графа используется для получения сбаланированного разделения с минимальными разрывами (balanced minimum-cut partitioning) графа на k разделов. Каждый кортеж приписывается к одному разделу (т.е. это разделение на уровне кортежей (per-tuple partitioning), и каждый раздел приписывается к одному физическому узлу.

Разделение графов

Представление графов в Schism характеризует как базу данных, так и операции над ней. При разделении граф расщепляется на k неперекрывающихся разделов таким образом, что общая стоимость разрезания дуг минимизируется (т.е. находится разделение с минимальными разрывами (mininimum-cut)). При этом веса разделов удерживаются в пределах допустимого отклонения от совершенной балансировки (коэффициент отклонения является параметром системы). Эта операция над графом приближенно минимизирует число распределенных транзакций, распределяя нагрузку или данные поровну между узлами.
Наше единообразное представление разделения и репликации позволяет алгоритму разделения графов для каждого кортежа принимать решение о том, следует ли реплицировать его в нескольких разделах (как, например, кортеж 1 на рис. 3) и нести затраты на выполнение распределенных оперцаций обновления, или же лучше хранить его в одном разделе (как, например, кортеж 4 на рис. 3) и нести расходы на выполнение распределенных транзакций. Если все реплики некоторого кортежа оказываются в одном разделе, этот кортеж не реплицируется. В противном случае принимается решение о его репликации. Естественно, алгоритм разделения не принимает решения о репликации кортежей, которые часто обновляются, поскольку разрывы дуг, соединяющих вершины-кортежи с вершинами репликами, обладают высокой стоимостью, соответствующей стоимости распределенных обновлений. И наоборот, велика вероятность репликации редко обновляемых кортежей, если это приводит к снижению стоимости разрыва дуг транзакций. В подразделе 4.3 мы обсуждаем, каким образом подход к принятию решений на уровне кортежей можно обобщить для принятия решений при разделении на уровне таблиц или по диапазонам значений.
Известно, что разделение графа на k частей при наличии ограничений – это NP-полная проблема. Однако, поскольку подобные разделения часто требуются в области автоматизиции проектирования сверхбольших интегральных схем, в последние сорок лет в этом направлении было выполнено много исследований и разработок [, , ], в результате которых были получены сложные эвристические правила и созданы хорошо оптимизированные свободно доступные библиотеки программного обеспечения.
В большинстве алгоритмов разделения графов используются методы многоуровневого огрубления (multilevel coarsening) и обеспечиваются параллельные реализации в распределенной среде, позволяющие обрабатывать исключительно крупные графы (сотни миллионов дуг). В Schism для разделения графов мы используем METIS .

Результатом фазы разделения графа является мелкозернистое отображение отдельных вершин (кортежей) на множество меток разделов. По причине наличия репликации один кортеж может быть приписан к нескольким разделам.

Мелкозернистое разделение. Одним из способов использования результатов фазы разделения является сохранение этих результатов в поисковой таблице (lookup table) типа той, которая показана в левой части рис. 3.

В распространенном случае доступа по ключам к кортежам (т.е. когда разделы WHERE запросов содержат предикаты сравнения на равенство или вхождения в диапазон значений идентификаторов кортежей) эти таблицы можно напрямую использовать для направления запросов в соответствующий раздел. В нашем прототипе для этого используется компонент маршрутизации промежуточного программного обеспечения, который разбирает запросы и сравнивает предикаты их разделов WHERE с содержимым поисковых таблиц. На физическом уровне поисковые таблицы могут сохраняться в виде индексов, битовых массивов или фильтров Блюма (Bloom-filter) – детали организации поисковых таблиц см. в Приложении C. При наличии плотного множества идентификаторов кортежей и числа кортежей в пределах 256 в узле-координаторе с 16 гигайбатами основной памяти можно сохранять поисковую таблицу, тратя по одному байту на каждый идентификатор кортежа и сохраняя информацию от разделении более 15 миллиардов кортежей (других потребностей по использованию основной памяти у координатора нет). Этого более чем достаточно для подавляющего большинства приложений OLTP. Кроме того, при исчерпании основной памяти такие таблицы можно хранить распределенным образом в основной памяти на разных машинах или в виде индекса в дисковой памяти.

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

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

Разделение и репликация

Установив стоимость распределенных транзакций, представим свой подход к разделению и репликации, направленный на то, чтобы транзакции обращались к данным только одного раздела.

Рис. 2. Представление графа.

Реализация толкования

Для реализации фазы толкования, описанной в подразделах 4.3 и 4.4, мы использовали свободно доступную библиотеку машинного обучения Weka . Процесс толкования состоит из следующих шагов:

Создание обучающей выборки (training set): Schism извлекает из трассы рабочей нагрузки информацию о запросах и затрагиваемых ими кортежах – для сокращения времени работы используется взятие образцов (sampling) без ухудшения качества результата. Кортежи помечаются метками разделов, произведенных алгоритмом разделения графа. Как описывалось в подразделе 4.3, реплицируемые кортежи помечаются метками виртуальных разделов, соответствующими наборам целевых разделов. Таким образом образуется обучающая выборка, используемая классификатором на основе дерева решений.

Выбор атрибутов: Система разбирает операторы SQL, присутствующие в рабочей нагрузке, и для каждого атрибута фиксирует частоту его вхождений в разделы WHERE. Редко используемые кортежи отбрасываются, поскольку они не годятся для марштрутизации запросов. Например, для таблицы TPC-C stock мы получаем два часто используемых атрибута (s_i_id, s_w_id), представляющие идентификаторы вида товара и склада соответственно. Выбранные атрибуты подаются на вход основанного на учете корреляции компонента Weka отбора признаков (feature selection), который выбирает набор атрибутов, коррелирующих с метками разделов. Для TPC-C на этом шаге отвергается атрибут s_i_id, и для последующей классификации оставляется единственный атрибут s_w_id.

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

Построение классификатора: Мы обучаем классификатор на основе дерева решений с использованием J48 – реализации на языке Java классификатора C4.5 . Атрибутами классификации являются метки разделов, которые мы хотим узнать на основе атрибутов, отобранных на предыдущем шаге. На выходе классификатора получается набор предикатов, аппроксимирующих разделение на уровне кортежей, которое было произведено алгоритмом разделения графов. Чрезмерно близкой подгонки удается избежать за счет перекрестной проверки и управляемого применения эвристики сокращения дерева решений для устранения правил с малой поддержкой.

Например, для базы данных TPC-C с двумя складами, разбитой на два раздела, мы получили для таблицы stock следующие правила:

s_w_id ≤ 1: partition: 1 (pred. error: 1.49%)

s_w_id > 1: partition: 2 (pred. error: 0.86%)

Для таблицы item классификатор произвел правило:

: partition: 0 (pred. error: 24.8%)

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

Общий результат для TPC-C состоит в разделении базы данных по складам и в репликации всей таблицы item. Такую же стратегию предлагали эксперты . Как отмечается в разд. 6, аналогичное разделение находится для TPC-C с большим числом складов и разделов. Хотя для определения разделов в случае TPC-C не требуются несколько атрибутов, в случае надобности классификатор может производить правила соответствующего вида.

Родственные работы

Методы разделения баз данных активно исследовались как для одномашинных серверов (например, ), так и для систем без совместно используемых ресурсов (например, [, ]). В этих подходах обычно используется схема базы данных для получения возможных разделений по диапазонам значений или хэш-разделений, которые затем оцениваются с применением эвристик или оценочных моделей. Обеспечивается ограниченная поддержка рабочих нагрузок OLTP, и обычно отсутствует возможность генерации осмысленных стратегий разделения для схем, содержащих несколько связей n-к-n.
Стохастический подход Цангариса (Tsangaris) и Нотона (Naughton) для кластеризации объектно-ориентированных баз данных опирается на эвристики разделения графов . В нашей же системе, кроме того, интегрируется репликация, и система разрабатывается в расчете на выполнение совсем других требований распределенных баз данных.
В последнее время имеется значительный интерес к "упрощенным" распределенным системам хранения данных, таким как BigTable или PNUTS . В этих системах постоянно выполняется переразделение данных для балансировки объемов данных и рабочей нагрузки между несколькими серверами. Будучи более динамичными, эти методы не имеют дела с транзакциями над несколькими таблицами.
Широко известна сложность проблемы масштабирования приложений социальных сетей из-за сильной взаимосвязанности соответствующих данных. Подход One Hop Replication направлен на масштабируемость таких приложений путем репликации связей, обеспечивая немедленный доступ ко всем элементам данных в пределах "одного скачка" ("one hop") от заданной записи . В этом подходе требуется алгоритм начального разделения данных, и Schism можно было бы использовать вместе с этой системой.
Гибридно-диапазонная стратегия разделения (hybrid-range partitioning strategy, HRPS) – это гибрид хэш-разделения и разделения по диапазонам значений, основанный на анализе запросов. Схема направлена на декластеризацию (параллельное выполнение на нескольких узлах путем распределения данных между ними) долговременных запросов и локализацию мелких запросов с условиями вхождения в диапазон значений. HRPS применима только к однотабличным запросам с условиями вхождения в диапазоны значений одного атрибута, и в этой стратегии репликация не предусматривается.
На противоположном конце спектра по отношению к Schism находятся исследовательские работы по чистой декластеризации и "советчики по разделению" (partitioning advisor), часто включаемые в коммерческие СУБД [, ], которые, главным образом, ориентированы на поддержку рабочих нагрузок OLAP и на оптимизацию расположения данных на дисках в одной системе. В работе Лиу (Liu) и др., как и в нашей работе, используется разделение графов, но для противоположной цели (декластеризация). Кроме того, в работе Лиу и др. не учитывается возможность репликации и не предлагается толкование на основе предикатов.

Schism: управляемый рабочей нагрузкой подход к репликации и разделению баз данных

Карло Курино, Эван Джонс, Янг Жанг и Сэм Мэдден
Перевод: Сергей Кузнецов

Оригинал: Carlo Curino, Evan Jones, Yang Zhang, Sam Madden. Schism: a Workload-Driven Approach to Database Replication and Partitioning. 36th International Conference on Very Large Data Bases, September 13-17, 2010, Singapore. Proceedings of the VLDB Endowment, Vol. 3, No. 1, 2010, pp. 48-57.

Сквозная проверка

Чтобы проверить свой сквозной подход и продемонстрировать, что Schism производит сбалансированные разделы, максимизирующие пропускную способность, мы пропускали тестовый набор, основанный на TPC-C, на кластере из 8 машин (подробное описание конфигурации см. в Приложении A). Мы использовали Schism для разделения базы данных на 1, 2, 4 и 8 разделов. Затем каждому разделу назначался отдельный кластер. Система Schism конфигурировалась в расчете на балансировку нагрузки между разделами, что в случае TPC-C приводит также к образованию разделов с почти одинаковыми размерами данных. Произведенные системой предикаты разделения по диапазонам были такими же, как полученные в описанных ранее экспериментах с TPC-C. Мы использовали две конфигурации. В первой из них 16 складов распределялись по узлам кластера. Это демонстрирует горизонтальное масштабирование одного приложения при добавлении больших аппаратных ресурсов. Во второй конфигурации одновременно с добавлением узлов мы добавляли и склады, так что на каждой машине всегда имелись данные о 16 складах. Это демонстрирует возможность Schism поддерживать рост масштаба приложения при добавлении аппаратуры. Использовалось достаточное число клиентов TPC-C, чтобы можно было насытить пропускную способность TPC-C. Пропускная способность показана на рис. 6.
Результаты показывают, что при наличии 16 складов один сервер способен достичь пропускной способности в 131 транзакцию в секунду. При горизонтальном масштабировании этой конфигурации производительность возрастала почти линейно при росте числа машин до четырех, но при наличии восьми машин достигалось повышение пропускной способности только в 4,7 раза. Это объсняется тем, что реализации TPC-C свойственны конфликты, которые образуют узкое место при хранении в одной машине данных только о двух складах. Невозможно насытить пропускную способность какой-либо одной машины, поскольку почти все транзакции конфликтуют, и это ограничивает максимально возможную пропускную способность. В конфигурации с постоянным хранением в каждой машине данных о шестнадцати складах это узкое место не возникает, и в этом случае демонстрируемая масштабируемость очень близка к линейной (при использовании восьми машин пропускная способность увеличивается в 7,7 раза – коэффициент 0,96).
Этот эксперимент показывает, что Schism может произвести высококачественную схему разделения, позволяющую добиться хорошей масштабируемости. Наши результаты показывают, что при применении к этой рабочей нагрузке хэш-разделения, мы получили бы 99% распределенных транзакций, что привело бы к значительному уменьшению пропускной способности.

Создание графа:

Создается графовое представление базы данных и рабочей нагрузки. Для каждого кортежа в этом графе создается вершина. Дуги представляют использование кортежей внутри транзакций. Две вершины-кортежа соединяются дугой, если к ним производится доступ в одной и той же транзакции. Как отмечается в разд. 4, простое расширение этой модели позволяет нам установить, какие кортежи следует реплицировать.

Толкование разделения:

Система анализирует операторы во входной трассе для формирования списка атрибутов, часто используемых в разделах WHERE для каждой таблицы; этот список мы называем набором часто используемых атрибутов (frequent attribute set). Используется алгоритм деревьев решений для извлечения набора правил, компактным образом представляющих полученное разделение на уровне кортежей. Эти правила представляют собой предикаты на значениях набора часто используемых атрибутов, которые производят отображение кортежей в номера разделов. Мы называем это разделением на основе предикатов диапазонов значений (range-predicate partitioning).

TPC-C 2W со взятием образцов

– этот эксперимент также основывался на TPC-C, но он посвящался проверке устойчивости Schism к взятию образцов: разделялся граф, созданный из 3% кортежей, а в обучающей выборке участвовало всего 20000 транзакций. Обучение дерева решений производилось на образце, включавшем по 250 кортежей из каждой таблицы. Тем не менее, система Schism все равно сумела обнаружить "идеальную" схему разделения/репликацию, описанную выше.

TPC-C 2W

– в этом эксперименте использовалась рабочая нагрузка OLTP с большим числом записей (2 склада, 100000 транзакций в обучающей выборке). Эксперимент показал, что Schism может произвести высококачественное разделение на основе предикатов. Кортежи разделяются на основе идентиифкаторов складов, а таблица item реплицируется – это та же стратегия, что была найдена экспертами .

TPC-C 50W

– в этом эксперименте мы увеличили число складов в TPC-C до 50 (размер базы данных составил 25 миллионов кортежей), чтобы показать, как масштабируется Schism при росте размеров базы данных. Мы также увеличили число разделов до 10. С использованием обучающей выборки из 150 тысяч транзакций и образца, включающего 1% кортежей базы данных, мы получили то же разделение по идентификаторам складов и репликацию таблицы item. В этом эксперименте с 50 складами и 10 разделами разделение Schism и разделение вручную привели к меньшему числу распределенных транзакций, чем в эксперименте с двумя складами и двумя разделами. Это объясняется тем, что некоторые транзакции TPC-C обращаются к нескольким складам (10,7% от общего числа транзакций в рабочей нагрузке). При разделении на два раздела базы данных с двумя складами каждая такая транзакция будет обращаться к нескольким (двум) разделам. Однако в конфигурации с 50 складами и 10 разделами у такой транзакции имеется шанс, что все требуемые ей склады окажутся в одном разделе. Поэтому в такой конфигурации имеется меньшее число многораздельных транзакций. Это была самая крупная рабочая нагрузка из всех, с которыми мы экспериментировали, и общее время работы Schism (построение графа, разделение, толкование и валидация) составило 11 минут 38 секунд.

TPC-E

– рабочая нагрузка OLTP с большим числом операций чтения, основанная на популярном тестовом наборе. Эксперимент выполнялся с 1000 клиентов и обучающей выборкой из 100 тысяч транзакций. Проверялась работа системы при наличии более сложной рабочей нагрузки OLTP. Разделение на основе предикатов диапазонов, полученное системой, оказывается лучше хэш-разделения и полной репликации. Из-за сложности тестового набора (33 таблицы, 188 столбцов, 10 видов транзакций) мы не смогли найти высококачественное разделение вручную, с которым можно было бы сравнить другие результаты. Однако полученный результат в 12,1% распределенных транзакций кажется нам вполне приличным.

YCSB-A

– Cloud Serving Benchmark (YCSB) компании Yahoo! является семейством тестовых наборов, достаточно простых, но отражающих специфику рабочих нагрузок Yahoo! . Рабочая нагрузка A состоит из чтений (50%) и обновлений (50%) одиночных кортежей, случайным образом выбираемых из таблицы со 100000 кортежей с использованием распределения Зипфа. Мы использовали трассы с 10000 запросов. Результаты эксперимента показывают, что Schism может справиться с простыми сценариями, для которых хорошо подходит любое разделение. В частности, мы хотели показать, что на фазе валидации выясняется предпочтительность простого хэш-разделения над более сложными методами разделения с использованием поисковых таблиц или диапазонов значений.

YCSB-E

– рабочая нагрузка из 10000 транзакций, выполняющих либо короткое сканирование с равномерной случайной длиной от 0 до 10 кортежей (95%), либо обновление одного кортежа (5%). Кортежи случайным образом выбирались из таблицы с 100000 кортежей с использованием распределения Зипфа. Из-за сканирований хэш-разделение для этой рабочей нагрузки становится неэффективным. На фазе толкования Schism производит набор предикатов диапазонов значения, которые обеспечиваются настолько же хорошее разделение, что и получаемое вручную (путем тщательного изучения рабочей нагрузки).

систему для мелкоструктурного разделения баз

Мы представили Schism – систему для мелкоструктурного разделения баз данных OLTP. В нашем подходе записи базы данных представляются как вершины графа, а дуги соединяют вершины, к которым обращается одна и та же транзакция. Затем мы используем алгоритм разделения графов для нахождения разделений, минимизирующих число распределенных транзакций. Кроме того, мы предлагаем ряд эвристик, включающих взятие образцов и группировку записей, позволяющих уменьшить сложность графа и оптимизировать производительность. Мы также вводим метод, основанный на деревьях решений, для толкования разделения в терминах компактного набора предикатов, позволяющего установить, к какому разделу относится заданный кортеж.
Наши результаты показывают практичность подхода Schism, обеспечивающего (i) умеренное время работы (в пределах нескольких минут во всех наших тестах), (ii) отличное качество разделения, находя разделения разнообразных баз данных OLTP, в которых только немногие транзакции являются многораздельными (часто автоматическое разделение, выполняемое Schism оказывается не хуже наилучших схем разделения вручную), (iii) простую интеграцию с существующими СУБД за счет поддержки разделения по диапазонам значений в параллельных системах баз данных типа DB2 или за счет использования промежуточного программного обеспечения для управления распределенными транзакциями.

Заключительная валидация:

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

Результирующее разделение можно (i) напрямую использовать в СУБД, поддерживающей разделение данных в распределенной архитектуре без совместно используемых ресурсов, (ii) явным образом закодировать в приложении или (iii) реализовать в маршрутизирующем компоненте промежуточного программного обеспечения типа того, которое мы использовали для тестирования Schism.

Базы данных: Разработка - Управление - Excel