[Wallet] Worst case performance improvement on KeyPool filtering #10184

pull NicolasDorier wants to merge 1 commits into bitcoin:master from NicolasDorier:hdinternalperf changing 1 files +6 −3
  1. NicolasDorier commented at 11:36 am on April 11, 2017: contributor

    #9294 introduced internal HD chain. This made ReserveKeyFromPool iterates on the whole keypool (One disk access per key) to find a key matching internal.

    This PR changes the way TopUpKeyPool creates keys in the pool. Instead of creating all the external keys followed by all the internal keys (which would provoke lots of disk hit in ReserveKeyFromPool if internal is true), it alternates them.

  2. NicolasDorier force-pushed on Apr 11, 2017
  3. [Wallet] Worst case performance improvement on KeyPool filtering 153966ccd5
  4. NicolasDorier force-pushed on Apr 11, 2017
  5. TheBlueMatt commented at 10:42 pm on April 11, 2017: member
    Isnt it a much simpler approach to just switch the keypool set to two separate sets instead? On wallet load we read each keypool entry from disk anyway, so just caching it differently should be trivial.
  6. NicolasDorier commented at 2:32 am on April 12, 2017: contributor

    I think this would be the right long term approach. I don’t think it is simple to change though. This PR is just some tape on the current approach.

    Anyway, I take a look, maybe it is not as complicated as I think.

  7. fanquake added the label Wallet on Apr 12, 2017
  8. jonasschnelli commented at 12:50 pm on April 12, 2017: contributor

    Long term, keypools do make little sense to me, in conjunction with HD. For encrypted wallets, we may want to disable any private key export function and use public key derivation (and remove both keypools). For the HD lookup window, we can generate (in memory) ~+50 keys during startup and extend it whenever the user retrieves a new address. IMO there is no need to persist the set.

    I’m not sure if it’s worth to optimise this further (this PR seems to be okay though).

  9. TheBlueMatt commented at 2:17 pm on April 12, 2017: member

    @jonasschnelli I think we very much need to fix the performance regressions before 0.15. The introduction of many disk hits on some paths is potentially a huge issue for some users.

    I’m slightly confused about this PR, however. Am I reading it correctly to think that its just a different way of identifying keys and the actual performance improvements will come in a later PR?

  10. NicolasDorier commented at 7:32 am on April 13, 2017: contributor

    @TheBlueMatt I think this PR is enough to solve current inconvenience.

    Before:

    TopUp of 100 key will fill the keypool in the following way:

    [external1][external2]…[external100][internal1][internal2]…[internal100]

    Now if you call ReserveKeyFromPool with internal=true this create 100 disk hit.

    This PR makes it so TopUp of 100 key fill the keypool in the following way

    [external1][internal1][external2][internal2]…[external100][internal100]

    Which mean that ReserveKeyFromPool will have 2 disk hits instead of 100.

  11. TheBlueMatt commented at 12:53 pm on April 13, 2017: member

    @NicolasDorier ahh, indeed, I was being dense. Still, we should also fix the massive slowdown in keypool counting (which I somehow assumed this was meant to also solve, though in a super roundabout way).

    On April 13, 2017 3:32:54 AM EDT, Nicolas Dorier notifications@github.com wrote:

    @TheBlueMatt I think this PR is enough to solve current inconvenience.

    Before:

    TopUp of 100 key will fill the keypool in the following way:

    [external1][external2]…[external100][internal1][internal2]…[internal100]

    Now if you call ReserveKeyFromPool with internal=true this create 100 disk hit.

    This PR makes it so TopUp of 100 key fill the keypool in the following way

    [external1][internal1][external2][internal2]…[external100][internal100]

    Which mean that ReserveKeyFromPool will have 2 disk hits instead of 100.

  12. NicolasDorier commented at 2:44 pm on April 13, 2017: contributor
    @TheBlueMatt I don’t think the perf regression is that bad. The only time there is a count is during TopUpKeyPool, which is slow anyway. With this PR the perf regression become +1 disk hit per call to ReserveKeyFromPool, which is not that bad.
  13. TheBlueMatt commented at 2:50 pm on April 13, 2017: member
    @NicolasDorier There are also a performance regression in GetOldestKeyPoolTime(), making getinfo and getwalletinfo have to iterate the entire keypool reading each element from disk. Note that TopUpKeyPool is called in a bunch of places, and isnt supposed to always be slow, as it is often called to top up the keypool by generating one or zero keys.
  14. NicolasDorier commented at 1:56 am on April 14, 2017: contributor

    @TheBlueMatt I think the problem of TopUpKeyPool is orthogonal to this PR. If we solve the TopUpKeyPool problem by caching the count, then we would still have the problem of 100 disk hit when creating internal key.

    Except if we cache the keys of the pool itself, and not only the count.

  15. TheBlueMatt commented at 8:01 pm on April 14, 2017: member
    @NicolasDorier yes, that was my original suggestion - split setKeyPool into two (since we already cache the sets of keys, might as well split them to keep extra information), and then you can fix TopUpKeyPool and all the other issues in one go :).
  16. jonasschnelli commented at 10:10 am on April 19, 2017: contributor

    To add some benchmarks to those speculation: System: host = OSX 2.9 GHz Intel Core i7, running a Ubuntu 16.10 VM with all 8 cores.

    I’m not convinced that we have a performance issue there,.. though I’m not opposed against doing performance improvements like this PR.

    0.14.1rc2 (non chain switch)

    getwalletinfo with a single key

     0user@ubuntu:~/Desktop$ time ./bitcoin-0.14.1/bin/bitcoin-cli --regtest --datadir=/home/user/Desktop/n1 getwalletinfo
 1{
 2  "walletversion": 130000,
 3  "balance": 0.00000000,
 4  "unconfirmed_balance": 0.00000000,
 5  "immature_balance": 0.00000000,
 6  "txcount": 0,
 7  "keypoololdest": 1492595934,
 8  "keypoolsize": 1,
 9  "paytxfee": 0.00000000,
10  "hdmasterkeyid": "a22d397ef2fb35d02ddbd096cd7f7f4c9dad189b"
11}
12
13real	0m0.004s
14user	0m0.000s
15sys	0m0.000s

    top up keypool 1000 keys

    0user@ubuntu:~/Desktop$ time ./bitcoin-0.14.1/bin/bitcoin-cli --regtest --datadir=/home/user/Desktop/n1 keypoolrefill 1000
