Источник: http://citeseer.ist.psu.edu/nicola00performance.html
Авторы: Matthias Nicola, Matthias Jarke.

Перевод: Афонов И.В.
Главная цель этого документа – исследования возможных вариантов моделирования производительности распределённых БД. В качестве показательного примера в данной работе, продемонстрирована разработка аналитической модели производительности, названной 2RC, которая включает в себя двумерную модель репликации во взаимодействии с развитой моделью коммуникаций(связи).

 

Структурированный анализ существующих моделей ориентирован на следующие компоненты:

         - общие концепции моделирования узлов-БД.

         - варианты рассмотрения взаимодействия между БД.

         - подмодели для расчётов показателей репликации.

         - предположения, касающиеся методов доступа к данным

         - модели обработки транзакций

         - взаимозависимости между всеми вышеперечисленными аспектами которые описаны (или нет) в существующих моделях

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

         В качестве показательного примера для данной работы, мы продемонстрировали разработку аналитической модели производительности, названной нами 2RC которая включает в себя двумерную модель репликации во взаимодействии с развитой моделью коммуникаций(связи). 2RC учитывает всё увеличивающееся взаимодействие между репликацией и коммуникацией и представляет сбалансированную модель и базы данных и модель коммуникационной части реплицированной и распределённой системы баз данных. 2RC также позволяет моделировать качество схемы репликации также как произвольные типы транзакций и методы доступа к данным в реальных приложениях. Результаты показывают как схемы частичной 2D репликации, которые не были рассчитаны до этого, влияют на время отклика, пропускную способность и масштабируемость. Это показывает что 2D модели являются более выразительными чем одномерные решения. Более того, мы показали как анализ узких мест («бутылочное горлышко»)  может выявить, проблемы в какой части системы (в сети или БД) являются препятствием к увеличению производительности системы целом. В конце мы определили свою версию метода оценки производительности DebitCredit и обсудили 2 из 40 измерений которые подтверждают выводы сделанные с применением  аналитической модели.

         В заключении, мы полагаем, что продолжающиеся усилия, прикладываемые к разработке и улучшению моделей производительности реплицированных баз данных необходимы, так как они позволяют развиваться реплицированным базам данных наравне с эволюцией распределённых информационных систем в целом. Как пример можно привести, появление взглядов «доступ к БД в любое время в любом месте»(«database access anywhere anytime») появление которых повлияло на производительность информационных систем в целом. Количество распределённых систем использующих репликацию постоянно увеличивается, беспроводные системы связи страдают от низкой надёжности и пропускной способности каналов связи, большие серверы БД постепенно заменяются на кластеры, состоящие из рабочих станций. Данные взгляды должны быть приняты во внимание при разработке будущих моделей и должны быть интегрированы с существующими, обоснованными и подтверждёнными на практике моделями.

 

 

1 2RC: Пример аналитической модели производительности.

Как краткий итог этого обзора, в Таблице 2 представлены типичные альтернативы для различных компонентов моделей. В каждом строке таблицы сложность моделирования увеличивается слева направо (что обычно не связано с выразительностью и точностью моделирования). Заштрихованные ячейки показывают наиболее распространённые методы используемые в большинстве решений. Чтобы показать выбор концепций моделирования представленный в предыдущих главах мы покажем пошаговую разработку аналитической модели производительности для распределённых и реплицированных БД. В главе 4.1 мы определили желаемые рамки модели и в главе 4.2 описываются необходимые зависимости. Просматривая классификацию концепций моделирования как конструктор, мы выбираем «строительные блоки» из таблицы 2 и используем их при построении модели. Данные ячейки выделены чёрной рамкой в таблице. В результате мы получаем 2-мерную реплицированную модель с интегрированными коммуникациями. Данная модель характеризуется тем что в ней как можно меньшее количество характеристик моделируется упрощённо либо вовсе ими пренебрегают. Используя данный пример мы в общих чертах опишем расчёт характеристик нагрузки на сеть, задержку обработки, время отклика и пропускную способность как основные характеристики производительности.

 

4.1 Возможности модели

