Coin select slowdown

[nulven]

Sending transactions, particularly opens, seems to have slowed down significantly. After investigating a bit further it seems that wallet.fill is the root cause.

Here’s a wallet I created to test. It has ~16 thousand, 1 coin none txos, sent over about 160 blocks. In my testing, I was getting open times of around 150 ms and transaction times of 50 ms.

If you want to test yourself, here’s the steps I took to see the time to send an open.

In ~/.hsd/regtest
unzip /path/to/file/wallet.zip -d wallet

wallet.zip
Change lines 1639-1648 in hsd/lib/wallet/wallet.js to the following to log the time.

async sendOpen(name, force, options) {
    console.time('SEND OPEN');
   const unlock = await this.fundLock.lock();
   try {
       return await this._sendOpen(name, force, options);
   } finally {
       unlock();
       console.timeEnd('SEND OPEN');
   }
}

Run the node
./bin/hsd --network=regtest --index-address=false --index-tx=false

Grind a new name, send the open, and check the logs for ‘SEND OPEN’
./bin/hsd-cli rpc --network=regtest grindname 10
./bin/hsw-cli rpc sendopen --network=regtest [NAME]

[pinheadmz]

How did you generate the 16000 utxo? If it was all by block generation you might have this issue:

bcoin-org/bcoin#882

A useful check would be the values of the utxos. If they are mostly 0 or below dust I think we will have an easy fix

[turbomaze]

@pinheadmz thanks for linking to that issue, the thread there is very relevant. We initially tested this by mining lots of blocks, and we noticed that mining into the wallet we were testing seemed to exacerbate the issue. However, to simplify the test case, we switched to sending many tiny txs from another wallet. Not sure if it's below dust value or not @nulven.

This issue is exacerbated in wallets with actual auction txos. I wonder if all of the 0 value open txos (and 0 value reveal/redeems for bids with 0 value or 0 blind??) cause a similar issue. What is the easy fix you have in mind?

[pinheadmz]

So I tried using your wallet.zip but since the chain data is missing the wallet had issues.

I recreated the conditions with this script which sends 32,000 1.0 HNS UTXO to a test wallet.

I can confirm the OPEN times were around 200-300 ms for the test wallet, compared to 10-20 for the primary wallet with only about 1,000 UTXO. I also got the same results with regular sendtoaddress transactions.

I can also confirm the delay is a direct result of leveldb fetching an unlimited amount of records from the database. Well, limited only by the total amount that exist (32,000).

So I could mitigate the issue entirely by adding a limit to the leveldb request for both the "no account specified" path and the "account specified" path. Specifying an account is slower but still below 70ms.

diff --git a/lib/wallet/txdb.js b/lib/wallet/txdb.js
index e52d2e65..f8a25a15 100644
--- a/lib/wallet/txdb.js
+++ b/lib/wallet/txdb.js
@@ -2369,6 +2369,7 @@ class TXDB {
   getAccountOutpoints(acct) {
     assert(typeof acct === 'number');
     return this.bucket.keys({
+      limit: 1000,
       gte: layout.C.min(acct),
       lte: layout.C.max(acct),
       parse: (key) => {
@@ -2646,6 +2647,7 @@ class TXDB {

     // Fast case
     return this.bucket.range({
+      limit: 1000,
       gte: layout.c.min(),
       lte: layout.c.max(),
       parse: (key, value) => {

This is the one-line band-aid fix for this issue. What are the side effects?

Well, it's not very smart, and after a wallet has 1,000 coins, every tx will take the max amount of time to create. Ideally the coin selection process uses something smart like branch & bound which would also mean we need to migrate the walletDB and index coins by their value, then only a handful of records are needed from the DB.

Coins in this part of the txdb are sorted by hash, so they are essentially random. That means (I guess) that the first batch of 1,000 coins is just as likely to have an optimal solution as the next 1,000 coins. Since we only use the first 1,000 coins from txdb every time we make a tx, the other 31,000 coins will sit dormant for a long time, trickling into the 1,000-coin window as those are being consumed (and removed).

The worst-case scenario is that you end up with a txdb that has 1,000 tiny coins in that window (which would be exceptional because they are sorted by hash) and the wallet struggles to make a decent sized tx with these suboptimal inputs, meanwhile "the perfect set of utxos" could be sitting in the db, just beyond the 1,000 window.

as @turbomaze pointed out, spent coins are not removed from txdb, so this is the wrong approach. If we migrated txdb so that spent coins were kept in a different leveldb bucket, then this 1000 limit would be more effective, because the content of those 1000 records would churn as coins are spent.

[pinheadmz]

also related: bcoin-org/bcoin#786