Ниже - мой доклад на семинаре о кэшировании в NFS и немного о NFS в целом. В самом конце - презентация, где на диаграммах все несколько понятнее.

Кэширование в сетевых ФС

Сетевые файловые системы становятся всё более популярны, в связи с чем возникает потребность ускорять их, а в частности, повышать доступность. Одним из таких решений возникло - кэширование данных на стороне клиента. То есть для работы с данными, клиенту не обязательно каждый раз обращаться на сервер - когда есть локальные данные можно работать с ними, а потом отправлять изменения на сервер целым пакетом.

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

NFS

Для того, что бы как-то конкретизировать понимание принципов кеширования файловых систем - рассмотрим пример Network File System (NFS). NFS - это протокол сетевого доступа к файловым системам, основанный на протоколе вызова удаленных процедур (ONC-RPC, разработанным Sun Microsystems). NFS абстрагирован от локальных файловых систем как сервера, так и клиента, что позволяет использовать его между совершенно различными программными и аппаратными архитектурами.

Исторически и из определенных соображений удобства, NFS сервер принимает запросы от клиента на TCP2049 порту, а сессия устанавливается на UDP2049 порту, хотя в последних версиях (выше 4) появилась возможность работать только через TCP. При этом, трафик NFS никак не шифруется и при желании может легко быть прочитан (хоть и не без помощи декодеров).

Основным преимуществом NFS (после кроссплатформенности) считается возможность прозрачной работы с удаленным каталогом/разделом так же, как если бы это была локальная файловая система.

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

В реализации NFS кэширование удобно следующими позициями:

