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



Разделение графов - часть 2


В большинстве алгоритмов разделения графов используются методы многоуровневого огрубления (multilevel coarsening) и обеспечиваются параллельные реализации в распределенной среде, позволяющие обрабатывать исключительно крупные графы (сотни миллионов дуг). В Schism для разделения графов мы используем METIS .

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

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

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

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

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




Содержание  Назад  Вперед