How does Git calculate commits to fetch

user_10662240 0
Viewed 51

I know what git fetch does and how this command is used.

I am interested in the internals: how does Git determine the exact commits to transmit?

For example for the situation below

local repo:

A - B - C - D master
     \  \- E - F feature1
      \- G feature2

origin:

A - B - C - D - D1 - D2 master
     \  \- E - F - F1 - F2 feature1
      \- G - G1 feature2

git fetch would need to download commits D1, D2, F1, F2, and G1.

Naively, my git client could send a list of local commit SHAs (A, B, C, D, E, F, G) to the remote repository. The remote repository would find all its SHAs not on my list (D1, D2, F1, F2, G1) and send them back to me. For big repositories this would involve sending lots of data and doing a lot of computation. The data to send to remote repo would be proportional to the total number of commits.

I am sure a more clever approach is used.

Is sending just the SHAs of tip of each branch (D, F, G) sufficient? Tracking the parents the remote repo can determine the commits both repos share and determine just the missing ones. The data to send to remote repo would be proportional to the total number of (unmerged) branches, which normally is much much lower than the number of commits.

Does it work in all cases (branches behind, ahead, rebased)?

Any other ideas? I am expecting a beautiful solution based on graph theory :-)

git-fetch git
1 Answers

Is sending just the SHAs of tip of each branch (D, F, G) sufficient?

Often, yes, but not always. In this case, it works perfectly: the receiving Git can announce that it has those three hash IDs, and since the sending Git has those commits, the sending Git can infer from this that, as long as the receiving Git is not a shallow repository, the receiving Git has those commits and all predecessors.

The clues to the "not always" are in the statement above: if the receiving Git is a shallow clone, it may lack some ancestors here. If the branch-tip-commits in the receiving Git are for commits that don't exist in the sender, their hash IDs convey no information to the sender.

For these cases, we fall back on "have" and "want". The sender sends his ref-names and hash IDs to the receiver. The receiver can tell if he has those objects. If not, and the receiver wants them, he signals that he "want"s them. The sender will need to offer additional hash IDs, for the parents of those commits; the receiver will indicate whether he has them, or not. In all cases, having some commit hash ID indicates that one has all ancestors, except for the shallow-repository case (these make a right mess of the obvious optimization, and I have not gone that deep into the Git source to see if there are more special cases for shallow clones—the graft points are known in the receiver, but I see nothing in the protocol description that would allow announcing them).

user_12564520
Related