Модель 2RC построена для оценки взаимосвязи между репликацией и коммуникацией и таким образом является сбалансированной моделью и базы данных и связи между узлами реальной системы. Модель 2RC базируется на новой двумерной модели репликации которая необходима для более точно представления и расчётов характеристик схемы репликации. В расчёт принимается не только время отклика сети, но и пропускная способность, как одна из важнейших характеристик производительности. Это требует реализации моделирования зависимости времени отклика от загрузки сети, ограничений (по характеристикам сети) пропускной способности транзакций и взаимозависимостей между репликацией и коммуникацией. Более того в модели поддерживается поиск узких мест реализации. С помощью модели возможно описать детально описать методы обработки транзакций и методы коммуникаций это позволяет моделировать реальные приложения. Более того, в модели приняты во внимание: различная вероятность доступа к различным объектам, качество схемы репликации.(+ relaxed coherency).

     В модели 2RC реализована модель обработки транзакций «primary copy», т.к эта модель оценивается как более выгодная по сравнению с другими концепциями обработки транзакций, также данная модель реализована во многих коммерческих СУБД таких как Sybase и Oracle. В модели 2RC предполагается, что  изменение данных асинхронно распространяется на другие копии данных, т.е в модели не реализована возможность двух-фазного подтверждения. Более того предполагается что транзакции выполняются только на одному узле (локальном или удалённом). С учётом того что модель не предназначена для сравнения алгоритмов разрешения конфликтов, мы воздержались от моделирования конфликтов для того, чтобы сконцентрироваться на репликации и коммуникации.

 

4.2 Структура зависимостей

Схема зависимостей представлена на рисунке 7. Ядром модели 2RC является двумерная схема репликации данных, это оказывает прямое влияние на качество репликации, интенсивности входных потоков, загрузку сети и оказывает значительное влияние на все последующие выводы и результаты. τ-типы транзакций (транзакции с различными интенсивностями входного потока и различным временем обслуживания) и 2 типа сообщений на транзакцию (с индивидуально распределенными временами передачи зависимыми от размеров передаваемых данных) позволяют моделировать широкий круг различных приложений и методов загрузки. Общая пропускная способность зависит и от пропукной способности сети и от пропускной способности базы данных, что позволяет анализировать «узкие места» реализаций модели. Схема репликации (вместе с разновероятностным доступом к данным и со слабой связностью) влияет не только на интенсивность поступления транзакций, но и на значения характеристик сети и таким образом на время задержки сети.  Модель 2RC содержит в себе всестороннюю модель репликации и детализированную модель взаимодействия, она покрывает большее количество взаимозависимостей между двумя вышеперечисленными моделями чем предшествующие методики. Однако тем не менее модель в своём прямом смысле это неполное и упрощённое отражение реальности.

 

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

Параметр	Значение
n	Количество узлов в сети (узел = БД)
r1	Доля реплицированных данных
ai	Доля транзакций типа i в общем потоке
qi	Отношение между чтением/записью
loci
plcmt	Качество размещения копий
F_plcmt	Дополнительный параметр, моделирует оценку качества размещения копий
bps	Пропускная способность
Size(c, send_i)	Объём посланных данных транзакции типа i
t	Среднее время посылки
tau	Количество типов транзакций
r2	Количество копий реплицированных объектов
λ	Интенсивность входного потока транзакций типа i на узел(TPS)
ti	Среднее время обслуживания  транзакции типа i (сек)
li	Вероятность выполнения транзакции на локальном узле
seli	Качество выбора данных для копирования
F_sel	Дополнительный параметр, моделирует оценку качества выбора данных для копирования
k	Индекс связности (когерентности данных) – показывает, насколько может быть отложена синхронизация данных, т. е насколько могут «отличатся» одни и те же данные в разных копиях.
Size(c, receive_i)	Размер возвращённых данных
t	Среднее время необходимое для возвратарезультирующих данных запроса

 

 

4.3 Загрузка и локальность

         Мы моделируем реплицированную базу данных с помощью разомкнутой сети СМО, в которой каждый из n узлов представлен СМО вида M / Hτ / 1. Появление заявок в распределённой системе ивзне системы смоделировано с помощью n идентичных потоков Пуассона с параметром λ (один поток на одну СМО). Потоки Пуассона являются хорошим приближением для моделирования заявок которые генерируются независимо большим количеством пользователей, и используются практически во всех моделях производительности распределённых БД. τ различных типов транзакций последовательно пронумерованны от 1 до τ. Транзакиця приндалежит к типу i с вероятностью аi, сумма аi = 1, таким образом входной поток Пуассона на узле состоит из τ отдельных потоков имеющих интенсивности λi = λ*аi, 1 <= i <= τ. Характеризующая функция q позволяет различать между собой запросы на выборку и на обновление в множестве типов транзакций. i – порядковый номер в множестве типов транзакций.

 

         q(i) = 0 если i запрос

