Go: pathfinding: optimize it by moving orderbooks into memory

[tomquisel]

Pathfinding is key for devs making wallets that support remittance payments. It's worth doing it right, since that's a central goal of Stellar.

It can be greatly sped up by moving orderbooks into memory. Hopefully we can also return the 20 best paths at that point, rather than the first 20 paths as we do now.

[bartekn]

One possible problem is that loading offers from core DB to build the initial state can be slow. I wrote some exp code connected to in-memory search some time ago in exp-paths branch.

[ire-and-curses]

Community in-memory implementation (typescript), fast, adds support for this approach: stellar-pathfinder-server

[marcinx]

If anyone is interested in benchmarking:

Deployed stellar-pathfinder-server and mapped it behind our /paths endpoint on Horizon. If anyone wants to play around with it or use it for benchmarking:

0.13s https://horizon.stellar.coinqvest.com/paths?source_account=GDUMWJ3ISSVBKGZHVQZRVUN6TUOJETXDV7POKVNXEYBCRN4CQOYCV5AA&destination_account=GDUMWJ3ISSVBKGZHVQZRVUN6TUOJETXDV7POKVNXEYBCRN4CQOYCV5AA&destination_asset_type=credit_alphanum4&destination_asset_code=BTC&destination_asset_issuer=GBSTRH4QOTWNSVA6E4HFERETX4ZLSR3CIUBLK7AXYII277PFJC4BBYOG&destination_amount=0.01

vs

6.71s https://horizon.stellar.org/paths?source_account=GDUMWJ3ISSVBKGZHVQZRVUN6TUOJETXDV7POKVNXEYBCRN4CQOYCV5AA&destination_account=GDUMWJ3ISSVBKGZHVQZRVUN6TUOJETXDV7POKVNXEYBCRN4CQOYCV5AA&destination_asset_type=credit_alphanum4&destination_asset_code=BTC&destination_asset_issuer=GBSTRH4QOTWNSVA6E4HFERETX4ZLSR3CIUBLK7AXYII277PFJC4BBYOG&destination_amount=0.01

Besides the significant response time improvement I noticed that stellar-pathfinder-server seems to find updated paths faster than Horizon because it fetches them directly from core-db before they even propagate to Horizon. I didn't measure this scientifically, just used my eyes, but even so I can see order book changes on Pathfinder first, then Horizon.

[bartekn]

@marcinx thanks for exposing this. I don't think it makes sense to do benchmarking though. As the title of this issue says, we need to move to in-memory search in the future. The algorithm currently used in Horizon is querying database every time it wants to extend the path (extend means, say, I have XLM->EUR->BTC path and I'm searching where I can go from here). When you have all the order books in memory it's significantly faster.

[marcinx]

How good are the chances that this is going to make it into one of the next few releases?

I'm suffering from abnormally slow /paths queries on our custom deployment and need to fall back to public SDF: https://stellar.stackexchange.com/questions/2560/why-is-the-paths-endpoint-on-my-custom-horizon-deployment-absurdly-slow (which is also not very fast but acceptable).

If anyone has any ideas while this is being worked on I would appreciate it.

[tomquisel]

@marcinx It's probably 2 months out, so you'll need something else in the meantime. What about Eric's suggestion above?

https://github.com/future-tense/stellar-pathfinder-server

[marcinx]

@tomquisel Thanks, Tom. We actually used pathfinder-server for a while but it stopped working with the schema changes in core-db 10.3.0 and it hasn't been updated in a while. Always better to go with native services I guess. I'd definitely like to get to the bottom of why our queries take 1m20s, while public Horizon only takes 3-6s. It's odd.

[tomquisel]

@marcinx ah that's a shame about pathfinder-server. Horizon's pathfinding is extremely database intensive using the stellar-core database, making hundreds of (small) queries to load orderbooks. So if your Horizon -> stellar-core connection is high latency, that'd be an issue. If your stellar-core DB has a low IOPS cap, that would also do it. I'd recommend profiling the stellar-core database while pathfinding to understand what's taking the most time.

[bartekn]

We believe this has been fixed in 0.20.0 release (and 0.20.1 that contains some performance fixes). Horizon 0.20.1rc1 is currently deployed to https://horizon.stellar.org. Please check it out. It is using the new in-memory order book graph.