Э. Таненбаум, М. ван Стеен - Распределённые системы (принципы и парадигмы) (1162619), страница 65
Текст из файла (страница 65)
4.16).Поле для доменаdom(N) с указателемна узел NПоле без данных/Локализующая записьдля сущности Ена узле ММЛокализующая записьдля сущности Ена узле МДомен D2Рис. 4 . 1 6 . Пример хранения информации о сущности, имеющей два адресав различных листовых доменахРассмотрим теперь, как в подобной иерархической службе осуществляетсяоперация поиска.
Как показано на рис. 4.17, клиент, желающий найти сущность Jf,посылает запрос на поиск направляющему узлу листового домена D, к которому4.2. Размещение мобильных сущностей251этот клиент прикреплен. Если направляющий узел не содержит локализующейзаписи для этой сущности, значит, в настоящее время она находится за пределами домена D. Соответственно, узел пересылает запрос своему родителю. Отметим, что родительский узел представляет больший домен, чем дочерний.
Если иродительский домен не содержит локализующей записи для Е, запрос на поискпередается уровнем выше и т. д.Узел не имеет записидля сущности Е,и запроспересылаетсяродительскомуузлуУзел имеет записьдля сущности Е,и запрос пересылаетсядочернему узлуЗапросна поискРис. 4 . 1 7 . Поиск сущности в иерархической службе локализацииПосле того как запрос достигнет направляющего узла М, где хранится локализующая запись для сущности Е, мы узнаем, что Е находится где-то в доменеdom(M)y содержимое которого отражено на узле М. На рисунке показано, что наМ хранится локализующая запись, содержащая указатель на один из поддоменов.
Запрос на поиск будет переслан направляющему узлу этого поддомена,который в свою очередь переправит его дальше, вниз по дереву, пока он не достигнет листового узла. Локализующая запись, хранящаяся на листовом узле, содержит адрес сущности Е в этом листовом домене. Этот адрес и будет возвращенклиенту, инициировавшему поиск.По поводу иерархических служб локализации следует сделать важное замечание: операция поиска разворачивается наступательно. Сущность ищется в постепенно увеличивающемся кольце, центром которого является отправивший запросклиент. Область поиска расширяется каждый раз, когда запрос на поиск пересылается направляющему узлу верхнего уровня.
В наиболее неудачном случае поиск продолжается до тех пор, пока запрос не достигнет корневого узла. Поскольку корневой узел содержит локализующие записи всех сущностей, запрос послеэтого будет просто пересылаться от указателя к указателю, пока не доберется доодного из листовых узлов.Операции обновления разворачиваются аналогичным образом, как продемонстрировано на рис. 4.18.
Рассмотрим сущность Е, для которой в листовом домене D была создан^ реплика. Необходимо вставить в направляющий узел адресэтой реплики. Вставка начинается с листового узла dir(D) домена Z), который не-252Глава 4. Именованиемедленно пересылает запрос на вставку своему родителю. Родитель также пересылает запрос на вставку, и так до тех пор, пока он не достигнет направляющегоузла М, в котором уже имеется локализующая запись для Е.Узел не имеетзаписидля сущности Е,поэтому запроспередаетсяродительскомуУзел имеет записьдля сущности Е,поэтому запроспередается дочернему узлуУзел создает записьи сохраняет указательУзел создаетзапись и сохраняетадресДомен DЗапросна вставкуРис. 4 .
1 8 . Запрос на вставку пересылается первому узлу, имеющему информациюо сущности Е (а). Создана цепочка передачи указателей до листового узла (б)Узел М сохранит указатель в локализующей записи для сущности £, ссылающийся на дочерний узел, от которого пришел запрос на вставку. После этого дочерний узел также создает локализующую запись для сущности £", содержащуюуказатель на узел еще более низкого уровня, от которого запрос пришел к нему.Этот процесс продолжается, пока мы не доберемся до листового узла, которыйинициировал вставку.
Листовой узел, наконец, создает запись с адресом сущности в ассоциированном с ним листовом домене.Таким образом, вставка адреса, как было описано, ведет к образованию цепочки указателей, ведущей сверху вниз и начинающейся с направляющего узла самого нижнего из имеющих локализующую запись для сущности Е уровня.Альтернативой является создание локализующей записи до передачи запроса родительскому узлу. Другими словами, цепочка указателей строится снизу вверх.Преимущество этого варианта состоит в том, что адрес для поисковых запросовоказывается доступным немедленно.
Соответственно, если родительский узел временно недоступен, адрес по-прежнему можно будет найти в домене, связанномс текущим узлом.Операция удаления аналогична операции вставки. При необходимости удаления адреса сущности Е из листового домена D направляющему узлу dir(D) поступает запрос на удаление этого адреса из локализующей записи для Е. Еслиэта локализующая запись оказывается пустой, то есть других адресов для сущности Е в домене D нет, запись можно удалять. В этом случае родительский для узлаdir(D) узел должен удалить свой указатель на dir(D).
Если локализующая записьдля Е на родительском узле стала пустой, эта запись также может быть удалена,при этом следует уведомить следующий уровень в иерархии. Таким образом.4.2. Размещение мобильных сущностей253этот процесс продолжается до тех пор, пока, удалив очередной указатель из очередной локализующей записи, мы не обнаружим там еще один или пока не доберемся до корневого узла.Кэширование указателейИерархическая служба локализации предназначена для поддержания мобильныхсущностей, то есть таких сущностей, местоположение которых регулярно меняется.
В традиционных службах именования отображение имени на адрес предполагается неизменным, как минимум для узлов глобального и административногоуровней. Это означает, что сохранение результатов поиска этих узлов в локальном кэше может сильно повысить эффективность работы.Локальное кэширование адресов для служб локализации обычно не слишкомэффективно. Зачем хранить адрес найденной мобильной сущности, если она в следующий раз вполне может оказаться в другом месте? Соответственно, потребуется провести полную процедуру поиска, которую только что описывали.
Этонеизбежно делает иерархические службы локализации значительно более дорогими, чем большинство служб именования.Кэширование эффективно только в том случае, если кэшируемые данные изменяются редко. Рассмотрим мобильную сущность £, которая регулярно перемещается в пределах домена D. Перемещение в пределах домена означает, что Ерегулярно меняет текущий адрес. Однако цепочка указателей сущности Е откорневого узла до направляющего узла dir(D) не изменяется.
Другими словами,место, где хранится наиболее свежая информация о местонахождении £, остается тем же самым, в данном случае это направляющий узел dir(D). Таким образом, кэширование ссылок на направляющий узел вполне оправдано.Обычно если D — наименьший домен, в пределах которого мобильная сущность регулярно перемещается, имеет смысл начинать поиск текущего местонахождения Е с направляющего узла dir(D), а не какого-либо другого узла. Этотподход используется в службе, описанной в [212], а также службе локалрхзацииGlobe [23, 470] и называется кэшированием указателей {pointer cashing). Ссылкана dir(D) может в принципе кэшироваться каждым узлом на пути к листовому узлу, с которого начинался поиск, как показано на рис.
4.19.Дальнейшие усовершенствования можно произвести, не позволив узлу dir(D)сохранить указатель на поддомен, в котором в настоящее время находится Е,а заменив его текущим адресом Е. В сочетании с кэшированием указателей операция поиска может быть реализована всего за два шага. Первый шаг требуетпросмотра локального кэша указателей, выводя нас прямо на соответствующийнаправляющий узел. Второй шаг включает в себя запрос к узлу с возвращениемтекущего адреса Е.Несмотря на то что принцип кэширования указателей в иерархических службах локализации работает, существует множество нюансов, требующих особоговнимания. Один из них состоит в выборе направляющего узла, наиболее подходящего для хранения текущего адреса мобильной сущности. Представьте себепользователя с мобильным компьютером, регулярно перемещающегося междудвумя различными городами, скажем, Сан-Франциско и Лос-Анджелесом.254Глава 4, ИменованиеДомен DКэшированныеуказателина узел dir(D)Сущность Е регулярноперемещается из одногоподдомена в другойРис.
4 . 1 9 . Кэширование указателей на направляющий узел доменасамого нижнего уровня из тех, на которых сущность находитсяподавляющую часть времениКогда пользователь находится в Сан-Франциско, можно предположить, чтоон будет регулярно менять свое местоположение внутри города. Соответственно,имеет смысл сохранять его текущее местоположение в направляющем узле, соответствующем домену Сан-Франциско. Такая же модель поведения будет характерна для нашего путешественника и в Лос-Анджелесе.Однако может статься, что пользователь все свое время летает из Сан-Франциско в Лос-Анджелес.
В этом случае, может быть, разумнее сохранять его текущее местоположение в направляющем узле более высокого уровня, например,соответствующем штату Калифорния, независимо от того, где находится пользователь — в Сан-Франциско или Лос-Анджелесе.Кэшированный указательна узел dir(D),который должен статьнедействительнымШ)Исходный адрес(по-прежнемуправильный)Рис. 4 . 2 0 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
