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

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

Оригинал: Tim Kraska, Martin Hentschel, Gustavo Alonso, Donald Kossmann. Consistency Rationing in the Cloud: Pay only when it matters. Proceedings of the 35th VLDB Conference, August 24-28, 2009, Lyon, France

Содержание

От переводчика: транзакционные данные в облаках – синергия идей СУБД и распределенных систем

Аннотация

1. Введение

2. Сценарии использования

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

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

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

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

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

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

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

5. Политики адаптации

5.1. Общая политика

5.2. Политики, основанные на времени

5.3. Политики для числовых типов

6. Реализация

6.1. Архитектура

6.2. Реализация протоколов

6.3. Логическая журнализация

6.4. Метаданные

6.5. Компонент статистики и политики

6.6. Реализационные альтернативы

7. Эксперименты

7.1. Экспериментальная среда

7.2. Эксперимент 1: стоимость в расчете на транзакцию

7.3. Эксперимент 2: время ответа

7.4. Эксперимент 3: политики

7.5. Эксперимент 4: фиксированное пороговое значение

8. Заключение

9. Литература

От переводчика: транзакционные данные в облаках – синергия идей СУБД и распределенных систем

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

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

• Майкла Стоунбрейкера и др. Сравнение подходов к крупномасштабному анализу данных и
• MapReduce и параллельные СУБД: друзья или враги?,
• Джо Хеллерстейна и др. МОГучие способности: новые приемы анализа больших данных,
• Эрика Фридмана и др. SQL/MapReduce: практический подход к поддержке самоописываемых, полиморфных и параллелизуемых функций, определяемых пользователями,
• Ави Зильбершаца и др. HadoopDB: архитектурный гибрид технологий MapReduce и СУБД для аналитических рабочих нагрузок.

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

По поводу второго направления мы тоже публиковали переводы наиболее интересных статей:

• Майкла Стоунбрейкера и др.Конец архитектурной эпохи, или Наступило время полностью переписывать системы управления данными и
• OLTP в Зазеркалье,
• Даниелы Флореску и Дональд Коссмана Переосмысление стоимости и производительности систем баз данных
• Пэта Хелланда и Дейва Кэмпбела Дом на песке.

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

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

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

В частности, это касается использования термина согласованность (consistency), который в данном случае означает не то же, что в контексте традиционных баз данных. Я всегда считал, что в области баз данных согласованность означает ровно то же, что целостность. Физическая согласованность, или целостность базы данных означает, что к ней могут корректно применяться операции уровня записей. Логическая согласованность, или целостность базы данных означает, что при вычислении над этой базой данных некоторого (возможно, очень сложного) логического выражения, задаваемого администратором базы данных, получается значение true.

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

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

Как я уже говорил, я пока не готов к подробному анализу направления транзакционных "облачных" средств управления данными, но, с моей точки зрения, в этом анализе должны найти отражение и вопросы терминологии.

А пока рекомендую вам почитать статью Тима Краски, Мартина Хеншеля, Густаво Алонсо и Дональда Коссмана. Она того, безусловно, заслуживает.

Сергей Кузнецов

Аннотация

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

В этой статье мы представляем новую парадигму транзакций, которая не только позволяет разработчикам определять гарантии согласованности на уровне данных, а не транзакций, но также обеспечивает возможность автоматически изменять гарантии согласованности во время выполнения. Мы демонстрируем ряд технических приемов, которые позволяют системе динамически приспосабливаться к уровню согласованности путем мониторинга данных и/или сбора статистики о поведении данных во времени. Применимость и перспективность этих идей подтверждается масштабными экспериментами на тестовом наборе TPC-W с использованием первого прототипа такой системы, реализованного в среде Amazon S3. Эти эксперименты показывают, что адаптивные стратегии, представленные в статье, приводят к значительному сокращению времени отклика и расходов, включая операционные расходы, возникающие из-за несогласованности данных.

1. Введение

