Using eBPF to load-balance traffic across UDP sockets with Go

Vincent Bernat

Akvo­rado col­lects sFlow and IPFIX flows over UDP. Be­cause UDP does not re­trans­mit lost pack­ets, it needs to process them quickly. Akvo­rado runs sev­eral work­ers lis­ten­ing to the same port. The ker­nel should load-bal­ance re­ceived pack­ets fairly be­tween these work­ers. How­ever, this does not work as ex­pected. A cou­ple of work­ers ex­hibit high packet loss:

$ curl -s 127.0.0.1:8080/api/v0/inlet/metrics \
> | sed -n s/akvorado_inlet_flow_input_udp_in_dropped//p
packets_total{listener="0.0.0.0:2055",worker="0"} 0
packets_total{listener="0.0.0.0:2055",worker="1"} 0
packets_total{listener="0.0.0.0:2055",worker="2"} 0
packets_total{listener="0.0.0.0:2055",worker="3"} 1.614933572278264e+15
packets_total{listener="0.0.0.0:2055",worker="4"} 0
packets_total{listener="0.0.0.0:2055",worker="5"} 0
packets_total{listener="0.0.0.0:2055",worker="6"} 9.59964121598348e+14
packets_total{listener="0.0.0.0:2055",worker="7"} 0

eBPF can help by im­ple­ment­ing an al­ter­nate bal­anc­ing al­gorithm. 🐝

Options for load-balancing#

There are three meth­ods to load-bal­ance UDP pack­ets across workers:

  1. One worker re­ceives the pack­ets and dis­patches them to the other workers.
  2. All work­ers share the same socket.
  3. Each worker has its own socket, lis­ten­ing to the same port, with the SO_​REUSEPORT socket option.

SO_​REUSEPORT option#

Tom Hebert added the SO_​REUSEPORT socket op­tion in Linux 3.9. The cover let­ter for his patch se­ries ex­plains why this new op­tion is bet­ter than the two ex­ist­ing ones from a per­for­mance point of view:

SO_​REUSEPORT al­lows mul­ti­ple lis­tener sock­ets to be bound to the same port. […] Re­ceived pack­ets are dis­trib­uted to mul­ti­ple sock­ets bound to the same port us­ing a 4-tu­ple hash.

The mo­ti­vat­ing case for SO_​RESUSEPORT in TCP would be some­thing like a web server bind­ing to port 80 run­ning with mul­ti­ple threads, where each thread might have it’s own lis­tener socket. This could be done as an al­ter­na­tive to other models:

  1. have one lis­tener thread which dis­patches com­pleted con­nec­tions to workers, or
  2. ac­cept on a sin­gle lis­tener socket from mul­ti­ple threads.

In case #1, the lis­tener thread can eas­ily be­come the bot­tle­neck with high con­nec­tion turn-over rate. In case #2, the pro­por­tion of con­nec­tions ac­cepted per thread tends to be un­even un­der high con­nec­tion load. […] We have seen the dis­pro­por­tion to be as high as 3:1 ra­tio be­tween thread ac­cept­ing most con­nec­tions and the one ac­cept­ing the fewest. With SO_​REUSEPORT the dis­tri­bu­tion is uniform.

The mo­ti­vat­ing case for SO_​REUSEPORT in UDP would be some­thing like a DNS server. An al­ter­na­tive would be to re­ceive on the same socket from mul­ti­ple threads. As in the case of TCP, the load across these threads tends to be dis­pro­por­tion­ate and we also see a lot of con­tec­tion on the socket lock.

Akvo­rado uses the SO_​REUSEPORT op­tion to dis­patch the pack­ets across the work­ers. How­ever, be­cause the dis­tri­bu­tion uses a 4-tu­ple hash, a sin­gle socket han­dles all the flows from one exporter.

SO_​ATTACH_​REUSEPORT_​EBPF option#

In Linux 4.5, Craig Gallek added the SO_​ATTACH_​REUSEPORT_​EBPF op­tion to at­tach an eBPF pro­gram to se­lect the tar­get UDP socket. In Linux 4.6, he ex­tended it to sup­port TCP. The socket(7) man­ual page doc­u­ments this mechanism:1

The BPF pro­gram must re­turn an in­dex be­tween 0 and N-1 rep­re­sent­ing the socket which should re­ceive the packet (where N is the num­ber of sock­ets in the group). If the BPF pro­gram re­turns an in­valid in­dex, socket se­lec­tion will fall back to the plain SO_​REUSEPORT mechanism.