1
2real	0m1.407s
3user	0m0.000s
4sys	0m0.000s

    getwalletinfo (there are now 1000 keys)

     0user@ubuntu:~/Desktop$ time ./bitcoin-0.14.1/bin/bitcoin-cli --regtest --datadir=/home/user/Desktop/n1 getwalletinfo
 1{
 2  "walletversion": 130000,
 3  "balance": 0.00000000,
 4  "unconfirmed_balance": 0.00000000,
 5  "immature_balance": 0.00000000,
 6  "txcount": 0,
 7  "keypoololdest": 1492595934,
 8  "keypoolsize": 1001,
 9  "paytxfee": 0.00000000,
10  "hdmasterkeyid": "a22d397ef2fb35d02ddbd096cd7f7f4c9dad189b"
11}
12
13real	0m0.012s
14user	0m0.000s
15sys	0m0.012s

    topup a single key

    0user@ubuntu:~/Desktop$ time ./bitcoin-0.14.1/bin/bitcoin-cli --regtest --datadir=/home/user/Desktop/n1 keypoolrefill 1001
1
2real	0m0.007s
3user	0m0.000s
4sys	0m0.000s

    With current master (build yesterday) https://bitcoin.jonasschnelli.ch/build/102

    getwalletinfo with a single key

     0user@ubuntu:~/Desktop$ time ./bitcoin-0.14.1/bin/bitcoin-cli --regtest --datadir=/home/user/Desktop/n2 getwalletinfo
 1{
 2  "walletversion": 139900,
 3  "balance": 0.00000000,
 4  "unconfirmed_balance": 0.00000000,
 5  "immature_balance": 0.00000000,
 6  "txcount": 0,
 7  "keypoololdest": 1492596058,
 8  "keypoolsize": 0,
 9  "keypoolsize_hd_internal": 1,
10  "paytxfee": 0.00000000,
11  "hdmasterkeyid": "658072512a5a0a71cdbe16a7dca1a55ac8ab82fe"
12}
13
14real	0m0.003s
15user	0m0.000s
16sys	0m0.000s

    topupkeypool with 1000x2 (now we have also 1000 internal keys)

    0user@ubuntu:~/Desktop$ time ./bitcoin-0.14.1/bin/bitcoin-cli --regtest --datadir=/home/user/Desktop/n2 keypoolrefill 1000
