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 t

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".