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

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

10.2.

Файловая система Coda 661

БД репликации

Г^" 1 IU "^ ^^

1 RVID

Дескриптор файла

VID1,

VID2

f=J

БД размещения

томов

Фай]

-^Сервер

Дескриптор файла |

Сервер1

Сервер2

1 W

новый сервер

(С—^

Файловый сервер

^-^Cepвep| Дескриптор файла |

1 ^

—1Ш1ЭД

Рис. 10,19, Реализация и разрешение идентификатора файла в Coda

10.2.5. Синхронизация

Многие распределенные файловые системы, включая предка Coda, систему AFS,

не поддерживают семантику разделения файлов UNIX, предоставляя вместо это-

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

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

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

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

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

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

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

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

Если бы у отсоединившегося клиента все нужные ему файлы были в локальном

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

нении с системой согласовал бы их с храняш;имися в системе копиями.

Разделение файлов в Coda

Чтобы поддерживать разделение файлов. Coda использует специальную схему

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

нием в

NFS.

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

Когда клиент успешно открывает файл /, на машину клиента пересылается точ-

ная копия этого файла /. Сервер записывает, что данный клиент имеет копию /.

Таким образом, этот подход схож с делегированием открытия в NFS.

Теперь предположим, что клиент А открыл файл / на запись. Когда другой

клиент, В, также хочет открыть файл /, у него ничего не выходит, поскольку сер-

вер уже зафиксировал тот факт, что клиент А имел возможность к этому момен-

ту изменить файл /. С другой стороны, если бы клиент А открыл файл / на чте-

662 Глава 10. Распределенные файловые системы

ние,

то

попытка клиента

получить

сервера копию файла

также для чтения

была бы успешной,

как и

попытка

получить этот файл для записи.

Рассмотрим теперь, что произойдет, если

клиентов будут локально хранить-

ся несколько копий файла. Произойдет именно то,

чем мы сейчас говорили

—

только один клиент сможет модифицировать файл/ Если этот клиент изменит/

и закроет файл, файл будет передан обратно

на

сервер. Однако

все

остальные

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

на

то,

что

эти копии устарели.

Причина такого поведения, явно нарушающего непротиворечивость данных,

состоит

том,

что

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

Coda

как

транзакция.

На

рис.

10.20

приведена временная диаграмма двух процессов, А

В.

Предполагается, что кли-

ент

А в

ходе сеанса

открыл

на чтение,

клиент

В в

ходе сеанса

5в

—

на за-

пись.

Сеанс

Клиент

Объявить

Файл копию

неправильной

Файл

Время

Сеанс

Рис. 10.20. Транзакционное поведение при совместном использовании файлов

Coda

Когда клиент

закрывает сеанс

SB,

ОН

пересылает измененный вариант

на

сервер, который посылает клиенту А сообщение о неправильности его копии. А те-

перь знает,

что

производит чтение устаревшей версии файла

Однако

точки

зрения транзакции это

не

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

был

на-

чат раньше сеанса

SB^

Транзакционная семантика

в Coda ключевую роль для определения транзакционной семантики играет поня-

тие раздела сети.

Раздел

(partition)

—

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

сети

содержащая коллекцию клиентов, серверов

или тех и

других. Основная

идея состоит в том, что последовательность операций с файлами должна продол-

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

ти.

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

ра-

ботают

одними

теми

же

данными

и как

минимум одна

из них

выполняет

запись.

Давайте сначала рассмотрим,

как

может возникнуть конфликт

при

наличии

разделов сети. Предположим, два процесса, Л

и 5,

до момента их отделения друг

от друга

результате дробления сети

на

разделы имеют идентичные реплики

10.2.

Файловая система Coda 663

различных разделяемых элементов данных. В идеале файловая система, поддер-

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

поочередную сериализацию

ко-

пий (one-copy

serializability),

то

есть выполнение операций процессами

А и В,

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

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

цессами. Эта концепция подробнее обсуждается

[118].

Мы уже рассматривали примеры сериализации

главе 5. Основная проблема,

возникающая при разбиении сети

на

разделы,

—

это распознавание факта сериа-

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

при

восстановлении

из

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

произошедших

каждом разделе (возможно,

теневых копиях, то есть

копиях

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

каций, аналогично теневым блокам в транзакциях). При этом необходимо прове-

рить,

можно

ли

сериализовать выполнение связанных операций

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

с последовательностью

их

поступления. Обычно это нелегкая задача.

Способ, который применятся

Coda для решения этой проблемы,

—

трактов-

ка сеанса как транзакции. Типичный сеанс начинается

явного открытия файла

вызовом open. Далее обычно следует последовательность операций записи

чте-

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

Большинство системных вызовов UNIX образуют один сеанс, состоящий

из са-

мих вызовов, который рассматривается

Coda как независимая транзакция.

Coda распознает разные типы сеансов. Так, например, каждый системный вы-

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

сеансов считаются те, которые начинаются вызовом open. Тип сеанса автоматиче-

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

мущество подобного подхода состоит

в том, что

приложение, использующее

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

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

В качестве примера рассмотрим сеанс

сохранения

{store),

который начинается

с открытия файла/на запись

от

имени определенного пользователя и,

как

опи-

сывалось выше. В табл. 10.10 перечислены метаданные, ассоциированные

фай-

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

ваться или вдобавок еще

модифицироваться. Так, например, может возникнуть

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

и к

файлу

При явном

оп-

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

модифицируются

конкретном

сеансе, определить конфликтующие операции гораздо проще.

Таблица 10.10. Чтение и модификация метаданных для сеанса сохранения в Coda

Ассоциированные

файлом данные Чтение Модификация

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

Да Нет

Права доступа

Да Нет

Время последней модификации

Да Да

Длина файла

Да Да

Содержимое файла

Да Да

664 Глава 10. Распределенные файловые системы

После явного определения метаданных выяснить ход сеанса достаточно про-

сто.

Начнем с рассмотрения серий одновременных сеансов, происходящих в од-

ном разделе сети. Для простоты предположим, что этот раздел расположен на

одном сервере. Когда клиент начинает сеанс, процесс Venus на клиентской ма-

шине получает от сервера все данные, содержащиеся в наборах операций чтения

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

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

ки чтения и записи.

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

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

вому),

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

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

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