1
2real	0m2.752s
3user	0m0.000s
4sys	0m0.000s

    getwalletinfo now with 1000x2 keys

     0user@ubuntu:~/Desktop$ time ./bitcoin-0.14.1/bin/bitcoin-cli --regtest --datadir=/home/user/Desktop/n2 getwalletinfo
 1{
 2  "walletversion": 139900,
 3  "balance": 0.00000000,
 4  "unconfirmed_balance": 0.00000000,
 5  "immature_balance": 0.00000000,
 6  "txcount": 0,
 7  "keypoololdest": 1492596074,
 8  "keypoolsize": 1000,
 9  "keypoolsize_hd_internal": 1000,
10  "paytxfee": 0.00000000,
11  "hdmasterkeyid": "658072512a5a0a71cdbe16a7dca1a55ac8ab82fe"
12}
13
14
15real	0m0.008s
16user	0m0.000s
17sys	0m0.000s

    topup a single key (actually two keys one internal one external)

    0user@ubuntu:~/Desktop$ time ./bitcoin-0.14.1/bin/bitcoin-cli --regtest --datadir=/home/user/Desktop/n2 keypoolrefill 1001
1
2real	0m0.012s
3user	0m0.000s
4sys	0m0.000s

    getwalletinfo

     0user@ubuntu:~/Desktop$ time ./bitcoin-0.14.1/bin/bitcoin-cli --regtest --datadir=/home/user/Desktop/n2 getwalletinfo
 1{
 2  "walletversion": 139900,
 3  "balance": 0.00000000,
 4  "unconfirmed_balance": 0.00000000,
 5  "immature_balance": 0.00000000,
 6  "txcount": 0,
 7  "keypoololdest": 1492596074,
 8  "keypoolsize": 1001,
 9  "keypoolsize_hd_internal": 1001,
10  "paytxfee": 0.00000000,
11  "hdmasterkeyid": "658072512a5a0a71cdbe16a7dca1a55ac8ab82fe"
12}
13
14real	0m0.008s
15user	0m0.000s
16sys	0m0.000s
  17. NicolasDorier commented at 11:38 am on April 19, 2017: contributor
    @jonasschnelli what disk drive are you using, SSD? I fear this has way more impact on HD or network attached disk which suffer high latency.
  18. jonasschnelli commented at 12:01 pm on April 19, 2017: contributor
    @NicolasDorier: Yes. It was SSD. NAS for key storage? Is that a reasonable use-case? I will redo the tests on an external USB 2 spinning disk a.s.a.p.
  19. NicolasDorier commented at 1:42 pm on April 19, 2017: contributor

    @jonasschnelli my bitcoin instances are hosted on Azure for example, attached data storages drives have kind of bad latency. Around 7ms if I remember.

    Let me know, if it is not so bad with USB, I will also try on an azure instance.

  20. TheBlueMatt commented at 3:09 pm on April 19, 2017: member
    @jonasschnelli sadly many, many servers use SANs for storage to avoid relying on a single server’s storage infrastructure.
  21. jonasschnelli commented at 3:22 pm on April 19, 2017: contributor

    I now connected a relatively old 2.5" HDD (1TB, spinning) to my Host (OSX) and made it available via folder sharing.

    I can’t see even a mild performance issue.

    The results are:

    0.14.1rc2

    getwalletinfo with a single key keypool:

     0time ./bitcoin-0.14.1/bin/bitcoin-cli --regtest --datadir=/mnt/hgfs/dummy/n1 getwalletinfo
 1{
 2  "walletversion": 130000,
 3  "balance": 0.00000000,
 4  "unconfirmed_balance": 0.00000000,
 5  "immature_balance": 0.00000000,
 6  "txcount": 0,
 7  "keypoololdest": 1492614680,
 8  "keypoolsize": 1,
 9  "paytxfee": 0.00000000,
10  "hdmasterkeyid": "07daa6d010bdc3c756d58acafce93ac322d66df1"
11}
12
13real	0m0.006s
14user	0m0.000s
15sys	0m0.004s

    topup keypool to 1000 keys

    0time ./bitcoin-0.14.1/bin/bitcoin-cli --regtest --datadir=/mnt/hgfs/dummy/n1 keypoolrefill 1000
1
2real	0m4.609s
3user	0m0.000s
4sys	0m0.000s

    getwalletinfo on a 1000 keys keypool

     0time ./bitcoin-0.14.1/bin/bitcoin-cli --regtest --datadir=/mnt/hgfs/dummy/n1 getwalletinfo
 1{
 2  "walletversion": 130000,
 3  "balance": 0.00000000,
 4  "unconfirmed_balance": 0.00000000,
 5  "immature_balance": 0.00000000,
 6  "txcount": 0,
 7  "keypoololdest": 1492614680,
 8  "keypoolsize": 1001,
 9  "paytxfee": 0.00000000,
10  "hdmasterkeyid": "07daa6d010bdc3c756d58acafce93ac322d66df1"
11}
12
13real	0m0.009s
14user	0m0.000s
15sys	0m0.000s

    topup and add a single key (= 1001 keys)

    0time ./bitcoin-0.14.1/bin/bitcoin-cli --regtest --datadir=/mnt/hgfs/dummy/n1 keypoolrefill 1001
