Why parent is stored in git notes?

Question

The way git store notes:

• Git only store one note per commit for single namespace. One can have multiple namespace. Default namespace is commit.
• .git/refs/notes/ contain one hash (say, MainHash_2), which is a tree object. Whenever you create a note the hash get changed.
• This tree object contain two more hashes. One to another tree structure (the notes tree structure, say NOTES_2) and one to parent tree object(the one in the the .git/refs/notes/ before creating this note, say MainHash_1 )
• The notes tree structure contains one entry for each note. Each entry have two hash: one to note content and other to specified commit.

As mentioned in third point why the parent is stored? As this parent(its type is same what is mentioned in point two) also contain another tree which contain one entry per note.

Suppose currently you have three notes. MainHash_2 contains a hash to NOTES_2, which contain three entries for each note. MainHash_1 contains a hash to NOTES_1, which contain two entries(for all the remaining notes except the one created now). Why storing these two entries twice and so on??

Answer 1

Simply because notes namespaces are not something special in git, they are just ordinary branches with complete history. You can do

git checkout notes/commits

and work with your notes as with any other branch, e.g. you can do

git log notes/commits

to see commit log for your notes. This way you can track all the changes to your notes.

You said that:

.git/refs/notes/commits contains one hash (say, MainHash_2), which is a tree object.

It's not a tree object, it's a commit. Just like in .git/refs/heads/master. You can check it with git cat-file -t <hash>

Answer 2

git notes was introduced in in commit 73f77b9, Git v1.6.6-rc0.
The notion of fanout was introduced with Git v1.7.1-rc0 in Feb. 2010 with commit 73f77b9, to determine optimal on-disk fanout for this part of the notes tree, in .git/refs/notes/commits.

Values of the 'fanout' variable:

• 0: No fanout (all notes are stored directly in the root notes tree)
• 1: 2/38 fanout
• 2: 2/2/36 fanout
• 3: 2/2/2/34 fanout

With Git 2.25.2 (March 2020), The code to automatically shrink the fan-out in the notes tree had an off-by-one bug, which has been killed.

See commit dbc2747, commit e1c5253 (03 Feb 2020) by Johan Herland (jherland).
^{(Merged by Junio C Hamano -- gitster -- in commit 8833260, 14 Feb 2020)}

t3305: check notes fanout more carefully and robustly

In short, before this patch, this test script:

• creates many notes
• verifies that all notes in the notes tree has a fanout of 1
• removes most notes
• verifies that the notes in the notes tree now has a fanout of 0

The fanout verification only happened twice: after creating all the notes, and after removing most of them.

This patch strengthens the test by checking the fanout after _each_ added/removed note: We assert that the switch from fanout 0 -> 1 happens exactly once while adding notes (and that the switch pervades the entire notes tree). Likewise, we assert that the switch from fanout 1 -> 0 happens exactly once while removing notes.

Additionally, we decrease the number of notes left after removal, from 50 to 15 notes, in order to ensure that fanout 1 -> 0 transition keeps happening regardless of external factors (1).

(1): Currently (with the SHA1 hash function and the deterministic object ids of the test environment) the fanout heuristic in the notes code happens to switch from 0 -> 1 at 109 notes, and from 1 -> 0 at 59 notes.
However, changing the hash function or other external factors will vary these numbers, and the latter may - in theory - go as low as 15.
For more details, please see the discussion.

And:

notes.c: fix off-by-one error when decreasing notes fanout

As noted in the previous commit, the nature of the fanout heuristic in the notes code causes the exact point at which we increase or decrease the notes fanout to vary with the objects being annotated.
Since the object ids generated by the test environment are deterministic (by design), the notes generated and tested by t3305 are always the same, and we therefore happen to see the same fanout behavior from one run to the next.

Coincidentally, if we were to change the test environment slightly (say by making a test commit on an unrelated branch before we start the t3305 test proper), we not only see the fanout switch happen at different points, we also manage to trigger a bug in the notes code where the fanout 1 -> 0 switch is not applied uniformly across the notes tree, but instead yields a notes tree like this:

...
bdeafb301e44b0e4db0f738a2d2a7beefdb70b70
bff2d39b4f7122bd4c5caee3de353a774d1e632a
d3/8ec8f851adf470131178085bfbaab4b12ad2a7
e0b173960431a3e692ae929736df3c9b73a11d5b
eb3c3aede523d729990ac25c62a93eb47c21e2e3
...

The bug occurs when we are writing out a notes tree with a newly decreased fanout, and the notes tree contains unexpanded subtrees that should be consolidated into the parent tree as a consequence of the decreased fanout):

Subtrees that happen to sit at an even level in the internal notes 16-tree structure (in other words: subtrees whose path - "d3" in the example above - is unique in the first nibble - i.e. there are no other note paths that start with "d") are not unpacked as part of the tree writeout.
This error will repeat itself in subsequent note trees until the subtree is forced to be unpacked. In t3305 this only happens when the d38ec8f8 note is itself removed from the tree.

The error is not severe (no information is lost, and the notes code is able to read/decode this tree and manipulate it correctly), but this is nonetheless a bug in the current implementation that should be fixed.

That said, fixing the off-by-one error is not without complications:

We must take into account that the load_subtree() call from for_each_note_helper() (that is now done to correctly unpack the subtree while we're writing out the notes tree) may end up inserting unpacked non-notes into the linked list of non_note entries held by the struct notes_tree.
Since we are in the process of writing out the notes tree, this linked list is currently in the process of being traversed by write_each_non_note_until().
The unpacked non-notes are necessarily inserted between the last non-note we wrote out, and the next non-note to be written.
Hence, we cannot simply hold the next_non_note to write in struct write_each_note_data (as we would then silently skip these newly inserted notes), but must instead always follow the ->next pointer from the last non-note we wrote. (This part was caught by an existing test in t3304.)