Таненбаум Э. Распределенные системы. Принципы и парадигмы

Подождите немного. Документ загружается.

4.2.

Размещение мобильных сущностей 241

более простой протокол, известный

кг^к упрощенный протокол доступа

катало-

гам

(Lightweight Directory Access

Protocol,

LDAP).

LDAP

—

это протокол прикладного уровня, реализованный непосредственно

поверх TCP [481, 501], что уже способствует его простоте по сравнению с офи-

циальным протоколом доступа OSI. Кроме того, параметры операций поиска и

обновления могут быть переданы просто в виде строк. Раздельного кодирования,

необходимого по протоколу OSI, не нужно. Протокол LDAP постепенно стано-

вится стандартом де-факто для служб каталогов в Интернете. Он включается во

многие распределенные системы, включая, например, Windows 2000, о которой

мы поговорим в главе 9. Практическую информацию по LDAP можно найти

[217].

4.2.

Размещение мобильных сущностей

Службы имен, которые мы обсуждали, используются в первую очередь для име-

нованных сущностей, имеющих постоянное местоположение. По своей природе

традиционные системы именования плохо подходят для поддержания отображе-

ния имени в адрес, если тот регулярно изменяется, как это происходит в случае

мобильных сущностей. Эту проблему, в том числе и решения для размещения

мобильных сущностей, мы и рассмотрим в этом разделе.

4.2.1.

Именование и локализация сущностей

Как мы узнали в предыдущем разделе, сущности именуются для того, чтобы

иметь возможность их найти и получить к ним доступ. Мы выделили три типа

имен: имена, удобные для восприятия, идентификаторы и адреса. Поскольку рас-

пределенные системы строятся для людей и для доступа к сущности, необходимо

знать ее адрес, фактически все системы именования поддерживают отображение

имен, удобных для восприятия, в адреса.

Как мы говорили, для эффективной реализации полномасштабного простран-

ства имен, такого как в DNS, удобно разбить пространство имен на три уровня.

Глобальный и административный уровни характеризуются тем, что имена изме-

няются нечасто. Точнее, содержимое узлов этих частей пространства имен отно-

сительно постоянно. Вследствие этого репликация и кэширование способны по-

высить эффективность реализации.

Содержимое узлов управленческого уровня часто изменяется. Поэтому произ-

водительность операций поиска и обновления на этом уровне становится особен-

но важной. На практике требования по производительности можно удовлетворить

путем реализации узлов на локальных высокопроизводительных серверах имен.

Рассмотрим теперь поближе, какое допущение следует сделать на самом деле

и как подобный подход можно использовать для реализации крупномасштабной

системы именования. Прежде всего рассмотрим поиск адреса удаленного хоста

ftp.cs.vu.nl. Если считать содержимое узлов глобального и административного уров-

ней стабильным, клиент, вероятно, сможет найти адрес сервера имен домена cs.vu.nl

242

Глава

4. Именование

в локальном кэше. Соответственно, ему понадобится всего один запрос к серверу

имен, чтобы найти адрес ftp.cs.vu.nl.

Рассмотрим далее изменение адреса ftp.cs.vu.nl, например, из-за переноса

FTP-сервера на другую машину. До тех пор пока сервер будет оставаться на ма-

шине, входящей в домен cs.vu.nl, обновление можно выполнить быстро. В этом

случае изменению подвергнется только база данных DNS сервера имен cs.vu.nl.

Поиск будет столь же эффективен, как и ранее.

Соответственно, в том случае, если узлы глобального и административного

уровней изменяются редко, а изменения обычно ограничиваются одним серве-

ром имен, системы именования, такие как DNS, весьма эффективны.

Посмотрим теперь, что произойдет, если сервер ftp.cs.vu.nl придется перено-

сить на машину с именем ftp.cs.umsa.edu.au, находящуюся в абсолютно другом

домене. Первое, на что следует обратить внимание,

—

имя ftp.cs.vu.nl предпочти-

тельно было бы не менять, поскольку многие приложения и пользователи могли

бы иметь на него символическую ссылку. Другими словами, это имя предполо-

жительно используется в качестве идентификатора. Его изменение сделает все

ссылки на него неверными.

Существует два основных решения. Первое решение

—

записать адрес новой

