Основным способом масштабирования систем баз
Основным способом масштабирования систем баз данных за счет их выполнения на нескольких физических машинах является горизонтальное разделение (horizontal partitioning). За счет размещения разделов в разных узлах часто оказывается возможным достижение почти линейного возрастания скорости обработки запросов, в особенности, аналитических запросов, при обработке которых в узлах параллельно производится сканирование разделов. Кроме повышения уровня масштабируемости, разделение может способствовать и повышению уровня доступности, поскольку при отказе какого-либо узла некоторые транзакции по-прежнему можно выполнить над данными разделов, оставшихся доступными. Разделение также может повысить и уровень управляемости (manageability) системы баз данных, поскольку внесение апгрейтов в программное и аппаратное обеспечение узла и изменение его конфигурации можно производить для разных узлов по отдельности.
Хотя исследовался ряд схем автматического разделения [, , ], наиболее распространенными подходами являются циклическое разделение (round-robin partitioning) (каждый следующий кортеж направляется в другой раздел), разделение по диапазонам (range partitioning) (кортежи разделяются в соответствии с набором предикатов диапазонов значений) и хэш-разделение (hash-partitioning) (каждому кортежу назначается раздел на основе его хэширования) . Все эти подходы могут быть эффективными для поддержки выполнения аналитических запросов, когда приходится сканировать крупные наборы данных.
К сожалению, ни один из этих подходов не является идеальным при наличии рабочих нагрузок, которые состоят из небольших транзакций, затрагивающих всего несколько записей. Если транзакция обращается более к одному кортежу, то циклическое и хэш-разделения, как правило, приведут к потребности доступа к нескольким узлам. При выполнении распределенных транзакций производительность системы ниже, чем при выполнении локальных транзакций. Наши результаты, изложенные в разд. 3, показывают, что при обработке только локальных транзакций пропускная способность системы удваивается.
Лучше может сработать разделение по диапазонам, но для этого нужно тщательно выбирать соответствующие диапазоны значений, что трудно делать вручную. Проблема разделения становится еще сложнее, если транзакции обращаются к нескольким таблицам, которые требуется разделять с учетом всех операций транзакций. Например, трудно разделять данные Web-сайтов социальных сетей, в схемах которых часто присутствует много связей n-к-n.
В этой статье мы представляем Schism – новую, основанную на использовании графов и управляемую данными систему разделения для транзакционных рабочих нагрузок. При использовании Schism база данных и рабочая нагрузка представляются в виде графа, в котором кортежам соответствуют вершины, а дуги связывают кортежи, используемые внутри одной транзакции. Затем мы применяем алгоритмы разделения графов для нахождения сбалансированного разделения, минимизирующего число многораздельных транзакций. Schism позволяет регулировать степень балансировки разделов в зависимости от характеристик рабочей нагрузки и размера базы данных, а также создавать разделы, содержащие записи нескольких таблиц.
Вкладом этой статьи, кроме описания нового метода разделения, основанного на использовании графов, является следующее:
Мы демонстриуем, что пропускная способность при выполнении небольших распределенных транзакций значительно уступает пропускной способности при выполнении транзакций в одном узле.
Мы демонстриуем способность Schism к репликации нечасто обновляемых записей. Это позволяет повысить долю в рабочих нагрузках "одноузловых" ("single-sited") транзакций (работающих в пределах только одного узла). В отличие от существующих методов разделения, в этом случае оказывается возможным реплицировать только часть таблицы.
Мы представляем схему, основанную на деревьях решений (decision tree) для выявления предикатов (диапазонов), которые "растолковывают" разделение, обнаруженное графовыми алгоритмами.
Мы показываем, что при работе с крупными наборами данных Schism разделяет их за приемлемое время.
Для разделения базы данных из миллионов записей требуется всего несколько минут. Мы также предлагаем и оцениваем эвристики, включающие взятие образцов (sampling) и группировку кортежей, которые позволяют сократить размер графов для снижения времени разделения.
Наконец, мы демонстрируем, что Schism может найти хорошие разделения для нескольких актуальных приложений, систематически выполняя такую работу не хуже или даже лучше хэш-разделения и разделения по диапазонам вручную. В наиболее сложном протестированном нами случае (сложный граф социальной сети со связями n-к-n) подход Schism обеспечил производительность, превосходящую производительность, которой удалось добиться при разделении вручную. Стоимость выполнения распределенных транзакций удалось сократить на дополнительные 30%.
Хотя в этой статье наш подход к разделению применяется к дисковым системам баз данных, основанным на архитектуре без совместно используемых ресурсов, он применим и в других случаях, включая системы баз данных в основной памяти типа H-Store , производительность которых сильно зависит от соответствия разделения базы данных имеющейся рабочей нагрузке, и автоматическое создание "кусочных" ("sharded") баз данных, для которых важно минимизировать число соединений между "кусочками".
Оставшаяся часть статьи организована следующим образом: в разд. 2 мы представляем общие сведения о своем подходе, в разд. 3 обсуждаем стоимость выполнения распределенных транзакций, в разд. 4 представляем ключевые идеи своей работы, в разд. 5 обсуждаем проблемы реализации и оптимизации, в разд. 6 приводим экспериментальное обоснование, в разд. 7 сравниваем свой подход с родственными работами и, наконец, в разд. 8 приводим свои выводы.
