Opensource internals

Random ClusterIPs on Purpose: The Allocator That Fights eBPF Hash Collisions

12 min read Jay Hubbert

Both ClusterIP allocators pick a random starting offset and scan forward, and both split the service CIDR so dynamic allocation stays in the upper subrange, because sequential ClusterIPs collide in eBPF datapaths.

TL;DR: Every ClusterIP allocator in Kubernetes picks a random starting offset and scans forward until it finds a free address, instead of handing out 10.96.0.1, 10.96.0.2, 10.96.0.3 in order. Sequential ClusterIPs are pathological for eBPF datapaths like Cilium, which hash on the 5-tuple: consecutive ClusterIPs land in the same hash bucket and create hot spots. Both allocators also split the service CIDR into a small lower subrange for statically requested IPs and an upper subrange for dynamic ones, using the formula min(max(16, cidrSize/16), 256).

A ClusterIP looks like an ordinary IP address, and that is exactly the problem. It is not a routable address; it is a key into a load balancer’s service map, and the key space is structured in a way that datapaths dislike.

If you allocate 10.96.0.1, 10.96.0.2, 10.96.0.3, … then a datapath that hashes on the 5-tuple will produce correlated hashes for them - consecutive values differ in the low bits, and most hash functions mix poorly with arithmetic progressions. The result is a small number of hot buckets in the service map and uneven load across it. Randomising the allocation makes the hash distribution uniform for free.

Two allocators, one idea

Kubernetes has two ClusterIP allocators and they are not interchangeable at the object level, but they agree on the algorithm:

  • The legacy bitmap allocator (pkg/registry/core/service/ipallocator/bitmap.go) keeps a big.Int bitmap of the CIDR in memory, and persists a snapshot of it in the kubernetes.io/service-cluster-ip-range ConfigMap.
  • The IPAddress-object allocator (pkg/registry/core/service/ipallocator/ipallocator.go) stores one networking.k8s.io/v1 IPAddress object per allocated IP and uses an informer as its cache.

The legacy one has a hard ceiling on IPv6, because it keeps a bitmap:

