Что такое разумная структура данных для обеспечения эффективной синхронизации между двумя корневыми путями? - PullRequest
Новая
       29

Что такое разумная структура данных для обеспечения эффективной синхронизации между двумя корневыми путями?

1 голос
/ 01 июля 2011

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

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

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

Каждый процесс будет иметь доступ (и поддерживать)) постоянная структура данных всех файлов / папок по указанному пути.Я думал, что в структуре данных должно быть следующее для каждого из файлов и папок:

  • Имя файла / папки;
  • Хэш файла (CRC32);
  • Данные последнего мода файла / папки;и
  • Размер файла / папки.

Эти фрагменты информации, очевидно, помогут проверить наличие каких-либо изменений в файлах / папках, но как лучше их хранить?

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

  • файл изменен (имя файла найдено в структуре данных, но хэш отличается);
  • добавлен файл (в структуре данных не найдено идентичного имени файла или хэша);
  • файл переименован (файл с таким же хешем существует в структуре данных, но не с тем же именем файла); * добавлена ​​папка
  • (без имени папки в структуре данных);
  • папка удалена (имя папки в структуре данных, но не в пути);
  • папка переименована ( хитрый один ).

Итак, какие данные лучше?-структура использовать для этой задачи?У меня в голове возникает какая-то форма отсортированного ассоциативного массива, например, красно-черное дерево, в котором хранятся объекты file и folder.Каждый объект file содержит атрибуты name, hash и mod-date, в то время как каждый объект folder содержит атрибуты name и children, где children хранит другой ассоциативный массив со всем, что внизу.Задавая путь к произвольному файлу, например, /foo/bar/file.txt, вы начинаете с корня (foo), проверяете наличие bar и так далее, пока не доберетесь до родительского объекта file.txt.

Еще одна альтернатива, о которой я могу подумать, - это просто хранить все однозначно , так что есть одно красно-черное дерево, где каждый ключ - полный путь к каждому файлу / папке, а значение - file/ folder объект.Это, вероятно, будет быстрее для извлечения, но будет невозможно обнаружить переименованные файлы / папки без перебора всех значений в любом случае, что звучит дорого.При первом подходе может быть так, что идентификация переименования будет включать в себя проверку только части структуры данных, а не всей.

Извините, но вышеприведенные идеи не очень хорошо продуманы.Каково состояние дел в этой области, и есть ли какие-либо хорошо продуманные подходы к этим типам проблем?

1 Ответ

0 голосов
/ 01 июля 2011

Вы моделируете файловую систему, поэтому вполне естественно использовать иерархическую структуру данных. В конце концов, вам не нужно сравнивать файл в dir1 \ dir2 \ foo.txt с dir3 \ bar.txt, верно? Вы не упоминали перемещения файлов между каталогами как то, что вы отслеживаете.

Итак, структура данных может быть: 

interface IFSEntry {
  string name
  datetime creationDate
  pure virtual bool Compare(IFSEntry other)
  pure virtual void UpdateFrom(IFSEntry other)
  pure virtual bool WasRenamed(Dictionary<string,IFSEntry> possibleOriginals, out string oldName)
  ...
} 

class File : IFSEntry {
  ...
} 

class Directory : IFSEntry {
  private Dictionary<string,IFSEntry> children;
  ...
}

Реализации Справочника UpdateFrom и Compare будут возвращать своих детей.

Переименование файлов будет сравнительно простым, если сравнивать CRC. Вы пропустите файлы, которые изменились в обоих местах и ​​были переименованы. Вы можете добавить словарь CRC в класс Directory, если время выполнения сравнений доказывает проблему производительности.

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

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

...