• Когда клиент читает большой файл, используя NFS-буфер, то асинхронно, пока содержимое буфера скидывается для локаьного отображения, заполняется ещё один буфер и.т.д. Таким образом, необходимые данные могут оказаться на клиенте уже в тот момент, когда он только их запросит (в связке с “упреждающим чтением”.
• В операциях записи мелких файлов, либо большого количества мелких правок одного файла - все изменения записываются лишь локально, а на сервер отправляется финальная версия всего сразу.

Каждый раз перед выполнением операции OPEN клиент обязан перепроверить кэш и синхронизировать его с данными на сервере. Это обеспечивает актуальность открытых данных. Помимо этого, клиенты могут делать проверку и чаще. Перед закрытием файла данные обязательно сохраняются на сервер. Для разграничения доступа к большим файлам может применяться кеширование диапазона байт. В таком случае, клиент должен точно знать, какому файлу и какому месту в файле соответствует данный диапазон, и также перепроверять при обращении и отправлять результаты на сервер при записи. Кэширование директорий же несколько отличается: при первом открытии директории запрашивается GETATTR (для проверки кэша), а последующие проверки выполняются только ПОСЛЕ прочтения директории, то есть, возможно, пользователю отображается неактуальный кэш.

В связи с тем, что данные накапливаются у клиента и отправляются на сервер асинхронно, возникает узкое место, когда данные уже отправлены на сервер, подтверждение не получено и отправляются новые данные. В версии NFSv2 это было очень острой проблемой, которую постарались решить в NFSv3 - с помощью логики транзакций и подтверждений. В версии 3 данные отправляются сначала в хранилище без доверия, после чего сервер высылает подтверждение о получении клиенту и клиент подтверждает запись данных. Таким образом, “условие гонки” было побеждено.

Протокол NFSv4.1 в плане кеширования стал некоторым шагом назад, потому что перестал обеспечивать распределенную согласованность кэша, то есть кэш не всегда совпадал с тем, что происходит на сервере, однако за счет этого, появилась возможность делегирования операций открытия, записи и блокировок между локальными клиентами, то есть, клиент кэш на клиенте стал общим для всех его процессов и работа с данными в кэше была отдана на распоряжение локальной файловой системе. Такой механизм более соответствовал реальным потребностям, когда множественное обращение к файлу случается нечасто или когда файл распределяется только для чтения.

Операции NFS

• LOOKUP - возвращает хэндл для запрашиваемого файла/директории
• GETATTR/SETATTR - возвращает/устанавливает аттрибуты и права на файл
• READ/WRITE - чтение/запись хэндла файла, однако зависят от контекста.
• STATFS - возвращает общую информацию с сервера.
• CREATE/REMOVE - создать/удалить файл.
• LINK/SYMLINK - создать ссылку/символьную ссылку на файл
• READLINK - получить хэндл файла по ссылке.
• MKDIR/RMDIR - создать/удалить директорию
• READDIR - вернуть листинг директории
• AUTH_NONE/UNIX/* - аутентификация на сервере

В pNFS появилась модель Layouts, выступающая вместо самих файлов, в связи с чем появилось несколько команд с префиксом LAYOUT_*, для создания, удаления и модификации слоев, но pNFS не является частью данного доклада, поэтому опустим.

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

Стратегии кэширования, используемые в предыдущих версиях NFS были успешны в обеспечении производительности, однако, с увеличением числа клиентов, появилась проблема географической распределенности, когда задержки сетевого доступа у клиентов становились всё больше и больше. Предыдущие версии NFS, в то время, как файл был открыт, периодически отправляли запросы о ревалидации кэша. Такое поведение несет в себе определенную нагрузку, которая достигает своего максимума в том случае, если с файлом работает только один клиент. Хорошее предположение, что если клиент периодически открывает один и тот же файл - позволить ему делать это без обращения к серверу. Но множественные обращения к файлу никто не отменял и в такой ситуации они вызовут конфликт. Похожая проблема возникает и когда кэширование производится не для файла целиком, а лишь для диапазона данных. Частые блокировки/разблокировки становятся бессмысленными в ситуации редких конфликтов - и несут ненужную нагрузку.

Когда клиент запрашивает файл, сервер открывает обратное соединение (которое клиент ОБЯЗАН реализовать), в котором делегирует этому клиенту управление доступом к файлу, запоминая у себя, с каким ClientID и файлом связано делегирование. Клиент не должен полагаться на это соединение и должен быть готов выполнять операции и без него, однако должен всегда ожидать переподключения. Локальные блокировки клиент обрабатывает не извещая об этом сервер. Когда другой сетевой клиент запрашивает этот же файл, сервер перезапрашивает делегирование у первого клиента, предоставляя (или отказывая в этом) запросившему.

Сервер может перезапрашивать делегирование в любое время, когда посчитает это необходимым, даже в том случае, если никаких операций, требующих перезапроса не было. Если же какие-то операции над данными произошли извне протокола (локально или по другим протоколам) - сервер также должен перезапросить делегирование и оно должно быть предоставлено или отклонено до того, как операция будет разрешена.

Когда клиент получает перезапрос делегирование - он отправляет все изменения (если таковые были) на сервер и возвращает делегирование. Делегирование должно быть вовращено до того, как конфликтующие операции будут выполнены. Перезапрос считается выполненным, если клиент вернул делегирование, либо если превышен таймаут на сервере, тогда делегирование отклоняется. (Очевидно, сервер решает конфликтную ситуацию не в пользу клиента, которому отклонено делегирование). Если в результате RPC запросов сервер видит, что клиент отправляет изменения, но их слишком много, то он может увеличить таймаут делегирования для нормального завершения ситуации.

Чтобы различать данные, которые необходимо кэшировать, в NFSv3 применялась типичная практика, что разные хэндлы файлов представляют разные файлы. Но в NFSv4.1 файл, закешированный локально может быть доступен нескольким клиентам, но из-за различий в пути может быть представлен разными хэндлами. Было бы бессмысленно вводить делегирование, если общий кэш использовался бы неправильно, поэтому появился новый способ различия файлов:

• Если GETATTR двух разных файловых хэндлов возвращает разные значения fsid, то и файлы разные.
• Если GETATTR вернул одинаковые значения fsid, но unique_handles=TRUE - файлы разные.
• Если GETATTR хотя бы у одного хэндла не вернул fileid, то о совпадении или различии файлов сказать ничего нельзя, даже если fsid совпал.
• Если GETATTR вернул разные значения fileid - то файлы разные.

Во всех остальных случаях файлы совпадают.

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

Стратегии кэширования

Существует несколько моделей - стратегий кэширования:

• Least Recently Used То что дольше всего неиспользовалось - вытесняется в первую очередь. Имеет накладные расходы, так как необходимо помнить “возраст” каждого объекта в кэше.
  • Возможно реализовать LRU-кэш с помощью очереди: Какой бы блок из кэша не использовался - он помещается в конец очереди. Таким образом, в конце всегда будет самый последний использованный, а в начале - наиболее давно неиспользуемый - и его можно будет заменить.(выбросить из кэша).
• Most recently Used Вытесняется последний использованный элемент. Логика стратегии в том, что элемент, только что использовавшийся - вряд ли понадобится в будщем. Стратегия полезна при операциях с частой сменой объектов и малым числом повторений.
• Псевдо-LRU Достаточно не следить за самым старым, а выбрасывать наименее используемый.
• Сегментированный LRU Кэш из двух сегментов - защищённый и пробный. В защищенный попадают только после того, как были в пробном и использовались. Пробный - модель MRU, защищённый - LRU. Таким образом, данные из защищённого сегмента будут использованы по крайней мере 2 раза.
• Least-Frequently Used Постоянно считает, как часто используются элементы - выбрасывает наименее используемый. Например, вместе с блоком в кэше можно хранить счётчик доступов к нему. При этом, счётчик увеличивается только при операциях чтения - запись же оставляет счётчик прежним. Таким образом, в очередной раз при поиске блока, который необходимо вытеснить из кэша - выбирается блок с наименьшим значением счётчика. (В примере необходимо помнить, что некоторые блоки могут достигнуть слишком больших значений и никогда не будут убираться из кэша - об этом необходиом позаботиться, например уменьшая все частоты каждый раз, как средняя частота всех блоков достигнет некоторого порогового значения)
• Адаптивная замена Балансирует между LRU и LFU, что улучшает итоговый результат.
• Очередь Вытесняется по принципу очереди, без каких либо дополнительных алгоритмов.
• Случайный Элемент для вытеснения выбирается случайным образом.

В связи с тем, что стратегия файловых систем, используемых Unix/Linux, такова, что файлы читаются последовательными блоками - оптимальным кэшированием локальных операций несомненно будет LRU/MRU (то есть, стратегии, основанные на времени использования, а не частоте). Но логика работы с файлами подсказывает, что в среднем, файлы не только читаются (преимущество MRU), но и записываются. И обычно, записываются сразу после чтения, что подразумевает работу с одним и тем же файлом продолжительное время. В такой ситуации, очевидно, необходимо иметь в кэше только что прочитанный элемент, поэтому меньший приоритет отдается тем файлам, которые использовались наиболее давно.

Но для NFS, где используются асинхронные RPC вызовы - последовательность может не сохраняться и LRU должен показать меньшее ускорение, нежели локальный LRU. Однако, на практике, всё же часто используется LRU, так как его производительность удовлетворяет многим параметрам.

Презентация

Список литературы:

• Managing NFS and NIS Авторы: Mike Eisler,Ricardo Labiaga,Hal Stern

• Analysis of caching algorithms for distributed file systems

  Авторы:

  • Benjamin Reed Department of Computer Science, University of California, Santa Cruz, CA
  • Darrell D. E. Long Department of Computer Science, University of California, Santa Cruz, CA

• Collective Caching: Application-aware Client-side File Caching

  Авторы:

  • Wei-keng Liao, Kenin Coloma, Alok Choudhary (Electrical and Computer Engineering Department Northwestern University)
  • Lee Ward, Eric Russell, and Sonja Tideman (Scalable Computing Systems Department Sandia National Laboratories)

• RFC 5661 - NFS Version 4 Minor Version 1 Internet Engineering Task Force (IETF), ISSN: 2070-1721

  Авторы:

  • S. Shepler, Ed.
  • Storspeed, Inc.
  • M. Eisler, Ed.
  • D. Noveck, Ed.