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

Недостатком является переносчасти функций базы данных на клиентскую машину, а, следовательно, ростобъема хранимых данных, наличие дополнительной задержки на синхронизациюлокального и общего хранилища данных.Такой подход можно использовать для узкого круга приложений, например,для уточнения целей при поиске данных. Согласованность в конечном счете (КСсогласованность) не рассматривалась.В статье [41] предлагается метод LibRe согласованности данных в базахданных NoSQL. Метод основывается на согласованности в конечном счете.Задача состоит в том, чтобы сочетать высокую доступность данных с высокимуровнем согласованности данных.

Например, если N=3, W=1, R=1, то имеет местоКС-согласованность, т.к. W+R≤ N. Подход, предлагаемый в статье, позволяетусилить согласованность. LibRe расшифровывается как Library For Replication.Подход заключается в следующем. Управляющий модуль LibRe располагаетсярядом с балансировщиком загрузки. Балансировщик загрузки перед каждойоперацией записи/обновления передает LibRe набор узлов, на которых возможновыполнить операцию. После выполнения операции LibRe хранит некоторое времяинформацию о том, какой узел ее выполнил.

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

Реестр может стать «узким местом».LibreРеестрFrontEndLibreМенеджер извещенияМенеджер доступностиБалансировщикзагрузкиКластерРисунок 1.14 – Расположение libre в системе.В работе [42] описывается механизм PAXOS обеспечения согласованности враспределенныхбазахданных.Подходосновываетсянасогласованной(consensus) репликации. Алгоритм согласования реплик в классическом варианте(paxos basic) заключается в следующем:1. Конкретная реплика (сервер) назначается в качестве координатора.2. Координатор выбирает запись и рассылает ее всем репликам дляподтверждения, принимающий сервер может принять запись илиотказать.363.

Как только большинство реплик приняли новую запись, согласованиедостигнуто и всем репликам высылается команда о подтвержденииоперации (commit).При необходимости пункты 1-3 могут быть повторены (из-за отказа сети).Координатор может также отказать. Но paxos не требует, чтобы координатор былединственным, в любой момент координатором может стать другая реплика.В статье [43] предлагается метод обеспечения причинной согласованностисо сходящейся обработкой конфликтов (CAUSAL+CONSISTENCY). Данный видсогласованностиявляетсярасширениемклассическойпричиннойсогласованности. Классический метод причинной связи не рассматриваетконкурирующие операции обновления, т.е.

операции работы над одним ключом,например, put(x, a) и put(x, b). Потенциальной причинной связи между этимиоперациями нет. Следовательно, в КС-согласованной системе возможныконфликтыирассогласованияприопределенныхусловиях.Конфликтынежелательны по двум причинам: во-первых, реплики могут логически«разойтись», во-вторых, полученные расхождения могут логически исключатьдруг друга, что требует специальной обработки. Предложенное в [43] расширениеклассическогометодазаключаетсявовведениисходящейсяобработкиконфликтов.

Обработкой конфликтов занимается специальная функция h,запускаемая для каждой реплики. Функция должна быть коммутативной иассоциативной. Сходимость заключается в равенстве результатов выполненияфункций h(a, h(b,c)) на одной реплике и h(c, h(b, a)) - на другой, где a→b→c –некоторая последовательность операций обновлений и чтений (put и get).Преимущества метода: усиление согласованности данных за счет введениякоммутативной и ассоциативной функции обработки конфликтов.Недостатки: обнаружение конфликтов является сложной задачей, решениекоторой вносит существенные задержки в работу системы.

Например, одним изтрех компонентов системы обнаружения конфликтов является введение явнойпричинной связи между операциями put текущей и предыдущей версии записи,37чтотребуетвыполнениядополнительнойоперацииdep_check(проверказависимости).1.4.2. Анализ моделей и методов оценки характеристик согласованияреплик NoSQLВ работе [90] был выполнен анализ существующих моделей и методовоценки показателей согласования реплик NoSQL.Вработе[44]показателиКС-согласованностиизмерялисьэкспериментально. Эксперимент состоял в последовательном считывании записидо того момента, пока устаревшее значение не перестанет возвращаться. Разницамеждувременемпоследнегосчитыванияустаревшейверсиипары<ключ/значение> и временем последнего обновления записи отражала окнорассогласованности.Для экспериментов была разработана очень простая система хранения суровнем репликации N=3, W=1, R=1.

