Re: [PATCHv4 08/12] Teach the notes lookup code to parse notes trees with various fanout schemes

On Thursday 27 August 2009, Junio C Hamano wrote:

As you may remember, the major, remaining problem with the jh/notes patch series was that as the number of notes in a repo grew, the runtime cost of displaying (even a single one of) them became prohibitive. This was the major reason why Dscho and me did NOT want you to merge this series earlier. The solution to this performance problem (which has been discussed since almost a year ago), is to use some fanout scheme in the notes tree, so that we can load individual notes without necessarily parsing the entire notes tree. This patch implements the _reading_ of a notes trees with fanout.

However, as you correctly identify, allowing fanout makes it possible to add multiple notes for the same commit in the same notes tree.

Therefore, we must now create the order/discipline/guideline you request by taking away this extra freedom.

This will take the form of enforcing a chosen fanout scheme when _writing_ notes. This code (yet to be written) will include:

- refactoring the notes tree when the number of notes call for a different 
fanout scheme (e.g. create a 2/38 fanout scheme when the number of notes in 
a (sub)tree exceed some threshold).

- adding and editing notes while following the current fanout scheme.

- adding a custom merge strategy for note trees, which reads notes trees 

Currently I have a two different ideas on a suitable fanout scheme:

1. Define a threshold where the number of notes in a (sub)tree becomes large 
enough warrant a fanout. For now, let's assume that threshold is 1024. Start 
with en empty notes tree with no fanout. When we reach 1024 notes, split the 
notes tree into 256 subdirs (2/38 fanout). As each of the subdirs reach 1024 
notes, split those subdirs further (2/2/36 fanout), and so on. In practice 
(since SHA1 gives us a uniform distribution), notes trees with up to:
- < 1024 notes will have no fanout
- < ~256K notes will have 2/38 fanout
- < ~64M notes will have 2/2/36 fanout
- < ~16G notes will have 2/2/2/34 fanout

2. Simply decide on a constant 2/2/36 fanout. For the case with < 256K 
notes, this is somewhat wasteful, but not prohibitively expensive. For the 
case with > 64M notes, performance will start to degrade. The big advantage 
with this approach is that when this is hardcoded into the notes code, we 
have regained the property that notes for a given commit have exactly _one_ 
unique position in the notes tree across all installations (enabling us to 
fall back on the regular merge strategy).

The end user should not know or care about what fanout scheme is used. Everything should be handled seamlessly by the code.

Nope, the code should decide which fanout scheme to use.

No. Again this should be invisible to the user.

The notes code should prevent notes that violate the fanout scheme from being created.

The fanout scheme is not something the user should have to worry about at all.

I totally understand that you don't want to merge the notes feature before the "writing" side is taken care of. As such, this iteration is simply yet another iteration towards that final goal.

...Johan