Make check to distinguish between orphan txs and old txs more efficient. #10557

1. 
   morcos commented at 3:31 pm on June 8, 2017: member

   Checking for the existence in the CCoinsViewCache of the outputs of a new tx will result in a disk hit for every output since they will not be found. On the other hand if those outputs exist already, then the inputs must also have been missing, so we can move this check inside the input existence check so in the common case of a new tx it doesn’t need to run.

   The purpose of the check is to avoid spamming the orphanMap with slightly old txs which we have already seen in a block, but it is already only optimistic (depending on the outputs not being spent), so make it even more efficient by only checking the cache and not the entire pcoinsTip. @sipa this is my biggest feedback to #10195

   For a single valid tx with 500 outputs in regtest on a machine with an SSD, the time to ATMP dropped from 4 ms to 2.4 ms.

2. in src/validation.cpp:503 in 301566d1cb outdated

   508             }
   509             if (!view.HaveCoin(txin.prevout)) {
   510+                // Are inputs missing because we already have the tx?
   511+                for (size_t out = 0; out < tx.vout.size(); out++) {
   512+                    // Optimistically just do efficient check of cache for outputs
   513+                    if (pcoinsTip->HaveCoinInCache(COutPoint(hash, out))) {
   

   ---

   ---

   

   sipa commented at 6:17 pm on June 8, 2017:

   I believe this risks resulting in true for transactions that are in fact not yet confirmed and not in the mempool, but were just disconnected in a reorg. Is that something we care about? If not, perhaps add a comment to explain.

   ---

   

   sdaftuar commented at 6:31 pm on June 8, 2017:

   Can we just change HaveCoinInCache() to have the same semantics as HaveCoin(), and only return true if the coin is unspent? Seems confusing that their semantics aren’t the same.

   For many of the existing usages of HaveCoinInCache(), we store the result to potentially Uncache() later – but I don’t think it’s possible to ever have a spent coin in your cache that is able to be uncached (ie not marked DIRTY)?

   This issue affects the existing usage of HaveCoinInCache() in AlreadyHave(), I think.

   ---

   

   morcos commented at 6:57 pm on June 8, 2017:

   @sipa I actually think that’s likely a better outcome, but it may be too confusing. If a tx was just disconnected in a reorg, and no longer has one of its inputs available, it means it or its parent was probably double spent and so it shouldn’t be in the orphan map anyway.

   ---

   

   sipa commented at 8:03 pm on June 8, 2017:

   @morcos Do you think it’s worth the complexity? I like @sdaftuar’s suggestion.

   ---

   

   morcos commented at 8:54 pm on June 8, 2017:

   Yes I like his suggestion as well. I think this PR is “correct” as is, and I will make that change in a separate PR as a fix to HaveCoinsInCache?

   ---

   

   sipa commented at 8:59 pm on June 8, 2017:

   Ok.
3. 
   sipa commented at 9:06 pm on June 8, 2017: member

   utACK 301566d1cb49e7ef78d91e0eb86783deee1885db
4. fanquake added the label Validation on Jun 8, 2017
5. 
   sipa commented at 1:29 am on June 23, 2017: member

   Needs rebase.
6. Make check to distinguish between orphan txs and old txs more efficient.

   Checking for the existence in the CCoinsViewCache of the outputs of a new tx
   will result in a disk hit for every output since they will not be found.  On the
   other hand if those outputs exist already, then the inputs must also have been
   missing, so we can move this check inside the input existence check so in the
   common case of a new tx it doesn't need to run.
   
   The purpose of the check is to avoid spamming the orphanMap with slightly old
   txs which we have already seen in a block, but it is already only optimistic
   (depending on the outputs not being spent), so make it even more efficient by
   only checking the cache and not the entire pcoinsTip.

   18bacec6c2
7. morcos force-pushed on Jun 27, 2017
8. 
   morcos commented at 6:16 pm on June 27, 2017: member

   Simple rebase due to #10503
9. 
   TheBlueMatt commented at 11:52 pm on June 27, 2017: member

   utACK 18bacec6c2c8493fd6b7011778446b3c7473bb25
10. 
    morcos commented at 2:15 am on July 7, 2017: member

    Please tag for 0.15
11. fanquake added this to the milestone 0.15.0 on Jul 7, 2017
12. gmaxwell approved
13. 
    gmaxwell commented at 11:22 pm on July 13, 2017: contributor

    utACK. “Duh”– it should have always done this.
14. 
    gmaxwell commented at 0:00 am on July 14, 2017: contributor

    This will spam the orphan map somewhat after flushing, unfortunately– but we can fix this by making flushing less hard in the future… and the orphan map is much less important than it used to be already.
15. 
    TheBlueMatt commented at 6:39 pm on July 14, 2017: member

    I still think we should take this for 15, but another thing to consider is to add a rolling bloom filter in net_processing ala https://github.com/TheBlueMatt/bitcoin/commit/316516cfd872a812f9672834c857bd084c5a877a (which is based on a big pile of changes, but could be pulled out separately), on top of this change.
16. sipa merged this on Jul 14, 2017
17. sipa closed this on Jul 14, 2017

    ---

18. sipa referenced this in commit 66270a416e on Jul 14, 2017
19. PastaPastaPasta referenced this in commit baa0fa98a1 on Jul 6, 2019
20. PastaPastaPasta referenced this in commit 605b7f7efd on Jul 8, 2019
21. PastaPastaPasta referenced this in commit f474fefa21 on Jul 9, 2019
22. PastaPastaPasta referenced this in commit 274de092d8 on Jul 11, 2019
23. PastaPastaPasta referenced this in commit a2e8bbc726 on Jul 13, 2019
24. PastaPastaPasta referenced this in commit a4785312b6 on Jul 17, 2019
25. PastaPastaPasta referenced this in commit dd73cf619b on Jul 17, 2019
26. PastaPastaPasta referenced this in commit 17177202a0 on Jul 18, 2019
27. barrystyle referenced this in commit e0e120b23b on Jan 22, 2020
28. DrahtBot locked this on Sep 8, 2021

Contributors
morcos sipa sdaftuar TheBlueMatt gmaxwell

Labels
Validation

Milestone
0.15.0