Для наглядности была добавленаискусственная задержка перед реплицированием (тиражированием) данных,равная 1000 мс. Обновление выполнялось раз в 5 секунд, чтение – раз в 10миллисекунд. Каждые 10 минут добавлялся читающий процесс. Таким образом,их число в ходе эксперимента изменялось от 1 до 12.Сравнивались размеры окон рассогласованности, полученные из журналовбазы данных NoSQL, с результатами проведенных экспериментов.

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

Модели не разрабатывались, поэтому не ясно, насколькосделанные выводы являются общими.38В работе [45] предлагается подход к количественному измерениюпоказателей согласованности через «вероятностно ограниченное устаревание»записи (пары <ключ, значение>). Вероятностно ограниченное устареваниеоценивается следующими показателями: k-устаревание, t-видимость и (k,t)устаревание.Вероятность, что считанный из распределенного хранилища набор версийзаписей не будет содержать актуальную версию записи, является функцией,зависящей от времени. Однако формулаp  1  p sk  1  (C NR WC NR)k ,(1.3)определяющая вероятность того, что считанный из распределенногохранилища набор версий записей будет содержать версию из последних kобновлений, не учитывает распространение обновлений (вероятность не зависитот времени) [45].

Здесь N, W, R – параметры, регулирующие требуемый уровеньсогласованности. Эта ошибка повторяется и в других формулах [45] (например, вформуле 2 этой статьи).В формулеp  1  p skt  1  (C NR WC NRC NR cRc[W, N) C N[ Pw (c  1, t )  Pw (c, t )])k(1.4)авторы попытались учесть распространение обновлений во времени [45]. Ноонипредлагают получитьфункциюPw(c,t)спомощьюимитационногомоделирования или измерений, что на наш взгляд является нереальным (в [45] этафункция так и не была получена). Также в формуле (1.4) содержится элемент ps1из формулы (1.3) [45], который уже содержит ошибку. В формуле 4 статьи [45]ошибка вытекает из описанных выше рассуждений.

В формулах (1.3), (1.4) неучитывается интенсивность запросов на чтение. Таким образом, модель оценкипоказателей согласования реплик, предложенную в [45], нельзя признатьадекватной, что подтверждается результатами натурных экспериментов (см.раздел 3.4.2).391.4.3.

Анализ методов оценки показателей отказоустойчивости в базахданных NoSQLВ работе [94] был выполнен анализ существующих методов оценкипоказателей отказоустойчивости в базах данных NoSQL.В теории кворумов [46] рассматриваются византийские системы кворума,предполагающие наличие неисправных серверов в распределенной системе.Пусть дано множество серверов Z. Системой кворума над Z называетсямножество подмножеств D={Q1,...,Qm} такое, что каждое Qi ⊆Z и |Q∩Q’|> 0 длявсех Q,Q’ ∈ D. Каждое Qi называется кворумом.

Некоторые процессы пишутданные в кворумы (обновляют записи), другие процессы читают эти данные изкворумов. Условие |Q∩Q’|> 0 гарантирует, что процесс чтения будет получатьактуальные записи по крайней мере с одного сервера, т.е. система будетсогласованной.Пусть b>0 – общее число неисправных серверов, B – множествонеисправных серверов (которые не отвечают на запрос). Рассматриваются трислучая. Во всех случаях предполагается, что существует Q∈D такое что |B∩Q|=0.Без этого ограничения неисправные серверы могут препятствовать работесистемы, просто не отвечая, поскольку клиент, как правило, требует ответа откакого-либо полного кворума серверов, чтобы продолжить работу.Случай 1.

|Q∩Q’\B|> 0 для любых Q,Q’∈D. Это означает, что два кворумаимеют по крайней мере один общий исправный сервер.Случай 2. |Q∩Q’\B|>|Q’∩B|. Это означает, что пересечение кворумовсодержит больше исправных серверов, чем неисправных в каком-либо кворуме.Случай 3. |Q∩Q’\B|>|(Q’∩B)∪(Q’\Q)|.Имеет место теорема [47].Теорема 1. Пусть n=|Z| и пусть D – кворум над Z. Тогда для случая 1 - b< n/3; для случай 2 - b< n/4; для случая 3 - b< n/5.40Использование теории кворумов применительно к базам данных NoSQLнаталкивается на серьезные препятствия. В NoSQL отказ сервера не приводит кпотере реплики (копии): если узел отказывает, то реплика автоматическисоздается на другом узле.