Proposal: New keydb format

[Neal H. Walfield]

Hi,

Some people have complained that GnuPG is slow when accessing the key
db (e.g., [1]).  To mitigate this, GnuPG has some ugly caches (commit
492792), which are not completely transparent and introduce subtle
bugs that are very hard to find (see, e.g., commits 60bc518 and
ee7ec12, which demonstrate a cache inconsistency).

Werner was the opinion that the performance problem is due to
signature verification and not due to DB accesses.  To test this
theory, I did some measurements yesterday and I implemented a small
prototype, which uses SQLite as the underlying storage engine.  It can
be retrieved from git on the neal/next branch.

  [1] https://bugs.gnupg.org/gnupg/issue2019

Here are some timing results.  I use the Debian keyring
(/usr/share/keyrings/debian-keyring.gpg), which contains 751 keys.

Importing the keyring: 2 minutes (keybox) vs. 8 seconds (new):

  $ rm pubring.kdx; time gpg2 --no-default-keyring --primary-keyring
  gnupg-kbx:pubring.kdx --import debian-keyring.gpg >/dev/null
  gpg: Total number processed: 751
  gpg:               imported: 751
  gpg: public key of ultimately trusted key 2183839A not found
  gpg: public key of ultimately trusted key BC15C85A not found
  gpg: public key of ultimately trusted key EE37CF96 not found
  
  real	1m52.560s
  user	0m6.268s
  sys	0m31.604s

  $ rm pubring.kdb; time gpg2 --no-default-keyring --primary-keyring
  gnupg-kdb:pubring.kdb --import debian-keyring.gpg >/dev/null
  gpg: Total number processed: 751
  gpg:               imported: 751
  
  real	0m7.729s
  user	0m5.404s
  sys	0m0.332s


Running --check-trustdb: 1 second (keybox) vs 0.2 seconds (new):

  $ time gpg2 --no-default-keyring --primary-keyring gnupg-kbx:pubring.kbx --check-trustdb
  real	0m0.975s
  user	0m0.012s
  sys	0m0.032s

  $ time gpg2 --no-default-keyring --primary-keyring gnupg-kdb:pubring.kdb --check-trustdb
  real	0m0.158s
  user	0m0.004s
  sys	0m0.004s

Doing a sequential scan is a bit slower with the new format: 1.2s
(keybox) vs 2.5s (new):

  $ time gpg2 --no-default-keyring --primary-keyring gnupg-kbx:pubring.kdx -k |
  grep ^pub | wc -l
  gpg: NOTE: THIS IS A DEVELOPMENT VERSION!
  gpg: It is only intended for test purposes and should NOT be
  gpg: used in a production environment or with production keys!
  751
  
  real	0m1.245s
  user	0m1.168s
  sys	0m0.076s
  
  $ time gpg2 --no-default-keyring --primary-keyring gnupg-kdb:pubring.kdb -k |
  grep ^pub | wc -l
  751
  
  real	0m2.515s
  user	0m2.432s
  sys	0m0.088s

This is likely due to the impedance mismatch between the current
interface for doing a full scan and SQLite API's interface for doing a
full scan (we need to resume the search; currently I reexecute a query
for each new result and skip the previous results).  If we decide to
use the new format, it shouldn't be hard to improve this.


I'd be interested in any feedback as well as some more measurements of
the performance in real conditions.  Note: the code is incomplete, but
the essentials should work.

Thanks,

:) Neal