Opensource internals

The 1/n Lottery: How kube-proxy Load-Balances Without a Single Line of State

11 min read Jay Hubbert

The iptables proxier splits traffic with a cascade of probabilistic rules: rule i fires with probability 1/(n-i) and the last matches unconditionally, giving an exact uniform split.

TL;DR: The iptables proxier does not keep a counter, a hash table or a round-robin index per service. It writes one iptables rule per endpoint, and rule i carries -m statistic --mode random --probability 1/(n-i); the last rule has no probability at all and matches unconditionally. A connection therefore reaches endpoint i with probability 1/n, exactly, and the kernel’s random number generator makes the choice — once per connection, not once per packet. No state, no lock, no coordination.

Every other load balancer in the data centre keeps state: a connection table, a round-robin cursor, a least-connections counter, a consistent-hash ring. kube-proxy’s iptables mode keeps none of it, and yet the split across endpoints of a Service is exactly uniform. The trick is that the state lives in the kernel’s conntrack table, and the algorithm is expressed as a cascade of probabilistic matches rather than as a lookup.

This is worth understanding properly, because the iptables mode is still the default on most clusters and its failure modes are unusual.

One rule per endpoint

The proxier builds a chain per service port (KUBE-SVC-XXXX) and a chain per endpoint (KUBE-SEP-XXXX), and fills the service chain with one rule per endpoint:

go 
// pkg/proxy/iptables/proxier.go:1430-1474
func (proxier *Proxier) writeServiceToEndpointRules(natRules proxyutil.LineBuffer, svcPortNameString string, svcInfo proxy.ServicePort, svcChain utiliptables.Chain, endpoints []proxy.Endpoint, args []string) {
	// First write session affinity rules, if applicable.
	if svcInfo.SessionAffinityType() == v1.ServiceAffinityClientIP {
		for _, ep := range endpoints {
			epInfo, ok := ep.(*endpointInfo)
			if !ok {
				continue
			}
			comment := fmt.Sprintf(`"%s -> %s"`, svcPortNameString, epInfo.String())

			args = append(args[:0],
				"-A", string(svcChain),
			)
			args = proxier.appendServiceCommentLocked(args, comment)
			args = append(args,
				"-m", "recent", "--name", string(epInfo.ChainName),
				"--rcheck", "--seconds", strconv.Itoa(svcInfo.StickyMaxAgeSeconds()), "--reap",
				"-j", string(epInfo.ChainName),
			)
			natRules.Write(args)
		}
	}

	// Now write loadbalancing rules.
	numEndpoints := len(endpoints)
	for i, ep := range endpoints {
		epInfo, ok := ep.(*endpointInfo)
		if !ok {
			continue
		}
		comment := fmt.Sprintf(`"%s -> %s"`, svcPortNameString, epInfo.String())

		args = append(args[:0], "-A", string(svcChain))
		args = proxier.appendServiceCommentLocked(args, comment)
		if i < (numEndpoints - 1) {
			// Each rule is a probabilistic match.
			args = append(args,
				"-m", "statistic",
				"--mode", "random",
				"--probability", proxier.probability(numEndpoints-i))
		}
		// The final (or only if n == 1) rule is a guaranteed match.
		natRules.Write(args, "-j", string(epInfo.ChainName))
	}
}

The comment // The final (or only if n == 1) rule is a guaranteed match. is the crux. Every rule except the last is guarded by a probability; the last one always fires. The probability attached to rule i is 1/(n-i) where n is the endpoint count and i is the rule index.

Each endpoint chain ends in a DNAT:

go 
// pkg/proxy/iptables/proxier.go:1229-1242
			args = append(args[:0], "-A", string(endpointChain))
			args = proxier.appendServiceCommentLocked(args, svcPortNameString)
			// Handle traffic that loops back to the originator with SNAT.
			natRules.Write(
				args,
				"-s", epInfo.IP(),
				"-j", string(kubeMarkMasqChain))
			// Update client-affinity lists.
			if svcInfo.SessionAffinityType() == v1.ServiceAffinityClientIP {
				args = append(args, "-m", "recent", "--name", string(endpointChain), "--set")
			}
			// DNAT to final destination.
			args = append(args, "-m", protocol, "-p", protocol, "-j", "DNAT", "--to-destination", epInfo.String())
			natRules.Write(args)

