Управление параллелизмом с низкими накладными расходами

       

Родственные работы


В большинстве распределенных систем баз данных (например, [9], [6], [19]) для обработки параллельных запросов используется некоторая разновидность двухфазных синхронизационных блокировок, которые в соответствии с нашими результатами лучше всего подходят при наличии рабочих загрузок с малым числом конфликтов. Другие схемы, такие как упорядочение по временным меткам, позволяют избежать синхронизационных тупиков, допуская при этом параллельное выполнение транзакций. Для поддержки таких схем требуется поддержка наборов чтения/записи, защелок и откатов.

Похоже, что Гарсиа-Молина (Garcia-Molina), Липтон (Lipton) и Вальдес (Valdes) первыми предложили подход к использованию основной памяти большого объема для устранения управления параллелизмом [11-12]. Этот метод использовался в некоторых ранних системах управления базами данных в основной памяти [16]. Шаша (Shasha) и др. в [27] представили механизм исполнения запросов к базам данных, похожий на нашу разработку. Они также отмечали, что схема, похожая на нашу блокировочную схему, может обеспечить существенный выигрыш в производительности при наличии рабочих нагрузок обработки транзакций. Однако их исследование выполнялось в контексте дисковых систем баз данных, требующих журналирования, и они не исследовали спекулятивную схему и схему с синхронизационными блокировками при наличии однопотокового выполнения. Вместо этого они позволяли пользователям указывать, какие транзакции конфликтуют. В системе промежуточного программного обеспечения (middleware) Sprint данные разделяются по нескольким экзмплярам коммерческой системы управления базами данных в основной памяти [7]. Транзакции должны заранее классифицироваться на однораздельные и многораздельные. В отличие от нашей схемы, журналы транзакций пишутся на диск, и используется традиционное управление параллелизмом, обеспечиваемое в используемой СУБД.

Одним из вариантов двухфазной фиксации, похожим на нашу работу, является OPT [13]. В этом протоколе допускает "заимствование" транзакциями незафиксированных ("грязных") данных некоторой транзакции, находящейся на фазе подготовки к фиксации. Хотя в этой работе предполагается использование синхронизационных блокировок, она очень похожа на нашу схему "локального спекулятивного выполнения". Однако в OPT спекулятивно выполняется только одна транзакция, в то время как при применении нашего спекулятивного управления параллелизмом спекулятивно выполняется много транзакций, и может совмещаться двухфазная фиксация многораздельных транзакций с одним и тем же координатором. Редди (Reddy) и Кицурегава (Kitsuregawa) предлагали спекулятивные синхронизационные блокировки, когда транзакция обрабатывает версии "до" и "после" изменяемых элементов данных [15]. Во время фиксации путем отслеживания зависимостей по данным между транзакциями выбирается и применяется корректный вариант выполнения. В этом подходе предполагается, что имеются обильные вычислительные ресурсы. В нашей среде возможности процессоров ограничены, и поэтому наше управление параллелизмом всегда действует на версии данных "после", а также не производит отслеживание зависимостей на мелкоструктурном уровне.




В [3] отмечалось, что синхронизационные блокировки плохо подходят для рабочих нагрузок с большим числом конфликтов, и рекомендовалось использовать в этих случаях оптимистическое управление параллелизмом. Мы придерживаемся близких к этому взглядов, хотя наши предварительные результаты, связанные с OCC, показывают, что в наших условиях этот подход не помогает, поскольку требуется дорогостоящая поддержка наборов чтения/записи. Мы считаем, что в условиях частых конфликтов более эффективно разделение данных и спекулятивное выполнение транзакций.

Разделение данных – это хорошо изученная проблема систем баз данных (среди прочего, см. [18], [24], [8], [17], [10]). В предыдущих исследованиях отмечалось, что разделение данных может эффективно повысить уровень масштабирования систем баз данных за счет распараллеливания ввода-вывода [17] или связывания с каждым разделом отдельного обработчика в кластере [18]. В отличие от этого, нас интересует разделение данных как средство освобождения от потребности в управлении параллелизмом.

H-Store [26] представляет собой инфраструктуру для системы, использующей разделение данных и однопотоковое выполнение для упрощения управления параллелизмом. Мы развиваем эту работу, предлагая несколько схем управления параллелизмом в системах разделенных баз данных в основной памяти и приходя к выводу, что спекулятивная схема часто превосходит по производительности комбинированную схему блокирования и OCC, описанную в статье про H-Store.

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


Содержание раздела