In any company where one or more key products are under constant, active development by multiple disparate teams, there is a real risk that sooner or later the code-base will diverge and it will become impossible to ever bring it back together. This problem inevitably leads to one or more of the branches being abandoned in favour of another.

Under normal development, features on a product are developed by a single team working in a fairly linear fashion.

divergence_1

Within this model, a new feature of the product is scoped, requirements put forward, then the main development branch is forked into a feature branch, the feature built against this branch and once complete, the feature branch is merged back into the development and the cycle is repeated until such a time as enough features have been completed to constitute a release candidate.

As more developers come on board, the complexity of this model rises, with multiple parallel features being started and managed in tandem.

Whilst complex, this model is still manageable as long as development of multiple features remains within a single team or the team is split across multiple modules.

divergence_2

When multiple branches are running concurrently on the same module, feature merging into development can be managed fairly easily by keeping the features short and merging regularly. This fits in with the industry standard development model whereby a feature is described as a small, atomic, non-breaking change.

Before a feature is merged into the development branch, the merge is first carried out in reverse as a rebase against development. This rebase maintains the timeline of commits within the log and ensures that the feature is up to date with the latest development changes.

When features are relatively short lived, the model works quite well and in general, few conflicts arise when branches are merged.

It’s probably going to conflict.

As more concurrent branches fork off, the probability of conflict rises in line with the number of branches created, files modified within those branches and the length of time maintained between rebases.

Given a generic repo of 10 files whereby only a single developer modifies one or more of these files as part of a single branch, the probability of conflict is zero, whilst if two or more developers modify one or more of these files as part of the same branch, the probability of conflict rises in line with the number of overlapping files each developer changes. If both developers modify 7 of the 10 files with 2 of the files overlapping, the probability of conflict is 20%. As the number of lines changed within these two files rises towards the 50% mark, the probability of conflict rises to 100%.

This problem is understood as Bayes’ Theorum [Wikipedia (2003), https://en.wikipedia.org/wiki/Bayes’_theorem] which in its simplest form is described as:

image005

Time is also a contributor to the problem. The longer a branch exists, the higher the probability of conflict arising within a merge due to changes carried out as part of the main development cycle.

divergence_3

The governing factor here is the accelerator effect which follows the equation image009 and demonstrates how the likelihood of an event occurring is impacted by the number of current changes over time.

The accelerator effect is an economical predictor of the effect of fixed investment on market growth. When applied to branching, it predicts how rapidly branches diverge based on the amount of effort invested in both branches.

There is no solution to conflicts arising on long lived branches without regular merges of the main development branch. Even with this model, long lived branches can stagnate, development may be halted whilst a new product is designed, bugs are fixed or existing features re-worked to meet new demand. Once development starts again, the feature branch will be so far out of date that the probability of irreversible conflict will have reached critical mass and the effort to bring the two branches back together would far outweigh the cost of re-development.

Atomic Branches

The solution to long lived branches is to follow the model of Atomic branches.

An atomic branch contains a change which can be started and completed within time image011 where l is the length of time for two branches to diverge beyond the point where it becomes too costly to merge them back together.

When dealing within change, the calculation of l is critical to the understanding of how long a branch can survive before it has to be merged from, or to its parent.

For the sake of argument, let’s assume that the repo given above has 2000 lines of code (10 files, 200 lines per file). If the branch starts at time t1, finishes at time t2 and contains 30 changes, then velocity of change is given as image013.

If we define the parent branch as a, and the feature branch as b then the distance these branches are apart is given as image015, that is to say distance is the sum of unique changes to branch a plus the sum of unique changes to branch b.

divergence-diff-branch-bIf branch a remains unchanged then a merge is always possible even if 100% of the codebase changes, with the reason for this lying in the understanding that whilst branch b has diverged from branch a, branch a has not diverged from branch b. In the diagram above, this equates to 11.9% of the code having being changed.

This possibility changes as soon as a commit is made to the branch a, and is not merged to branch b.

In the following diagram, a number of changes have been made to both branch a and branch b. The divergence point is highlighted in amber and as you can see, both branches are now on different tracks.

divergence-differences

At time t2, branch a contains 438 changes whilst branch b contains 238 changes, giving a total distance of 676, equating to just over 1/3 of the codebase having been changed.

The complexity of merging these two branches can then be calculated on the intersection of both branches wherebyimage021 with the sum of changes contained in the intersection of both branches becoming n in big-o notation O(n).

Once we understand the complexity of merging, the decisive factor of which branch to maintain moves back from complexity of merging to cost of merging. For example if it took 6 developers 10 days to develop both branches and the cost of merging is 1 developer x 1 day then it may prove efficient to merge if the benefit of saving both branches outweighs the cost of losing a day of productivity for that single developer. If, however it had taken 2 developers 10 days to develop both branches and would cost a further 5 days development to merge the changes, it may prove too expensive to continue development and one branch would need to be abandoned.

There is an expense involved in maintaining any branch beyond a certain point without regular updates being pulled in from its’ parent.

In the above example, the cost of merging the two branches is greatly reduced if branch a is regularly merged into branch b as the distance between the two is kept to a minimum.

As shown in the figure below, this reduces the number of changes between the two branches to 73 at time t2 which is equivalent to 3.6% of the 2000 lines in the repository.

divergence-differences-merge

Whilst this example has been contrite in that it only focuses on lines changing and not being added or deleted as happens under the normal development cycle, the reality is complexity regularly fluxes as the number of lines changes, and a constant calculation needs to be carried out to ensure that a long lived branch is continually maintainable.

The economics of branching are such that it proves more efficient to maintain continuous short lived branches than to try and maintain even a single branch for more than a few days with the implication being that numerous long lived branches costing a business more in maintaining them than it makes from the sale of the original product.

If branches are surviving beyond this length, then it can point to problems elsewhere within the development cycle. Stories and features may be too big and need to be broken down; requirements may be incomplete or constantly changing or it could be that you are attempting to re-factor the code as part of a separate branch.

Whatever the reason you come up with, it’s wrong.

If your requirements are not fixed then you’re not ready for development. If your stories are too big, break them down into bite-size pieces and if you’re trying to re-factor the code, you are definitely going about it in a manner which would most likely create a larger mess of spaghetti than you had before.

As a general rule of thumb, if your branch is surviving longer than 3 or 4 days or you have to merge branch a more than once, your branch is no longer atomic and the cost of continuing development is likely to become more than the cost of abandoning the branch and starting again.

There are few key points to remember when it comes to branching.

  1. The Principle of Single responsibility. If a branch contains changes for multiple factors, each separate factor belongs on its’ own branch, ergo your branch is too big and should be broken down.
  2. The magic number 7. That people in general can only remember up to 7 ± 2 items at a time. Similarly to the previous point, if you have more changes than this, your branch is probably too big and needs to be broken down.
  3. YAGNI – You ain’t gonna need it. If your branch is too big it probably contains things it shouldn’t.
  4. KISS – Keep it Simple (Stupid) – Don’t add complexity for the sake of adding complexity, keep it simple.

Finally, if you’re developing a branch, remember that sooner or later someone is going to have to review it. Write it, test it, document it; but above all, don’t over-complicate it.

Leave a Comment