The cascade computes exactly 1/n

Walk the three-endpoint case. Rule 0 matches with probability 1/3. Rule 1 matches with probability 1/2 — but only if rule 0 did not match, which happens with probability 2/3. Rule 2 always matches, but only if the first two did not, which happens with probability (2/3) x (1/2) = 1/3.

  • P(endpoint 0) = 1/3
  • P(endpoint 1) = (2/3) x (1/2) = 1/3
  • P(endpoint 2) = (2/3) x (1/2) = 1/3

Uniform, exactly, with no floating-point accumulation error beyond the printed precision. For four endpoints the cascade is 1/4, 1/3, 1/2, unconditional, and the products telescope the same way: 1/4, (3/4)(1/3) = 1/4, (3/4)(2/3)(1/2) = 1/4, and the remainder is 1 - 3/4 = 1/4.

This is why the last rule has no probability attached. If it did — say the chain ended with 1/(n-(n-1)) = 1/1 — the kernel’s statistic match would still be consulted, but there is no point: the probability of reaching the last rule is already exactly 1/n, so the rule matches everything that gets to it.

The distribution is uniform per connection, not per packet, and not per byte. A client that opens 1000 connections gets roughly 333 to each endpoint, with binomial variance. A client that opens one connection and streams a gigabyte sends all of it to one endpoint. This is a per-connection load balancer and nothing more.

Precomputing the probability strings

The probabilities themselves are computed once and cached, because fmt.Sprintf is expensive and the proxier calls it for every endpoint of every service on every sync:

go 
// pkg/proxy/iptables/proxier.go:390-410
func computeProbability(n int) string {
	return fmt.Sprintf("%0.10f", 1.0/float64(n))
}

// This assumes proxier.mu is held
func (proxier *Proxier) precomputeProbabilities(numberOfPrecomputed int) {
	if len(proxier.precomputedProbabilities) == 0 {
		proxier.precomputedProbabilities = append(proxier.precomputedProbabilities, "<bad value>")
	}
	for i := len(proxier.precomputedProbabilities); i <= numberOfPrecomputed; i++ {
		proxier.precomputedProbabilities = append(proxier.precomputedProbabilities, computeProbability(i))
	}
}

// This assumes proxier.mu is held
func (proxier *Proxier) probability(n int) string {
	if n >= len(proxier.precomputedProbabilities) {
		proxier.precomputeProbabilities(n)
	}
	return proxier.precomputedProbabilities[n]
}

The comment on the field explains why:

go 
// pkg/proxy/iptables/proxier.go:167-170
	// Since converting probabilities (floats) to strings is expensive
	// and we are using only probabilities in the format of 1/n, we are
	// precomputing some number of those and cache for future reuse.
	precomputedProbabilities []string

The slice is pre-sized for 1000 entries and index 0 is a sentinel:

go 
// pkg/proxy/iptables/proxier.go:283
		precomputedProbabilities: make([]string, 0, 1001),

"%0.10f" gives ten decimal places: 1/3 is 0.3333333333, which is slightly less than the true 1/3. The bias is on the order of 1e-11 per rule and utterly irrelevant next to the kernel’s own 32-bit random value. But it does mean the split is “uniform to ten decimal places”, not exactly uniform — worth knowing if you are trying to explain a 0.0001% discrepancy in a traffic report.

The conntrack gate

The whole cascade runs in the kernel’s NAT table, and the kernel only consults NAT for the first packet of a connection. Subsequent packets of the same flow follow the conntrack entry and skip the NAT chains entirely. That single kernel behaviour is what makes this a per-connection load balancer without a single line of kube-proxy state.

The filter table is where the proxier has to be explicit about it. The jump chains from the built-in INPUT, FORWARD and OUTPUT chains into the kube-proxy chains are gated on the connection being new:

