Функция, подобная Inotify, в распределенной файловой системе

Если у вас есть только черный ящик доступа (например, протокол NFS) к удаленным системам, у вас не так много вариантов, если только протокол не поддерживает то, что вам нужно. Итак, я предполагаю, что вы контролируете удаленные системы.

«Тривиальный» подход заключается в запуске локального прослушивателя inotify/fanotify на каждом компьютере, который будет пересылать уведомление по сети. FAM может делать это через NFS.

Проблемой всех систем, основанных на уведомлениях, является риск потери уведомлений в различных крайних случаях. Это становится намного более острым в сети - например. клиент подтверждает получение уведомления, после чего сразу вылетает. Существуют надежные очереди сообщений, на которые вы можете опираться, но, ИМХО, это безумие...

Более разумным подходом является сканирование на основе хеша без сохранения состояния.

Мне нравится называть следующий дизайн «hnotify», но это не общепринятый термин. Эти идеи широко используются многими системами контроля версий и резервного копирования, начиная с Plan 9.

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

Почему хэш-деревья — это круто? Если у вас есть 2 хеш-дерева — одно представляет состояние файловой системы, которое вы видели в какой-то момент в прошлом, другое представляет текущее состояние — вы можете легко узнать, что изменилось между ними:

1. Вы начинаете с корней. Если они разные, вы читаете 2 корневых каталога и сравниваете хэши для подкаталогов.
2. Если подкаталог имеет одинаковый хэш в обоих деревьях, то ничего под ним не изменилось. Нет смысла туда идти.
3. Если хэш подкаталога изменился, рекурсивно сравнить его содержимое — вызвать шаг (1).
4. Если у одного есть подкаталог, у другого его нет, что ж, это изменение. С некоторой глобальной таблицей вы также можете обнаруживать перемещения/переименования.

Обратите внимание, что если изменилось несколько файлов, вы читаете только небольшую часть текущего состояния. Таким образом, удаленная система не должна отправлять вам все дерево хэшей, это может быть интерактивный пинг-понг типа «дайте мне хэши для этого каталога; хорошо, теперь для этого ...».
(Это похоже на как работал тупой http-протокол Git ; есть более новый протокол с меньшим количеством поездок туда и обратно.)

Это так же надежно и защищено от ошибок, как опрос всей файловой системы на наличие изменений — вы ничего не пропустите — но достаточно эффективно!

Но как сервер отслеживает текущие хэши?

К сожалению, полное хеширование всех операций записи на диск слишком дорого для большинства людей. Вы можете получить if бесплатно, если вам повезло, что у вас есть дедуплицирующая файловая система, например. ZFS или Btrfs.
В противном случае вам придется перечитывать все измененные файлы (что еще дороже, чем делать это на уровне файловой системы) или использовать фальшивые хэши файлов: при любом изменении файл, изобретите новый случайный «хэш», чтобы сделать его недействительным (и попытайтесь сохранить поддельные хэши при перемещениях). Все еще вычисляйте реальные хэши вверх по дереву. Теперь у вас могут быть ложные срабатывания — вы «обнаружите изменение», когда содержимое такое же, — но никогда ложноотрицательные.

В любом случае, суть в том, что какие бы хаки с отслеживанием состояния вы ни делали (например, inotify с периодическим сканированием, чтобы быть уверенным), вы делаете их только локально на сервере. По сети вы отправляете только хэши, представляющие моментальные снимки текущего состояния (или его поддеревьев)! Таким образом, вы можете иметь распределенную систему с множеством серверов и клиентов, прерывистым подключением и при этом оставаться в здравом уме.

P.S. Btrfs может эффективно находить отличия от старый снимок. Но это моментальный снимок, сделанный на сервере (и обеспечивающий сохранение всех данных!), менее гибкий, чем облегченное дерево хэшей на стороне клиента.

P.S. Один из ваших тегов — HadoopFS. Я не совсем знаком с ним, но я подозреваю, что многие его файлы являются неизменяемыми с однократной записью, и он может изначально дать вам какие-то идентификаторы файлов/фрагментов, которые могут служить поддельными хэшами?

Существующие инструменты

• Первый инструмент, который приходит мне на ум, это bup index. bup — очень умный инструмент для дедупликации резервного копирования, созданный на git (масштабируется только для больших объемов данных), поэтому он находится на фундамент, описанный выше. Теоретически, индексация данных в bup на сервере и выполнение git fetch по сети даже реализовали бы сравнение хеш-прохождения того, что нового я описал выше — к сожалению, репозитории git, которые создает bup, слишком велики, чтобы сам git мог с ними справиться. Также вы, вероятно, не хотите, чтобы bup считывал и сохранял все ваши данные. Но bup index – это отдельная подсистема, которая быстро сканирует файловую систему на наличие потенциальных изменений, еще не считывая измененные файлы.
  В настоящее время bup не использует inotify, но это было подробно обсуждается.

  О, и bup использует фильтры Блума, которые являются почти оптимальным способом представления наборов с ложными срабатываниями. Я почти уверен, что фильтры Блума играют определенную роль в оптимизации протоколов уведомлений без сохранения состояния («вот сжатое растровое изображение всего, что у меня есть; с его помощью вы сможете сузить свои запросы» или «вот сжатое растровое изображение того, что я хотите получать уведомления»). Не уверен, что способ их использования bup полезен для вас, но эта структура данных обязательно должна быть в вашем наборе инструментов.

• Еще одним инструментом является приложение git. Он также основан на Git (вы заметили тенденцию?), но предназначен для хранения самих данных вне репозиториев Git (так что git fetch должен просто работать!) и имеет "WORM", который использует поддельные хэши для повышения производительности.

Альтернативный дизайн: сжатый воспроизводимый журнал

Раньше я думал, что это единственный разумный подход без сохранения состояния для клиентов, чтобы проверить, что изменилось. Но я только что прочитал http://arstechnica.com/apple/2007/10/mac-os-x-10-5/7/ о платформе OS X FSEvents, которая, возможно, имеет более простой дизайн:

• ВСЕ изменения регистрируются в файле. Он хранится навсегда.
• Клиенты могут попросить «повторить для меня все, начиная с события 51348».
• Волшебный трюк заключается в том, что журнал имеет грубую степень детализации («что-то в этом каталоге изменилось, просканируйте его еще раз, чтобы узнать, что именно», повторяющиеся изменения в течение 30 секунд объединяются), поэтому этот файл журнала очень компактен.

На низком уровне вы можете прибегнуть к аналогичным методам — например, хэши — но интерфейс верхнего уровня другой: вместо снимков вы имеете дело с хронологией событий. Это может быть проще для некоторых приложений.