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