q(i) = 1 если i обновление.

 

         Количество объектов доступ, к которым получен в рамках одной транзакции, считается геометрически распределённым, время обслуживания для транзакции типа i на локальной базе данных смоделировано как экспоненциально распределённое со средним значением времени обслуживании ti (в секундах). Отсюда следует, что время обслуживания для составного входного потока из τ типов транзакций подчинено τ-phase hyperexponential распределению.

         Мы моделируем неравновероятностный доступ к данным с помощью двух дополняющих подходов: преимущества доступа к реплицированным данным и локальной модели доступа. Локальная модель доступа охватывает предпочтения доступа к локальным данным, так как без репликации, но из-за хорошо фрагментированных и размещённых данных, транзакции проявляют поведение локальности в том смысле, что они проявляют тенденции к получению данных доступных на локальном узле. Данное свойство смоделировано с помощью показателя вероятности loci[0;1] (1<=i<=τ), который показывает, что транзакция типа i может быть выполнена на локальном узле, (1-loci)  - вероятность того, что транзакцию необходимо будет перенаправить на удалённый узел. Введение 2-мерной репликации (r1,r2) увеличивает вероятность доступа к локальным данным на значение (r1*r2)/n. Из-за использования подхода Primary copy, вероятность записи не изменяется.

 

4.4 Качество репликации.

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

 

Обновления: Наша модель принимает во внимание, что запросы на обновление выполняются на основной копии и затем распространяются на другие копии в асинхронном режиме. Таким образом, для запросов на обновление показателем, влияющим на скорость их выполнения, является местоположение главной копии, а не ведомых копий. Однако выбор данных для репликации оказывает гораздо большее влияние. Выбор данных для репликации, которые должны часто обновляться вызывает повышенную загрузку сети во время распространения изменений на ведомые копии. Таким образом «функция выбора данных» seli для 1<=i<=τ и q(i) = 0, выражает до каких пределов, обновления типа i имеют  тенденцию к доступу к данным которые были выбраны для репликации. Первый аргумент функции r1 – так как увеличение доли реплицированных данных приводит к увеличению не только интенсивностей запросов на выборку данных, но и к увеличению интенсивностей запросов на изменение данных. Второй аргумент функции – входной параметр f_seli [-∞;1] и сама функция выглядит следующим образом:

 

         Sel(r1,f_seli) = 1/(r1)^f_seli               [0;1/r1]

 

Значение Seli влияет на поведение функции издержек на обновление ведомых копий при возрастании части r1 данных выбранных для репликации. Параметр f_sel предназначен для подстройки скорости, с которой издержки обновлений увеличиваются.

 

При f_seli -> -∞  seli->0, что говорит о том, что была возможность выбрать данные для репликации которые не обновляются, т.е данные которые не будут изменяться при работе системы. В случае f_sel = 0 (seli = 0), при работе системы не отдаётся предпочтения реплицированным либо локальным данным и доступ к обоим видам данных равновероятен. Значение f_sel = 1 (sel = 1/r)  говорит о том, что данные для репликации выбраны настолько неудачно, что в рамках каждой транзакции на обновление производится доступ к ним, что приводит к сильной нагрузке всей системы из-за распространения обновлений. Естественным показателем загрузки системы распространением обновлений является интенсивность входного потока заявок (транзакций). Если параметр f_sel = 0, нагрузка, вызываемая распространением обновлений, возрастает линейно вместе с увеличение доли реплицированных данных, что обычно происходит в моделях, где не учитывается качество выбора данных для репликации. «Плохой» выбор данных для репликации приводит к нелинейному и быстрому возрастанию нагрузки с увеличением доли реплицируемых данных. «Хороший» выбор данных не приводит к значительному увеличению нагрузки на систему и функция возрастает «медленнее» линейной.

 

Запросы: (под запросом понимается запрос на выборку данных)

Кроме того, что выбор данных для репликации оказывает влияние на производительность обработки запросов, размещение копий оказывает большее влияние на обработку запросов. Даже если все данные, к которым наиболее вероятен доступ, реплицированы, производительность всей системы не будет значительно увеличиваться, пока эти данные не будут доступны для запросов на локальных узлах. Таким образом «функция размещения» plcmti для 1<=i<=τ и q(i) = 1 выражает, до какого предела размещение копий увеличивает вероятность локального выполнения запроса типа i. Первый аргумент функции уровень репликации – (r1*r2)/n, т.к чем выше уровень репликации тем более увеличивается вероятность локального выполнения запроса. Второй аргумент функции входной параметр f_plcmti [0;1]. Сама функция определена следующим образом.

 

Plcmt (r1,r2,n,f_plcmti) = 1 / (degree) ^f_plcmti [1;n/(r1*r2)]

 

