Анализ процессов обработки версий записи в базах данных NoSQL

Тип работы:
Реферат
Предмет:
ТЕХНИЧЕСКИЕ НАУКИ


Узнать стоимость

Детальная информация о работе

Выдержка из работы

Наука к Образование
МГТУ им. Н.Э. Баумана
Сетевое научное издание
ISSN 1994−0408
Наука и Образование. МГТУ им. Н. Э. Баумана. Электрон. журн. 2015. № 01. С. 128−136.
DOI: 10. 7463/0115. 753 706
Представлена в редакцию: 08. 01. 2015
© МГТУ им. Н.Э. Баумана
УДК 004. 657
Анализ процессов обработки версий записи в базах данных NoSQL
профессор, д.т.н. Григорьев Ю. А. 1,
1 *
Цвященко Е. В. '-
& quot- euaene. tsvia shchenko @ gmaiLcom
1МГТУ им. Н. Э. Баумана, Москва, Россия
В статье рассмотрены процессы обработки версий записей. Представлен алгоритм ведения версий записей в базах данных NoSQL. Разработана модель обработки версий записи при одновременной работе пользователей с записью. Модель позволяет оценить время согласования, а также число версий записи, одновременно существующих в базе данных. Представлено два варианта модели. В первом варианте время обработки пользователем версий записи рассчитывается из числа версий, считанных пользователем. Во втором варианте время обработки рассчитывается из числа обновлений, выполненных другими пользователями между последовательными обновлениями записи текущим клиентом. Представлен анализ модельных экспериментов.
Ключевые слова: база данных NoSQL, версии записи, вектор часов, модель согласования, доверительный интервал
Введение
Для повышения производительности и отказоустойчивости автоматизированных информационных систем (АИС) в настоящее время все чаще используются системы баз данных (БД), построенные на парадигме распределенных хранилищ «ключей/значений», получивших название NoSQL (Not-Only-SQL) [1]. В базах данных NoSQL не поддерживается режим ведения транзакций, поэтому возникает проблема согласования данных. Поддержание требуемого уровня согласованности для каждой конкретной предметной области может регулироваться параметрами (N, W, R) [2].
При слабой согласованности, когда W+R& lt-N, пользователи могут одновременно обновлять записи с одним и тем же ключом, следовательно, система будет хранить несколько версий данной записи. В этом случае возникает проблема согласования версий (конфликт обновления). Базы данных NoSQL поддерживают механизм ведения вектора часов (Vector Clock — VC) [2] для каждой версии записи, хранящейся в БД, который содержит информацию о пользователях, выполнявших изменения данной версии записи.
При чтении пользователь получает все версии записи с данным ключом, обрабатывает их и сохраняет новую версию записи, при этом старые версии удаляются из хранилища.
При увеличении числа версий записи возрастает время их согласования клиентами (просмотр и объединение). В статье рассматривается механизм ведения вектора часов, предлагается имитационная модель обновления какой-либо записи, параллельно обрабатываемой пользователями. Рассматриваются два варианта модели, в которых по-разному рассчитывается время обработки пользователем считанных записей. Исследуется время согласования версий записи и число версий, одновременно хранящихся в хранилище NoSQL. Приводится анализ полученных результатов.
1. Ведение версий записи и вектора часов в NoSQL системах
При наличии нескольких узлов возможны конфликты данных, т.к. многие клиенты могут одновременно обновлять записи (документы), имеющие одинаковые ключи и хранящиеся в разных репликах. Конечно, подобные конфликты можно разрешить, если каждую запись базы данных снабдить временной меткой и отдавать предпочтение той версии записи, у которой метка самая последняя. Однако в кластере узлов это решение будет работать, если все часы точно синхронизированы, что часто является невыполнимой задачей.
СУБД NoSQL типа Шак [3] предоставляет механизм, позволяющий разрешать конфликты, используя так называемые векторные часы. Векторные часы — это последовательность пар & lt-пользователь, номер версии записи для этого пользователя& gt-, которая описывает порядок обновления этой записи. Кратко рассмотрим алгоритмы формирования векторных часов и обновления записей [4].
Пусть {А^ - множество идентификаторов пользователей (клиентов), обновляющих записи базы данных. Рассмотрим два варианта.
Случай 1. Пользователь Am е{А^ добавляет новую запись. Для этой записи СУБД установит следующий вектор часов: VC= АЦ1], где 1 — номер версии записи для пользователя А^
Случай 2. Пользователь Am читает запись по ключу, а затем обновляет её. Ниже приведены алгоритмы формирования вектора часов и обновления записи в базе данных для этого случая.
1. Алгоритм 1 формирования вектора часов VC новой версии записи.
Вход: Am — идентификатор пользователя, который читает запись. ^Си}, VCn = {А1^]}и — вектор часов прочитанной пользователем Am и-ой версии записи (при чтении пользователь Am получает все версии записи с тем же ключом). Алгоритм: К = 0- VC = 0-
ДЛЯ каждой прочитанной п-ой версии записи ЕСЛИ АтЫ е VCn, ТО VC = VC и (УСп — АтЫ) — К = тах (К, jn) — КОНЕЦ ДЛЯ УС = УС и Лт[К + 1]). 2. Алгоритм 2 обновления записи в базе данных.
Вход: ^Сп}, УСп= {Л^]}п — вектор часов существующей в базе данных п-ой версии записи (не обязательно прочитанной пользователем). VC = -
сформированный алгоритмом 1 вектор часов новой версии записи. Алгоритм:
ДЛЯ каждой существующей в базе данных п-ой версии записи
ЕСЛИ УМ: АмИ е УСп (АМ[К] е VC и L & lt- К), ТО удалить существующую п-
ую версию записи из базы данных-
КОНЕЦ ДЛЯ
Включить в базу данных новую запись с вектором часов VC и с тем же ключом. Из последнего алгоритма следует, что для записи с одним и тем же ключом в базе данных могут одновременно храниться несколько версий записей. В этом случае при чтении записи по этому ключу пользователь получает все версии записи. На рис. 1 представлен пример обновления записи с использованием вектора часов.
Запись й добавлена пользователем Ач
Р (Д1[1])
Запись й обновлена пользователем А1
Запись й обновлена О (Ач[2]) пользователем, А одновременно с
Запись й обновлена пользователем А3 одновременно с Д2
й1(А1[2], А2[1])
й2(А1[2], Аз[1])
Запись й согласована и обновлена пользователем А1
й (А1[3], А2[1], Аз[1])
Рис. 1. Пример использования вектора часов
Запись D (например, какой-то документ) обновляется пользователями A1, A2, A3. В скобках показан вектор часов записи. Первые два обновления выполняются пользователем A1 последовательно. Далее пользователи A2, A3 одновременно обновляют эту запись (случайное совпадение). В базе данных сохраняются две версии записи: D1 и D2. При чтении документа D пользователю A1 возвращаются две версии записи с одним и тем же ключом (D1 и D2). Он вносит изменения, например, объединяет обновления, выполненные клиентами A2, A3, или добавляет новые обновления. В базе сохраняется одна версия записи с вектором часов, включающим идентификаторы трёх пользователей.
С течением времени длина вектора часов растёт. В NoSQL существуют механизмы, позволяющие его «обрезать» [2]. При увеличении числа версий записи, одновременно хранящихся в базе данных, возрастает время их согласования клиентами (просмотр, обновление или объединение). В статье разработана модель оценки времени работы какого-либо клиента с этими версиями.
Распределение числа версий записи, одновременно хранящихся в NoSQL, сложно представить в аналитическом виде. Поэтому в работе используется имитационный подход к моделированию. Оцениваются характеристики случайного числа версий записи и времени их обработки пользователем.
2. Модель обновления версий записи (вариант 1)
Представим процесс обработки клиентом версий записи в виде следующих шагов:
1. Приложение получает все версии с тем же ключом (читает пары «ключ/значение») и предлагает их клиенту в форме, удобной для анализа.
2. Клиент анализирует эти версии и обрабатывает их согласно своей роли: объединяет мнения других пользователей (данный клиент играет роль руководителя группы), вносит свои предложения (клиент является рядовым членом группы) и т. д.- назовём это время временем обработки.
3. Приложение сохраняет обновлённую запись в базе (NoSQL формирует вектор часов, может быть удаляет старые версии записи, добавляет в базу данных новую версию).
4. Клиент через некоторое время возвращается к ранее откорректированной записи (документу) — назовём это время временем обдумывания. Перейти к шагу 1.
Время реализации шагов 1 и 3 намного меньше времени выполнения шагов 2 и 4, поэтому это время в модели не учитывается.
На рис. 2 представлена схема работы модели.
Источники работы с записью (клиенты)
1
2
N
Тп
З
анять позицию в
массиве
Массив обработки версий записи
01
02
W
Число версий записи
Рис. 2. Модель обработки версий записи
0п
Занять позицию в источнике
На рис. 2 приняты следующие обозначения:
X — параметр экспоненциального закона распределения времени обдумывания клиентом (1. результатов работы с версиями записи,
Т — момент поступления требования на чтение версий записи от 1-го источника
Ж
(клиента): 1-й клиент читает W версий записей, ф = ^^ - время обработки всех версий
1
записи клиентом, — случайное время обработки, связанное с одной версией записи, W — текущее число версий записи в базе данных NoSQL.
Массив обработки версий записи содержит один столбец. Значение Qi — это число версий записи, которые необходимо удалить из базы данных в момент, когда 1-й источник покидает фазу обработки.
В табл. 1 приводится описание алгоритма работы модели.
Описанный в табл. 1 алгоритм был реализован в среде GPSS [5]. GPSS является средством моделирования параллельных процессов. Система позволяет задавать различные распределения вероятностей для случайного времени пребывания в источнике
(времени обдумывания) и времени обработки клиентом одной версии записи, а также имеет встроенные механизмы сбора статистики и построения гистограмм.
Таблица 1. Алгоритм модели по варианту 1
№ Пункт алгоритма Примечание
1 Положить W=1, массив обработки пуст. Новая запись включена в БД.
2 & gt-ое требование поступает на обработку. Наступил момент времени тг
3 Сохранить текущее число версий записи в _|-ой строке массива: QJ = W, определить ф, задержать транзакт (требование) на время ф (обработать записи). ]-й клиент читает W версий записи из базы данных, Г ф = ^, 4 — случайное время обработки, 1 связанное с одной версией записи.
4 Если очередное & gt-ое требование поступает на обработку, то перейти к пункту 3 алгоритма Наступило очередное время т
5 Если требование покидает массив обработки (пусть это будет ]-я строка массива), то выполнить следующие действия: а) W: = W — ^ + 1 Клиент) обработал прочитанные версии записи (затратив на это время ф), сформировал вектор часов, удаляет из БД все старые версии записи (если их ранее не удалил другой клиент, т. е. если Qj0), добавляет в БД свою версию записи (+1, см. алгоритм 2 ведения версий записи).
б) для всех строк массива обработки Ql := Ql — 3, если Ql & lt- 0, то положить Ql = 0 Учесть, что QJ, версий записи уже удалены из БД текущим ]-м клиентом и их не надо удалять 1-м клиентом (если Qj,^0). Затем покидающее 1-ое требование удалит ранее им считанные версии, которые остались не удалёнными, и увеличит число версий записей W на единицу (см. пункт 5а -другие версии записей, поступившие позже чтения записей 1-м клиентом, этот клиент удалить не может, т.к. они будут содержать в векторе часов новые номера версий других клиентов — это объясняет, почему только минус QJ в 5а).
в) задержать клиента на время обдумывания результатов работы с версиями.
6 Перейти к пункту 4 алгоритма
В качестве функции распределения вероятностей времени обработки клиентом одной версии записи использовалась функция, обратная следующей функции GPSS: VRF FUNCTION RN1, D7
0,0/. 125,1/. 375,2/. 5,3/. 625,8/. 875,9/1. 0,10 (1)
Плотность соответствующей функции распределения является двугорбой со средним значением, равным 5.5.
1А, — среднее время обдумывания (т.е. среднее время между последовательными чтениями версий записи) принималось равным величие k*t0, где t0 — среднее время обработки клиентом одной версии записи (t0=5. 5), k = 0. 2- 1- 3- 6.
На рис. 3 представлены результаты моделирования: средние значения числа версий записи (Wc) и времени обработки документа (версий записи) одним клиентом (Tc), N -число клиентов. Единицей измерения времени Tc (ось ординат) может быть секунда, минута, какая-то доля часа и т. д.
а) б)
Рис. 3. Среднее значение числа версий записи WС (а) и времени обработки версий записи клиентом ТС (б)
Можно заметить, что с увеличением среднего времени обдумывания (т.е. с ростом ф среднее число версий записи уменьшается (рис. 3а) и стремится к 1 для каждого N. Причем, уменьшается тем быстрее, чем больше число клиентов, одновременно обрабатывающих запись. Соответственно уменьшается и среднее время обработки версий записи (рис. 3б). Ясно, что при этом функция распределения вероятностей времени обработки этих записей стремится к закону, определённому функцией (1).
Рассмотренная модель не учитывает в явном виде того, что время обработки версий записи зависит от числа обновлений, выполненных другими клиентами между последовательными обновлениями записи данным клиентом. Поэтому предлагается второй вариант модели обработки версий записи.
3. Модель обработки версий записи (вариант 2)
Модель отличается от предложенной ранее тем, что в массив обработки добавляется столбец (иь. ип), который содержит количество обновлений записи другими источниками (клиентами), выполненных между последовательными обновлениями записи данным клиентом. Время обработки рассчитывается не как сумма по W, а как сумма по и В таблице 2 приводится описание алгоритма работы модели.
Таблица 2. Алгоритм модели по варианту 2
№ Пункт алгоритма Примечание
1 Положить W = 1, массив обработки пуст Новая запись включена в БД.
2 & gt-ое требование поступает на обработку Наступил момент времени т
3 Сохранить текущее число версий записи в ]-ой строке массива: QJ = W, определить ф, положить и1=0, задержать требование на время ф (обработать обновления записи). ]-й клиент читает W версий записей, и] +1 ф = ^, 4 — случайное время обработки 1 клиентом одного обновления записи, и1 — число обновлений, выполненных другими клиентами.
4 Если _|-ое требование поступает на обработку, то перейти к пункту 3 алгоритма. Наступило очередное время т
5 Если требование покидает массив обработки (пусть это будет _|-я строка массива), то выполнить следующие действия: а) W = W — 3 + 1 б) для всех строк массива Ql = Ql — если Q1 & lt- 0, то положить Q1 = 0, если 1 & lt->- то увеличить и1 на 1 г) задержать клиента на время обдумывания результатов работы с версиями. См. примечание в таблице 1. См. примечание в таблице 1. Накапливать для 1-го клиента число обновлений, выполненных другими клиентами.
6 Перейти к пункту 4 алгоритма
Исходные данные модельных экспериментов совпадают с данными для варианта 1. В качестве функции распределения вероятностей времени обработки клиентом одного обновления, выполненного другим клиентом, использовалась функция, обратная (1). Результаты моделирования представлены на рис. 4 и рис. 5.
160 ТС 140 120 100 80 60 40 20 0
X X





