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

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

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

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

В этом разделе мы описываем пять разных политик адаптации гарантий согласованности, обеспечиваемых для отдельных элементов данных категории B. Во всех случаях адаптация состоит в переключении с уровня сериализуемости (категория A) на уровень сессионной согласованности (категория B) и наоборот. Политики различаются способами определения потребности в переключении. Например, Общая политика (General policy) основывается на исследовании вероятности конфликта на заданном элементе данных, и переключение на уровень сериализуемости происходит, если эта вероятность достаточно велика. Политика, основанная на времени, (Time policy) вызывает переключение между уровнями гарантии согласованности на основе времени; обычно работа выполняется на уровне сесионной согласованности до некоторого заданного момента времени, а затем производится переключение на уровень сериализуемости. Эти две первые политики могут применяться к любому элементу данных независимо от его типа.

Для очень распространенного случая числовых данных (например, данных о ценах и запасах) мы предлагаем три дополнительные политики. Политика фиксированного порогового значения (Fixed threshold policy) приводит к переключению уровня гарантий на основе абсолютной величины элемента данных. Поскольку эта политика зависит от порогового значения, который может оказаться трудно определяемым, в последних двух политиках используются более гибкие пороги. В Политике разграничения (Demarcation policy) анализируются относительные величины с учетом глобального порогового значения, а в Динамической политике (Dynamic policy) используются идеи Общей политики применительно к числовым данным, для которых анализируются частота обновлений и реальные значения элементов данных.

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

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

5.1.1. Модель

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

Здесь X – это случайная переменная, соответствующая числу обновлений одной и той же записи в течение интервала кэширования CI. P(X > 1) – это вероятность того, что в течение интервала кэширования CI произойдет более одного обновления одной и той же записи. Однако конфликт может возникнуть только в том случае, когда эти обновления производятся на разных серверах. Поэтому в части (ii) правой части соотношения вычисляется вероятность того, что обновления будут произведены в одном и том же сервере, и полученное значение вычитается из вероятности того, чтобы было произведено более чем одно обновление. В соотношении не учитывается вероятность возникновения двойного конфликта для одной и той же записи. Это связано с тем, что мы предполагаем наличие возможности распознавать и устранять конфликты (например, просто путем отбрасывания конфликтующих обновлений), а также считаем пренебрежимо малой вероятность возникновения двух конфликтов для одной и той же записи за время, которое требуется для обнаружения конфликта (например, время интервала кэширования).

Как и в [30], мы предполагаем, что поступление транзакций в систему является пуассоновским процессом, и это позволяет нам переписать соотношение (1) с использованием средней скорости потока (mean arrival rate) λ. Для пуассоновского распределения функция плотности вероятности (probability density function, PDF) задается соотношением

Поэтому соотношение (1) можно переписать следующим образом:

Если n > 1, и вероятность возникновения конфликта считается достаточно малой (например, не больше 1%), то вторым элементом (iv) правой части этого соотношения можно пренебречь (моделирование показывает, что при k > 3 составляющие этого элемента принебрежимо малы). Следовательно, в качестве верхней границы вероятности конфликта можно использовать значение следующего выражения:

Если требуется большая точность, можно учесть первые одно или два слагаемых из (iv).

5.1.2. Темпоральная статистика

Для вычисления вероятности конфликта во время выполнения без потребности в какой-либо централизованной службе в каждом сервере собирается темпоральная статистика по поводу запросов. Мы используем скользящее окно (sliding window) размера w с показателем скольжения (sliding factor) δ. Размер окна определяет число содержащихся в нем интервалов. Показатель скольжения указывает гранулярность перемещения окна. Для каждого временного окна подсчитывается число обновлений всех данных категории B. Все завершившиеся интервалы окна образуют гистограмму обновлений. Размер окна действует как показатель сглаживания (smoothing factor). Чем больше размер окна, тем лучше статистика, и тем больше требуется времени для адаптации к изменению скоростей потоков. Показатель скольжения влияет на гранулярность гистограммы. Для простоты мы считаем, что показатель скольжения δ кратен интервалу кэширования CI. Чтобы получить на основе локальных статистических данных скорость потока для всей системы λ, достаточно вычислить среднее арифметическое значение числа обновлений некоторой записи и умножить его на число серверов n (которое считается известным во всех серверах), а также поделить на показатель скольжения δ:

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

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

