Repository: chainguard-dev/apko
Pull request #1617 (2025-04-10 23:42:39)

Implement generic layering
This uses a "simple" strategy of merging origins and replaces, then
taking the largest $budget groups of packages, merging the remainder.

This should not have any effect on apko configs that don't opt into
layering via the "layering" field, which is marked experimental:

```yaml
layering:
    strategy: "origin"
    budget: 10
```

This will split packages into up to 10 different layers (+1 for
everything that doesn't belong to a package).



Patch:
diff --git a/pkg/apk/apk/implementation.go b/pkg/apk/apk/implementation.go
index 1e6859a..35e4679 100644
--- a/pkg/apk/apk/implementation.go
+++ b/pkg/apk/apk/implementation.go
@@ -581,7 +581,7 @@ func (a *APK) ResolveAndCalculateWorld(ctx context.Context) ([]*APKResolved, err
 }
 
 // FixateWorld force apk's resolver to re-resolve the requested dependencies in /etc/apk/world.
-func (a *APK) FixateWorld(ctx context.Context, sourceDateEpoch *time.Time) error {
+func (a *APK) FixateWorld(ctx context.Context, sourceDateEpoch *time.Time) ([]*Package, error) {
 	log := clog.FromContext(ctx)
 	/*
 		equivalent of: "apk fix --arch arch --root root"
@@ -598,7 +598,7 @@ func (a *APK) FixateWorld(ctx context.Context, sourceDateEpoch *time.Time) error
 	// 1. Get the apkIndexes for each repository for the target arch
 	allpkgs, conflicts, err := a.ResolveWorld(ctx)
 	if err != nil {
-		return fmt.Errorf("error getting package dependencies: %w", err)
+		return nil, fmt.Errorf("error getting package dependencies: %w", err)
 	}
 
 	// 3. For each name on the list:
@@ -611,10 +611,10 @@ func (a *APK) FixateWorld(ctx context.Context, sourceDateEpoch *time.Time) error
 	for _, pkg := range conflicts {
 		isInstalled, err := a.isInstalledPackage(pkg)
 		if err != nil {
-			return fmt.Errorf("error checking if package %s is installed: %w", pkg, err)
+			return nil, fmt.Errorf("error checking if package %s is installed: %w", pkg, err)
 		}
 		if isInstalled {
-			return fmt.Errorf("cannot install due to conflict with %s", pkg)
+			return nil, fmt.Errorf("cannot install due to conflict with %s", pkg)
 		}
 	}
 	// Cast []*RepositoryPackage into []InstallablePackage.
@@ -626,7 +626,7 @@ func (a *APK) FixateWorld(ctx context.Context, sourceDateEpoch *time.Time) error
 	return a.InstallPackages(ctx, sourceDateEpoch, allInstPkgs)
 }
 
-func (a *APK) InstallPackages(ctx context.Context, sourceDateEpoch *time.Time, allpkgs []InstallablePackage) error {
+func (a *APK) InstallPackages(ctx context.Context, sourceDateEpoch *time.Time, allpkgs []InstallablePackage) ([]*Package, error) {
 	// TODO: Consider making this configurable option.
 	jobs := runtime.GOMAXPROCS(0)
 
@@ -710,7 +710,7 @@ func (a *APK) InstallPackages(ctx context.Context, sourceDateEpoch *time.Time, a
 	}
 
 	if err := g.Wait(); err != nil {
-		return fmt.Errorf("installing packages: %w", withCause(ctx, err))
+		return nil, fmt.Errorf("installing packages: %w", withCause(ctx, err))
 	}
 
 	// update the installed file
@@ -737,11 +737,11 @@ func (a *APK) InstallPackages(ctx context.Context, sourceDateEpoch *time.Time, a
 		})
 
 		if err := a.AddInstalledPackage(pkg, files); err != nil {
-			return fmt.Errorf("unable to update installed file for pkg %s: %w", pkg.Name, err)
+			return nil, fmt.Errorf("unable to update installed file for pkg %s: %w", pkg.Name, err)
 		}
 	}
 
-	return nil
+	return infos, nil
 }
 
 type NoKeysFoundError struct {
diff --git a/pkg/apk/apk/repo.go b/pkg/apk/apk/repo.go
index b46679f..bad47e6 100644
--- a/pkg/apk/apk/repo.go
+++ b/pkg/apk/apk/repo.go
@@ -34,7 +34,7 @@ import (
 
 var (
 	parsedVersions    sync.Map // map[string]Version
-	parsedConstraints sync.Map // map[string]parsedConstraint
+	parsedConstraints sync.Map // map[string]ParsedConstraint
 )
 
 // NamedIndex an index that contains all of its packages,
@@ -268,7 +268,7 @@ func newPkgResolver(ctx context.Context, indexes []NamedIndex) *PkgResolver {
 	for _, pkgVersions := range allPkgs {
 		for _, pkg := range pkgVersions {
 			for _, provide := range pkg.Provides {
-				name := cachedResolvePackageNameVersionPin(provide).name
+				name := cachedResolvePackageNameVersionPin(provide).Name
 				pkgNameMap[name] = append(pkgNameMap[name], pkg)
 			}
 		}
@@ -311,7 +311,7 @@ func (p *PkgResolver) nextPackage(packages []string, dq map[*RepositoryPackage]s
 // Disqualify anything that provides "constraint". This is used for !foo style constraints.
 func (p *PkgResolver) disqualifyProviders(constraint string, dq map[*RepositoryPackage]string) {
 	parsed := cachedResolvePackageNameVersionPin(constraint)
-	providers, ok := p.nameMap[parsed.name]
+	providers, ok := p.nameMap[parsed.Name]
 	if !ok {
 		return
 	}
@@ -328,7 +328,7 @@ func (p *PkgResolver) disqualifyProviders(constraint string, dq map[*RepositoryP
 	}
 }
 
-func (p *PkgResolver) conflictingVersion(constraint parsedConstraint, conflict *repositoryPackage) bool {
+func (p *PkgResolver) conflictingVersion(constraint ParsedConstraint, conflict *repositoryPackage) bool {
 	// If the constraint is not a virtual, everything will conflict with it.
 	// TODO: Figure out if this logic is actually equivalent to how apk disqualifies virtual.
 	if constraint.version != "" {
@@ -337,13 +337,13 @@ func (p *PkgResolver) conflictingVersion(constraint parsedConstraint, conflict *
 
 	// From here on, "the same version" really means it's a virtual, but let's keep the diff small until we revisit.
 
-	if conflict.Name == constraint.name {
+	if conflict.Name == constraint.Name {
 		return conflict.Version != constraint.version
 	}
 
 	for _, confProv := range conflict.Provides {
 		confConstraint := cachedResolvePackageNameVersionPin(confProv)
-		if confConstraint.name != constraint.name {
+		if confConstraint.Name != constraint.Name {
 			// Not the constraint we're looking for.
 			continue
 		}
@@ -363,7 +363,7 @@ func (p *PkgResolver) conflictingVersion(constraint parsedConstraint, conflict *
 func (p *PkgResolver) disqualifyConflicts(pkg *RepositoryPackage, dq map[*RepositoryPackage]string) {
 	for _, prov := range pkg.Provides {
 		constraint := cachedResolvePackageNameVersionPin(prov)
-		providers, ok := p.nameMap[constraint.name]
+		providers, ok := p.nameMap[constraint.Name]
 		if !ok {
 			continue
 		}
@@ -383,7 +383,7 @@ func (p *PkgResolver) disqualifyConflicts(pkg *RepositoryPackage, dq map[*Reposi
 				continue
 			}
 
-			p.disqualify(dq, conflict.RepositoryPackage, pkg.Filename()+" already provides "+constraint.name)
+			p.disqualify(dq, conflict.RepositoryPackage, pkg.Filename()+" already provides "+constraint.Name)
 		}
 	}
 }
@@ -402,8 +402,8 @@ func (p *PkgResolver) pick(pkg *RepositoryPackage) error {
 
 	for _, prov := range pkg.Provides {
 		constraint := cachedResolvePackageNameVersionPin(prov)
-		if conflict, ok := p.selected[constraint.name]; ok {
-			return fmt.Errorf("selecting package %s conflicts with %s on %q", pkg.Filename(), conflict.Filename(), constraint.name)
+		if conflict, ok := p.selected[constraint.Name]; ok {
+			return fmt.Errorf("selecting package %s conflicts with %s on %q", pkg.Filename(), conflict.Filename(), constraint.Name)
 		}
 
 		// We don't care about virtuals, actually.
@@ -411,7 +411,7 @@ func (p *PkgResolver) pick(pkg *RepositoryPackage) error {
 			continue
 		}
 
-		p.selected[constraint.name] = pkg
+		p.selected[constraint.Name] = pkg
 	}
 
 	return nil
@@ -437,7 +437,7 @@ func (p *PkgResolver) constrain(constraints []string, dq map[*RepositoryPackage]
 			continue
 		}
 
-		providers, ok := p.nameMap[parsed.name]
+		providers, ok := p.nameMap[parsed.Name]
 		if !ok {
 			continue
 		}
@@ -449,7 +449,7 @@ func (p *PkgResolver) constrain(constraints []string, dq map[*RepositoryPackage]
 		}
 
 		for _, provider := range providers {
-			if provider.Name == parsed.name {
+			if provider.Name == parsed.Name {
 				actualVersion, err := cachedParseVersion(provider.Version)
 				// skip invalid ones
 				if err != nil {
@@ -463,7 +463,7 @@ func (p *PkgResolver) constrain(constraints []string, dq map[*RepositoryPackage]
 			} else {
 				for _, provides := range provider.Provides {
 					pp := cachedResolvePackageNameVersionPin(provides)
-					if pp.name != parsed.name {
+					if pp.Name != parsed.Name {
 						continue
 					}
 					actualVersion, err := cachedParseVersion(pp.version)
@@ -608,7 +608,7 @@ func (p *PkgResolver) GetPackageWithDependencies(ctx context.Context, pkgName st
 			for _, subDep := range installIfPkg.InstallIf {
 				// two possibilities: package name, or name=version
 				constraint := cachedResolvePackageNameVersionPin(subDep)
-				name, version := constraint.name, constraint.version
+				name, version := constraint.Name, constraint.version
 				// precise match of whatever it is, take it and continue
 				if _, ok := added[subDep]; ok {
 					matchCount++
@@ -638,7 +638,7 @@ func (p *PkgResolver) GetPackageWithDependencies(ctx context.Context, pkgName st
 // returns multiple in case you need to see all potential matches.
 func (p *PkgResolver) ResolvePackage(pkgName string, dq map[*RepositoryPackage]string) ([]*RepositoryPackage, error) {
 	constraint := cachedResolvePackageNameVersionPin(pkgName)
-	name, version, compare, pin := constraint.name, constraint.version, constraint.dep, constraint.pin
+	name, version, compare, pin := constraint.Name, constraint.version, constraint.dep, constraint.pin
 	pkgsWithVersions, ok := p.nameMap[name]
 	if !ok {
 		return nil, fmt.Errorf("nothing provides %q", name)
@@ -664,7 +664,7 @@ func (p *PkgResolver) ResolvePackage(pkgName string, dq map[*RepositoryPackage]s
 // This is like ResolvePackage but we only care about the best match and not all matches.
 func (p *PkgResolver) resolvePackage(pkgName string, dq map[*RepositoryPackage]string) (*RepositoryPackage, error) {
 	constraint := cachedResolvePackageNameVersionPin(pkgName)
-	name, version, compare, pin := constraint.name, constraint.version, constraint.dep, constraint.pin
+	name, version, compare, pin := constraint.Name, constraint.version, constraint.dep, constraint.pin
 
 	pkgsWithVersions, ok := p.nameMap[name]
 	if !ok {
@@ -719,7 +719,7 @@ func (p *PkgResolver) getPackageDependencies(ctx context.Context, pkg *Repositor
 	myProvides := make(map[string]bool, 2*len(pkg.Provides))
 	// see if we provide this
 	for _, provide := range pkg.Provides {
-		name := cachedResolvePackageNameVersionPin(provide).name
+		name := cachedResolvePackageNameVersionPin(provide).Name
 		myProvides[provide] = true
 		myProvides[name] = true
 	}
@@ -747,7 +747,7 @@ func (p *PkgResolver) getPackageDependencies(ctx context.Context, pkg *Repositor
 
 			// this package might be pinned to a version
 			constraint := cachedResolvePackageNameVersionPin(dep)
-			name, version, compare := constraint.name, constraint.version, constraint.dep
+			name, version, compare := constraint.Name, constraint.version, constraint.dep
 			// see if we provide this
 			if myProvides[name] || myProvides[dep] {
 				// we provide this, so skip it
@@ -792,7 +792,7 @@ func (p *PkgResolver) getPackageDependencies(ctx context.Context, pkg *Repositor
 				satisfiedByProvide := false
 				for _, provide := range picked.Provides {
 					prostraint := cachedResolvePackageNameVersionPin(provide)
-					pname, pversion, pcompare := prostraint.name, prostraint.version, prostraint.dep
+					pname, pversion, pcompare := prostraint.Name, prostraint.version, prostraint.dep
 					if pname != name {
 						continue
 					}
@@ -860,7 +860,7 @@ func (p *PkgResolver) getPackageDependencies(ctx context.Context, pkg *Repositor
 		}
 
 		pkgs := options[lowest]
-		name := cachedResolvePackageNameVersionPin(lowest).name
+		name := cachedResolvePackageNameVersionPin(lowest).Name
 
 		// Remove this from our constraints.
 		constraints = slices.DeleteFunc(constraints, func(s string) bool {
@@ -919,13 +919,13 @@ func cachedParseVersion(version string) (Version, error) {
 	return parsed, nil
 }
 
-func cachedResolvePackageNameVersionPin(pkgName string) parsedConstraint {
+func cachedResolvePackageNameVersionPin(pkgName string) ParsedConstraint {
 	cached, ok := parsedConstraints.Load(pkgName)
 	if ok {
-		return cached.(parsedConstraint)
+		return cached.(ParsedConstraint)
 	}
 
-	pin := resolvePackageNameVersionPin(pkgName)
+	pin := ResolvePackageNameVersionPin(pkgName)
 
 	parsedConstraints.Store(pkgName, pin)
 	return pin
@@ -1070,7 +1070,7 @@ func (p *PkgResolver) getDepVersionForName(pkg *repositoryPackage, name string)
 	}
 	for _, prov := range pkg.Provides {
 		constraint := cachedResolvePackageNameVersionPin(prov)
-		pName, pVersion := constraint.name, constraint.version
+		pName, pVersion := constraint.Name, constraint.version
 		if pVersion == "" {
 			pVersion = pkg.Version
 		}
diff --git a/pkg/apk/apk/version.go b/pkg/apk/apk/version.go
index f675723..e03077c 100644
--- a/pkg/apk/apk/version.go
+++ b/pkg/apk/apk/version.go
@@ -349,16 +349,27 @@ func (v versionDependency) satisfies(actualVersion, requiredVersion Version) boo
 	}
 }
 
-type parsedConstraint struct {
-	name    string
+type ParsedConstraint struct {
+	Name    string
 	version string
 	dep     versionDependency
 	pin     string
 }
 
+func (p ParsedConstraint) SatisfiedBy(v Version) (bool, error) {
+	if p.version == "" {
+		return true, nil
+	}
+	pv, err := cachedParseVersion(p.version)
+	if err != nil {
+		return false, err
+	}
+	return p.dep.satisfies(v, pv), nil
+}
+
 var endsWithReleaseStr = regexp.MustCompile(`-r\d+$`)
 
-func resolvePackageNameVersionPin(pkgName string) parsedConstraint {
+func ResolvePackageNameVersionPin(pkgName string) ParsedConstraint {
 	// Due to https://github.com/chainguard-dev/melange/pull/1871,
 	// we have to treat shared library depends/provides
 	// differently.
@@ -380,14 +391,14 @@ func resolvePackageNameVersionPin(pkgName string) parsedConstraint {
 
 	parts := packageNameRegex.FindAllStringSubmatch(pkgName, -1)
 	if len(parts) == 0 || len(parts[0]) < 2 {
-		return parsedConstraint{
-			name: pkgName,
+		return ParsedConstraint{
+			Name: pkgName,
 			dep:  versionAny,
 		}
 	}
 	// layout: [full match, name, =version, =|>|<, version, @pin, pin]
-	p := parsedConstraint{
-		name:    parts[0][1],
+	p := ParsedConstraint{
+		Name:    parts[0][1],
 		version: parts[0][4],
 		pin:     parts[0][6],
 		dep:     versionAny,
diff --git a/pkg/build/build.go b/pkg/build/build.go
index 590bb61..4bdf7de 100644
--- a/pkg/build/build.go
+++ b/pkg/build/build.go
@@ -94,7 +94,7 @@ func (bc *Context) BuildImage(ctx context.Context) error {
 	ctx, span := otel.Tracer("apko").Start(ctx, "BuildImage")
 	defer span.End()
 
-	if err := bc.buildImage(ctx); err != nil {
+	if _, err := bc.buildImage(ctx); err != nil {
 		log.Debugf("buildImage failed: %v", err)
 		b, err2 := yaml.Marshal(bc.ic)
 		if err2 != nil {
@@ -134,20 +134,16 @@ func (bc *Context) BuildLayers(ctx context.Context) ([]v1.Layer, error) {
 	ctx, span := otel.Tracer("apko").Start(ctx, "BuildLayers")
 	defer span.End()
 
-	// build image filesystem
-	if err := bc.BuildImage(ctx); err != nil {
-		return nil, err
-	}
-	if err := bc.postBuildSetApk(ctx); err != nil {
-		return nil, err
-	}
+	if bc.ic.Layering == nil {
+		_, layer, err := bc.BuildLayer(ctx)
+		if err != nil {
+			return nil, err
+		}
 
-	_, layer, err := bc.ImageLayoutToLayer(ctx)
-	if err != nil {
-		return nil, err
+		return []v1.Layer{layer}, nil
 	}
 
-	return []v1.Layer{layer}, nil
+	return bc.buildLayers(ctx)
 }
 
 // ImageLayoutToLayer given an already built-out
diff --git a/pkg/build/build_implementation.go b/pkg/build/build_implementation.go
index 7088fd8..a67836f 100644
--- a/pkg/build/build_implementation.go
+++ b/pkg/build/build_implementation.go
@@ -84,6 +84,7 @@ func pooledBufioWriter(w io.Writer) *bufio.Writer {
 // images where we are writing to multiple layers at the same time.
 type layerWriter struct {
 	w        *tar.Writer
+	stack    []*file // only used by multi-layer builds
 	finalize func() (*layer, error)
 }
 
@@ -150,7 +151,7 @@ func newLayerWriter(out *os.File) *layerWriter {
 	}
 }
 
-func (bc *Context) buildImage(ctx context.Context) error {
+func (bc *Context) buildImage(ctx context.Context) ([]*apk.Package, error) {
 	log := clog.FromContext(ctx)
 
 	// When using base image for the build, apko adds new layer on top of the base. This means
@@ -163,34 +164,39 @@ func (bc *Context) buildImage(ctx context.Context) error {
 		for index := range basePkgs {
 			err := bc.apk.AddInstalledPackage(&basePkgs[index].Package, basePkgs[index].Files)
 			if err != nil {
-				return err
+				return nil, err
 			}
 		}
 	}
 
+	var (
+		pkgs []*apk.Package
+		err  error
+	)
 	if bc.o.Lockfile != "" {
 		lock, err := lock.FromFile(bc.o.Lockfile)
 		if err != nil {
-			return fmt.Errorf("failed to load lock-file: %w", err)
+			return nil, fmt.Errorf("failed to load lock-file: %w", err)
 		}
 		if lock.Config == nil {
 			log.Warnf("The lock file does not contain checksum of the config. Please regenerate.")
 		} else if bc.o.ImageConfigChecksum != "" && bc.o.ImageConfigChecksum != lock.Config.DeepChecksum {
-			return fmt.Errorf("checksum in the lock file '%v' does not matches the original config: '%v' "+
+			return nil, fmt.Errorf("checksum in the lock file '%v' does not matches the original config: '%v' "+
 				"(maybe regenerate the lock file)",
 				bc.o.Lockfile, bc.o.ImageConfigFile)
 		}
 		allPkgs, err := installablePackagesForArch(lock, bc.Arch())
 		if err != nil {
-			return fmt.Errorf("failed getting packages for install from lockfile %s: %w", bc.o.Lockfile, err)
+			return nil, fmt.Errorf("failed getting packages for install from lockfile %s: %w", bc.o.Lockfile, err)
 		}
-		err = bc.apk.InstallPackages(ctx, &bc.o.SourceDateEpoch, allPkgs)
+		pkgs, err = bc.apk.InstallPackages(ctx, &bc.o.SourceDateEpoch, allPkgs)
 		if err != nil {
-			return fmt.Errorf("failed installation from lockfile %s: %w", bc.o.Lockfile, err)
+			return nil, fmt.Errorf("failed installation from lockfile %s: %w", bc.o.Lockfile, err)
 		}
 	} else {
-		if err := bc.apk.FixateWorld(ctx, &bc.o.SourceDateEpoch); err != nil {
-			return fmt.Errorf("installing apk packages: %w", err)
+		pkgs, err = bc.apk.FixateWorld(ctx, &bc.o.SourceDateEpoch)
+		if err != nil {
+			return nil, fmt.Errorf("installing apk packages: %w", err)
 		}
 	}
 
@@ -199,40 +205,40 @@ func (bc *Context) buildImage(ctx context.Context) error {
 	// If one wants to add a support for adding additional users they would need to look into this piece of code.
 	if bc.ic.Contents.BaseImage == nil {
 		if err := mutateAccounts(bc.fs, &bc.ic); err != nil {
-			return fmt.Errorf("failed to mutate accounts: %w", err)
+			return nil, fmt.Errorf("failed to mutate accounts: %w", err)
 		}
 	}
 
 	if err := bc.WriteEtcApkoConfig(ctx); err != nil {
-		return fmt.Errorf("failed to install apko config: %w", err)
+		return nil, fmt.Errorf("failed to install apko config: %w", err)
 	}
 
 	if err := mutatePaths(bc.fs, &bc.o, &bc.ic); err != nil {
-		return fmt.Errorf("failed to mutate paths: %w", err)
+		return nil, fmt.Errorf("failed to mutate paths: %w", err)
 	}
 
 	if err := bc.s6.WriteSupervisionTree(ctx, bc.ic.Entrypoint.Services); err != nil {
-		return fmt.Errorf("failed to write supervision tree: %w", err)
+		return nil, fmt.Errorf("failed to write supervision tree: %w", err)
 	}
 
 	// add busybox symlinks
 	installed, err := bc.apk.GetInstalled()
 	if err != nil {
-		return fmt.Errorf("getting installed packages: %w", err)
+		return nil, fmt.Errorf("getting installed packages: %w", err)
 	}
 
 	if err := installBusyboxLinks(bc.fs, installed); err != nil {
-		return err
+		return nil, err
 	}
 
 	// add necessary character devices
 	if err := installCharDevices(bc.fs); err != nil {
-		return err
+		return nil, err
 	}
 
 	log.Debug("finished building filesystem")
 
-	return nil
+	return pkgs, nil
 }
 
 func (bc *Context) WriteEtcApkoConfig(_ context.Context) error {
diff --git a/pkg/build/layers.go b/pkg/build/layers.go
new file mode 100644
index 0000000..baf1cb3
--- /dev/null
+++ b/pkg/build/layers.go
@@ -0,0 +1,416 @@
+// Copyright 2025 Chainguard, Inc.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package build
+
+import (
+	"archive/tar"
+	"cmp"
+	"context"
+	"fmt"
+	"io"
+	"maps"
+	"os"
+	"path"
+	"slices"
+
+	"chainguard.dev/apko/pkg/apk/apk"
+	apkfs "chainguard.dev/apko/pkg/apk/fs"
+
+	"github.com/chainguard-dev/clog"
+	v1 "github.com/google/go-containerregistry/pkg/v1"
+)
+
+func (bc *Context) buildLayers(ctx context.Context) ([]v1.Layer, error) {
+	log := clog.FromContext(ctx)
+
+	if strategy := bc.ic.Layering.Strategy; strategy != "origin" {
+		return nil, fmt.Errorf("unrecognized layering strategy %q", strategy)
+	}
+
+	if bc.ic.Contents.BaseImage != nil {
+		return nil, fmt.Errorf("layering with %q is unsupported", "baseimage")
+	}
+
+	// Build a single fs.FS, the normal way (this writes to bc.fs).
+	pkgs, err := bc.buildImage(ctx)
+	if err != nil {
+		return nil, fmt.Errorf("building filesystem: %w", err)
+	}
+
+	// Use our layering strategy to partition packages into a set of Budget groups.
+	groups, err := groupByOriginAndSize(pkgs, bc.ic.Layering.Budget)
+	if err != nil {
+		return nil, fmt.Errorf("grouping packages: %w", err)
+	}
+	log.Infof("Building %d layers with budget %d", len(groups), bc.ic.Layering.Budget)
+
+	for i, g := range groups {
+		log.Infof("  layer[%d]:", i)
+
+		for _, pkg := range g.pkgs {
+			log.Infof("    - %s=%s", pkg.Name, pkg.Version)
+		}
+	}
+
+	// Then partition that single fs.FS into multiple layers based on our layering strategy.
+	return splitLayers(ctx, bc.fs, groups, bc.o.TempDir())
+}
+
+func replacesGroup(rep string, g *group) (bool, error) {
+	constraint := apk.ResolvePackageNameVersionPin(rep)
+
+	// Look for the package to make sure the version satisfies Replaces.
+	for _, pkg := range g.pkgs {
+		if pkg.Name != constraint.Name {
+			// This is not the package we're looking for.
+			continue
+		}
+
+		ver, err := apk.ParseVersion(pkg.Version)
+		if err != nil {
+			return false, fmt.Errorf("parsing %s version %s: %w", pkg.Name, pkg.Version, err)
+		}
+
+		ok, err := constraint.SatisfiedBy(ver)
+		if err != nil {
+			return false, fmt.Errorf("checking %s satisfies %s: %w", pkg.Version, constraint.Name, err)
+		}
+
+		if ok {
+			return true, nil
+		}
+	}
+
+	return false, nil
+}
+
+func groupByOriginAndSize(pkgs []*apk.Package, budget int) ([]*group, error) {
+	// First, we're going to group packages by their origin.
+	byOrigin := map[string]*group{}
+	for _, pkg := range pkgs {
+		origin := pkg.Origin
+		if _, ok := byOrigin[origin]; !ok {
+			byOrigin[origin] = &group{}
+		}
+
+		g, ok := byOrigin[origin]
+		if !ok {
+			panic(fmt.Errorf("byOrigin[%q] missing", origin))
+		}
+
+		g.pkgs = append(g.pkgs, pkg)
+	}
+
+	// Then we need to merge any packages that replace each other.
+	byPackage := map[string]*group{}
+	for _, g := range byOrigin {
+		for _, pkg := range g.pkgs {
+			byPackage[pkg.Name] = g
+		}
+	}
+
+	replaceMap := map[string][]string{}
+	for _, g := range byPackage {
+		for _, pkg := range g.pkgs {
+			if len(pkg.Replaces) == 0 {
+				continue
+			}
+
+			replaceMap[pkg.Name] = pkg.Replaces
+		}
+	}
+
+	for pkg, replaces := range replaceMap {
+		for _, rep := range replaces {
+			constraint := apk.ResolvePackageNameVersionPin(rep)
+
+			replacee, ok := byPackage[constraint.Name]
+			if !ok {
+				// Whatever this package replaces is not in the image, that's normal.
+				continue
+			}
+
+			if ok, err := replacesGroup(rep, replacee); err != nil {
+				return nil, fmt.Errorf("checking %s replaces %s: %w", pkg, constraint.Name, err)
+			} else if !ok {
+				continue
+			}
+
+			g, ok := byPackage[pkg]
+			if !ok {
+				panic(fmt.Errorf("byPackage[%q] missing", pkg))
+			}
+
+			// If they're already merged, nothing to do.
+			if replacee == g {
+				continue
+			}
+
+			// Otherwise, we need to merge the two groups.
+			merged := merge(g, replacee)
+
+			// Update our maps so we can test identity above.
+			for _, pkg := range merged.pkgs {
+				byPackage[pkg.Name] = merged
+				byOrigin[pkg.Origin] = merged
+			}
+		}
+	}
+
+	// Now we need to pick the best groups to keep.
+	// First pass we'll set the size of each group to the sum of the installed size of all its packages.
+	groups := make([]*group, 0, budget)
+	seen := map[*group]struct{}{}
+	for v := range maps.Values(byOrigin) {
+		if _, ok := seen[v]; ok {
+			continue
+		}
+		seen[v] = struct{}{}
+		groups = append(groups, v)
+	}
+	for _, g := range groups {
+		for _, pkg := range g.pkgs {
+			g.size += pkg.InstalledSize
+			g.tiebreaker = max(g.tiebreaker, pkg.Name)
+		}
+	}
+
+	// Then we'll sort by the size and take the top $budget, merging the remainders.
+	slices.SortFunc(groups, func(a, b *group) int {
+		return cmp.Or(
+			cmp.Compare(b.size, a.size),             // Descending size.
+			cmp.Compare(a.tiebreaker, b.tiebreaker)) // In the rare case where we have identical sizes.
+	})
+
+	if len(groups) > budget {
+		cutoff := max(budget-1, 0) // Even if budget == 0, we want 1 group.
+
+		remainder := groups[cutoff:]
+		groups = groups[:cutoff]
+
+		groups = append(groups, merge(remainder...))
+	}
+
+	// Sort packages too just so they're in a consistent order.
+	for _, g := range groups {
+		slices.SortFunc(g.pkgs, func(a, b *apk.Package) int {
+			return cmp.Compare(a.Name, b.Name)
+		})
+	}
+
+	return groups, nil
+}
+
+type group struct {
+	pkgs []*apk.Package
+
+	size uint64
+
+	// This is silly but in the event that two groups have identical size,
+	// we want a predictable sort order _somehow_.
+	tiebreaker string
+}
+
+func merge(groups ...*group) *group {
+	merged := &group{}
+	for _, g := range groups {
+		merged.pkgs = slices.Concat(merged.pkgs, g.pkgs)
+		merged.size += g.size
+		merged.tiebreaker = max(merged.tiebreaker, g.tiebreaker)
+	}
+	return merged
+}
+
+func splitLayers(ctx context.Context, fsys apkfs.FullFS, groups []*group, tmpdir string) ([]v1.Layer, error) {
+	buf := make([]byte, 1<<20)
+
+	// We'll create a writer for each layer and a map to quickly access the writer given a package or group.
+	packageToWriter := map[string]*layerWriter{}
+	groupToWriter := map[*group]*layerWriter{}
+
+	for _, g := range groups {
+		f, err := os.CreateTemp(tmpdir, "layer-*.tar.gz")
+		if err != nil {
+			return nil, err
+		}
+		defer f.Close()
+
+		w := newLayerWriter(f)
+		groupToWriter[g] = w
+
+		for _, pkg := range g.pkgs {
+			packageToWriter[pkg.Name] = w
+		}
+	}
+
+	// The top layer holds anything that doesn't belong to a package.
+	f, err := os.CreateTemp(tmpdir, "layer-*.tar.gz")
+	if err != nil {
+		return nil, err
+	}
+	defer f.Close()
+
+	top := newLayerWriter(f)
+
+	// In a tar file, it is customary to include directories before files in those directories.
+	// In order to know which directories we need to include, we maintain a directory stack for each layer.
+	// We compare those stacks to the full FS that we're walking whenever we create a new tar entry.
+	// If the main stack doesn't match the layer's stack, we update the layer's stack and add
+	// any missing directory entries to the layer before we write the actual file entry.
+	stack := []*file{}
+
+	for f, err := range walkFS(ctx, fsys) {
+		if err != nil {
+			return nil, err
+		}
+
+		// Maintain our "main" stack.
+		if f.header.Typeflag == tar.TypeDir {
+			// Pop off any directories that are not parents of the current file's directory.
+			for i := len(stack) - 1; i >= 0; i-- {
+				if stack[i].path == path.Dir(f.path) {
+					break
+				}
+
+				stack = stack[:i]
+			}
+
+			// Push the current file onto the stack.
+			stack = append(stack, f)
+		}
+
+		// By default, all files go into the top layer.
+		w := top
+
+		// However, if a file implements an extension interface that tells us what package owns it,
+		// we can use that to determine which layer it belongs to (if any).
+		if pkger, ok := f.info.(interface {
+			Package() *apk.Package
+		}); ok {
+			if pkg := pkger.Package(); pkg != nil {
+				w, ok = packageToWriter[pkg.Name]
+				if !ok {
+					panic(fmt.Errorf("packageToWriter[%q] missing", pkg.Name))
+				}
+			}
+		}
+
+		// As described above, bring the layer's stack up to date with the main stack.
+		for _, todo := range w.alignStacks(stack) {
+			// We need to write any missing directories returned by alignStacks.
+			// But sometimes the result of alignStacks will include the file we're
+			// about to write (f) after this loop. In those cases, make sure we
+			// don't write it twice by skipping over it here.
+			if todo.header == f.header {
+				continue
+			}
+
+			if err := w.w.WriteHeader(todo.header); err != nil {
+				return nil, fmt.Errorf("writing header %s: %w", todo.header.Name, err)
+			}
+		}
+
+		// Now we're back to normal tar stuff.
+		if err := w.w.WriteHeader(f.header); err != nil {
+			return nil, fmt.Errorf("writing header %s: %w", f.header.Name, err)
+		}
+
+		if f.header.Typeflag == tar.TypeReg && f.header.Size > 0 {
+			data, err := fsys.Open(f.path)
+			if err != nil {
+				return nil, fmt.Errorf("opening %s: %w", f.path, err)
+			}
+
+			if _, err := io.CopyBuffer(w.w, data, buf); err != nil {
+				return nil, fmt.Errorf("copying %s: %w", f.path, err)
+			}
+
+			// Should never fail in practice.
+			if err := data.Close(); err != nil {
+				return nil, fmt.Errorf("closing %s: %w", f.path, err)
+			}
+		}
+	}
+
+	// Once we're done walking the FS, we need to finalize each layer...
+	layers := make([]v1.Layer, 0, len(groups)+1)
+	for i, g := range groups {
+		w := groupToWriter[g]
+		l, err := w.finalize()
+		if err != nil {
+			return nil, fmt.Errorf("finalizing group[%d] layer: %w", i, err)
+		}
+		layers = append(layers, l)
+	}
+
+	// ...including the top layer.
+	topLayer, err := top.finalize()
+	if err != nil {
+		return nil, fmt.Errorf("finalizing top layer: %w", err)
+	}
+
+	layers = append(layers, topLayer)
+
+	return layers, nil
+}
+
+// alignStacks ensures that w.stack is aligned with the passed in "main" stack
+// by updating w.stack and returning any directories w hasn't already seen written.
+// This relies on the fact that WalkDir iterates in lexicographic order, so we will
+// only ever write a tar entry the first time we see a dir (for a given layer).
+//
+// Examples...
+//
+// stack:   [etc]
+// w.stack: []
+// return:  [etc]
+//
+// stack:   [usr, usr/lib]
+// w.stack: [etc, etc/apk, etc/apk/keys]
+// return:  [usr, usr/lib]
+//
+// stack:   [usr, usr/lib]
+// w.stack: [usr]
+// return:  [usr/lib]
+//
+// stack:   [usr, usr/lib]
+// w.stack: [usr, usr/bin]
+// return:  [usr/lib]
+
+// stack:   [usr, usr/lib]
+// w.stack: [usr, usr/lib, usr/lib/foo]
+// return:  []
+func (w *layerWriter) alignStacks(stack []*file) []*file {
+	for i := 0; i < max(len(w.stack), len(stack)); i++ {
+		// The layer's stack is taller than the main stack, truncate layer's stack.
+		if i >= len(stack) {
+			w.stack = w.stack[:i]
+			return nil
+		}
+
+		// Otherwise skip over any entries that are the same.
+		if i < len(w.stack) && w.stack[i] == stack[i] {
+			continue
+		}
+
+		// For anything left that's not the same, we'll truncate w.stack,
+		// then append the main stack and return the difference.
+		w.stack = w.stack[:i]
+		w.stack = append(w.stack, stack[i:]...)
+		return w.stack[i:]
+	}
+
+	return nil
+}
diff --git a/pkg/build/oci/image.go b/pkg/build/oci/image.go
index c1ab992..2d45ce3 100644
--- a/pkg/build/oci/image.go
+++ b/pkg/build/oci/image.go
@@ -52,6 +52,12 @@ func BuildImageFromLayers(ctx context.Context, baseImage v1.Image, layers []v1.L
 		return nil, err
 	}
 
+	comment := "This is an apko single-layer image"
+	if len(layers) > 1 {
+		// TODO: Consider plumbing per-layer info here?
+		comment = ""
+	}
+
 	adds := make([]mutate.Addendum, 0, len(layers))
 	for _, layer := range layers {
 		digest, err := layer.Digest()
@@ -71,9 +77,9 @@ func BuildImageFromLayers(ctx context.Context, baseImage v1.Image, layers []v1.L
 			Layer: layer,
 			History: v1.History{
 				Author:    "apko",
-				Comment:   "This is an apko single-layer image", // TODO: Update this once we confirm no other changes.
+				Comment:   comment,
 				CreatedBy: "apko",
-				Created:   v1.Time{Time: created},
+				Created:   v1.Time{Time: created}, // TODO: Consider per-layer creation time?
 			},
 		})
 	}
diff --git a/pkg/build/types/image_configuration.go b/pkg/build/types/image_configuration.go
index b6b6f53..65d7b21 100644
--- a/pkg/build/types/image_configuration.go
+++ b/pkg/build/types/image_configuration.go
@@ -119,6 +119,9 @@ func (ic *ImageConfiguration) MergeInto(target *ImageConfiguration) error {
 	if target.WorkDir == "" {
 		target.WorkDir = ic.WorkDir
 	}
+	if target.Layering == nil {
+		target.Layering = ic.Layering
+	}
 	if len(target.Archs) == 0 {
 		target.Archs = ic.Archs
 	}
diff --git a/pkg/build/types/schema.json b/pkg/build/types/schema.json
index 6ba79e7..f652cf5 100644
--- a/pkg/build/types/schema.json
+++ b/pkg/build/types/schema.json
@@ -130,6 +130,10 @@
           },
           "type": "array",
           "description": "Optional: A list of volumes to configure\n\nThis is _not_ the same as Paths, but refers to the OCI spec \"volumes\"\nfield used by some container runtimes (docker) to create volumes at\nruntime. For most use cases, this is not needed, but consider using this\nwhen the image requires special volume configuration at runtime for\nsupported container runtimes."
+        },
+        "layering": {
+          "$ref": "#/$defs/Layering",
+          "description": "Experimental: Optional: Configuration to control layering of the OCI image."
         }
       },
       "additionalProperties": false,
@@ -197,6 +201,18 @@
       "additionalProperties": false,
       "type": "object"
     },
+    "Layering": {
+      "properties": {
+        "strategy": {
+          "type": "string"
+        },
+        "budget": {
+          "type": "integer"
+        }
+      },
+      "additionalProperties": false,
+      "type": "object"
+    },
     "PathMutation": {
       "properties": {
         "path": {
diff --git a/pkg/build/types/types.go b/pkg/build/types/types.go
index cb5b51b..68ac758 100644
--- a/pkg/build/types/types.go
+++ b/pkg/build/types/types.go
@@ -193,6 +193,9 @@ type ImageConfiguration struct {
 	// when the image requires special volume configuration at runtime for
 	// supported container runtimes.
 	Volumes []string `json:"volumes,omitempty" yaml:"volumes,omitempty"`
+
+	// Experimental: Optional: Configuration to control layering of the OCI image.
+	Layering *Layering `json:"layering,omitempty" yaml:"layering,omitempty" apko:"experimental"`
 }
 
 // Architecture represents a CPU architecture for the container image.
@@ -407,3 +410,8 @@ type SBOM struct {
 	Format string
 	Digest v1.Hash
 }
+
+type Layering struct {
+	Strategy string `json:"strategy,omitempty" yaml:"strategy,omitempty"`
+	Budget   int    `json:"budget,omitempty" yaml:"budget,omitempty"`
+}
diff --git a/pkg/tarfs/fs.go b/pkg/tarfs/fs.go
index 079dcec..c0a0073 100644
--- a/pkg/tarfs/fs.go
+++ b/pkg/tarfs/fs.go
@@ -1033,3 +1033,12 @@ func (m *memFileInfo) Sys() any {
 
 	return th
 }
+
+// This is a bit janky, but we need a way to know who owns this.
+func (m *memFileInfo) Package() *apk.Package {
+	if m.node.te == nil {
+		return nil
+	}
+
+	return m.node.te.pkg
+}


Test patch:
diff --git a/internal/cli/publish_test.go b/internal/cli/publish_test.go
index 8d73c6f..0bbddc0 100644
--- a/internal/cli/publish_test.go
+++ b/internal/cli/publish_test.go
@@ -151,3 +151,74 @@ func (s *sentinel) RoundTrip(in *http.Request) (*http.Response, error) {
 	in.Header.Set("Magic", "SecretValue")
 	return s.rt.RoundTrip(in)
 }
+
+func TestPublishLayering(t *testing.T) {
+	ctx := context.Background()
+	tmp := t.TempDir()
+
+	// Set up a registry that requires we see a magic header.
+	// This allows us to make sure that remote options are getting passed
+	// around to anything that hits the registry.
+	r := registry.New()
+	h := http.HandlerFunc(func(w http.ResponseWriter, req *http.Request) {
+		require.Equal(t, req.Header.Get("Magic"), "SecretValue")
+		r.ServeHTTP(w, req)
+	})
+	s := httptest.NewServer(h)
+	defer s.Close()
+	u, err := url.Parse(s.URL)
+	require.NoError(t, err)
+
+	st := &sentinel{s.Client().Transport}
+	dst := fmt.Sprintf("%s/test/publish", u.Host)
+
+	config := filepath.Join("testdata", "layering.yaml")
+
+	outputRefs := ""
+	archs := types.ParseArchitectures([]string{"amd64", "arm64"})
+	ropt := []remote.Option{remote.WithTransport(st)}
+	opts := []build.Option{
+		build.WithConfig(config, []string{}),
+		build.WithTags(dst),
+		build.WithSBOMFormats(sbom.DefaultOptions.Formats),
+		build.WithAnnotations(map[string]string{"foo": "bar"}),
+	}
+	publishOpts := []cli.PublishOption{cli.WithTags(dst)}
+
+	sbomPath := filepath.Join(tmp, "sboms")
+	err = os.MkdirAll(sbomPath, 0o750)
+	require.NoError(t, err)
+
+	err = cli.PublishCmd(ctx, outputRefs, archs, ropt, sbomPath, opts, publishOpts)
+	require.NoError(t, err)
+
+	ref, err := name.ParseReference(dst)
+	require.NoError(t, err)
+
+	idx, err := remote.Index(ref, ropt...)
+	require.NoError(t, err)
+
+	// Not strictly necessary, but this will validate that the index is well-formed.
+	require.NoError(t, validate.Index(idx))
+
+	digest, err := idx.Digest()
+	require.NoError(t, err)
+
+	// This test will fail if we ever make a change in apko that changes the image.
+	// Sometimes, this is intentional, and we need to change this and bump the version.
+	want := "sha256:e4854bdd74aca1534a30da899edef2ad46b9a7e088ceae2094d85a287a20891a"
+	require.Equal(t, want, digest.String())
+
+	im, err := idx.IndexManifest()
+	require.NoError(t, err)
+
+	for _, m := range im.Manifests {
+		child, err := idx.Image(m.Digest)
+		require.NoError(t, err)
+
+		cm, err := child.Manifest()
+		require.NoError(t, err)
+
+		require.Equal(t, 2, len(cm.Layers))
+	}
+}
diff --git a/internal/cli/testdata/layering.yaml b/internal/cli/testdata/layering.yaml
new file mode 100644
index 0000000..4b7b66c
--- /dev/null
+++ b/internal/cli/testdata/layering.yaml
@@ -0,0 +1,18 @@
+contents:
+  keyring:
+    - ./testdata/melange.rsa.pub
+  repositories:
+    - ./testdata/packages
+  packages:
+    - replayout
+
+entrypoint:
+  command: /bin/sh -l
+
+archs:
+- x86_64
+- aarch64
+
+layering:
+  strategy: origin
+  budget: 2
diff --git a/pkg/apk/apk/install_test.go b/pkg/apk/apk/install_test.go
index d47975a..5eba3c7 100644
--- a/pkg/apk/apk/install_test.go
+++ b/pkg/apk/apk/install_test.go
@@ -171,7 +171,7 @@ func TestInstallAPKFiles(t *testing.T) {
 				{overwriteFilename, 0o755, false, finalContent, nil},
 			})
 
-			err = apk.InstallPackages(context.Background(), nil, []InstallablePackage{fp1, fp2})
+			_, err = apk.InstallPackages(context.Background(), nil, []InstallablePackage{fp1, fp2})
 			require.Error(t, err, "some double-write error")
 
 			actual, err := src.ReadFile(overwriteFilename)
@@ -200,7 +200,7 @@ func TestInstallAPKFiles(t *testing.T) {
 				{overwriteFilename, 0755, false, finalContent, nil},
 			})
 
-			err = apk.InstallPackages(context.Background(), nil, []InstallablePackage{fp1, fp2})
+			_, err = apk.InstallPackages(context.Background(), nil, []InstallablePackage{fp1, fp2})
 			require.NoError(t, err)
 
 			actual, err := src.ReadFile(overwriteFilename)
@@ -229,7 +229,7 @@ func TestInstallAPKFiles(t *testing.T) {
 				{overwriteFilename, 0o755, false, finalContent, nil},
 			})
 
-			err = apk.InstallPackages(context.Background(), nil, []InstallablePackage{fp1, fp2})
+			_, err = apk.InstallPackages(context.Background(), nil, []InstallablePackage{fp1, fp2})
 			require.NoError(t, err)
 
 			actual, err := src.ReadFile(overwriteFilename)
@@ -257,7 +257,7 @@ func TestInstallAPKFiles(t *testing.T) {
 				{overwriteFilename, 0o755, false, originalContent, nil},
 			})
 
-			err = apk.InstallPackages(context.Background(), nil, []InstallablePackage{fp1, fp2})
+			_, err = apk.InstallPackages(context.Background(), nil, []InstallablePackage{fp1, fp2})
 			require.NoError(t, err)
 
 			actual, err := src.ReadFile(overwriteFilename)
@@ -286,7 +286,7 @@ func TestInstallAPKFiles(t *testing.T) {
 				{overwriteFilename, 0755, false, finalContent, nil},
 			})
 
-			err = apk.InstallPackages(context.Background(), nil, []InstallablePackage{fp1, fp2})
+			_, err = apk.InstallPackages(context.Background(), nil, []InstallablePackage{fp1, fp2})
 			require.NoError(t, err)
 
 			actual, err := src.ReadFile(overwriteFilename)
diff --git a/pkg/apk/apk/repo_test.go b/pkg/apk/apk/repo_test.go
index f12fe52..60e18d8 100644
--- a/pkg/apk/apk/repo_test.go
+++ b/pkg/apk/apk/repo_test.go
@@ -987,12 +987,12 @@ func makeResolver(provs, deps map[string][]string) *PkgResolver {
 	packages := make(map[string]*Package, max(len(provs), len(deps)))
 
 	for pkgver := range provs {
-		parsed := resolvePackageNameVersionPin(pkgver)
-		packages[pkgver] = &Package{Name: parsed.name, Version: parsed.version}
+		parsed := ResolvePackageNameVersionPin(pkgver)
+		packages[pkgver] = &Package{Name: parsed.Name, Version: parsed.version}
 	}
 	for pkgver := range deps {
-		parsed := resolvePackageNameVersionPin(pkgver)
-		packages[pkgver] = &Package{Name: parsed.name, Version: parsed.version}
+		parsed := ResolvePackageNameVersionPin(pkgver)
+		packages[pkgver] = &Package{Name: parsed.Name, Version: parsed.version}
 	}
 
 	for pkgver, pkgProvs := range provs {
diff --git a/pkg/apk/apk/version_test.go b/pkg/apk/apk/version_test.go
index 07240d1..7edefa4 100644
--- a/pkg/apk/apk/version_test.go
+++ b/pkg/apk/apk/version_test.go
@@ -941,8 +941,8 @@ func TestResolverPackageNameVersionPin(t *testing.T) {
 
 	for _, tt := range tests {
 		t.Run(tt.input, func(t *testing.T) {
-			constraint := resolvePackageNameVersionPin(tt.input)
-			require.Equal(t, tt.name, constraint.name)
+			constraint := ResolvePackageNameVersionPin(tt.input)
+			require.Equal(t, tt.name, constraint.Name)
 			require.Equal(t, tt.version, constraint.version)
 			require.Equal(t, tt.dep, constraint.dep)
 			require.Equal(t, tt.pin, constraint.pin)
diff --git a/pkg/build/build_test.go b/pkg/build/build_test.go
index c663cc1..388b6d8 100644
--- a/pkg/build/build_test.go
+++ b/pkg/build/build_test.go
@@ -30,7 +30,24 @@ import (
 	"chainguard.dev/apko/pkg/build/types"
 )
 
-func TestBuildLayer(t *testing.T) {
+func TestBuildLayers(t *testing.T) {
+	ctx := context.Background()
+
+	opts := []build.Option{
+		build.WithConfig("layering.yaml", []string{"testdata"}),
+	}
+
+	bc, err := build.New(ctx, fs.NewMemFS(), opts...)
+	if err != nil {
+		t.Fatal(err)
+	}
+
+	layers, err := bc.BuildLayers(ctx)
+	if err != nil {
+		t.Fatal(err)
+	}
+
+	require.Len(t, layers, 2)
 }
 
 func TestBuildImage(t *testing.T) {
diff --git a/pkg/build/layers_test.go b/pkg/build/layers_test.go
new file mode 100644
index 0000000..96ed748
--- /dev/null
+++ b/pkg/build/layers_test.go
@@ -0,0 +1,226 @@
+// Copyright 2025 Chainguard, Inc.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package build
+
+import (
+	"fmt"
+	"slices"
+	"testing"
+
+	"chainguard.dev/apko/pkg/apk/apk"
+)
+
+func size(pkgs ...*apk.Package) uint64 {
+	var total uint64
+	for _, pkg := range pkgs {
+		total += pkg.InstalledSize
+	}
+	return total
+}
+
+func TestGroupByOriginAndSize(t *testing.T) {
+	crane := &apk.Package{Name: "crane", Origin: "crane", InstalledSize: 100}
+
+	glibc := &apk.Package{Name: "glibc", Origin: "glibc", InstalledSize: 6113087}
+	posix := &apk.Package{Name: "glibc-locale-posix", Origin: "glibc", InstalledSize: 417444}
+
+	libcrypt1 := &apk.Package{Name: "libcrypt1", Origin: "glibc", Version: "2.38-r14", InstalledSize: 23508}
+	libxcrypt := &apk.Package{Name: "libxcrypt", Origin: "libxcrypt", InstalledSize: 235761, Replaces: []string{"libcrypt1<2.38-r15"}}
+
+	newcrypt1 := &apk.Package{Name: "libcrypt1", Origin: "glibc", Version: "2.38-r16", InstalledSize: 23508}
+
+	repxcrypt := &apk.Package{Name: "libxcrypt", Origin: "libxcrypt", InstalledSize: 235761, Replaces: []string{"libcrypt1"}}
+	for _, tc := range []struct {
+		pkgs   []*apk.Package
+		budget int
+		want   []*group
+		err    error
+	}{{
+		pkgs:   []*apk.Package{crane},
+		budget: 1,
+		want:   []*group{{pkgs: []*apk.Package{crane}, size: size(crane), tiebreaker: "crane"}},
+	}, {
+		// glibc and glibc-locale-posix should be grouped by origin
+		pkgs:   []*apk.Package{crane, glibc, posix},
+		budget: 2,
+		want: []*group{
+			{pkgs: []*apk.Package{glibc, posix}, size: size(glibc, posix), tiebreaker: "glibc-locale-posix"},
+			{pkgs: []*apk.Package{crane}, size: size(crane), tiebreaker: "crane"},
+		},
+	}, {
+		// reasonable default if budget is unspecified
+		pkgs: []*apk.Package{crane, glibc, posix},
+		want: []*group{
+			{pkgs: []*apk.Package{crane, glibc, posix}, size: size(crane, glibc, posix), tiebreaker: "glibc-locale-posix"},
+		},
+	}, {
+		// libxcrypt replace libcrypt1, so it should be merged into the glibc origin
+		pkgs:   []*apk.Package{crane, glibc, posix, libcrypt1, libxcrypt},
+		budget: 5,
+		want: []*group{
+			{pkgs: []*apk.Package{glibc, posix, libcrypt1, libxcrypt}, size: size(glibc, libcrypt1, libxcrypt, posix), tiebreaker: "libxcrypt"},
+			{pkgs: []*apk.Package{crane}, size: size(crane), tiebreaker: "crane"},
+		},
+	}, {
+		// libxcrypt replaces does not match the version constraint for "newcrypt1", so it doesn't get merged.
+		pkgs:   []*apk.Package{crane, glibc, posix, newcrypt1, libxcrypt},
+		budget: 5,
+		want: []*group{
+			{pkgs: []*apk.Package{glibc, posix, newcrypt1}, size: size(glibc, newcrypt1, posix), tiebreaker: "libcrypt1"},
+			{pkgs: []*apk.Package{libxcrypt}, size: size(libxcrypt), tiebreaker: "libxcrypt"},
+			{pkgs: []*apk.Package{crane}, size: size(crane), tiebreaker: "crane"},
+		},
+	}, {
+		// "repxcrypt" replaces has no version, so it _does_ merge with "newcrypt1".
+		pkgs:   []*apk.Package{crane, glibc, posix, newcrypt1, repxcrypt},
+		budget: 5,
+		want: []*group{
+			{pkgs: []*apk.Package{glibc, posix, newcrypt1, repxcrypt}, size: size(glibc, newcrypt1, posix, repxcrypt), tiebreaker: "libxcrypt"},
+			{pkgs: []*apk.Package{crane}, size: size(crane), tiebreaker: "crane"},
+		},
+	}, {
+		// should be 3 groups but budget constricts that to 2
+		pkgs:   []*apk.Package{crane, glibc, posix, newcrypt1, libxcrypt},
+		budget: 2,
+		want: []*group{
+			{pkgs: []*apk.Package{glibc, posix, newcrypt1}, size: size(glibc, newcrypt1, posix), tiebreaker: "libcrypt1"},
+			{pkgs: []*apk.Package{crane, libxcrypt}, size: size(crane, libxcrypt), tiebreaker: "libxcrypt"},
+		},
+	}} {
+		got, err := groupByOriginAndSize(tc.pkgs, tc.budget)
+		if err != nil && tc.err != nil {
+			continue
+		}
+
+		if err != nil && tc.err == nil {
+			t.Errorf("groupByOriginAndSize(%v, %d) unexpected error: %v", tc.pkgs, tc.budget, err)
+		} else if err == nil && tc.err != nil {
+			t.Errorf("groupByOriginAndSize(%v, %d) expected error: %v", tc.pkgs, tc.budget, tc.err)
+		}
+
+		if err := compareGroups(got, tc.want); err != nil {
+			t.Errorf("groupByOriginAndSize(%v, %d) mismatch: %v", tc.pkgs, tc.budget, err)
+
+			for i, g := range got {
+				t.Logf("got[%d]: %v", i, g.pkgs)
+			}
+			for i, g := range tc.want {
+				t.Logf("want[%d]: %v", i, g.pkgs)
+			}
+		}
+	}
+}
+
+func compareGroups(a, b []*group) error {
+	if len(a) != len(b) {
+		return fmt.Errorf("len(a) = %d; len(b) = %d", len(a), len(b))
+	}
+	for i := range a {
+		aa, bb := a[i], b[i]
+		if len(aa.pkgs) != len(bb.pkgs) {
+			return fmt.Errorf("len(a[%d].pkgs) = %d; len(b[%d].pkgs) = %d", i, len(aa.pkgs), i, len(bb.pkgs))
+		}
+
+		for j := range aa.pkgs {
+			if aa.pkgs[j].Name != bb.pkgs[j].Name {
+				return fmt.Errorf("a[%d].pkgs[%d] = %s; b[%d].pkgs[%d] = %s", i, j, aa.pkgs[j].Name, i, j, bb.pkgs[j].Name)
+			}
+		}
+
+		if aa.size != bb.size {
+			return fmt.Errorf("a[%d].size = %d; b[%d].size = %d", i, aa.size, i, bb.size)
+		}
+		if aa.tiebreaker != bb.tiebreaker {
+			return fmt.Errorf("a[%d].tiebreaker = %s; b[%d].tiebreaker = %s", i, aa.tiebreaker, i, bb.tiebreaker)
+		}
+	}
+
+	return nil
+}
+
+func TestAlignStacks(t *testing.T) {
+	usr := []*file{{
+		path: "usr",
+	}, {
+		path: "usr/lib",
+	}}
+	etc := []*file{{
+		path: "etc",
+	}, {
+		path: "etc/apk",
+	}, {
+		path: "etc/apk/key",
+	}}
+	for i, tc := range []struct {
+		stack  []*file
+		before []*file
+		diff   []*file
+		after  []*file
+	}{{
+		stack:  usr,
+		before: usr,
+		after:  usr,
+	}, {
+		stack: usr,
+		after: usr,
+		diff:  usr,
+	}, {
+		stack:  usr,
+		before: etc,
+		after:  usr,
+		diff:   usr,
+	}, {
+		stack:  etc,
+		before: usr,
+		after:  etc,
+		diff:   etc,
+	}, {
+		stack:  etc[:2],
+		before: etc,
+		after:  etc[:2],
+	}, {
+		stack:  etc,
+		before: etc[:2],
+		after:  etc,
+		diff:   etc[2:],
+	}} {
+		t.Run(fmt.Sprintf("case_%d", i), func(t *testing.T) {
+			// clone to avoid mutating the usr and etc slices directly
+			w := &layerWriter{stack: slices.Clone(tc.before)}
+
+			if err := compareStacks(w.alignStacks(tc.stack), tc.diff); err != nil {
+				t.Errorf("alignStacks() mismatch: %v", err)
+			}
+			if err := compareStacks(w.stack, tc.after); err != nil {
+				t.Errorf("w.stack mismatch: %v", err)
+			}
+		})
+	}
+}
+
+// NB: this only cares about path
+func compareStacks(a, b []*file) error {
+	if len(a) != len(b) {
+		return fmt.Errorf("len(a) = %d; len(b) = %d", len(a), len(b))
+	}
+
+	for i := range len(a) {
+		if a[i].path != b[i].path {
+			return fmt.Errorf("a[%d] = %s; b[%d] = %s", i, a[i].path, i, b[i].path)
+		}
+	}
+
+	return nil
+}