Аналитическая модель производительности системы при наличии "загромождения"

p_n = (s^k)ⁿ = s^kn

В этом случае мы предполагаем (поскольку транзакции являются короткими), что T_i зафиксируется и сразу освободит свои блокировки, так что T_i+1 также будет выполняться в среде, в которой блокированы k записей. Однако если T_i обратится к какой-либо из этих k записей, она не сможет завершиться. В этом случае мы хотим оценить число удерживаемых T_iблокировок новых записей, чтобы определить, как изменяется k. В традиционной модели T_i запрашивает блокировки по ходу своего выполнения, блокируясь при возникновении первого конфликта, и больше блокировки не запрашивая. Поэтому ожидаемое приращение числа k в традиционном случае зависит от числа блокировок (обозначенного ниже как m), которые удалось получить в транзакции T_i до того, как она наткнулась на одну из k блокировок, уже удерживаемых другими транзакциями:

где

и .

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

При использовании нашей детерминированной модели выполнения T_i запрашивает все блокировки в начале своего выполнения, независимо от того, какие из запросов удовлетворяются, так что ожидаемое приращение числа k зависит от общего числа записей, по которым T_i конфликтует при наличии k заранее удерживаемых запросов (ниже это обозначается как n-m, где m – это снова число новых запрашиваемых блокировок):

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

В обоих случаях нас интересует не просто то, сколько записей блокируется, а как это повлияет на последующее выполнение. На рис. 4 показано значение 1 - p_n (вероятность того, что поступающие транзакции не смогут выполняться из-за конфликта блокировок) как функция от i (числа новых транзакций, поступивших в систему после транзакции T₀).

Начало координат представляет собой точку выполнения транзакций сразу после приостановки T₀: i = 0 и . При использовании обеих моделей выполнения на раннем этапе (до того, как много транзакций заблокируются прямо или косвенно из-за блокировок, удерживаемых T₀) большинство транзакций сможет продолжать выполнение, не испытывая конфликта блокировок, так что значение k возрастает медленно. Потом застрянет большее число транзакций, загромождая менеджер блокировок и создавая цикл с положительной обратной связью, в котором уровень загромождения в течение некоторого времени экспоненциально возрастает, асимптотически приводя систему в состояние, в котором поступающие транзакции со стопроцентной вероятностью не смогут завершаться. Не удивительно, что взрывообразный рост загромождения наступает гораздо раньше в детерминированном случае, в котором даже транзакции, конфликтующие с другими транзакциями лишь по немногим записям, добавляют к набору заблокированных записей свои наборы чтения и записи целиком.

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

Аналитическая модель производительности декомпозированных зависимых транзакций первого порядка

При наличии рабочих нагрузок, насыщенных декомпозированными зависимыми транзакциями, можно расчитывать на хорошую производительность, если зависимости транзакции обновляются не часто. Когда записи, от которых зависят транзакции рабочей нагрузки, становятся более изменчивыми, можно ожидать ухудшения производительности. Пусть (T₁, T₂) – это декомпозиция зависимой транзакции первого порядка T, набор чтения/записи которой зависит от множества записей . Общее время, в течение которого обновление некоторой записи r ∈ должно привести к аварийному завершению и перезапуску T₂, примерно совпадает со временем между запросом транзакции T₁ на образование транзакции T₂ и началом выполнения T₂. Обозначим этот интервал времени как D. Если R обозначает общую транзакционную пропускную способность, и V – изменчивость , то вероятность того, что ни одна транзакция не обновит запись в течении любого интервала времени длиной D, выражается как

P = (1 - V/R)^DR,

и ожидаемое число раз выполнения T₂ вычисляется следующим образом:

Рис. 5. Ожидаемое число перезапусков декомпозированной зависимой транзакции первого порядка как функция от общей изменчивости ее зависимостей.

На рис. 5 показано ожидаемое число перезапусков типичной декомпозированной транзакции как функция от изменчивости ее зависимостей.

Экспериментальные измерения декомпозированных зависимых транзакций первого порядка

Рис. 6. Измеренные пропускная способность и среднее число перезапусков зависимых транзакций первого порядка как функция от изменичивости их зависимостей.

На рис. 6 показаны общая транзакционная пропускная способность и среднее число перезапусков транзакции до того, как она могла выполниться вплоть до завершения – и то, и другое как функции от средней изменчивости элементов индекса. Приведены результаты для рабочих нагрузок, включающих 0%, 20%, 40%, 60%, 80% и 100% зависимых транзакций.

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

Однако мы выяснили, что при наличии даже сильно зависимых рабочих нагрузок, если изменчивость находится в разумных пределах (меньше 1000 обновлений каждой записи в секунду), то декомпозиция транзакций для обеспечения возможности работы с вычисляемыми наборами чтения/записи оказывает пренебрежимо малое влияние на производительность.

Рис. 7. Транзакционная пропускная способность TPC-C (100% транзакций New Order), измеренная интенсивность конфликтов блокировок и средняя задержка транзакций.

Дополнительные характеристики производительности TPC-C

Графики интенсивности конфликтов блокировок и задержки демонстрируют два важных эффекта, которые помогают лучше понять детали поведения систем во время проведения наших экспериментов:

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


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

  Предстоящая работа

  Мы намереваемся продолжать исследования в нескольких направлениях.

  Переупорядочивание в препроцессоре

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

  Гладкие переходы между детерминированной и недетерминированной моделями выполнения/репликации

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

  Планирование потоков управления в детерминированных системах

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

  Другие детерминированные схемы управления параллелизмом

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

  ---

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