Repository: lightningnetwork/lnd
Pull request #3418 (2019-08-20 16:33:10)

routing, channeldb: several optimizations for path finding
This PR brings down path finding time by using the channel cache and some other small optimizations. The goal was to bring the time down to ~10ms range. Using a benchmark, described below, it started at 220ms/72mb per path finding operation and with these changes it comes down to 9ms/1.1mb.

## Benchmarking

I've written [a benchmark](https://github.com/lightningnetwork/lnd/commit/fd34d90b89d500118ab10763c408cc55c2b969cf) based on a dump of the main net graph (its a few months old now) in order to test these changes. The bench is roughly as follows:
 - The first time only, a DB is built using the graph dump JSON
 - The DB is used for a simple path finding run to prime the channel cache
 - Path finding runs in a nested benchmark as many times as `go test` sees fit

A second bench, almost equal to the first one runs the nested benchmark in parallel to stress concurrency.

If you wish to run it, first uncomment the DB generation code and run the test with a ~20m timeout to let it generate the full DB. Then comment that again and run your benchmarks.

## Findings

Bench @ master
```
BenchmarkBigGraphCachePerformance/findPath-4         	     100	 203460951 ns/op	72351182 B/op	 1459914 allocs/op
BenchmarkBigGraphCacheConcurrency/findPath-4         	      50	 204061673 ns/op	72480387 B/op	 1460464 allocs/op
```

At first glance path finding spent a lot of its time in three things:
 - Reading from the DB
 - Parsing the contents read
 - GC'ing

Adding the channel cache brings down the time and allocations considerably:
```
BenchmarkBigGraphCachePerformance/findPath-4         	     500	  27721522 ns/op	 9830663 B/op	  155751 allocs/op
BenchmarkBigGraphCacheConcurrency/findPath-4         	     200	  65236737 ns/op	 9910162 B/op	  156245 allocs/op
```

This is mostly because it avoids hitting disk and allocating new copies of channels. The wire format parsing code seems to be heavy on small allocations, so avoiding that is also a huge win.

The next find was that the hot path has a log on trace level. That log creates a lot of small allocations regardless of the current log level. Adding a log level check around it avoids that for most configs around and removes quite a bit of allocations, also bringing down the runtime by 18%:
```
BenchmarkBigGraphCachePerformance/findPath-4         	    1000	  22749674 ns/op	 7599558 B/op	   97047 allocs/op
BenchmarkBigGraphCacheConcurrency/findPath-4         	     200	  59610474 ns/op	 7676371 B/op	   97534 allocs/op
```

The `distance` map was being pre-populated with all nodes, consuming about 20% of the path finding time. Turns out the code used this fact in only one place to check if the candidate distance was better than the existing one. Changing that code to check for existance first let us remove the pre-population:
```
BenchmarkBigGraphCachePerformance/findPath-4         	    1000	  13426902 ns/op	 4516310 B/op	   19026 allocs/op
BenchmarkBigGraphCacheConcurrency/findPath-4         	     200	  62240894 ns/op	 4592095 B/op	   19509 allocs/op
```

Path finding uses several structures that grow to hold references to a big part of the graph. Tweaking the capacity for those resulted in lower memory usage and some modest speed bump:
```
BenchmarkBigGraphCachePerformance/findPath-4         	    1000	  12426815 ns/op	 3432225 B/op	   18771 allocs/op
BenchmarkBigGraphCacheConcurrency/findPath-4         	     300	  55189725 ns/op	 3507752 B/op	   19248 allocs/op
```

There were 3 structures used: `distance`, `next` and `distanceHeap`. `distance` and `next` could be merged by adding a `nextHop` pointer to `nodeWithDist` this is updated whenever a cheaper path is found. Also, `nodeWithDist` is a big struct now and `distanceHeap` held it by value, changing it to use a pointer removed a lot of copying work. Both these changes reduced memory usage by about half and runtime by 20%.
```
BenchmarkBigGraphCachePerformance/findPath-4         	    2000	  10203189 ns/op	 1639554 B/op	   18759 allocs/op
BenchmarkBigGraphCacheConcurrency/findPath-4         	     300	  55169048 ns/op	 1716604 B/op	   19259 allocs/op
```

