Implement a custom DNS Resolver for Gitaly

gRPC supports a built-in DNS resolver. This resolver works quite well
in most scenarios. It has some drawbacks:
- After the DNS is resolved for the first time, the resolver does not
refresh the list of addresses until the client connection triggers the
resolver actively. Client connection does so when it detects some of its
subchannels are unavailable permanently. It means as soon as the client
connection is stable, the client is not aware of new hosts added to
the cluster via DNS service discovery. This behavior leads to unexpected
stickiness and workload skew, especially after a failover.
- The support for SRV record is in a weird state. This type of record
is only supported when grpclb load balancing strategy is enabled. This
strategy is deprecated, unfortunately. Its behavior is also not as we
expected. In short-term, we would like to use round-robin strategy. In
longer term, we may have a custom strategy for Raft-based cluster. Thus,
SRV service discovery is crucial in the future.
- The resolver detects service config via TXT record if any. While this
option is convenient for a generic grpc setting, it does not make sense
for Gitaly. So, we should get rid of it.

This commit implements a custom DNS resolver. This resolver has some
major features:
- Resolve DNS service discovery via A records
- Periodically refresh the DNS (5 minutes by default)
- Update DNS state only if it detects real changes
- Support logging

Service discovery via SRV records is not supported in this version to
keep the backward compatibility with Ruby clients.

12 files changed, 1292 insertions, 0 deletions

diff --git a/NOTICE b/NOTICE
index 98f04798b..8fe111971 100644
--- a/NOTICE
+++ b/NOTICE
@@ -20705,6 +20705,39 @@ NOTICE - github.com/matttproud/golang_protobuf_extensions/pbutil
 Copyright 2012 Matt T. Proud (matt.proud@gmail.com)
 
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+LICENSE - github.com/miekg/dns
+Copyright (c) 2009 The Go Authors. All rights reserved.
+
+Redistribution and use in source and binary forms, with or without
+modification, are permitted provided that the following conditions are
+met:
+
+   * Redistributions of source code must retain the above copyright
+notice, this list of conditions and the following disclaimer.
+   * Redistributions in binary form must reproduce the above
+copyright notice, this list of conditions and the following disclaimer
+in the documentation and/or other materials provided with the
+distribution.
+   * Neither the name of Google Inc. nor the names of its
+contributors may be used to endorse or promote products derived from
+this software without specific prior written permission.
+
+THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+As this is fork of the official Go code the same license applies.
+Extensions of the original work are copyright (c) 2011 Miek Gieben
+
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 LICENSE - github.com/mitchellh/go-homedir
 The MIT License (MIT)
 