5.1.3. Адаптивная установка порогового значения

Критическим аспектом нашего подхода, влияющим и на расходы, и на корректность, является определение момента времени, в который следует переключать уровни согласованности.

Пусть C_x обозначает стоимость выполнения операции обновления записи категории x. В этой стоимости отражаются только дополнительные расходы в расчете на запись в уже выполняемой транзакции; расходы на образование транзакции не учитываются. Пусть C_O – это расходы, связанные с нарушением согласованности. Запись следует обрабатывать на уровне слабой согласованности, только если ожидаемая экономия от применения слабой согласованности превышает ожидаемые расходы E_O(X), вызываемые несогласовавнностью:

Если C_A - C_C > E_O(X), то запись следует обрабатывать на уровне сессионной согласованности (данные категории C). Если C_A - C_C < E_O(X), то запись следует обрабатывать на уровне строгой согласованности (данные категории A). В предположении, что E_O(X) = P_C(X) × C_O, запись следует обрабатывать в режиме слабой согласованности, если вероятность конфликта меньше значения (C_A - C_C) / C_O:

Это же соотношение можно использовать и для оптимизации параметров, отличных от стоимости. Например, если оптимизируется пропускная способность системы, и мы предполагаем, что разрешение конфликтов снижает производительность, то можно использовать ту же формулу, заменив показатели стоимости показателями производительности.

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

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

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

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

Как и раньшего, очень важно правильно определить это пороговое значение. Аналогично Общей политике, мы можем определить вероятность конфликта P_c(X_T). Различие состоит в том, что случайная переменная X_T изменяется во времени t.

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

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

Во многих сценариях использования большинство конфликтующих обновлений связано с числовыми величинами. К числу примеров таких величин относятся объем запаса товаров в магазине, число доступных билетов в системе резервирования, остаток на счету в банковской системе. Для подобных сценариев часто характерно наличие некоторого ограничения целостности, определяющего предельно допустимые значения данных (например, объем запаса товаров должен быть неотрицательным), и коммутационных операций обновления (например, сложение, вычитание). Эти характеристики позволяют нам оптимизировать Общую политику за счет анализа реальных обновляемых значений для принятия решения о требуемом уровне согласованности. Это можно сделать с применением одной из трех следующих политик. Политика с фиксированным пороговым значением (Fixed threshold policy) основывается на сравнении реальных значений элементов данных и их сравнении с пороговым значением. В Политике разграничения (Demarcation policy) применяется идея протокола разграничения (Demarcation protocol) [3], и для принятия решения анализируется некоторый диапазон значений. Наконец, в Динамической политике (Dynamic policy) модель конфликтов Общей политики расширяется применительно к числовым типам.

5.3.1. Политика с фиксированным пороговым значением

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

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

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

Наибольшим недостатком Политики с фиксированным пороговым значением является статический характер порога. Если изменяются потребности в каком-либо продукте, или какие-то продукты отличаются особой привлекательностью, Политика с фиксированным пороговым значением ведет себя не оптимальным образом (см. описание эксперимента 2 в разд. 7).

5.3.2. Политика разграничения

Протокол разграничения (Demarcation protocol) [3] изначально был предложен для реплицируемых систем. Идея этого протокола состоит в том, что каждому серверу назначается некоторый объем ценностей (например, часть запаса товаров), и весь объем ценностей распределяется между серверами. Каждый сервер может изменять свой локальный объем ценностей, но не выходить за локальные границы. Эти границы обеспечивают глобальную согласованность без потребности в коммуникации серверов. Если границы нарушаются, сервер должен запросить дополнительную долю от других серверов или синхронизоваться с ними для регулировки границ. Этот протокол гарантирует, что общий объем ценностей никогда не станет меньше некоторого порогового значения, и что координация будет производиться только при реальной потребности.

