graph/db: allow async cache population

diff --git a/graph/db/graph.go b/graph/db/graph.go
index 7662253..e7ed585 100644
--- a/graph/db/graph.go
+++ b/graph/db/graph.go
@@ -31,11 +31,9 @@ type ChannelGraph struct {
 	started atomic.Bool
 	stopped atomic.Bool
 
-	// cacheLoaded is true if the initial graphCache population has
-	// finished. We use this to ensure that when performing any reads,
-	// we only read from the graphCache if it has been fully populated.
-	cacheLoaded atomic.Bool
-	graphCache  *GraphCache
+	opts *chanGraphOptions
+
+	cache *graphCacheState
 
 	db Store
 	*topologyManager
@@ -55,6 +53,7 @@ func NewChannelGraph(v1Store Store,
 	}
 
 	g := &ChannelGraph{
+		opts:            opts,
 		db:              v1Store,
 		topologyManager: newTopologyManager(),
 		quit:            make(chan struct{}),
@@ -63,7 +62,7 @@ func NewChannelGraph(v1Store Store,
 	// The graph cache can be turned off (e.g. for mobile users) for a
 	// speed/memory usage tradeoff.
 	if opts.useGraphCache {
-		g.graphCache = NewGraphCache(opts.preAllocCacheNumNodes)
+		g.cache = newGraphCacheState(opts.preAllocCacheNumNodes)
 	}
 
 	return g, nil
@@ -82,8 +81,21 @@ func (c *ChannelGraph) Start() error {
 	ctx, cancel := context.WithCancel(context.Background())
 	c.cancel = fn.Some(cancel)
 
-	if err := c.populateCache(ctx); err != nil {
-		return fmt.Errorf("could not populate the graph cache: %w", err)
+	if c.opts.asyncGraphCachePopulation {
+		c.wg.Add(1)
+		go func() {
+			defer c.wg.Done()
+
+			if err := c.populateCache(ctx); err != nil {
+				log.Criticalf("Could not populate the "+
+					"graph cache: %v", err)
+			}
+		}()
+	} else {
+		if err := c.populateCache(ctx); err != nil {
+			return fmt.Errorf("could not populate the graph "+
+				"cache: %w", err)
+		}
 	}
 
 	c.wg.Add(1)
@@ -167,12 +179,21 @@ func (c *ChannelGraph) handleTopologySubscriptions(ctx context.Context) {
 
 // populateCache loads the entire channel graph into the in-memory graph cache.
 func (c *ChannelGraph) populateCache(ctx context.Context) error {
-	if c.graphCache == nil {
+	if c.cache == nil {
 		log.Info("In-memory channel graph cache disabled")
 
 		return nil
 	}
 
+	c.cache.beginPopulation()
+
+	loaded := false
+	defer func() {
+		c.cache.finishPopulation(loaded)
+	}()
+
+	cache := c.cache.graphCache
+
 	startTime := time.Now()
 	log.Info("Populating in-memory channel graph, this might take a " +
 		"while...")
@@ -186,7 +207,7 @@ func (c *ChannelGraph) populateCache(ctx context.Context) error {
 			func(node route.Vertex,
 				features *lnwire.FeatureVector) error {
 
-				c.graphCache.AddNodeFeatures(node, features)
+				cache.AddNodeFeatures(node, features)
 
 				return nil
 			}, func() {},
@@ -203,7 +224,7 @@ func (c *ChannelGraph) populateCache(ctx context.Context) error {
 				policy1,
 				policy2 *models.CachedEdgePolicy) error {
 
-				c.graphCache.AddChannel(info, policy1, policy2)
+				cache.AddChannel(info, policy1, policy2)
 
 				return nil
 			}, func() {},
@@ -215,10 +236,10 @@ func (c *ChannelGraph) populateCache(ctx context.Context) error {
 		}
 	}
 
-	c.cacheLoaded.Store(true)
+	loaded = true
 
 	log.Infof("Finished populating in-memory channel graph (took %v, %s)",
-		time.Since(startTime), c.graphCache.Stats())
+		time.Since(startTime), cache.Stats())
 
 	return nil
 }
@@ -237,8 +258,8 @@ func (c *ChannelGraph) ForEachNodeDirectedChannel(ctx context.Context,
 	node route.Vertex, cb func(channel *DirectedChannel) error,
 	reset func()) error {
 
-	if c.graphCache != nil && c.cacheLoaded.Load() {
-		return c.graphCache.ForEachChannel(node, cb)
+	if c.cache != nil && c.cache.isLoaded() {
+		return c.cache.graphCache.ForEachChannel(node, cb)
 	}
 
 	// TODO(elle): once the no-cache path needs to support
@@ -258,8 +279,8 @@ func (c *ChannelGraph) ForEachNodeDirectedChannel(ctx context.Context,
 func (c *ChannelGraph) FetchNodeFeatures(ctx context.Context,
 	node route.Vertex) (*lnwire.FeatureVector, error) {
 
-	if c.graphCache != nil && c.cacheLoaded.Load() {
-		return c.graphCache.GetFeatures(node), nil
+	if c.cache != nil && c.cache.isLoaded() {
+		return c.cache.graphCache.GetFeatures(node), nil
 	}
 
 	return c.db.FetchNodeFeatures(ctx, lnwire.GossipVersion1, node)
@@ -272,7 +293,7 @@ func (c *ChannelGraph) FetchNodeFeatures(ctx context.Context,
 func (c *ChannelGraph) GraphSession(ctx context.Context,
 	cb func(graph NodeTraverser) error, reset func()) error {
 
-	if c.graphCache != nil && c.cacheLoaded.Load() {
+	if c.cache != nil && c.cache.isLoaded() {
 		return cb(c)
 	}
 
@@ -288,8 +309,8 @@ func (c *ChannelGraph) ForEachNodeCached(ctx context.Context,
 	cb func(ctx context.Context, node route.Vertex, addrs []net.Addr,
 		chans map[uint64]*DirectedChannel) error, reset func()) error {
 
-	if !withAddrs && c.graphCache != nil && c.cacheLoaded.Load() {
-		return c.graphCache.ForEachNode(
+	if !withAddrs && c.cache != nil && c.cache.isLoaded() {
+		return c.cache.graphCache.ForEachNode(
 			func(node route.Vertex,
 				channels map[uint64]*DirectedChannel) error {
 
@@ -315,10 +336,12 @@ func (c *ChannelGraph) AddNode(ctx context.Context,
 		return err
 	}
 
-	if c.graphCache != nil {
-		c.graphCache.AddNodeFeatures(
-			node.PubKeyBytes, node.Features,
-		)
+	if c.cache != nil {
+		c.cache.applyUpdate(func(cache *GraphCache) {
+			cache.AddNodeFeatures(
+				node.PubKeyBytes, node.Features,
+			)
+		})
 	}
 
 	select {
@@ -344,8 +367,10 @@ func (c *ChannelGraph) AddChannelEdge(ctx context.Context,
 		return err
 	}
 
-	if c.graphCache != nil {
-		c.graphCache.AddChannel(models.NewCachedEdge(edge), nil, nil)
+	if c.cache != nil {
+		c.cache.applyUpdate(func(cache *GraphCache) {
+			cache.AddChannel(models.NewCachedEdge(edge), nil, nil)
+		})
 	}
 
 	select {
@@ -368,7 +393,7 @@ func (c *ChannelGraph) MarkEdgeLive(ctx context.Context,
 		return err
 	}
 
-	if c.graphCache != nil {
+	if c.cache != nil {
 		// We need to add the channel back into our graph cache,
 		// otherwise we won't use it for path finding.
 		infos, err := c.db.FetchChanInfos(ctx, v, []uint64{chanID})
@@ -390,9 +415,12 @@ func (c *ChannelGraph) MarkEdgeLive(ctx context.Context,
 			policy2 = models.NewCachedPolicy(info.Policy2)
 		}
 
-		c.graphCache.AddChannel(
-			models.NewCachedEdge(info.Info), policy1, policy2,
-		)
+		c.cache.applyUpdate(func(cache *GraphCache) {
+			cache.AddChannel(
+				models.NewCachedEdge(info.Info),
+				policy1, policy2,
+			)
+		})
 	}
 
 	return nil
@@ -417,13 +445,15 @@ func (c *ChannelGraph) DeleteChannelEdges(ctx context.Context,
 		return err
 	}
 
-	if c.graphCache != nil {
-		for _, info := range infos {
-			c.graphCache.RemoveChannel(
-				info.NodeKey1Bytes, info.NodeKey2Bytes,
-				info.ChannelID,
-			)
-		}
+	if c.cache != nil {
+		c.cache.applyUpdate(func(cache *GraphCache) {
+			for _, info := range infos {
+				cache.RemoveChannel(
+					info.NodeKey1Bytes, info.NodeKey2Bytes,
+					info.ChannelID,
+				)
+			}
+		})
 	}
 
 	return err
@@ -444,13 +474,15 @@ func (c *ChannelGraph) DisconnectBlockAtHeight(ctx context.Context,
 		return nil, err
 	}
 
-	if c.graphCache != nil {
-		for _, edge := range edges {
-			c.graphCache.RemoveChannel(
-				edge.NodeKey1Bytes, edge.NodeKey2Bytes,
-				edge.ChannelID,
-			)
-		}
+	if c.cache != nil {
+		c.cache.applyUpdate(func(cache *GraphCache) {
+			for _, edge := range edges {
+				cache.RemoveChannel(
+					edge.NodeKey1Bytes, edge.NodeKey2Bytes,
+					edge.ChannelID,
+				)
+			}
+		})
 	}
 
 	return edges, nil
@@ -475,20 +507,22 @@ func (c *ChannelGraph) PruneGraph(ctx context.Context,
 		return nil, err
 	}
 
-	if c.graphCache != nil {
-		for _, edge := range edges {
-			c.graphCache.RemoveChannel(
-				edge.NodeKey1Bytes, edge.NodeKey2Bytes,
-				edge.ChannelID,
-			)
-		}
+	if c.cache != nil {
+		c.cache.applyUpdate(func(cache *GraphCache) {
+			for _, edge := range edges {
+				cache.RemoveChannel(
+					edge.NodeKey1Bytes, edge.NodeKey2Bytes,
+					edge.ChannelID,
+				)
+			}
+			for _, node := range nodes {
+				cache.RemoveNode(node)
+			}
+		})
 
-		for _, node := range nodes {
-			c.graphCache.RemoveNode(node)
+		if stats, ok := c.cache.stats(); ok {
+			log.Debugf("Pruned graph, cache now has %s", stats)
 		}
-
-		log.Debugf("Pruned graph, cache now has %s",
-			c.graphCache.Stats())
 	}
 
 	if len(edges) != 0 {
@@ -518,10 +552,12 @@ func (c *ChannelGraph) PruneGraphNodes(ctx context.Context) error {
 		return err
 	}
 
-	if c.graphCache != nil {
-		for _, node := range nodes {
-			c.graphCache.RemoveNode(node)
-		}
+	if c.cache != nil {
+		c.cache.applyUpdate(func(cache *GraphCache) {
+			for _, node := range nodes {
+				cache.RemoveNode(node)
+			}
+		})
 	}
 
 	return nil
@@ -589,8 +625,10 @@ func (c *ChannelGraph) MarkEdgeZombie(ctx context.Context,
 		return err
 	}
 
-	if c.graphCache != nil {
-		c.graphCache.RemoveChannel(pubKey1, pubKey2, chanID)
+	if c.cache != nil {
+		c.cache.applyUpdate(func(cache *GraphCache) {
+			cache.RemoveChannel(pubKey1, pubKey2, chanID)
+		})
 	}
 
 	return nil
@@ -611,10 +649,12 @@ func (c *ChannelGraph) UpdateEdgePolicy(ctx context.Context,
 		return err
 	}
 
-	if c.graphCache != nil {
-		c.graphCache.UpdatePolicy(
-			models.NewCachedPolicy(edge), from, to,
-		)
+	if c.cache != nil {
+		c.cache.applyUpdate(func(cache *GraphCache) {
+			cache.UpdatePolicy(
+				models.NewCachedPolicy(edge), from, to,
+			)
+		})
 	}
 
 	select {
@@ -820,8 +860,8 @@ func NewVersionedGraph(c *ChannelGraph,
 func (c *VersionedGraph) FetchNodeFeatures(ctx context.Context,
 	node route.Vertex) (*lnwire.FeatureVector, error) {
 
-	if c.graphCache != nil {
-		return c.graphCache.GetFeatures(node), nil
+	if c.cache != nil && c.cache.isLoaded() {
+		return c.cache.graphCache.GetFeatures(node), nil
 	}
 
 	return c.db.FetchNodeFeatures(ctx, c.v, node)
@@ -837,8 +877,8 @@ func (c *VersionedGraph) ForEachNodeDirectedChannel(ctx context.Context,
 	node route.Vertex, cb func(channel *DirectedChannel) error,
 	reset func()) error {
 
-	if c.graphCache != nil {
-		return c.graphCache.ForEachChannel(node, cb)
+	if c.cache != nil && c.cache.isLoaded() {
+		return c.cache.graphCache.ForEachChannel(node, cb)
 	}
 
 	return c.db.ForEachNodeDirectedChannel(ctx, c.v, node, cb, reset)
@@ -891,7 +931,7 @@ func (c *VersionedGraph) ChannelView(ctx context.Context) ([]EdgePoint,
 func (c *VersionedGraph) GraphSession(ctx context.Context,
 	cb func(graph NodeTraverser) error, reset func()) error {
 
-	if c.graphCache != nil {
+	if c.cache != nil && c.cache.isLoaded() {
 		return cb(c)
 	}
 
@@ -951,8 +991,10 @@ func (c *VersionedGraph) DeleteNode(ctx context.Context,
 		return err
 	}
 
-	if c.graphCache != nil {
-		c.graphCache.RemoveNode(nodePub)
+	if c.cache != nil {
+		c.cache.applyUpdate(func(cache *GraphCache) {
+			cache.RemoveNode(nodePub)
+		})
 	}
 
 	return nil
@@ -1096,7 +1138,13 @@ func MakeTestGraph(t testing.TB,
 
 	store := NewTestDB(t)
 
-	graph, err := NewChannelGraph(store, opts...)
+	// Default to synchronous cache population in tests so that the
+	// cache is fully loaded before the test proceeds.
+	allOpts := append(
+		[]ChanGraphOption{WithSyncGraphCachePopulation()}, opts...,
+	)
+
+	graph, err := NewChannelGraph(store, allOpts...)
 	require.NoError(t, err)
 	require.NoError(t, graph.Start())
 
diff --git a/graph/db/graph_cache_state.go b/graph/db/graph_cache_state.go
new file mode 100644
index 0000000..716d770
--- /dev/null
+++ b/graph/db/graph_cache_state.go
@@ -0,0 +1,105 @@
+package graphdb
+
+import (
+	"sync"
+	"sync/atomic"
+)
+
+// pendingUpdatesWarnThreshold is the number of buffered cache mutations at
+// which a warning is logged. A large buffer indicates that cache population is
+// taking a long time relative to the incoming gossip rate.
+const pendingUpdatesWarnThreshold = 10_000
+
+// graphCacheState tracks the in-memory graph cache together with its
+// population state. The underlying GraphCache is independently thread-safe, so
+// once reads are allowed to use it, they do not need to hold updateMtx.
+type graphCacheState struct {
+	graphCache *GraphCache
+	loaded     atomic.Bool
+	failed     atomic.Bool
+
+	updateMtx sync.Mutex
+	loading   bool
+
+	pendingUpdates []func(*GraphCache)
+}
+
+// newGraphCacheState constructs a graph cache state with a new cache instance.
+func newGraphCacheState(preAllocNumNodes int) *graphCacheState {
+	return &graphCacheState{
+		graphCache: NewGraphCache(preAllocNumNodes),
+	}
+}
+
+// isLoaded reports whether the cache has finished its initial population and
+// is safe to serve reads from.
+func (s *graphCacheState) isLoaded() bool {
+	return s.loaded.Load()
+}
+
+// isFailed reports whether the cache population attempt has failed.
+func (s *graphCacheState) isFailed() bool {
+	return s.failed.Load()
+}
+
+// stats returns the cache stats if the cache has finished its initial
+// population.
+func (s *graphCacheState) stats() (string, bool) {
+	if !s.isLoaded() {
+		return "", false
+	}
+
+	return s.graphCache.Stats(), true
+}
+
+// beginPopulation marks the cache as loading and starts buffering concurrent
+// cache mutations until the population pass completes.
+func (s *graphCacheState) beginPopulation() {
+	s.updateMtx.Lock()
+	defer s.updateMtx.Unlock()
+
+	s.loading = true
+	s.pendingUpdates = nil
+}
+
+// finishPopulation replays any buffered mutations and marks the cache as ready
+// when the initial population completed successfully. If population failed,
+// buffered mutations are discarded since the cache won't be used for reads.
+func (s *graphCacheState) finishPopulation(loaded bool) {
+	s.updateMtx.Lock()
+	defer s.updateMtx.Unlock()
+
+	if loaded {
+		for _, update := range s.pendingUpdates {
+			update(s.graphCache)
+		}
+
+		s.loaded.Store(true)
+	} else {
+		s.failed.Store(true)
+	}
+
+	s.pendingUpdates = nil
+	s.loading = false
+}
+
+// applyUpdate applies a cache mutation immediately or buffers it when the
+// cache is still being populated.
+func (s *graphCacheState) applyUpdate(update func(cache *GraphCache)) {
+	s.updateMtx.Lock()
+	defer s.updateMtx.Unlock()
+
+	if s.loading {
+		s.pendingUpdates = append(s.pendingUpdates, update)
+
+		if len(s.pendingUpdates)%pendingUpdatesWarnThreshold == 0 {
+			log.Warnf("Graph cache has %d pending updates "+
+				"buffered during population",
+				len(s.pendingUpdates))
+		}
+
+		return
+	}
+
+	update(s.graphCache)
+}
diff --git a/graph/db/graph_test.go b/graph/db/graph_test.go
index 13f24ed..f82ed51 100644
--- a/graph/db/graph_test.go
+++ b/graph/db/graph_test.go
@@ -24,6 +24,7 @@ import (
 	"github.com/lightningnetwork/lnd/fn/v2"
 	"github.com/lightningnetwork/lnd/graph/db/models"
 	"github.com/lightningnetwork/lnd/kvdb"
+	"github.com/lightningnetwork/lnd/lntest/wait"
 	"github.com/lightningnetwork/lnd/lnwire"
 	"github.com/lightningnetwork/lnd/routing/route"
 	"github.com/stretchr/testify/require"
@@ -440,7 +441,9 @@ func testPartialNode(t *testing.T, v lnwire.GossipVersion) {
 	t.Parallel()
 	ctx := t.Context()
 
-	graph := NewVersionedGraph(MakeTestGraph(t), v)
+	graph := NewVersionedGraph(
+		MakeTestGraph(t, WithSyncGraphCachePopulation()), v,
+	)
 
 	// To insert a partial node, we need to add a channel edge that has
 	// node keys for nodes we are not yet aware of.
@@ -612,7 +615,9 @@ func testEdgeInsertionDeletion(t *testing.T, v lnwire.GossipVersion) {
 	t.Parallel()
 	ctx := t.Context()
 
-	graph := NewVersionedGraph(MakeTestGraph(t), v)
+	graph := NewVersionedGraph(
+		MakeTestGraph(t, WithSyncGraphCachePopulation()), v,
+	)
 
 	// We'd like to test the insertion/deletion of edges, so we create two
 	// vertexes to connect.
@@ -849,7 +854,7 @@ func TestDisconnectBlockAtHeight(t *testing.T) {
 	t.Parallel()
 	ctx := t.Context()
 
-	graph := MakeTestGraph(t)
+	graph := MakeTestGraph(t, WithSyncGraphCachePopulation())
 
 	sourceNode := createTestVertex(t, lnwire.GossipVersion1)
 	require.NoError(t, graph.SetSourceNode(ctx, sourceNode))
@@ -1148,7 +1153,9 @@ func testEdgeInfoUpdates(t *testing.T, v lnwire.GossipVersion) {
 	t.Parallel()
 	ctx := t.Context()
 
-	graph := NewVersionedGraph(MakeTestGraph(t), v)
+	graph := NewVersionedGraph(
+		MakeTestGraph(t, WithSyncGraphCachePopulation()), v,
+	)
 
 	// We'd like to test the update of edges inserted into the database, so
 	// we create two vertexes to connect.
@@ -1166,7 +1173,7 @@ func testEdgeInfoUpdates(t *testing.T, v lnwire.GossipVersion) {
 	// is added, will fail.
 	err := graph.UpdateEdgePolicy(ctx, edge1)
 	require.ErrorIs(t, err, ErrEdgeNotFound)
-	require.Len(t, graph.graphCache.nodeChannels, 0)
+	require.Len(t, graph.cache.graphCache.nodeChannels, 0)
 
 	// Add the edge info.
 	require.NoError(t, graph.AddChannelEdge(ctx, edgeInfo))
@@ -1329,8 +1336,9 @@ func assertNodeInCache(t *testing.T, g *ChannelGraph, n *models.Node,
 	expectedFeatures *lnwire.FeatureVector) {
 
 	// Let's check the internal view first.
+	nodeFeatures := g.cache.graphCache.nodeFeatures
 	require.Equal(
-		t, expectedFeatures, g.graphCache.nodeFeatures[n.PubKeyBytes],
+		t, expectedFeatures, nodeFeatures[n.PubKeyBytes],
 	)
 
 	// The external view should reflect this as well. Except when we expect
@@ -1339,16 +1347,19 @@ func assertNodeInCache(t *testing.T, g *ChannelGraph, n *models.Node,
 	if expectedFeatures == nil {
 		expectedFeatures = lnwire.EmptyFeatureVector()
 	}
-	features := g.graphCache.GetFeatures(n.PubKeyBytes)
+	features := g.cache.graphCache.GetFeatures(n.PubKeyBytes)
 	require.Equal(t, expectedFeatures, features)
 }
 
 func assertNodeNotInCache(t *testing.T, g *ChannelGraph, n route.Vertex) {
-	_, ok := g.graphCache.nodeFeatures[n]
+	_, ok := g.cache.graphCache.nodeFeatures[n]
+	require.False(t, ok)
+
+	_, ok = g.cache.graphCache.nodeChannels[n]
 	require.False(t, ok)
 
 	// We should get the default features for this node.
-	features := g.graphCache.GetFeatures(n)
+	features := g.cache.graphCache.GetFeatures(n)
 	require.Equal(t, lnwire.EmptyFeatureVector(), features)
 }
 
@@ -1356,8 +1367,8 @@ func assertEdgeWithNoPoliciesInCache(t *testing.T, g *ChannelGraph,
 	e *models.ChannelEdgeInfo) {
 
 	// Let's check the internal view first.
-	require.NotEmpty(t, g.graphCache.nodeChannels[e.NodeKey1Bytes])
-	require.NotEmpty(t, g.graphCache.nodeChannels[e.NodeKey2Bytes])
+	require.NotEmpty(t, g.cache.graphCache.nodeChannels[e.NodeKey1Bytes])
+	require.NotEmpty(t, g.cache.graphCache.nodeChannels[e.NodeKey2Bytes])
 
 	expectedNode1Channel := &DirectedChannel{
 		ChannelID:    e.ChannelID,
@@ -1367,12 +1378,13 @@ func assertEdgeWithNoPoliciesInCache(t *testing.T, g *ChannelGraph,
 		OutPolicySet: false,
 		InPolicy:     nil,
 	}
+	nodeChannels := g.cache.graphCache.nodeChannels
 	require.Contains(
-		t, g.graphCache.nodeChannels[e.NodeKey1Bytes], e.ChannelID,
+		t, nodeChannels[e.NodeKey1Bytes], e.ChannelID,
 	)
 	require.Equal(
 		t, expectedNode1Channel,
-		g.graphCache.nodeChannels[e.NodeKey1Bytes][e.ChannelID],
+		nodeChannels[e.NodeKey1Bytes][e.ChannelID],
 	)
 
 	expectedNode2Channel := &DirectedChannel{
@@ -1384,16 +1396,16 @@ func assertEdgeWithNoPoliciesInCache(t *testing.T, g *ChannelGraph,
 		InPolicy:     nil,
 	}
 	require.Contains(
-		t, g.graphCache.nodeChannels[e.NodeKey2Bytes], e.ChannelID,
+		t, nodeChannels[e.NodeKey2Bytes], e.ChannelID,
 	)
 	require.Equal(
 		t, expectedNode2Channel,
-		g.graphCache.nodeChannels[e.NodeKey2Bytes][e.ChannelID],
+		nodeChannels[e.NodeKey2Bytes][e.ChannelID],
 	)
 
 	// The external view should reflect this as well.
 	var foundChannel *DirectedChannel
-	err := g.graphCache.ForEachChannel(
+	err := g.cache.graphCache.ForEachChannel(
 		e.NodeKey1Bytes, func(c *DirectedChannel) error {
 			if c.ChannelID == e.ChannelID {
 				foundChannel = c
@@ -1406,7 +1418,7 @@ func assertEdgeWithNoPoliciesInCache(t *testing.T, g *ChannelGraph,
 	require.NotNil(t, foundChannel)
 	require.Equal(t, expectedNode1Channel, foundChannel)
 
-	err = g.graphCache.ForEachChannel(
+	err = g.cache.graphCache.ForEachChannel(
 		e.NodeKey2Bytes, func(c *DirectedChannel) error {
 			if c.ChannelID == e.ChannelID {
 				foundChannel = c
@@ -1423,7 +1435,7 @@ func assertEdgeWithNoPoliciesInCache(t *testing.T, g *ChannelGraph,
 func assertNoEdge(t *testing.T, g *ChannelGraph, chanID uint64) {
 	// Make sure no channel in the cache has the given channel ID. If there
 	// are no channels at all, that is fine as well.
-	for _, channels := range g.graphCache.nodeChannels {
+	for _, channels := range g.cache.graphCache.nodeChannels {
 		for _, channel := range channels {
 			require.NotEqual(t, channel.ChannelID, chanID)
 		}
@@ -1434,7 +1446,7 @@ func assertEdgeWithPolicyInCache(t *testing.T, g *ChannelGraph,
 	e *models.ChannelEdgeInfo, p *models.ChannelEdgePolicy, policy1 bool) {
 
 	// Check the internal state first.
-	c1, ok := g.graphCache.nodeChannels[e.NodeKey1Bytes][e.ChannelID]
+	c1, ok := g.cache.graphCache.nodeChannels[e.NodeKey1Bytes][e.ChannelID]
 	require.True(t, ok)
 
 	if policy1 {
@@ -1447,7 +1459,7 @@ func assertEdgeWithPolicyInCache(t *testing.T, g *ChannelGraph,
 		)
 	}
 
-	c2, ok := g.graphCache.nodeChannels[e.NodeKey2Bytes][e.ChannelID]
+	c2, ok := g.cache.graphCache.nodeChannels[e.NodeKey2Bytes][e.ChannelID]
 	require.True(t, ok)
 
 	if policy1 {
@@ -1465,14 +1477,14 @@ func assertEdgeWithPolicyInCache(t *testing.T, g *ChannelGraph,
 		c1Ext *DirectedChannel
 		c2Ext *DirectedChannel
 	)
-	require.NoError(t, g.graphCache.ForEachChannel(
+	require.NoError(t, g.cache.graphCache.ForEachChannel(
 		e.NodeKey1Bytes, func(c *DirectedChannel) error {
 			c1Ext = c
 
 			return nil
 		},
 	))
-	require.NoError(t, g.graphCache.ForEachChannel(
+	require.NoError(t, g.cache.graphCache.ForEachChannel(
 		e.NodeKey2Bytes, func(c *DirectedChannel) error {
 			c2Ext = c
 
@@ -5137,7 +5149,9 @@ func TestGraphLoading(t *testing.T) {
 	// Next, create the graph for the first time.
 	graphStore := NewTestDB(t)
 
-	graph, err := NewChannelGraph(graphStore)
+	graph, err := NewChannelGraph(
+		graphStore, WithSyncGraphCachePopulation(),
+	)
 	require.NoError(t, err)
 	require.NoError(t, graph.Start())
 	t.Cleanup(func() {
@@ -5153,7 +5167,9 @@ func TestGraphLoading(t *testing.T) {
 
 	// Recreate the graph. This should cause the graph cache to be
 	// populated.
-	graphReloaded, err := NewChannelGraph(graphStore)
+	graphReloaded, err := NewChannelGraph(
+		graphStore, WithSyncGraphCachePopulation(),
+	)
 	require.NoError(t, err)
 	require.NoError(t, graphReloaded.Start())
 	t.Cleanup(func() {
@@ -5162,14 +5178,444 @@ func TestGraphLoading(t *testing.T) {
 
 	// Assert that the cache content is identical.
 	require.Equal(
-		t, graph.graphCache.nodeChannels,
-		graphReloaded.graphCache.nodeChannels,
+		t, graph.cache.graphCache.nodeChannels,
+		graphReloaded.cache.graphCache.nodeChannels,
 	)
 
 	require.Equal(
-		t, graph.graphCache.nodeFeatures,
-		graphReloaded.graphCache.nodeFeatures,
+		t, graph.cache.graphCache.nodeFeatures,
+		graphReloaded.cache.graphCache.nodeFeatures,
+	)
+}
+
+// TestAsyncGraphCache tests the behaviour of the ChannelGraph when the graph
+// cache is populated asynchronously.
+func TestAsyncGraphCache(t *testing.T) {
+	t.Parallel()
+	ctx := t.Context()
+
+	const (
+		numNodes    = 100
+		numChannels = 3
+	)
+
+	// Next, create the graph for the first time.
+	graphStore := NewTestDB(t)
+
+	// The first time we spin up the graph, we Start is as normal and fill
+	// it with test data. This will ensure that the graph cache has
+	// something to load on the next Start.
+	graph, err := NewChannelGraph(graphStore)
+	require.NoError(t, err)
+	require.NoError(t, graph.Start())
+	channels, nodes := fillTestGraph(
+		t, graph, numNodes, numChannels, lnwire.GossipVersion1,
+	)
+
+	assertGraphState := func() {
+		var (
+			numNodes  int
+			chanIndex = make(map[uint64]struct{}, numChannels)
+		)
+
+		// We query the graph for all nodes and channels, and
+		// assert that we get the expected number of nodes and
+		// channels.
+		err := graph.ForEachNodeCached(
+			ctx, lnwire.GossipVersion1, false,
+			func(_ context.Context, node route.Vertex,
+				_ []net.Addr,
+				chans map[uint64]*DirectedChannel) error {
+
+				numNodes++
+				for chanID := range chans {
+					chanIndex[chanID] = struct{}{}
+				}
+
+				return nil
+			}, func() {
+				numNodes = 0
+				chanIndex = make(
+					map[uint64]struct{}, numChannels,
+				)
+			},
+		)
+		require.NoError(t, err)
+
+		require.Equal(t, len(nodes), numNodes)
+		require.Equal(t, len(channels), len(chanIndex))
+	}
+
+	assertGraphState()
+
+	// Now we stop the graph.
+	require.NoError(t, graph.Stop())
+
+	// Recreate it but don't start it yet.
+	graph, err = NewChannelGraph(graphStore)
+	require.NoError(t, err)
+
+	// Spin off a goroutine that starts to make queries to the ChannelGraph.
+	// We start this before we start the graph, so that we can ensure that
+	// the queries are made while the graph cache is being populated.
+	var (
+		wg      sync.WaitGroup
+		numRuns = 10
+	)
+	for i := 0; i < numRuns; i++ {
+		wg.Add(1)
+		go func() {
+			defer wg.Done()
+
+			assertGraphState()
+		}()
+	}
+
+	require.NoError(t, graph.Start())
+	t.Cleanup(func() {
+		require.NoError(t, graph.Stop())
+	})
+
+	wg.Wait()
+
+	// Wait for the cache to be fully populated.
+	err = wait.Predicate(func() bool {
+		return graph.cache.isLoaded()
+	}, wait.DefaultTimeout)
+	require.NoError(t, err)
+
+	// And then assert that all the expected nodes and channels are
+	// present in the graph cache.
+	for _, node := range nodes {
+		_, ok := graph.cache.graphCache.nodeChannels[node.PubKeyBytes]
+		require.True(t, ok)
+	}
+}
+
+type blockingCacheLoadStore struct {
+	Store
+
+	cacheLoadStarted chan struct{}
+	allowCacheLoad   chan struct{}
+	blockOnce        sync.Once
+}
+
+// ForEachChannelCacheable pauses the first cacheable channel iteration until
+// the test allows it to continue.
+func (s *blockingCacheLoadStore) ForEachChannelCacheable(ctx context.Context,
+	v lnwire.GossipVersion, cb func(*models.CachedEdgeInfo,
+		*models.CachedEdgePolicy, *models.CachedEdgePolicy) error,
+	reset func()) error {
+
+	return s.Store.ForEachChannelCacheable(
+		ctx, v, func(info *models.CachedEdgeInfo,
+			policy1,
+			policy2 *models.CachedEdgePolicy) error {
+
+			s.blockOnce.Do(func() {
+				close(s.cacheLoadStarted)
+				<-s.allowCacheLoad
+			})
+
+			return cb(info, policy1, policy2)
+		}, reset,
+	)
+}
+
+type shutdownBlockingCacheLoadStore struct {
+	Store
+
+	cacheLoadStarted chan struct{}
+	blockOnce        sync.Once
+}
+
+// ForEachChannelCacheable blocks until the context is canceled so tests can
+// assert that Stop interrupts async cache population.
+func (s *shutdownBlockingCacheLoadStore) ForEachChannelCacheable(
+	ctx context.Context, v lnwire.GossipVersion,
+	cb func(*models.CachedEdgeInfo, *models.CachedEdgePolicy,
+		*models.CachedEdgePolicy) error, reset func()) error {
+
+	return s.Store.ForEachChannelCacheable(
+		ctx, v, func(info *models.CachedEdgeInfo,
+			policy1,
+			policy2 *models.CachedEdgePolicy) error {
+
+			s.blockOnce.Do(func() {
+				close(s.cacheLoadStarted)
+				<-ctx.Done()
+			})
+
+			return ctx.Err()
+		}, reset,
+	)
+}
+
+type failingCacheLoadStore struct {
+	Store
+
+	cacheLoadAttempted chan struct{}
+	populateErr        error
+}
+
+// ForEachChannelCacheable fails the initial cache population after signaling
+// that the async load reached channel iteration.
+func (s *failingCacheLoadStore) ForEachChannelCacheable(ctx context.Context,
+	v lnwire.GossipVersion, cb func(*models.CachedEdgeInfo,
+		*models.CachedEdgePolicy, *models.CachedEdgePolicy) error,
+	reset func()) error {
+
+	close(s.cacheLoadAttempted)
+
+	return s.populateErr
+}
+
+// TestAsyncGraphCacheReplaysConcurrentWrites asserts that graph mutations that
+// happen while the async cache population is running are replayed onto the
+// cache before it becomes readable.
+func TestAsyncGraphCacheReplaysConcurrentWrites(t *testing.T) {
+	t.Parallel()
+	ctx := t.Context()
+
+	store := NewTestDB(t)
+
+	setupGraph, err := NewChannelGraph(
+		store, WithSyncGraphCachePopulation(),
+	)
+	require.NoError(t, err)
+	require.NoError(t, setupGraph.Start())
+
+	node1 := createTestVertex(t, lnwire.GossipVersion1)
+	require.NoError(t, setupGraph.AddNode(ctx, node1))
+	node2 := createTestVertex(t, lnwire.GossipVersion1)
+	require.NoError(t, setupGraph.AddNode(ctx, node2))
+
+	edgeInfo, edge1, edge2 := createChannelEdge(
+		node1, node2, lnwire.GossipVersion1,
+	)
+	require.NoError(t, setupGraph.AddChannelEdge(ctx, edgeInfo))
+	require.NoError(t, setupGraph.UpdateEdgePolicy(ctx, edge1))
+	require.NoError(t, setupGraph.UpdateEdgePolicy(ctx, edge2))
+	require.NoError(t, setupGraph.Stop())
+
+	blockingStore := &blockingCacheLoadStore{
+		Store:            store,
+		cacheLoadStarted: make(chan struct{}),
+		allowCacheLoad:   make(chan struct{}),
+	}
+
+	graph, err := NewChannelGraph(blockingStore)
+	require.NoError(t, err)
+	require.NoError(t, graph.Start())
+	t.Cleanup(func() {
+		require.NoError(t, graph.Stop())
+	})
+
+	<-blockingStore.cacheLoadStarted
+
+	updatedEdge := *edge1
+	updatedEdge.LastUpdate = nextUpdateTime()
+	updatedEdge.FeeBaseMSat++
+	require.NoError(t, graph.UpdateEdgePolicy(ctx, &updatedEdge))
+
+	close(blockingStore.allowCacheLoad)
+
+	err = wait.Predicate(func() bool {
+		return graph.cache.isLoaded()
+	}, wait.DefaultTimeout)
+	require.NoError(t, err)
+
+	var cachedFee lnwire.MilliSatoshi
+	err = graph.ForEachNodeDirectedChannel(
+		ctx, updatedEdge.ToNode,
+		func(channel *DirectedChannel) error {
+			if channel.ChannelID != updatedEdge.ChannelID {
+				return nil
+			}
+
+			require.NotNil(t, channel.InPolicy)
+			cachedFee = channel.InPolicy.FeeBaseMSat
+
+			return nil
+		}, func() {},
+	)
+	require.NoError(t, err)
+	require.Equal(t, updatedEdge.FeeBaseMSat, cachedFee)
+}
+
+// TestAsyncGraphCacheStopCancelsLoad asserts that Stop interrupts async cache
+// population instead of waiting for the full load to finish.
+func TestAsyncGraphCacheStopCancelsLoad(t *testing.T) {
+	t.Parallel()
+	ctx := t.Context()
+
+	store := NewTestDB(t)
+
+	setupGraph, err := NewChannelGraph(
+		store, WithSyncGraphCachePopulation(),
+	)
+	require.NoError(t, err)
+	require.NoError(t, setupGraph.Start())
+
+	node1 := createTestVertex(t, lnwire.GossipVersion1)
+	require.NoError(t, setupGraph.AddNode(ctx, node1))
+	node2 := createTestVertex(t, lnwire.GossipVersion1)
+	require.NoError(t, setupGraph.AddNode(ctx, node2))
+
+	edgeInfo, edge1, edge2 := createChannelEdge(
+		node1, node2, lnwire.GossipVersion1,
+	)
+	require.NoError(t, setupGraph.AddChannelEdge(ctx, edgeInfo))
+	require.NoError(t, setupGraph.UpdateEdgePolicy(ctx, edge1))
+	require.NoError(t, setupGraph.UpdateEdgePolicy(ctx, edge2))
+	require.NoError(t, setupGraph.Stop())
+
+	blockingStore := &shutdownBlockingCacheLoadStore{
+		Store:            store,
+		cacheLoadStarted: make(chan struct{}),
+	}
+
+	graph, err := NewChannelGraph(blockingStore)
+	require.NoError(t, err)
+	require.NoError(t, graph.Start())
+
+	<-blockingStore.cacheLoadStarted
+
+	stopErr := make(chan error, 1)
+	go func() {
+		stopErr <- graph.Stop()
+	}()
+
+	select {
+	case err := <-stopErr:
+		require.NoError(t, err)
+
+	case <-time.After(wait.DefaultTimeout):
+		t.Fatal("Stop did not cancel graph cache loading")
+	}
+}
+
+// TestAsyncGraphCachePopulationFailureFallsBackToDB asserts that cache
+// population errors leave the cache unreadable while reads continue to succeed
+// through the DB-backed path.
+func TestAsyncGraphCachePopulationFailureFallsBackToDB(t *testing.T) {
+	t.Parallel()
+	ctx := t.Context()
+
+	store := NewTestDB(t)
+
+	setupGraph, err := NewChannelGraph(
+		store, WithSyncGraphCachePopulation(),
+	)
+	require.NoError(t, err)
+	require.NoError(t, setupGraph.Start())
+
+	node1 := createTestVertex(t, lnwire.GossipVersion1)
+	require.NoError(t, setupGraph.AddNode(ctx, node1))
+	node2 := createTestVertex(t, lnwire.GossipVersion1)
+	require.NoError(t, setupGraph.AddNode(ctx, node2))
+
+	edgeInfo, edge1, edge2 := createChannelEdge(
+		node1, node2, lnwire.GossipVersion1,
+	)
+	require.NoError(t, setupGraph.AddChannelEdge(ctx, edgeInfo))
+	require.NoError(t, setupGraph.UpdateEdgePolicy(ctx, edge1))
+	require.NoError(t, setupGraph.UpdateEdgePolicy(ctx, edge2))
+	require.NoError(t, setupGraph.Stop())
+
+	populateErr := errors.New("cache population failed")
+	failingStore := &failingCacheLoadStore{
+		Store:              store,
+		cacheLoadAttempted: make(chan struct{}),
+		populateErr:        populateErr,
+	}
+
+	graph, err := NewChannelGraph(failingStore)
+	require.NoError(t, err)
+	require.NoError(t, graph.Start())
+	t.Cleanup(func() {
+		require.NoError(t, graph.Stop())
+	})
+
+	<-failingStore.cacheLoadAttempted
+	require.False(t, graph.cache.isLoaded())
+
+	var numChannels int
+	err = graph.ForEachNodeDirectedChannel(
+		ctx, edge1.ToNode,
+		func(channel *DirectedChannel) error {
+			if channel.ChannelID != edge1.ChannelID {
+				return nil
+			}
+
+			numChannels++
+			require.NotNil(t, channel.InPolicy)
+			require.Equal(t, edge1.FeeBaseMSat,
+				channel.InPolicy.FeeBaseMSat)
+
+			return nil
+		}, func() {},
+	)
+	require.NoError(t, err)
+	require.Equal(t, 1, numChannels)
+}
+
+// TestKVCacheableIteratorsRespectCancellation asserts that KV-backed cache
+// iterators return when their context is canceled.
+func TestKVCacheableIteratorsRespectCancellation(t *testing.T) {
+	t.Parallel()
+
+	if isSQLDB {
+		t.Skip("KV iterator cancellation is specific to KVStore")
+	}
+
+	ctx := t.Context()
+	store := NewTestDB(t)
+
+	kvStore, ok := store.(*KVStore)
+	require.True(t, ok)
+
+	graph, err := NewChannelGraph(
+		kvStore, WithSyncGraphCachePopulation(),
+	)
+	require.NoError(t, err)
+	require.NoError(t, graph.Start())
+	t.Cleanup(func() {
+		require.NoError(t, graph.Stop())
+	})
+
+	node1 := createTestVertex(t, lnwire.GossipVersion1)
+	require.NoError(t, graph.AddNode(ctx, node1))
+	node2 := createTestVertex(t, lnwire.GossipVersion1)
+	require.NoError(t, graph.AddNode(ctx, node2))
+
+	edgeInfo, edge1, edge2 := createChannelEdge(
+		node1, node2, lnwire.GossipVersion1,
+	)
+	require.NoError(t, graph.AddChannelEdge(ctx, edgeInfo))
+	require.NoError(t, graph.UpdateEdgePolicy(ctx, edge1))
+	require.NoError(t, graph.UpdateEdgePolicy(ctx, edge2))
+
+	canceledCtx, cancel := context.WithCancel(ctx)
+	cancel()
+
+	err = kvStore.ForEachNodeCacheable(
+		canceledCtx, lnwire.GossipVersion1,
+		func(route.Vertex, *lnwire.FeatureVector) error {
+			return nil
+		}, func() {},
+	)
+	require.ErrorIs(t, err, context.Canceled)
+
+	err = kvStore.ForEachChannelCacheable(
+		canceledCtx, lnwire.GossipVersion1,
+		func(*models.CachedEdgeInfo, *models.CachedEdgePolicy,
+			*models.CachedEdgePolicy) error {
+
+			return nil
+		}, func() {},
 	)
+	require.ErrorIs(t, err, context.Canceled)
 }
 
 // TestClosedScid tests that we can correctly insert a SCID into the index of
diff --git a/graph/db/kv_store.go b/graph/db/kv_store.go
index 3021fe9..aa32f75 100644
--- a/graph/db/kv_store.go
+++ b/graph/db/kv_store.go
@@ -250,7 +250,7 @@ func (c channelMapKey) String() string {
 
 // getChannelMap loads all channel edge policies from the database and stores
 // them in a map.
-func getChannelMap(edges kvdb.RBucket) (
+func getChannelMap(ctx context.Context, edges kvdb.RBucket) (
 	map[channelMapKey]*models.ChannelEdgePolicy, error) {
 
 	// Create a map to store all channel edge policies.
@@ -440,7 +440,9 @@ func forEachChannel(db kvdb.Backend, cb func(*models.ChannelEdgeInfo,
 
 		// First, load all edges in memory indexed by node and channel
 		// id.
-		channelMap, err := getChannelMap(edges)
+		channelMap, err := getChannelMap(
+			context.Background(), edges,
+		)
 		if err != nil {
 			return err
 		}
@@ -510,7 +512,7 @@ func (c *KVStore) ForEachChannelCacheable(ctx context.Context,
 
 		// First, load all edges in memory indexed by node and channel
 		// id.
-		channelMap, err := getChannelMap(edges)
+		channelMap, err := getChannelMap(ctx, edges)
 		if err != nil {
 			return err
 		}
diff --git a/graph/db/options.go b/graph/db/options.go
index 15ea6f4..df49fd7 100644
--- a/graph/db/options.go
+++ b/graph/db/options.go
@@ -85,14 +85,21 @@ type chanGraphOptions struct {
 	// preAllocCacheNumNodes is the number of nodes we expect to be in the
 	// graph cache, so we can pre-allocate the map accordingly.
 	preAllocCacheNumNodes int
+
+	// asyncGraphCachePopulation indicates whether the graph cache
+	// should be populated asynchronously or if the Start method should
+	// block until the cache is fully populated. This is true by
+	// default.
+	asyncGraphCachePopulation bool
 }
 
 // defaultChanGraphOptions returns a new chanGraphOptions instance populated
 // with default values.
 func defaultChanGraphOptions() *chanGraphOptions {
 	return &chanGraphOptions{
-		useGraphCache:         true,
-		preAllocCacheNumNodes: DefaultPreAllocCacheNumNodes,
+		useGraphCache:             true,
+		asyncGraphCachePopulation: true,
+		preAllocCacheNumNodes:     DefaultPreAllocCacheNumNodes,
 	}
 }
 
@@ -115,6 +122,25 @@ func WithPreAllocCacheNumNodes(n int) ChanGraphOption {
 	}
 }
 
+// WithAsyncGraphCachePopulation sets whether the graph cache should be
+// populated asynchronously or if the Start method should block until the
+// cache is fully populated.
+func WithAsyncGraphCachePopulation(async bool) ChanGraphOption {
+	return func(o *chanGraphOptions) {
+		o.asyncGraphCachePopulation = async
+	}
+}
+
+// WithSyncGraphCachePopulation will cause the ChannelGraph to block
+// until the graph cache is fully populated before returning from the Start
+// method. This is useful for tests that need to ensure the graph cache is
+// fully populated before proceeding with further operations.
+func WithSyncGraphCachePopulation() ChanGraphOption {
+	return func(o *chanGraphOptions) {
+		o.asyncGraphCachePopulation = false
+	}
+}
+
 // StoreOptions holds parameters for tuning and customizing a graph DB.
 type StoreOptions struct {
 	// RejectCacheSize is the maximum number of rejectCacheEntries to hold