Рационализация согласованности в "облаках": не платите за то, что вам не требуется

Тим Краска, Мартин Хеншель, Густаво Алонсо, Дональд Коссман
Перевод: Сергей Кузнецов

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

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

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

Подходы, наиболее близкие к тому, что мы предлагаем в этой статье, описываются в [21], [36] и [12]. В [21] представлена инфрастуктура для обеспечения адаптивных гарантий согласованности данных на основе обнаружения случаев их несогласованности (Infrastructure for DEtection-based Adaptive consistency guarantees, IDEA). При обнаружении несогласованностей IDEA устраняет их, если текущий уровень согласованности не удовлетворяет определенным требованиям. В отличие от этого, наш подход направлен на то, чтобы с самого начала избегать возникновения несогласованностей за счет использования информации времени выполнения. В [36] предлагаются набор показателей, покрывающих весь спектр согласованности (например, числовая ошибка, ошибка порядка), и различные протоколы, поддерживающие разные виды согласованности. Эти протоколы похожи на политику разграничения (п. 5.3.2). Однако в [36] упор делается на обеспечение максимально допустимого отклонения значения от того, каким оно должно было бы быть при поддержке строгой согласованности. В своей работе мы сосредотачиваемся на поддержке определенных ограничений согласованности (например, размер запасов должен быть ненулевым). В [12] авторы подразделяют данные на категории, для которых обеспечиваются разные стратегии репликации. Предлагаемая стратегия репликации для данных об объеме запасов снова похожа на политику разграничения, но является более консервативной, поскольку она никогда не приводит к продаже продукта сверх имеющихся запасов, а при некоторых обстоятельствах может даже не позволить продать имеющийся товар.

Понятие категории данных B до некоторой степени напоминает IMS/FastPath и транзакционную модель Escrow [13, 23]. В модели Escrow сокращается продолжительность блокировок, и допускается параллельное выполнение большего числа транзакций за счет отправки при начале транзакции в центральную систему некоторых предикатов. Если центральная система принимает эти предикаты, то в пределах этой транзакции можно считать, что их истинность сохранится без удержания блокировок. По сравнению с этим, в IMS/FastPath не гарантируется, что истинность предикатов сохранится на протяжении всей транзакции. Вместо этого предикаты заново вычисляются во время фиксации транзакции. Оба подхода гарантируют строгую согласованность. Мы расширяем идеи IMS/FastPath и Escrow путем введения понятий вероятностных гарантий и и адаптивного поведения. Кроме того, в IMS/FastPath и Escrow требуется глобальная синхронизация для упорядочивания поступления предикатов, а в своем подходе мы везде, где можно, избегаем синхронизации.

Аналогичным образом, большая работа в направлениях распределенных ограничений согласованности и лимитирования расхождений реплик была выполнена в [10, 18] и [22, 26] соответственно. При распределенном управлении ограничениями согласованности либо обеспечивается строгая согласованность, либо согласованность ослабляется на небольшие промежутки времени, что, в свою очередь, может привести к несогласованности данных. В работах, посвященных лимитированию расхождений реплик, для повышения производительности ослабляются критерии согласованности реплик, но в то же время ограничиваются расхождения между репликами (например, по значениям или времени последнего обновления). Мы расширяем эти подходы посредством вероятностных гарантий согласованности и использования в качестве целей оптимизации производительности и стоимости.

В [16, 19, 17] авторы предлагают метод реализации ограничений согласованности локальных кэшированных копий в системах обработки SQL-запросов. При таком подходе пользователи читают данные из локальных устаревших мгновенных снимков данных, если эти данные находятся в пределах границ, определяемых ограничениями согласованности. Все записи перенаправляются в основное хранилище, для чего требуются традиционные транзакционные модели. В нашей работе не требуется централизованное хранилище, и идеи расширяются понятием вероятностных грарантий.

Система Mariposa – это распределенная система управления данными, в которой поддерживается высокий уровень мобильности данных [28]. В Mariposa на стороне клиентов могут храниться кэшированные копии элементов данных. Все записи в элемент данных должны выполняться над основной копией. Модель стоимости в Mariposa определяет, где располагается основная копия. Наша работа ортогональна по отношению к Mariposa, потому что мы не занимаемся локальностью данных и концентрируемся на изменении протоколов согласованности во время выполнения.

