Диссертация (Модели процессов согласования реплик в базах данных NoSQL), страница 11

При чтении записи будемполагать, что w=1.φkd(s) – ПЛС времени обновления хеш-таблицы (keydir) в ОП; не зависит отразмера значения, т.к. хеш-таблица строится по ключу, значение которого58соответствует структуре <идентификатор файла, длина значения, смещениезначения, временная метка>. Размер этой структуры - 20 байтов.kd ( s) m (20  k ) p 16m (20  k )  s  p 16  s,(2.31)(20+K) – учитывает передачу описанной структуры в памяти и передачуключа в кэш процессора для подсчета контрольной суммы.16 – учитывает, что количество процессорных операций, необходимых дляподсчета хеша примерно равно 16.Таким образом, ПЛС времени обновления реплики можно определить, как:i (s)   i ( s, r , t )  i ( s) ,гдеΛi(s,r,t)иΘi(s)(2.32)определяютсявыражениями(2.24)и(2.27)соответственно.Оценка среднего значения времени обновления реплики.Дифференцируя (2.32) как сложную функцию по s в 0, получимматематическое ожидание времени обновления i-ой реплики:MQmmQnnQns nsQd1 d1Qpp(2.33),Коэффициенты Q в числителях слагаемых представлены в таблице 2.1.Таблица 2.1 – Коэффициенты при средних величинах.QmQpQd1QnQns(k+v)(t+1)+3k+2v+484(k+v+12)+16wb2t(K+V)tr(K+V)Для типа репликации «master-slave» и «master-master» необходимоучитывать интервал времени Δt, через который slave-серверы опрашивают masterсервер и проверяют наличие обновлений (в некоторых базах данных, например,Hbase активными являются master-серверы).

Для получения ПЛС ΦΔ(s) интервалавремени от произвольного момента до момента начала опроса можновоспользоваться формулой Риордана (2.14). Предполагая, что Δt=const, получим591  e st  (s) .st(2.34)При наличии опроса сервера выражение (2.32) следует дополнительноумножить на (2.34).2.2. Анализ моделей процессов согласования реплик при обновлениикакой-либо записи базы данных2.2.1. Анализ моделей согласования реплик в конечном счетеНиже приведены результаты анализа вероятности, что клиент прочитаетустаревшую запись за время распространения обновлений записи по ее N-Wрепликам, для синхронного режима распространения изменений (формула (2.8)).Характеристики ресурсов (интенсивности обработки) были получены спомощью программы синтетических тестов AIDA64 [55]. Расчеты быливыполнены при следующих значениях характеристик ресурсов.1. Процессор – Mobile DualCore Intel Core i5-2450M, 2900 MHz.

Длявыбранного процессора измеренное значение числа процессорных циклов,выполняемых в секунду, равно μP=2900106 (1/с).2. Внешняя память - Momentus 5400 640423 Seagate <ST9640423AS>5400rpm 16Mb; интенсивность ввода/вывода данных на диск равна μd1 =13010241024 (байт/с).3. Оперативная память – DDR3-1333 PC3-10667. Интенсивность чтенияданных из ОП равна μm=984210241024 (байт/с).4.

Производительность локальной сети внутри сегмента равна 1 Гбит/с;интенсивность передачи данных по шине локальной сети равна μn=125106(байт/с).5. Производительность сети между ее сегментами составляет 128 Мбит/с;интенсивность передачи данных по шине сети, соединяющей подсети, равнаμns=16106 (байт/с).60На рисунке 2.6 показаны зависимости вероятности, что клиент прочитаетустаревшую запись за время распространения обновлений записи по ее N-Wрепликам, от интенсивности входящих запросов (требований) при различныхзначениях N (синхронный режим). Общее число физических узлов – 20, узлыразделены на два сегмента сети по 10 узлов в каждом. Число виртуальных узлов(v-узлов) – 64. Длина «k» поля ключа записи составляет 20 байтов, длина «v»поля значения равна 512 байтов.

W=R=1.Рисунок 2.6 – Зависимости вероятности, что клиент прочитает устаревшую записьза время распространения обновлений записи по ее N-1 репликам, отинтенсивности запросов на чтение λ (1/с) при различных N (синхронный режим).В базах данных NoSQL, например, RIAK [18] число реплик N каждойзаписи БД по умолчанию равно 3. В этом случае даже при больших λ вероятностьравна 0.03 (надежность согласования реплик составляет почти две девятки: 0,97).При больших N вероятность может достигать 0.3 при больших значенияхинтенсивности поступления требований на чтение.Рассмотрим вероятность,что клиент прочитает устаревшую запись завремя распространения обновлений записи поасинхронногорежимараспространенияее N-W репликам, дляизменений(формула(2.11)).61Характеристики ресурсов совпадают с описанными ранее. На рисунке 2.7показаны зависимости вероятности, что клиент прочитает устаревшую запись завремяраспространенияобновленийзаписипоееN-Wрепликам,отинтенсивности входящих запросов (требований) при различных значениях N(асинхронный режим обновления реплик).Рисунок 2.7 – Зависимости вероятности, что клиент прочитает устаревшую записьза время распространения обновлений записи по ее N-W репликам, отинтенсивности запросов на чтение λ (1/с) при различных N (асинхронный режим).В случае N=3 даже при больших λ вероятность не превышает 0.0004(надежность согласования составляет почти четыре девятки: 0,9996).Сравним вероятности доступа к несогласованным данным при синхронноми асинхронном режимах распространения изменений.