In Linux 4.19, Mar­tin KaFai Lau added the BPF_​PROG_​TYPE_​SK_​REUSEPORT pro­gram type. Such an eBPF pro­gram se­lects the socket from a BPF_​MAP_​TYPE_​REUSEPORT_​ARRAY map in­stead. This new ap­proach is more re­li­able when switch­ing tar­get sock­ets from one in­stance to an­other—for ex­am­ple, when up­grad­ing, a new in­stance can add its sock­ets and re­move the old ones.

Load-balancing with eBPF and Go#

Al­ter­ing the load-bal­anc­ing al­go­rithm for a group of sock­ets re­quires two steps:

  1. write and com­pile an eBPF pro­gram in C,2 and
  2. load it and at­tach it in Go.

eBPF program in C#

A sim­ple load-bal­anc­ing al­go­rithm is to ran­domly choose the des­ti­na­tion socket. The ker­nel pro­vides the bpf_​get_​prandom_​u32() helper func­tion to get a pseudo-ran­dom number.

volatile const __u32 num_sockets; // ❶

struct {
    __uint(type, BPF_MAP_TYPE_REUSEPORT_SOCKARRAY);
    __type(key, __u32);
    __type(value, __u64);
    __uint(max_entries, 256);
} socket_map SEC(".maps"); // ❷

SEC("sk_reuseport")
int reuseport_balance_prog(struct sk_reuseport_md *reuse_md)
{
    __u32 index = bpf_get_prandom_u32() % num_sockets; // ❸
    bpf_sk_select_reuseport(reuse_md, &socket_map, &index, 0); // ❹
    return SK_PASS; // ❺
}

char _license[] SEC("license") = "GPL";

In ❶, we de­clare a volatile con­stant for the num­ber of sock­ets in the group. We will ini­tial­ize this con­stant be­fore load­ing the eBPF pro­gram into the ker­nel. In ❷, we de­fine the socket map. We will pop­u­late it with the socket file de­scrip­tors. In ❸, we ran­domly se­lect the in­dex of the tar­get socket.3 In ❹, we in­voke the bpf_​sk_​select_​reuseport() helper to record our de­ci­sion. Fi­nally, in ❺, we ac­cept the packet.

Header files#

If you com­pile the C source with clang, you get er­rors due to miss­ing head­ers. The rec­om­mended way to solve this is to gen­er­ate a vmlinux.h file with bpftool:

$ bpftool btf dump file /sys/kernel/btf/vmlinux format c > vmlinux.h

Then, in­clude the fol­low­ing headers:4

#include "vmlinux.h"
#include <bpf/bpf_helpers.h>

For my 6.17 ker­nel, the gen­er­ated vmlinux.h is quite big: 2.7 MiB. More­over, bpf/​bpf_​helpers.h is shipped with libbpf. This adds an­other de­pen­dency for users. As the eBPF pro­gram is quite small, I pre­fer to put the strict min­i­mum in vmlinux.h by cherry-pick­ing the def­i­ni­tions I need.

Compilation#

The eBPF Li­brary for Go ships bpf2go, a tool to com­pile eBPF pro­grams and to gen­er­ate some scaf­fold­ing code. We cre­ate a gen.go file with the fol­low­ing content:

package main

//go:generate go tool bpf2go -tags linux reuseport reuseport_kern.c

Af­ter run­ning go generate ./..., we can in­spect the re­sult­ing ob­jects with readelf and llvm-objdump:

$ readelf -S reuseport_bpfeb.o
There are 14 section headers, starting at offset 0x840:
  [Nr] Name              Type             Address           Offset
[…]
  [ 3] sk_reuseport      PROGBITS         0000000000000000  00000040
  [ 6] .maps             PROGBITS         0000000000000000  000000c8
  [ 7] license           PROGBITS         0000000000000000  000000e8
