Классификация сетей ЭВМ по способам распределения данных, сравнительная характеристика различных типов сетей
Существуют два основных способа распределения данных в сети - с помощью распределенных транзакций и с помощью репликации данных. В случае, если сеть ЭВМ является аппаратной основой распределенной системы, то такие сети можно классифицировать в соответствии с вышеуказанными способами распределения данных.
Рассмотрим способы распределения данных подробнее.
Транзакция - это сложная многоступенчатая операция, выполняющаяся как единый неделимый единовременный процесс.
Свойства транзакций:
1. Атомарность. Для окружающего мира транзакция неделима, то есть она либо полностью выполняется, либо полностью не выполняется, причем если она выполняется, то как одна неделимая одновременная операция;
2. Непротиворечивость. Транзакция не нарушает инвариантов (ключевых свойств) системы;
3. Изолированность. Одновременно выполняющиеся транзакции не влияют друг на друга;
4. Долговечность. После завершения транзакции результаты её работы неизменны.
Виды транзакций:
1. Плоская транзакция - это транзакция, строго удовлетворяющая четырем вышеизложенным свойствам транзакций;
2. Вложенная транзакция - это транзакция, состоящая из дочерних транзакций, способных работать параллельно без взаимных блокировок (у дочерних транзакций отсутствует свойство долговечности);
3. Распределенная транзакция - это набор плоских транзакций, совместно выполняющих одну общую задачу.
При реализации транзакции на локальной ЭВМ, процесс, её выполняющий, получает закрытое рабочее пространство оперативной памяти, в котором производит все промежуточные действия до тех пор, пока транзакция не выполнится или не прервется.
При реализации распределенных транзакций на различных ЭВМ сети, необходим алгоритм управления для сохранения свойств транзакций. Для управления распределенными транзакциями служат три иерархических процесса:
1. Менеджер данных. Менеджер данных находится на верхнем уровне иерархии и осуществляет транзактнонезависимые операции чтения и записи данных;
2. Планировщик. Планировщик определяет, в какой момент времени и какой транзакции разрешается передать операцию чтения или записи менеджеру данных;
3. Менеджер транзакций. Менеджер транзакций находится на нижнем уровне иерархии и обрабатывает команды транзакций, преобразуя их в запросы к планировщику.
Планировщик и менеджер данных размещаются на каждой из ЭВМ распределенной системы и, работая совместно, обеспечивают гарантии непротиворечивости локальных данных. Менеджер транзакций размещается только на сервере транзакций.
Для обеспечения свойства изолированности транзакций необходима синхронизация конфликтующих операций. Две операции конфликтуют, если они работают с одним и тем же элементом данных, и хотя бы одна из них является операцией записи. Синхронизация конфликтующих операций при выполнении транзакций производится двумя методами:
1. Двухфазная блокировка. Когда процесс в ходе транзакции нуждается в чтении или записи элемента данных, он делает запрос планировщику заблокировать для него этот элемент данных. Когда необходимость в этом элементе данных исчезает, процесс делает запрос планировщику снять блокировку. Задача планировщика состоит в том, чтобы устанавливать и снимать блокировку, не допуская некорректного перемежения операций, выполняемых различными транзакциями над одним и тем же элементом данных. При двухфазной блокировке различают две фазы:
а) Фаза подъема, на которой планировщик устанавливает все необходимые блокировки;
б) Фаза спада, на которой планировщик снимает все необходимые блокировки.
При этом выполняются три правила:
а) Если запрашивается операция, конфликтующая с операциями, уже получившими блокировку, то её выполнение откладывается;
б) Если менеджер данных уведомил планировщик, что он осуществляет операцию с элементом данных, планировщик не снимет блокировку с этого элемента данных до окончания работы менеджера данных с этим элементом данных;
в) Если планировщик снял блокировку с данных по требованию какойлибо транзакции, он никогда больше не заблокирует данные по требованию этой транзакции.
Варианты двухфазной блокировки:
а) Строгая двухфазная блокировка. В этом варианте блокировки фаза спада не начинается до тех пор, пока транзакция не завершится;
б) Централизованная двухфазная блокировка. В отличие от классического варианта, в этом случае за установку и снятие блокировок отвечает один централизованный процесс-планировщик, называемый менеджер блокировок;
в) Первичная двухфазная блокировка. В этом варианте блокировки с каждого элемента данных снимается копия, на которую устанавливаются блокировки. В отличие от централизованной двухфазной блокировки, первичная двухфазная блокировка может быть распределена по нескольким ЭВМ сети;
г) Распределенная двухфазная блокировка. Этот вариант блокировки применяется, когда данные распределены по нескольким ЭВМ сети. При этом планировщики каждой ЭВМ сети отвечают не только за установку и снятие блокировок, но и за пересылку операций локальным менеджерам данных.
2. Упорядочивание по меткам времени. Упорядочивание по меткам времени может быть двух видов:
а) Пессимистическое упорядочивание по меткам времени. В момент начала каждой транзакции ей присваивается метка времени. Каждая операция, являющаяся частью транзакции, также получает метку времени, эквивалентную метке времени транзакции, частью которой она является. Каждый элемент данных получает метку времени записи и метку времени считывания. Метка времени записи эквивалентна метке времени транзакции, которая последней записывала этот элемент данных. Метка времени считывания эквивалентна метке времени транзакции, которая последней считывала этот элемент данных. В случае конфликта двух операций выполняется операция с меньшим значением метки времени, операция с большим значением метки времени переводится в режим ожидания;
б) Оптимистическое упорядочивание по меткам времени. Параллельно выполняемые транзакции не обращают никакого внимания друг на друга. По окончании выполнения каждой транзакции результаты её работы анализируются на достоверность и либо принимаются, либо отбрасываются, причем в последнем случае инициируется повторное выполнение транзакции. Анализ результатов работы транзакции на достоверность основан на проверке факта изменения элемента данных, с которым работает транзакция, другой транзакцией. Если в процессе выполнения транзакции, элемент данных, с которым она работает, был изменен другой транзакцией, результаты работы обеих транзакций признаются недостоверными.
Цель репликации заключается в повышении надежности системы и её производительности. В то же время возникновение любой копии какого-либо ресурса ставит проблему сохранения непротиворечивости реплик. Под непротиворечивостью реплики ресурса понимается сохранение актуальности копий ресурса. Набор копий ресурса актуален, если операция чтения данных дает одинаковые результаты для каждой из копий. Обновление данных должно распространяться на все копии до того, как начнется следующая операция чтения данных, то есть обновление данных должно являться транзакцией.
Как правило, в распределенных системах данные существуют не автономно, а в составе объектов. Поэтому правильнее говорить не о репликации данных, а о репликации объектов.
Репликация с целью увеличения производительности системы часто одновременно используется и в качестве способа масштабирования. Это происходит за счет сокращения времени доступа к реплике ресурса при её территориальном приближении к потребителю ресурса. Однако, с ростом сети и числа реплик одного ресурса, увеличивается время на обновление данных, вследствие чего общая производительность распределенной системы падает. Таким образом, при репликации необходим разумный компромисс между количеством реплик одного ресурса и значением общей производительности распределенной системы. Решение данной проблемы заключается в жертвовании требованием об атомарности обновления данных, то есть непротиворечивостью. Для этого производители сетевого программного обеспечения разрабатывают протоколы непротиворечивости, под которыми понимают соглашения о том, какие правила должны выполнять процессы, чтобы хранилище данных работало правильно. При этом внутри системы возможны отдельные состояния нарушения непротиворечивости данных, которые должны скрываться от клиентов. Существует два вида протоколов непротиворечивости:
1. Протоколы непротиворечивости, ориентированные на данные. Эта группа протоколов обеспечивает непротиворечивое представление данных;
2. Протоколы непротиворечивости, ориентированные на клиента. Эти протоколы допускают нарушения непротиворечивости данных, но обеспечивают сокрытие факта нарушений от клиента.
Рассмотренные протоколы определяют одноименные виды непротиворечивости.
Непротиворечивость, ориентированная на данные, бывает двух видов: 1. Непротиворечивость, не требующая операций синхронизации. В свою очередь, этот вид непротиворечивости разбивается на четыре подвида:
а) Строгая непротиворечивость. При этой непротиворечивости всякое чтение элемента данных возвращает значение, соответствующее результату последней записи этого элемента данных. Когда хранилище данных строго непротиворечиво, все операции записи мгновенно замечаются всеми процессами. Выдерживается абсолютный глобальный порядок во времени. Если элемент данных изменяется, все последующие операции чтения этого элемента данных возвращают новое значение. Строгая непротиворечивость это идеализированный вид непротиворечивости, который в распределенной системе достигнуть очень сложно, а чаще всего невозможно. Поэтому на практике в зависимости от конкретной ситуации применяют другие, менее строгие виды непротиворечивости;
б) Последовательная непротиворечивость. Это менее строгая непротиворечивость. Хранилище данных последовательно непротиворечиво, если результат любого действия над элементом данных такой же, как если бы операции чтения и записи элемента данных выполнялись бы в некотором последовательном порядке. При последовательной непротиворечивости все процессы видят одно и то же чередование операций записи элемента данных. Процесс видит операции записи всех процессов, но только свои собственные операции чтения. Недостаток последовательной непротиворечивости заключается в том, что для всякого последовательно непротиворечивого хранилища данных увеличение скорости чтения вызывает падение скорости записи и наоборот;
в) Причинная непротиворечивость. Этот вид непротиворечивости представляет собой ослабленный вариант последовательной непротиворечивости, при котором проводится разделение между событиями, потенциально обладающими причинно-следственной связью, и событиями, ею не обладающими. Чтение связано с записью, предоставляющей данные для этого чтения, причинно-следственной связью. Операции, не имеющие причинно-следственной связи, называются параллельными. Хранилище данных поддерживает причинную непротиворечивость, если операции записи, потенциально связанные причинно-следственной связью, наблюдаются всеми процессами в одинаковом порядке, а параллельные операции записи могут наблюдаться в произвольном порядке. Реализация причинной непротиворечивости требует отслеживания, какие процессы какие операции записи видели. Одним из способов такого отслеживания является использование векторных меток времени для определения причинно-следственной связи;
г) Непротиворечивость FIFO. Данная непротиворечивость подчиняется следующему условию: операции записи, осуществляемые единичным процессом, наблюдаются всеми остальными процессами в том порядке, в котором они осуществляются, но операции записи, осуществляемые различными процессами, могут наблюдаться всеми остальными процессами в разном порядке. Непротиворечивость FIFO предполагает, что все операции записи, осуществляемые различными процессами, являются параллельными. Реализация непротиворечивости FIFO осуществляется путем именования каждой операции парой чисел - номером процесса и номером операции в процессе - и осуществления операций записи каждого из процессов в порядке их номеров;
2. Непротиворечивость, использующая операции синхронизации. Этот вид непротиворечивости основан на использовании переменной синхронизации. Переменная синхронизации - это ассоциированная с хранилищем данных переменная, значение которой эквивалентно номеру процесса, имеющего право изменять данные в хранилище. С переменной синхронизации ассоциирована операция синхронизации, обеспечивающая сохранение актуальности всех реплик хранилища данных при каждом изменении данных в хранилище. Непротиворечивость, использующая операции синхронизации, бывает трех подвидов:
а) Слабая непротиворечивость. Эта непротиворечивость обладает тремя свойствами:
– доступ к переменным синхронизации производится на условии последовательной непротиворечивости, то есть внешние по отношению к хранилищу данных процессы наблюдают не отдельные операции записи или считывания, а только все операции над переменной синхронизации;
– с переменной синхронизации не может быть произведена ни одна операция до полного завершения всех операций владеющего этой переменной процесса (то есть процесса, номер которого присвоен этой переменной) с хранилищем данных;
– с элементами данных не может быть произведена ни одна операция до полного завершения всех операций с переменной синхронизации.
Слабая непротиворечивость реализует непротиворечивость не отдельных операций записи или считывания, а групп операций, выделение которых производится с помощью переменных синхронизации. В случае слабой непротиворечивости соблюдается последовательная непротиворечивость между группами операций. При этом допускается существование неверных значений отдельных данных внутри такой группы операций. Слабая непротиворечивость чаще всего используется при пакетировании процедур доступа к данным, когда много операций выполняются одна за другой в короткий срок (например, сортировка данных), а затем в течение длительного времени обращения к данным не происходит. Проблема слабой непротиворечивости состоит в том, что хранилище данных не знает, какую операцию над данными совершает процесс, владеющий переменной синхронизации. В то же время ряд реализаций хранилищ данных требует распознавать разницу между операциями чтения и записи данных;
б) Свободная непротиворечивость. Возможность распознавания разницы между операциями записи и чтения данных предоставляет свободная непротиворечивость. Свободная непротиворечивость использует две переменные синхронизации - одну для операций записи, а другую для операций чтения данных. В случае эквивалентности значений обеих переменных номеру одного и того же процесса, говорят о захвате процесса. Если значение одной из переменных синхронизации перестает быть эквивалентно номеру захваченного процесса, говорят об освобождении процесса. Распределенное хранилище данных является свободно непротиворечивым, если выполняются три условия:
– перед выполнением операций записи или считывания данных должен быть произведен захват процесса, работающего с этими данными;
– перед освобождением процесса все операции записи или считывания данных должны быть полностью завершены;
– доступ к переменным синхронизации должен обладать непротиворечивостью FIFO.
Хранилище данных со свободной непротиворечивостью гарантирует, что при захвате процесса все локальные реплики данных будут непротиворечивы относительно своих удаленных копий. Изменения, сделанные процессом в локальных данных, будут распространены на удаленные реплики только при освобождении процесса;
в) Поэлементная непротиворечивость. Эта непротиворечивость является вариантом свободной непротиворечивости, но не для групп, а для отдельных элементов данных. При этом каждому элементу данных ассоциируются две переменные синхронизации. В поэлементной непротиворечивости отсутствует связь между совместно используемыми элементами данных. В то же время, поэлементная непротиворечивость дает возможность независимого параллельного доступа к хранилищу данных.
Непротиворечивость, ориентированная на клиента, бывает пяти видов:
1. Потенциальная непротиворечивость. Хранилище данных потенциально непротиворечиво, если в отсутствии изменений все реплики постепенно становятся идентичными (например, кэширование Web-сайта прокси-сервером при условии отсутствия диалогового режима). Потенциальная непротиворечивость требует только того, чтобы все изменения гарантированно расходились по всем репликам. Потенциальная непротиворечивость используется, если вносить изменения в хранилище данных может лишь ограниченная небольшая группа процессов, а также, если клиент всегда осуществляет доступ только к одной реплике. Мобильные клиенты, при перемещении в другую соту, могут быть переключены на другую реплику хранилища данных. В случае потенциальной непротиворечивости сделанные изменения в прежней реплике могут не успеть дойти до новой реплики данных. В этом случае применяют другие четыре вида непротиворечивости;
2. Непротиворечивость монотонного чтения. Хранилище данных обеспечивает непротиворечивость монотонного чтения, если каждая последующая операция чтения возвращает значение элемента данных, эквивалентное предыдущей операции чтения или более новое. При монотонном чтении процесс никогда не увидит более старого элемента данных, чем полученное при предыдущей операции чтения;
3. Непротиворечивость монотонной записи. Хранилище данных обеспечивает непротиворечивость монотонной записи, если операция записи процессом элемента данных завершается раньше любой из последующих операций записи этим же процессом того же элемента данных. Непротиворечивость монотонной записи подобна непротиворечивости FIFO с тем лишь различием, что в непротиворечивости FIFO участвует набор параллельных процессов, а в непротиворечивости монотонной записи - только
один;
4. Непротиворечивость чтения собственных записей. Хранилище данных обеспечивает непротиворечивость чтения собственных записей, если результат операции записи процессом элемента данных всегда виден последующим операциям чтения этим же процессом того же элемента данных. Непротиворечивость чтения собственных записей должна обеспечиваться при обновлении Web-страниц с последующим просмотром результатов;
5. Непротиворечивость записи за чтением. Хранилище данных обеспечивает непротиворечивость записи за чтением, если операция записи процессом элемента данных, следующая за операцией чтения этим же процессом того же элемента данных, гарантирует, что будет выполняться над тем же самым или более новым значением элемента данных, чем то, которое было прочитано предыдущей операцией. Непротиворечивость записи за чтением должна обеспечиваться при реализации сетевой службы новостей, чтобы все пользователи данной службы видели ответы на заданный вопрос только после поступления этого вопроса, а не наоборот.
Основные проблемы, возникающие при проектировании распределенных хранилищ данных, заключаются в определении времени создания, места создания и владельца копии хранилища данных, а также в распространении обновлений. Различают три типа реплик:
1. Постоянные реплики - это исходный набор реплик, образующих распределенное хранилище данных;
2. Реплики, инициируемые сервером. Эти реплики являются копиями хранилища данных, создаваемыми для повышения производительности системы;
3. Реплики, инициируемые клиентом. Эти реплики являются копиями хранилища данных, создаваемыми для сокращения времени доступа к данным.
При любом изменении данных в хранилище, необходимо актуализировать все реплики хранилища данных, то есть распространять обновления по всем репликам. Для распространения обновлений существуют три основные возможности:
1. Распространять только извещения об обновлении. Распространение извещений об обновлении производится в соответствии с протоколом о несостоятельности. Под протоколом о несостоятельности понимается соглашение о способах определения места обновления, то есть какая именно часть хранилища данных была изменена и перестала быть непротиворечивой своим репликам. При распространении извещений об обновлении не передается ничего, кроме собственно извещения. Конкретные действия по фактическому обновлению реплик зависят от поддерживаемого вида непротиворечивости. Преимущество передачи извещений об обновлении состоит в минимизации использования ресурсов сети. Извещения об обновлении чаще всего применяются при значительном преобладании операций записи по отношению к операциям чтения;
2. Передавать данные из одной копии в другую. Такое распространение обновлений применяется при значительном преобладании операций чтения по отношению к операциям записи. Для сокращения требуемых ресурсов сети можно передавать не сами данные, а так называемые журналы обновлений, представляющие собой несколько модификаций данных, упакованных в одно сообщение;
3. Распространять операции обновления по всем копиям. Этот вид распространения обновлений заключается в отказе от переноса модифицированных данных целиком, а указании каждой реплике, какую операцию с ней необходимо произвести. Для реализации распространения операций обновления по всем копиям необходимо, чтобы хранилище данных поддерживало активную репликацию. Активная репликация предполагает, что каждая реплика представлена процессом, способным сохранять актуальность своих данных при распространении операций обновления.
Распространение обновлений может инициироваться как сервером, так и клиентом. Серверное распространение обновлений применяется для поддержания высокого уровня непротиворечивости, делая реплицируемые данные непротиворечивыми сразу после обновления какого-либо элемента данных. При обновлении элемента данных сервер немедленно инициирует распространение обновлений.
В случае клиентского распространения обновлений клиент при необходимости использования какого-либо элемента данных опрашивает сервер в поисках обновлений этого элемента данных.
Встречается смешанная форма инициализации распространения обновлений. В этом случае назначается промежуток времени, в течение которого сервер должен хотя бы один раз передать обновления клиенту. Если по истечении этого промежутка времени сервер ни разу не передал обновлений, клиент сам запрашивает обновления у сервера.
При распространении обновлений возникают проблемы при распространении удалений элементов данных. Если какой-либо элемент данных просто изъять из хранилища данных, то наличие этого элемента в более старой копии хранилища данных может быть интерпретировано как обновление, включающее в себя новый элемент данных. Проблема решается путем замены удаляемого элемента данных записью о его удалении. Но при этом возникает другая проблема - постепенное накопление хранилищем данных большого количества никому не нужных записей об удалении данных. Для решения данной проблемы запись об удалении содержит метку времени её создания, и по истечении заданного промежутка времени устаревания, устаревшие записи об удалении изымаются из хранилища данных.