"Облачные" службы хранения данных становятся все более популярными, поскольку сулят высокие уровни масштабируемости и доступности с низкими затратами. Эти службы используют компьютерные фермы, основанные на аппаратных средствах массового спроса, для обеспечения средств удаленного хранения данных. Существующие коммерческие службы гарантируют строгую согласованность для небольших наборов данных (например, SQL Data Services компании Microsoft) или обеспечивают только согласованность "в конечном счете" (eventual consistency) (например, S3 компании Amazon). Если приложению требуются дополнительные транзакционные гарантии, то их приходится обеспечивать поверх решения "облачного" хранения данных [7].

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

Стоимость конкретного уровня согласованности можно измерить в терминах числа системных вызовов, требуемых для его поддержки. Поскольку существующие платформы обеспечивают только базовые гарантии, дополнительные уровни согласованности (значительно) повышают стоимость выполнения каждой операции. Аналогично, стоимость несогласованности данных можно измерить в терминах процентного соотношения числа некорректных операций, выполняемых из-за поддержки более низких уровней согласованности. Это процентное соотношение часто можно точно отобразить в соответствующие денежные расходы (например, убытки в связи с компенсацией ущерба от ошибочно выполненных заказов или потерей заказчиков). Объемы таких расходов обычно хорошо известны компаниям, предоставляющим подобные услуги.

Нахождение правильного баланса между стоимостью, согласованностью и доступностью является нетривиальной задачей. В крупномасштабных системах обеспечение высокого уровня согласованности приводит к высокой стоимости транзакций и сниженному уровню доступности [7], но позволяет избежать убытков от некорректно выполненных операций. Низкий уровень согласованности означает более низкую стоимость выполнения операций, но может привести к большим убыткам (например, при продаже товаров в Internet-магазине сверх имеющихся запасов). Эта ситуация усложняется тем, что упомянутый баланс зависит от нескольких факторов, включая семантику приложений. В этой статье мы предлагаем путь к обходу этой дилеммы за счет использования динамической стратегии поддержки согласованности: снижение требований к согласованности, когда это возможно, (например, это не приведет к большим убыткам) и повышение их, когда это разумно (например, убытки могут оказаться слишком большими). Такая адаптация управляется моделью стоимости и разными стратегиями, которые диктуют требуемое поведение системы. Мы называем этот подход рационализацией согласованности (Consistency Rationing) по аналогии с рационализацией запасов (Inventory Rationing)[27]. Рационализация запасов – это стратегия управления запасами, при которой запасы отслеживаются с разной точностью в зависимости от наличного числа инвентарных объектов. Следуя этой идее, мы разделяем данные на три категории (A, B и C) и обращаемся с каждой категорией по-своему в зависимости от обеспечиваемого уровня согласованности.

Категория A содержит данные, нарушение согласованности которых привело бы к крупным убыткам. К категории C относятся данные, (временная) несогласованность которых является приемлемой (т.е. либо несогласованность данных вызовет лишь небольшие убытки, либо в действительности несогласованность не возникает). Категория B включает все данные, требования к согласованности которых изменяются во времени в зависимости, например, от реальной доступности некоторого элемента. Обычно такие данные параллельно изменяются многими пользователями и часто являются узким местом в системе. В этой статье мы фокусируемся на категории B. Именно для этой категории можно добиться оптимального соотношения расходов на выполнение операций и обеспечиваемого уровня согласованности. Мы описываем несколько сценариев использования, обосновывающих выделение такой категории данных B. Затем мы излагаем модель стоимости системы и обсуждаем различные стратегии динамического изменения уровней согласованности в зависимости от потенциальных убытков. Эти стратегии направлены на минимизацию общей стоимости выполнения операций над "облачной" системой хранения данных. Наши эксперименты с "облачным" сервисом, реализованным поверх службы S3 компании Amazon, показывают, что динамические политики, которые описываются в этой статье, могут принести значительную экономию затрат. Основным вкладом статьи является следующее:

