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

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

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

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

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

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

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

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

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

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

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

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


fingerprint synchronization filesystems data-structures red-black-tree
person Edwardr    schedule 30.06.2011    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Вы моделируете файловую систему, поэтому вполне естественно использовать иерархическую структуру данных. В конце концов, вам не нужно сравнивать файл 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, если время выполнения сравнений окажется проблемой для производительности.

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

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

person David Gladfelter    schedule 30.06.2011
comment
Извините, что я так долго помечал этот ответ. Я использовал ваш подход, и он работает достаточно хорошо с точки зрения производительности, используя красно-черные деревья и словарь для CRC. Спасибо. - person Edwardr; 17.07.2011