необходимые блокировки в самом начале сеанса.

Второе замечание состоит в том, что раз уж семантика разделения файлов на

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

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

двухфазной блокировки (2PL), которую мы разбирали в главе 5. Важным свой-

ством 2PL является возможность упорядочения всех запланированных операций

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

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

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

лами. С этой целью Coda использует простую схему версий. Каждый файл имеет

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

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

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

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

данных.

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

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

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

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

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

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

тором они происходили на клиенте.

Когда изменения, сделанные в файле /, передаются на сервер, мы априори

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

ра, не изменяли информацию в файле /. Конфликт подобного рода может быть

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

Vdient —

номер версии

/, полученной с сервера при передаче файла клиенту. Пусть

Nupdates

— число

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

сле повторного подключения. И наконец, пусть

Vnow —

текущий номер версии /,

находящейся на сервере. В этом случае следующее обновление / в ходе сеанса

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

^now "*" i ~ ^client ' ^updates •

10.2.

Файловая система Coda 665

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

ли это изменение приведет к появлению следующей версии файла /. На практи-

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

конфликт будет так или иначе разрешен.

Конфликты возникнут, если файл/будет изменяться в параллельно происхо-

дящих сеансах. При возникновении конфликта обновления, сделанные в ходе се-

анса с клиентом, отменяются, но клиент в принципе может сохранить свою вер-

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

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

разрешение конфликта оставляется пользователю. Ниже мы еще вернемся к это-

му вопросу.

10.2.6.

Кэширование и репликация

Как теперь должно быть понятно, кэширование и репликация играют в Coda важ-

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

работчиками Coda цели

—

высокой доступности. Далее мы сначала рассмотрим

кэширование на стороне клиента, которое требуется при выполнении операций

в отрыве от сервера. После этого мы рассмотрим репликацию томов на сервере.

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

Кэширование на клиенте чрезвычайно важно для системы Coda по двум причи-

нам. Во-первых, в русле подхода, принятого в AFS

[398],

кэширование выполня-

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

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

этим двум причинам клиенты в Coda всегда кэшируют файлы целиком. Другими

словами, когда файл открывается

—

на чтение или на запись,

—

клиенту передает-

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

В отличие от многих других распределенных файловых систем, согласован-

ность кэша в Coda обеспечивается при помощи обратных вызовов. Для каждого

файла сервер хранит информацию обо всех клиентах, которым была выслана

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

сывает для клиента

обещание обратного вызова {callback

promise).

После того как

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

этом сервер, который, в свою очередь, рассылает остальным клиентам сообще-

ния о некорректности их копий. Это сообщение о некорректности копий называ-

ется отменой

обратного

вызова

{callback

break), поскольку сервер освобождает

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

измененной версии.

Интересный аспект этой схемы состоит в том, что до тех пор, пока клиент

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

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

своего кэша. Он может использовать этот предоставленный сервером файл до

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

Клиент может проверить на сервере, действительно ли еще это обещание. Если

666 Глава 10. Распределенные файловые системы

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