go 
// pkg/registry/core/service/ipallocator/bitmap.go:68
	if netutils.IsIPv6CIDR(cidr) {
		family = api.IPv6Protocol
		// Limit the max size, since the allocator keeps a bitmap of that size.
		if max > 65536 {
			max = 65536
		}
	} else {

65536 entries is nothing for an IPv6 service CIDR, which is why the new allocator exists. The new one has a different constraint - the CIDR must be at least a /64:

go 
// pkg/registry/core/service/ipallocator/ipallocator.go:87
	if prefix.Addr().Is6() && prefix.Bits() < 64 {
		return nil, fmt.Errorf("shortest allowed prefix length for service CIDR is 64, got %d", prefix.Bits())
	}

The subrange split

KEP-3070 introduced a split of the service CIDR into two subranges, and both allocators implement it. The lower subrange is where statically requested IPs are expected to live; the upper subrange is where dynamic allocation happens. The split point is computed by a single function:

go 
// pkg/registry/core/service/ipallocator/bitmap.go:352
// calculateRangeOffset estimates the offset used on the range for statically allocation based on
// the following formula `min(max($min, cidrSize/$step), $max)`, described as ~never less than
// $min or more than $max, with a graduated step function between them~. The function returns 0
// if any of the parameters is invalid.
func calculateRangeOffset(cidr *net.IPNet) int {
	// default values for min(max($min, cidrSize/$step), $max)
	const (
		min  = 16
		max  = 256
		step = 16
	)

	cidrSize := netutils.RangeSize(cidr)
	// available addresses are always less than the cidr size
	// A /28 CIDR returns 16 addresses, but 2 of them, the network
	// and broadcast addresses are not available.
	if cidrSize <= min {
		return 0
	}

	offset := cidrSize / step
	if offset < min {
		return min
	}
	if offset > max {
		return max
	}
	return int(offset)
}

So the reserved lower subrange is min(max(16, cidrSize/16), 256) addresses. For the default 10.96.0.0/12 service CIDR - 1 048 574 usable addresses - cidrSize/16 is 65536, which is above the maximum of 256, so the offset is 256. The lower 256 addresses of the service CIDR are reserved for static requests; dynamic allocation starts at 10.96.1.0 and above.

For a small CIDR like a /24 (254 usable addresses), 254/16 = 15, which is below the minimum of 16, so the offset is 16. For a /28 (14 usable addresses after excluding network and broadcast) the function returns 0 - there is no room to split, so there is no split.

The new allocator computes the same offset and turns it into an address boundary:

go 
// pkg/registry/core/service/ipallocator/ipallocator.go:113
	// KEP-3070: Reserve Service IP Ranges For Dynamic and Static IP Allocation
	// calculate the subrange offset
	rangeOffset := calculateRangeOffset(cidr)
	offsetAddress, err := addOffsetAddress(ipFirst, uint64(rangeOffset))
	if err != nil {
		return nil, err
	}

The Allocator struct then carries both boundaries explicitly:

go 
// pkg/registry/core/service/ipallocator/ipallocator.go:49
type Allocator struct {
	cidr          *net.IPNet
	prefix        netip.Prefix
	firstAddress  netip.Addr   // first IP address within the range
	offsetAddress netip.Addr   // IP address that delimits the upper and lower subranges
	lastAddress   netip.Addr   // last IP address within the range
	family        api.IPFamily // family is the IP family of this range

	rangeOffset int    // subdivides the assigned IP range to prefer dynamic allocation from the upper range
	size        uint64 // cap the total number of IPs available to maxInt64

One caveat worth stating plainly: this is a soft reservation in the new allocator. allocateService - the static path - only checks that the requested IP is inside [firstAddress, lastAddress], not that it is in the lower subrange. The lower subrange is kept free by not allocating from it dynamically, not by forbidding static requests there.

The legacy random scan

The legacy allocator’s randomisation lives in the bit-strategy object rather than in the allocator itself. randomScanStrategyWithOffset picks a random start and scans forward:

go 
// pkg/registry/core/service/allocator/bitmap.go:72
func NewAllocationMapWithOffset(max int, rangeSpec string, offset int) *AllocationBitmap {
	a := AllocationBitmap{
		strategy: randomScanStrategyWithOffset{
			rand:   rand.New(rand.NewSource(time.Now().UnixNano())),
			offset: offset,
		},
		allocated: big.NewInt(0),
		count:     0,

The upper subrange is tried first, and the lower one only as a fallback:

go 
// pkg/registry/core/service/allocator/bitmap.go:238
func (rss randomScanStrategyWithOffset) AllocateBit(allocated *big.Int, max, count int) (int, bool) {
	if count >= max {
		return 0, false
	}
	// size of the upper subrange, prioritized for random allocation
	subrangeMax := max - rss.offset
	// try to get a value from the upper range [rss.reserved, max]
	start := rss.rand.Intn(subrangeMax)
	for i := 0; i < subrangeMax; i++ {
		at := rss.offset + ((start + i) % subrangeMax)
		if allocated.Bit(at) == 0 {
			return at, true
		}
	}

	start = rss.rand.Intn(rss.offset)
	// subrange full, try to get the value from the first block before giving up.
	for i := 0; i < rss.offset; i++ {
		at := (start + i) % rss.offset
		if allocated.Bit(at) == 0 {
			return at, true
		}
	}
	return 0, false
}

The rand is seeded per allocator instance from the wall clock:

go 
// pkg/registry/core/service/allocator/bitmap.go:238
func (rss randomScanStrategyWithOffset) AllocateBit(allocated *big.Int, max, count int) (int, bool) {
	if count >= max {
		return 0, false
	}
	// size of the upper subrange, prioritized for random allocation
	subrangeMax := max - rss.offset
	// try to get a value from the upper range [rss.reserved, max]
	start := rss.rand.Intn(subrangeMax)
	for i := 0; i < subrangeMax; i++ {
		at := rss.offset + ((start + i) % subrangeMax)
		if allocated.Bit(at) == 0 {
			return at, true
		}
	}

	start = rss.rand.Intn(rss.offset)
	// subrange full, try to get the value from the first block before giving up.
	for i := 0; i < rss.offset; i++ {
		at := (start + i) % rss.offset
		if allocated.Bit(at) == 0 {
			return at, true
		}
	}
	return 0, false
}

Note the loop structure: the scan is at := offset + ((start + i) % subrangeMax), i.e. it wraps around within the upper subrange rather than running off the end of the range. And the fallback into the lower subrange uses a second independent random start, so a nearly-full range does not degenerate into allocating the low addresses in order.

The IPAddress random scan

The new allocator does the same thing with netip.Addr and an explicit iterator instead of a bitmap. The random offset is chosen in three branches, because the range size is a uint64 and rand.Int63n panics on a non-positive argument:

go 
// pkg/registry/core/service/ipallocator/ipallocator.go:248
	// rand.Int63n panics for n <= 0 so we need to avoid problems when
	// converting from uint64 to int64
	rangeSize := a.size - uint64(a.rangeOffset)
	var offset uint64
	switch {
	case rangeSize >= math.MaxInt64:
		offset = rand.Uint64()
		// a.offsetAddress + offset should not overflow a 64 bit CIDR.
		if math.MaxUint64-offset < uint64(a.rangeOffset) {
			offset -= uint64(a.rangeOffset)
		}
	case rangeSize == 0:
		return net.IP{}, ErrFull
	default:
		offset = uint64(rand.Int63n(int64(rangeSize)))
	}
	iterator := ipIterator(a.offsetAddress, a.lastAddress, offset)

The iterator starts at offsetAddress + offset and wraps within [offsetAddress, lastAddress]:

go 
// pkg/registry/core/service/ipallocator/ipallocator.go:293
func ipIterator(first netip.Addr, last netip.Addr, offset uint64) func() netip.Addr {
	// There are no modulo operations for IP addresses
	modulo := func(addr netip.Addr) netip.Addr {
		if addr.Compare(last) == 1 {
			return first
		}
		return addr
	}
	next := func(addr netip.Addr) netip.Addr {
		return modulo(addr.Next())
	}

And when the upper subrange is exhausted, the lower one is tried, again with a fresh random start:

go 
// pkg/registry/core/service/ipallocator/ipallocator.go:270
	// if the upper range is full, try to allocate from the lower range
	if errors.Is(err, ErrFull) && a.rangeOffset != 0 {
		offset = uint64(rand.Intn(a.rangeOffset))
		iterator = ipIterator(a.firstAddress, a.offsetAddress.Prev(), offset)
		ip, err = a.allocateFromRange(iterator, svc)

The mid-air collision

The new allocator’s cache is an informer, so it can be stale. The check for “is this IP free?” is a cache lookup, and the actual allocation is an API write - a classic time-of-check-to-time-of-use window. The code handles it explicitly:

go 
// pkg/registry/core/service/ipallocator/ipallocator.go:346
		// address is not present on the cache, try to allocate it
		err = a.createIPAddress(name, svc, "dynamic")
		// an error can happen if there is a TOCTOU race and the IP address
		// was allocated by another instance, in that case, swallow the error
		// and try with the next IP address, but abort on other errors.
		// Ref: https://issues.k8s.io/135333
		if err != nil {
			if errors.Is(err, ErrAllocated) {
				klog.Infof("mid-air collision trying to allocate IP %s that already exists, retrying ...", name)
				continue
			}
			klog.Infof("can not create IPAddress %s: %v", name, err)
			return nil, err
		}

ErrAllocated is what createIPAddress returns when the API server answers AlreadyExists - another apiserver replica (or another allocator instance) got there first. Swallowing it and continuing the scan is correct: the address really is taken, and the loop simply moves to the next candidate.

The scan itself is a linear walk over the range with a cache lookup per candidate, and the source is honest that this could be better:

go 
// pkg/registry/core/service/ipallocator/ipallocator.go:326
// allocateFromRange allocates an empty IP address from the range of
// IPs between the first and last address (both included), starting
// from the start address.
// TODO: this is a linear search, it can be optimized.
func (a *Allocator) allocateFromRange(iterator func() netip.Addr, svc *api.Service) (net.IP, error) {

The edges of the range

Two addresses are never allocatable, and both allocators agree on which:

go 
// pkg/registry/core/service/ipallocator/ipallocator.go:563
func hostsPerNetwork(subnet *net.IPNet) uint64 {
	ones, bits := subnet.Mask.Size()
	// this checks that we are not overflowing an int64
	if bits-ones >= 64 {
		return math.MaxUint64
	}
	max := uint64(1) << uint(bits-ones)
	// Don't use the network's ".0" address,
	if max == 0 {
		return 0
	}
	max--
	if netutils.IsIPv4CIDR(subnet) {
		// Don't use the IPv4 network's broadcast address
		if max == 0 {
			return 0
		}
		max--
	}
	return max
}

IPv4 loses two addresses (network .0 and broadcast .255), IPv6 loses one (the all-zeros address, since IPv6 has no broadcast). The legacy bitmap allocator does the same thing with two explicit max-- calls, and adds the detail that the network address is bumped by one rather than merely excluded (pkg/registry/core/service/ipallocator/bitmap.go:81).

go 
// pkg/registry/core/service/ipallocator/bitmap.go:81
	// Don't use the network's ".0" address, but don't just Allocate() it - we
	// don't ever want to be able to release it.
	base.Add(base, big.NewInt(1))
	max--

Trade-offs

What randomisation buys. ClusterIPs that do not form an arithmetic progression, so datapaths that hash on them get a uniform bucket distribution. It also removes a class of information leak: with sequential allocation, the creation order of services is recoverable from their ClusterIPs.

What it costs.

  • A linear scan per allocation. allocateFromRange walks candidates until it finds one that is free, and the legacy allocator does the same over its bitmap. The TODO in the source acknowledges it.
  • Worse locality for humans. kubectl get svc -o wide no longer shows services in creation order, and there is no way to tell which ClusterIP came first.
  • Two allocators with different ceilings. The legacy one caps IPv6 at 65536 entries; the new one requires a /64 or longer but has no practical upper bound. Which one you get depends on whether the cluster uses ServiceCIDR objects and IPAddress objects.
  • Randomness is per allocator instance, not per cluster. With multiple service CIDRs, the MetaAllocator walks them in map order and does not weight by capacity - there is an explicit TODO about it:
go 
// pkg/registry/core/service/ipallocator/cidrallocator.go:351
	// TODO(aojea) add strategy to return a random allocator but
	// taking into consideration the number of addresses of each allocator.
	// Per example, if we have allocator A and B with 256 and 1024 possible
	// addresses each, the chances to get B has to be 4 times the chances to
	// get A so we can spread the load of IPs randomly.
	// However, we need to validate the best strategy before going to Beta.

Wrapping up

The one thing to remember: both ClusterIP allocators start from a random offset and scan forward, and both split the service CIDR with calculateRangeOffset - min(max(16, cidrSize/16), 256) - so dynamic allocation lives in the upper subrange and the lower 256 addresses are left for statically requested IPs. The legacy allocator caps IPv6 at 65536 entries; the IPAddress allocator requires a /64 or longer.

The part people get wrong: assuming clusterIP: None and manually picked IPs play by the same rules as dynamically allocated ones. The subrange split is a soft reservation in the new allocator - a statically requested IP is accepted from anywhere inside the CIDR, and the lower subrange is kept clear only because dynamic allocation never picks from it.

What to go do about it: check what your cluster is actually using with kubectl get servicecidr and kubectl get ipaddress - if the IPAddress objects exist, you are on the new allocator; if they do not, you are on the legacy bitmap one, which is the one with the 65536-entry IPv6 ceiling. To see the split in your own CIDR, compute min(max(16, cidrSize/16), 256) for your serviceSubnet and check that the first dynamically allocated ClusterIP is above that boundary. And if you run Cilium or another eBPF datapath, watch the per-service bucket counts in the datapath’s own metrics - the whole point of the randomisation is that those counts should be flat rather than skewed towards the low ClusterIPs.

KubernetesInternalsNetworking