Обеспечение масштабируемости
Практическое инструментальное средство разделения должно обладать способностью к обработке очень больших баз данных. С ростом размера базы данных и числа кортежей, к которым обращается каждая транзакция, растет и графовое представление. Чем больше разных транзакций содержится в рабочей нагрузке, тем больших размеров трасса рабочей нагрузки требуется для фиксации типичного поведения. С ростом числа разделов требуется обнаруживать больше разрезов в графе. Эти факторы могли бы ограничить размеры баз данных, с обработкой которых справляется наша система.
Как мы покажем в разд. 6, средства разбиения графов хорошо масштабируются по отношению к числу разделов, но с ростом размера графа время их работы существенно возрастает. Поэтому мы сосредоточили усилия на уменьшении размеров графов. Интуитивно кажется, что это поможет уменьшить время работы алгоритма разделения, но ухудшит качество результата, поскольку входной граф меньшего размера содержит меньше информации. Однако мы разработали ряд эвристик, которые позволяют сократить размер графа с умеренным воздействием на качество разделения. Более точно, мы реализовали следующие эвристики:
-
Взятие образцов на уровне транзакций (transaction-level sampling), что позволяет ограничить объем рабочей нагрузки, представляемой в графе, т.е. уменьшить число дуг.
-
Взятие образцов на уровне кортежей (tuple-level sampling), что позволяет сократить число кортежей (узлов), представляемых в графе.
-
Отбрасывание "ковровых" запросов (blanket statement filtering), что позволяет не учитывать редко встречающиеся запросы, приводящие к сканированию больших частей таблицы. Эта эвристика оправдывается тем, что (i) наличие таких запросов приводит к образованию в графе многих дуг, несущих мало информации, и (ii) выполнение подобных запросов эффективно распаллеливается по разделам, поскольку накладные расходы распределенных транзакций менее значительны, чем расходы на выполнение частей запроса в разных узлах.
-
Фильтрация по релевантности (relevance filtering), когда удаляются кортежи, к которым обращения производятся очень редко (предельным случаем являются кортежи, к которым в рассматриваемой рабочей нагрузке вообще отсутствуют обращения).
Соответствующие вершины графа мало информативны.
Звездообразная репликация (star-shaped replication), когда вершины-реплики связываются в звездообразную конфигурацию, а не в полный подграф (clique), что ограничивает число дуг.
Склеивание кортежей (tuple-coalescing), что позволяет представлять одной вершиной графа группу кортежей, к которым доступ всегда производится ко всем сразу. Это не вызывает потери информации и в некоторых случаях приводит к существенному сокращению размера графа.
Эти эвристики обеспечили эффективное сокращение размеров графов для наших тестовых наборов, сохранив при этом высокое качество результатов. Например, в подразделе 6.2 мы показываем, что (при наличии нескольких тысяч транзакций) в покрытии графа, включающем всего 0,5% от числа кортежей базы данных, остается достаточно информации, чтобы получить разделение, качество которого сопоставимо с наилучшим разделением базы данных, выполненным вручную.
