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

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

4.1.

Именованные сущности 221

четш других полей суперблока, а также внутренней информации операционной

системы об организации суперблока.

Чтобы прояснить этот момент, рассмотрим строковое представление имени

файла /home/steen/mbox. Чтобы разрешить это имя, необходимо иметь доступ

к направляющей таблице корневого узла соответствующего графа именования.

Будучи корневым узлом, этот узел не может быть разрешен, если только он не

реализован в виде другого узла иного графа именования, скажем G. Но в этом

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

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

механизмов, которые начнут процесс разрешения.

Абсолютно другой пример

—

использование строки "0031204430784". Боль-

шинство людей не поймут, что делать с этими цифрами. Исключением будут

лишь те, кому скажут, что эта цепочка цифр

—

номер телефона. Подобная инфор-

мация необходима для того, чтобы начать разрешение имени, в частности, для

набора номера. После этого телефонная система сделает то, чего от нее требуют.

В качестве последнего примера рассмотрим использование в распределенных

системах глобальных и локальных имен. Типичный пример локального имени

—

переменная среды. Так, в UNIX-системах переменная с именем

НОМЕ

использует-

ся для ссылки на домашний каталог пользователя. Каждый пользователь имеет

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

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

тывания, ассоциированный с переменными среды, гарантирует, что имя этой

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

пользователя.

Организация ссылок и монтирование

С разрешением имен связано использование

псевдопимов

{aliases).

Псевдоним

—

это другое имя той же сущности. Переменные среды

—

пример псевдонимов.

по-

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

нимов. Первый способ

—

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

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

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

терминологии UNIX оба пути, /keys и /home/steen/keys, называются

жесткими

ссылками

(hard links) к узлу п5.

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

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

сти,

сохранить в нем ее абсолютный путь. Когда первое разрешение абсолютного

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

чего мы продолжим разрешение нового пути. Этот принцип соответствует ис-

пользованию

символических ссылок

(symbolic links) в файловых системах UNIX

его иллюстрирует рис. 4.3. В этом случае имя пути /home/steen/keys, ссылаю-

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

ссылкой на узел п5.

Описанное разрешение имени полностью относится к одиночным простран-

ствам имен. Однако разрешение имен может также использоваться и при про-

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

зрачном слиянии нескольких пространств имен. Давайте сначала рассмотрим

монтируемые файловые системы. В понятиях нашей модели именования монти-

руемая файловая система

—

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

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

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

тификатор узла, называется

моптаэююй

точкой {mount point). Соответственно,

направляющий узел во внешнем пространстве имен называется

точкой

монтиро-

вания {mounting

point).

Обычно точка монтирования является корнем пространст-

ва имен. В ходе разрешения имен отыскивается точка монтирования, и процесс

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

Данные, хранящиеся

в узле п1

п2:

пЗ:

п4:

"eike"

"max"

"steen"

steen

Данные, хранящиеся

п4 I в узле п6

Листовой узел Q .twmrc У»Жх\1^®У^ Пкеу£;)

Направляющий ["j Q О @nhome/steen/keys"

Рис. 4.3. Концепция символической ссылки в графе именования

Принципы монтирования могут быть обобщены и на другие пространства

имен. В частности, все, что необходимо для использования направляюш.его узла

в качестве монтажной точки,

—

это чтобы в ней хранилась вся информация, не-

обходимая для идентификации монтирующей точки чужого пространства имен

и доступа к ней. Этот подход соблюдается в системе именования Jade

[371],

ему

также следуют многие распределенные файловые системы.

Рассмотрим набор пространств имен, распределенных по нескольким маши-

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

которые, возможно, работают на разных машинах. Соответственно, если мы хо-

тим смонтировать внешнее пространство имен NS2 с пространством имен NS1,

нужно (если серверы NS2 и NS1 работают на разных Maunniax) организовать связь

по сети между этими серверами. Чтобы смонтировать внешнее пространство имен

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

> имя протокола доступа;

-f имя сервера;

имя монтирующей точки во внешнем пространстве имен.

Отметим, что каждое из этих имен должно разрешаться. Имя протокола дос-

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

ганизуется связь с сервером внешнего пространства имен. Имя сервера должно

разрешаться посредством адреса сервера. И наконец, имя монтирующей точки

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

ве имен.

4.1.

Именованные сущности 223

В нераспределенных системах любая из этих трех точек может оказаться не-

востребованной. Так, в системе UNIX нет ни протоколов доступа, ни серверов.

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

корневой каталог внешнего пространства имен.

Имя монтирующей точки может быть разрешено сервером внешнего про-

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

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

все эти три имени

—

это URL.

Чтобы сделать разговор более конкретным, рассмотрим ситуацию, когда поль-

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

ловому серверу. И машина клиента, и файловый сервер сконфигурированы под

сетевую

файловую систему

{Network File

System^

NFS) фирмы Sun, которую мы

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

10.

NFS

—

это распределенная файловая сис-

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

получить доступ к файлу, хранящемуся на (удаленном) файловом сервере NFS.

В частности, чтобы система NFS работала через Интернет, клиент должен ука-

зать,

к какому файлу он хочет получить доступ посредством URL, например,

nfs://flits.cs.vu.nl//honne/steen. Этот URL-адрес именует файл (который может

быть и каталогом) с именем /home/steen на файловом сервере NFS flits.cs.vu.nl,