В таблице 2.2 приведенызначения вероятности, что клиент прочитает устаревшую запись за времяраспространения обновлений записи по ее N-W репликам, для различных величининтенсивности входящих запросов при больших значениях N (7 и 9) длясинхронного и асинхронного режимов. Здесь W=R=1.62Таблица 2.2 – Вероятность чтения устаревших записей.Синхронный режимАсинхронный режимN=7N=9N=7N=9λPPPP24681012141618200.039700.077530.113570.147940.180710.211990.241840.270340.297570.323580.067050.128960.186180.239100.288100.333490.375580.414640.450910.484620.00010.000210.000310.000410.000520.000620.000720.000830.000930.001030.000140.000280.000410.000550.000690.000830.000960.001100.001240.00138Из таблицы видно, что разница в вероятностях, рассчитанных с учетомсинхронного и асинхронного режимов достигает несколько порядков.2.2.2.

Анализ модели строгого согласования репликНиже приведены результаты модельных экспериментов по оценке времениожидания требованием на чтение окончания обновления W реплик (формула(2.21)). Расчеты были выполнены для следующих значений характеристикресурсов:1. Производительность локальной сети внутри сегмента равна 100 Мбит/с;интенсивность передачи данных по шине локальной сети равна μn=12.5106(байт/с).2. Производительность μns сети между ее сегментами не учитывалась(отсутствуют подсети).Остальные характеристики ресурсов совпадают с соответствующимизначениямиизпункта2.2.1.Нарисунке2.8показанызависимостиматематического ожидания (МО) времени ожидания требованием на чтениеокончания обновления W=N/2+1 реплик от интенсивности входящих запросов63(требований) при различных значениях N.

Длина «k» поля ключа записисоставляет 20 байтов, длина «v» поля значения равна 2048 байтов.Рисунок 2.8 – Зависимости МО времени ожидания требованием на чтениеокончания обновления W реплик от интенсивности запросов на чтение λ (1/с) приразличных N.Из рисунка 2.8 видно, что время ожидания требованием на чтениеокончания обновления W реплик при значении N=3 измеряется в десятых доляхмиллисекунды. Однако при больших N и большой интенсивности входящихтребований на чтение это время может достигать 3.2 мс.На рисунке 2.9 показаны зависимости МО времени чтения R реплик сучетом времени ожидания требованием на чтение окончания обновления Wреплик (W=R=N/2+1) от интенсивности входящих запросов при различныхзначениях N (см. формулу (2.22))64Рисунок 2.9 – Зависимости МО времени чтения R реплик с учетом времениожидания требованием на чтение окончания обновления W реплик отинтенсивности запросов на чтение λ (1/с) при различных N.2.3.

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

Возникаетпроблема согласования версий (конфликт обновления). Базы данных NoSQLподдерживают механизм ведения вектора часов (Vector Clock - VC) для каждой65хранящейся в БД версии записи, который содержит информацию о пользователях,выполнявших изменения данной версии записи. При чтении пользовательполучает все версии записи с данным ключом, обрабатывает их и сохраняетновую версию записи, при этом старые версии удаляются из базы данных. Приувеличении числа версий записи возрастает время их согласования клиентами(просмотр и объединение).Векторные часы – это последовательность пар <пользователь, номер версиизаписи для этого пользователя>, которая описывает порядок обновления этойзаписи. Рассмотрим механизм ведения вектора часов на примере базы данныхRiak [19].

Ниже приведены алгоритмы формирования векторных часов иобновления записей, описанные в [14, 18].Пусть {Ai} – множество идентификаторов пользователей (клиентов),обновляющих записи базы данных. Рассмотрим два варианта.Случай 1. Пользователь Am {Ai} добавляет новую запись. Для этой записибаза данных установит следующий вектор часов: VC= Am[1], где 1 – номер версиизаписи для пользователя Am.Случай 2.

Пользователь Am читает запись по ключу, а затем обновляет ее.Ниже приведены алгоритмы формирования вектора часов и обновления записи вбазе данных для этого случая (алгоритмы 1 и 2).1. Алгоритм 1 формирования вектора часов VC новой версии записи.Вход: Am – идентификатор пользователя, который читает запись, VCn ={Ai[j]}n - вектор часов прочитанной пользователем Am n-ой версии записи (причтении пользователь Am получает все версии записи с тем же ключом), {VCn} –множество векторов часов всех n версий записи, хранящихся в базе данных.Алгоритм:К = 0; VC = ;ДЛЯ каждой прочитанной n-ой версии записиЕСЛИ Am[jn]  VCn , ТО VC = VC  (VCn - Am[jn]);К = max(К, jn);КОНЕЦ ДЛЯ66VC = VC  Am[К + 1]).2.