у сервера.

Этот подход иллюстрирует рис.

10.21,

который представляет собой дальней-

шую доработку рис. 10.20. Когда клиент А начинает сеанс 5л, сервер записывает

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

ет сеанс

SB.

Однако когда В закрывает сеанс 5^, сервер отказывается от обещания

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

что в соответствие с транзакционной семантикой Coda, когда клиент А закрыва-

ет сеанс

SA,

не происходит ничего особенного; закрытие просто принимается как

ожидаемое событие.

Сеанс 8д

Клиент А

Открыть

на чтение

Сервер

Объявить копию

неправильной

(отмена обратного

Файл вызова)

Открыть

на запись

Файл

Закрыть

Открыть

на чтение

Открыть

на запись

Закрыть

Файл

ОК (файл

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

Закрыть

Клиент В

Сеанс Sg Сеанс Sg Время •

Рис.

10.21.

Использование локальных копий при открытии сеанса

Coda

Когда клиент А позже захочет открыть сеанс

S'A,

ОН

обнаружит, что его ло-

кальная копия файла неправильная и нужно получать новую версию с сервера.

С другой стороны, когда В откроет сеанс

S'B,

ОН

обнаружит, что сервер по-преж-

нему поддерживает оставленное им обещание обратного вызова, а значит, В мо-

жет просто использовать локальную копию файла, сохранившуюся у него в кэше

после сеанса

SB-

Репликация серверов

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

репликации является том. Коллекция серверов, имеюш;их копию тома, известна

под названием

группы

хранилищ

тома (Volume Storage

Group,

VSG). В случае от-

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

ма. Группа доступных хранилищ тома

{Accessible Volume

Storage

Group,

AVSG)

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

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

соединенньш

{disconnected).

Для поддержания непротиворечивости реплицированного тома Coda исполь-

зует протокол реплицированнои записи. Так, в частности, используется вариант

«читаем раз, пишем все» (Read-One

—

Write-All, ROW

А),

который мы рассмат-

ривали в главе 6. Когда клиенту нужно прочесть файл, он связывается с одним

10.2.

Файловая система Coda 667

из членов группы AVSG тома, на котором находится этот файл. Однако при за-

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

нам AVSG. Эта параллельная пересылка выполняется при помощи вызовов

multiRPC, как было описано ранее.

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

для каждого клиента, у которого группа AVSG тома совпадает с его группой VSG.

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

реплицированный на три сервера

—

5i, 52 и 5з. Предположим, что для клиента А

AVSG состоит из серверов 5i и 52, а клиент В имеет доступ только к серверу 5з,

как показано на рис. 10.22.

• 1

Клиент

Сервер

^1 7г*\

Сервер

Разрыв

сети

-Q

Клиент

Рис. 10.22. Два клиента с разными группами AVSG для одного реплицированного файла

Coda использует оптимистическую стратегию репликации файлов. В частно-

сти,

обоим клиентам, Л и В, будет разрешено открывать файл / на запись, изме-

нять соответствующие копии и передавать эти копии назад, членам AVSG. По-

нятно, что в результате в VSG окажутся разные версии файла. Вопрос состоит

в том, как обнаружить и устранить это противоречие.

В Coda эта задача решается при помоиди расширения схемы версий, которую

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

Si,

входящий в VSG, поддер-

живает

вектор версий Coda {Coda version vector)

CVVi{f) для каждого файла/, со-

держащегося в данной группе VSG. Если CWi{f)[j] =

значит, серверу 5/ извест-

но,

что сервер 5, содержит как минимум версию k файла /. CFV;[/]

—

это номер

текущей версии /, хранящейся на сервере 5/. Изменение / на сервере 5/ приведет

к увеличению CWi[z]. Отметим, что механизм векторов версий полностью анало-

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

Вернемся к нашему примеру с тремя серверами. Вектор CWi{f) изначально

равен [1,1,1] для каждого из серверов

5j.

Когда клиент А считывает/с одного из

серверов своей группы AVSG, скажем, 5i, он получает также и CW\{f). После

изменения / клиент Л производит рассылку /

всем

серверам своей группы AVSG,

то есть серверам S\ и

52.

Оба сервера после этого записывают тот факт, что их ко-

пии были изменены, а копия 5з не изменялась. Другими словами:

CW,{f) = CVV2{f) =

[2,2,1].

Тем временем клиент В открывает сеанс, получая при этом копию/с сервера 5з,

после чего изменяет ее. После закрытия сеанса он передает изменения на сервер 5з,

который изменяет свой вектор версий на CVV^if) =

[1,1,2].

668 Глава 10. Распределенные файловые системы

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