машины в базе данных DNS для cs.vu.nl. Второе решение

—

записать имя новой

машины, а не ее адрес, включив fip.cs.vu.nl в символическую ссылку. Оба реше-

ния имеют серьезные недостатки.

Сначала рассмотрим запись адреса новой машины. Ясно, что на операцию по-

иска подобный подход не повлияет. Однако если сервер ftp.cs.vu.nl придется еще

раз переносить на новую машину, придется обновлять и его элемент базы дан-

ных DNS в cs.vu.nl. Важно отметить, что само по себе обновление выполняется

не дольше локальной операции, однако в реальности может потребовать сотен

миллисекунд. Другими словами, подобный подход нарушает предположение о том,

что операции в узлах управленческого уровня эффективны.

Основной недостаток использования символических ссылок состоит в том,

что теряется эффективность операций поиска. Каждая операция поиска выпол-

няется за два шага.

Поиск имени новой машины.

Поиск адреса, соответствующего этому имени.

Однако, если сервер ftp.cs.vu.nl снова переместится, скажем, на адрес ftp.cs.berke-

ley.edu, мы сможем осуществить операцию локального обновления, поместив имя

ftp.cs.unisa.edu.au в символическую ссылку на ftp.cs.berkeley.edu и сохранив для

cs.vu.nl элемент в базе данных DNS таким, как он есть. Недостаток

—

добавление

еще одного шага к операции поиска.

Для сущностей с высокой мобильностью ситуация может быть только хуже.

Каждый раз при переносе сущности либо приходится выполнять нелокальную

операцию внесения изменений, либо добавляется еще один шаг к операции

поиска.

Другая серьезная проблема обсуждаемых подходов состоит в том, что имя

ftp.cs.vu.nl не должно изменяться. Таким образом, становится чрезвычайно важ-

4.2.

Размещение мобильных сущностей 243

ным выбирать имена, которые (предположительно) не придется менять в тече-

ние всего времени существования той сущности, которую они идентифицируют.

Более того, такое имя нельзя использовать для каких-либо других сущностей.

На практике подбор подобных имен, особенно для долгоживущих сущностей, за-

труднен, что демонстрирует нам система именования в World Wide Web. Так,

многие сайты известны под разными именами и все эти имена остаются правиль-

ными, то есть всегда ссылаются на одну и ту же сущность, даже в случае мобиль-

ности.

По этим причинам традиционные службы имен, такие как DNS, не справ-

ляются с мобильными сущностями. Тут необходимо другое решение. По сути,

проблемы связаны с тем, что традиционные службы именования поддерживают

прямое отображение имен, удобных для восприятия человеком, в адреса сущно-

стей. Каждый раз, когда имя или адрес изменяются, приходится изменять и ото-

бражение, как показано на рис. 4.11, а.

Имя Имя Имя

Имя Ж

Идентификатор

сущности

Адрес Адрес Адрес N1

Служба

именования

Служба

локализации

Рис. 4.11. Прямое одноуровневое отображение имен в адреса (а). Двухуровневое

отображение с использованием идентификаторов (б)

Наилучшее решение состоит в том, чтобы отделить именование сущностей от

их размещения, введя идентификаторы, как показано на рис. 4.11, б. Напомним,

что идентификаторы никогда не изменяются, каждая сущность имеет только

один идентификатор, и идентификатор не может быть назначен другой сущнос-

ти

[212].

В общем случае идентификатор не предназначен для восприятия чело-

веком. Иначе говоря, он оптимизирован исключительно для машинной обработки.

При поиске сущности средствами службы именования она возвращает иден-

тификатор. Идентификатор может быть сохранен на локальной машине на

любой необходимый срок, поскольку он не может ни начать указывать на дру-

гую сущность, ни измениться. Под каким именем он сохранен, не важно. Со-

ответственно, когда этот идентификатор потребуется снова, его можно будет

просто взять с локальной машины, не обращаясь к поиску средствами службы

именования.

Размещение сущности определяется посредством отдельной

службы

локали-

зации

{location

service).

Служба локализации, собственно, использует в качестве

исходных данных идентификатор и возвращает текущий адрес соответствующей

244 Глава 4. Именование

ему сущности. Если имеется несколько копий сущности, будет возвращено не-

