News for hackers. Stuff that matters.
Re:Scaling monorepo maintenance by infogulch on Saturday May 01, 2021 @01:33PM (#27008093)
This was great! My summary:

A git packfile is an aggregated and indexed collection of historical git objects which reduce the time it takes to serve requests to those objects, implemented as two files: .pack and .idx. GitHub was having issues maintaining packfiles for very large repos in particular because regular repacking always has to repack the entire history into a single new packfile every time -- which is an expensive quadratic algorithm. GitHub's engineering team ameliorated this problem in two steps: 1. Enable repos to be served from multiple packfiles at once, 2. Design a packfile maintenance strategy that uses multiple packfiles sustainably.

Multi-pack indexes are a new git feature, but the initial implementation was missing performance-critial reachability bitmaps for multi-pack indexes. In general, index files store object names in lexicographic order and point to the named object's position in the associated packfile. As a first step to implement reachability bitmaps for multi-pack indexes, they introduced a reverse index file (.rev) which maps packfile object positions back to index file name offsets. This alone had a big performance improvement, but it also filled in the missing piece in order to implement multi-pack bitmaps.

With the issues of serving repos from multiple packs solved, they need to efficiently utilize multiple packs to reduce maintenance overhead. They chose to maintain historical packfiles in a geometrically increasing size. I.e., during the maintenance job, consider the first N most recent packfiles, if the sum of the size of all packfiles from [1, N] is less than the size of packfile N+1, then packfiles [1, N] are repacked into a single packfile, done; however if their summed size is greater than the size of packfile N+1, then iterate and consider all the packfiles [1, N+1] compared to packfile N+2 etc. This results in a set of packfiles where each file is roughly double the size of the previous when ordered by age, which has a number of beneficial properties for both serving and the average case maintenance run. Funny enough, this selection procedure struck me as similar to the game "2048".

There are no comments on this comment yet.