[…]
$ llvm-objdump -S reuseport_bpfeb.o
reuseport_bpfeb.o:  file format elf64-bpf
Disassembly of section sk_reuseport:
0000000000000000 <reuseport_balance_prog>:
; {
       0:   bf 61 00 00 00 00 00 00     r6 = r1
;     __u32 index = bpf_get_prandom_u32() % num_sockets;
       1:   85 00 00 00 00 00 00 07     call 0x7
[…]

Usage from Go#

Let’s set up 10 work­ers lis­ten­ing to the same port.5 Each socket en­ables the SO_​REUSEPORT op­tion be­fore binding:6

var (
    err error
    fds []uintptr
    conns []*net.UDPConn
)
workers := 10
listenAddr := "127.0.0.1:0"
listenConfig := net.ListenConfig{
    Control: func(_, _ string, c syscall.RawConn) error {
        c.Control(func(fd uintptr) {
            err = unix.SetsockoptInt(int(fd), unix.SOL_SOCKET, unix.SO_REUSEPORT, 1)
            fds = append(fds, fd)
        })
        return err
    },
}
for range workers {
    pconn, err := listenConfig.ListenPacket(t.Context(), "udp", listenAddr)
    if err != nil {
        t.Fatalf("ListenPacket() error:\n%+v", err)
    }
    udpConn := pconn.(*net.UDPConn)
    listenAddr = udpConn.LocalAddr().String()
    conns = append(conns, udpConn)
}

The sec­ond step is to load the eBPF pro­gram, ini­tial­ize the num_​sockets vari­able, pop­u­late the socket map, and at­tach the pro­gram to the first socket.7

// Load the eBPF collection.
spec, err := loadReuseport()
if err != nil {
    t.Fatalf("loadVariables() error:\n%+v", err)
}

// Set "num_sockets" global variable to the number of file descriptors we will register
if err := spec.Variables["num_sockets"].Set(uint32(len(fds))); err != nil {
    t.Fatalf("NumSockets.Set() error:\n%+v", err)
}

// Load the map and the program into the kernel.
var objs reuseportObjects
if err := spec.LoadAndAssign(&objs, nil); err != nil {
    t.Fatalf("loadReuseportObjects() error:\n%+v", err)
}
t.Cleanup(func() { objs.Close() })

// Assign the file descriptors to the socket map.
for worker, fd := range fds {
    if err := objs.reuseportMaps.SocketMap.Put(uint32(worker), uint64(fd)); err != nil {
        t.Fatalf("SocketMap.Put() error:\n%+v", err)
    }
}

// Attach the eBPF program to the first socket.
socketFD := int(fds[0])
progFD := objs.reuseportPrograms.ReuseportBalanceProg.FD()
if err := unix.SetsockoptInt(socketFD, unix.SOL_SOCKET, unix.SO_ATTACH_REUSEPORT_EBPF, progFD); err != nil {
    t.Fatalf("SetsockoptInt() error:\n%+v", err)
}

We are now ready to process in­com­ing pack­ets. Each worker is a gor­ou­tine in­cre­ment­ing a counter for each re­ceived packet:8

var wg sync.WaitGroup
receivedPackets := make([]int, workers)
for worker := range workers {
    conn := conns[worker]
    packets := &receivedPackets[worker]
    wg.Go(func() {
        payload := make([]byte, 9000)
        for {
            if _, err := conn.Read(payload); err != nil {
                if errors.Is(err, net.ErrClosed) {
                    return
                }
                t.Logf("Read() error:\n%+v", err)
            }
            *packets++
        }
    })
}

Let’s send 1000 packets:

sentPackets := 1000
conn, err := net.Dial("udp", conns[0].LocalAddr().String())
if err != nil {
    t.Fatalf("Dial() error:\n%+v", err)
}
defer conn.Close()
for range sentPackets {
    if _, err := conn.Write([]byte("hello world!")); err != nil {
        t.Fatalf("Write() error:\n%+v", err)
    }
}

If we print the con­tent of the receivedPackets ar­ray, we can check the bal­anc­ing works as ex­pected, with each worker get­ting about 100 packets:

=== RUN   TestUDPWorkerBalancing
    balancing_test.go:84: receivedPackets[0] = 107
    balancing_test.go:84: receivedPackets[1] = 92
    balancing_test.go:84: receivedPackets[2] = 99
    balancing_test.go:84: receivedPackets[3] = 105
    balancing_test.go:84: receivedPackets[4] = 107
    balancing_test.go:84: receivedPackets[5] = 96
    balancing_test.go:84: receivedPackets[6] = 102
    balancing_test.go:84: receivedPackets[7] = 105
    balancing_test.go:84: receivedPackets[8] = 99
    balancing_test.go:84: receivedPackets[9] = 88

    balancing_test.go:91: receivedPackets = 1000
    balancing_test.go:92: sentPackets     = 1000

Graceful restart#

You can also use SO_​ATTACH_​REUSEPORT_​EBPF to grace­fully restart an ap­pli­ca­tion. A new in­stance of the ap­pli­ca­tion binds to the same ad­dress and pre­pares its own ver­sion of the socket map. Once it at­taches the eBPF pro­gram to the first socket, the ker­nel steers in­com­ing pack­ets to this new in­stance. The old in­stance needs to drain the al­ready-re­ceived pack­ets be­fore shut­ting down.

To check we are not los­ing any packet, we spawn a gor­ou­tine to send as many pack­ets as possible:

sentPackets := 0
notSentPackets := 0
done := make(chan bool)
conn, err := net.Dial("udp", conns1[0].LocalAddr().String())
if err != nil {
    t.Fatalf("Dial() error:\n%+v", err)
}
defer conn.Close()
go func() {
    for {
        if _, err := conn.Write([]byte("hello world!")); err != nil {
            notSentPackets++
        } else {
            sentPackets++
        }
        select {
        case <-done:
            return
        default:
        }
    }
}()

Then, while the Go rou­tine runs, we start the sec­ond set of work­ers. Once they are run­ning, they start re­ceiv­ing pack­ets. If we grace­fully stop the ini­tial set of work­ers, not a sin­gle packet is lost!9

=== RUN   TestGracefulRestart
    graceful_test.go:135: receivedPackets1[0] = 165
    graceful_test.go:135: receivedPackets1[1] = 195
    graceful_test.go:135: receivedPackets1[2] = 194
    graceful_test.go:135: receivedPackets1[3] = 190
    graceful_test.go:135: receivedPackets1[4] = 213
    graceful_test.go:135: receivedPackets1[5] = 187
    graceful_test.go:135: receivedPackets1[6] = 170
    graceful_test.go:135: receivedPackets1[7] = 190
    graceful_test.go:135: receivedPackets1[8] = 194
    graceful_test.go:135: receivedPackets1[9] = 155

    graceful_test.go:139: receivedPackets2[0] = 1631
    graceful_test.go:139: receivedPackets2[1] = 1582
    graceful_test.go:139: receivedPackets2[2] = 1594
    graceful_test.go:139: receivedPackets2[3] = 1611
    graceful_test.go:139: receivedPackets2[4] = 1571
    graceful_test.go:139: receivedPackets2[5] = 1660
    graceful_test.go:139: receivedPackets2[6] = 1587
    graceful_test.go:139: receivedPackets2[7] = 1605
    graceful_test.go:139: receivedPackets2[8] = 1631
    graceful_test.go:139: receivedPackets2[9] = 1689

    graceful_test.go:147: receivedPackets = 18014
    graceful_test.go:148: sentPackets     = 18014

Un­for­tu­nately, grace­fully shut­ting down a UDP socket is not triv­ial in Go.10 Pre­vi­ously, we were ter­mi­nat­ing work­ers by clos­ing their sock­ets. How­ever, if we close them too soon, the ap­pli­ca­tion loses pack­ets that were as­signed to them but not yet pro­cessed. Be­fore stop­ping, a worker needs to call conn.​Read() un­til there are no more pack­ets. A so­lu­tion is to set a dead­line for conn.​Read() and check if we should stop the gor­ou­tine when the dead­line is exceeded:

payload := make([]byte, 9000)
for {
    conn.SetReadDeadline(time.Now().Add(50 * time.Millisecond))
    if _, err := conn.Read(payload); err != nil {
        if errors.Is(err, os.ErrDeadlineExceeded) {
            select {
            case <-done:
                return
            default:
                continue
            }
        }
        t.Logf("Read() error:\n%+v", err)
    }
    *packets++
}

With TCP, this as­pect is sim­pler: af­ter en­abling the net.​ipv4.​tcp_​migrate_​req sysctl, the ker­nel au­to­mat­i­cally mi­grates wait­ing con­nec­tions to a ran­dom socket in the same group. Al­ter­na­tively, eBPF can also con­trol this mi­gra­tion. Both fea­tures are avail­able since Linux 5.14.

Addendum#

Af­ter im­ple­ment­ing this strat­egy in Akvo­rado, all work­ers now drop packets! 😱

$ curl -s 127.0.0.1:8080/api/v0/inlet/metrics \
> | sed -n s/akvorado_inlet_flow_input_udp_in_dropped//p
packets_total{listener="0.0.0.0:2055",worker="0"} 838673
packets_total{listener="0.0.0.0:2055",worker="1"} 843675
packets_total{listener="0.0.0.0:2055",worker="2"} 837922
packets_total{listener="0.0.0.0:2055",worker="3"} 841443
packets_total{listener="0.0.0.0:2055",worker="4"} 840668
packets_total{listener="0.0.0.0:2055",worker="5"} 850274
packets_total{listener="0.0.0.0:2055",worker="6"} 835488
packets_total{listener="0.0.0.0:2055",worker="7"} 834479

The root cause is the de­fault limit of 32 records for Kafka batch sizes. This limit is too low be­cause the bro­kers have a large over­head when han­dling each batch: they need to en­sure they per­sist cor­rectly be­fore ac­knowl­edg­ing them. In­creas­ing the limit to 4096 records fixes this issue.

While load-bal­anc­ing in­com­ing flows with eBPF re­mains use­ful, it did not solve the main is­sue. At least the even dis­tri­bu­tion of dropped pack­ets helped iden­tify the real bot­tleneck. 😅