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

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

4.2.

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

этот клиент прикреплен. Если направляющий узел не содержит локализующей

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

ми домена D. Соответственно, узел пересылает запрос своему родителю. Отме-

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

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

передается уровнем выше и т. д.

Узел не имеет записи

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

и запрос

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

родительскому

узлу

Узел имеет запись

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

и запрос пересылается

дочернему узлу

Запрос

на поиск

Рис. 4.17. Поиск сущности

иерархической службе локализации

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

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

dom(M)y

содержимое которого отражено на узле М. На рисунке показано, что на

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

нов.

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

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

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

держит адрес сущности Е в этом листовом домене. Этот адрес и будет возвращен

клиенту, инициировавшему поиск.

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

ние:

операция поиска разворачивается наступательно. Сущность ищется в посте-

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

клиент. Область поиска расширяется каждый раз, когда запрос на поиск пересы-

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

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

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

этого будет просто пересылаться от указателя к указателю, пока не доберется до

одного из листовых узлов.

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

стрировано на рис. 4.18. Рассмотрим сущность

Е,

для которой в листовом доме-

не D была создан^ реплика. Необходимо вставить в направляющий узел адрес

этой реплики. Вставка начинается с листового узла dir(D) домена

Z),

который не-

252

Глава

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

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

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

узла М, в котором уже имеется локализующая запись для Е.

Узел не имеет

записи

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

поэтому запрос

передается

родительскому

Узел имеет запись

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

поэтому запрос

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

Узел создает запись

и сохраняет указатель

Узел создает

запись и сохраняет

адрес

Домен D

Запрос

на вставку

Рис. 4.18. Запрос на вставку пересылается первому

узлу,

имеющему информацию

о сущности Е (а). Создана цепочка передачи указателей до листового узла (б)

Узел М сохранит указатель в локализующей записи для сущности £, ссылаю-

щийся на дочерний узел, от которого пришел запрос на вставку. После этого до-

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

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

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

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

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

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

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

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

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

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

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

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

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

с текущим узлом.

Операция удаления аналогична операции вставки. При необходимости уда-

ления адреса сущности Е из листового домена 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.19. Кэширование указателей на направляющий узел домена

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

подавляющую часть времени

Когда пользователь находится в Сан-Франциско, можно предположить, что

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

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

ветствующем домену Сан-Франциско. Такая же модель поведения будет харак-

терна для нашего путешественника и в Лос-Анджелесе.

Однако может статься, что пользователь все свое время летает из Сан-Фран-

циско в Лос-Анджелес. В этом случае, может быть, разумнее сохранять его теку-

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

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

ватель

—

в Сан-Франциско или Лос-Анджелесе.

Кэшированный указатель

на узел dir(D),

который должен стать

недействительным

Ш) Исходный адрес

(по-прежнему

правильный)

Рис. 4.20. Запись

кэше становится неправильной, поскольку возвращает

нелокальный адрес,

то время как существует локальный

Другой оставшийся открытым вопрос

—

когда содержимое кэша перестает со-

ответствовать действительности. Предположим, что пользователь из нашего при-

мера получил столько заявок из Нью-Йорка, что решил открыть офис на Ман-

4.2.

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

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

имя запросы в район Нью-Йорка. В терминах службы локализации у него по-

явился постоянный адрес в домене Манхеттен. На все запросы на поиск из Нью-

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

направляющий узел Калифорнии, как показано на рис. 4.20.

Проблемы масштабирования

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

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

всем сущностям. Объем хранимой информации сам по себе не является главной

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

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

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

1 Кбайт, то для хранения, скажем, миллиарда сущностей необходим всего один

терабайт. Этот объем обеспечат десять дисков по 100 Гбайт.

Настоящая проблема состоит в том, что без принятия специальных мер кор-

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

новление, что здесь неизбежно возникнет узкое место. Решение этой проблемы

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

уровня на вложенные узлы. Каждый вложенный узел будет отвечать за обработ-

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

локализации.

К сожалению, просто разделить узлы верхнего уровня на части недостаточно.

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

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

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

зации, физически.

Одна из возможностей

—

расположить вложенные узлы в соответствии с цен-

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