ра должны объединить свои копии /. Сравнив векторы версий, они обнаружива-

ют, что между ними существует конфликт, который необходимо устранить. Во

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

разрешения в приложении, как утверждается в

[243].

Однако остается еще нема-

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

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

и того же файла.

10.2.7.

Отказоустойчивость

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

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

и репликации серверов. Мы обсуждали то и другое в предыдущем подразделе.

Интересная особенность Coda, требующая дополнительного обсуждения: как

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

ность отключения составляет несколько часов или дней.

Операции в автономном режиме

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

па AVSG для этого тома пуста. Другими словами, клиент не может связаться ни

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

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

связаться хотя бы с одним сервером. В Coda принят иной подход. Здесь клиент

просто переключается на свою локальную копию файла, которую он получил, ко-

гда открывал файл на сервере.

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

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

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

автоматическое разрешение конфликтов невозможно, требуется вмешательство

человека. Практический опыт использования Coda показывает, что операции

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

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

Успешность подхода, используемого в Coda, в основном объясняется тем фак-

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

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

же файл на запись. Разумеется, совместное чтение из файлов встречается гораз-

до чаще, но оно не вызывает каких-либо конфликтов. Эти замечания относятся

также и к другим файловым системам (о разрешении конфликтов в сильно рас-

пределенных файловых системах см., например, [338]). Кроме того, транзакци-

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

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

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

но вносит в него изменения.

10.2.

Файловая система Coda 669

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

шить серьезную проблему

—

как гарантировать, что в кэше клиента окажутся

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

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

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

лов.

Заблаговременное заполнение кэша нужными файлами называется накопле-

нием (hoarding). Отношения клиента и тома (а значит, и файлов в этом томе)

можно теперь продемонстрировать на диаграмме в виде конечного автомата, ко-

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

10.23.

( НАКОПЛЕНИЕ )

Отсоединение / \ Завершение

Отсоединение \ восстановления

(

ЭМУЛЯЦИЯ

)

(ВОССТАНОВЛЕНИЕ)

Повторное

соединение

Рис. 10.23. Диаграмма отношений клиента Coda и тома

виде конечного автомата

Обычно клиент находится в состоянии

накопления.

В этом состоянии клиент

соединен как минимум с одним сервером, содержащим копию тома. Находясь

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

на файлы, необходимые для работы. Одновременно он также старается сохра-

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

и каталоги).

В определенный момент число серверов в AVSG клиента падает до нуля, что

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

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

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

пий файла. Отметим, что когда клиент находится в состоянии эмуляции, он по-

прежнему может связываться с серверами, поддерживающими другие тома. В этих

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

физическим отключением клиента от сети.

И, наконец, когда происходит восстановление связи, сервер переходит в со-

стояние

восстановления,

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

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

ности автоматически разрешаются конфликты. Как показано на

рис.

10.23,

суще-

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

потеряна и клиент вернется обратно в состояние эмуляции.

Для успешного продолжения операций после отсоединения решающим фак-

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

бы гарантированно это обеспечить. Coda использует сложный механизм приори-

тетов. Во-первых, пользователь может явно указать, какие файлы или каталоги

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

670 Глава 10. Распределенные файловые системы

{hoard

database).

Coda поддерживает подобные базы на своих рабочих станциях.

Сочетание информации из базы данных накопления с информацией о последних

запросах к файлам позволяет Coda вычислить текущий приоритет каждого фай-

ла, после чего файлы загружаются в кэш в соответствии с их приоритетом так,

чтобы выполнялись следующие три условия:

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

у любого кэшированного файла;

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

тетом должны быть кэшированы;

"f каждый из кэшированных файлов должен быть копией файла, поддержи-

ваемого в группе AVSG клиента.

Детали вычисления текущего приоритета файла описаны в

[235].

Если все

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

равновесии

{equilibrium).

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

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

вободить место для других файлов. То есть равновесие кэша время от времени

необходимо пересчитывать. Реорганизация кэша с целью достижения равнове-

сия называется

инвентаризацией накопления {hoard walk)

и выполняется каждые

10 минут.

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

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

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

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

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

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

осуществление операций в автономном режиме будет невозможно по причине

недоступности данных.

Восстанавливаемая виртуальная память

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

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

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

данных, носит название

восстановимой виртуальной

памяти

{Recoverable

Virtual

Memory,

RVM). RVM

—

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

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

достаточно несложное их восстановление после сбоев. Детально технология RVM

описана в

[400].

Идея, лежащая в основе RVM, относительно проста: данные, которые долж-

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

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

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

На самом деле модель, на которой построена технология RVM, близка к модели

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

раллельного доступа.