Авторы [30] предлагают адаптивное управление параллелизмом на основе стохастической модели. Однако в их модели не принимается во внимание несогласованность. Вместо этого реализация переключается с оптимистического управления параллелизмом на пессимистическое управление и наоборот при обеспечении одного и того же уровня гарантий.

В H-Store [29, 25] предпринимается попытка полностью избежать любого вида синхронизации за счет анализа транзакций и разделения данных. В H-Store обеспечиваются гарантии строгой согласованности, но требуется заранее знать все запросы и транзакции. Мы не делаем подобного предположения. Кроме того, может оказаться возможным объединить эти два подхода, добившись соответствующего повышения производительности.

Исследования, описываемые в этой статье, мотивируются, главным образом, наличием "облачных" служб баз данных с точными ценовыми показателями (в денежном выражении) в расчете на одну транзакцию. В Simple Storage Service компании Amazon [2] и BigTable компании Google [9] обеспечиваются гарантии согласованности "в конечном счете" (eventual consistency). В последнее время некоторые исследовательские работы фокусируются на обеспечении более строгих гарантий. В PNUTS компании Yahoo [11] обеспечиваются гарантии монотонности и изоляция с использованием мгновенных снимков на уровне записей. Мотивация этой работы аналогична нашей: чем выше уровень согласованности, тем выше стоимость и ниже производительность. В MegaStore компании Google [8] и SQL Data Services компании Microsoft [20] обеспечиваются транзакционные гарантии, но с ограничениями на размер данных (например, при использовании SQL Data Services транзакционные гарантии обеспечиваются только при размере данных в пределах одного гигабайта на контейнер). Но даже для поставщиков услуг, обеспечивающих гарантии согласованности более высокого уровня, насущным остает вопрос стоимости, поскольку поддержка более высокого уровня согласованности означает более высокую стоимость транзакций.

4. Рационализация согласованности

Сценарии использования, рассмотренные в разд. 2, показывают, что не для всех данных требуются одни и те же гарантии согласованности. Этот факт хорошо известен в области стандартных приложений баз данных, и ситуация регулируется за счет обеспечения разных уровней согласованности различным транзакциям. Хотя можно ослабить любое из свойств ACID (Atomicy, Consistency, Isolation, Durability), в этой статье мы фокусируемся на изоляции (Isolation) и согласованности (Consistency) в предположении, что атомарность (Atomicy) и долговечность хранения (Durability) обеспечиваются.

В направлении ослабления гарантий согласованности получены ценные результаты как в области распределенных систем (например, согласованность "в конечном счете" (eventual consistency), монотонность чтения-записи (read-write monotonicity) и сессионная согласованность (session consistency) [31]), так и в области управления транзакциями (например, режимы чтения зафиксированных данных (read committed), чтения незафиксированных данных (read uncommitted), сериализуемости (serializability) и (обобщенный) метод изоляции на основе мгновенных снимков (snapshot isolation) [4]). Основной вывод, который можно сделать на основе этих работ, состоит в том, что назначением моделей ослабленной согласованности является обеспечение наилучшего соотношения затрат и прибыли при сохранении понимаемого разработчиками поведения приложений. Имея это в виду, мы рассматриваем только два уровня согласованности (сессионная согласованность и сериализуемость) и подразделяем данные на три категории.

4.1. Категория C – сессионная согласованность

Категория C включает данные, для которых поддерживается сессионная согласованность (session consistency). Сессионная согласованность определяется как минимальный уровень согласованности в распределенной среде, не приводящий к чрезмерной сложности разработки приложений [31]. При поддержке сессионной согласованности приложения не обязательно видят свои собственные изменения данных и при последующих обращениях могут получить несогласованные данные.

