Э. Таненбаум, М. ван Стеен - Распределённые системы (принципы и парадигмы) (1162619), страница 98
Текст из файла (страница 98)
Когда сервер понимает, что постепенно «переполняется», то сокращает время новой аренды, предоставляемой клиентам. В результатетакого подхода серверу приходится отслеживать минимум клиентов — срокаренды истекает быстро. Другими словами, сервер динамически сокращает объемдискового пространства, отводимый на сохранение состояния клиентов (превращаясь в пределе в сервер без фиксации состояния).
Это разгружает его, и он начинает работать эффективнее.Целевая рассылка против групповойс вопросом о том, как рассылать обновления — продвигая или извлекая, — тесносвязан и вопрос о методе рассылки — целевой или групповой. При целевой рассылке (unicasting) сервер является частью хранилища данных и передает обновления на N'других серверов путем отправки Л^- отдельных сообщений, по одному накаждый сервер. В случае групповой рассылки (multicasting) за эффективную передачу одного сообщения нескольким получателям отвечает базовая сеть.Во многих случаях оказывается дешевле использовать доступные средствагрупповой рассылки. Предельный случай имеет место, когда все получатели сосредоточены в пределах одной локальной сети и в наличии имеются аппаратныесредства широковещательной рассылки (broadcasting).
Тогда затраты на передачуодного сообщения путем широковещательной или групповой рассылки не превышают затрат на сквозную (от точки к точке) передачу этого сообщения. В такой ситуации передача обновлений путем целевой рассылки была бы значительно менее эффективной.Групповая рассылка часто может быть эффективна в сочетании с распространением обновлений путем продвижения. В этом случае сервер, который хочет«продвинуть» обновление на несколько других серверов, просто использует одну группу групповой рассылки. В противоположность этому, при извлечении обновление копии требуется обычно только одному серверу или одному клиенту.В этом случае целевая рассылка — наиболее эффективное решение.6.4.3.
Эпидемические протоколыМы уже упоминали, что для многих хранилищ данных достаточно лишь причинной непротиворечивости. Другими словами, в отсутствии обновлений нам достаточно лишь гарантировать причинную идентичность копий. Распространение обновлений в причинно непротиворечивых хранилищах данных часто реализуется6.4. Протоколы распределения375при помощи класса алгоритмов, известных под названием эпидемических протоколов (epidemic protocols).
Эпидемические алгоритмы не разрешают конфликтовобновления, для этого требуются индивидуальные решения. Вместо этого ониориентированы на то, чтобы распространить обновления при помощи как можноменьшего количества сообщений. Для этой цели несколько обновлений частообъединяются в одно сообщение, которым затем обмениваются два сервера. Эпидемические алгоритмы образуют основу системы Bayou, о которой мы говорилиранее, различные схемы распространения обновлений, использованные в ней,описаны в [349].Чтобы понять основной принцип этих алгоритмов, предположим, что все обновления конкретных элементов данных инициируются одним сервером. Такимобразом, мы просто исключаем возможность конфликтов двойной записи.
Дальнейшее изложение основано на классической статье по эпидемическим алгоритмам [124].Модели распространения обновленийКак следует из названия, эпидемические алгоритмы основываются на теорииэпидемий, которая объясняет правила распространения инфекционных заболеваний. Если вместо инфекционных заболеваний взять реплицируемые хранилищаданных, они будут распространять обновления. Исследования эпидемий в хранилищах данных преследуют также и совершенно иную цель: в то время как органыздравоохранения считают, что было бы великолепно не допустить активного распространения инфекционных заболеваний, разработчики эпидемических алгоритмов для распределенных хранилищ данных стараются «заразить» все репликиобновлениями как можно быстрее.Используя терминологию эпидемиологов, сервер, являющийся частью распределенной системы, называется инфицированным {infective), если на нем хранится обновление, которое он готов распространять на другие серверы.
Сервер,который еще не получил обновления, называется восприимчивьш {susceptible).И наконец, сервер, данные которого были обновлены, но не готовый или неспособный распространять обновление дальше, называется очищенным {removed).Одна из популярных моделей распространения — антиэнтропия {antientropy). Согласно этой модели сервер Р случайным образом выбирает другойсервер Q, после чего обменивается с ним обновленршми. Существует три способаобмена обновлениями:4- сервер Р только продвигает свои обновления на сервер Q;4 сервер Р только извлекает новые обновления с сервера Q;4 серверы Р и Q пересылают обновления друг другу (то есть метод «тянито лкая»).В отношении скорости распространения обновлений плохим выбором кажется только продвижение обновлений.
Интуитивно это можно объяснить следующим образомг Во-первых, отметим, что при чистом продвижении обновлениямогут распространяться только инфицированными серверами. Однако если инфицировано множество серверов, вероятность того, что каждый из них случайно376Глава 6. Непротиворечивость и репликациявыберет восприимчивый сервер, относительно мала (скорее они будут натыкаться друг на друга).
Соответственно, имеется шанс на то, что какой-то из серверовв течение длительного времени будет оставаться восприимчивым просто потому,что он не был выбран инфицированным сервером.В противоположность этому, извлечение обновлений при большом количестве инфицированных серверов будет работать гораздо лучше. В этом случае распространение обновлений, в сущности, возлагается на восприимчивые серверы.Шансы значительно выше, ведь теперь сам восприимчивый сервер должен связаться с инфицированныхМ сервером, чтобы затем получить от него обновления исамому стать инфицированным.Можно показать, что если изначально инфицирован лишь один сервер, прииспользовании любой из форм антиэнторпии обновления потенциально могутраспространиться на все серверы. Однако, чтобы убедиться, что обновления распространяются быстро, имеет смысл задействовать дополнительный механизм,при помощи которого более или менее инфицированными немедленно стануткак минимум несколько серверов.
Обычно в таком случае помогает прямое продвижение обновления на несколько серверов.Один из специальных вариантов подобного подхода именуется распространением слухов {rumor spreading), или просто болтовней {gossiping). Он работаетследующим образом. Если на сервере Р имеется обновленный элемент данных х,значит, он связывается с другим произвольным сервером Q и пытается продвинуть обновление на Q.
Однако возможно, что Q У^^ получил это обновление сдругого сервера. В этом случае Р может потерять интерес к дальнейшему распространению обновления, скажем, с вероятностью \/k. Другими словами, он становится очищенным.Болтовня полностью соответствует реальной жизни.
Если Боб узнает какуюто «жареную» новость, о которой можно посплетничать, он, скорее всего, позвонит своей подружке Алисе и все ей расскажет. Алиса, как и Боб, будет заинтересована в том, чтобы нести эту новость дальше. Однако она может быть разочарована, если, позвонив приятелю, скажем Чаку, услышит от него, что он уже знаетэту новость. Имеется шанс на то, что она перестанет обзванивать своих друзей.Зачем ей это, если все и так знают ее новость?Болтовня может быть действительно хорошим способом быстрого распространения обновлений. Однако оно не гарантирует, что будут обновлены все серверы[124].
Можно показать, что в случае хранилищ данных, содержащих множествосерверов, доля s серверов, которые не получат обновления, то есть останутся восприР1мчивыми, рассчитывается следующим образом:Например, при ^ = 3 значение s составляет менее 0,02. Это означает, что восприимчивыми останутся менее 2 % серверов. Тем не менее следует принять специальные меры, чтобы гарантировать, что эти серверы также будут обновлены.Комбинирование антиэнтропии с механизмом распространения слухов — однаиз таких уловокОдно из основных преимуществ эпидемических алгоритмов — их масштабируемость, вытекающая из того факта, что синхронизировать друг с другом при-6.5.
Протоколы непротиворечивости377холится относительно мало процессов по сравнению с другими методами распространения. В [266] показано, что для глобальных систем для получениялучших результатов имеет смысл учитывать особенности топологии. При этомподходе серверы, соединенные с малым количеством других серверов, контактируют с относительно большей вероятностью.
Предполагается, что эти серверыформируют мостик к другим, удаленным частям системы, а поэтому должнысвязываться друг с другом как можно чаще.Удаление данныхЭпидемические алгоритмы хорошо подходят для распространения обновлений впричинно непротиворечивых хранилищах данных. Однако у них имеется довольно странный побочный эффект: затрудненное распространение удалений элементов данных. Сущность проблемы заключается в том факте, что удаление элементаданных уничтожает всю информацию об этом элементе. Соответственно, еслиэлемент данных просто изъять с сервера, сервер может, получив старые копииэлемента данных, интерпретировать их как обновления, включающие в себя новый элемент.Хитрость состоит в том, чтобы зафиксировать факт удаления элемента данныхв виде очередного обновления и сохранить о нем запись.
При этом старые копиибудут считаться не новыми элементами, а просто старыми версиями, которыебыли обновлены при помощи операции удаления. Запись о произведенном удалении выполняется путем рассылки свидетельств о смерти (death certificates).Разумеется, остается проблема свидетельств о смерти, состоящая в том, что иони в конечном итоге также должны быть удалены. В противном случае каждыйсервер постепенно накопит гигантскую никому не нужную локальную базу данных с исторической информацией об удаленных элементах данных.
В [124]предложено использовать так называемые спящие свидетельства о смерти. Каждое свидетельство о смерти получает отметку о времени создания. Если предположить, что обновления распространяются на все серверы за известное конечноевремя, то по истечении максимального времени распространения свидетельствоо смерти можно удалять.Однако для получения твердой гарантии того, что удаление действительнораспространилось на все серверы, только очень немного серверов поддерживаютспящие свидетельства о смерти, никогда не передавая их дальше.
Предположим,что сервер Р имеет подобное свидетельство на элемент данных х. Если из-за какой-то случайности на Р придет устаревшее обновление для х, сервер Р отреагирует на это событие просто повторной рассылкой свидетельства о смерти этогоэлемента данных.6.5. Протоколы непротиворечивостиДо сих пор мы в основном обсуждали различные модели непротиворечивости иобщие вопросы проектирования протоколов непротиворечивости. В этом разделемы сосредоточимся на конкретных реализациях моделей непротиворечивости378Глава 6. Непротиворечивость и репликацияи рассмотрим несколько реальных протоколов непротиворечивости. Протоколнепротиворечивости (consistency protocol) описывает реализацию конкретной модели непротиворечивости.
Вообще говоря, очень важны и широко используютсямодели непротиворечивости, в которых операции обладают глобальной сериализуемостью. Имеются в виду такие модели, как последовательная непротиворечивость, слабая непротиворечивость с переменными синхронизации, а такжеатомарные транзакции.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