Мы можем перенять протокол разграничения следующим образом. У каждого сервера имеется некоторая доля ценностей, которые он может использовать без блокировок. Далее мы без потери общности будем предполагать, что для каждой записи предельным значением является ноль. Если n – это число серверов, и v – общий объем ценностей (например, размер запаса продуктов), то мы можем определить долю, которую сервер может использовать без строгой согласованности, как . Тогда пороговое значение T определяется, как

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

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

Дополнительным недостатком Политики разграничения является то, что при большом числе серверов n пороговое значение стремится к v. Тогда Политика разграничения будет трактовать данные категории B как данные категории A, и для большинства транзакций потребуются блокировки. Проблемой является и скошенное распределение данных: если некоторый элемент используется редко или неравномерно, пороговое значение может быть увеличено без соответствующего повышения расходов, вызываемых несогласованностью данных.

5.3.3. Динамическая политика

Динамическая политика обеспечивает вероятностные гарантии согласованности за счет регулировки порогового значения.

Модель. Как и при рассмотрении Общей политики, мы предполагаем, что имеется интервал кэширования, и что обновления равномерно распределены между серверами. Следовательно, вероятность того, что значение некоторой записи станет отрицательно, выражается следующим образом:

Здесь Y – это случайная переменная, соответствующая общему объему изменений в течение интервала кэширования CI. Y отличается от X из соотношения (1) тем, что в значении этой переменной отражается не число выполненных операций обновления, а общий объем всех обновлений в течение интервала кэширования. P(T - Y < 0) соответствует вероятности нарушения ограничения согласованности (например, за счет покупки слишком большого числа товаров до того, как сервер начинает применять строгую согласованность).

Темпоральная статистика. Для сбора статистики для Y мы снова используем окно с размеров w и показателем скольжения δ. В отличие от случая Общей политики, мы полагаем, что показатель скольжения δ не кратен интервалу кэширования CI, а является его долей. Для этого имеются два основания. Во-первых, для Динамической политики требуется определение дисперсии. Более точные значения дисперсии получаются при использовании меньших показателей скольжения. Во-вторых, политика концентрируется на часто обновляемых значениях. События (т.е. обновления) не являются редкими, и, следовательно, требуемый объем данных можно собрать в течение меньшего времени.

Для каждого интервала скольжения собирается общий объем всех обновлений данных категории B. Все завершившиеся интервалы окна составляют гистограмму обновлений. Если в некоторой транзакции требуется обновить некоторую запись, то на основе гистограммы скользящего окна с использованием стандартной формулы вычисляется эмпирическая функция плотности вероятности (probability density function, PDF) f. Затем f свертывается (convoluted) CI / δ раз для построения PDF f_CI для всего интервала кэширования:

Свертка требуется, поскольку для нас важно сохранить десперсию.

Чтобы можно было судить об обновлениях в системе целиком, должно быть известно число серверов n. Если свернуть n раз f_CI, мы получим PDF для обновлений во всей системе:

При наличии f_CI*n можно построить интегральную функцию распределения (cumulative distribution function, CDF), которую, в конце концов, можно использовать для определения порогового значения для P(T - X < 0) путем поиска такой вероятности, что

Для оптимизации P_C(Y) можно использовать тот же метод, что и ранее:

Заметим, что пороговое значение T определяется при условии, что вероятность больше, чем P_C(Y), а не меньше.

Хотя существуют эффективные алгоритмы свертки функций, если значение n*CI/δ достаточно велико и/или элемент часто обновляется, то центральная предельная теорема позволяет аппроксимировать CDF нормальным распределением. Это обеспечивает возможность более быстрого вычисления порогового значения для гарантирования процентиля согласованности. С использованием гистограммы плавающего окна можно вычислить арифметическое среднее значение и выборочное среднеквадратичное отклонение s. CDF F_CI*n можно аппроксимировать с использованием нормального распределения со средним значением

и стандартным отклонением

Мы используем статистические данные собираемые во время выполнения, для установки порогового значения для каждой отдельной записи в зависимости от частоты ее обновления. Как показывают результаты эксперимента 2, описываемые в разд. 7, это Динамическая политика превосходит все другие политики по показателям как производительности, так и стоимости. Поскольку статистика собирается во время выполнения, система также имеет возможность реагировать на изменение темпа поступления операций изменения записей.

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