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

Мы рассматриваем систему баз данных, выполняющую рабочую нагрузку, которая однородным образом составлена из транзакций с n операциями обновления, где два обновления не затрагивают общих данных с вероятостью s (т.е. они конфликтуют с вероятностью 1 - s). Если мы запускаем транзакцию Ti в ситуации, когда k блокировок удерживается другими транзакциями, мы ожидаем, что для Ti будет немедленно удовлетворен запрос всех n блокировок с вероятностью

pn = (sk)n = skn

В этом случае мы предполагаем (поскольку транзакции являются короткими), что Ti зафиксируется и сразу освободит свои блокировки, так что Ti+1 также будет выполняться в среде, в которой блокированы k записей.

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

где

Еще раз повторим, что

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

– что не удовлетворяется ни один из этих x запросов.

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

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

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

Начало координат представляет собой точку выполнения транзакций сразу после приостановки T0: i = 0 и

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

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

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