стер.

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

раллельного компьютера типа COW или МРР (с которыми мы познакомились в

главе 1). Однако несмотря на то, что вычислительной мощности в этом случае

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

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

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

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

ный способ может привести к появлению проблемы масштабирования. Рассмот-

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

Франциско и Лос-Анджелесом. Корневой узел разбит на вложенные узлы, и во-

прос,

который предстоит решить,

—

какой вложенный узел сделать ответствен-

ным за этого пользователя.

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

го пользователя выбран вложенный узел, находящийся в Финляндии. Опуская

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

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

256

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

пройти через корневой узел в Финляндии. Однако, как показано на рис.

4.21,

ра-

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

пример, в Калифорнии. Вопрос о том, какому вложенному узлу за какую сущ-

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

г Вложенный узел корневого узлаГ

Л отвечающий за обработку

3 запросов для сущности Е

Домен,

в котором

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

находится сущность Е

Альтернативный

маршрут

запроса

на поиск

Текущий маршрут^

с==.

^V^

запроса на поиск ^v^^ уч

Клиент, запросивший текущий адрес сущности Е

^j'

Рис. 4.21. Иллюстрация проблем масштабирования, связанных с задачей равномерного

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

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

была создана сущность

Е,

В частности, вложенный узел корневого узла, располо-

женный неподалеку от места, где была создана сущность £, может быть назначен

ответственным за обработку относящихся к Е запросов корневого уровня. Это

решение срабатывает для сущностей, которые имеют тенденцию находиться не-

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

в отдаленное место, проблема остается. Детальное описание этого подхода мож-

но найти в [31].

4.3.

Удаление сущностей,

на которые нет ссылок

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

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

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

к сущности прекращается, ее следует удалить.

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

мер,

если процесс Р знает, что он

—

последний из процессов, использующих не-

4.3.

Удаление сущностей, на которые нет ссылок 257

который файл, причем в будущем этот файл ни одному процессу не понадобит-

ся,

Р может при своем завершении удалить этот файл. К сожалению, управление

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

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

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

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

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

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

из-за отсутствия гарантий, что на нее не существует ссылок. Если ссылок все же

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

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

—

просто мусор и ее следует удалить.

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

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

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

пределенных сборщиков

мусора

{distributed garbage

collectors).

В этом разделе мы

поближе познакомимся с взаимоотношениями сущностей именования и локали-

зации, а также с автоматической уборкой «ничейных» сущностей.

4.3.1.

Проблема объектов, на которые нет ссылок

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

пределенных объектов, в частности удаленных объектов. Напомним, что удален-

ный объект реализуется так, что его состояние целиком находится на сервере

объектов, а клиент работает исключительно с заместителем. Как мы узнали в раз-

деле 2.3, ссылка на удаленный объект обычно реализуется парой (заместитель,

скелетон). Заместитель клиента содержит всю информацию, необходимую для

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

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

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

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

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

объекты, например локальные ссылки на заместители этих объектов. Точно так

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

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

Из этого следует, что к объекту можно получить доступ, только если у нас

есть удаленная ссылка на него. Объект, на который отсутствуют удаленные ссыл-

ки,

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

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

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

гих ссылок. Эта ситуация может быть легко обобщена на цепочку объектов, каж-

дый из которых ссылается на соседа. Подобные объекты также следует выявлять

и удалять.

В общем виде модель ссылок на объекты может быть представлена в виде гра-

фа, каждый узел которого

—

это объект. Ребро, идущее от узла М к узлу N, отра-

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

жает тот факт, что объект М содержит ссылку на объект

Подмножество объек-

тов,

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

корневого набора

{root

set). Объекты корневого набора обычно представляют системные службы,

пользователей и т. д.

На рис. 4.22 показан граф ссылок. Все белые узлы представляют объекты, на

которые у объектов корневого набора нет прямых или косвенных ссылок. Такие

объекты могут быть удалены.

Недостижимые сущности,

образующие замкнутый цикл ссылок

Корневой набор

Достижимые

для корневого

набора сущности

Недостижимая для корневого

набора сущность