сколько адресов. В этом пункте мы сосредоточимся исключительно на проблеме

реализации эффективной службы локализации.

4.2.2.

Простые решения

Обсудим сначала два простых решения по локализации сущностей. Оба эти ре-

шения применимы только в локальных сетях. Тем не мене в этой среде они обыч-

но успешно работают, что делает их простоту особенно привлекательной.

Широковещательная и групповая рассылки

Рассмотрим распределенную систему, построенную на основе компьютерной се-

ти,

предоставляющей эффективные механизмы широковещательной рассылки.

Обычно подобные механизмы предоставляются в локальной сети, в которой все

машины присоединены к одному кабелю. Беспроводные локальные сети также

попадают в эту категорию.

Локализация сущности в такой среде проста: сообщение, содержащее иденти-

фикатор сущности, широковещательной рассылкой доносится до каждой машины

и каждая из машин откликается на этот запрос проверкой, не на ней ли размеще-

на эта сущность. Те машины, которые могут предоставить точку входа к искомой

сущности, посылают ответное сообщение, содержащее адрес точки входа.

Этот принцип использован в

протоколе

разрешения

адресов {Address

Resolu-

tion

Protocol,

ARP) Интернета для поиска канального адреса машины, для кото-

рой известен только IP-адрес

[358].

В сущности, машина, посылающая широко-

вещательный пакет в локальную сеть, спрашивает, кто владеет указанным IP-

адресом. Когда машина принимает подобное сообщение, получатель проверяет,

не отслеживает ли он указанный IP-адрес. Если это так, он посылает ответный

пакет, содержащий, например, его адрес в сети Ethernet.

Широковещательная рассылка с ростом сети теряет эффективность. Потери

пропускной способности сети на пересылку сообщений

—

не единственная про-

блема, более важно то, что множество хостов вынуждены прерывать свою работу

из-за запроса, на который они не будут отвечать. Одно из возможных решений

этой проблемы

—

переход к групповой рассылке, при которой запрос получает

лишь ограниченная группа хостов. Так, например, сеть Ethernet аппаратно под-

держивает групповую рассылку канального уровня.

Групповая рассылка может также использоваться для локализации сущностей

в некоммутируемых сетях. Так, например, в Интернете поддерживается группо-

вая рассылка сетевого уровня, при которой хостам разрешено присоединяться

к конкретной группе рассылки. Эта группа определяется адресом групповой рас-

сылки. Когда хост посылает сообщение на адрес групповой рассылки, сетевой

уровень предоставляет удобную службу по доставке этого сообщения каждому

из членов группы. Эффективная реализация групповой рассылки в Интернете

обсуждается в [121, 122].

Адрес групповой рассылки может использоваться в качестве обобщенной

службы локализации для множества сущностей. Рассмотрим, например, органи-

4.2.

Размещение мобильных сущностей 245

зацию, в которой каждый сотрудник имеет собственный мобильный компьютер.

Когда этот компьютер присоединяется к локальной сети, ему динамически при-

сваивается IP-адрес. Кроме того, он включается в группу рассылки. Когда про-

цесс желает локализовать компьютер Л, он посылает запрос «Где А?» в группу

рассылки. Если компьютер А в этот момент подключен к сети, он отвечает, сооб-

щая свой текущий IP-адрес.

Другой способ использования адреса групповой рассылки

—

ассоциировать

его с реплицируемой сущностью и путем групповой рассылки выполнить поиск

ближайшей

реплики. При посылке запроса на адрес групповой рассылки каждая

реплика сообщает свой текущий (обычный) IP-адрес. Примитивный способ ото-

брать ближайшую реплику

—

взять ту, ответ от которой пришел первым. Более

разумные способы описаны в

[189].

Как оказывается, выбрать ближайшую реп-

лику в общем не так-то просто.

Передача указателей

Другой популярный подход к локализации мобильных сущностей основан на пе-

редаче указателей

[149].

Принцип прост. Когда сущность перемещается из А в В,

она сохраняет ссылку на свое новое местоположение в А. Преимущество этого

подхода

—

в его простоте: как только сущность локализуется при помощи, напри-

мер,

традиционной службы именования, клиент может найти ее текущий адрес,

пройдя по цепочке переданных указателей.

Имеется в наличии и комплект недостатков. Во-первых, если не предприни-