• Вводится понятие рационализации согласованности (Consistency Rationing), позволяющее приложениям получать требуемые уровни согласованности с наименьшими возможными затратами.
• Определяется и анализируется ряд политик для изменения протоколов согласованности во время выполнения. Наши эксперименты показывают, что политики динамического выбора уровня согласованности оказываются эффективнее политик статического назначения гарантий согласованности.
• Вводится понятие вероятностых гарантий согласованности (т.е. процентили) с использованием темпоральных статистик числовых и нечисловых данных. Такие статистические гарантии очень важны с точки зрения соглашений об уровне обслуживания (service level agreement), хотя, насколько мы знаем, в нашей работе вероятностные гарантии согласованности подробно исследуются впервые.
• Представляется законченная реализация концепции рационализации согласованности на основе S3 компании Amazon. Мы приводим данные о показателях (денежной) стоимости и производительности пропуска тестового набора TPC-W [32] для нескольких категорий согласованности, смеси категорий и различных политик категории B. Результаты этих экспериментов обепечивают правильное представление о стоимостных характеристиках таких систем, о стоимостной структуре каждой операции и о том, как можно оптимизировать эти стоимостные показатели с использованием соответствующих моделей стоимости.

Основная часть статьи организована следующим образом. В разд. 2 описываются сценарии использования рационализации согласованности в "облачных" средах. В разд. 3 обсуждаются родственные работы. В разд. 4 рассматриваются рационализация согласованности, приводится анализ категорий A, B и C и обсуждается, как можно обеспечить смешанные гарантии согласованности. В разд. 5 представляются альтернативные стратегии для управления данными категории B. В разд. 6 описывается реализация рационализации согласованности в "облачной" среде. В разд. 7 приводится сводка результатов экспериментов с использованием тестового набора TPC-W. Разд. 8 содержит заключение.

2. Сценарии использования

Потребность в разных стратегиях поддержки согласованности данных легко выявляется в различных приложениях и уже исследовалась в других контекстах (например, в [11], [12]). Ниже мы представляем различные сценарии, в которых можно было бы применить рационализацию согласованности.

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

Разработчики такого Internet-магазина могли бы использовать рационализацию согласованности следующим образом:

1. Учетная информация считается относящейся к категории данных A, и доступ к таким данным осуществляется при соблюдении гарантий строгой согласованности (т.е. сериализуемости).
2. Данные о наличном количестве товаров относятся к категории данных B. При наличии достаточно больших запасов система допускает некоторую несогласованность данных. Если объем запасов становится ниже некоторого порога, доступ к данным производится с соблюдением гарантий строгой согласованности, чтобы избежать продаж сверх имеющихся запасов.
3. Предпочтения покупателей и журнальная информация классифицируются, как данные категории C. Системе не требуется видеть последнее по времени состояние большинства таких данных, а для их изменения не обязательно нужно предоставлять монопольный доступ к ним.

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

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

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

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

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

Совместное редактирование. Средства совместного редактирования (Collaborative Editing) позволяют людям одновременно работать над одними и тем же документами или исходными текстами программ (к таким средствам относятся, например, Google Docs, системы управления версиями, Wiki и т.д.). Основная функциональность такой системы состоит в выявлении конфликтов, возникающих в процессе редактирования, и отслеживании истории изменений. Традиционно такие системы работают на уровне строгой согласованности. Если система обнаруживает конфликт, то от пользователя обычно требуется его устранение. Только после устранения конфликта пользователю предоставляется возможность внести изменение, если к этому времени не образовался какой-либо другой конфликт. Хотя в реальных ситуациях могут иметься некоторые части документа, часто изменяемые участниками процесса редактирования (например, цитаты из какой-либо статьи), люди обычно стараются организовать материал таким образом, чтобы избегать конфликтов с самого начала. Поэтому для большинства частей документа конфликты маловероятны, и не требуется никакого управления параллелизмом. В отличие от этого, для тех частей, которые часто изменяются несколькими участниками, лучше всего было бы соблюдать гарантии строгой согласованности, чтобы избежать всех конфликтов.

В отличие от предыдущих примеров, в данном случае выбор протокола согласованности основывается на вероятности конфликтов, в не на значимости или времени. В нашей общей политике, описываемой в подразделе 5.1, проблемы этого случая разрешаются путем автоматического применения стратегии, основанной на частоте обновлений.

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