diff --git a/go.mod b/go.mod
index 694a6656e..7b512d181 100644
--- a/go.mod
+++ b/go.mod
@@ -27,6 +27,7 @@ require (
 	github.com/jackc/pgx/v4 v4.17.2
 	github.com/kelseyhightower/envconfig v1.4.0
 	github.com/libgit2/git2go/v34 v34.0.0
+	github.com/miekg/dns v1.1.50
 	github.com/olekukonko/tablewriter v0.0.5
 	github.com/opencontainers/runtime-spec v1.0.3-0.20210326190908-1c3f411f0417
 	github.com/opentracing/opentracing-go v1.2.0
@@ -180,9 +181,11 @@ require (
 	go.uber.org/atomic v1.10.0 // indirect
 	golang.org/x/crypto v0.3.0 // indirect
 	golang.org/x/exp v0.0.0-20221031165847-c99f073a8326 // indirect
+	golang.org/x/mod v0.6.0 // indirect
 	golang.org/x/net v0.4.0 // indirect
 	golang.org/x/oauth2 v0.2.0 // indirect
 	golang.org/x/text v0.5.0 // indirect
+	golang.org/x/tools v0.2.0 // indirect
 	golang.org/x/xerrors v0.0.0-20220907171357-04be3eba64a2 // indirect
 	gonum.org/v1/gonum v0.8.2 // indirect
 	google.golang.org/api v0.103.0 // indirect
diff --git a/go.sum b/go.sum
index dc5b5d0db..5797f64de 100644
--- a/go.sum
+++ b/go.sum
@@ -1569,6 +1569,7 @@ github.com/miekg/dns v1.0.14/go.mod h1:W1PPwlIAgtquWBMBEV9nkV9Cazfe8ScdGz/Lj7v3N
 github.com/miekg/dns v1.1.26/go.mod h1:bPDLeHnStXmXAq1m/Ch/hvfNHr14JKNPMBo3VZKjuso=
 github.com/miekg/dns v1.1.41/go.mod h1:p6aan82bvRIyn+zDIv9xYNUpwa73JcSh9BKwknJysuI=
 github.com/miekg/dns v1.1.48/go.mod h1:e3IlAVfNqAllflbibAZEWOXOQ+Ynzk/dDozDxY7XnME=
+github.com/miekg/dns v1.1.50 h1:DQUfb9uc6smULcREF09Uc+/Gd46YWqJd5DbpPE9xkcA=
 github.com/miekg/dns v1.1.50/go.mod h1:e3IlAVfNqAllflbibAZEWOXOQ+Ynzk/dDozDxY7XnME=
 github.com/miekg/pkcs11 v1.0.3/go.mod h1:XsNlhZGX73bx86s2hdc/FuaLm2CPZJemRLMA+WTFxgs=
 github.com/mistifyio/go-zfs v2.1.2-0.20190413222219-f784269be439+incompatible/go.mod h1:8AuVvqP/mXw1px98n46wfvcGfQ4ci2FwoAjKYxuo3Z4=
@@ -2212,6 +2213,7 @@ golang.org/x/mod v0.5.0/go.mod h1:5OXOZSfqPIIbmVBIIKWRFfZjPR0E5r58TLhUjH0a2Ro=
 golang.org/x/mod v0.5.1/go.mod h1:5OXOZSfqPIIbmVBIIKWRFfZjPR0E5r58TLhUjH0a2Ro=
 golang.org/x/mod v0.6.0-dev.0.20220106191415-9b9b3d81d5e3/go.mod h1:3p9vT2HGsQu2K1YbXdKPJLVgG5VJdoTa1poYQBtP1AY=
 golang.org/x/mod v0.6.0-dev.0.20220419223038-86c51ed26bb4/go.mod h1:jJ57K6gSWd91VN4djpZkiMVwK6gcyfeH4XE8wZrZaV4=
+golang.org/x/mod v0.6.0 h1:b9gGHsz9/HhJ3HF5DHQytPpuwocVTChQJK3AvoLRD5I=
 golang.org/x/mod v0.6.0/go.mod h1:4mET923SAdbXp2ki8ey+zGs1SLqsuM2Y0uvdZR/fUNI=
 golang.org/x/net v0.0.0-20180724234803-3673e40ba225/go.mod h1:mL1N/T3taQHkDXs73rZJwtUhF3w3ftmwwsq0BUmARs4=
 golang.org/x/net v0.0.0-20180826012351-8a410e7b638d/go.mod h1:mL1N/T3taQHkDXs73rZJwtUhF3w3ftmwwsq0BUmARs4=
diff --git a/internal/dnsresolver/builder.go b/internal/dnsresolver/builder.go
new file mode 100644
index 000000000..88a5bd763
--- /dev/null
+++ b/internal/dnsresolver/builder.go
@@ -0,0 +1,111 @@
+package dnsresolver
+
+import (
+	"context"
+	"strings"
+	"time"
+
+	"github.com/sirupsen/logrus"
+	"gitlab.com/gitlab-org/gitaly/v15/internal/backoff"
+	"gitlab.com/gitlab-org/gitaly/v15/internal/structerr"
+	"google.golang.org/grpc/resolver"
+)
+
+// Default DNS desc server port. This is a de-facto convention for both UDP and TCP.
+const defaultDNSNameserverPort = "53"
+
+// gRPC depends on the target's scheme to determine which resolver to use. Built-in DNS Resolver
+// registers itself with "dns" scheme. We should use a different scheme for this resolver. However,
+// Ruby, and other cares-based clients, don't support custom resolver. At GitLab, the gRPC target
+// configuration is shared between components. To ensure the compatibility between clients, this
+// resolver intentionally replaces the built-in resolver by itself.
+// The client should use grpc.WithResolvers to inject Gitaly custom DNS resolver when resolving
+// the target URL.
+const dnsResolverScheme = "dns"
+
+// BuilderConfig defines the configuration for customizing the builder.
+type BuilderConfig struct {
+	// RefreshRate determines the periodic refresh rate of the resolver. The resolver may issue
+	// the resolver earlier if client connection demands
+	RefreshRate time.Duration
+	// Logger defines a logger for logging internal activities
+	Logger *logrus.Logger
+	// Backoff defines the backoff strategy when the resolver fails to resolve or pushes new
+	// state to client connection
+	Backoff backoff.Strategy
+	// DefaultGrpcPort sets the gRPC port if the target URL doesn't specify a target port
+	DefaultGrpcPort string
+	// authorityFinder is to inject a custom authority finder from the authority address in
+	// the target URL. For example: dns://authority-host:authority-port/host:port
+	authorityFinder func(authority string) (dnsLookuper, error)
+}
+
+// Builder is an object to build the resolver for a connection. A client connection uses the builder
+// specified by grpc.WithResolvers dial option or the one fetched from global Resolver registry. The
+// local option has higher precedence than the global one.
+type Builder struct {
+	opts *BuilderConfig
+}
+
+// NewBuilder creates a builder option with an input option
+func NewBuilder(opts *BuilderConfig) *Builder {
+	return &Builder{opts: opts}
+}
+
+// Scheme returns the scheme handled by this builder. Client connection queries the resolver based
+// on the target URL scheme. This builder handles dns://*/* targets.
+func (d *Builder) Scheme() string {
+	return dnsResolverScheme
+}
+
+// Build returns a resolver that periodically resolves the input target. Each client connection
+// maintains a resolver. It's a part of client connection's life cycle. The target follows
+// gRPC desc resolution format (https://github.com/grpc/grpc/blob/master/doc/naming.md). As this
+// builds a DNS resolver, we care about dns URL only: dns:[//authority/]host[:port]
+// If the authority is missing (dns:host[:port]), it fallbacks to use OS resolver.
+func (d *Builder) Build(target resolver.Target, cc resolver.ClientConn, _ resolver.BuildOptions) (resolver.Resolver, error) {
+	path := target.URL.Path
+	if path == "" {
+		path = target.URL.Opaque
+	}
+	host, port, err := parseTarget(strings.TrimPrefix(path, "/"), d.opts.DefaultGrpcPort)
+	if err != nil {
+		return nil, structerr.New("building dns resolver: %w", err).WithMetadata("target", target.URL.String())
+	}
+
+	if addr, ok := tryParseIP(host, port); ok {
+		// When the address is a static IP, we don't need this resolver anymore. Client
+		// connection is responsible for handling network error in this case.
+		_ = cc.UpdateState(resolver.State{Addresses: []resolver.Address{{Addr: addr}}})
+		return &noopResolver{}, nil
+	}
+
+	authorityFinder := findDNSLookup
+	if d.opts.authorityFinder != nil {
+		authorityFinder = d.opts.authorityFinder
+	}
+	lookup, err := authorityFinder(target.URL.Host)
+	if err != nil {
+		return nil, structerr.New("finding DNS resolver: %w", err).WithMetadata("authority", target.URL.Host)
+	}
+
+	ctx, cancel := context.WithCancel(context.Background())
+	dr := &dnsResolver{
+		logger: logrus.NewEntry(d.opts.Logger).WithField("target", target.URL.String()),
+		retry:  d.opts.Backoff,
+
+		ctx:         ctx,
+		cancel:      cancel,
+		host:        host,
+		port:        port,
+		cc:          cc,
+		refreshRate: d.opts.RefreshRate,
+		lookup:      lookup,
+		reqs:        make(chan struct{}, 1),
+	}
+
+	dr.wg.Add(1)
+	go dr.watch()
+
+	return dr, nil
+}
diff --git a/internal/dnsresolver/builder_test.go b/internal/dnsresolver/builder_test.go
new file mode 100644
index 000000000..807d1260f
--- /dev/null
+++ b/internal/dnsresolver/builder_test.go
@@ -0,0 +1,144 @@
+package dnsresolver
+
+import (
+	"net"
+	"net/url"
+	"testing"
+	"time"
+
+	"github.com/miekg/dns"
+	"github.com/stretchr/testify/require"
+	"gitlab.com/gitlab-org/gitaly/v15/internal/testhelper"
+	"google.golang.org/grpc/resolver"
+)
+
+func TestBuildDNSBuilder_withBuiltInResolver(t *testing.T) {
+	t.Parallel()
+
+	for _, tc := range []struct {
+		desc   string
+		target string
+	}{
+		{desc: "with triple slashes", target: "dns:///localhost:50051"},
+		{desc: "without triple slashes", target: "dns:localhost:50051"},
+	} {
+		tc := tc
+		t.Run(tc.desc, func(t *testing.T) {
+			t.Parallel()
+
+			// Actually resolve with built-in resolver. Localhost may return different results
+			// between machines.
+			expectedIPs, err := net.DefaultResolver.LookupHost(testhelper.Context(t), "localhost")
+			require.NoError(t, err)
+
+			builder := newTestDNSBuilder(t)
+			conn := newFakeClientConn(1, 0)
+
+			targetURL, err := url.Parse(tc.target)
+			require.NoError(t, err)
+
+			r, err := builder.Build(resolver.Target{URL: *targetURL}, conn, resolver.BuildOptions{})
+			require.NoError(t, err)
+			defer r.Close()
+
+			conn.Wait()
+
+			// Compare the recorded state with real DNS resolution
+			require.Equal(t, 1, len(conn.states))
+			state := conn.states[0]
+
+			var actualIPs []string
+			for _, addr := range state.Addresses {
+				host, port, err := net.SplitHostPort(addr.Addr)
+				require.NoError(t, err)
+				require.Equal(t, port, "50051")
+				actualIPs = append(actualIPs, host)
+			}
+			require.ElementsMatch(t, expectedIPs, actualIPs)
+		})
+	}
+}
+
+func TestBuildDNSBuilder_customAuthorityResolver(t *testing.T) {
+	t.Parallel()
+
+	fakeServer := testhelper.NewFakeDNSServer(t).WithHandler(dns.TypeA, func(host string) []string {
+		if host == "grpc.test." {
+			return []string{"1.2.3.4"}
+		}
+		return nil
+	}).Start()
+
+	builder := NewBuilder(&BuilderConfig{
+		RefreshRate: 1 * time.Millisecond,
+		Logger:      testhelper.NewDiscardingLogger(t),
+		Backoff:     &fakeBackoff{duration: 1 * time.Millisecond},
+	})
+
+	conn := newFakeClientConn(1, 0)
+	r, err := builder.Build(buildResolverTarget(fakeServer, "grpc.test:50051"), conn, resolver.BuildOptions{})
+	require.NoError(t, err)
+	defer r.Close()
+
+	conn.Wait()
+	require.Equal(t, []resolver.State{{Addresses: []resolver.Address{{
+		Addr: "1.2.3.4:50051",
+	}}}}, conn.states)
+}
+
+func TestBuildDNSBuilder_staticIPAddress(t *testing.T) {
+	t.Parallel()
+
+	for _, tc := range []struct {
+		desc string
+		addr string
+	}{
+		{
+			desc: "IPv4",
+			addr: "4.3.2.1:50051",
+		},
+		{
+			desc: "Full IPv6",
+			addr: "[2001:0db8:85a3:0000:0000:8a2e:0370:7334]:50051",
+		},
+		{
+			desc: "Shortened IPv6",
+			addr: "[::3]:50051",
+		},
+	} {
+		tc := tc
+		t.Run(tc.desc, func(t *testing.T) {
+			t.Parallel()
+
+			fakeServer := testhelper.NewFakeDNSServer(t).WithHandler(dns.TypeA, func(_ string) []string {
+				require.FailNow(t, "resolving IP address should not result in a real DNS resolution")
+				return nil
+			}).Start()
+
+			builder := NewBuilder(&BuilderConfig{
+				RefreshRate: 1 * time.Millisecond,
+				Logger:      testhelper.NewDiscardingLogger(t),
+				Backoff:     &fakeBackoff{duration: 1 * time.Millisecond},
+			})
+
+			conn := newFakeClientConn(1, 0)
+			r, err := builder.Build(buildResolverTarget(fakeServer, tc.addr), conn, resolver.BuildOptions{})
+			require.NoError(t, err)
+			defer r.Close()
+
+			conn.Wait()
+			require.Equal(t, []resolver.State{{Addresses: []resolver.Address{{
+				Addr: tc.addr,
+			}}}}, conn.states)
+
+			require.IsType(t, &noopResolver{}, r, "building a resolver for IP address should return a no-op resolver")
+		})
+	}
+}
+
+func TestSchemeDNSBuilder(t *testing.T) {
+	t.Parallel()
+
+	d := &Builder{}
+	require.Equal(t, d.Scheme(), "dns")
+}
diff --git a/internal/dnsresolver/noop.go b/internal/dnsresolver/noop.go
new file mode 100644
index 000000000..6197653ed
--- /dev/null
+++ b/internal/dnsresolver/noop.go
@@ -0,0 +1,10 @@
+package dnsresolver
+
+import "google.golang.org/grpc/resolver"
+
+// noopResolver does nothing. It is used when a target is not resolvable.
+type noopResolver struct{}
+
+func (noopResolver) ResolveNow(resolver.ResolveNowOptions) {}
+
+func (noopResolver) Close() {}
diff --git a/internal/dnsresolver/resolver.go b/internal/dnsresolver/resolver.go
new file mode 100644
index 000000000..76be0dbe4
--- /dev/null
+++ b/internal/dnsresolver/resolver.go
@@ -0,0 +1,134 @@
+package dnsresolver
+
+import (
+	"context"
+	"net"
+	"sync"
+	"time"
+
+	"github.com/sirupsen/logrus"
+	"gitlab.com/gitlab-org/gitaly/v15/internal/backoff"
+	"gitlab.com/gitlab-org/gitaly/v15/internal/structerr"
+	"google.golang.org/grpc/resolver"
+)
+
+type dnsResolver struct {
+	logger *logrus.Entry
+	retry  backoff.Strategy
+
+	ctx         context.Context
+	cancel      context.CancelFunc
+	cc          resolver.ClientConn
+	host        string
+	port        string
+	refreshRate time.Duration
+	lookup      dnsLookuper
+	reqs        chan struct{}
+	wg          sync.WaitGroup
+}
+
+var dnsLookupTimeout = 15 * time.Second
+
+type dnsLookuper interface {
+	LookupHost(context.Context, string) ([]string, error)
+}
+
+// ResolveNow signals the resolver to perform a DNS resolution immediately. This method returns
+// without waiting for the result. The resolver treats this as a hint rather than a command. The
+// client connection receives the resolution result asynchronously via `clientconn.UpdateState`
+// This method also skip resolver caching because it's likely the client calls this method after
+// encounter an error with recent subchannels.
+func (d *dnsResolver) ResolveNow(resolver.ResolveNowOptions) {
+	select {
+	case d.reqs <- struct{}{}:
+	default:
+	}
+}
+
+// Close cancels all activities of this dns resolver. It waits until the watch goroutine exits.
+func (d *dnsResolver) Close() {
+	d.cancel()
+	d.wg.Wait()
+}
+
+func (d *dnsResolver) watch() {
+	defer d.wg.Done()
+	d.logger.Info("dns resolver: started")
+	defer d.logger.Info("dns resolver: stopped")
+
+	// Exponential retry after failed to resolve or client connection failed to update its state
+	var retries uint
+	for {
+		state, err := d.resolve()
+		if err != nil {
+			d.logger.WithField("dns.retries", retries).WithField("dns.error", err).Error(
+				"dns resolver: fail to lookup dns")
+			d.cc.ReportError(err)
+		} else {
+			err = d.updateState(state)
+		}
+
+		var timer *time.Timer
+		if err == nil {
+			timer = time.NewTimer(d.refreshRate)
+			retries = 0
+		} else {
+			timer = time.NewTimer(d.retry.Backoff(retries))
+			retries++
+		}
+
+		select {
+		case <-d.ctx.Done():
+			timer.Stop()
+			return
+		case <-timer.C:
+			// Refresh timer expires, issue another DNS lookup.
+			d.logger.Debug("dns resolver: refreshing")
+			continue
+		case <-d.reqs:
+			// If the resolver is requested to resolve now, force notify the client
+			// connection. Typically, client connection contacts the resolver when any
+			// of the subchannels change its connectivity state.
+			timer.Stop()
+			d.logger.Debug("dns resolver: handle ResolveNow request")
+		}
+	}
+}
+
+func (d *dnsResolver) updateState(state *resolver.State) error {
+	d.logger.WithField("dns.state", state).Info("dns resolver: updating state")
+	return d.cc.UpdateState(*state)
+}
+
+func (d *dnsResolver) resolve() (*resolver.State, error) {
+	ctx, cancel := context.WithTimeout(d.ctx, dnsLookupTimeout)
+	defer cancel()
+
+	addrs, err := d.lookup.LookupHost(ctx, d.host)
+	if err != nil {
+		err = handleDNSError(err)
+		return &resolver.State{Addresses: []resolver.Address{}}, err
+	}
+	newAddrs := make([]resolver.Address, 0, len(addrs))
+	for _, a := range addrs {
+		addr, ok := tryParseIP(a, d.port)
+		if !ok {
+			return nil, structerr.New("dns: error parsing dns record IP address %v", a)
+		}
+		newAddrs = append(newAddrs, resolver.Address{Addr: addr})
+	}
+
+	return &resolver.State{Addresses: newAddrs}, nil
+}
+
+// handleDNSError massages the error to fit into expectations of the gRPC model:
+//   - Timeouts and temporary errors should be communicated to gRPC to attempt another DNS query (with
+//     Backoff).
+//   - Other errors should be suppressed (they may represent the absence of a TXT record).
+func handleDNSError(err error) error {
+	if dnsErr, ok := err.(*net.DNSError); ok && !dnsErr.IsTimeout && !dnsErr.IsTemporary {
+		return nil
+	}
+
+	return structerr.New("dns: record resolve error: %w", err)
+}
diff --git a/internal/dnsresolver/resolver_test.go b/internal/dnsresolver/resolver_test.go
new file mode 100644
index 000000000..5a410afdb
--- /dev/null
+++ b/internal/dnsresolver/resolver_test.go
@@ -0,0 +1,386 @@
+package dnsresolver
+
+import (
+	"context"
+	"fmt"
+	"math/rand"
+	"net"
+	"testing"
+	"time"
+
+	"github.com/miekg/dns"
+	"github.com/stretchr/testify/require"
+	"gitlab.com/gitlab-org/gitaly/v15/internal/backoff"
+	"gitlab.com/gitlab-org/gitaly/v15/internal/structerr"
+	"gitlab.com/gitlab-org/gitaly/v15/internal/testhelper"
+	grpccorrelation "gitlab.com/gitlab-org/labkit/correlation/grpc"
+	"google.golang.org/grpc"
+	"google.golang.org/grpc/credentials/insecure"
+	"google.golang.org/grpc/resolver"
+	"google.golang.org/grpc/test/grpc_testing"
+)
+
+func TestDnsResolver(t *testing.T) {
+	t.Parallel()
+
+	testCases := []struct {
+		name            string
+		setup           func(*testhelper.FakeDNSServer, *Builder) *fakeClientConn
+		address         string
+		builder         *Builder
+		expectedStates  []resolver.State
+		expectedErrors  []error
+		expectedRetries []uint
+	}{
+		{
+			name: "resolver updates a single IPv4 each resolution",
+			setup: func(server *testhelper.FakeDNSServer, _ *Builder) *fakeClientConn {
+				ips := ipList{ips: [][]string{
+					{"1.2.3.4"},
+					{"1.2.3.5"},
+					{"1.2.3.6"},
+				}}
+				server.WithHandler(dns.TypeA, func(host string) []string {
+					if host != "grpc.test." {
+						return nil
+					}
+					return ips.next()
+				})
+
+				return newFakeClientConn(3, 0)
+			},
+			address: "grpc.test:50051",
+			expectedStates: []resolver.State{
+				{Addresses: []resolver.Address{{Addr: "1.2.3.4:50051"}}},
+				{Addresses: []resolver.Address{{Addr: "1.2.3.5:50051"}}},
+				{Addresses: []resolver.Address{{Addr: "1.2.3.6:50051"}}},
+			},
+		},
+		{
+			name: "resolver updates multiple IPv4 each resolution",
+			setup: func(server *testhelper.FakeDNSServer, _ *Builder) *fakeClientConn {
+				ips := ipList{ips: [][]string{
+					{"1.2.3.4", "1.2.3.5"},
+					{"1.2.3.6"},
+					{"1.2.3.7", "1.2.3.8"},
+				}}
+				server.WithHandler(dns.TypeA, func(host string) []string {
+					if host != "grpc.test." {
+						return nil
+					}
+					return ips.next()
+				})
+
+				return newFakeClientConn(3, 0)
+			},
+			address: "grpc.test:50051",
+			expectedStates: []resolver.State{
+				{Addresses: []resolver.Address{{Addr: "1.2.3.4:50051"}, {Addr: "1.2.3.5:50051"}}},
+				{Addresses: []resolver.Address{{Addr: "1.2.3.6:50051"}}},
+				{Addresses: []resolver.Address{{Addr: "1.2.3.7:50051"}, {Addr: "1.2.3.8:50051"}}},
+			},
+		},
+		{
+			name: "resolver updates multiple IPv6 each resolution",
+			setup: func(server *testhelper.FakeDNSServer, _ *Builder) *fakeClientConn {
+				ips := ipList{ips: [][]string{
+					{"::1", "::2"},
+					{"::3", "::4"},
+					{"::5", "::6"},
+				}}
+				server.WithHandler(dns.TypeAAAA, func(host string) []string {
+					if host != "grpc.test." {
+						return nil
+					}
+					return ips.next()
+				})
+
+				return newFakeClientConn(3, 0)
+			},
+			address: "grpc.test:50051",
+			expectedStates: []resolver.State{
+				{Addresses: []resolver.Address{{Addr: "[::1]:50051"}, {Addr: "[::2]:50051"}}},
+				{Addresses: []resolver.Address{{Addr: "[::3]:50051"}, {Addr: "[::4]:50051"}}},
+				{Addresses: []resolver.Address{{Addr: "[::5]:50051"}, {Addr: "[::6]:50051"}}},
+			},
+		},
+		{
+			name: "resolver resolves address without port",
+			setup: func(server *testhelper.FakeDNSServer, _ *Builder) *fakeClientConn {
+				ips := ipList{ips: [][]string{
+					{"1.2.3.4"},
+					{"1.2.3.5"},
+					{"1.2.3.6"},
+				}}
+				server.WithHandler(dns.TypeA, func(host string) []string {
+					if host != "grpc.test." {
+						return nil
+					}
+					return ips.next()
+				})
+
+				return newFakeClientConn(3, 0)
+			},
+			address: "grpc.test",
+			expectedStates: []resolver.State{
+				{Addresses: []resolver.Address{{Addr: "1.2.3.4:1234"}}},
+				{Addresses: []resolver.Address{{Addr: "1.2.3.5:1234"}}},
+				{Addresses: []resolver.Address{{Addr: "1.2.3.6:1234"}}},
+			},
+		},
+		{
+			name: "resolver retries with exponential Backoff when client connection fails to update",
+			setup: func(server *testhelper.FakeDNSServer, _ *Builder) *fakeClientConn {
+				conn := newFakeClientConn(2, 0)
+				connErr := 2
+				conn.customUpdateState = func(state resolver.State) error {
+					if connErr > 0 {
+						connErr--
+						return fmt.Errorf("something goes wrong")
+					}
+					return conn.doUpdateState(state)
+				}
+
+				ips := ipList{ips: [][]string{
+					{"1.2.3.4"},
+					{"1.2.3.5"},
+					{"1.2.3.6"},
+					{"1.2.3.7"},
+				}}
+				server.WithHandler(dns.TypeA, func(host string) []string {
+					if host != "grpc.test." {
+						return nil
+					}
+					return ips.next()
+				})
+
+				return conn
+			},
+			address: "grpc.test:50051",
+			expectedStates: []resolver.State{
+				{Addresses: []resolver.Address{{Addr: "1.2.3.6:50051"}}},
+				{Addresses: []resolver.Address{{Addr: "1.2.3.7:50051"}}},
+			},
+			expectedRetries: []uint{0, 1},
+		},
+		{
+			name: "DNS nameserver returns empty addresses",
+			setup: func(server *testhelper.FakeDNSServer, _ *Builder) *fakeClientConn {
+				server.WithHandler(dns.TypeA, func(_ string) []string {
+					return nil
+				})
+				return newFakeClientConn(3, 0)
+			},
+			address: "grpc.test:50051",
+			expectedStates: []resolver.State{
+				{Addresses: []resolver.Address{}},
+				{Addresses: []resolver.Address{}},
+				{Addresses: []resolver.Address{}},
+			},
+		},
+		{
+			name: "DNS nameserver raises timeout error",
+			setup: func(server *testhelper.FakeDNSServer, builder *Builder) *fakeClientConn {
+				ips := ipList{ips: [][]string{
+					{"1.2.3.4"},
+					{},
+					{"1.2.3.5"},
+					{"1.2.3.6"},
+				}}
+
+				builder.opts.authorityFinder = func(authority string) (dnsLookuper, error) {
+					f := newFakeLookup(t, authority)
+					f.stubLookup = func(ctx context.Context, host string) ([]string, error) {
+						nextIPs := ips.peek()
+						if nextIPs != nil && len(nextIPs) == 0 {
+							ips.next()
+							return nil, &net.DNSError{
+								Err:       "timeout",
+								Name:      host,
+								IsTimeout: true,
+							}
+						}
+						return f.realLookup.LookupHost(ctx, host)
+					}
+					return f, nil
+				}
+				server.WithHandler(dns.TypeA, func(host string) []string {
+					if host != "grpc.test." {
+						return nil
+					}
+					return ips.next()
+				})
+				return newFakeClientConn(3, 1)
+			},
+			address: "grpc.test:50051",
+			expectedStates: []resolver.State{
+				{Addresses: []resolver.Address{{Addr: "1.2.3.4:50051"}}},
+				{Addresses: []resolver.Address{{Addr: "1.2.3.5:50051"}}},
+				{Addresses: []resolver.Address{{Addr: "1.2.3.6:50051"}}},
+			},
+			expectedErrors: []error{
+				structerr.New("dns: record resolve error: %w", &net.DNSError{
+					Err:       "timeout",
+					Name:      "grpc.test",
+					IsTimeout: true,
+				}),
+			},
+			expectedRetries: []uint{0},
+		},
+		{
+			name: "DNS nameserver raises a temporary error",
+			setup: func(server *testhelper.FakeDNSServer, builder *Builder) *fakeClientConn {
+				ips := ipList{ips: [][]string{
+					{"1.2.3.4"},
+					{},
+					{},
+					{},
+					{"1.2.3.5"},
+					{"1.2.3.6"},
+					{},
+					{"1.2.3.6"},
+				}}
+
+				builder.opts.authorityFinder = func(authority string) (dnsLookuper, error) {
+					f := newFakeLookup(t, authority)
+					f.stubLookup = func(ctx context.Context, host string) ([]string, error) {
+						nextIPs := ips.peek()
+						if nextIPs != nil && len(nextIPs) == 0 {
+							ips.next()
+							return nil, &net.DNSError{
+								Err:         "temporary",
+								Name:        host,
+								IsTemporary: true,
+							}
+						}
+						return f.realLookup.LookupHost(ctx, host)
+					}
+					return f, nil
+				}
+				server.WithHandler(dns.TypeA, func(host string) []string {
+					if host != "grpc.test." {
+						return nil
+					}
+					return ips.next()
+				})
+				return newFakeClientConn(3, 4)
+			},
+			address: "grpc.test:50051",
+			expectedStates: []resolver.State{
+				{Addresses: []resolver.Address{{Addr: "1.2.3.4:50051"}}},
+				{Addresses: []resolver.Address{{Addr: "1.2.3.5:50051"}}},
+				{Addresses: []resolver.Address{{Addr: "1.2.3.6:50051"}}}, // Cached
+			},
+			expectedErrors: []error{
+				structerr.New("dns: record resolve error: %w", &net.DNSError{
+					Err:         "temporary",
+					Name:        "grpc.test",
+					IsTemporary: true,
+				}),
+				structerr.New("dns: record resolve error: %w", &net.DNSError{
+					Err:         "temporary",
+					Name:        "grpc.test",
+					IsTemporary: true,
+				}),
+				structerr.New("dns: record resolve error: %w", &net.DNSError{
+					Err:         "temporary",
+					Name:        "grpc.test",
+					IsTemporary: true,
+				}),
+				structerr.New("dns: record resolve error: %w", &net.DNSError{
+					Err:         "temporary",
+					Name:        "grpc.test",
+					IsTemporary: true,
+				}),
+			},
+			expectedRetries: []uint{0, 1, 2, 0},
+		},
+	}
+
+	for _, tc := range testCases {
+		t.Run(tc.name, func(t *testing.T) {
+			b := &fakeBackoff{duration: 1 * time.Millisecond}
+			builder := NewBuilder(&BuilderConfig{
+				RefreshRate:     1 * time.Millisecond,
+				Logger:          testhelper.NewDiscardingLogger(t),
+				DefaultGrpcPort: "1234",
+				Backoff:         b,
+			})
+
+			fakeServer := testhelper.NewFakeDNSServer(t)
+			conn := tc.setup(fakeServer, builder)
+			fakeServer.Start()
+
+			r, err := builder.Build(buildResolverTarget(fakeServer, tc.address), conn, resolver.BuildOptions{})
+			require.NoError(t, err)
+
+			conn.Wait()
+			r.Close()
+
+			require.Equal(t, tc.expectedStates, conn.states)
+			require.Equal(t, tc.expectedErrors, conn.errors)
+			require.Equal(t, tc.expectedRetries, b.retries)
+		})
+	}
+}
+
+// This test spawns a real gRPC server and a fake DNS nameserver that maps grpc.test to spawned
+// gRPC server. Too bad, it's very likely the testing machine has only one localhost loopback.
+// We could not bind to another IP address without modifying ipconfig/ifconfig. Service discovery
+// with SRV record overcomes this limitation. However, we don't support that at the moment.
+func TestDnsResolver_grpcCallWithOurDNSResolver(t *testing.T) {
+	t.Parallel()
+
+	listener := spawnTestGRPCServer(t)
+	serverHost, serverPort, err := net.SplitHostPort(listener.Addr().String())
+	require.NoError(t, err)
+
+	fakeServer := testhelper.NewFakeDNSServer(t).WithHandler(dns.TypeA, func(host string) []string {
+		if host == "grpc.test." {
+			return []string{serverHost}
+		}
+		return nil
+	}).Start()
+
+	// This scheme uses our DNS resolver
+	target := buildResolverTarget(fakeServer, fmt.Sprintf("grpc.test:%s", serverPort))
+	conn, err := grpc.Dial(
+		target.URL.String(),
+		grpc.WithTransportCredentials(insecure.NewCredentials()),
+		grpc.WithResolvers(NewBuilder(&BuilderConfig{
+			RefreshRate:     1 * time.Millisecond,
+			Logger:          testhelper.NewDiscardingLogger(t),
+			DefaultGrpcPort: "1234",
+			Backoff:         backoff.NewDefaultExponential(rand.New(rand.NewSource(time.Now().UnixNano()))),
+		})),
+	)
+	require.NoError(t, err)
+	defer testhelper.MustClose(t, conn)
+
+	client := grpc_testing.NewTestServiceClient(conn)
+	for i := 0; i < 10; i++ {
+		_, err = client.UnaryCall(testhelper.Context(t), &grpc_testing.SimpleRequest{})
+		require.NoError(t, err)
+	}
+}
+
+func spawnTestGRPCServer(t *testing.T) net.Listener {
+	listener, err := net.Listen("tcp", "localhost:0")
+	require.NoError(t, err)
+
+	grpcServer := grpc.NewServer(grpc.UnaryInterceptor(grpccorrelation.UnaryServerCorrelationInterceptor()))
+	svc := &testSvc{}
+	grpc_testing.RegisterTestServiceServer(grpcServer, svc)
+	go testhelper.MustServe(t, grpcServer, listener)
+	t.Cleanup(func() { grpcServer.Stop() })
+
+	return listener
+}
+
+type testSvc struct {
+	grpc_testing.UnimplementedTestServiceServer
+}
+
+func (ts *testSvc) UnaryCall(_ context.Context, _ *grpc_testing.SimpleRequest) (*grpc_testing.SimpleResponse, error) {
+	return &grpc_testing.SimpleResponse{}, nil
+}
diff --git a/internal/dnsresolver/target.go b/internal/dnsresolver/target.go
new file mode 100644
index 000000000..3ae9c86be
--- /dev/null
+++ b/internal/dnsresolver/target.go
@@ -0,0 +1,70 @@
+package dnsresolver
+
+import (
+	"context"
+	"net"
+
+	"gitlab.com/gitlab-org/gitaly/v15/internal/structerr"
+)
+
+// parseTarget takes the user input target string and default port, returns formatted host and port info.
+// This is a shameless copy of built-in gRPC dns resolver, because we don't want to have any
+// inconsistency between our resolver and dns resolver.
+// Source: https://github.com/grpc/grpc-go/blob/eeb9afa1f6b6388152955eeca8926e36ca94c768/internal/resolver/dns/dns_resolver.go#L378-L378
+func parseTarget(target, defaultPort string) (string, string, error) {
+	var err error
+
+	if target == "" {
+		return "", "", structerr.New("dns resolver: missing address")
+	}
+
+	if ip := net.ParseIP(target); ip != nil {
+		// target is an IPv4 or IPv6(without brackets) address
+		return target, defaultPort, nil
+	}
+
+	if host, port, err := net.SplitHostPort(target); err == nil {
+		if port == "" {
+			// If the port field is empty (target ends with colon), e.g. "[::1]:", this is an error.
+			return "", "", structerr.New("dns resolver: missing port after port-separator colon")
+		}
+		if host == "" {
+			host = "localhost"
+		}
+		return host, port, nil
+	}
+
+	host, port, err := net.SplitHostPort(target + ":" + defaultPort)
+	if err == nil {
+		return host, port, nil
+	}
+	return "", "", structerr.New("dns resolver: %w", err)
+}
+
+func tryParseIP(host, port string) (addr string, ok bool) {
+	ip := net.ParseIP(host)
+	if ip == nil {
+		return "", false
+	}
+	return net.JoinHostPort(host, port), true
+}
+
+func findDNSLookup(authority string) (dnsLookuper, error) {
+	if authority == "" {
+		return net.DefaultResolver, nil
+	}
+
+	host, port, err := parseTarget(authority, defaultDNSNameserverPort)
+	if err != nil {
+		return nil, err
+	}
+
+	addr := net.JoinHostPort(host, port)
+	return &net.Resolver{
+		PreferGo: true,
+		Dial: func(ctx context.Context, network, address string) (net.Conn, error) {
+			var dialer net.Dialer
+			return dialer.DialContext(ctx, network, addr)
+		},
+	}, nil
+}
diff --git a/internal/dnsresolver/target_test.go b/internal/dnsresolver/target_test.go
new file mode 100644
index 000000000..7b97ded41
--- /dev/null
+++ b/internal/dnsresolver/target_test.go
@@ -0,0 +1,147 @@
+package dnsresolver
+
+import (
+	"fmt"
+	"net"
+	"testing"
+
+	"github.com/miekg/dns"
+	"github.com/stretchr/testify/require"
+	"gitlab.com/gitlab-org/gitaly/v15/internal/structerr"
+	"gitlab.com/gitlab-org/gitaly/v15/internal/testhelper"
+)
+
+func TestFindDNSLookup_default(t *testing.T) {
+	t.Parallel()
+
+	resolver, err := findDNSLookup("")
+	require.NoError(t, err)
+	require.Equal(t, net.DefaultResolver, resolver)
+}
+
+func TestFindDNSLookup_invalidAuthority(t *testing.T) {
+	t.Parallel()
+
+	resolver, err := findDNSLookup("this:is:not:good")
+	require.ErrorIs(t, structerr.New("dns resolver: %w", &net.AddrError{
+		Err:  "too many colons in address",
+		Addr: "this:is:not:good:53",
+	}), err)
+	require.Nil(t, resolver)
+}
+
+func TestFindDNSLookup_validAuthority(t *testing.T) {
+	t.Parallel()
+
+	fakeServer := testhelper.NewFakeDNSServer(t).WithHandler(dns.TypeA, func(host string) []string {
+		if host == "grpc.test." {
+			return []string{"1.2.3.4"}
+		}
+		return nil
+	}).Start()
+
+	resolver, err := findDNSLookup(fakeServer.Addr())
+	require.NoError(t, err)
+
+	addrs, err := resolver.LookupHost(testhelper.Context(t), "grpc.test")
+	require.NoError(t, err)
+
+	require.Equal(t, []string{"1.2.3.4"}, addrs)
+}
+
+func TestParseTarget(t *testing.T) {
+	t.Parallel()
+
+	defaultPort := "443"
+	tests := []struct {
+		target       string
+		expectedHost string
+		expectedPort string
+		expectedErr  error
+	}{
+		{
+			target:       "www.google.com",
+			expectedHost: "www.google.com",
+			expectedPort: "443",
+		},
+		{
+			target:       "google.com:50051",
+			expectedHost: "google.com",
+			expectedPort: "50051",
+		},
+		{
+			target:       "1.2.3.4",
+			expectedHost: "1.2.3.4",
+			expectedPort: "443",
+		},
+		{
+			target:       "1.2.3.4:50051",
+			expectedHost: "1.2.3.4",
+			expectedPort: "50051",
+		},
+		{
+			target:       "[2001:0db8:85a3:0000:0000:8a2e:0370:7334]",
+			expectedHost: "2001:0db8:85a3:0000:0000:8a2e:0370:7334",
+			expectedPort: "443",
+		},
+		{
+			target:       "[fe80::1ff:fe23:4567:890a]:50051",
+			expectedHost: "fe80::1ff:fe23:4567:890a",
+			expectedPort: "50051",
+		},
+		{
+			target:      "[fe80::1ff:fe23:4567:890a]:",
+			expectedErr: structerr.New("dns resolver: missing port after port-separator colon"),
+		},
+		{
+			target:       ":50051",
+			expectedHost: "localhost",
+			expectedPort: "50051",
+		},
+		{
+			target:      "",
+			expectedErr: structerr.New("dns resolver: missing address"),
+		},
+		{
+			target: "this:is:invalid:address",
+			expectedErr: structerr.New("dns resolver: %w", &net.AddrError{
+				Err:  "too many colons in address",
+				Addr: "this:is:invalid:address:443",
+			}),
+		},
+	}
+	for _, tc := range tests {
+		t.Run(fmt.Sprintf("target: %s", tc.target), func(t *testing.T) {
+			host, port, err := parseTarget(tc.target, defaultPort)
+
+			require.Equal(t, tc.expectedErr, err)
+			require.Equal(t, tc.expectedHost, host)
+			require.Equal(t, tc.expectedPort, port)
+		})
+	}
+}
+
+func TestTryParseIP(t *testing.T) {
+	t.Parallel()
+
+	tests := []struct {
+		host         string
+		port         string
+		expectedAddr string
+		expectedOk   bool
+	}{
+		{host: "google.com", port: "50051", expectedOk: false},
+		{host: "1.2.3", port: "50051", expectedOk: false},
+		{host: "1.2.3.4", port: "50051", expectedAddr: "1.2.3.4:50051", expectedOk: true},
+		{host: "64:ff9b::", port: "50051", expectedAddr: "[64:ff9b::]:50051", expectedOk: true},
+		{host: "2001:0db8:85a3:0000:0000:8a2e:0370:7334", port: "50051", expectedAddr: "[2001:0db8:85a3:0000:0000:8a2e:0370:7334]:50051", expectedOk: true},
+	}
+	for _, tc := range tests {
+		t.Run(fmt.Sprintf("host: %s, port: %s", tc.host, tc.port), func(t *testing.T) {
+			addr, ok := tryParseIP(tc.host, tc.port)
+
+			require.Equal(t, tc.expectedOk, ok)
+			require.Equal(t, tc.expectedAddr, addr)
+		})
+	}
+}
diff --git a/internal/dnsresolver/testhelper_test.go b/internal/dnsresolver/testhelper_test.go
new file mode 100644
index 000000000..c89af7faa
--- /dev/null
+++ b/internal/dnsresolver/testhelper_test.go
@@ -0,0 +1,164 @@
+package dnsresolver
+
+import (
+	"context"
+	"fmt"
+	"net/url"
+	"sync"
+	"testing"
+	"time"
+
+	"github.com/stretchr/testify/require"
+	"gitlab.com/gitlab-org/gitaly/v15/internal/testhelper"
+	"google.golang.org/grpc/resolver"
+	"google.golang.org/grpc/serviceconfig"
+)
+
+func TestMain(m *testing.M) {
+	testhelper.Run(m)
+}
+
+// fakeClientConn stubs resolver.ClientConn. It captures all states and errors received from the
+// resolver. As the resolver runs asynchronously, we cannot control when and how many states are
+// pushed to the connection. For testing purpose, the fake connection doesn't need to capture all
+// states and errors. Instead, it captures some first states and errors (configured via waitState
+// and waitError). The caller is expected to call Wait(). This method returns when enough data
+// arrives. Afterward, further data are rejected.
+type fakeClientConn struct {
+	customUpdateState func(resolver.State) error
+	states            []resolver.State
+	errors            []error
+
+	waitState     int
+	waitStateChan chan struct{}
+
+	waitError     int
+	waitErrorChan chan struct{}
+}
+
+func newFakeClientConn(waitState int, waitError int) *fakeClientConn {
+	return &fakeClientConn{
+		waitState:     waitState,
+		waitStateChan: make(chan struct{}, waitState),
+		waitError:     waitError,
+		waitErrorChan: make(chan struct{}, waitError),
+	}
+}
+
+func (c *fakeClientConn) UpdateState(state resolver.State) error {
+	if c.customUpdateState != nil {
+		return c.customUpdateState(state)
+	}
+	return c.doUpdateState(state)
+}
+
+func (c *fakeClientConn) doUpdateState(state resolver.State) error {
+	// Do nothing if received enough states
+	if len(c.states) >= c.waitState {
+		return nil
+	}
+	c.states = append(c.states, state)
+	c.waitStateChan <- struct{}{}
+
+	return nil
+}
+
+func (c *fakeClientConn) Wait() {
+	for i := 0; i < c.waitState; i++ {
+		<-c.waitStateChan
+	}
+	for i := 0; i < c.waitError; i++ {
+		<-c.waitErrorChan
+	}
+}
+
+func (c *fakeClientConn) ReportError(err error) {
+	// Do nothing if received enough errors
+	if len(c.errors) >= c.waitError {
+		return
+	}
+	c.errors = append(c.errors, err)
+	c.waitErrorChan <- struct{}{}
+}
+
+func (c *fakeClientConn) NewAddress(_ []resolver.Address) { panic("deprecated") }
+
+func (c *fakeClientConn) NewServiceConfig(_ string) { panic("deprecated") }
+
+func (c *fakeClientConn) ParseServiceConfig(_ string) *serviceconfig.ParseResult { panic("deprecated") }
+
+// fakeBackoff stubs the exponential Backoff strategy. It always returns a tiny duration regardless
+// of the retry attempts. While it's possible to set to 0 (no timer), it makes sense to set a tiny
+// delay.
+type fakeBackoff struct {
+	duration time.Duration
+	retries  []uint
+}
+
+func (c *fakeBackoff) Backoff(retries uint) time.Duration {
+	c.retries = append(c.retries, retries)
+
+	return c.duration
+}
+
+// fakeLookup stubs the DNS lookup. It wraps around a real DNS lookup. The caller can return an
+// alternative addresses, errors, or fallback to use the real DNS lookup if needed.
+type fakeLookup struct {
+	realLookup dnsLookuper
+	stubLookup func(context.Context, string) ([]string, error)
+}
+
+func (f *fakeLookup) LookupHost(ctx context.Context, s string) ([]string, error) {
+	return f.stubLookup(ctx, s)
+}
+
+func newFakeLookup(t *testing.T, authority string) *fakeLookup {
+	lookup, err := findDNSLookup(authority)
+	require.NoError(t, err)
+
+	return &fakeLookup{realLookup: lookup}
+}
+
+func buildResolverTarget(s *testhelper.FakeDNSServer, addr string) resolver.Target {
+	return resolver.Target{URL: url.URL{
+		Scheme: "dns",
+		Host:   s.Addr(),
+		Path:   fmt.Sprintf("/%s", addr),
+	}}
+}
+
+func newTestDNSBuilder(t *testing.T) *Builder {
+	return NewBuilder(&BuilderConfig{
+		RefreshRate: 1 * time.Millisecond,
+		Logger:      testhelper.NewDiscardingLogger(t),
+		Backoff:     &fakeBackoff{duration: 1 * time.Millisecond},
+	})
+}
+
+// ipList simulates the list of IPs returned by the DNS server in order
+type ipList struct {
+	ips   [][]string
+	mutex sync.Mutex
+	index int
+}
+
+func (list *ipList) next() []string {
+	list.mutex.Lock()
+	defer list.mutex.Unlock()
+
+	if list.index < len(list.ips) {
+		list.index++
+		return list.ips[list.index-1]
+	}
+	return nil
+}
+
+func (list *ipList) peek() []string {
+	list.mutex.Lock()
+	defer list.mutex.Unlock()
+
+	if list.index < len(list.ips) {
+		return list.ips[list.index]
+	}
+	return nil
+}
diff --git a/internal/testhelper/dnsserver.go b/internal/testhelper/dnsserver.go
new file mode 100644
index 000000000..494ef095d
--- /dev/null
+++ b/internal/testhelper/dnsserver.go
@@ -0,0 +1,88 @@
+package testhelper
+
+import (
+	"fmt"
+	"sync"
+	"testing"
+
+	"github.com/miekg/dns"
+	"github.com/stretchr/testify/require"
+)
+
+// FakeDNSServer starts a fake DNS server serving real DNS queries via UDP. The answers are returned
+// from an input handler method.
+type FakeDNSServer struct {
+	t         *testing.T
+	mux       *dns.ServeMux
+	dnsServer *dns.Server
+	handlers  map[uint16]fakeDNSHandler
+}
+
+type fakeDNSHandler func(string) []string
+
+// WithHandler adds a handler for an input DNS record type
+func (s *FakeDNSServer) WithHandler(t uint16, handler fakeDNSHandler) *FakeDNSServer {
+	s.handlers[t] = handler
+	return s
+}
+
+// Start starts the DNS name server. The server stops in the test clean-up phase
+func (s *FakeDNSServer) Start() *FakeDNSServer {
+	s.mux.HandleFunc(".", func(writer dns.ResponseWriter, msg *dns.Msg) {
+		m := new(dns.Msg)
+		m.SetReply(msg)
+		m.Compress = false
+
+		switch msg.Opcode {
+		case dns.OpcodeQuery:
+			for _, q := range m.Question {
+				handler := s.handlers[q.Qtype]
+				if handler == nil {
+					continue
+				}
+
+				for _, answer := range handler(q.Name) {
+					rr, err := dns.NewRR(fmt.Sprintf("%s %s %s", q.Name, dns.Type(q.Qtype).String(), answer))
+					require.NoError(s.t, err)
+					m.Answer = append(m.Answer, rr)
+				}
+			}
+		}
+
+		require.NoError(s.t, writer.WriteMsg(m))
+	})
+
+	var wg sync.WaitGroup
+	s.dnsServer.NotifyStartedFunc = func() { wg.Done() }
+
+	wg.Add(1)
+	go func() { require.NoError(s.t, s.dnsServer.ListenAndServe()) }()
+
+	s.t.Cleanup(func() {
+		require.NoError(s.t, s.dnsServer.Shutdown())
+	})
+
+	wg.Wait()
+	return s
+}
+
+// Addr returns the UDP address used to access the DNS nameserver
+func (s *FakeDNSServer) Addr() string {
+	return s.dnsServer.PacketConn.LocalAddr().String()
+}
+
+// NewFakeDNSServer returns a new real fake DNS server object
+func NewFakeDNSServer(t *testing.T) *FakeDNSServer {
+	mux := dns.NewServeMux()
+	dnsServer := &dns.Server{
+		Addr:    ":0",
+		Net:     "udp",
+		Handler: mux,
+	}
+	return &FakeDNSServer{
+		t:         t,
+		mux:       mux,
+		dnsServer: dnsServer,
+		handlers:  make(map[uint16]fakeDNSHandler),
+	}
+}