Значение f_plcmti = 0 (plcmt = 1) значит, что местонахождение копий не обязательно увеличивает шансы запроса i быть выполненным локально.  Значение f_plcmti = 1 (plcmt = n / r1*r2) означает, что запросы типа i могут всегда быть выполнены на локальном узле. Промежуточные значения f_plcmt приводят к средним показателям локальной доступности данных. Предполагая, что копии распределены случайно между узлами, каждый узел получает равную долю перенаправленных запросов и распространяемых обновлений. Таким образом, общая вероятность того, что транзакция типа i может быть выполнена на локальном узле:

 

Li = loci + qi*(1-loci) *(r1*r2/n)*plcmti

 

Без репликации транзакция выполняется на локальном узле с вероятностью loci (первая часть выражения). Вторая часть добавлена только для запросов (q = 1), т.к подход «главной копии» не увеличивает вероятности локального выполнения запросов на обновление. Вторая часть выражения также доказывает факт, что часть запросов, которая не может быть выполнена локально без репликации («потенциальные удалённые запросы»), может, тем не менее, быть выполнена локально в зависимости от уровня репликации и качества размещения копий. Если выбрана объективная выборка копий (худшая оценка?) f_plcmt = 0, вероятность локального выполнения удаленных запросов возрастает линейно, вместе с увеличением общего уровня репликации, обычно такое происходит в моделях, которые не учитывают качество схемы репликации. В модели 2rc промежуточные значения f_plcmt могут выразить, как лучший выбор размещения может повлиять на нелинейное увеличение вероятности локальной обработки удалённых запросов, даже при невысоких уровнях репликации. Такое поведение модели охватывает хорошо известный феномен – при пошаговом увеличении кэш-памяти увеличение вероятности того что необходимые данные также находятся в кэше также увеличивается скачкообразно. Т.к репликация может рассматриваться как одна из форм кэширования данных, модель локального нахождения и качества репликации  является адекватной аппроксимацией эффекта, который репликация оказывает на локальную доступность данных. В таблице приведены возможные значения и пределы параметров для моделирования качества репликации.

 

	Пределы	Лучшее значение	Объективное значение	Худшее значение
F_sel	[-∞;1]	-∞	0	1
Sel	[0;1/r1]	0	1	1/r1

 

	Пределы	Лучшее значение	Объективное/худшее
F_plcmt	[0;1]	1	0
plcmt	[1;n/(r1*r2)]	n/(r1*r2)	1

 

Интервал параметра f_plcmt начинается от 0, а не от –∞ т.к модель допускает что местонахождение копий не может уменьшать вероятность локального выполнения запроса. Однако отрицательные значения могут быть использованы для моделирования настолько плохой выборки копий, при котором на локальных узлах размещаются реплицированные данные, к которым доступ с этих узлов не производится. Значение f_plcmt = 0 является хорошим для моделирования систем с высоким уровнем репликации. Математически это происходит из-за того, что оптимальное значение для функции plcmt сходится к 1 при увеличении уровня репликации. На интуитивном уровне понятно, что при увеличении уровня репликации тяжелее спроектировать систему с неудачным выбором размещением копий. Аналогично при выборе большой доли данных для репликации труднее спроектировать систему с плохими показателями выборки данных для репликации.

4.5 Обработка транзакций и интенсивности входных потоков.

Модель обработки транзакций в системе построена на основе модели «primary copy». Обновления распространяются асинхронно на ведомые копии, таким образом, в модели не учитывается 2-фазное подтверждение обновлений. Также в рамках одной транзакции доступ может быть произведён только к локальным или только к удалённым данным.

         Производительность реплицированной базы данных может быть улучшена за счёт ослабления требования того что, данные должны быть абсолютно одинаковыми во всех репликах. Различные концепции ослабленной взаимосвязи могут быть выделены по различным условиям связи, которые позволяют ввести понятие индекса когерентности k [0;1] как меру допустимого уровня различий между копиями. Малые значения индекса позволяют моделировать системы со слабой когерентностью, при k = 0 моделируется система с отложенной синхронизацией. При k = 1 все обновления сразу распространяются по копиям данных. К примеру, вместо немедленного распространения обновлений, обновление части данных х могут распространяться на вторичные копии с периодичностью m единиц времени. Если х обновляется λ(х, u) раз в секунду, не каждое обновление должно быть распространено на ведомые копии, а только последнее состояние данных. Реальная вероятность распространения

         k = 1 / ((λ (x,u) * m) + 1)

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

(1)За счёт того что используется модель локального доступа часть(l) транзакций могут быть выполнены локально (первая часть выражения), а оставшаяся часть транзакций (1-l) перенаправляется на узлы содержащие необходимые данные.

(2)N-1 узлов также перенаправляют (1-li)* λ своих транзакций, которые будут получены каждым из узлов БД с равной вероятностью 1/(n-1).