Клиенты подключаются к системе в контексте сессий. Пока длится сессия, система гарантирует монотонность по чтению собственных записей (read-your-own-writes monotonicity). Гарантии монотонности не распространяются за границы сессий. Если некоторая сессия завершается, в новой сессии могут быть сразу не видны записи, произведенные в предыдущей сессии. В сессии одного клиента могут быть не видны изменения, произведенные в сессии другого клиента. По истечении некоторого времени (и при отсутствии сбоев) система достигает устойчивого состояния, и данные становятся согласованными (это свойство, полезное в распределенных вычислениях, называется согласованностью "в конечном счете" (eventual consistency). Например, в службе S3 компании Amazon, направленной на хранение файлов, обеспечивается согласованность "в конечном счете".

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

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

4.2. Категория A – сериализуемость

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

Данные следует относить к категории A, если их согласованность и актуальность являются обязательными. Мы обеспечиваем сериализуемость на основе использования пессимистического протокола (протокола двухфазных блокировок, 2PL). Мы выбрали сериализацию, а не, например, изоляцию на основе мгновенных снимков, чтобы транзакции всегда видели последнее по времени состояние базы данных.

4.3. Категория B – адаптивность

В промежутке между данными с сессионной согласованностью (C) и данными, для которых поддерживается режим сериализации (A), существует широкий спектр типов данных и приложений, для которых требуемый уровень согласованности зависит от конкретной ситуации. Иногда требуется строгая согласованность, а иногда она может ослабляться. Принимая во внимание двойное влияние транзакционной согласованности в условиях "облачных" баз данных (на стоимость и производительность), мы вводим категорию B, включающую все данные, для которых имеются требования адаптивной согласованности.

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

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

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

4.4. Смеси категорий

В нашей "облачной" инфраструктуре баз данных гарантии согласованности обеспечиваются для данных, а не для транзакций. Это мотивируется тем, что у данных имеются разные стоимостные характеристики. Например, для данных о банковских счетах и запасах требуется изоляция, а для журнальных данных или профилей клиентов – нет. Определение согласованности на данных, а не на транзакциях позволяет обращаться с данными в соответствии с их важностью. Однако побочным эффектом этого подхода является то, что транзакции при доступе к разным данным могут выдеть разные уровни согласованности.

Если в одной транзакции обрабатываются данные разных категорий, то каждая запись, затрагиваемая этой транзакцией, обрабатывается в соответствии с гарантиями согласованности, свойственными категории этой записи. Поэтому операции чтения данных категории A получают согласованные данные, а операции записи оставляют их в согласованном состоянии. При чтении данных категории A всегда выбираются актуальные данные. При чтении данных категории C в зависимости от эффектов кэширования могут выбираться устаревшие данные. Логическим следствием является то, что для результатов операций соединения, объединения и т.д. данных категорий A и C обеспечиваются только гарантии категории C. В большинстве ситуаций это не приносит вреда и является ожидаемым/желательным поведением. Например, в результате соединения данных об остатках на счетах (данные категории A) и данных о профилях клиентов (данные категории C) будет содержаться только актуальная информация о балансах счетов, но, возможно, устаревшие данные об адресах клиентов.

Если это необходимо с точки зрения приложения, для транзакций можно указать требуемые им гарантии. Это позволяет транзакции видеть актуальное состояние любой записи. Однако это не гарантирует, что у этой транзакции имеется монопольное право на обновление этой записи. Если одна транзакция производит запись в режиме сессионной согласованности, а другая – в режиме сериализуемости, то все равно может возникнуть несогласованность.

4.5. Модель разработки

Рационализация согласованности приводит к усложнению процесса разработки приложений, выполяемых над "облачной" системой хранения данных. Во-первых, данные должны быть разделены (рационированы) на категории согласованности. Этот процесс производится на основе операционной стоимости транзакций и расходов, вызываемых несогласованностью данных. Во-вторых, требуемый уровень согласованности должен быть определен для коллекции данных (т.е. отношения) вместе с соответствующей политикой и всеми ограничениями целостности. Это можно сделать путем аннотирования схемы, аналогично тому, что предлагается в [35].

Мы думаем, что процессы разработки приложения и рационализации согласованности можно разделить. В течение процесса разработки предполагается наличие строгой согласованности. Программист будет следовать обычной модели программирования приложений баз данных с явно определяемыми транзакциями. Независимо от категоризации данных программист будет всегда задавать команду start transaction в начале транзакции и команду commit transaction в конце транзакции. При развертывании приложения данные рационируются в соответствии со стоимостью. Рационализация может производится специалистом не из отдела разработки. Конечно, при этом предполагается. что разделение разработки и рационирования не влияет на корректность системы. Вопрос о том, какими свойствами должно обладать приложение, чтобы можно было разделить процессы разработки и рационирования данных, в этой статье не обсуждается и заслуживает дополнительных исследований.

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