мать специальных мер, цепочка может стать настолько длинной, что локализа-

ция сущности станет слишком дорогим удовольствием. Во-вторых, все промежу-

точные местоположения в цепочке должны поддерживать свою часть цепочки

так долго, как это будет необходимо. Третий и самый серьезный недостаток

—

уязвимость к потере ссылок. Как только пересылаемый указатель по каким-то

причинам будет утрачен, сущность окажется невозможным локализовать. Таким

образом, важно сохранить цепочку короткой и гарантировать сохранность пере-

сылаемых указателей.

Чтобы лучше понять, как работает передача указателей, рассмотрим ее в кон-

тексте распределенных объектов. В соответствии с подходом цепочек SSP (SSP

chains),

каждый из пересылаемых указателей реализуется в виде пары (замести-

тель,

скелетон), как показано на рис. 4.12

[408].

ПРИМЕЧАНИЕ '•

В SSP заместитель (proxy) называется заглушкой (stub), а скелетон (skeleton) — побегом

(scion), что приводит нас к паре (stub, scion), от которой и происходит аббревиатура SSP.

Скелетон (то есть серверная заглушка) содержит либо локальную ссылку на

реальный объект, либо локальную ссылку на заместитель (то есть клиентскую

заглушку) этого объекта. Чтобы подчеркнуть, что скелетоны выступают для уда-

ленных ссылок в роли

входных

элементов,

а заместители

—

в роли

выходных

эле-

ментов,

они обозначены на рисунке особыми образом.

Всякий раз при передаче объекта из адресного пространства А в адресное

пространство В он оставляет вместо себя в адресном пространстве А заместите-

246

Глава 4. Именование

ля,

а для связи с этим заместителем в адресное пространство В устанавливает

скелетон. Интересно, что эти перемещения абсолютно незаметны клиенту. Все,

что он видит,

—

это заместитель. Как и куда заместитель передает вызовы, от

клиента скрыто. Заметим также, что передача указателей не имеет ничего обще-

го с поиском адреса. Вместо того чтобы отыскивать адрес, мы просто передаем

запрос клиента по цепочке реальному объекту.

Процесс Р2 Заместитель р' ссылается

^ на тот же скелетон,

что и заместитель р

Процесс РЗ

Идентичный заместитель

Процесс Р4 Объект

Заместитель р

Идентичный

скелетон

Рис. 4.12. Принцип передачи указателей с использованием пар (заместитель, скелетон)

Для сокращения длины цепочки пар (заместитель, скелетон) вместе с вызо-

вом передается идентификатор того заместителя, который инициировал этот вы-

зов.

В идентификатор заместителя входит адрес клиента транспортного уровня,

совмещенный с числом, идентифицирующим конкретный заместитель. Когда вы-

зов добирается до объекта в том месте, где он в настоящее время расположен,

ответ возвращается непосредственно тому заместителю, который инициировал

вызов. Текущее местоположение объекта вкладывается в ответное сообщение,

и заместитель меняет тот скелетон, с которым он работал, на скелетон из теку-

щего местоположения объекта. Этот принцип иллюстрирует рис. 4.13.

Запрос

передается

объекту

Скелетон текущего

процесса объекта

возвращает текущее

местоположение

Скелетон больше

не ссылается

на заместитель'

Клиентский

заместитель устанавливает

прямую связь

Рис. 4.13. Перенаправление передаваемого указателя путем настройки

заместителя на прямую связь

4.2.

Размещение мобильных сущностей 247

Существует большая разница между посылкой ответа непосредственно на-

чавшему обмен заместителю и посылкой ответа обратно по цепочке передающих

указателей. В первом случае связь быстрее, поскольку во взаимодействие вовле-

чены немногие процессы. С другой стороны, подстроить можно только замести-

тель,

начавший обмен, в то время как посылка ответа обратно по тому же пути

дает возможность подстроить все промежуточные заместители.

После того как скелетон перестанет ссылаться на какой бы то ни было замес-

титель, его можно удалить. Как сделать это автоматически, рассматривается в

разделе 4.3.

Как мы говорили в главе 2, ссылки на объекты в распределенных системах

можно реализовать как заместители, передаваемые в виде параметров при обра-

щении к методу. Эта схема подходит также и для пересылки указателей. Предпо-