1
2real	0m0.010s
3user	0m0.004s
4sys	0m0.000s

    with nightly build from yesterday

    ### getwalletinfo single key keypool

     0time ./bitcoin-0.14.1/bin/bitcoin-cli --regtest --datadir=/mnt/hgfs/dummy/n2 getwalletinfo
 1{
 2  "walletversion": 139900,
 3  "balance": 0.00000000,
 4  "unconfirmed_balance": 0.00000000,
 5  "immature_balance": 0.00000000,
 6  "txcount": 0,
 7  "keypoololdest": 1492614816,
 8  "keypoolsize": 0,
 9  "keypoolsize_hd_internal": 1,
10  "paytxfee": 0.00000000,
11  "hdmasterkeyid": "aaca57ac9a28ad0097a6b4d9f256e9a8ca02b16a"
12}
13
14real	0m0.004s
15user	0m0.000s
16sys	0m0.000s

    ### topup keypool (1000 keys each == 2000 keys)

    0time ./bitcoin-0.14.1/bin/bitcoin-cli --regtest --datadir=/mnt/hgfs/dummy/n2 keypoolrefill 1000
1
2real	0m4.367s
3user	0m0.000s
4sys	0m0.000s

    getwalletinfo on a 1000+1000 keys keypool

     0time ./bitcoin-0.14.1/bin/bitcoin-cli --regtest --datadir=/mnt/hgfs/dummy/n2 getwalletinfo
 1{
 2  "walletversion": 139900,
 3  "balance": 0.00000000,
 4  "unconfirmed_balance": 0.00000000,
 5  "immature_balance": 0.00000000,
 6  "txcount": 0,
 7  "keypoololdest": 1492614832,
 8  "keypoolsize": 1000,
 9  "keypoolsize_hd_internal": 1000,
10  "paytxfee": 0.00000000,
11  "hdmasterkeyid": "aaca57ac9a28ad0097a6b4d9f256e9a8ca02b16a"
12}
13
14real	0m0.047s
15user	0m0.000s
16sys	0m0.000s

    topup a single key

    0time ./bitcoin-0.14.1/bin/bitcoin-cli --regtest --datadir=/mnt/hgfs/dummy/n2 keypoolrefill 1001
1
2real	0m0.020s
3user	0m0.000s
4sys	0m0.000s
  22. jonasschnelli commented at 3:27 pm on April 19, 2017: contributor

    @TheBlueMatt @NicolasDorier: SAN for servers make sense. But here we talk about key material, maybe even secret key material. Storing something like this on an Azure system or VPS SAN can be reckless. What would be the worst case if the SAN/Cloud provider could inject/alter the pubkeys during fetch? Could an attacker re-route incoming funds?

    IMO full nodes (especially those with --enable-wallet) and Azure, AWS, etc. are fundamentally incompatible.

    I see reasons to move block files or to a SAN, but what could be the reason to move the wallet BerkleyDB to a NAS? If you have no other options you are very likely doing something very insecure.

  23. TheBlueMatt commented at 5:13 pm on April 19, 2017: member
    @jonasschnelli see #10235, I think the changes are pretty simple, so still worth doing. As for discouraging use on remote hosts, I dont buy that argument. What if someone buys insurance or has little money on it? Doesn’t mean it shouldnt perform.
  24. NicolasDorier commented at 3:39 am on April 20, 2017: contributor

    @jonasschnelli I think the perf are not that bad actually. Will review #10235. It does not seems that bad to fix properly.

    I am using Bitcoin Core more for coin tracking with watch only and the hdwatchonly.

    When it is not the case, it really depends on how much money are stored on it, versus the cost and inconvenience of hosting my own physical server.

  25. NicolasDorier commented at 3:57 am on April 20, 2017: contributor
    Closing in favor of #10235 which solve the problem completely, and simplify things.
  26. NicolasDorier closed this on Apr 20, 2017
  27. sipa referenced this in commit 5cfdda2503 on Jul 15, 2017
  28. DrahtBot locked this on Sep 8, 2021


NicolasDorier TheBlueMatt jonasschnelli

Labels
Wallet

github-metadata-mirror

This is a metadata mirror of the GitHub repository bitcoin/bitcoin. This site is not affiliated with GitHub. Content is generated from a GitHub metadata backup.
generated: 2024-12-18 06:12 UTC
This site is hosted by @0xB10C
More mirrored repositories can be found on mirror.b10c.me