problem might be py2 vs py3. For queens we only have python3-nova and no python-nova (reference version 2:17.0.11-1).

Change 576290 had a related patch set uploaded (by Arturo Borrero Gonzalez; owner: Arturo Borrero Gonzalez):
[operations/puppet@production] openstack: serverpackages: queens: stretch: introduce some apt pinnings

https://gerrit.wikimedia.org/r/576290

Change 576290 merged by Arturo Borrero Gonzalez:
[operations/puppet@production] openstack: serverpackages: queens: stretch: introduce some apt pinnings

https://gerrit.wikimedia.org/r/576290

I'm working on cloudservices2002-dev.

The first issue I see is that we're not getting the key for the new repo from puppet:

GPG error: http://mirrors.wikimedia.org/osbpo stretch-queens-backports InRelease: The following signatures couldn't be verified because the public key is not available: NO_PUBKEY 56056AB2FEE4EECB

I've hacked around that temporarily; the next issue I see is that apt doesn't ever settle into a state where everything is upgraded. No matter how many 'apt-get update && apt-get upgrade' cycles I run it still shows 20+ packages to upgrade. And some of them behave strangely, e.g.:

Preparing to unpack .../0-python-chardet_3.0.4-1~bpo9+1_all.deb ...
Unpacking python-chardet (3.0.4-1~bpo9+1) over (3.0.4-1~bpo9+1) ...
Preparing to unpack .../1-python-idna_2.6-1~bpo9+1_all.deb ...
Unpacking python-idna (2.6-1~bpo9+1) over (2.6-1~bpo9+1) ...
Preparing to unpack .../2-python-jinja2_2.10-1~bpo9+1_all.deb ...
Unpacking python-jinja2 (2.10-1~bpo9+1) over (2.10-1~bpo9+1) ...
Preparing to unpack .../3-python-munch_2.2.0-2~bpo9+1_all.deb ...
Unpacking python-munch (2.2.0-2~bpo9+1) over (2.2.0-2~bpo9+1) ..

etc.

Change 576643 had a related patch set uploaded (by Arturo Borrero Gonzalez; owner: Arturo Borrero Gonzalez):
[operations/puppet@production] openstack: serverpackages: include pubkey for osbpo repository

https://gerrit.wikimedia.org/r/576643

Change 576643 merged by Arturo Borrero Gonzalez:
[operations/puppet@production] openstack: serverpackages: include pubkey for osbpo repository

https://gerrit.wikimedia.org/r/576643

In T246671#5937828, @Andrew wrote:

I'm working on cloudservices2002-dev.

The first issue I see is that we're not getting the key for the new repo from puppet:

GPG error: http://mirrors.wikimedia.org/osbpo stretch-queens-backports InRelease: The following signatures couldn't be verified because the public key is not available: NO_PUBKEY 56056AB2FEE4EECB

This should be fixed now, puppet patch.

I've hacked around that temporarily; the next issue I see is that apt doesn't ever settle into a state where everything is upgraded. No matter how many 'apt-get update && apt-get upgrade' cycles I run it still shows 20+ packages to upgrade. And some of them behave strangely, e.g.:

Preparing to unpack .../0-python-chardet_3.0.4-1~bpo9+1_all.deb ...
Unpacking python-chardet (3.0.4-1~bpo9+1) over (3.0.4-1~bpo9+1) ...
Preparing to unpack .../1-python-idna_2.6-1~bpo9+1_all.deb ...
Unpacking python-idna (2.6-1~bpo9+1) over (2.6-1~bpo9+1) ...
Preparing to unpack .../2-python-jinja2_2.10-1~bpo9+1_all.deb ...
Unpacking python-jinja2 (2.10-1~bpo9+1) over (2.10-1~bpo9+1) ...
Preparing to unpack .../3-python-munch_2.2.0-2~bpo9+1_all.deb ...
Unpacking python-munch (2.2.0-2~bpo9+1) over (2.2.0-2~bpo9+1) ..

This is annoying but harmless. I couldn't find yet a proper solution to this.

The problem is the exact same packages are present in two different repositories and this confuses the apt resolver. I tried with different pinning configurations with no luck so far.
I'm inclined to stop looking any further unless we decide this is an actual problem worth investing the time to solve it.

Now this weird thing is happening on cloudservices2002-dev:

Err:2 http://apt.wikimedia.org/wikimedia stretch-wikimedia InRelease
  The following signatures couldn't be verified because the public key is not available: NO_PUBKEY 9D392D3FFADF18FB
No directory, logging in with HOME=/

This key is apparently configured as part of our server install setup, see modules/install_server/files/autoinstall/common.cfg in the puppet tree.
In the resulting server filesystem, the key is added to /etc/apt/trusted.gpg. In a "sane" hardware server, this contains the apt.wikimedia.org key, but not in cloudservices2002-dev.

I checked the server and I found the /etc/apt/trusted.gpg was mangled (by hand?) and only contained the osbpo key:

aborrero@cloudservices2002-dev:~ $ sudo apt-key list
/etc/apt/trusted.gpg
--------------------
pub   rsa4096 2019-11-16 [SCEA]
      0FB8 E8DD 1949 8FEC 90B2  5E5E 5605 6AB2 FEE4 EECB
uid           [ unknown] Autogenerated key <root@osbpo.debian.net>

So I just added the missing key by hand following the docs: https://wikitech.wikimedia.org/wiki/APT_repository#Security

and now:

aborrero@cloudservices2002-dev:~ 2s $ sudo apt-key list
/etc/apt/trusted.gpg
--------------------
pub   rsa4096 2019-11-16 [SCEA]
      0FB8 E8DD 1949 8FEC 90B2  5E5E 5605 6AB2 FEE4 EECB
uid           [ unknown] Autogenerated key <root@osbpo.debian.net>

pub   rsa4096 2017-02-10 [SC]
      B8A2 DF05 748F 9D52 4A3A  2ADE 9D39 2D3F FADF 18FB
uid           [ unknown] Wikimedia Archive Automatic Signing Key <root@wikimedia.org>

apt upgrade works now!