ложим, что процесс Р1 (см. рис. 4.12) передает свою ссылку на объект О процес-

су Р2. Передача ссылки производится путем установки копии заместителя р

в адресное пространство процесса Р2 (при этом копия превращается в замести-

тель р'). Заместитель р' ссылается на тот же самый скелетон, что

р, так что ме-

ханизм пересылки обращения работает так же, как раньше.

Проблемы возникают, когда процесс в цепочке пар (заместитель, скелетон)

зависает. Это делает остальные процессы недоступными. Возможно несколько

решений. Одна из возможностей, использованная в Emerald [220] и системе ЬП

[64],

—

позволить машине, на которой был создан объект,

—

ее называют

базовой

точкой {home location)

объекта

—

всегда хранить ссылку на его текущее местона-

хождение. Эта ссылка хранится и обрабатывается так, чтобы исключить сбои.

При обрыве цепочки текущее местонахождение объекта запрашивается у его ба-

зовой точки. Для изменения базовой точки объекта можно использовать традици-

онную службу имен, в которой записывается текущая базовая точка. Подобные

подходы мы обсудим далее.

4.2.3. Подходы на основе базовой точки

Использование широковещательной рассылки и передачи указателей создает

проблемы масштабируемости. Широковещательные и групповые рассылки труд-

но

эффективно реализовать в крупномасштабных сетях, а длинные цепочки пере-

сылаемых указателей создают проблемы с производительностью и чувствитель-

ны к обрывам связей.

Популярный подход к поддержке мобильных сущностей в полномасштабных

сетях состоит во введении понятия

базовой точки {home

location),

из которой от-

слеживается текущее местоположение объекта. Для защиты базовой точки от сбо-

ев в сети или процессах можно применять специальные методики. На практике

базовой точкой обычно выбирается то место, где была создана сущность.

Как говорилось ранее, подход на основе базовой точки используется в качестве

аварийного метода служб локализации, основанных на передаче указателей. Дру-

гим примером подобного подхода является схема мобильного IP-адреса

[348].

Каж-

дый мобильный хост имеет фиксированный IP-адрес. Всякая связь с этим IP-ад-

ресом изначально перенаправляется агенту

базы {home

agent) мобильного хоста.

Этот агент находится в локальной сети, соответствующей сетевому адресу, со-

248 Глава 4. Именование

держащему IP-адрес мобильного хоста. Каждый раз, когда мобильный хост пере-

мещается в другую сеть, он запрашивает временный адрес для связи. Этот адрес,

который называется контрольным адресом (care-of address), регистрируется

агентом базы.

Когда агент базы получает

от

мобильного хоста пакет,

он

проверяет местона-

хождение хоста. Если хост находится

текущей локальной сети, пакет просто

пересылается ему.

противном случае

он

передается туда, где

настоящее вре-

мя находится хост,

то

есть помещается

виде данных

IP-пакет

пересылается

на контрольный адрес. Одновременно отправитель пакета уведомляется

теку-

щем местоположении хоста. Этот принцип иллюстрирует рис. 4.14. Отметим,

что

IP-адрес успешно используется

качестве идентификатора мобильного хоста.

Текущее местоположение хоста

Рис. 4.14. Принцип работы схемы мобильного IP-адреса

В соответствии

рисунком схема мобильного IP-адреса работает следующим

образом.

Отправка пакета хосту

на

его базу.

Возвращение текущего адреса.

Передача сигнального пакета по текущему адресу.

Передача последующих пакетов

по

текущему адресу.

Рисунок также иллюстрирует недостатки подходов, основанных

на

базовой

точке,

для

крупномасштабных сетей.

Для

связи

мобильной сущностью клиент

должен сперва связаться

базой, которая может находиться совершенно

не

там,

где сама сущность.

результате задержки связи возрастают.

Решение, которое применяется

мобильной телефонии,

—

это двухуровневая

схема

[302].

При установке связи

мобильной сущностью клиент сначала прове-

4.2.

Размещение мобильных сущностей 249

ряет локальный реестр, чтобы определить, нельзя ли связаться с клиентом ло-

кально. Если нельзя, осуществляется контакт с базой сущности для определения

ее текущего местоположения. Позднее мы обсудим расширенный вариант этой

схемы с множеством иерархических уровней.

Другой важный недостаток подходов, основанных на базовой точке, состоит

в ее обязательной фиксированности. То есть мы всегда должны гарантировать

существование базовой точки. В противном случае связаться с сущностью не

удастся. Проблемы усугубляются, если сущность имеет длительный срок суще-

ствования и постоянно перемещается в удаленные от базовой точки части се-

ти.

В этом случае было бы лучше позволить базе перемещаться вместе с хостом.

Решение этой проблемы состоит в том, чтобы регистрировать базовую точку

в традиционной службе именования и требовать от клиента искать сперва базо-

вую точку. Поскольку местонахождение базовой точки можно считать относи-

тельно стабильным, после нахождения его можно успешно кэшировать.

4.2.4. Иерархические подходы

Двухэтапный подход к локализации сущностей, основанный на базовой точке,

можно обобщить на случай множества уровней. В этом пункте мы рассмотрим

сначала общий подход к иерархической схеме локализации, а затем представим

способы его оптимизации. Подход, о котором мы будем говорить, основан на

службе локализации Globe, описанной в

[470].

Это служба локализации общего

назначения, представленная множеством иерархических служб локализации

[355,

487], реализованных в

персональных системах связи (personal communication

systems).

Основной механизм

иерархической схеме сеть делится на

домены.

Это сильно напоминает иерархи-

ческую организацию DNS. Домен верхнего уровня охватывает сеть целиком. Каж-

дый домен делится на множество поддоменов. Домен самого нижнего уровня, на-

зываемый лг/с/повьдл/

доменом

(leaf

domain),

обычно соответствует локальной сети

в компьютерных сетях или соту в мобильной телефонии.

Также аналогично DNS и другим иерархическим системам именования. Каж-

дый домен D имеет ассоциированный с ним направляющий узел dir(D), который

отслеживает сущности домена. Таким образом, мы получаем дерево направляю-

щих узлов. Направляющий узел домена верхнего уровня, именуемый

корневым

направляющим

узлом

(root directory

node),

содержит сведения обо всех сущностях.

Подобная обобщенная организация сети из доменов и направляющих узлов по-

казана на рис. 4.15.

Чтобы отслеживать местонахождение сущностей, каждая сущность, находя-

щаяся в домене

представлена

локализующей записью (location record)

в направ-

ляющем узле dir(D). Локализующая запись для сущности Е

направляющем узле

листового домена D содержит текущий адрес сущности в этом домене. С дру-

гой стороны, направляющий узел N' в домене следующего уровня £)', в который

250 Глава 4. Именование

входит D, содержит в локализующей записи для Е только указатель на

Л^.

Точно

так же и родительский для N' узел содержит в локализующей записи для Е толь-

ко указатель на N'. Соответственно, на корневом узле находятся локализующие

записи для всех сущностей, и каждая локализующая запись содержит указатель

на направляющий узел в домене нижнего уровня, в котором находится сущ-

ность, идентифицируемая этой записью.

Корневой направляющий

узел dir(T)

Домен верхнего

уровня Т

Направляющий узел

clir(S) домена S

Поддомен S домена

верхнего уровня Т

(S содержится в Т)

- 7^^

Листовой домен, содержащийся в S

Рис. 4.15. Иерархическая организация службы локализации в виде доменов,

каждый из которых имеет ассоциированный с ним направляющий узел

Сущность может иметь несколько адресов, например, когда она реплицирова-

на. Если сущность имеет адреса в листовых доменах D1 и D2 соответственно, то

направляющий узел наименьшего из доменов, в который входят D1 и D2, будет

содержать два указателя

—

по адресу на каждый поддомен. Это приводит нас

к обобщенной организации сети (рис. 4.16).

Поле для домена

dom(N) с указателем

на узел N

Поле без данных

/ Локализующая запись

для сущности Е

на узле М

Локализующая запись

для сущности Е

на узле М

Домен D2

Рис. 4.16. Пример хранения информации о сущности, имеющей два адреса

в различных листовых доменах

Рассмотрим теперь, как в подобной иерархической службе осуществляется

операция поиска. Как показано на рис. 4.17, клиент, желающий найти сущность Jf,

посылает запрос на поиск направляющему узлу листового домена D, к которому