Диссертация (1148255), страница 7
Текст из файла (страница 7)
Вслучае обнаружения выхода из строя сервера, потери данных не происходит,так как они имеются на узле-копии, который становится новым сервером, выде37ляя какой-то из оставшихся узлов в качестве своей копии. Клиент, заметившийсработавший таймаут может разослать широковещательное сообщение, чтобынайти новый сервер, либо же немного подождать – новый сервер может сампослать широковещательное сообщение, информируя узлы в системе о сменеузла-сервера.Очевидно, что при одновременном выходе из строя и сервера и его копии, восстановиться системе уже не удастся, и здесь разработчику необходимоопределиться – какую надежность должна обеспечивать его система. В случаенеобходимости у узла-копии может изначально иметься и собственная копия,что, соответственно, повысит надежность системы, но увеличит задержки привыполнении операций и нагрузку на каналы передачи данных.Данный алгоритм применим ко многим моделям консистентности, так какне вносит новых ограничений на пересылку данных, а лишь требует, чтобыоперации записи, когда бы они (согласно требованиям конкретной модели) нираспространялись между узлами, происходили не напрямую, а через выделенный серверный узел.1.5.2.
Алгоритм миграции данныхВ данном алгоритме данные всегда хранятся лишь на одном узле. В случае, если они потребовались на каком-то другом – осуществляется их миграция(рис. 1.10).запрос данных1234миграция данныхРисунок 1.10 – Алгоритм миграции данныхПри таком подходе, завладевший данными узел, может сколь угодно долго осуществлять операции чтения и записи без необходимости обмена данными38с другими узлами (по крайней мере до тех пор, пока какой-то другой узел непотребует те же данные). Текущий владелец может быть обнаружен через рассылку широковещательного запроса, либо каждый элемент данных может бытьсвязан с конкретным узлом-менеджером (однозначно определяемым, например,по некоторой хэш-функции из свойств элемента), который будет контролировать перемещение данного блока и всегда «знать» его текущего владельца.Устойчивость ко сбоям отдельных узлов привносится в алгоритм достаточно просто – нужно лишь обеспечить наличие копий у всех блоков данных,что проще всего сделать следующим образом: в момент, когда осуществляетсятрансфер данных от одного узла к другому, данные на первом узле не уничтожаются, а лишь помечаются как запасные (в англоязычных работах обычноиспользуется слово invalid).
Одновременно с запрошенными данными следуетотправлять и остальные, которые были изменены на узле, но пока никому неотправлялись (так называемые dirty данные). При получении, такие данныемаркируются как invalid, а в совокупности всё это приводит к наличию копииу любых данных, из чего достаточно просто можно создать алгоритм восстановления в случае сбоя любого узла, аналогично алгоритму, представленномув случае с центральным сервером.Алгоритм миграции данных хорошо применим для реализации моделей,подобных модели ленивой консистентности по выходу, и совершенно неприменим в случаях, когда измененные данные нужно как можно скорее распространить по всем узлам, а также в случаях, когда требуется обеспечить возможностьнеэксклюзивного захвата синхро-переменной (в котором допускается одновременное чтение несколькими узлами одних и тех же данных).
Отсюда вытекаети еще один минус алгоритма – высокая нагрузка на каналы передачи данныхв случае если различные узлы часто обращаются к одним и тем же данным,даже если производят лишь операции чтения.391.5.3. Алгоритм репликации по чтениюДанный алгоритм призван повысить эффективность алгоритма миграции,описанного выше. Он допускает создание множественных копий одних и тех жеданных в случае если к этим данным осуществляется доступ только на чтение.Очевидно, что во многих случаях затрат на пересылку данных в этом алгоритмеудастся избежать, однако операции записи становятся несколько более затратными – ведь теперь им нужно ещё и оповестить всех владельцев копий соответствующих данных о том, что эти данные больше не актуальны.
За неимениемлаконичного русскоязычного синонима английскому слову invalidate, назовемтакое оповещение инвалидацией.На рисунке 1.11 показано, как выглядит операция записи в общие данныев данном алгоритме: данные являются реплицированными на узлах №3 и №4;узел №1 собирается произвести в них запись, и выполняет соответствующийзапрос к текущему владельцу №3 (в нашем случае к одному из владельцев, таккак данные реплицированы); запрос выполняется и новым владельцем данныхстановится узел №1, который тут же оповещает прежних владельцев №3 и №4о том, что их данные теперь считаются устаревшими.запрос данных1234данныеинвалидацияинвалидацияРисунок 1.11 – Операция записи в алгоритме репликации по чтениюУстойчивость ко сбоям в данном алгоритме может быть достигнута такимже способом, как было описано в случае для алгоритма миграции выше.401.5.4. Алгоритм полной репликацииПо сравнению с алгоритмом репликации по чтению, алгоритм полной репликации идёт еще дальше, позволяя нескольким узлам одновременно не толькочитать, но и записывать одни и те же данные.
Чтобы сохранять в таких условиях консистентность, все операции записи должны быть каким-то образомупорядочены. В мультипроцессорах упорядоченность достигается автоматически, при использовании шины данных, которая одновременно может заниматься передачей информации только об одной операции. В условиях отсутствиятакой шины, среди узлов может быть выделен особый узел, осуществляющийнеобходимое упорядочивание. В англоязычных работах данный узел обычно называется sequencer, мы же назовём его просто «сервер».Роль этого сервера похожа на роль одноименного узла, описанного в разделе 1.5.1, однако в отличие от последнего, в данном случае сервер не хранитвсе данные, а лишь гарантирует единственно верную для всех узлов последовательность операций записи.
Для этого, как и раньше, любому узлу, желающемупроизвести операцию записи в общую память, необходимо сообщить об этом серверу. Задача же сервера – оповестить о данной операции все узлы, включая иузел-источник изменения, который по получении такого сообщения может бытьуверен, что операция действительно произведена (см. 1.12).Каждое своё оповещение сервер может снабжать номером, который возрастает с каждой рассылкой.
Благодаря данному номеру узлы могут быть уверены,что получают оповещения в правильном порядке (а пропустив какое-то из них,имеют возможность запросить его снова, указав в запросе соответствующийномер).Так как данные распределены по всем узлам, выход из строя любого изних оказывается обратим без дополнительных усовершенствований алгоритма.Сервер может быть восстановлен как и любой другой узел, так как всё, что емунужно «знать», кроме состояния общей памяти, это последний использованный41его предшественником номер, а эта информация имеется по крайней мере водном из узлов (нужно лишь выбрать максимальное значение из имеющихся).Для ускорения процесса восстановления, можно поддерживать копию сервера– так же как было описано в разделе 1.5.1.Алгоритм может быть полезен нетолько для реализации полностью репСерверлицированных данных, но и (частич1записьно), скажем, в ситуации, когда канаобновлениелы передачи данных не могут обеспечить упорядоченную рассылку ши2роковещательных сообщений (инымиКлиентсловами, не могут гарантировать, чтосообщение, отправленное узлом рань43КлиентКлиентРисунок 1.12 – Операция записи в алгоритмеше, придет ко всем остальным узлам полной репликациитоже раньше, чем отправленное следующим).1.5.5.
ЗаключениеВыше рассмотрены лишь основные подходы и принципы, на основе которых может быть создано бесконечное множество алгоритмов, уместных в томили ином окружении. Собственный алгоритм, применимый в нашей ситуации,будет выработан в разделах ниже.1.6. РеализацииС момента возникновения концепции DSM было создано множество реализующих её систем. Так как автору не удалось найти подходящий их список (вобнаруженных работах рассматривается от одной, до, в лучшем случае, пятисистем), он собрал его самостоятельно (см. раздел 1.6.8).42Мы не рассматриваем здесь аппаратные и гибридные DSM системы (такие как Alewife, DASH, FLASH, Typhoon и др.), сосредотачиваясь именно напрограммных решениях.Для детального обзора каждой из систем потребовалось бы слишком многоместа, но мы выделим из списка, по крайней мере, наиболее известные системыи укажем их наиболее интересные (для данной работы) свойства.1.6.1.
LindaLinda [24], по всей видимости, была предтечей известных нам сегодня DSMсистем. Основываясь на уже существующем языке программирования, Lindaпредлагает расширить этот язык несколькими операциями, создать препроцессор, который «развернет» эти операции в вызовы рантайм библиотек Linda идалее собирать программу пользователя обычным для него способом. В частности были поддержаны языки Си и Фортран.Ключевой объект в Linda – так называемое «пространство кортежей» – глобальное пространство, в которое каждый узел системы может добавить новыйэлемент или же прочесть/удалить существующий. Данное пространство выглядит как DSM, а кортеж напоминает структуру из языка Си.
Однако операциидля работы с этими структурами нетипичны для данного языка – к примеру,операция «out("abc", 1, 2, 3)» создаст кортеж с именем «abc», и значением, состоящим из нескольких чисел. Операция «in(\"abc\", 1, ? i, ? j)»,которая может выполняться и на другом узле, извлечет этот кортеж, поместивзначения 2 и 3 в переменные и соответственно. Если бы подходящего под«шаблон» кортежа в пространстве кортежей не нашлось, операция «in» былабы заблокирована до его появления. Кроме этого, система включает операциичтения без удаления и создания новых процессов.Таким образом, разработка под Linda, с одной стороны, позволяет пользователю не изучать новые языки программирования, с другой же, эти нескольконовых операций оказались настолько необычны, что разработка под Linda тре43бовала перестройки подходов к программированию, а перенос готового ПО вLinda или обратное портирование в другие системы были нетривиальной задачей.1.6.2.
IVYIVY [32] во многих источниках считается первой DSM системой, а указанная работа – первой, где в явном виде сформулирована известная и по сегодняшний день концепция DSM.Реализует модель последовательной консистентности (см. раздел 1.4.2).Поддерживает страничную организацию распределённой памяти; при отсутствии страницы на локальном узле – обеспечивает её трансфер по сети.Данная система была создана для того, чтобы имитировать мультипроцессоры и выполнять ПО, разработанное для них, без изменений, таким образомосуществляя мягкий переход к распределённым системам.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