The last insight was that a function introduced to access the channel cache was returning a `*ChannelEdge`. That struct is small and the pointer was introducing an allocation that added up since its part of the hot path. Changing that function to return by value reduced time by 10% and memory by 39%.
```
BenchmarkBigGraphCachePerformance/findPath-4         	    2000	   9136682 ns/op	 1171369 B/op	    4083 allocs/op
BenchmarkBigGraphCacheConcurrency/findPath-4         	     300	  50998898 ns/op	 1247789 B/op	    4579 allocs/op
```

#### Pull Request Checklist

- [x] If this is your first time contributing, we recommend you read the [Code
  Contribution Guidelines](https://github.com/lightningnetwork/lnd/blob/master/docs/code_contribution_guidelines.md)
- [x] All changes are Go version 1.12 compliant
- [x] The code being submitted is commented according to [Code Documentation and Commenting](https://github.com/lightningnetwork/lnd/blob/master/docs/code_contribution_guidelines.md#CodeDocumentation)
- [x] For new code: Code is accompanied by tests which exercise both
  the positive and negative (error paths) conditions (if applicable)
- [x] For bug fixes: Code is accompanied by new tests which trigger
  the bug being fixed to prevent regressions
- [x] Any new logging statements use an appropriate subsystem and
  logging level
- [x] Code has been formatted with `go fmt`
- [x] For code and documentation: lines are wrapped at 80 characters
  (the tab character should be counted as 8 characters, not 4, as some IDEs do
  per default)
- [x] Running `make check` does not fail any tests
- [x] Running `go vet` does not report any issues
- [x] Running `make lint` does not report any **new** issues that did not
  already exist
- [x] All commits build properly and pass tests. Only in exceptional
  cases it can be justifiable to violate this condition. In that case, the
  reason should be stated in the commit message.
- [x] Commits have a logical structure according to [Ideal Git Commit Structure](https://github.com/lightningnetwork/lnd/blob/master/docs/code_contribution_guidelines.md#IdealGitCommitStructure)


champo: The overall memory usage should remain similar. The cache is limited to a number of channels set by a config value. If the number of channels exceeds that value, this code will still fallback to reading from the DB. If the graph is big in relation to the cache, the performance gains will be lower.

I'll address the coments in the next few days 🙂
champo: @joostjager updated with the feedback and rebasing against latest master. I've fixed a bug along the way relating to edge policies with missing nodes. Lastly, a few smaller changes to bring memory usage down by about 1mb.

champo: Added 4 new changes bringing down the time to 9ms and memory usage to 1.1mb. This is the last of the updated I'll send, I've run out of ideas I can easily implement.
joostjager: Good changes again :+1: 

Main question is what to do with the added `if node == nil` and `if db == nil` code. I think that with the right design this should be avoidable, but it probably requires more changes. On the other hand, building on top of something that shouldn't be there in the first place defers paying those costs to the future.

Final comment is about commit structure. In the end, these commits should be reorganized so that it becomes a logical stack. For example (some of these are already a separate commit now):
* all the cache changes in `graph.go` can be done first in one or multiple commits first. 
* add `NumNodes` to `graph.go` and pre-allocate map
* merging nextNode into the path finding heap
* change to nodeWithDist pointers
* remove unused k-shortest code
* remove distance map infinity initialization
* fix log performance

What you generally want to avoid in one pr is to make changes in a commit and change them again later. For example, initializing the map first with 10000 and later replacing it by `NumNodes`. I find it easier if those two are just squashed together and there is one commit that presents the final changes in a particular area.

You could also consider making two prs. One with the internal path finding improvements that are pretty straight-forward to review and get approval on. Then a second one to carefully do the cache.
halseth: > Also, would it make sense to add the performance benchmark to the codebase (as a new PR that we could merge before this change) so that we could make sure we don't have regressions in the future?

I wouldn't consider this blocking.


halseth: @champo This is close! Do you want to make the last fixups? :)
champo: @halseth I'll work on it this weekend :D 
champo: @halseth done!
halseth: Also, linter is failing (run `make lint`).
champo: @halseth @joostjager updated with the estimated node count changes and linter fixes :)

Patch:
diff --git a/routing/heap.go b/routing/heap.go
index 1cbbc5e53..62b3e3dd0 100644
--- a/routing/heap.go
+++ b/routing/heap.go
@@ -3,6 +3,7 @@ package routing
 import (
 	"container/heap"
 
+	"github.com/lightningnetwork/lnd/channeldb"
 	"github.com/lightningnetwork/lnd/lnwire"
 	"github.com/lightningnetwork/lnd/routing/route"
 )
@@ -35,12 +36,15 @@ type nodeWithDist struct {
 	// Includes the routing fees and a virtual cost factor to account for
 	// time locks.
 	weight int64
+
+	// nextHop is the edge this route comes from.
+	nextHop *channeldb.ChannelEdgePolicy
 }
 
 // distanceHeap is a min-distance heap that's used within our path finding
 // algorithm to keep track of the "closest" node to our source node.
 type distanceHeap struct {
-	nodes []nodeWithDist
+	nodes []*nodeWithDist
 
 	// pubkeyIndices maps public keys of nodes to their respective index in
 	// the heap. This is used as a way to avoid db lookups by using heap.Fix
@@ -50,9 +54,10 @@ type distanceHeap struct {
 
 // newDistanceHeap initializes a new distance heap. This is required because
 // we must initialize the pubkeyIndices map for path-finding optimizations.
-func newDistanceHeap() distanceHeap {
+func newDistanceHeap(numNodes int) distanceHeap {
 	distHeap := distanceHeap{
-		pubkeyIndices: make(map[route.Vertex]int),
+		pubkeyIndices: make(map[route.Vertex]int, numNodes),
+		nodes:         make([]*nodeWithDist, 0, numNodes),
 	}
 
 	return distHeap
@@ -84,7 +89,7 @@ func (d *distanceHeap) Swap(i, j int) {
 //
 // NOTE: This is part of the heap.Interface implementation.
 func (d *distanceHeap) Push(x interface{}) {
-	n := x.(nodeWithDist)
+	n := x.(*nodeWithDist)
 	d.nodes = append(d.nodes, n)
 	d.pubkeyIndices[n.node] = len(d.nodes) - 1
 }
@@ -96,6 +101,7 @@ func (d *distanceHeap) Push(x interface{}) {
 func (d *distanceHeap) Pop() interface{} {
 	n := len(d.nodes)
 	x := d.nodes[n-1]
+	d.nodes[n-1] = nil
 	d.nodes = d.nodes[0 : n-1]
 	delete(d.pubkeyIndices, x.node)
 	return x
@@ -106,7 +112,7 @@ func (d *distanceHeap) Pop() interface{} {
 // modify its position and reorder the heap. If the vertex does not already
 // exist in the heap, then it is pushed onto the heap. Otherwise, we will end
 // up performing more db lookups on the same node in the pathfinding algorithm.
-func (d *distanceHeap) PushOrFix(dist nodeWithDist) {
+func (d *distanceHeap) PushOrFix(dist *nodeWithDist) {
 	index, ok := d.pubkeyIndices[dist.node]
 	if !ok {
 		heap.Push(d, dist)
diff --git a/routing/pathfind.go b/routing/pathfind.go
index 33c452f0b..743adad1d 100644
--- a/routing/pathfind.go
+++ b/routing/pathfind.go
@@ -6,6 +6,7 @@ import (
 	"math"
 	"time"
 
+	"github.com/btcsuite/btcd/btcec"
 	"github.com/coreos/bbolt"
 
 	"github.com/lightningnetwork/lnd/channeldb"
@@ -36,6 +37,11 @@ const (
 	// some effect with smaller time lock values. The value may need
 	// tweaking and/or be made configurable in the future.
 	RiskFactorBillionths = 15
+
+	// estimatedNodeCount is used to preallocate the path finding structures
+	// to avoid resizing and copies. It should be number on the same order as
+	// the number of active nodes in the network.
+	estimatedNodeCount = 10000
 )
 
 // pathFinder defines the interface of a path finding algorithm.
@@ -319,61 +325,40 @@ func findPath(g *graphParams, r *RestrictParams, cfg *PathFindingConfig,
 		defer tx.Rollback()
 	}
 
-	// First we'll initialize an empty heap which'll help us to quickly
-	// locate the next edge we should visit next during our graph
-	// traversal.
-	nodeHeap := newDistanceHeap()
-
-	// For each node in the graph, we create an entry in the distance map
-	// for the node set with a distance of "infinity". graph.ForEachNode
-	// also returns the source node, so there is no need to add the source
-	// node explicitly.
-	distance := make(map[route.Vertex]nodeWithDist)
-	if err := g.graph.ForEachNode(tx, func(_ *bbolt.Tx,
-		node *channeldb.LightningNode) error {
-		// TODO(roasbeef): with larger graph can just use disk seeks
-		// with a visited map
-		vertex := route.Vertex(node.PubKeyBytes)
-		distance[vertex] = nodeWithDist{
-			dist: infinity,
-			node: route.Vertex(node.PubKeyBytes),
-		}
+	if r.DestPayloadTLV {
+		// Check if the target has TLV enabled
 
-		// If we don't have any features for this node, then we can
-		// stop here.
-		if node.Features == nil || !r.DestPayloadTLV {
-			return nil
+		targetKey, err := btcec.ParsePubKey(target[:], btcec.S256())
+		if err != nil {
+			return nil, err
 		}
 
-		// We only need to perform this check for the final node, so we
-		// can exit here if this isn't them.
-		if vertex != target {
-			return nil
+		targetNode, err := g.graph.FetchLightningNode(targetKey)
+		if err != nil {
+			return nil, err
 		}
 
-		// If we have any records for the final hop, then we'll check
-		// not to ensure that they are actually able to interpret them.
-		supportsTLV := node.Features.HasFeature(
-			lnwire.TLVOnionPayloadOptional,
-		)
-		if !supportsTLV {
-			return fmt.Errorf("destination hop doesn't " +
-				"understand new TLV paylods")
+		if targetNode.Features != nil {
+			supportsTLV := targetNode.Features.HasFeature(
+				lnwire.TLVOnionPayloadOptional,
+			)
+			if !supportsTLV {
+				return nil, fmt.Errorf("destination hop doesn't " +
+					"understand new TLV paylods")
+			}
 		}
-
-		return nil
-	}); err != nil {
-		return nil, err
 	}
 
+	// First we'll initialize an empty heap which'll help us to quickly
+	// locate the next edge we should visit next during our graph
+	// traversal.
+	nodeHeap := newDistanceHeap(estimatedNodeCount)
+
+	// Holds the current best distance for a given node.
+	distance := make(map[route.Vertex]*nodeWithDist, estimatedNodeCount)
+
 	additionalEdgesWithSrc := make(map[route.Vertex][]*edgePolicyWithSource)
 	for vertex, outgoingEdgePolicies := range g.additionalEdges {
-		// We'll also include all the nodes found within the additional
-		// edges that are not known to us yet in the distance map.
-		distance[vertex] = nodeWithDist{
-			dist: infinity,
-			node: vertex,
-		}
 
 		// Build reverse lookup to find incoming edges. Needed because
 		// search is taken place from target to source.
@@ -391,12 +376,12 @@ func findPath(g *graphParams, r *RestrictParams, cfg *PathFindingConfig,
 	}
 
 	// We can't always assume that the end destination is publicly
-	// advertised to the network and included in the graph.ForEachNode call
-	// above, so we'll manually include the target node. The target node
-	// charges no fee. Distance is set to 0, because this is the starting
-	// point of the graph traversal. We are searching backwards to get the
-	// fees first time right and correctly match channel bandwidth.
-	distance[target] = nodeWithDist{
+	// advertised to the network so we'll manually include the target node.
+	// The target node charges no fee. Distance is set to 0, because this
+	// is the starting point of the graph traversal. We are searching
+	// backwards to get the fees first time right and correctly match
+	// channel bandwidth.
+	distance[target] = &nodeWithDist{
 		dist:            0,
 		weight:          0,
 		node:            target,
@@ -405,15 +390,10 @@ func findPath(g *graphParams, r *RestrictParams, cfg *PathFindingConfig,
 		probability:     1,
 	}
 
-	// We'll use this map as a series of "next" hop pointers. So to get
-	// from `Vertex` to the target node, we'll take the edge that it's
-	// mapped to within `next`.
-	next := make(map[route.Vertex]*channeldb.ChannelEdgePolicy)
-
 	// processEdge is a helper closure that will be used to make sure edges
 	// satisfy our specific requirements.
 	processEdge := func(fromVertex route.Vertex, bandwidth lnwire.MilliSatoshi,
-		edge *channeldb.ChannelEdgePolicy, toNode route.Vertex) {
+		edge *channeldb.ChannelEdgePolicy, toNodeDist *nodeWithDist) {
 
 		edgesExpanded++
 
@@ -440,16 +420,18 @@ func findPath(g *graphParams, r *RestrictParams, cfg *PathFindingConfig,
 
 		// Calculate amount that the candidate node would have to sent
 		// out.
-		toNodeDist := distance[toNode]
 		amountToSend := toNodeDist.amountToReceive
 
 		// Request the success probability for this edge.
 		edgeProbability := r.ProbabilitySource(
-			fromVertex, toNode, amountToSend,
+			fromVertex, toNodeDist.node, amountToSend,
 		)
 
-		log.Tracef("path finding probability: fromnode=%v, tonode=%v, "+
-			"probability=%v", fromVertex, toNode, edgeProbability)
+		log.Trace(newLogClosure(func() string {
+			return fmt.Sprintf("path finding probability: fromnode=%v,"+
+				" tonode=%v, probability=%v", fromVertex, toNodeDist.node,
+				edgeProbability)
+		}))
 
 		// If the probability is zero, there is no point in trying.
 		if edgeProbability == 0 {
@@ -548,7 +530,8 @@ func findPath(g *graphParams, r *RestrictParams, cfg *PathFindingConfig,
 		// route, return. It is important to also return if the distance
 		// is equal, because otherwise the algorithm could run into an
 		// endless loop.
-		if tempDist >= distance[fromVertex].dist {
+		current, ok := distance[fromVertex]
+		if ok && tempDist >= current.dist {
 			return
 		}
 
@@ -563,21 +546,21 @@ func findPath(g *graphParams, r *RestrictParams, cfg *PathFindingConfig,
 		// better than the current best known distance to this node.
 		// The new better distance is recorded, and also our "next hop"
 		// map is populated with this edge.
-		distance[fromVertex] = nodeWithDist{
+		withDist := &nodeWithDist{
 			dist:            tempDist,
 			weight:          tempWeight,
 			node:            fromVertex,
 			amountToReceive: amountToReceive,
 			incomingCltv:    incomingCltv,
 			probability:     probability,
+			nextHop:         edge,
 		}
+		distance[fromVertex] = withDist
 
-		next[fromVertex] = edge
-
-		// Either push distance[fromVertex] onto the heap if the node
+		// Either push withDist onto the heap if the node
 		// represented by fromVertex is not already on the heap OR adjust
 		// its position within the heap via heap.Fix.
-		nodeHeap.PushOrFix(distance[fromVertex])
+		nodeHeap.PushOrFix(withDist)
 	}
 
 	// TODO(roasbeef): also add path caching
@@ -592,7 +575,7 @@ func findPath(g *graphParams, r *RestrictParams, cfg *PathFindingConfig,
 
 		// Fetch the node within the smallest distance from our source
 		// from the heap.
-		partialPath := heap.Pop(&nodeHeap).(nodeWithDist)
+		partialPath := heap.Pop(&nodeHeap).(*nodeWithDist)
 		pivot := partialPath.node
 
 		// If we've reached our source (or we don't have any incoming
@@ -642,7 +625,7 @@ func findPath(g *graphParams, r *RestrictParams, cfg *PathFindingConfig,
 
 			// Check if this candidate node is better than what we
 			// already have.
-			processEdge(route.Vertex(chanSource), edgeBandwidth, inEdge, pivot)
+			processEdge(chanSource, edgeBandwidth, inEdge, partialPath)
 			return nil
 		}
 
@@ -662,30 +645,28 @@ func findPath(g *graphParams, r *RestrictParams, cfg *PathFindingConfig,
 		bandWidth := partialPath.amountToReceive
 		for _, reverseEdge := range additionalEdgesWithSrc[pivot] {
 			processEdge(reverseEdge.sourceNode, bandWidth,
-				reverseEdge.edge, pivot)
+				reverseEdge.edge, partialPath)
 		}
 	}
 
-	// If the source node isn't found in the next hop map, then a path
-	// doesn't exist, so we terminate in an error.
-	if _, ok := next[source]; !ok {
-		return nil, newErrf(ErrNoPathFound, "unable to find a path to "+
-			"destination")
-	}
-
-	// Use the nextHop map to unravel the forward path from source to
+	// Use the distance map to unravel the forward path from source to
 	// target.
-	pathEdges := make([]*channeldb.ChannelEdgePolicy, 0, len(next))
+	var pathEdges []*channeldb.ChannelEdgePolicy
 	currentNode := source
 	for currentNode != target { // TODO(roasbeef): assumes no cycles
 		// Determine the next hop forward using the next map.
-		nextNode := next[currentNode]
+		currentNodeWithDist, ok := distance[currentNode]
+		if !ok {
+			// If the node doesnt have a next hop it means we didn't find a path.
+			return nil, newErrf(ErrNoPathFound, "unable to find a "+
+				"path to destination")
+		}
 
 		// Add the next hop to the list of path edges.
-		pathEdges = append(pathEdges, nextNode)
+		pathEdges = append(pathEdges, currentNodeWithDist.nextHop)
 
 		// Advance current node.
-		currentNode = route.Vertex(nextNode.Node.PubKeyBytes)
+		currentNode = currentNodeWithDist.nextHop.Node.PubKeyBytes
 	}
 
 	// The route is invalid if it spans more than 20 hops. The current


Test patch:
diff --git a/routing/heap_test.go b/routing/heap_test.go
index 4214e965b..659653f70 100644
--- a/routing/heap_test.go
+++ b/routing/heap_test.go
@@ -17,19 +17,19 @@ func TestHeapOrdering(t *testing.T) {
 
 	// First, create a blank heap, we'll use this to push on randomly
 	// generated items.
-	nodeHeap := newDistanceHeap()
+	nodeHeap := newDistanceHeap(0)
 
 	prand.Seed(1)
 
 	// Create 100 random entries adding them to the heap created above, but
 	// also a list that we'll sort with the entries.
 	const numEntries = 100
-	sortedEntries := make([]nodeWithDist, 0, numEntries)
+	sortedEntries := make([]*nodeWithDist, 0, numEntries)
 	for i := 0; i < numEntries; i++ {
 		var pubKey [33]byte
 		prand.Read(pubKey[:])
 
-		entry := nodeWithDist{
+		entry := &nodeWithDist{
 			node: route.Vertex(pubKey),
 			dist: prand.Int63(),
 		}
@@ -55,9 +55,9 @@ func TestHeapOrdering(t *testing.T) {
 
 	// One by one, pop of all the entries from the heap, they should come
 	// out in sorted order.
-	var poppedEntries []nodeWithDist
+	var poppedEntries []*nodeWithDist
 	for nodeHeap.Len() != 0 {
-		e := heap.Pop(&nodeHeap).(nodeWithDist)
+		e := heap.Pop(&nodeHeap).(*nodeWithDist)
 		poppedEntries = append(poppedEntries, e)
 	}