go 
// pkg/proxy/iptables/proxier.go:364-377
var iptablesJumpChains = []iptablesJumpChain{
	{utiliptables.TableFilter, kubeExternalServicesChain, utiliptables.ChainInput, "kubernetes externally-visible service portals", []string{"-m", "conntrack", "--ctstate", "NEW"}},
	{utiliptables.TableFilter, kubeExternalServicesChain, utiliptables.ChainForward, "kubernetes externally-visible service portals", []string{"-m", "conntrack", "--ctstate", "NEW"}},
	{utiliptables.TableFilter, kubeNodePortsChain, utiliptables.ChainInput, "kubernetes health check service ports", nil},
	{utiliptables.TableFilter, kubeServicesChain, utiliptables.ChainForward, "kubernetes service portals", []string{"-m", "conntrack", "--ctstate", "NEW"}},
	{utiliptables.TableFilter, kubeServicesChain, utiliptables.ChainOutput, "kubernetes service portals", []string{"-m", "conntrack", "--ctstate", "NEW"}},
	{utiliptables.TableFilter, kubeForwardChain, utiliptables.ChainForward, "kubernetes forwarding rules", nil},
	{utiliptables.TableFilter, kubeProxyFirewallChain, utiliptables.ChainInput, "kubernetes load balancer firewall", []string{"-m", "conntrack", "--ctstate", "NEW"}},
	{utiliptables.TableFilter, kubeProxyFirewallChain, utiliptables.ChainOutput, "kubernetes load balancer firewall", []string{"-m", "conntrack", "--ctstate", "NEW"}},
	{utiliptables.TableFilter, kubeProxyFirewallChain, utiliptables.ChainForward, "kubernetes load balancer firewall", []string{"-m", "conntrack", "--ctstate", "NEW"}},
	{utiliptables.TableNAT, kubeServicesChain, utiliptables.ChainOutput, "kubernetes service portals", nil},
	{utiliptables.TableNAT, kubeServicesChain, utiliptables.ChainPrerouting, "kubernetes service portals", nil},
	{utiliptables.TableNAT, kubePostroutingChain, utiliptables.ChainPostrouting, "kubernetes postrouting rules", nil},
}

The pattern is exact: every filter-table jump carries -m conntrack --ctstate NEW, and every NAT-table jump does not. The NAT table does not need the gate because conntrack already restricts NAT to the first packet of a flow — the kernel would not re-evaluate the statistic match for subsequent packets anyway, so the gate would be redundant there. The filter table is traversed by every packet, so the gate is load-bearing: without it, the KUBE-FW- and KUBE-SERVICES accept rules would be evaluated on every packet of every connection for no reason.

The two filter-table jumps without the gate are deliberate. KUBE-NODEPORTS jumping into INPUT is the health-check path, and KUBE-FORWARD into FORWARD handles the masquerade mark — neither is per-connection work.

Session affinity rides on the same chains

If the Service asks for sessionAffinity: ClientIP, the proxier prepends rules that use the recent match to pin a client to an endpoint. The structure above is the real code, but the shape is the important part: for each endpoint, a rule that checks whether this client’s IP was recently seen for that endpoint chain, and if so jumps straight to it.

The recent module keeps a small per-IP list per named set, keyed by the endpoint chain name, with a TTL equal to svcInfo.StickyMaxAgeSeconds(). The --reap flag means expired entries are cleaned up as the list is traversed. The affinity rules come before the probabilistic rules, so a pinned client never takes a chance on the lottery.

INVALID state is dropped

One more rule in the filter table, and it is not about balancing:

go 
// pkg/proxy/iptables/proxier.go:1316-1335
	// Drop the packets in INVALID state, which would potentially cause
	// unexpected connection reset if nf_conntrack_tcp_be_liberal is not set.
	// Ref: https://github.com/kubernetes/kubernetes/issues/74839
	// Ref: https://github.com/kubernetes/kubernetes/issues/117924
	if !proxier.conntrackTCPLiberal {
		rule := []string{
			"-A", string(kubeForwardChain),
			"-m", "conntrack",
			"--ctstate", "INVALID",
		}
		if proxier.nfAcctCounters[metrics.IPTablesCTStateInvalidDroppedNFAcctCounter] {
			rule = append(rule,
				"-m", "nfacct", "--nfacct-name", metrics.IPTablesCTStateInvalidDroppedNFAcctCounter,
			)
		}
		rule = append(rule,
			"-j", "DROP",
		)
		proxier.filterRules.Write(rule)
	}

