From ZmnSCPxj at protonmail.com Thu Aug 1 05:02:59 2019 From: ZmnSCPxj at protonmail.com (ZmnSCPxj) Date: Thu, 01 Aug 2019 05:02:59 +0000 Subject: [Lightning-dev] Improving Lightning Network Pathfinding Latency by Path Splicing and Other Real-Time Strategy Game Techniques In-Reply-To: References: Message-ID: Good morning laolu, Sent with ProtonMail Secure Email. ??????? Original Message ??????? On Thursday, August 1, 2019 10:29 AM, Olaoluwa Osuntokun wrote: > > I found out recently (mid-2019) that mainnet Lightning nodes take an > > inordinate amount of time to find a route between themselves and an > > arbitrary payee node. > > Typical quotes suggested that commodity hardware would take 2 seconds to > > find a route > ? > Can you provide a reproducible benchmark or further qualify this number (2 > seconds)? No reproducible benchmark. However, this is my reference: https://medium.com/@cryptotony/why-does-ln-payments-arent-instantaneous-d24f7e5f88cb which claims this 2 seconds for LND implementations. (It is entirely possible this information is obsolete, as it was published a month ago and things move fast in LN.) As per Rene, from his C-Lightning mainnet node, `getroute` typically takes 1.1 to 1.3s to a particular unspecified destination. I do not know details of his hardware; it would be better to ask him. > Not commenting on the rest of this email as I haven't read the > rest of it yet, but this sounds like just an issue of engineering > optimization. The rest of the email *is* engineering optimization. > AFAIK, most implementations are using unoptimized on-disk > representations of the graph, do minimal caching, and really haven't made > any sort of push to optimize these hot spots. C-Lightning has always used in-memory representation of the graph (helped massively by the low-level nature of C so we can fit a larger graph in the same space), and has the "million channel project" to attempt to generate graphs at 1 million channels that seem to represent the distribution of actual graphs today. C-Lightning is barely able to fit in a RPi-level computer today with the actual mainnet graph. > There's no reason that finding > a path in a graph of a 10s of thousands of edges should take _2 seconds_. > > Beyond that, to my knowledge, all implementations other and lnd implement a > very rudimentary time based edge/node pruning in response to failures. I > call it rudimentary, as it just waits a small period of time, then forgets > all its past path finding history. As a result, each attempt will include > nodes that have been known to be offline, or nonoperational channels, > effectively doing redundant work each attempt. Indeed, C-Lightning does this. > > The latest version of our software has moved beyond this [1], and will > factor in past path finding attempts into its central "mission control", > allowing it to learn from each attempt, and even import existing state into > its path finding memory (essentially a confidence factor that takes into > account the cost of a failed attempt mapped into a scalar weight we can use > for comparison purposes). This is just an initial first step, but we've seen > a significant improvement with just a _little_ bit more intelligence in our > path finding heuristics. Indeed. Our main algorithm for pathfinding is Dijkstra, which is O(n log n) formally with proper data structure implementation, though at large sizes approaches O(n ^ 2) as caching and so on get involved. I believe this is approximately what you will find in the "best" pathfinding algorithms. Limiting what you scan to a smaller slice of the graph is a valid engineering change to optimize pathfinding, as you will get near-optimal results while greatly cutting down on runtime. > We should take care to not get distracted by more > distant "pie in the sky" like ideas (since many of them are half-baked), > lest we ignore these low hanging engineering fruits and incremental > algorithmic updates. As you have not read the rest of the email, I believe you should. They are almost entirely low-hanging engineering fruits, and many are practically deployable today. The primary point of this thread is to show that there exists a similar field (real-time strategy games) whose pathfinding problems are suspiciously similar to ours: 1. Dynamically-changing world. 2. Limited knowledge of actual world conditions (fog of war). 3. Low-latency for UX. 4. Large maps. Taking a short visit to this field may be helpful, regardless. Regards, ZmnSCPxj