доступ к которому возможен с использованием протокола NFS [80].

Имя nfs широко известно, в том смысле, что существует глобальное соглаше-

ние о его интерпретации. Другими словами, при разборе того, что мы исполь-

зовали в качестве URL, имя nfs разрешается реализацией протокола NFS. Имя

сервера разрешается его адресом DNS с помощью системы DNS, которую мы об-

судим в следующем пункте. Как мы уже говорили, имя /home/steen разрешается

сервером внешнего пространства имен.

Организация файловой системы на клиентской машине частично приведена

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

ностей, включая вложенный каталог под названием /remote. Этот вложенный ка-

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

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

этой стороны узел каталога с именем /remote/vu используется для хранения

URL nfs://flits.cs.vu.nl//home/steen.

Теперь рассмотрим имя /remote/vu/mbox. Это имя разрешается, начиная с

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

мы не достигнем узла /remote/vu. Затем разрешение имени продолжится возвра-

щением URL nfs://flits.cs.vu.nl//home/steen, что, в свою очередь, заставляет кли-

ентскую машину установить связь с файловым сервером flits.cs.vu.nl по протоко-

лу NFS и получить доступ в каталог /home/steen. Затем разрешение имени

продолжается чтением файла mbox в этом каталоге.

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

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

меру, выполнить следующие команды:

cd /remote/vu

Is -1

224

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

Сервер имен

Машина А

Сервер имен внешнего пространства имен

Машина В

lote / \keys