п-1−1-1
0.2 1 3 6
к
N=5 10 20 30
а) б)
Рис. 4. Среднее значение числа версий записи Wc (а) и времени обработки версий записи клиентом ТС
(б)
а) б)
Рис. 5. Правая граница доверительного интервала (уровень надёжности 0,95) числа версий записи Wпp (а) и времени обработки версий записи клиентом Тпр (б)
Неожиданный результат — зависимость Wc от «к» имеет выраженный максимум (рис. 4а). С увеличением времени между последовательными чтениями версий записи (времени обдумывания, т. е. с ростом «к») среднее число версий записи стремится к 1 для каждого К, как и в варианте 1, но очень медленно. Так при К=100 Wc=1, 2, 3, 4 соответственно для К= 5, 10, 20, 30. Из графика видно, что среднее значение времени обработки версий записи (ТС) (рис. 4б) практически постоянно для каждого N. Это можно объяснить так. За промежуток времени 1 между последовательными чтениями версий записи клиентом в среднем будет выполнено ^К-1)Л=К-1 обновлений, что и объясняет отсутствие зависимости ТС от «к». Причём чем выше К, тем выше корреляция между количеством обновлений, выполненных за время обдумывания, для разных клиентов. Для N=30 ТС= 142. 4, а не (30−1)(1−0=5. 5)= 160, как следовало ожидать. Эта тенденция сохраняется с ростом к. Так при к=100 ТС=23. 7, 47. 5, 95. 0, 142.5 для К= 5, 10, 20, 30.
Правая граница доверительного интервала времени обработки версий записи (уровень надёжности равен 0. 95) имеет минимум (рис. 5б) — это тоже любопытный результат.
С ростом «к» Тпр сначала убывает, а затем возрастает (см. вертикальную линию справа для к=100). Так Тпр =520 для к=100 и N=30. Это означает, что за один цикл работы какого-либо клиента (время между чтениями версий записи + время их обработки) другой клиент (ы) может обновить запись несколько раз.
Заключение
1. Разработана имитационная модель анализа времени обработки версий записи. Модель предусматривает параллельную обработку клиентами записи с одним и тем же ключом, хранящейся в распределенной системе КоБОЬ. Предложены два варианта модели. Согласно первому варианту, время обработки клиентом версий записи зависит от количества версий, считанных из базы данных КоБОЬ. Согласно второму варианту, время обработки клиентом версий записи зависит от числа выполненных обновлений записи другими клиентами между последовательными чтениями версий записи данным клиентом.
2. Выполнены модельные эксперименты в среде ОРББ. Анализ результатов показал, что несмотря на внешнее сходство вариантов модели, характер изменения средних значений числа версий записи и времени их обработки существенно различается.
3. Во 2-м варианте зависимости среднего числа версий записей в базе данных и его правой границы доверительного интервала и Wпp) от среднего времени обдумывания (т.е. от «к») имеют выраженный максимум (рис. 4а и 5а).
4. В этом же 2-м варианте среднее время обработки версий записи практически не зависит от среднего времени обдумывания (см. рисунок 4б). Но правая граница доверительного интервала этого времени имеет выраженный минимум (рис. 5б).
Список литературы
1. NoSQL. Википедия: Свободная энциклопедия. Режим доступа: http: //ru. wikipedia. org/wiki/NoSQL (дата обращения 07. 01. 2015).
2. Редмон Э., Уилсон Д. Р. Семь баз данных за семь недель. Введение в современные базы данных и идеологию NoSQL. М.: ДМК Пресс, 2013. 384 с.
3. Riak documentation. Режим доступа: http: //docs. basho. com/index. html (дата обращения 07. 01. 2015).
4. Григорьев Ю. А. Анализ свойств баз данных NoSQL // Информатика и системы управления. 2013.№ 2. С. 3−13.
5. GPSS World Reference Manual // Minuteman Software: website. Режим доступа: http: //www. minutemansoftware. com/reference/reference_manual. htm (дата обращения 07. 01. 2015).
Science and Education of the Bauman MSTU, 2015, no. 01, pp. 176−188.
DOI: 10. 7463/0115. 753 706
Received:
08. 01. 2015
Science^Education
of the Bauman MSTU
I SS N 1994−0408 © Bauman Moscow State Technical Unversity
Analysis of Handling Processes of Record Versions in NoSQL Databases
Yu-A-Grigorev1, E.V. Tsviashchenko1'-* & quot-eusene. ts^ashchenko@gmail. com
: Bauman Moscow State Technical University, Moscow, Russia
Keywords: NoSQL database, record versions, vector clock, consistency model, confidence interval
This article investigates the handling processes versions of a record in NoSQL databases. The goal of this work is to develop a model, which enables users both to handle record versions and work with a record simultaneously. This model allows us to estimate both a time distribution for users to handle record versions and a distribution of the count of record versions. With eventual consistency (W=R=1) there is a possibility for several users to update any record simultaneously. In this case, several versions of records with the same key will be stored in database. When reading, the user obtains all versions, handles them, and saves a new version, while older versions are deleted. According to the model, the user'-s time for handling the record versions consists of two parts: random handling time of each version and random deliberation time for handling a result. Record saving time and records deleting time are much less than handling time, so, they are ignored in the model. The paper offers two model variants. According to the first variant, client'-s handling time of one record version is calculated as the sum of random handling times of one version based on the count of record versions. This variant ignores explicitly the fact that handling time of record versions may depend on the update count, performed by the other users between the sequential updates of the record by the current client. So there is the second variant, which takes this feature into consideration. The developed models were implemented in the GPSS environment. The model experiments with different counts of clients and different ratio between one record handling time and results deliberation time were conducted. The analysis showed that despite the resemblance of model variants, a difference in change nature between average values of record versions count and handling time is significant. In the second variant dependences of the average count of record versions in database and its right bound of the confidence interval on the average deliberation time have a pronounced maximum. In the same variant an average handling time of record versions practically does not depend on the average deliberation time, but the right bound of the confidence interval of this time has a pronounced minimum.
References
1. NoSQL. Wikipedia, the free encyclopedia. Available at: http: //en. wikipedia. org/wiki/NoSQL, accessed 07. 01. 2015.
2. Redmond E., Wilson J.R. Seven Databases in Seven Weeks: A Guide to Modern Databases and the NoSQL Movement. Pragmatic Bookshelf, 2012. (Russ. ed.: Redmond E., Wilson J.R. Sem'- baz dannykh za sem'- nedel'-. Vvedenie v sovremennye bazy dannykh i ideologiyu NoSQL. Moscow, DMK Press, 2013. 384 p.).
3. Riak Docs: Riak documentation. Available at: http: //docs. basho. com/index. html, accessed 07. 01. 2015.
4. Grigor'-ev Yu.A. Analysis of NoSQL database properties. Informatika i sistemy upravleniya = Information Science and Control Systems, 2013, no. 2, pp. 3−13.
5. GPSS World Reference Manual. Minuteman Software: website. Available at: http: //www. minutemansoftware. com/reference/reference manual. htm, accessed 07. 01. 2015.

ПоказатьСвернуть
Заполнить форму текущей работой