A packet in the INVALID conntrack state is one the kernel could not classify — a stray ACK, a malformed handshake. If it reached the service chain it would pick an endpoint at random and get a connection reset, which looks exactly like the service flapping. Dropping it in KUBE-FORWARD before it ever reaches the lottery is what makes the failure mode legible. The proxier reads the nf_conntrack_tcp_be_liberal sysctl at startup and only installs the rule when the kernel is not in liberal mode:

go 
// pkg/proxy/iptables/proxier.go:237-244
	// Be conservative in what you do, be liberal in what you accept from others.
	// If it's non-zero, we mark only out of window RST segments as INVALID.
	// Ref: https://docs.kernel.org/networking/nf_conntrack-sysctl.html
	conntrackTCPLiberal := false
	if val, err := sysctl.GetSysctl(sysctlNFConntrackTCPBeLiberal); err == nil && val != 0 {
		conntrackTCPLiberal = true
		logger.Info("nf_conntrack_tcp_be_liberal set, not installing DROP rules for INVALID packets")
	}

Note the nfacct counter: when enabled, the drops are counted per node so you can see the rate of INVALID packets. That is the metric to look at if clients are reporting intermittent connection resets.

What it buys and what it costs

The iptables mode’s data path is remarkable for what it does not have:

  • No per-service state. Adding a Service adds rules. Removing one removes rules. There is no runtime cursor, no counter, no map.
  • No lock. The kernel evaluates the rules; the proxier is not in the path after iptables-restore.
  • No synchronization between nodes. Every node’s kernel picks independently, which is exactly what you want for spread.
  • O(1) state per service. The rules themselves are the state.

The costs are equally clear:

  • Unevenness at low connection counts. With 3 endpoints and 10 connections, the expected split is 3.3/3.3/3.3 and the actual split might be 6/3/1. Long-lived connections are pinned for their whole life, so the imbalance persists.
  • Rules scale with services times endpoints. A cluster with 5000 Services and 10 endpoints each has 50 000 endpoint chains. iptables-restore on that takes seconds and the kernel’s rule lookup gets slow — this is the motivation for the nftables and IPVS modes.
  • No health weighting. Endpoints are in or out of the Service; there is no gradual degradation based on endpoint load.
  • The lottery is per connection. Long-lived, high-bandwidth connections get an uneven share of the bytes, not just of the connections.

Wrapping up

The one thing to remember: the split is exact and stateless because the probabilities telescope. Rule i fires with probability 1/(n-i), the last rule fires unconditionally, and the product of the surviving probabilities gives every endpoint exactly 1/n. The randomness comes from the kernel’s -m statistic --mode random match, and the “per connection” property comes from conntrack, not from kube-proxy.

The part people get wrong: “kube-proxy load-balances round-robin.” It does not, and it does not even do weighted random. It does probabilistic per-connection balancing, so a single client making one connection gets one endpoint, and a client making ten connections gets a random split. If you are chasing uneven traffic with a long-lived connection, the lottery already picked and you will not get a better answer by waiting.

What to go do about it: look at the rules themselves with iptables-save -t nat | grep KUBE-SVC- on any node and read the --probability values — they should be 1/n, 1/(n-1), … and the last rule should have no probability at all. If the last rule has one, or the values do not match the endpoint count, the rules are stale. Watch kube_proxy_sync_proxy_rules_duration_seconds and kube_proxy_sync_full_proxy_rules_duration_seconds for the rule-count cliff — a full sync re-runs iptables-restore over the entire rule set, and that is what gets slow with tens of thousands of endpoint chains. If it is what is hurting you, switch to the nftables mode (--proxy-mode=nftables) or IPVS. For the INVALID-drop path, the counter is a kernel nfacct counter named ct_state_invalid_dropped_pkts (see pkg/proxy/metrics/metrics.go:157), readable with nfacct -l or from /proc/net/nf_conntrack_acct — look at it if clients are seeing connection resets that look like endpoint flapping. And check net.netfilter.nf_conntrack_tcp_be_liberal: when it is set, kube-proxy logs nf_conntrack_tcp_be_liberal set, not installing DROP rules for INVALID packets and skips that rule entirely.

KubernetesInternalsNetworking