Git designed for AI agents.
package housekeeping
import (
"context"
"fmt"
"math"
"time"
"github.com/feder-cr/git-ai/internal/git"
"github.com/feder-cr/git-ai/internal/git/housekeeping/config"
"github.com/feder-cr/git-ai/internal/git/stats"
)
const (
// FullRepackCooldownPeriod is the cooldown period that needs to pass since the last full
// repack before we consider doing another full repack.
FullRepackCooldownPeriod = 5 * 24 * time.Hour
)
// OptimizationStrategy is an interface to determine which parts of a repository should be
// optimized.
type OptimizationStrategy interface {
// ShouldRepackObjects determines whether the repository needs to be repacked and, if so,
// how it should be done.
ShouldRepackObjects(context.Context) (bool, config.RepackObjectsConfig)
// ShouldPruneObjects determines whether the repository has stale objects that should be
// pruned and, if so, how it should be done.
ShouldPruneObjects(context.Context) (bool, PruneObjectsConfig)
// ShouldRepackReferences determines whether the repository's references need to be
// repacked.
ShouldRepackReferences(context.Context) bool
// ShouldWriteCommitGraph determines whether we need to write the commit-graph and how it
// should be written.
ShouldWriteCommitGraph(context.Context) (bool, config.WriteCommitGraphConfig, error)
}
// HeuristicalOptimizationStrategy is an optimization strategy that is based on a set of
// heuristics.
type HeuristicalOptimizationStrategy struct {
info stats.RepositoryInfo
expireBefore time.Time
}
// NewHeuristicalOptimizationStrategy constructs a heuristicalOptimizationStrategy for the given
// repository info. It derives all data from the repository so that the heuristics used by this
// repository can be decided without further disk reads.
func NewHeuristicalOptimizationStrategy(info stats.RepositoryInfo) HeuristicalOptimizationStrategy {
return HeuristicalOptimizationStrategy{
info: info,
expireBefore: time.Now().Add(stats.StaleObjectsGracePeriod),
}
}
// ShouldRepackObjects checks whether the repository's objects need to be repacked. This uses a
// set of heuristics that scales with the size of the object database: the larger the repository,
// the less frequent does it get a full repack.
func (s HeuristicalOptimizationStrategy) ShouldRepackObjects(ctx context.Context) (bool, config.RepackObjectsConfig) {
// If there are neither packfiles nor loose objects in this repository then there is no need
// to repack anything.
if s.info.Packfiles.Count == 0 && s.info.LooseObjects.Count == 0 {
return false, config.RepackObjectsConfig{}
}
nonCruftPackfilesCount := s.info.Packfiles.Count - s.info.Packfiles.CruftCount
timeSinceLastFullRepack := time.Since(s.info.Packfiles.LastFullRepack)
fullRepackCfg := config.RepackObjectsConfig{
// We use the full-with-unreachable strategy to also pack all unreachable
// objects into the packfile. This only happens for object pools though,
// as they should never delete objects.
Strategy: config.RepackObjectsStrategyFullWithUnreachable,
// We cannot write bitmaps when there are alternates as we don't have full
// closure of all objects in the packfile.
WriteBitmap: len(s.info.Alternates.ObjectDirectories) == 0,
// We rewrite all packfiles into a single one and thus change the layout
// that was indexed by the multi-pack-index. We thus need to update it, as
// well.
WriteMultiPackIndex: true,
}
if !s.info.IsObjectPool {
// When we don't have an object pool at hand we want to be able to expire
// unreachable objects. We thus use cruft packs with an expiry date.
fullRepackCfg.Strategy = config.RepackObjectsStrategyFullWithCruft
fullRepackCfg.CruftExpireBefore = s.expireBefore
}
geometricRepackCfg := config.RepackObjectsConfig{
Strategy: config.RepackObjectsStrategyGeometric,
// We cannot write bitmaps when there are alternates as we don't have full
// closure of all objects in the packfile.
WriteBitmap: len(s.info.Alternates.ObjectDirectories) == 0,
// We're rewriting packfiles that may be part of the multi-pack-index, so we
// do want to update it to reflect the new layout.
WriteMultiPackIndex: true,
}
// Incremental repacks only pack unreachable objects into a new pack. As we only
// perform this kind of repack in the case where the overall repository structure
// looks good to us we try to do use the least amount of resources to update them.
// We thus neither update the multi-pack-index nor do we update bitmaps.
incrementalRepackCfg := config.RepackObjectsConfig{
Strategy: config.RepackObjectsStrategyIncrementalWithUnreachable,
WriteBitmap: false,
WriteMultiPackIndex: false,
}
// When alternative object directories have been modified since our last full repack
// then we have likely joined an object pool since then. This means that we'll want
// to perform a full repack in order to deduplicate objects that are part of the
// object pool.
if s.info.Alternates.LastModified.After(s.info.Packfiles.LastFullRepack) {
return true, fullRepackCfg
}
// It is mandatory for us that we perform regular full repacks in repositories so
// that we can evict objects which are unreachable into a separate cruft pack. So in
// the case where we have more than one non-cruft packfiles and the time since our
// last full repack is longer than the grace period we'll perform a full repack.
//
// This heuristic is simple on purpose: customers care about when objects will be
// declared as unreachable and when the pruning grace period starts as it impacts
// usage quotas. So with this simple policy we can tell customers that we evict and
// expire unreachable objects on a regular schedule.
//
// On the other hand, for object pools, we also need to perform regular full
// repacks. The reason is different though, as we don't ever delete objects from
// pool repositories anyway.
//
// Geometric repacking does not take delta islands into account as it does not
// perform a graph walk. We need proper delta islands though so that packfiles can
// be efficiently served across forks of a repository.
//
// Once a full repack has been performed, the deltas will be carried forward even
// across geometric repacks. That being said, the quality of our delta islands will
// regress over time as new objects are pulled into the pool repository.
//
// So we perform regular full repacks in the repository to ensure that the delta
// islands will be "freshened" again. If geometric repacks ever learn to take delta
// islands into account we can get rid of this condition and only do geometric
// repacks.
if nonCruftPackfilesCount > 1 && timeSinceLastFullRepack > FullRepackCooldownPeriod {
return true, fullRepackCfg
}
// In case both packfiles and loose objects are in a good state, but we don't yet
// have a multi-pack-index we perform an incremental repack to generate one. We need
// to have multi-pack-indices for the next heuristic, so it's bad if it was missing.
if !s.info.Packfiles.MultiPackIndex.Exists {
return true, geometricRepackCfg
}
// Last but not least, we also need to take into account whether new packfiles have
// been written into the repository since our last geometric repack. This is
// necessary so that we can enforce the geometric sequence of packfiles and to make
// sure that the multi-pack-index tracks those new packfiles.
//
// To calculate this we use the number of packfiles tracked by the multi-pack index:
// the difference between the total number of packfiles and the number of packfiles
// tracked by the index is the amount of packfiles written since the last geometric
// repack. As we only update the MIDX during housekeeping this metric should in
// theory be accurate.
//
// Theoretically, we could perform a geometric repack whenever there is at least one
// untracked packfile as git-repack(1) would exit early in case it finds that the
// geometric sequence is kept. But there are multiple reasons why we want to avoid
// this:
//
// - We would end up spawning git-repack(1) on almost every single repository
// optimization, but ideally we want to be lazy and do only as much work as is
// really required.
//
// - While we wouldn't need to repack objects in case the geometric sequence is kept
// anyway, we'd still need to update the multi-pack-index. This action scales with
// the number of overall objects in the repository.
//
// Instead, we use a strategy that heuristically determines whether the repository
// has too many untracked packfiles and scale the number with the combined size of
// all packfiles. The intent is to perform geometric repacks less often the larger
// the repository, also because larger repositories tend to be more active, too.
//
// The formula we use is:
//
// log(total_packfile_size) / log(1.8)
//
// Which gives us the following allowed number of untracked packfiles:
//
// -----------------------------------------------------
// | total packfile size | allowed untracked packfiles |
// -----------------------------------------------------
// | none or <10MB | 2 |
// | 10MB | 3 |
// | 100MB | 7 |
// | 500MB | 10 |
// | 1GB | 11 |
// | 5GB | 14 |
// | 10GB | 15 |
// | 100GB | 19 |
// -----------------------------------------------------
allowedLowerLimit := 2.0
allowedUpperLimit := math.Log(float64(s.info.Packfiles.Size/1024/1024)) / math.Log(1.8)
actualLimit := math.Max(allowedLowerLimit, allowedUpperLimit)
untrackedPackfiles := s.info.Packfiles.Count - s.info.Packfiles.MultiPackIndex.PackfileCount
if untrackedPackfiles > uint64(actualLimit) {
return true, geometricRepackCfg
}
// If there are loose objects then we want to roll them up into a new packfile.
// Loose objects naturally accumulate during day-to-day operations, e.g. when
// executing RPCs part of the OperationsService which write objects into the repo
// directly.
//
// As we have already verified that the packfile structure looks okay-ish to us, we
// don't need to perform a geometric repack here as that could be expensive: we
// might end up soaking up packfiles because the geometric sequence is not intact,
// but more importantly we would end up writing the multi-pack-index and potentially
// a bitmap. Writing these data structures introduces overhead that scales with the
// number of objects in the repository.
//
// So instead, we only do an incremental repack of all loose objects, regardless of
// their reachability. This is the cheapest we can do: we don't need to compute
// whether objects are reachable and we don't need to update any data structures
// that scale with the repository size.
if s.info.LooseObjects.Count > LooseObjectLimit {
return true, incrementalRepackCfg
}
return false, config.RepackObjectsConfig{}
}
// ShouldWriteCommitGraph determines whether we need to write the commit-graph and how it should be
// written.
func (s HeuristicalOptimizationStrategy) ShouldWriteCommitGraph(ctx context.Context) (bool, config.WriteCommitGraphConfig, error) {
switch s.info.References.ReferenceBackendName {
case git.ReferenceBackendReftables.Name, git.ReferenceBackendMVCC.Name:
// For reftables, we don't have a loose ref or packsize count. While we could check if
// 'tables.list' is empty or not. The reftable backend always populates it with HEAD,
// even for an empty repository. So fallback to creating the commit graph. This could
// be end up with an empty graph, but that's okay.
//
// The MVCC backend keeps its references in manifest artifacts that we don't
// enumerate either, so it gets the same treatment.
case git.ReferenceBackendFiles.Name:
// If the repository doesn't have any references at all then there is no point in writing
// commit-graphs given that it would only contain reachable objects, of which there are
// none.
if s.info.References.LooseReferencesCount == 0 && s.info.References.PackedReferencesSize == 0 {
return false, config.WriteCommitGraphConfig{}, nil
}
default:
return false, config.WriteCommitGraphConfig{}, fmt.Errorf("unexpected reference backend: %q", s.info.References.ReferenceBackendName)
}
// When we have pruned objects in the repository then it may happen that the commit-graph
// still refers to commits that have now been deleted. While this wouldn't typically cause
// any issues during runtime, it may cause errors when explicitly asking for any commit that
// does exist in the commit-graph, only. Furthermore, it causes git-fsck(1) to report that
// the commit-graph is inconsistent.
//
// To fix this case we will replace the complete commit-chain when we have pruned objects
// from the repository.
if shouldPrune, _ := s.ShouldPruneObjects(ctx); shouldPrune {
return true, config.WriteCommitGraphConfig{
ReplaceChain: true,
}, nil
}
if commitGraphNeedsRewrite(ctx, s.info.CommitGraph) {
return true, config.WriteCommitGraphConfig{
ReplaceChain: true,
}, nil
}
// When we repacked the repository then chances are high that we have accumulated quite some
// objects since the last time we wrote a commit-graph.
if needsRepacking, repackCfg := s.ShouldRepackObjects(ctx); needsRepacking {
return true, config.WriteCommitGraphConfig{
// Same as with pruning: if we are repacking the repository and write cruft
// packs with an expiry date then we may end up pruning objects. We thus
// need to replace the commit-graph chain in that case.
ReplaceChain: repackCfg.Strategy == config.RepackObjectsStrategyFullWithCruft && !repackCfg.CruftExpireBefore.IsZero(),
}, nil
}
return false, config.WriteCommitGraphConfig{}, nil
}
// ShouldPruneObjects determines whether the repository has stale objects that should be pruned.
// Object pools are never pruned to not lose data in them, but otherwise we prune when we've found
// enough stale objects that might in fact get pruned.
func (s HeuristicalOptimizationStrategy) ShouldPruneObjects(context.Context) (bool, PruneObjectsConfig) {
// Pool repositories must never prune any objects, or otherwise we may corrupt members of
// that pool if they still refer to that object.
if s.info.IsObjectPool {
return false, PruneObjectsConfig{}
}
// When we have a number of loose objects that is older than two weeks then they have
// surpassed the grace period and may thus be pruned.
if s.info.LooseObjects.StaleCount <= LooseObjectLimit {
return false, PruneObjectsConfig{}
}
return true, PruneObjectsConfig{
ExpireBefore: s.expireBefore,
}
}
// ShouldRepackReferences determines whether the repository's references need to be repacked based
// on heuristics. The more references there are, the more loose referencos may exist until they are
// packed again.
func (s HeuristicalOptimizationStrategy) ShouldRepackReferences(context.Context) bool {
// If there aren't any loose refs then there is nothing we need to do.
// For reftables, if there is a single reftable, then there is no auto-compaction
// needed.
if s.info.References.LooseReferencesCount == 0 && len(s.info.References.ReftableTables) <= 1 {
return false
}
// Reftables auto-compact their tables on the fly and don't generally rely
// on housekeeping or 'git-pack-refs(1)' to be run. In Gitaly, we override
// the auto-compaction capabilities because we want finer control and to
// also prevent conflicts between concurrent writes.
//
// This replicates the behavior in Git (reftable_stack_auto_compact from
// reftable/stack.c) to ensure that the tables follow a geometric progression.
if len(s.info.References.ReftableTables) > 1 {
// Git uses a different overhead based on the version of the reftable
// format. Let's just use the bigger value, this makes our calculations
// here slightly different from Git, but that is okay, since we would
// still maintain geometric progression.
var overhead uint64 = 28
tables := s.info.References.ReftableTables
for i := len(tables) - 1; i > 0; i-- {
sizePrev := tables[i-1].Size - overhead
sizeCur := tables[i].Size - overhead
if sizePrev < sizeCur*2 {
return true
}
}
return false
}
// Packing loose references into the packed-refs file scales with the number of references
// we're about to write. We thus decide whether we repack refs by weighing the current size
// of the packed-refs file against the number of loose references. This is done such that we
// do not repack too often on repositories with a huge number of references, where we can
// expect a lot of churn in the number of references.
//
// As a heuristic, we repack if the number of loose references in the repository exceeds
// `log(packed_refs_size_in_bytes/100)/log(1.15)`, which scales as following (number of refs
// is estimated with 100 bytes per reference):
//
// - 1kB ~ 10 packed refs: 16 refs
// - 10kB ~ 100 packed refs: 33 refs
// - 100kB ~ 1k packed refs: 49 refs
// - 1MB ~ 10k packed refs: 66 refs
// - 10MB ~ 100k packed refs: 82 refs
// - 100MB ~ 1m packed refs: 99 refs
//
// We thus allow roughly 16 additional loose refs per factor of ten of packed refs.
//
// This heuristic may likely need tweaking in the future, but should serve as a good first
// iteration.
if uint64(math.Max(16, math.Log(float64(s.info.References.PackedReferencesSize)/100)/math.Log(1.15))) > s.info.References.LooseReferencesCount {
return false
}
return true
}
// EagerOptimizationStrategy is a strategy that will eagerly perform optimizations. All of the data
// structures will be optimized regardless of whether they already are in an optimal state or not.
type EagerOptimizationStrategy struct {
info stats.RepositoryInfo
expireBefore time.Time
}
// NewEagerOptimizationStrategy creates a new EagerOptimizationStrategy.
func NewEagerOptimizationStrategy(info stats.RepositoryInfo) EagerOptimizationStrategy {
return EagerOptimizationStrategy{
info: info,
expireBefore: time.Now().Add(stats.StaleObjectsGracePeriod),
}
}
// ShouldRepackObjects always instructs the caller to repack objects. The strategy will always be to
// repack all objects into a single packfile and write a bitmap when there are no alternates. On
// MVCC repositories it requests geometric maintenance only.
func (s EagerOptimizationStrategy) ShouldRepackObjects(ctx context.Context) (bool, config.RepackObjectsConfig) {
// git-repack(1) cannot see packs outside the MVCC manifest, so the full repacks below die on
// MVCC repositories with exit 128. Use geometric maintenance instead, as the heuristical
// strategy does. No bitmap, multi-pack-index or cruft expiry may leak into the config.
if s.info.References.ReferenceBackendName == git.ReferenceBackendMVCC.Name {
return true, config.RepackObjectsConfig{
Strategy: config.RepackObjectsStrategyGeometric,
}
}
cfg := config.RepackObjectsConfig{
WriteBitmap: len(s.info.Alternates.ObjectDirectories) == 0,
WriteMultiPackIndex: true,
}
// Object pools should generally never contain unreachable objects. However, if an object
// pool does contain unreachable objects, they should never be deleted or we could end up
// corrupting object pool members that depend on them. To ensure this, we disable cruft
// packs and expiration times in this context.
//
// However, by disabling cruft packs Git would by default explode unreachable objects into
// loose objects. This is inefficient as these objects cannot be deltified and thus take up
// more space. Instead, we ask git-repack(1) to append unreachable objects to the newly
// created packfile.
if !s.info.IsObjectPool {
cfg.Strategy = config.RepackObjectsStrategyFullWithCruft
cfg.CruftExpireBefore = s.expireBefore
} else {
cfg.Strategy = config.RepackObjectsStrategyFullWithUnreachable
}
return true, cfg
}
// ShouldWriteCommitGraph always instructs the caller to write the commit-graph. The strategy will
// always be to completely rewrite the commit-graph chain.
func (s EagerOptimizationStrategy) ShouldWriteCommitGraph(context.Context) (bool, config.WriteCommitGraphConfig, error) {
return true, config.WriteCommitGraphConfig{
ReplaceChain: true,
}, nil
}
// ShouldPruneObjects always instructs the caller to prune objects, unless the repository is an
// object pool or on MVCC.
func (s EagerOptimizationStrategy) ShouldPruneObjects(context.Context) (bool, PruneObjectsConfig) {
if s.info.IsObjectPool {
return false, PruneObjectsConfig{}
}
// The MVCC backend keeps no loose objects, and git-prune(1) runs read-pinned so it could not
// publish anyway. Pruning would only log a prune that deleted nothing.
if s.info.References.ReferenceBackendName == git.ReferenceBackendMVCC.Name {
return false, PruneObjectsConfig{}
}
return true, PruneObjectsConfig{
ExpireBefore: s.expireBefore,
}
}
// ShouldRepackReferences always instructs the caller to repack references.
func (s EagerOptimizationStrategy) ShouldRepackReferences(context.Context) bool {
return true
}