["nfs://flits.cs.vu.ni//home/steen^

Операционная

система

home

/y\stee.

mbox i

Ссылка на внешнее

пространство имен

Сеть

Рис. 4.4. Монтирование удаленного пространства имен

посредством особого протокола доступа

Эти команды создают список файлов в каталоге /home/steen удаленного фай-

лового сервера. Прелесть всего этого в том, что пользователь освобождается от

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

потерю производительности по сравнению с доступом к локальным файлам. Фак-

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

локальной машине и в каталоге /home/steen на удаленной машине, образуют

единое пространство имен.

Монтирование

—

это лишь один из способов объединения различных про-

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

глобальной службе

имен {Global

Name

Service,

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

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

[253].

Этот

принцип, который иллюстрирует рис. 4.5, рассмотрен ниже.

Проблема подобного подхода состоит в том, что созданные имена иногда прихо-

дится изменять. Например, абсолютный путь /home/steen в пространстве имен NS1

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

ветствует абсолютному пути /vu/home/steen. Чтобы решить эту проблему и позво-

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

чают (неявно) идентификатор узла, с которого должно начинаться разрешение.

Так, например, в пространстве имен NS1 на рисунке имя /home/steen/keys всег-

да расширяется для включения идентификатора узла пО, превращаясь в имя

nO:/home/steen/keys. Расширение обычно скрыто от пользователей. Оно означа-

ет, что идентификатор узла абсолютно уникален. Соответственно, узлы из раз-

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

4.1.

Именованные сущности 225

mO-^home

-•vu \—\

NS1

mbox

"m6:/mbox"

"np:/home/steen/keys"

Рис.

4.5.

Организация глобальной службы имен компании DEC

Объединение двух пространств имен NS1

и NS2 без

изменения существую-

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

невого узла этот узел получает

на

хранение таблицу, отображающую иденти-

фикатор корневого узла NS1

на

имя, под которым этот корень будет известен

новом пространстве адресов.

То же

самое происходит

и с

корневым узлом NS2.

Разрешение имен всегда начинается

корня нового адресного пространства, имя

nO:/home/steen после обнаружения идентификатора узла

пО

таблице корневого

узла сначала преобразуется

имя /vu/home/steen.

Потенциальная проблема GNS состоит

том,

что

корневой узел объединен-

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

старых корневых узлов

в их

новые имена. Если объединить тысячи пространств

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

4.1.3. Реализация пространств имен

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

зволяет пользователям

процессам добавлять, удалять

находить имена. Служ-

ба именования реализуется

при

помощи серверов имен. Если распределенная

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

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

крупных распределенных системах

множеством сущностей, возможно, разне-

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

странства имен

по

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

Распределение пространства имен

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

систем обычно организованы иерархически.

Как и

ранее,

мы

предполагаем,

что

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

пространство имен имеет только один корневой узел. Для эффективной реализа-

ции этого пространства имен удобно разбить его на логические уровни. В [98] вы-

деляют три уровня:

4- глобальный уровень;

администратршный уровень;

4 управленческий уровень.

Глобальный уровень (global layer) формируется узлами верхнего уровня, то

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

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

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

щие таблицы изменяются редко. Эти узлы могут представлять организации или

группы организаций, имена которых хранятся в пространстве имен.

Лдминистративгсый

уровень

(administrational

layer) формируется из направ-

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

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

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

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

всех отделений организации или направляющий узел всех хостов. Другой на-

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

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

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

ного уровня.

И, наконец,

управленческий

уровень

{managerial layer)

состоит из узлов, кото-

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

ставляющие хосты локальной сети. По той же причине этот уровень включает

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

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

ляются те, которые представляют каталоги и файлы пользователей. В противо-

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

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

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

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

ния части пространства имен DNS, включающего имена файлов организации,

к которым можно получить доступ через Интернет (например, web-страниц и

файлов, предназначенных для загрузки). Этот пример иллюстрирует рис. 4.6.

Пространство имен разделено на неперекрывающиеся части, которые [301] в DNS

называются зонами {zones). Зона

—

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

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

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

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

на для серверов имен глобального уровня. Если происходит сбой сервера имен,

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

ние имен не может «перескочить через голову» иерархии имен на оконечные сер-

веры.

4.1.

Именованные сущности 227

Глобальный

уровень

Административный <;

уровень

I eng /csVр jack/ \jiill к'ёГо" |'п"

ai/

\linda

Управленческий

уровень

oceV-Y vu

robot

pc24

csl 1 ftp tp / \ www

i^pu6"-^

globe

Зона

^ jf index.txt /

Рис. 4.6. Пример разбиения пространства имен DNS на три уровня

Требования к производительности не столь жесткие. Поскольку узлы гло-

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

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

эффективно подвергнуты кэшированию (то есть локально сохранены) на клиен-

те.

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

жет быть извлечен из кэша клиента без обращения к серверам имен. В результа-

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

поисковые запросы. С

другое!

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

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

Требования по доступности и производительности серверов имен глобально-

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

рованием на стороне клиента. Как мы выясним в главе 6, изменения, вносимые

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

чает поддержание непротиворечивости реплик.

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

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

вер имен. Если с сервером имен происходит сбой, множество ресурсов организа-

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

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

ее ресурсов не столь важна.

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

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

228

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

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

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

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

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

независимо от их источника (непосредственно с сервера или из локального кэша

клиента). Изменения также должны вноситься быстрее, чем на глобальном уров-

не.

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

зователя проходило несколько часов.

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

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

рование на стороне клиента в сочетании с репликацией серверов для повышения

общей доступности.

Требования к доступности серверов имен управленческого уровня обычно

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

машины (выделенной), даже с риском временной недоступности. Однако кри-

тична производительность. Пользователи требуют, чтобы операции осуществля-

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

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

которые будут обсуждаться в главе 6.

Сравнение серверов имен различных уровней приведено в табл.

4.1.

В распре-

деленных системах серверы имен глобального и административного уровней

реализовывать нелегко. Трудности связаны с репликацией и кэшированием, ко-

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

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

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

рая вносит длительные задержки связи и значительно затрудняет синхрониза-

цию.

Репликация и кэширование детально обсуждаются в главе 6.

Таблица 4,1. Сравнение серверов имен при реализации узлов

в большом пространстве имен

Элемент Глобальный Административный Управленческий

уровень уровень уровень

Географический масштаб сети Всемирная

Общее число узлов Несколько

Время поиска Секунды

Распространение изменений Медленное

Число реплик Множество

Кэширование на клиенте Да

Организация

Много

Миллисекунды

Немедленное

Мало или нет

Да

Отдел

Огромное число

Немедленно

Немедленное

Нет

Иногда

Реализация разрешения имен

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

реализацию разрешения имен. Чтобы пояснить реализацию разрешения имен в

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

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

4.1.

Именованные сущности 229

калькой процедуре разрешения имен {пате

resolver),

которая и отвечает за этот

процесс. В соответствии с рис. 4.6 предположим, что разрешается (абсолютный)

путь:

root:<nl,

VU,

OS,

ftp, pub, globe, jndex.txt>

Если использовать форму записи URL, этот путь соответствует имени

ftp://ftp.cs.vu.nl/pub/globe/index.txt. Теперь у нас есть два способа реализации раз-

решения имен.

При

итеративном разрешении

имени

{iterative

пате

resolution)

процедура раз-

решения имен передает полное имя корневому серверу имен. Предполагается,

что адрес корневого сервера, с которым контактирует процедура разрешения имен,

общеизвестен. Корневой сервер разрешит ту часть пути, которую сможет, и вер-

нет результат клиенту. В нашем примере корневой сервер может разрешить толь-

ко метку

п1,

для которой он и вернет адрес ассоциированного с ней сервера имен.

После этого клиент передаст этому серверу имен оставшуюся часть пути (то

есть имя nl:<vu, cs, ftp, pub, globe, index.txt>). Сервер сможет разрешить только

метку

и вернет адрес ассоциированного с этой меткой сервера имен вместе с

оставшейся частью пути, vu:<cs, ftp, pub, globe, index.txt>.

Процедура разрешения имен клиента свяжется со следующим сервером имен,

который сможет разрешить метку cs, а также ftp и вернет адрес FTP-сервера вме-

сте с путем ftp:<pub, globe, index.txt>. После этого клиент свяжется с FTP-серве-

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

шит последовательно метки pub, globe и jndex.txt и передаст запрошенный файл

(в данном случае по протоколу FTP). Подобный процесс итеративного разреше-

ния иллюстрирует рис. 4.7 (запись #<cs> используется для указания адреса сер-

вера, отвечающего за обработку метки <cs>).

Процедура

разрешения

имен

клиента

<nl,vu,cs,

.ftp>|

<nl.vu,cs.ftp>

#<nl>, <vu,cs,ftp>

3. <vu,cs,ftp>

Корневой

сервер имен

•.•-•:!:VL.

4. #<vu>, <cs,ftp>

5. <cs.ftp>

6. #<cs>, <ftp>

7. <ftp>

8. #<ftp>

#<nl,vu,cs,ftp>

Узлы,

обслуживаемые

одним сервером

имен

Рис. 4.7. Принцип итеративного разрешения имен

На практике последний шаг, а именно связь с FTP-сервером и запрос на пере-

дачу файла с путем ftp:<pub, globe, index.txt>, выполняется клиентским процес-

230

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

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

обрабатывает только путь root:<nl, vu, cs, ftp>, из которого он извлекает адрес, по

которому находится FTP-сервер, как и показано на рисунке.

Альтернативой итеративному разрешению имен является использование в хо-

де разрешения рекурсии. Вместо того чтобы возвращать процедуре разрешения

имен клиента промежуточные результаты, при рекурсивном разрешении имени

{recursive

пате

resolution)

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

наруженному серверу имен. Рассмотрим, например, что происходит, когда кор-

невой сервер обнаруживает адрес сервера имен, реализованного на узле с име-

нем п1. Он требует от сервера имен разрешить путь nl:<vu, cs, ftp, pub, globe,

index.M>. Используя и далее рекурсивное разрешение имен, этот следующий

сервер разрешит путь целиком и вернет файл index.txt корневому серверу, кото-

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

Рекурсивное разрешение имен иллюстрирует рис. 4.8. Как и при итеративном

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

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

Процедура

разрешения

имен

клиента

<nl,vu,cs,ftp>

8. #<nl,vu,cs,ftp>

7. #<vu,cs,ftp> V

6. #<cs,ftp>

5. #<ftp>

Корневой

сервер имен

Сервер имен

узла п1

Сервер имен

узла VU

Сервер имен

узла CS

<nl.vu

,cs,ftp> #<nl,vu,cs,ftp>

Рис. 4.8. Принцип рекурсивного разрешения имен

<vu,cs,ftp>

3. <cs,ftp>

4. <ftp>

Основной недостаток рекурсивного разрешения имен состоит в том, что к

производительности каждого из серверов имен предъявляются повышенные тре-

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

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

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

уровня'поддерживают только итеративное разрешение имен.

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

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

разрешением имен более эффективно. Второе

—

это снижение затрат на взаимо-

действие. Эти преимущества объясняются тем, что процедура разрешения имен

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

уровня. Для разрешения частей пути, относящихся к управленческому уровню,

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

ему процедурой разрешения имен. Мы говорили об этом выше.