Родственные работы
В литературе, посвященной тематике распределенных систем и баз данных, предлагалось много моделей транзакций и согласованности. В литературе из области баз данных к наиболее часто упоминаемым источникам относятся , и . В области распределенных систем стандартным является учебник, в котором описываются альтернативные модели согласованности, а также свойственные им соотношения согласованности и доступности. В нашей работе эти традиционные модели расширяются за счет возможности определения уровней согласованности на основе данных и изменения гарантий согласованности во время выполнения.
Подходы, наиболее близкие к тому, что мы предлагаем в этой статье, описываются в , и . В представлена инфрастуктура для обеспечения адаптивных гарантий согласованности данных на основе обнаружения случаев их несогласованности (Infrastructure for DEtection-based Adaptive consistency guarantees, IDEA). При обнаружении несогласованностей IDEA устраняет их, если текущий уровень согласованности не удовлетворяет определенным требованиям. В отличие от этого, наш подход направлен на то, чтобы с самого начала избегать возникновения несогласованностей за счет использования информации времени выполнения. В предлагаются набор показателей, покрывающих весь спектр согласованности (например, числовая ошибка, ошибка порядка), и различные протоколы, поддерживающие разные виды согласованности. Эти протоколы похожи на политику разграничения (п. 5.3.2). Однако в упор делается на обеспечение максимально допустимого отклонения значения от того, каким оно должно было бы быть при поддержке строгой согласованности. В своей работе мы сосредотачиваемся на поддержке определенных ограничений согласованности (например, размер запасов должен быть ненулевым). В авторы подразделяют данные на категории, для которых обеспечиваются разные стратегии репликации. Предлагаемая стратегия репликации для данных об объеме запасов снова похожа на политику разграничения, но является более консервативной, поскольку она никогда не приводит к продаже продукта сверх имеющихся запасов, а при некоторых обстоятельствах может даже не позволить продать имеющийся товар.
Понятие категории данных B до некоторой степени напоминает IMS/FastPath и транзакционную модель Escrow . В модели Escrow сокращается продолжительность блокировок, и допускается параллельное выполнение большего числа транзакций за счет отправки при начале транзакции в центральную систему некоторых предикатов. Если центральная система принимает эти предикаты, то в пределах этой транзакции можно считать, что их истинность сохранится без удержания блокировок. По сравнению с этим, в IMS/FastPath не гарантируется, что истинность предикатов сохранится на протяжении всей транзакции. Вместо этого предикаты заново вычисляются во время фиксации транзакции. Оба подхода гарантируют строгую согласованность. Мы расширяем идеи IMS/FastPath и Escrow путем введения понятий вероятностных гарантий и и адаптивного поведения. Кроме того, в IMS/FastPath и Escrow требуется глобальная синхронизация для упорядочивания поступления предикатов, а в своем подходе мы везде, где можно, избегаем синхронизации.
Аналогичным образом, большая работа в направлениях распределенных ограничений согласованности и лимитирования расхождений реплик была выполнена в и соответственно. При распределенном управлении ограничениями согласованности либо обеспечивается строгая согласованность, либо согласованность ослабляется на небольшие промежутки времени, что, в свою очередь, может привести к несогласованности данных. В работах, посвященных лимитированию расхождений реплик, для повышения производительности ослабляются критерии согласованности реплик, но в то же время ограничиваются расхождения между репликами (например, по значениям или времени последнего обновления). Мы расширяем эти подходы посредством вероятностных гарантий согласованности и использования в качестве целей оптимизации производительности и стоимости.
В авторы предлагают метод реализации ограничений согласованности локальных кэшированных копий в системах обработки SQL-запросов. При таком подходе пользователи читают данные из локальных устаревших мгновенных снимков данных, если эти данные находятся в пределах границ, определяемых ограничениями согласованности.
Все записи перенаправляются в основное хранилище, для чего требуются традиционные транзакционные модели. В нашей работе не требуется централизованное хранилище, и идеи расширяются понятием вероятностных грарантий.
Система Mariposa – это распределенная система управления данными, в которой поддерживается высокий уровень мобильности данных . В Mariposa на стороне клиентов могут храниться кэшированные копии элементов данных. Все записи в элемент данных должны выполняться над основной копией. Модель стоимости в Mariposa определяет, где располагается основная копия. Наша работа ортогональна по отношению к Mariposa, потому что мы не занимаемся локальностью данных и концентрируемся на изменении протоколов согласованности во время выполнения.
Авторы предлагают адаптивное управление параллелизмом на основе стохастической модели. Однако в их модели не принимается во внимание несогласованность. Вместо этого реализация переключается с оптимистического управления параллелизмом на пессимистическое управление и наоборот при обеспечении одного и того же уровня гарантий.
В H-Store предпринимается попытка полностью избежать любого вида синхронизации за счет анализа транзакций и разделения данных. В H-Store обеспечиваются гарантии строгой согласованности, но требуется заранее знать все запросы и транзакции. Мы не делаем подобного предположения. Кроме того, может оказаться возможным объединить эти два подхода, добившись соответствующего повышения производительности.
Исследования, описываемые в этой статье, мотивируются, главным образом, наличием "облачных" служб баз данных с точными ценовыми показателями (в денежном выражении) в расчете на одну транзакцию. В Simple Storage Service компании Amazon и BigTable компании Google обеспечиваются гарантии согласованности "в конечном счете" (eventual consistency). В последнее время некоторые исследовательские работы фокусируются на обеспечении более строгих гарантий. В PNUTS компании Yahoo обеспечиваются гарантии монотонности и изоляция с использованием мгновенных снимков на уровне записей.Мотивация этой работы аналогична нашей: чем выше уровень согласованности, тем выше стоимость и ниже производительность. В MegaStore компании Google и SQL Data Services компании Microsoft обеспечиваются транзакционные гарантии, но с ограничениями на размер данных (например, при использовании SQL Data Services транзакционные гарантии обеспечиваются только при размере данных в пределах одного гигабайта на контейнер). Но даже для поставщиков услуг, обеспечивающих гарантии согласованности более высокого уровня, насущным остает вопрос стоимости, поскольку поддержка более высокого уровня согласованности означает более высокую стоимость транзакций.