(3)Если транзакция типа i является обновлением (т.е 1 – qi = 1) интенсивность входного потока увеличивается за счёт распространения копий с n-1 узлов. Вероятность того что обновление затронет данные, которые реплицированы равна r1*seli. Вероятность того что корреспондирующая ведомая копия находится на локальном узле - (r2-1)(n-1) т.к r2-1 реплик распределены случайно на n-1 узле. Благодаря ослабленной когерентности (k<1) формула может быть упрощена.

Следует отметить что r1*seli (вероятность того что обновление затронет реплицированные данные) = r1 для несмещённой выборки данных (seli = 1). Это значение нулевое если оптимальный выбор данных для репликации сделан таким образом, что данные которые могут изменяться не затронуты репликацией, и значение 1 если обновления всегда затрагивают реплицированные данные. Таким образом, в модели с частичной репликацией наихудший выбор данных для репликации, приводит к тому же результату, как и выбор всех данных для репликации.

 

 

4.6 Связь между узлами

Два сообщения необходимы для выполнения транзакции на удалённом узле: посылка и возврат, т.е запрос должен быть послан на удалённый узел и от узла должен прийти ответ. Мы считаем, что для каждого типа транзакции i задержка передачи сообщения для посылки (возврата) не постоянна  и распределена экспоненциально со средними значениями t(c,send_i) и t(c,return_i) секунд соответственно. Выбор экспоненциального распределения вызван тем, что мы ожидаем, что количество малых и средних сообщений будет превышать количество больших сообщений. Данные средние значения в основном зависят от пропускной способности сети и размера сообщений. Параметр bps показывает пропускную способность сети в битах в секунду, а параметры size(c, send_i) и size(c, return_i) означают среднее значение длины (размера) сообщения в байтах для транзакции типа i. Средние значения t(c,send_i) и t(c,return_i)  определены следующим образом:

 

Среднее число сообщений в распределённой системе:

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

В отличие от многих моделей, модель 2rc учитывает ограниченность сети как накопителя данных. Каждый локальный узел подключен к сети через собственный коммуникационные сервер, который моделируется как СМО M/H2τ/1. Интенсивность входного потока на каждом из таких серверов N / n сообщений в секунду, т.к каждый узел отправляет и получает одинаковое количество сообщений в следствии идентичности серверов и симметричности их поведения (В следствии предположения об однородности системы). Время обслуживания имеет распределение H2τ, т.к τ типов транзакций предполагают 2τ различных типов сообщений: τ типов сообщений имеют экспоненциальное распределенное время обслуживания со средним временем t(c, send_i),и τ типов сообщений со средним временем t(c, receive_i). Из выражения * следует, что доля сообщений со временем обслуживания t(c, send_i) равна

Доля сообщений со временем обслуживания t(c, receive_i).

Отсюда, первый и второй моменты H2τ распределение времени обслуживания могут быть получены следующим образом:

и

Среднее время ожидания W на локальном сервере связи может быть получено с помощью формулы Pollaczek-Khinchin для СМО типа M/G/1

где

        

        

4.7 Критерий производительности

Критериями производительности модели являются: среднее время отклика и пропускная способность системы. Аналогично расчёту среднего времени Wc, среднее время ожидания W на локальном узле может быть вычислено как:

Откуда следует, что общее среднее время отклика для всех типов транзакций:

 

где

В среднем транзакция должна ожидать W секунд в БД, прежде чем получить доступ к ресурсу на ti секунд. Дополнительно, с вероятностью 1-li транзакция должна быть перенаправлена на удалённый узел, что займёт дополнительно Wc секунд, ко времени посылки и возврата результата.

В стабильном состоянии, пропускная способность локального узла равна интенсивности входного потока, но ограничена верхней границей ёмкости системы. Пропускная способность может возрастать до тех пока либо сервер базы данных либо сервер связи (сеть), не будут нагружены полностью, т.е их загрузка достигнет 1.(Pd и Pc соответственно). Т.к загрузка равна произведению интенсивности входного потока и среднего времени обслуживания, загрузка pd локального узла БД может быть выражена следующим образом:

Считая, что pd = 1 и решая уравнение относительно λ, мы получаем показатель максимальной производительности базы данных Td

Нагрузка Рс локального сервера связи

Решая уравнение при Рс = 1 (максимальная нагрузка сети).

 

Максимальная пропускная способность узла системы T = min(Tc,Td), т.к независимо какого предела производительности система достигнет быстрее(БД или сети), дальше общая производительность расти не будет. Общая пропускная способность системы равна n*T.