Add index to wallet UTXO #7823

1. 
   joaopaulofonseca commented at 10:38 am on April 6, 2016: contributor

   This PR implements an index of unspent transaction outputs (UTXOs).

   This approach optimizes CWallet::AvailableCoins, by doing some of its work each time a wallet transaction changes. For instance, using CWallet::IsMine earlier for each transaction output, it manages to keep track only of UTXOs related to wallet addresses.

   That brings large improvements on RPCs such as listunspent and fundrawtransaction. Depending on the size of your wallet and number of UTXOs, performance gains may be up to 98%.

   This way, instead of going through all the wallet transactions, the search for UTXOs is made only on this updated list of outputs.

   Depends on #7822 to ensure functionality behaviour remains the same.

2. laanwj added the label Wallet on Apr 6, 2016
3. 
   laanwj commented at 10:49 am on April 6, 2016: member

   Depending on the size of your wallet and number of UTXOs, performance gains may be up to 98%.

   Yes, this makes sense.

   How does it affect memory usage?

4. 
   sipa commented at 11:04 am on April 6, 2016: member

   Concept ACK, it’s silly that we didn’t have this.

   Memory usage: I expect it to consume around 80 bytes per unspent output on 64-bit platforms.

5. 
   promag commented at 11:15 am on April 6, 2016: member

   ACK

   Rename first commit to something like Add index to wallet UTXO

6. 
   joaopaulofonseca commented at 11:19 am on April 6, 2016: contributor

   The overall memory usage will depend on the wallet size, more particularly on the UTXO count. Given the info being stored per UTXO (an outpoint and a pair with isminetype and pointer to Tx), the extra memory increment won’t be that much.
7. 
   joaopaulofonseca commented at 11:20 am on April 6, 2016: contributor

   @promag that makes sense. This is not a cache, but more like an index..
8. 
   pedrobranco commented at 11:30 am on April 6, 2016: contributor

   Tested ACK.

   In my case the improvements of listunspent are from 12s. to 0.1s .

9. joaopaulofonseca renamed this:
   [Wallet] Add index of unspent transaction outputs (UTXOs)
   Add index to wallet UTXO
   on Apr 6, 2016
10. joaopaulofonseca force-pushed on Apr 6, 2016
11. 
    jonasschnelli commented at 11:40 am on April 6, 2016: contributor

    Nice work! Concept ACK.
12. 
    laanwj commented at 11:59 am on April 6, 2016: member

    Given the info being stored per UTXO (an outpoint and a pair with isminetype and pointer to Tx), the extra memory increment won’t be that much.

    So this only uses (~80 bytes) memory per actually unspent output that is in the wallet? That’s great. I then don’t expect the extra memory use for that to be significant. The bulk is wasted on keeping historical transactions anyway.

    Concept ACK.

13. joaopaulofonseca force-pushed on Apr 6, 2016
14. joaopaulofonseca force-pushed on Apr 6, 2016
15. joaopaulofonseca force-pushed on Apr 6, 2016
16. joaopaulofonseca force-pushed on Apr 6, 2016
17. 
    gmaxwell commented at 3:02 pm on April 6, 2016: contributor

    Concept ACK. Thanks for working on this.
18. 
    promag commented at 11:03 pm on April 6, 2016: member

    Solves #6573.
19. 
    instagibbs commented at 6:35 pm on April 12, 2016: member

    lightly tested ACK
20. laanwj added the label Resource usage on Apr 15, 2016
21. joaopaulofonseca force-pushed on Apr 15, 2016
22. 
    promag commented at 1:49 pm on April 19, 2016: member

    This change greatly improves the performance of AvailableCoins and indirectly listunspent and others. Is it reasonable to expect this in next 0.12 update?
23. 
    sipa commented at 1:58 pm on April 19, 2016: member

    @promag Only bug fixes and consensus changes are backported to old releases. It’s well on track for 0.13, though.
24. 
    laanwj commented at 2:12 pm on April 19, 2016: member

    I think this needs at least one more code review ACK before merge (to master, not 0.12)
25. in src/wallet/wallet.cpp: in bb06356ce5 outdated

    501@@ -498,9 +502,12 @@ bool CWallet::IsSpent(const uint256& hash, unsigned int n) const
    502 
    503 void CWallet::AddToSpends(const COutPoint& outpoint, const uint256& wtxid)
    504 {
    505+    // since this output is being marked as a spend output, we remove it from the UTXO index
    

    ---

    ---

    

    sipa commented at 2:25 pm on April 19, 2016:

    Typo: spent output
26. in src/wallet/wallet.cpp: in bb06356ce5 outdated

    543+    }
    544+}
    545+
    546+void CWallet::RemoveFromUnspents(const COutPoint &outpoint)
    547+{
    548+    TxUnspents::iterator uit = mapTxUnspents.find(outpoint);
    

    ---

    ---

    

    sipa commented at 2:27 pm on April 19, 2016:

    Simpler to write as mapTxUnspents.erase(outpoint)
27. 
    sipa commented at 2:38 pm on April 19, 2016: member

    How does this deal with:

    • reorganizations (coins marked as spent may go back to being unspent)?
    • conflicts (there may be multiple unconfirmed transactions at the tip, and which set of them is accepted can change easily)?
    • abandoned transactions?
28. joaopaulofonseca force-pushed on Apr 26, 2016
29. joaopaulofonseca force-pushed on Apr 26, 2016
30. 
    fanquake commented at 7:59 am on May 27, 2016: member

    This needs a rebase.
31. Add index to wallet UTXO 3bdf9710f0
32. Improve CWallet::AvailableCoins with UTXO index 55abe3a5c8
33. joaopaulofonseca force-pushed on May 31, 2016
34. 
    sipa commented at 5:04 pm on June 1, 2016: member

    @jpdffonseca Feel like answering my questions above?
35. 
    joaopaulofonseca commented at 9:39 am on June 2, 2016: contributor

    @sipa I’m working to unify mapTxSpends and mapTxUnspents.
36. 
    paveljanik commented at 4:50 pm on October 8, 2016: contributor

    @jpdffonseca Are you still working on this? We need performance improvements especially for large wallets.

    Needs rebase.

37. 
    joaopaulofonseca commented at 9:11 am on October 10, 2016: contributor

    @paveljanik lately I haven’t had too much time to work on it. After testing more deeply, I realized that this solution does not always handles well some of the cases mentioned above by @sipa, so it should have a different approach.

    I’ve been trying another improvements that optimize not the unspents list itself but other values necessary to calculate the unspents, such as the call CWallet::IsMine(). With that I obtained satisfactory results, around 50% for large wallets. I’ll finish that and submit PR.

38. 
    fanquake commented at 2:48 pm on January 12, 2017: member

    Closing due to inactivity. @joaopaulofonseca if you do end up finishing work on your other improvements PRs are welcome.
39. fanquake closed this on Jan 12, 2017

    ---

40. 
    joaopaulofonseca commented at 2:01 pm on March 7, 2017: contributor

    Deprecated partially by #9939. Caching accurately these values gets a little tricky because of all the scenarios that could make the cache invalidated (conflicts, double-spends, reorganizations, abandoned transactions, etc, …).
41. MarcoFalke locked this on Sep 8, 2021

Contributors
joaopaulofonseca laanwj sipa promag pedrobranco jonasschnelli gmaxwell instagibbs fanquake paveljanik

Labels
Wallet Resource usage