Какой алгоритм использует git для обнаружения изменений в вашем рабочем дереве?

Question

Это о внутренних органах git.

Я читал замечательную книгу 'Pro Git' и немного узнал о том, как Git работает внутри (все о SHA1, BLOB-объектах, ссылках, Tress, коммитах и ​​т. Д. И т. Д.). Кстати, довольно умная архитектура.

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

Наивный подход будет заключаться в том, что каждый раз, когда вы запускаете команду как git status или аналогичную команду, он просматривает все файлы в рабочем каталоге, вычисляет SHA1 и сравнивает его с тем, который имеет последний совершить. Но это кажется очень неэффективным для больших проектов, таких как ядро ​​Linux.

Другая идея может заключаться в проверке даты последнего изменения файла, но я думаю, что git не хранит эту информацию (когда вы клонируете репозиторий, у всех файлов новое время)

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

PD: Просто чтобы добавить интересную ссылку об индексе git, в частности, указав, что индекс хранит информацию о временных метках файлов, даже если объекты дерева этого не делают.

Answer 1

Индекс Git поддерживает временные метки, когда git последний раз записывал каждый файл в рабочее дерево (и обновляет их всякий раз, когда файлы кэшируются из рабочего дерева или из коммита).Вы можете увидеть метаданные с git ls-files --debug.В дополнение к метке времени, он записывает размер, индекс и другую информацию из lstat , чтобы уменьшить вероятность ложного срабатывания.

Когда вы выполняете git-status, он просто вызывает lstat для каждого файла в рабочем дереве и сравнивает метаданные, чтобы быстро определить, какие файлы не изменены.Это описано в документации под racy-git и update-index .

Answer 2

В файловой системе unix информация о файле отслеживается и может быть принята с помощью метода lstat . Структура stat содержит несколько отметок времени, информацию о размере и многое другое:

struct stat {
    dev_t     st_dev;     /* ID of device containing file */
    ino_t     st_ino;     /* inode number */
    mode_t    st_mode;    /* protection */
    nlink_t   st_nlink;   /* number of hard links */
    uid_t     st_uid;     /* user ID of owner */
    gid_t     st_gid;     /* group ID of owner */
    dev_t     st_rdev;    /* device ID (if special file) */
    off_t     st_size;    /* total size, in bytes */
    blksize_t st_blksize; /* blocksize for file system I/O */
    blkcnt_t  st_blocks;  /* number of 512B blocks allocated */
    time_t    st_atime;   /* time of last access */
    time_t    st_mtime;   /* time of last modification */
    time_t    st_ctime;   /* time of last status change */
};

Кажется, что изначально Git просто полагался на эту статистическую структуру , чтобы решить, был ли файл изменен ( см. Ссылку ):

При проверке, отличаются ли они, Git сначала запускает lstat(2) для файлов и сравнивает результат с этой информацией

Однако сообщалось о состоянии гонки ( racy-git ), которое обнаружилось, если файл был изменен следующим образом:

: modify 'foo'
$ git update-index 'foo'
: modify 'foo' again, in-place, without changing its size 
                      (And quickly enough to not change it's timestamps)

Это оставило файл в состоянии, которое было изменено, но не обнаружено lstat.

Чтобы исправить эту проблему, теперь в таких ситуациях, когда состояние lstat неоднозначно, Git сравнивает содержимое файлов, чтобы определить, было ли оно изменено.

---

Примечание:

Если кто-то запутался, как я, по поводу st_mtime description , в котором говорится, что оно обновляется записью «больше нуля байтов», это означает absolute изменить.

Например, в случае файла текстового файла с одним символом A: если A изменяется на B, то общий размер байта изменяется на 0, но st_mtime все равно будет обновляться ( пришлось проверить это самому, чтобы проверить, используйте ls -l, чтобы увидеть метку времени).