Разделение графов
Представление графов в 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. Кроме того, при исчерпании основной памяти такие таблицы можно хранить распределенным образом в основной памяти на разных машинах или в виде индекса в дисковой памяти.
При использовании поисковых таблиц новые кортежи сначала вставляются в произвольный раздел, и сохраняются там, пока не будет заново подсчитано разделение, после чего их можно переместить в соответствующие разделы. Поскольку разделение графа выполняется быстро, эту процедуру можно будет выполнять часто, что будет препятствовать удорожанию распределенных транзакций из-за добавления новых кортежей.
Хотя этот подход эффективен, если требуется стратегия мелкоструктурного разделения (например, в некоторых приложениях социальных сетей), он не идеален для очень крупных систем баз данных с рабочими нагрузками с очень интенсивной вставкой кортежей. Поэтому мы разработали аналитическое инструментальное средство, которое может обнаружить более простое, основанное на использовании предикатов средство разделения, близко аппроксимирующее результат компонента разделения графов.