Рис. 4.22. Пример графа объектов, содержащих ссылки друг на друга

В однопроцессорных системах обнаружение и удаление объектов, на которые

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

пределенных системах (описание сборки мусора в однопроцессорных системах

можно найти в [226]). Поскольку объекты в нашем случае разбросаны по множе-

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

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

бируемость решений. Кроме того, связь (как и машины, как и процессы) подвер-

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

В этом пункте мы рассмотрим несколько общеизвестных решений проблемы

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

тично решают проблему. Наш подход подобен подходу, примененному в

[356],

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

нительную информацию можно почерпнуть также из [2].

4.3.2.

Подсчет ссылок

Метод проверки (который весьма популярен в однопроцессорных системах) воз-

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

подсчет ссылок на этот объект. Каждый раз при создании ссылки на объект счет-

чик ссылок на этот объект увеличивается на единицу. Когда ссылка на объект

4.3.

Удаление сущностей, на которые нет ссылок 259

уничтожается, значение счетчика уменьшается. Как только значение счетчика ста-

нет равным нулю, объект можно удалять.

Простой подсчет ссылок

Простой подсчет ссылок в распределенных системах приводит к некоторым про-

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

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

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

объект. Этот случай показан на рис. 4.23.

Процесс Р

Скелетон (поддерживает счетчик ссылок)

Объект О

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

учтен в расчетах

дважды

Рис. 4.23. Проблема сохранения правильности счетчика ссылок

в условиях ненадежной связи

Когда процесс Р создает ссылку на удаленный объект О, он, как показано на

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

Для увеличения счетчика ссылок заместитель посылает сообщение (1) скелетону

объекта и ожидает, что последний вернет подтверждение. Однако если подтвер-

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

ния (3). Если не предпринимать никаких мер для обнаружения повторных со-

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

относительно несложно организовать обнаружение повторных сообщений.

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

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

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

приведет к повторному, на этот раз ошибочному уменьшению счетчика. Таким

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

сообщения и в случае обнаружения игнорировать их.

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

удаленной ссылки в другой процесс. Если процесс

Р1

передает ссылку процессу Р2,

объект О, или точнее, его скелетон, может остаться в неведении относительно

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

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

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

стрирует рис. 4.24, а.

260

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

Процесс Р1 Процесс Р1

посылает ссылку удаляет свою

процессу Р2 ссылку на объект О

Процесс

Р1

сообщает Процесс Р1

объекту О, что он передаст удаляет свою ссылку

ссылку на него процессу Р2 на объект О

Процесс Р2 сообщает объекту О,

что у него есть ссылка на него

Процесс Р1

посылает

ссылку

процессу Р2

Объект О подтверждает,

что ему известно

о существовании ссылки

на него у процесса Р2

Рис. 4.24. Копирование ссылки в другой процесс и запоздавшее увеличение счетчика (а).

Решение (б)

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

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

Р2.

Кроме того, процесс не

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

знает о создании ссылки. Это решение продемонстрировано на рис. 4.24, 6. Под-

тверждение, посылаемое от объекта О процессу Р2, уведомляет

F2,

что объект О

зарегистрировал ссылку, что позволяет Р1 позднее удалить свою ссылку. До тех

пор пока процесс Р2 не уверен, что

знает о существовании у него ссылки, Р1 не

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

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

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

ро приведет нас к проблемам с производительностью.

Улучшенные механизмы подсчета ссылок

Как было показано, простой распределенный подсчет ссылок требует соблюде-

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

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

ем счетчика. Такое решение реализовано во

взвешенном подсчете ссылок {weighted

reference

counting, при котором каждый объект имеет фиксированный общий вес.

При создании объекта этот вес сохраняется в ассоциированном с ним скелетоне

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

казано на рис. 4.25, а.

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

гося в скелетоне объекта, присваивается новому заместителю, как показано на

рис.

4.25,

б.

Оставшаяся половина хранится в скелетоне. Когда удаленная ссылка

дублируется, например, при ее передаче из процесса Р1 в процесс Р2, половина

частичного веса заместителя из Р1 передается заместителю процесса Р2, в кото-

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

цесса Р1, как показано на рис. 4.25, в.