Repository: libp2p/go-libp2p
Pull request #1667 (2022-08-09 11:41:54)

move go-libp2p-peerstore to p2p/host/peerstore
Part of #1556.


Patch:
diff --git a/config/config.go b/config/config.go
index e1ce6545..405d6d97 100644
--- a/config/config.go
+++ b/config/config.go
@@ -16,12 +16,12 @@ import (
 	"github.com/libp2p/go-libp2p-core/routing"
 	"github.com/libp2p/go-libp2p-core/sec"
 	"github.com/libp2p/go-libp2p-core/transport"
-	"github.com/libp2p/go-libp2p-peerstore/pstoremem"
 
 	"github.com/libp2p/go-libp2p/p2p/host/autonat"
 	"github.com/libp2p/go-libp2p/p2p/host/autorelay"
 	bhost "github.com/libp2p/go-libp2p/p2p/host/basic"
 	blankhost "github.com/libp2p/go-libp2p/p2p/host/blank"
+	"github.com/libp2p/go-libp2p/p2p/host/peerstore/pstoremem"
 	routed "github.com/libp2p/go-libp2p/p2p/host/routed"
 	"github.com/libp2p/go-libp2p/p2p/net/swarm"
 	tptu "github.com/libp2p/go-libp2p/p2p/net/upgrader"
diff --git a/defaults.go b/defaults.go
index 26d9d416..904d8e6f 100644
--- a/defaults.go
+++ b/defaults.go
@@ -5,6 +5,7 @@ package libp2p
 import (
 	"crypto/rand"
 
+	"github.com/libp2p/go-libp2p/p2p/host/peerstore/pstoremem"
 	"github.com/libp2p/go-libp2p/p2p/muxer/yamux"
 	"github.com/libp2p/go-libp2p/p2p/net/connmgr"
 	"github.com/libp2p/go-libp2p/p2p/security/noise"
@@ -15,7 +16,6 @@ import (
 
 	"github.com/libp2p/go-libp2p-core/crypto"
 
-	"github.com/libp2p/go-libp2p-peerstore/pstoremem"
 	rcmgr "github.com/libp2p/go-libp2p-resource-manager"
 	"github.com/multiformats/go-multiaddr"
 )
diff --git a/go.mod b/go.mod
index 2431b45a..4b93dfd7 100644
--- a/go.mod
+++ b/go.mod
@@ -13,6 +13,8 @@ require (
 	github.com/hashicorp/golang-lru v0.5.4
 	github.com/ipfs/go-cid v0.2.0
 	github.com/ipfs/go-datastore v0.5.1
+	github.com/ipfs/go-ds-badger v0.3.0
+	github.com/ipfs/go-ds-leveldb v0.5.0
 	github.com/ipfs/go-log/v2 v2.5.1
 	github.com/jbenet/go-temp-err-catcher v0.1.0
 	github.com/klauspost/compress v1.15.1
@@ -20,7 +22,6 @@ require (
 	github.com/libp2p/go-eventbus v0.2.1
 	github.com/libp2p/go-libp2p-asn-util v0.2.0
 	github.com/libp2p/go-libp2p-core v0.19.1
-	github.com/libp2p/go-libp2p-peerstore v0.7.1
 	github.com/libp2p/go-libp2p-resource-manager v0.5.1
 	github.com/libp2p/go-libp2p-testing v0.11.0
 	github.com/libp2p/go-mplex v0.7.0
@@ -34,6 +35,7 @@ require (
 	github.com/marten-seemann/tcp v0.0.0-20210406111302-dfbc87cc63fd
 	github.com/mikioh/tcpinfo v0.0.0-20190314235526-30a79bb1804b
 	github.com/minio/sha256-simd v1.0.0
+	github.com/multiformats/go-base32 v0.0.4
 	github.com/multiformats/go-multiaddr v0.6.0
 	github.com/multiformats/go-multiaddr-dns v0.3.1
 	github.com/multiformats/go-multiaddr-fmt v0.1.0
@@ -43,14 +45,17 @@ require (
 	github.com/prometheus/client_golang v1.12.1
 	github.com/raulk/go-watchdog v1.3.0
 	github.com/stretchr/testify v1.8.0
+	go.uber.org/goleak v1.1.12
 	golang.org/x/crypto v0.0.0-20220525230936-793ad666bf5e
 	golang.org/x/sync v0.0.0-20210220032951-036812b2e83c
 	golang.org/x/sys v0.0.0-20220520151302-bc2c85ada10a
 )
 
 require (
+	github.com/AndreasBriese/bbloom v0.0.0-20190825152654-46b345b51c96 // indirect
 	github.com/beorn7/perks v1.0.1 // indirect
 	github.com/btcsuite/btcd/btcec/v2 v2.2.0 // indirect
+	github.com/cespare/xxhash v1.1.0 // indirect
 	github.com/cespare/xxhash/v2 v2.1.2 // indirect
 	github.com/cheekybits/genny v1.0.0 // indirect
 	github.com/containerd/cgroups v1.0.4 // indirect
@@ -58,13 +63,17 @@ require (
 	github.com/coreos/go-systemd/v22 v22.3.2 // indirect
 	github.com/davecgh/go-spew v1.1.1 // indirect
 	github.com/decred/dcrd/dcrec/secp256k1/v4 v4.0.1 // indirect
+	github.com/dgraph-io/badger v1.6.2 // indirect
+	github.com/dgraph-io/ristretto v0.0.2 // indirect
 	github.com/docker/go-units v0.4.0 // indirect
+	github.com/dustin/go-humanize v1.0.0 // indirect
 	github.com/elastic/gosigar v0.14.2 // indirect
 	github.com/francoispqt/gojay v1.2.13 // indirect
 	github.com/fsnotify/fsnotify v1.5.4 // indirect
 	github.com/go-task/slim-sprig v0.0.0-20210107165309-348f09dbbbc0 // indirect
 	github.com/godbus/dbus/v5 v5.1.0 // indirect
 	github.com/golang/protobuf v1.5.2 // indirect
+	github.com/golang/snappy v0.0.0-20180518054509-2e65f85255db // indirect
 	github.com/google/uuid v1.3.0 // indirect
 	github.com/huin/goupnp v1.0.3 // indirect
 	github.com/jackpal/go-nat-pmp v1.0.2 // indirect
@@ -83,7 +92,6 @@ require (
 	github.com/miekg/dns v1.1.50 // indirect
 	github.com/mikioh/tcpopt v0.0.0-20190314235656-172688c1accc // indirect
 	github.com/mr-tron/base58 v1.2.0 // indirect
-	github.com/multiformats/go-base32 v0.0.4 // indirect
 	github.com/multiformats/go-base36 v0.1.0 // indirect
 	github.com/multiformats/go-multibase v0.1.1 // indirect
 	github.com/multiformats/go-multicodec v0.5.0 // indirect
@@ -98,6 +106,7 @@ require (
 	github.com/prometheus/procfs v0.7.3 // indirect
 	github.com/spacemonkeygo/spacelog v0.0.0-20180420211403-2296661a0572 // indirect
 	github.com/spaolacci/murmur3 v1.1.0 // indirect
+	github.com/syndtr/goleveldb v1.0.0 // indirect
 	go.uber.org/atomic v1.9.0 // indirect
 	go.uber.org/multierr v1.8.0 // indirect
 	go.uber.org/zap v1.21.0 // indirect
diff --git a/go.sum b/go.sum
index ee45c59e..3560881c 100644
--- a/go.sum
+++ b/go.sum
@@ -38,9 +38,11 @@ dmitri.shuralyov.com/html/belt v0.0.0-20180602232347-f7d459c86be0/go.mod h1:JLBr
 dmitri.shuralyov.com/service/change v0.0.0-20181023043359-a85b471d5412/go.mod h1:a1inKt/atXimZ4Mv927x+r7UpyzRUf4emIoiiSC2TN4=
 dmitri.shuralyov.com/state v0.0.0-20180228185332-28bcc343414c/go.mod h1:0PRwlb0D6DFvNNtx+9ybjezNCa8XF0xaYcETyp6rHWU=
 git.apache.org/thrift.git v0.0.0-20180902110319-2566ecd5d999/go.mod h1:fPE2ZNJGynbRyZ4dJvy6G277gSllfV2HJqblrnkyeyg=
+github.com/AndreasBriese/bbloom v0.0.0-20190825152654-46b345b51c96 h1:cTp8I5+VIoKjsnZuH8vjyaysT/ses3EvZeaV/1UkF2M=
 github.com/AndreasBriese/bbloom v0.0.0-20190825152654-46b345b51c96/go.mod h1:bOvUY6CB00SOBii9/FifXqc0awNKxLFCL/+pkDPuyl8=
 github.com/BurntSushi/toml v0.3.1/go.mod h1:xHWCNGjB5oqiDr8zfno3MHue2Ht5sIBksp03qcyfWMU=
 github.com/BurntSushi/xgb v0.0.0-20160522181843-27f122750802/go.mod h1:IVnqGOEym/WlBOVXweHU+Q+/VP0lqqI8lqeDx9IjBqo=
+github.com/OneOfOne/xxhash v1.2.2 h1:KMrpdQIwFcEqXDklaen+P1axHaj9BSKzvpUUfnHldSE=
 github.com/OneOfOne/xxhash v1.2.2/go.mod h1:HSdplMjZKSmBqAxg5vPj2TmRDmfkzw+cTzAElWljhcU=
 github.com/aead/siphash v1.0.1/go.mod h1:Nywa3cDsYNNK3gaciGTWPwHt0wlpNV15vwmswBAUSII=
 github.com/alecthomas/template v0.0.0-20160405071501-a0175ee3bccc/go.mod h1:LOuyumcjzFXgccqObfd/Ljyb9UuFJ6TxHnclSeseNhc=
@@ -121,11 +123,15 @@ github.com/decred/dcrd/crypto/blake256 v1.0.0/go.mod h1:sQl2p6Y26YV+ZOcSTP6thNdn
 github.com/decred/dcrd/dcrec/secp256k1/v4 v4.0.1 h1:YLtO71vCjJRCBcrPMtQ9nqBsqpA1m5sE92cU+pd5Mcc=
 github.com/decred/dcrd/dcrec/secp256k1/v4 v4.0.1/go.mod h1:hyedUtir6IdtD/7lIxGeCxkaw7y45JueMRL4DIyJDKs=
 github.com/decred/dcrd/lru v1.0.0/go.mod h1:mxKOwFd7lFjN2GZYsiz/ecgqR6kkYAl+0pz0tEMk218=
+github.com/dgraph-io/badger v1.6.2 h1:mNw0qs90GVgGGWylh0umH5iag1j6n/PeJtNvL6KY/x8=
 github.com/dgraph-io/badger v1.6.2/go.mod h1:JW2yswe3V058sS0kZ2h/AXeDSqFjxnZcRrVH//y2UQE=
+github.com/dgraph-io/ristretto v0.0.2 h1:a5WaUrDa0qm0YrAAS1tUykT5El3kt62KNZZeMxQn3po=
 github.com/dgraph-io/ristretto v0.0.2/go.mod h1:KPxhHT9ZxKefz+PCeOGsrHpl1qZ7i70dGTu2u+Ahh6E=
+github.com/dgryski/go-farm v0.0.0-20190423205320-6a90982ecee2 h1:tdlZCpZ/P9DhczCTSixgIKmwPv6+wP5DGjqLYw5SUiA=
 github.com/dgryski/go-farm v0.0.0-20190423205320-6a90982ecee2/go.mod h1:SqUrOPUnsFjfmXRMNPybcSiG0BgUW2AuFH8PAnS2iTw=
 github.com/docker/go-units v0.4.0 h1:3uh0PgVws3nIA0Q+MwDC8yjEPf9zjRfZZWXZYDct3Tw=
 github.com/docker/go-units v0.4.0/go.mod h1:fgPhTUdO+D/Jk86RDLlptpiXQzgHJF7gydDDbaIK4Dk=
+github.com/dustin/go-humanize v1.0.0 h1:VSnTsYCnlFHaM2/igO1h6X3HA71jcobQuxemgkq4zYo=
 github.com/dustin/go-humanize v1.0.0/go.mod h1:HtrtbFcZ19U5GC7JDqmcUSB87Iq5E25KnS6fMYU6eOk=
 github.com/elastic/gosigar v0.12.0/go.mod h1:iXRIGg2tLnu7LBdpqzyQfGDEidKCfWcCMS0WKyPWoMs=
 github.com/elastic/gosigar v0.14.2 h1:Dg80n8cr90OZ7x+bAax/QjoW/XqTI11RmA79ZwIm9/4=
@@ -201,6 +207,7 @@ github.com/golang/protobuf v1.4.3/go.mod h1:oDoupMAO8OvCJWAcko0GGGIgR6R6ocIYbsSw
 github.com/golang/protobuf v1.5.0/go.mod h1:FsONVRAS9T7sI+LIUmWTfcYkHO4aIWwzhcaSAoJOfIk=
 github.com/golang/protobuf v1.5.2 h1:ROPKBNFfQgOUMifHyP+KYbvpjbdoFNs+aK7DXlji0Tw=
 github.com/golang/protobuf v1.5.2/go.mod h1:XVQd3VNwM+JqD3oG2Ue2ip4fOMUkwXdXDdiuN0vRsmY=
+github.com/golang/snappy v0.0.0-20180518054509-2e65f85255db h1:woRePGFeVFfLKN/pOkfl+p/TAqKOfFu+7KPlMVpok/w=
 github.com/golang/snappy v0.0.0-20180518054509-2e65f85255db/go.mod h1:/XxbfmMg8lxefKM7IXC3fBNl/7bRcc72aCRzEWrmP2Q=
 github.com/google/btree v0.0.0-20180813153112-4030bb1f1f0c/go.mod h1:lNA+9X1NB3Zf8V7Ke586lFgjr2dZNuvo3lPJSGZ5JPQ=
 github.com/google/btree v1.0.0/go.mod h1:lNA+9X1NB3Zf8V7Ke586lFgjr2dZNuvo3lPJSGZ5JPQ=
@@ -269,12 +276,13 @@ github.com/ipfs/go-datastore v0.5.1 h1:WkRhLuISI+XPD0uk3OskB0fYFSyqK8Ob5ZYew9Qa1
 github.com/ipfs/go-datastore v0.5.1/go.mod h1:9zhEApYMTl17C8YDp7JmU7sQZi2/wqiYh73hakZ90Bk=
 github.com/ipfs/go-detect-race v0.0.1 h1:qX/xay2W3E4Q1U7d9lNs1sU9nvguX0a7319XbyQ6cOk=
 github.com/ipfs/go-detect-race v0.0.1/go.mod h1:8BNT7shDZPo99Q74BpGMK+4D8Mn4j46UU0LZ723meps=
+github.com/ipfs/go-ds-badger v0.3.0 h1:xREL3V0EH9S219kFFueOYJJTcjgNSZ2HY1iSvN7U1Ro=
 github.com/ipfs/go-ds-badger v0.3.0/go.mod h1:1ke6mXNqeV8K3y5Ak2bAA0osoTfmxUdupVCGm4QUIek=
+github.com/ipfs/go-ds-leveldb v0.5.0 h1:s++MEBbD3ZKc9/8/njrn4flZLnCuY9I79v94gBUNumo=
 github.com/ipfs/go-ds-leveldb v0.5.0/go.mod h1:d3XG9RUDzQ6V4SHi8+Xgj9j1XuEk1z82lquxrVbml/Q=
 github.com/ipfs/go-ipfs-delay v0.0.0-20181109222059-70721b86a9a8/go.mod h1:8SP1YXK1M1kXuc4KJZINY3TQQ03J2rwBG9QfXmbRPrw=
 github.com/ipfs/go-ipfs-util v0.0.2/go.mod h1:CbPtkWJzjLdEcezDns2XYaehFVNXG9zrdrtMecczcsQ=
 github.com/ipfs/go-log/v2 v2.0.5/go.mod h1:eZs4Xt4ZUJQFM3DlanGhy7TkwwawCZcSByscwkWG+dw=
-github.com/ipfs/go-log/v2 v2.3.0/go.mod h1:QqGoj30OTpnKaG/LKTGTxoP2mmQtjVMEnK72gynbe/g=
 github.com/ipfs/go-log/v2 v2.5.0/go.mod h1:prSpmC1Gpllc9UYWxDiZDreBYw7zp4Iqp1kOLU9U5UI=
 github.com/ipfs/go-log/v2 v2.5.1 h1:1XdUzF7048prq4aBjDQQ4SL5RxftpRGdXhNRwKSAlcY=
 github.com/ipfs/go-log/v2 v2.5.1/go.mod h1:prSpmC1Gpllc9UYWxDiZDreBYw7zp4Iqp1kOLU9U5UI=
@@ -340,18 +348,14 @@ github.com/libp2p/go-libp2p-asn-util v0.2.0 h1:rg3+Os8jbnO5DxkC7K/Utdi+DkY3q/d1/
 github.com/libp2p/go-libp2p-asn-util v0.2.0/go.mod h1:WoaWxbHKBymSN41hWSq/lGKJEca7TNm58+gGJi2WsLI=
 github.com/libp2p/go-libp2p-core v0.2.0/go.mod h1:X0eyB0Gy93v0DZtSYbEM7RnMChm9Uv3j7yRXjO77xSI=
 github.com/libp2p/go-libp2p-core v0.5.7/go.mod h1:txwbVEhHEXikXn9gfC7/UDDw7rkxuX0bJvM49Ykaswo=
-github.com/libp2p/go-libp2p-core v0.12.0/go.mod h1:ECdxehoYosLYHgDDFa2N4yE8Y7aQRAMf0sX9mf2sbGg=
 github.com/libp2p/go-libp2p-core v0.19.0/go.mod h1:AkA+FUKQfYt1FLNef5fOPlo/naAWjKy/RCjkcPjqzYg=
 github.com/libp2p/go-libp2p-core v0.19.1 h1:zaZQQCeCrFMtxFa1wHy6AhsVynyNmZAvwgWqSSPT3WE=
 github.com/libp2p/go-libp2p-core v0.19.1/go.mod h1:2uLhmmqDiFY+dw+70KkBLeKvvsJHGWUINRDdeV1ip7k=
-github.com/libp2p/go-libp2p-peerstore v0.7.1 h1:7FpALlqR+3+oOBXdzm3AVt0vjMYLW1b7jM03E4iEHlw=
-github.com/libp2p/go-libp2p-peerstore v0.7.1/go.mod h1:cdUWTHro83vpg6unCpGUr8qJoX3e93Vy8o97u5ppIM0=
 github.com/libp2p/go-libp2p-resource-manager v0.5.1 h1:jm0mdqn7yfh7wbUzlj948BYZX0KZ3RW7OqerkGQ5rYY=
 github.com/libp2p/go-libp2p-resource-manager v0.5.1/go.mod h1:CggtV6EZb+Y0dGh41q5ezO4udcVKyhcEFpydHD8EMe0=
 github.com/libp2p/go-libp2p-testing v0.1.1/go.mod h1:xaZWMJrPUM5GlDBxCeGUi7kI4eqnjVyavGroI2nxEM0=
 github.com/libp2p/go-libp2p-testing v0.11.0 h1:+R7FRl/U3Y00neyBSM2qgDzqz3HkWH24U9nMlascHL4=
 github.com/libp2p/go-libp2p-testing v0.11.0/go.mod h1:qG4sF27dfKFoK9KlVzK2y52LQKhp0VEmLjV5aDqr1Hg=
-github.com/libp2p/go-maddr-filter v0.1.0/go.mod h1:VzZhTXkMucEGGEOSKddrwGiOv0tUhgnKqNEmIAz/bPU=
 github.com/libp2p/go-mplex v0.7.0 h1:BDhFZdlk5tbr0oyFq/xv/NPGfjbnrsDam1EvutpBDbY=
 github.com/libp2p/go-mplex v0.7.0/go.mod h1:rW8ThnRcYWft/Jb2jeORBmPd6xuG3dGxWN/W168L9EU=
 github.com/libp2p/go-msgio v0.0.4/go.mod h1:63lBBgOTDKQL6EWazRMCwXsEeEeK9O2Cd+0+6OOuipQ=
@@ -392,7 +396,6 @@ github.com/marten-seemann/tcp v0.0.0-20210406111302-dfbc87cc63fd h1:br0buuQ854V8
 github.com/marten-seemann/tcp v0.0.0-20210406111302-dfbc87cc63fd/go.mod h1:QuCEs1Nt24+FYQEqAAncTDPJIuGs+LxK1MCiFL25pMU=
 github.com/mattn/go-colorable v0.0.9/go.mod h1:9vuHe8Xs5qXnSaW/c/ABM9alt+Vo+STaOChaDxuIBZU=
 github.com/mattn/go-isatty v0.0.4/go.mod h1:M+lRXTBqGeGNdLjl/ufCoiOlB5xdOkqRJdNxMWT7Zi4=
-github.com/mattn/go-isatty v0.0.13/go.mod h1:cbi8OIDigv2wuxKPP5vlRcQ1OAZbq2CE4Kysco4FUpU=
 github.com/mattn/go-isatty v0.0.14 h1:yVuAays6BHfxijgZPzw+3Zlu5yQgKGP2/hcQbHb7S9Y=
 github.com/mattn/go-isatty v0.0.14/go.mod h1:7GGIvUiUoEMVVmxf/4nioHXj79iQHKdU27kJ6hsGG94=
 github.com/matttproud/golang_protobuf_extensions v1.0.1 h1:4hp9jkHxhMHkqkrB3Ix0jegS5sx/RkqARlsWZ6pIwiU=
@@ -438,7 +441,6 @@ github.com/multiformats/go-multiaddr v0.0.4/go.mod h1:xKVEak1K9cS1VdmPZW3LSIb6lg
 github.com/multiformats/go-multiaddr v0.1.1/go.mod h1:aMKBKNEYmzmDmxfX88/vz+J5IU55txyt0p4aiWVohjo=
 github.com/multiformats/go-multiaddr v0.2.0/go.mod h1:0nO36NvPpyV4QzvTLi/lafl2y95ncPj0vFwVF6k6wJ4=
 github.com/multiformats/go-multiaddr v0.2.2/go.mod h1:NtfXiOtHvghW9KojvtySjH5y0u0xW5UouOmQQrn6a3Y=
-github.com/multiformats/go-multiaddr v0.3.3/go.mod h1:lCKNGP1EQ1eZ35Za2wlqnabm9xQkib3fyB+nZXHLag0=
 github.com/multiformats/go-multiaddr v0.4.1/go.mod h1:3afI9HfVW8csiF8UZqtpYRiDyew8pRX7qLIGHu9FLuM=
 github.com/multiformats/go-multiaddr v0.6.0 h1:qMnoOPj2s8xxPU5kZ57Cqdr0hHhARz7mFsPMIiYNqzg=
 github.com/multiformats/go-multiaddr v0.6.0/go.mod h1:F4IpaKZuPP360tOMn2Tpyu0At8w23aRyVqeK0DbFeGM=
@@ -588,6 +590,7 @@ github.com/stretchr/testify v1.7.0/go.mod h1:6Fq8oRcR53rry900zMqJjRRixrwX3KX962/
 github.com/stretchr/testify v1.7.1/go.mod h1:6Fq8oRcR53rry900zMqJjRRixrwX3KX962/h/Wwjteg=
 github.com/stretchr/testify v1.8.0 h1:pSgiaMZlXftHpm5L7V1+rVB+AZJydKsMxsQBIJw4PKk=
 github.com/stretchr/testify v1.8.0/go.mod h1:yNjHg4UonilssWZ8iaSj1OCr/vHnekPRkoO+kdMU+MU=
+github.com/syndtr/goleveldb v1.0.0 h1:fBdIW9lB4Iz0n9khmH8w27SJ3QEJ7+IgjPEwGSZiFdE=
 github.com/syndtr/goleveldb v1.0.0/go.mod h1:ZVVdQEZoIme9iO1Ch2Jdy24qqXrMMOU6lpPAyBWyWuQ=
 github.com/tarm/serial v0.0.0-20180830185346-98f6abe2eb07/go.mod h1:kDXzergiv9cbyO7IOYJZWg1U88JhDg3PB6klq9Hg2pA=
 github.com/ugorji/go/codec v0.0.0-20181204163529-d75b2dcb6bc8/go.mod h1:VFNgLljTbGfSG7qAOspJ7OScBnGdDN/yBr0sguwnwf0=
@@ -613,7 +616,6 @@ go.uber.org/atomic v1.6.0/go.mod h1:sABNBOSYdrvTF6hTgEIbc7YasKWGhgEQZyfxyTvoXHQ=
 go.uber.org/atomic v1.7.0/go.mod h1:fEN4uk6kAWBTFdckzkM89CLk9XfWZrxpCo0nPH17wJc=
 go.uber.org/atomic v1.9.0 h1:ECmE8Bn/WFTYwEW/bpKD3M8VtR/zQVbavAoalC1PYyE=
 go.uber.org/atomic v1.9.0/go.mod h1:fEN4uk6kAWBTFdckzkM89CLk9XfWZrxpCo0nPH17wJc=
-go.uber.org/goleak v1.1.10/go.mod h1:8a7PlsEVH3e/a/GLqe5IIrQx6GzcnRmZEufDUTk4A7A=
 go.uber.org/goleak v1.1.11-0.20210813005559-691160354723/go.mod h1:cwTWslyiVhfpKIDGSZEM2HlOvcqm+tG4zioyIeLoqMQ=
 go.uber.org/goleak v1.1.11/go.mod h1:cwTWslyiVhfpKIDGSZEM2HlOvcqm+tG4zioyIeLoqMQ=
 go.uber.org/goleak v1.1.12 h1:gZAh5/EyT/HQwlpkCy6wTpqfH9H8Lz8zbm3dZh+OyzA=
@@ -624,7 +626,6 @@ go.uber.org/multierr v1.8.0 h1:dg6GjLku4EH+249NNmoIciG9N/jURbDG+pFlTkhzIC8=
 go.uber.org/multierr v1.8.0/go.mod h1:7EAYxJLBy9rStEaz58O2t4Uvip6FSURkq8/ppBp95ak=
 go.uber.org/tools v0.0.0-20190618225709-2cfd321de3ee/go.mod h1:vJERXedbb3MVM5f9Ejo0C68/HhF8uaILCdgjnY+goOA=
 go.uber.org/zap v1.14.1/go.mod h1:Mb2vm2krFEG5DV0W9qcHBYFtp/Wku1cvYaqPsS/WYfc=
-go.uber.org/zap v1.16.0/go.mod h1:MA8QOfq0BHJwdXa996Y4dYkAqRKB8/1K1QMMZVaNZjQ=
 go.uber.org/zap v1.19.1/go.mod h1:j3DNczoxDZroyBnOT1L/Q79cfUMGZxlv/9dzN7SM1rI=
 go.uber.org/zap v1.21.0 h1:WefMeulhovoZ2sYXz7st6K0sLj7bBhpiFaud4r4zST8=
 go.uber.org/zap v1.21.0/go.mod h1:wjWOCqI0f2ZZrJF/UufIOkiC8ii6tm1iqIsLo76RfJw=
@@ -677,6 +678,7 @@ golang.org/x/lint v0.0.0-20190909230951-414d861bb4ac/go.mod h1:6SW0HCj/g11FgYtHl
 golang.org/x/lint v0.0.0-20190930215403-16217165b5de/go.mod h1:6SW0HCj/g11FgYtHlgUYUwCkIfeOF89ocIRzGO/8vkc=
 golang.org/x/lint v0.0.0-20191125180803-fdd1cda4f05f/go.mod h1:5qLYkcX4OjUUV8bRuDixDT3tpyyb+LUpUlRWLxfhWrs=
 golang.org/x/lint v0.0.0-20200130185559-910be7a94367/go.mod h1:3xt1FjdF8hUf6vQPIChWIBhFzV8gjjsPE/fR3IyQdNY=
+golang.org/x/lint v0.0.0-20200302205851-738671d3881b h1:Wh+f8QHJXR411sJR8/vRBTZ7YapZaRvUcLFFJhusH0k=
 golang.org/x/lint v0.0.0-20200302205851-738671d3881b/go.mod h1:3xt1FjdF8hUf6vQPIChWIBhFzV8gjjsPE/fR3IyQdNY=
 golang.org/x/mobile v0.0.0-20190312151609-d3739f865fa6/go.mod h1:z+o9i4GpDbdi3rU15maQ/Ox0txvL9dWGYEHz965HBQE=
 golang.org/x/mobile v0.0.0-20190719004257-d2bd2a29d028/go.mod h1:E/iHnbuqvinMTCcRqshq8CkpyQDoeVncDDYHnLhea+o=
@@ -795,7 +797,6 @@ golang.org/x/sys v0.0.0-20191204072324-ce4227a45e2e/go.mod h1:h1NjWce9XRLGQEsW7w
 golang.org/x/sys v0.0.0-20191228213918-04cbcbbfeed8/go.mod h1:h1NjWce9XRLGQEsW7wpKNCjG9DtNlClVuFLEZdDNbEs=
 golang.org/x/sys v0.0.0-20200106162015-b016eb3dc98e/go.mod h1:h1NjWce9XRLGQEsW7wpKNCjG9DtNlClVuFLEZdDNbEs=
 golang.org/x/sys v0.0.0-20200113162924-86b910548bc1/go.mod h1:h1NjWce9XRLGQEsW7wpKNCjG9DtNlClVuFLEZdDNbEs=
-golang.org/x/sys v0.0.0-20200116001909-b77594299b42/go.mod h1:h1NjWce9XRLGQEsW7wpKNCjG9DtNlClVuFLEZdDNbEs=
 golang.org/x/sys v0.0.0-20200122134326-e047566fdf82/go.mod h1:h1NjWce9XRLGQEsW7wpKNCjG9DtNlClVuFLEZdDNbEs=
 golang.org/x/sys v0.0.0-20200124204421-9fbb57f87de9/go.mod h1:h1NjWce9XRLGQEsW7wpKNCjG9DtNlClVuFLEZdDNbEs=
 golang.org/x/sys v0.0.0-20200202164722-d101bd2416d5/go.mod h1:h1NjWce9XRLGQEsW7wpKNCjG9DtNlClVuFLEZdDNbEs=
@@ -870,7 +871,6 @@ golang.org/x/tools v0.0.0-20190911174233-4f2ddba30aff/go.mod h1:b+2E5dAYhXwXZwtn
 golang.org/x/tools v0.0.0-20191012152004-8de300cfc20a/go.mod h1:b+2E5dAYhXwXZwtnZ6UAqBI28+e2cm9otk0dWdXHAEo=
 golang.org/x/tools v0.0.0-20191029041327-9cc4af7d6b2c/go.mod h1:b+2E5dAYhXwXZwtnZ6UAqBI28+e2cm9otk0dWdXHAEo=
 golang.org/x/tools v0.0.0-20191029190741-b9c20aec41a5/go.mod h1:b+2E5dAYhXwXZwtnZ6UAqBI28+e2cm9otk0dWdXHAEo=
-golang.org/x/tools v0.0.0-20191108193012-7d206e10da11/go.mod h1:b+2E5dAYhXwXZwtnZ6UAqBI28+e2cm9otk0dWdXHAEo=
 golang.org/x/tools v0.0.0-20191113191852-77e3bb0ad9e7/go.mod h1:b+2E5dAYhXwXZwtnZ6UAqBI28+e2cm9otk0dWdXHAEo=
 golang.org/x/tools v0.0.0-20191115202509-3a792d9c32b2/go.mod h1:b+2E5dAYhXwXZwtnZ6UAqBI28+e2cm9otk0dWdXHAEo=
 golang.org/x/tools v0.0.0-20191119224855-298f0cb1881e/go.mod h1:b+2E5dAYhXwXZwtnZ6UAqBI28+e2cm9otk0dWdXHAEo=
diff --git a/p2p/host/peerstore/metrics.go b/p2p/host/peerstore/metrics.go
new file mode 100644
index 00000000..87a94104
--- /dev/null
+++ b/p2p/host/peerstore/metrics.go
@@ -0,0 +1,58 @@
+package peerstore
+
+import (
+	"sync"
+	"time"
+
+	"github.com/libp2p/go-libp2p-core/peer"
+)
+
+// LatencyEWMASmoothing governs the decay of the EWMA (the speed
+// at which it changes). This must be a normalized (0-1) value.
+// 1 is 100% change, 0 is no change.
+var LatencyEWMASmoothing = 0.1
+
+type metrics struct {
+	mutex  sync.RWMutex
+	latmap map[peer.ID]time.Duration
+}
+
+func NewMetrics() *metrics {
+	return &metrics{
+		latmap: make(map[peer.ID]time.Duration),
+	}
+}
+
+// RecordLatency records a new latency measurement
+func (m *metrics) RecordLatency(p peer.ID, next time.Duration) {
+	nextf := float64(next)
+	s := LatencyEWMASmoothing
+	if s > 1 || s < 0 {
+		s = 0.1 // ignore the knob. it's broken. look, it jiggles.
+	}
+
+	m.mutex.Lock()
+	ewma, found := m.latmap[p]
+	ewmaf := float64(ewma)
+	if !found {
+		m.latmap[p] = next // when no data, just take it as the mean.
+	} else {
+		nextf = ((1.0 - s) * ewmaf) + (s * nextf)
+		m.latmap[p] = time.Duration(nextf)
+	}
+	m.mutex.Unlock()
+}
+
+// LatencyEWMA returns an exponentially-weighted moving avg.
+// of all measurements of a peer's latency.
+func (m *metrics) LatencyEWMA(p peer.ID) time.Duration {
+	m.mutex.RLock()
+	defer m.mutex.RUnlock()
+	return m.latmap[p]
+}
+
+func (m *metrics) RemovePeer(p peer.ID) {
+	m.mutex.Lock()
+	delete(m.latmap, p)
+	m.mutex.Unlock()
+}
diff --git a/p2p/host/peerstore/pb/Makefile b/p2p/host/peerstore/pb/Makefile
new file mode 100644
index 00000000..51e71f89
--- /dev/null
+++ b/p2p/host/peerstore/pb/Makefile
@@ -0,0 +1,12 @@
+PB = $(wildcard *.proto)
+GO = $(PB:.proto=.pb.go)
+
+all: $(GO)
+
+%.pb.go: %.proto
+		protoc --proto_path=$(GOPATH)/src:. --gogofaster_out=. $<
+
+clean:
+		rm -f *.pb.go
+
+.PHONY: clean
\ No newline at end of file
diff --git a/p2p/host/peerstore/pb/custom.go b/p2p/host/peerstore/pb/custom.go
new file mode 100644
index 00000000..41784a4f
--- /dev/null
+++ b/p2p/host/peerstore/pb/custom.go
@@ -0,0 +1,110 @@
+package pstore_pb
+
+import (
+	"encoding/json"
+
+	proto "github.com/gogo/protobuf/proto"
+	peer "github.com/libp2p/go-libp2p-core/peer"
+	pt "github.com/libp2p/go-libp2p-core/test"
+	ma "github.com/multiformats/go-multiaddr"
+)
+
+// customGogoType aggregates the interfaces that custom Gogo types need to implement.
+// it is only used for type assertions.
+type customGogoType interface {
+	proto.Marshaler
+	proto.Unmarshaler
+	json.Marshaler
+	json.Unmarshaler
+	proto.Sizer
+}
+
+// ProtoAddr is a custom type used by gogo to serde raw peer IDs into the peer.ID type, and back.
+type ProtoPeerID struct {
+	peer.ID
+}
+
+var _ customGogoType = (*ProtoPeerID)(nil)
+
+func (id ProtoPeerID) Marshal() ([]byte, error) {
+	return []byte(id.ID), nil
+}
+
+func (id ProtoPeerID) MarshalTo(data []byte) (n int, err error) {
+	return copy(data, []byte(id.ID)), nil
+}
+
+func (id ProtoPeerID) MarshalJSON() ([]byte, error) {
+	m, _ := id.Marshal()
+	return json.Marshal(m)
+}
+
+func (id *ProtoPeerID) Unmarshal(data []byte) (err error) {
+	id.ID = peer.ID(string(data))
+	return nil
+}
+
+func (id *ProtoPeerID) UnmarshalJSON(data []byte) error {
+	var v []byte
+	err := json.Unmarshal(data, &v)
+	if err != nil {
+		return err
+	}
+	return id.Unmarshal(v)
+}
+
+func (id ProtoPeerID) Size() int {
+	return len([]byte(id.ID))
+}
+
+// ProtoAddr is a custom type used by gogo to serde raw multiaddresses into the ma.Multiaddr type, and back.
+type ProtoAddr struct {
+	ma.Multiaddr
+}
+
+var _ customGogoType = (*ProtoAddr)(nil)
+
+func (a ProtoAddr) Marshal() ([]byte, error) {
+	return a.Bytes(), nil
+}
+
+func (a ProtoAddr) MarshalTo(data []byte) (n int, err error) {
+	return copy(data, a.Bytes()), nil
+}
+
+func (a ProtoAddr) MarshalJSON() ([]byte, error) {
+	m, _ := a.Marshal()
+	return json.Marshal(m)
+}
+
+func (a *ProtoAddr) Unmarshal(data []byte) (err error) {
+	a.Multiaddr, err = ma.NewMultiaddrBytes(data)
+	return err
+}
+
+func (a *ProtoAddr) UnmarshalJSON(data []byte) error {
+	v := new([]byte)
+	err := json.Unmarshal(data, v)
+	if err != nil {
+		return err
+	}
+	return a.Unmarshal(*v)
+}
+
+func (a ProtoAddr) Size() int {
+	return len(a.Bytes())
+}
+
+// NewPopulatedProtoAddr generates a populated instance of the custom gogo type ProtoAddr.
+// It is required by gogo-generated tests.
+func NewPopulatedProtoAddr(r randyPstore) *ProtoAddr {
+	a, _ := ma.NewMultiaddr("/ip4/123.123.123.123/tcp/7001")
+	return &ProtoAddr{Multiaddr: a}
+}
+
+// NewPopulatedProtoPeerID generates a populated instance of the custom gogo type ProtoPeerID.
+// It is required by gogo-generated tests.
+func NewPopulatedProtoPeerID(r randyPstore) *ProtoPeerID {
+	id, _ := pt.RandPeerID()
+	return &ProtoPeerID{ID: id}
+}
diff --git a/p2p/host/peerstore/pb/pstore.pb.go b/p2p/host/peerstore/pb/pstore.pb.go
new file mode 100644
index 00000000..e9d7dfda
--- /dev/null
+++ b/p2p/host/peerstore/pb/pstore.pb.go
@@ -0,0 +1,1027 @@
+// Code generated by protoc-gen-gogo. DO NOT EDIT.
+// source: pstore.proto
+
+package pstore_pb
+
+import (
+	fmt "fmt"
+	_ "github.com/gogo/protobuf/gogoproto"
+	proto "github.com/gogo/protobuf/proto"
+	io "io"
+	math "math"
+	math_bits "math/bits"
+)
+
+// Reference imports to suppress errors if they are not otherwise used.
+var _ = proto.Marshal
+var _ = fmt.Errorf
+var _ = math.Inf
+
+// This is a compile-time assertion to ensure that this generated file
+// is compatible with the proto package it is being compiled against.
+// A compilation error at this line likely means your copy of the
+// proto package needs to be updated.
+const _ = proto.GoGoProtoPackageIsVersion3 // please upgrade the proto package
+
+// AddrBookRecord represents a record for a peer in the address book.
+type AddrBookRecord struct {
+	// The peer ID.
+	Id *ProtoPeerID `protobuf:"bytes,1,opt,name=id,proto3,customtype=ProtoPeerID" json:"id,omitempty"`
+	// The multiaddresses. This is a sorted list where element 0 expires the soonest.
+	Addrs []*AddrBookRecord_AddrEntry `protobuf:"bytes,2,rep,name=addrs,proto3" json:"addrs,omitempty"`
+	// The most recently received signed PeerRecord.
+	CertifiedRecord *AddrBookRecord_CertifiedRecord `protobuf:"bytes,3,opt,name=certified_record,json=certifiedRecord,proto3" json:"certified_record,omitempty"`
+}
+
+func (m *AddrBookRecord) Reset()         { *m = AddrBookRecord{} }
+func (m *AddrBookRecord) String() string { return proto.CompactTextString(m) }
+func (*AddrBookRecord) ProtoMessage()    {}
+func (*AddrBookRecord) Descriptor() ([]byte, []int) {
+	return fileDescriptor_f96873690e08a98f, []int{0}
+}
+func (m *AddrBookRecord) XXX_Unmarshal(b []byte) error {
+	return m.Unmarshal(b)
+}
+func (m *AddrBookRecord) XXX_Marshal(b []byte, deterministic bool) ([]byte, error) {
+	if deterministic {
+		return xxx_messageInfo_AddrBookRecord.Marshal(b, m, deterministic)
+	} else {
+		b = b[:cap(b)]
+		n, err := m.MarshalToSizedBuffer(b)
+		if err != nil {
+			return nil, err
+		}
+		return b[:n], nil
+	}
+}
+func (m *AddrBookRecord) XXX_Merge(src proto.Message) {
+	xxx_messageInfo_AddrBookRecord.Merge(m, src)
+}
+func (m *AddrBookRecord) XXX_Size() int {
+	return m.Size()
+}
+func (m *AddrBookRecord) XXX_DiscardUnknown() {
+	xxx_messageInfo_AddrBookRecord.DiscardUnknown(m)
+}
+
+var xxx_messageInfo_AddrBookRecord proto.InternalMessageInfo
+
+func (m *AddrBookRecord) GetAddrs() []*AddrBookRecord_AddrEntry {
+	if m != nil {
+		return m.Addrs
+	}
+	return nil
+}
+
+func (m *AddrBookRecord) GetCertifiedRecord() *AddrBookRecord_CertifiedRecord {
+	if m != nil {
+		return m.CertifiedRecord
+	}
+	return nil
+}
+
+// AddrEntry represents a single multiaddress.
+type AddrBookRecord_AddrEntry struct {
+	Addr *ProtoAddr `protobuf:"bytes,1,opt,name=addr,proto3,customtype=ProtoAddr" json:"addr,omitempty"`
+	// The point in time when this address expires.
+	Expiry int64 `protobuf:"varint,2,opt,name=expiry,proto3" json:"expiry,omitempty"`
+	// The original TTL of this address.
+	Ttl int64 `protobuf:"varint,3,opt,name=ttl,proto3" json:"ttl,omitempty"`
+}
+
+func (m *AddrBookRecord_AddrEntry) Reset()         { *m = AddrBookRecord_AddrEntry{} }
+func (m *AddrBookRecord_AddrEntry) String() string { return proto.CompactTextString(m) }
+func (*AddrBookRecord_AddrEntry) ProtoMessage()    {}
+func (*AddrBookRecord_AddrEntry) Descriptor() ([]byte, []int) {
+	return fileDescriptor_f96873690e08a98f, []int{0, 0}
+}
+func (m *AddrBookRecord_AddrEntry) XXX_Unmarshal(b []byte) error {
+	return m.Unmarshal(b)
+}
+func (m *AddrBookRecord_AddrEntry) XXX_Marshal(b []byte, deterministic bool) ([]byte, error) {
+	if deterministic {
+		return xxx_messageInfo_AddrBookRecord_AddrEntry.Marshal(b, m, deterministic)
+	} else {
+		b = b[:cap(b)]
+		n, err := m.MarshalToSizedBuffer(b)
+		if err != nil {
+			return nil, err
+		}
+		return b[:n], nil
+	}
+}
+func (m *AddrBookRecord_AddrEntry) XXX_Merge(src proto.Message) {
+	xxx_messageInfo_AddrBookRecord_AddrEntry.Merge(m, src)
+}
+func (m *AddrBookRecord_AddrEntry) XXX_Size() int {
+	return m.Size()
+}
+func (m *AddrBookRecord_AddrEntry) XXX_DiscardUnknown() {
+	xxx_messageInfo_AddrBookRecord_AddrEntry.DiscardUnknown(m)
+}
+
+var xxx_messageInfo_AddrBookRecord_AddrEntry proto.InternalMessageInfo
+
+func (m *AddrBookRecord_AddrEntry) GetExpiry() int64 {
+	if m != nil {
+		return m.Expiry
+	}
+	return 0
+}
+
+func (m *AddrBookRecord_AddrEntry) GetTtl() int64 {
+	if m != nil {
+		return m.Ttl
+	}
+	return 0
+}
+
+// CertifiedRecord contains a serialized signed PeerRecord used to
+// populate the signedAddrs list.
+type AddrBookRecord_CertifiedRecord struct {
+	// The Seq counter from the signed PeerRecord envelope
+	Seq uint64 `protobuf:"varint,1,opt,name=seq,proto3" json:"seq,omitempty"`
+	// The serialized bytes of the SignedEnvelope containing the PeerRecord.
+	Raw []byte `protobuf:"bytes,2,opt,name=raw,proto3" json:"raw,omitempty"`
+}
+
+func (m *AddrBookRecord_CertifiedRecord) Reset()         { *m = AddrBookRecord_CertifiedRecord{} }
+func (m *AddrBookRecord_CertifiedRecord) String() string { return proto.CompactTextString(m) }
+func (*AddrBookRecord_CertifiedRecord) ProtoMessage()    {}
+func (*AddrBookRecord_CertifiedRecord) Descriptor() ([]byte, []int) {
+	return fileDescriptor_f96873690e08a98f, []int{0, 1}
+}
+func (m *AddrBookRecord_CertifiedRecord) XXX_Unmarshal(b []byte) error {
+	return m.Unmarshal(b)
+}
+func (m *AddrBookRecord_CertifiedRecord) XXX_Marshal(b []byte, deterministic bool) ([]byte, error) {
+	if deterministic {
+		return xxx_messageInfo_AddrBookRecord_CertifiedRecord.Marshal(b, m, deterministic)
+	} else {
+		b = b[:cap(b)]
+		n, err := m.MarshalToSizedBuffer(b)
+		if err != nil {
+			return nil, err
+		}
+		return b[:n], nil
+	}
+}
+func (m *AddrBookRecord_CertifiedRecord) XXX_Merge(src proto.Message) {
+	xxx_messageInfo_AddrBookRecord_CertifiedRecord.Merge(m, src)
+}
+func (m *AddrBookRecord_CertifiedRecord) XXX_Size() int {
+	return m.Size()
+}
+func (m *AddrBookRecord_CertifiedRecord) XXX_DiscardUnknown() {
+	xxx_messageInfo_AddrBookRecord_CertifiedRecord.DiscardUnknown(m)
+}
+
+var xxx_messageInfo_AddrBookRecord_CertifiedRecord proto.InternalMessageInfo
+
+func (m *AddrBookRecord_CertifiedRecord) GetSeq() uint64 {
+	if m != nil {
+		return m.Seq
+	}
+	return 0
+}
+
+func (m *AddrBookRecord_CertifiedRecord) GetRaw() []byte {
+	if m != nil {
+		return m.Raw
+	}
+	return nil
+}
+
+func init() {
+	proto.RegisterType((*AddrBookRecord)(nil), "pstore.pb.AddrBookRecord")
+	proto.RegisterType((*AddrBookRecord_AddrEntry)(nil), "pstore.pb.AddrBookRecord.AddrEntry")
+	proto.RegisterType((*AddrBookRecord_CertifiedRecord)(nil), "pstore.pb.AddrBookRecord.CertifiedRecord")
+}
+
+func init() { proto.RegisterFile("pstore.proto", fileDescriptor_f96873690e08a98f) }
+
+var fileDescriptor_f96873690e08a98f = []byte{
+	// 322 bytes of a gzipped FileDescriptorProto
+	0x1f, 0x8b, 0x08, 0x00, 0x00, 0x00, 0x00, 0x00, 0x02, 0xff, 0xe2, 0xe2, 0x29, 0x28, 0x2e, 0xc9,
+	0x2f, 0x4a, 0xd5, 0x2b, 0x28, 0xca, 0x2f, 0xc9, 0x17, 0xe2, 0x84, 0xf1, 0x92, 0xa4, 0x74, 0xd3,
+	0x33, 0x4b, 0x32, 0x4a, 0x93, 0xf4, 0x92, 0xf3, 0x73, 0xf5, 0xd3, 0xf3, 0xd3, 0xf3, 0xf5, 0xc1,
+	0x2a, 0x92, 0x4a, 0xd3, 0xc0, 0x3c, 0x30, 0x07, 0xcc, 0x82, 0xe8, 0x54, 0xba, 0xcc, 0xc4, 0xc5,
+	0xe7, 0x98, 0x92, 0x52, 0xe4, 0x94, 0x9f, 0x9f, 0x1d, 0x94, 0x9a, 0x9c, 0x5f, 0x94, 0x22, 0x24,
+	0xcf, 0xc5, 0x94, 0x99, 0x22, 0xc1, 0xa8, 0xc0, 0xa8, 0xc1, 0xe3, 0xc4, 0x7f, 0xeb, 0x9e, 0x3c,
+	0x77, 0x00, 0x48, 0x65, 0x40, 0x6a, 0x6a, 0x91, 0xa7, 0x4b, 0x10, 0x53, 0x66, 0x8a, 0x90, 0x25,
+	0x17, 0x6b, 0x62, 0x4a, 0x4a, 0x51, 0xb1, 0x04, 0x93, 0x02, 0xb3, 0x06, 0xb7, 0x91, 0xb2, 0x1e,
+	0xdc, 0x76, 0x3d, 0x54, 0xa3, 0xc0, 0x5c, 0xd7, 0xbc, 0x92, 0xa2, 0xca, 0x20, 0x88, 0x0e, 0xa1,
+	0x10, 0x2e, 0x81, 0xe4, 0xd4, 0xa2, 0x92, 0xcc, 0xb4, 0xcc, 0xd4, 0x94, 0xf8, 0x22, 0xb0, 0x22,
+	0x09, 0x66, 0x05, 0x46, 0x0d, 0x6e, 0x23, 0x4d, 0xdc, 0xa6, 0x38, 0xc3, 0x74, 0x40, 0xf8, 0x41,
+	0xfc, 0xc9, 0xa8, 0x02, 0x52, 0x11, 0x5c, 0x9c, 0x70, 0x9b, 0x84, 0x14, 0xb9, 0x58, 0x40, 0x76,
+	0x41, 0x3d, 0xc0, 0x7b, 0xeb, 0x9e, 0x3c, 0x27, 0xd8, 0x03, 0x20, 0x15, 0x41, 0x60, 0x29, 0x21,
+	0x31, 0x2e, 0xb6, 0xd4, 0x8a, 0x82, 0xcc, 0xa2, 0x4a, 0x09, 0x26, 0x05, 0x46, 0x0d, 0xe6, 0x20,
+	0x28, 0x4f, 0x48, 0x80, 0x8b, 0xb9, 0xa4, 0x24, 0x07, 0xec, 0x20, 0xe6, 0x20, 0x10, 0x53, 0xca,
+	0x94, 0x8b, 0x1f, 0xcd, 0x76, 0x90, 0xa2, 0xe2, 0xd4, 0x42, 0xb0, 0xf1, 0x2c, 0x41, 0x20, 0x26,
+	0x48, 0xa4, 0x28, 0xb1, 0x1c, 0x6c, 0x16, 0x4f, 0x10, 0x88, 0xe9, 0xa4, 0xf0, 0xe3, 0xa1, 0x1c,
+	0xe3, 0x81, 0x47, 0x72, 0x8c, 0x27, 0x1e, 0xc9, 0x31, 0x5e, 0x78, 0x24, 0xc7, 0xf8, 0xe0, 0x91,
+	0x1c, 0xe3, 0x84, 0xc7, 0x72, 0x0c, 0x17, 0x1e, 0xcb, 0x31, 0xdc, 0x78, 0x2c, 0xc7, 0x90, 0xc4,
+	0x06, 0x0e, 0x7e, 0x63, 0x40, 0x00, 0x00, 0x00, 0xff, 0xff, 0x29, 0xcd, 0xe8, 0xd4, 0xc8, 0x01,
+	0x00, 0x00,
+}
+
+func (m *AddrBookRecord) Marshal() (dAtA []byte, err error) {
+	size := m.Size()
+	dAtA = make([]byte, size)
+	n, err := m.MarshalToSizedBuffer(dAtA[:size])
+	if err != nil {
+		return nil, err
+	}
+	return dAtA[:n], nil
+}
+
+func (m *AddrBookRecord) MarshalTo(dAtA []byte) (int, error) {
+	size := m.Size()
+	return m.MarshalToSizedBuffer(dAtA[:size])
+}
+
+func (m *AddrBookRecord) MarshalToSizedBuffer(dAtA []byte) (int, error) {
+	i := len(dAtA)
+	_ = i
+	var l int
+	_ = l
+	if m.CertifiedRecord != nil {
+		{
+			size, err := m.CertifiedRecord.MarshalToSizedBuffer(dAtA[:i])
+			if err != nil {
+				return 0, err
+			}
+			i -= size
+			i = encodeVarintPstore(dAtA, i, uint64(size))
+		}
+		i--
+		dAtA[i] = 0x1a
+	}
+	if len(m.Addrs) > 0 {
+		for iNdEx := len(m.Addrs) - 1; iNdEx >= 0; iNdEx-- {
+			{
+				size, err := m.Addrs[iNdEx].MarshalToSizedBuffer(dAtA[:i])
+				if err != nil {
+					return 0, err
+				}
+				i -= size
+				i = encodeVarintPstore(dAtA, i, uint64(size))
+			}
+			i--
+			dAtA[i] = 0x12
+		}
+	}
+	if m.Id != nil {
+		{
+			size := m.Id.Size()
+			i -= size
+			if _, err := m.Id.MarshalTo(dAtA[i:]); err != nil {
+				return 0, err
+			}
+			i = encodeVarintPstore(dAtA, i, uint64(size))
+		}
+		i--
+		dAtA[i] = 0xa
+	}
+	return len(dAtA) - i, nil
+}
+
+func (m *AddrBookRecord_AddrEntry) Marshal() (dAtA []byte, err error) {
+	size := m.Size()
+	dAtA = make([]byte, size)
+	n, err := m.MarshalToSizedBuffer(dAtA[:size])
+	if err != nil {
+		return nil, err
+	}
+	return dAtA[:n], nil
+}
+
+func (m *AddrBookRecord_AddrEntry) MarshalTo(dAtA []byte) (int, error) {
+	size := m.Size()
+	return m.MarshalToSizedBuffer(dAtA[:size])
+}
+
+func (m *AddrBookRecord_AddrEntry) MarshalToSizedBuffer(dAtA []byte) (int, error) {
+	i := len(dAtA)
+	_ = i
+	var l int
+	_ = l
+	if m.Ttl != 0 {
+		i = encodeVarintPstore(dAtA, i, uint64(m.Ttl))
+		i--
+		dAtA[i] = 0x18
+	}
+	if m.Expiry != 0 {
+		i = encodeVarintPstore(dAtA, i, uint64(m.Expiry))
+		i--
+		dAtA[i] = 0x10
+	}
+	if m.Addr != nil {
+		{
+			size := m.Addr.Size()
+			i -= size
+			if _, err := m.Addr.MarshalTo(dAtA[i:]); err != nil {
+				return 0, err
+			}
+			i = encodeVarintPstore(dAtA, i, uint64(size))
+		}
+		i--
+		dAtA[i] = 0xa
+	}
+	return len(dAtA) - i, nil
+}
+
+func (m *AddrBookRecord_CertifiedRecord) Marshal() (dAtA []byte, err error) {
+	size := m.Size()
+	dAtA = make([]byte, size)
+	n, err := m.MarshalToSizedBuffer(dAtA[:size])
+	if err != nil {
+		return nil, err
+	}
+	return dAtA[:n], nil
+}
+
+func (m *AddrBookRecord_CertifiedRecord) MarshalTo(dAtA []byte) (int, error) {
+	size := m.Size()
+	return m.MarshalToSizedBuffer(dAtA[:size])
+}
+
+func (m *AddrBookRecord_CertifiedRecord) MarshalToSizedBuffer(dAtA []byte) (int, error) {
+	i := len(dAtA)
+	_ = i
+	var l int
+	_ = l
+	if len(m.Raw) > 0 {
+		i -= len(m.Raw)
+		copy(dAtA[i:], m.Raw)
+		i = encodeVarintPstore(dAtA, i, uint64(len(m.Raw)))
+		i--
+		dAtA[i] = 0x12
+	}
+	if m.Seq != 0 {
+		i = encodeVarintPstore(dAtA, i, uint64(m.Seq))
+		i--
+		dAtA[i] = 0x8
+	}
+	return len(dAtA) - i, nil
+}
+
+func encodeVarintPstore(dAtA []byte, offset int, v uint64) int {
+	offset -= sovPstore(v)
+	base := offset
+	for v >= 1<<7 {
+		dAtA[offset] = uint8(v&0x7f | 0x80)
+		v >>= 7
+		offset++
+	}
+	dAtA[offset] = uint8(v)
+	return base
+}
+func NewPopulatedAddrBookRecord(r randyPstore, easy bool) *AddrBookRecord {
+	this := &AddrBookRecord{}
+	this.Id = NewPopulatedProtoPeerID(r)
+	if r.Intn(5) != 0 {
+		v1 := r.Intn(5)
+		this.Addrs = make([]*AddrBookRecord_AddrEntry, v1)
+		for i := 0; i < v1; i++ {
+			this.Addrs[i] = NewPopulatedAddrBookRecord_AddrEntry(r, easy)
+		}
+	}
+	if r.Intn(5) != 0 {
+		this.CertifiedRecord = NewPopulatedAddrBookRecord_CertifiedRecord(r, easy)
+	}
+	if !easy && r.Intn(10) != 0 {
+	}
+	return this
+}
+
+func NewPopulatedAddrBookRecord_AddrEntry(r randyPstore, easy bool) *AddrBookRecord_AddrEntry {
+	this := &AddrBookRecord_AddrEntry{}
+	this.Addr = NewPopulatedProtoAddr(r)
+	this.Expiry = int64(r.Int63())
+	if r.Intn(2) == 0 {
+		this.Expiry *= -1
+	}
+	this.Ttl = int64(r.Int63())
+	if r.Intn(2) == 0 {
+		this.Ttl *= -1
+	}
+	if !easy && r.Intn(10) != 0 {
+	}
+	return this
+}
+
+func NewPopulatedAddrBookRecord_CertifiedRecord(r randyPstore, easy bool) *AddrBookRecord_CertifiedRecord {
+	this := &AddrBookRecord_CertifiedRecord{}
+	this.Seq = uint64(uint64(r.Uint32()))
+	v2 := r.Intn(100)
+	this.Raw = make([]byte, v2)
+	for i := 0; i < v2; i++ {
+		this.Raw[i] = byte(r.Intn(256))
+	}
+	if !easy && r.Intn(10) != 0 {
+	}
+	return this
+}
+
+type randyPstore interface {
+	Float32() float32
+	Float64() float64
+	Int63() int64
+	Int31() int32
+	Uint32() uint32
+	Intn(n int) int
+}
+
+func randUTF8RunePstore(r randyPstore) rune {
+	ru := r.Intn(62)
+	if ru < 10 {
+		return rune(ru + 48)
+	} else if ru < 36 {
+		return rune(ru + 55)
+	}
+	return rune(ru + 61)
+}
+func randStringPstore(r randyPstore) string {
+	v3 := r.Intn(100)
+	tmps := make([]rune, v3)
+	for i := 0; i < v3; i++ {
+		tmps[i] = randUTF8RunePstore(r)
+	}
+	return string(tmps)
+}
+func randUnrecognizedPstore(r randyPstore, maxFieldNumber int) (dAtA []byte) {
+	l := r.Intn(5)
+	for i := 0; i < l; i++ {
+		wire := r.Intn(4)
+		if wire == 3 {
+			wire = 5
+		}
+		fieldNumber := maxFieldNumber + r.Intn(100)
+		dAtA = randFieldPstore(dAtA, r, fieldNumber, wire)
+	}
+	return dAtA
+}
+func randFieldPstore(dAtA []byte, r randyPstore, fieldNumber int, wire int) []byte {
+	key := uint32(fieldNumber)<<3 | uint32(wire)
+	switch wire {
+	case 0:
+		dAtA = encodeVarintPopulatePstore(dAtA, uint64(key))
+		v4 := r.Int63()
+		if r.Intn(2) == 0 {
+			v4 *= -1
+		}
+		dAtA = encodeVarintPopulatePstore(dAtA, uint64(v4))
+	case 1:
+		dAtA = encodeVarintPopulatePstore(dAtA, uint64(key))
+		dAtA = append(dAtA, byte(r.Intn(256)), byte(r.Intn(256)), byte(r.Intn(256)), byte(r.Intn(256)), byte(r.Intn(256)), byte(r.Intn(256)), byte(r.Intn(256)), byte(r.Intn(256)))
+	case 2:
+		dAtA = encodeVarintPopulatePstore(dAtA, uint64(key))
+		ll := r.Intn(100)
+		dAtA = encodeVarintPopulatePstore(dAtA, uint64(ll))
+		for j := 0; j < ll; j++ {
+			dAtA = append(dAtA, byte(r.Intn(256)))
+		}
+	default:
+		dAtA = encodeVarintPopulatePstore(dAtA, uint64(key))
+		dAtA = append(dAtA, byte(r.Intn(256)), byte(r.Intn(256)), byte(r.Intn(256)), byte(r.Intn(256)))
+	}
+	return dAtA
+}
+func encodeVarintPopulatePstore(dAtA []byte, v uint64) []byte {
+	for v >= 1<<7 {
+		dAtA = append(dAtA, uint8(uint64(v)&0x7f|0x80))
+		v >>= 7
+	}
+	dAtA = append(dAtA, uint8(v))
+	return dAtA
+}
+func (m *AddrBookRecord) Size() (n int) {
+	if m == nil {
+		return 0
+	}
+	var l int
+	_ = l
+	if m.Id != nil {
+		l = m.Id.Size()
+		n += 1 + l + sovPstore(uint64(l))
+	}
+	if len(m.Addrs) > 0 {
+		for _, e := range m.Addrs {
+			l = e.Size()
+			n += 1 + l + sovPstore(uint64(l))
+		}
+	}
+	if m.CertifiedRecord != nil {
+		l = m.CertifiedRecord.Size()
+		n += 1 + l + sovPstore(uint64(l))
+	}
+	return n
+}
+
+func (m *AddrBookRecord_AddrEntry) Size() (n int) {
+	if m == nil {
+		return 0
+	}
+	var l int
+	_ = l
+	if m.Addr != nil {
+		l = m.Addr.Size()
+		n += 1 + l + sovPstore(uint64(l))
+	}
+	if m.Expiry != 0 {
+		n += 1 + sovPstore(uint64(m.Expiry))
+	}
+	if m.Ttl != 0 {
+		n += 1 + sovPstore(uint64(m.Ttl))
+	}
+	return n
+}
+
+func (m *AddrBookRecord_CertifiedRecord) Size() (n int) {
+	if m == nil {
+		return 0
+	}
+	var l int
+	_ = l
+	if m.Seq != 0 {
+		n += 1 + sovPstore(uint64(m.Seq))
+	}
+	l = len(m.Raw)
+	if l > 0 {
+		n += 1 + l + sovPstore(uint64(l))
+	}
+	return n
+}
+
+func sovPstore(x uint64) (n int) {
+	return (math_bits.Len64(x|1) + 6) / 7
+}
+func sozPstore(x uint64) (n int) {
+	return sovPstore(uint64((x << 1) ^ uint64((int64(x) >> 63))))
+}
+func (m *AddrBookRecord) Unmarshal(dAtA []byte) error {
+	l := len(dAtA)
+	iNdEx := 0
+	for iNdEx < l {
+		preIndex := iNdEx
+		var wire uint64
+		for shift := uint(0); ; shift += 7 {
+			if shift >= 64 {
+				return ErrIntOverflowPstore
+			}
+			if iNdEx >= l {
+				return io.ErrUnexpectedEOF
+			}
+			b := dAtA[iNdEx]
+			iNdEx++
+			wire |= uint64(b&0x7F) << shift
+			if b < 0x80 {
+				break
+			}
+		}
+		fieldNum := int32(wire >> 3)
+		wireType := int(wire & 0x7)
+		if wireType == 4 {
+			return fmt.Errorf("proto: AddrBookRecord: wiretype end group for non-group")
+		}
+		if fieldNum <= 0 {
+			return fmt.Errorf("proto: AddrBookRecord: illegal tag %d (wire type %d)", fieldNum, wire)
+		}
+		switch fieldNum {
+		case 1:
+			if wireType != 2 {
+				return fmt.Errorf("proto: wrong wireType = %d for field Id", wireType)
+			}
+			var byteLen int
+			for shift := uint(0); ; shift += 7 {
+				if shift >= 64 {
+					return ErrIntOverflowPstore
+				}
+				if iNdEx >= l {
+					return io.ErrUnexpectedEOF
+				}
+				b := dAtA[iNdEx]
+				iNdEx++
+				byteLen |= int(b&0x7F) << shift
+				if b < 0x80 {
+					break
+				}
+			}
+			if byteLen < 0 {
+				return ErrInvalidLengthPstore
+			}
+			postIndex := iNdEx + byteLen
+			if postIndex < 0 {
+				return ErrInvalidLengthPstore
+			}
+			if postIndex > l {
+				return io.ErrUnexpectedEOF
+			}
+			var v ProtoPeerID
+			m.Id = &v
+			if err := m.Id.Unmarshal(dAtA[iNdEx:postIndex]); err != nil {
+				return err
+			}
+			iNdEx = postIndex
+		case 2:
+			if wireType != 2 {
+				return fmt.Errorf("proto: wrong wireType = %d for field Addrs", wireType)
+			}
+			var msglen int
+			for shift := uint(0); ; shift += 7 {
+				if shift >= 64 {
+					return ErrIntOverflowPstore
+				}
+				if iNdEx >= l {
+					return io.ErrUnexpectedEOF
+				}
+				b := dAtA[iNdEx]
+				iNdEx++
+				msglen |= int(b&0x7F) << shift
+				if b < 0x80 {
+					break
+				}
+			}
+			if msglen < 0 {
+				return ErrInvalidLengthPstore
+			}
+			postIndex := iNdEx + msglen
+			if postIndex < 0 {
+				return ErrInvalidLengthPstore
+			}
+			if postIndex > l {
+				return io.ErrUnexpectedEOF
+			}
+			m.Addrs = append(m.Addrs, &AddrBookRecord_AddrEntry{})
+			if err := m.Addrs[len(m.Addrs)-1].Unmarshal(dAtA[iNdEx:postIndex]); err != nil {
+				return err
+			}
+			iNdEx = postIndex
+		case 3:
+			if wireType != 2 {
+				return fmt.Errorf("proto: wrong wireType = %d for field CertifiedRecord", wireType)
+			}
+			var msglen int
+			for shift := uint(0); ; shift += 7 {
+				if shift >= 64 {
+					return ErrIntOverflowPstore
+				}
+				if iNdEx >= l {
+					return io.ErrUnexpectedEOF
+				}
+				b := dAtA[iNdEx]
+				iNdEx++
+				msglen |= int(b&0x7F) << shift
+				if b < 0x80 {
+					break
+				}
+			}
+			if msglen < 0 {
+				return ErrInvalidLengthPstore
+			}
+			postIndex := iNdEx + msglen
+			if postIndex < 0 {
+				return ErrInvalidLengthPstore
+			}
+			if postIndex > l {
+				return io.ErrUnexpectedEOF
+			}
+			if m.CertifiedRecord == nil {
+				m.CertifiedRecord = &AddrBookRecord_CertifiedRecord{}
+			}
+			if err := m.CertifiedRecord.Unmarshal(dAtA[iNdEx:postIndex]); err != nil {
+				return err
+			}
+			iNdEx = postIndex
+		default:
+			iNdEx = preIndex
+			skippy, err := skipPstore(dAtA[iNdEx:])
+			if err != nil {
+				return err
+			}
+			if (skippy < 0) || (iNdEx+skippy) < 0 {
+				return ErrInvalidLengthPstore
+			}
+			if (iNdEx + skippy) > l {
+				return io.ErrUnexpectedEOF
+			}
+			iNdEx += skippy
+		}
+	}
+
+	if iNdEx > l {
+		return io.ErrUnexpectedEOF
+	}
+	return nil
+}
+func (m *AddrBookRecord_AddrEntry) Unmarshal(dAtA []byte) error {
+	l := len(dAtA)
+	iNdEx := 0
+	for iNdEx < l {
+		preIndex := iNdEx
+		var wire uint64
+		for shift := uint(0); ; shift += 7 {
+			if shift >= 64 {
+				return ErrIntOverflowPstore
+			}
+			if iNdEx >= l {
+				return io.ErrUnexpectedEOF
+			}
+			b := dAtA[iNdEx]
+			iNdEx++
+			wire |= uint64(b&0x7F) << shift
+			if b < 0x80 {
+				break
+			}
+		}
+		fieldNum := int32(wire >> 3)
+		wireType := int(wire & 0x7)
+		if wireType == 4 {
+			return fmt.Errorf("proto: AddrEntry: wiretype end group for non-group")
+		}
+		if fieldNum <= 0 {
+			return fmt.Errorf("proto: AddrEntry: illegal tag %d (wire type %d)", fieldNum, wire)
+		}
+		switch fieldNum {
+		case 1:
+			if wireType != 2 {
+				return fmt.Errorf("proto: wrong wireType = %d for field Addr", wireType)
+			}
+			var byteLen int
+			for shift := uint(0); ; shift += 7 {
+				if shift >= 64 {
+					return ErrIntOverflowPstore
+				}
+				if iNdEx >= l {
+					return io.ErrUnexpectedEOF
+				}
+				b := dAtA[iNdEx]
+				iNdEx++
+				byteLen |= int(b&0x7F) << shift
+				if b < 0x80 {
+					break
+				}
+			}
+			if byteLen < 0 {
+				return ErrInvalidLengthPstore
+			}
+			postIndex := iNdEx + byteLen
+			if postIndex < 0 {
+				return ErrInvalidLengthPstore
+			}
+			if postIndex > l {
+				return io.ErrUnexpectedEOF
+			}
+			var v ProtoAddr
+			m.Addr = &v
+			if err := m.Addr.Unmarshal(dAtA[iNdEx:postIndex]); err != nil {
+				return err
+			}
+			iNdEx = postIndex
+		case 2:
+			if wireType != 0 {
+				return fmt.Errorf("proto: wrong wireType = %d for field Expiry", wireType)
+			}
+			m.Expiry = 0
+			for shift := uint(0); ; shift += 7 {
+				if shift >= 64 {
+					return ErrIntOverflowPstore
+				}
+				if iNdEx >= l {
+					return io.ErrUnexpectedEOF
+				}
+				b := dAtA[iNdEx]
+				iNdEx++
+				m.Expiry |= int64(b&0x7F) << shift
+				if b < 0x80 {
+					break
+				}
+			}
+		case 3:
+			if wireType != 0 {
+				return fmt.Errorf("proto: wrong wireType = %d for field Ttl", wireType)
+			}
+			m.Ttl = 0
+			for shift := uint(0); ; shift += 7 {
+				if shift >= 64 {
+					return ErrIntOverflowPstore
+				}
+				if iNdEx >= l {
+					return io.ErrUnexpectedEOF
+				}
+				b := dAtA[iNdEx]
+				iNdEx++
+				m.Ttl |= int64(b&0x7F) << shift
+				if b < 0x80 {
+					break
+				}
+			}
+		default:
+			iNdEx = preIndex
+			skippy, err := skipPstore(dAtA[iNdEx:])
+			if err != nil {
+				return err
+			}
+			if (skippy < 0) || (iNdEx+skippy) < 0 {
+				return ErrInvalidLengthPstore
+			}
+			if (iNdEx + skippy) > l {
+				return io.ErrUnexpectedEOF
+			}
+			iNdEx += skippy
+		}
+	}
+
+	if iNdEx > l {
+		return io.ErrUnexpectedEOF
+	}
+	return nil
+}
+func (m *AddrBookRecord_CertifiedRecord) Unmarshal(dAtA []byte) error {
+	l := len(dAtA)
+	iNdEx := 0
+	for iNdEx < l {
+		preIndex := iNdEx
+		var wire uint64
+		for shift := uint(0); ; shift += 7 {
+			if shift >= 64 {
+				return ErrIntOverflowPstore
+			}
+			if iNdEx >= l {
+				return io.ErrUnexpectedEOF
+			}
+			b := dAtA[iNdEx]
+			iNdEx++
+			wire |= uint64(b&0x7F) << shift
+			if b < 0x80 {
+				break
+			}
+		}
+		fieldNum := int32(wire >> 3)
+		wireType := int(wire & 0x7)
+		if wireType == 4 {
+			return fmt.Errorf("proto: CertifiedRecord: wiretype end group for non-group")
+		}
+		if fieldNum <= 0 {
+			return fmt.Errorf("proto: CertifiedRecord: illegal tag %d (wire type %d)", fieldNum, wire)
+		}
+		switch fieldNum {
+		case 1:
+			if wireType != 0 {
+				return fmt.Errorf("proto: wrong wireType = %d for field Seq", wireType)
+			}
+			m.Seq = 0
+			for shift := uint(0); ; shift += 7 {
+				if shift >= 64 {
+					return ErrIntOverflowPstore
+				}
+				if iNdEx >= l {
+					return io.ErrUnexpectedEOF
+				}
+				b := dAtA[iNdEx]
+				iNdEx++
+				m.Seq |= uint64(b&0x7F) << shift
+				if b < 0x80 {
+					break
+				}
+			}
+		case 2:
+			if wireType != 2 {
+				return fmt.Errorf("proto: wrong wireType = %d for field Raw", wireType)
+			}
+			var byteLen int
+			for shift := uint(0); ; shift += 7 {
+				if shift >= 64 {
+					return ErrIntOverflowPstore
+				}
+				if iNdEx >= l {
+					return io.ErrUnexpectedEOF
+				}
+				b := dAtA[iNdEx]
+				iNdEx++
+				byteLen |= int(b&0x7F) << shift
+				if b < 0x80 {
+					break
+				}
+			}
+			if byteLen < 0 {
+				return ErrInvalidLengthPstore
+			}
+			postIndex := iNdEx + byteLen
+			if postIndex < 0 {
+				return ErrInvalidLengthPstore
+			}
+			if postIndex > l {
+				return io.ErrUnexpectedEOF
+			}
+			m.Raw = append(m.Raw[:0], dAtA[iNdEx:postIndex]...)
+			if m.Raw == nil {
+				m.Raw = []byte{}
+			}
+			iNdEx = postIndex
+		default:
+			iNdEx = preIndex
+			skippy, err := skipPstore(dAtA[iNdEx:])
+			if err != nil {
+				return err
+			}
+			if (skippy < 0) || (iNdEx+skippy) < 0 {
+				return ErrInvalidLengthPstore
+			}
+			if (iNdEx + skippy) > l {
+				return io.ErrUnexpectedEOF
+			}
+			iNdEx += skippy
+		}
+	}
+
+	if iNdEx > l {
+		return io.ErrUnexpectedEOF
+	}
+	return nil
+}
+func skipPstore(dAtA []byte) (n int, err error) {
+	l := len(dAtA)
+	iNdEx := 0
+	depth := 0
+	for iNdEx < l {
+		var wire uint64
+		for shift := uint(0); ; shift += 7 {
+			if shift >= 64 {
+				return 0, ErrIntOverflowPstore
+			}
+			if iNdEx >= l {
+				return 0, io.ErrUnexpectedEOF
+			}
+			b := dAtA[iNdEx]
+			iNdEx++
+			wire |= (uint64(b) & 0x7F) << shift
+			if b < 0x80 {
+				break
+			}
+		}
+		wireType := int(wire & 0x7)
+		switch wireType {
+		case 0:
+			for shift := uint(0); ; shift += 7 {
+				if shift >= 64 {
+					return 0, ErrIntOverflowPstore
+				}
+				if iNdEx >= l {
+					return 0, io.ErrUnexpectedEOF
+				}
+				iNdEx++
+				if dAtA[iNdEx-1] < 0x80 {
+					break
+				}
+			}
+		case 1:
+			iNdEx += 8
+		case 2:
+			var length int
+			for shift := uint(0); ; shift += 7 {
+				if shift >= 64 {
+					return 0, ErrIntOverflowPstore
+				}
+				if iNdEx >= l {
+					return 0, io.ErrUnexpectedEOF
+				}
+				b := dAtA[iNdEx]
+				iNdEx++
+				length |= (int(b) & 0x7F) << shift
+				if b < 0x80 {
+					break
+				}
+			}
+			if length < 0 {
+				return 0, ErrInvalidLengthPstore
+			}
+			iNdEx += length
+		case 3:
+			depth++
+		case 4:
+			if depth == 0 {
+				return 0, ErrUnexpectedEndOfGroupPstore
+			}
+			depth--
+		case 5:
+			iNdEx += 4
+		default:
+			return 0, fmt.Errorf("proto: illegal wireType %d", wireType)
+		}
+		if iNdEx < 0 {
+			return 0, ErrInvalidLengthPstore
+		}
+		if depth == 0 {
+			return iNdEx, nil
+		}
+	}
+	return 0, io.ErrUnexpectedEOF
+}
+
+var (
+	ErrInvalidLengthPstore        = fmt.Errorf("proto: negative length found during unmarshaling")
+	ErrIntOverflowPstore          = fmt.Errorf("proto: integer overflow")
+	ErrUnexpectedEndOfGroupPstore = fmt.Errorf("proto: unexpected end of group")
+)
diff --git a/p2p/host/peerstore/pb/pstore.proto b/p2p/host/peerstore/pb/pstore.proto
new file mode 100644
index 00000000..0d1abd1d
--- /dev/null
+++ b/p2p/host/peerstore/pb/pstore.proto
@@ -0,0 +1,40 @@
+syntax = "proto3";
+package pstore.pb;
+
+import "github.com/gogo/protobuf/gogoproto/gogo.proto";
+
+option (gogoproto.benchgen_all) = true;
+option (gogoproto.populate_all) = true;
+
+// AddrBookRecord represents a record for a peer in the address book.
+message AddrBookRecord {
+	// The peer ID.
+	bytes id = 1 [(gogoproto.customtype) = "ProtoPeerID"];
+
+	// The multiaddresses. This is a sorted list where element 0 expires the soonest.
+	repeated AddrEntry addrs = 2;
+
+	// The most recently received signed PeerRecord.
+	CertifiedRecord certified_record = 3;
+
+	// AddrEntry represents a single multiaddress.
+	message AddrEntry {
+		bytes addr = 1 [(gogoproto.customtype) = "ProtoAddr"];
+
+		// The point in time when this address expires.
+		int64 expiry = 2;
+
+		// The original TTL of this address.
+		int64 ttl = 3;
+	}
+
+	// CertifiedRecord contains a serialized signed PeerRecord used to
+	// populate the signedAddrs list.
+	message CertifiedRecord {
+		// The Seq counter from the signed PeerRecord envelope
+		uint64 seq = 1;
+
+		// The serialized bytes of the SignedEnvelope containing the PeerRecord.
+		bytes raw = 2;
+	}
+}
diff --git a/p2p/host/peerstore/peerstore.go b/p2p/host/peerstore/peerstore.go
new file mode 100644
index 00000000..9f5eda8f
--- /dev/null
+++ b/p2p/host/peerstore/peerstore.go
@@ -0,0 +1,22 @@
+package peerstore
+
+import (
+	"github.com/libp2p/go-libp2p-core/peer"
+	pstore "github.com/libp2p/go-libp2p-core/peerstore"
+)
+
+func PeerInfos(ps pstore.Peerstore, peers peer.IDSlice) []peer.AddrInfo {
+	pi := make([]peer.AddrInfo, len(peers))
+	for i, p := range peers {
+		pi[i] = ps.PeerInfo(p)
+	}
+	return pi
+}
+
+func PeerInfoIDs(pis []peer.AddrInfo) peer.IDSlice {
+	ps := make(peer.IDSlice, len(pis))
+	for i, pi := range pis {
+		ps[i] = pi.ID
+	}
+	return ps
+}
diff --git a/p2p/host/peerstore/pstoreds/addr_book.go b/p2p/host/peerstore/pstoreds/addr_book.go
new file mode 100644
index 00000000..ac540154
--- /dev/null
+++ b/p2p/host/peerstore/pstoreds/addr_book.go
@@ -0,0 +1,605 @@
+package pstoreds
+
+import (
+	"context"
+	"fmt"
+	"sort"
+	"sync"
+	"time"
+
+	pb "github.com/libp2p/go-libp2p/p2p/host/peerstore/pb"
+	"github.com/libp2p/go-libp2p/p2p/host/peerstore/pstoremem"
+
+	"github.com/libp2p/go-libp2p-core/peer"
+	pstore "github.com/libp2p/go-libp2p-core/peerstore"
+	"github.com/libp2p/go-libp2p-core/record"
+
+	lru "github.com/hashicorp/golang-lru"
+	ds "github.com/ipfs/go-datastore"
+	"github.com/ipfs/go-datastore/query"
+	logging "github.com/ipfs/go-log/v2"
+	b32 "github.com/multiformats/go-base32"
+	ma "github.com/multiformats/go-multiaddr"
+)
+
+type ttlWriteMode int
+
+const (
+	ttlOverride ttlWriteMode = iota
+	ttlExtend
+)
+
+var (
+	log = logging.Logger("peerstore/ds")
+
+	// Peer addresses are stored db key pattern:
+	// /peers/addrs/<b32 peer id no padding>
+	addrBookBase = ds.NewKey("/peers/addrs")
+)
+
+// addrsRecord decorates the AddrBookRecord with locks and metadata.
+type addrsRecord struct {
+	sync.RWMutex
+	*pb.AddrBookRecord
+	dirty bool
+}
+
+// flush writes the record to the datastore by calling ds.Put, unless the record is
+// marked for deletion, in which case we call ds.Delete. To be called within a lock.
+func (r *addrsRecord) flush(write ds.Write) (err error) {
+	key := addrBookBase.ChildString(b32.RawStdEncoding.EncodeToString([]byte(r.Id.ID)))
+
+	if len(r.Addrs) == 0 {
+		if err = write.Delete(context.TODO(), key); err == nil {
+			r.dirty = false
+		}
+		return err
+	}
+
+	data, err := r.Marshal()
+	if err != nil {
+		return err
+	}
+	if err = write.Put(context.TODO(), key, data); err != nil {
+		return err
+	}
+	// write succeeded; record is no longer dirty.
+	r.dirty = false
+	return nil
+}
+
+// clean is called on records to perform housekeeping. The return value indicates if the record was changed
+// as a result of this call.
+//
+// clean does the following:
+// * sorts addresses by expiration (soonest expiring first).
+// * removes expired addresses.
+//
+// It short-circuits optimistically when there's nothing to do.
+//
+// clean is called from several points:
+// * when accessing an entry.
+// * when performing periodic GC.
+// * after an entry has been modified (e.g. addresses have been added or removed, TTLs updated, etc.)
+//
+// If the return value is true, the caller should perform a flush immediately to sync the record with the store.
+func (r *addrsRecord) clean(now time.Time) (chgd bool) {
+	nowUnix := now.Unix()
+	addrsLen := len(r.Addrs)
+
+	if !r.dirty && !r.hasExpiredAddrs(nowUnix) {
+		// record is not dirty, and we have no expired entries to purge.
+		return false
+	}
+
+	if addrsLen == 0 {
+		// this is a ghost record; let's signal it has to be written.
+		// flush() will take care of doing the deletion.
+		return true
+	}
+
+	if r.dirty && addrsLen > 1 {
+		sort.Slice(r.Addrs, func(i, j int) bool {
+			return r.Addrs[i].Expiry < r.Addrs[j].Expiry
+		})
+	}
+
+	r.Addrs = removeExpired(r.Addrs, nowUnix)
+
+	return r.dirty || len(r.Addrs) != addrsLen
+}
+
+func (r *addrsRecord) hasExpiredAddrs(now int64) bool {
+	if len(r.Addrs) > 0 && r.Addrs[0].Expiry <= now {
+		return true
+	}
+	return false
+}
+
+func removeExpired(entries []*pb.AddrBookRecord_AddrEntry, now int64) []*pb.AddrBookRecord_AddrEntry {
+	// since addresses are sorted by expiration, we find the first
+	// survivor and split the slice on its index.
+	pivot := -1
+	for i, addr := range entries {
+		if addr.Expiry > now {
+			break
+		}
+		pivot = i
+	}
+
+	return entries[pivot+1:]
+}
+
+// dsAddrBook is an address book backed by a Datastore with a GC procedure to purge expired entries. It uses an
+// in-memory address stream manager. See the NewAddrBook for more information.
+type dsAddrBook struct {
+	ctx  context.Context
+	opts Options
+
+	cache       cache
+	ds          ds.Batching
+	gc          *dsAddrBookGc
+	subsManager *pstoremem.AddrSubManager
+
+	// controls children goroutine lifetime.
+	childrenDone sync.WaitGroup
+	cancelFn     func()
+
+	clock clock
+}
+
+type clock interface {
+	Now() time.Time
+	After(d time.Duration) <-chan time.Time
+}
+
+type realclock struct{}
+
+func (rc realclock) Now() time.Time {
+	return time.Now()
+}
+
+func (rc realclock) After(d time.Duration) <-chan time.Time {
+	return time.After(d)
+}
+
+var _ pstore.AddrBook = (*dsAddrBook)(nil)
+var _ pstore.CertifiedAddrBook = (*dsAddrBook)(nil)
+
+// NewAddrBook initializes a new datastore-backed address book. It serves as a drop-in replacement for pstoremem
+// (memory-backed peerstore), and works with any datastore implementing the ds.Batching interface.
+//
+// Addresses and peer records are serialized into protobuf, storing one datastore entry per peer, along with metadata
+// to control address expiration. To alleviate disk access and serde overhead, we internally use a read/write-through
+// ARC cache, the size of which is adjustable via Options.CacheSize.
+//
+// The user has a choice of two GC algorithms:
+//
+//   - lookahead GC: minimises the amount of full store traversals by maintaining a time-indexed list of entries that
+//     need to be visited within the period specified in Options.GCLookaheadInterval. This is useful in scenarios with
+//     considerable TTL variance, coupled with datastores whose native iterators return entries in lexicographical key
+//     order. Enable this mode by passing a value Options.GCLookaheadInterval > 0. Lookahead windows are jumpy, not
+//     sliding. Purges operate exclusively over the lookahead window with periodicity Options.GCPurgeInterval.
+//
+//   - full-purge GC (default): performs a full visit of the store with periodicity Options.GCPurgeInterval. Useful when
+//     the range of possible TTL values is small and the values themselves are also extreme, e.g. 10 minutes or
+//     permanent, popular values used in other libp2p modules. In this cited case, optimizing with lookahead windows
+//     makes little sense.
+func NewAddrBook(ctx context.Context, store ds.Batching, opts Options) (ab *dsAddrBook, err error) {
+	ctx, cancelFn := context.WithCancel(ctx)
+	ab = &dsAddrBook{
+		ctx:         ctx,
+		ds:          store,
+		opts:        opts,
+		cancelFn:    cancelFn,
+		subsManager: pstoremem.NewAddrSubManager(),
+		clock:       realclock{},
+	}
+
+	if opts.Clock != nil {
+		ab.clock = opts.Clock
+	}
+
+	if opts.CacheSize > 0 {
+		if ab.cache, err = lru.NewARC(int(opts.CacheSize)); err != nil {
+			return nil, err
+		}
+	} else {
+		ab.cache = new(noopCache)
+	}
+
+	if ab.gc, err = newAddressBookGc(ctx, ab); err != nil {
+		return nil, err
+	}
+
+	return ab, nil
+}
+
+func (ab *dsAddrBook) Close() error {
+	ab.cancelFn()
+	ab.childrenDone.Wait()
+	return nil
+}
+
+// loadRecord is a read-through fetch. It fetches a record from cache, falling back to the
+// datastore upon a miss, and returning a newly initialized record if the peer doesn't exist.
+//
+// loadRecord calls clean() on an existing record before returning it. If the record changes
+// as a result and the update argument is true, the resulting state is saved in the datastore.
+//
+// If the cache argument is true, the record is inserted in the cache when loaded from the datastore.
+func (ab *dsAddrBook) loadRecord(id peer.ID, cache bool, update bool) (pr *addrsRecord, err error) {
+	if e, ok := ab.cache.Get(id); ok {
+		pr = e.(*addrsRecord)
+		pr.Lock()
+		defer pr.Unlock()
+
+		if pr.clean(ab.clock.Now()) && update {
+			err = pr.flush(ab.ds)
+		}
+		return pr, err
+	}
+
+	pr = &addrsRecord{AddrBookRecord: &pb.AddrBookRecord{}}
+	key := addrBookBase.ChildString(b32.RawStdEncoding.EncodeToString([]byte(id)))
+	data, err := ab.ds.Get(context.TODO(), key)
+
+	switch err {
+	case ds.ErrNotFound:
+		err = nil
+		pr.Id = &pb.ProtoPeerID{ID: id}
+	case nil:
+		if err = pr.Unmarshal(data); err != nil {
+			return nil, err
+		}
+		// this record is new and local for now (not in cache), so we don't need to lock.
+		if pr.clean(ab.clock.Now()) && update {
+			err = pr.flush(ab.ds)
+		}
+	default:
+		return nil, err
+	}
+
+	if cache {
+		ab.cache.Add(id, pr)
+	}
+	return pr, err
+}
+
+// AddAddr will add a new address if it's not already in the AddrBook.
+func (ab *dsAddrBook) AddAddr(p peer.ID, addr ma.Multiaddr, ttl time.Duration) {
+	ab.AddAddrs(p, []ma.Multiaddr{addr}, ttl)
+}
+
+// AddAddrs will add many new addresses if they're not already in the AddrBook.
+func (ab *dsAddrBook) AddAddrs(p peer.ID, addrs []ma.Multiaddr, ttl time.Duration) {
+	if ttl <= 0 {
+		return
+	}
+	addrs = cleanAddrs(addrs)
+	ab.setAddrs(p, addrs, ttl, ttlExtend, false)
+}
+
+// ConsumePeerRecord adds addresses from a signed peer.PeerRecord (contained in
+// a record.Envelope), which will expire after the given TTL.
+// See https://godoc.org/github.com/libp2p/go-libp2p-core/peerstore#CertifiedAddrBook for more details.
+func (ab *dsAddrBook) ConsumePeerRecord(recordEnvelope *record.Envelope, ttl time.Duration) (bool, error) {
+	r, err := recordEnvelope.Record()
+	if err != nil {
+		return false, err
+	}
+	rec, ok := r.(*peer.PeerRecord)
+	if !ok {
+		return false, fmt.Errorf("envelope did not contain PeerRecord")
+	}
+	if !rec.PeerID.MatchesPublicKey(recordEnvelope.PublicKey) {
+		return false, fmt.Errorf("signing key does not match PeerID in PeerRecord")
+	}
+
+	// ensure that the seq number from envelope is >= any previously received seq no
+	// update when equal to extend the ttls
+	if ab.latestPeerRecordSeq(rec.PeerID) > rec.Seq {
+		return false, nil
+	}
+
+	addrs := cleanAddrs(rec.Addrs)
+	err = ab.setAddrs(rec.PeerID, addrs, ttl, ttlExtend, true)
+	if err != nil {
+		return false, err
+	}
+
+	err = ab.storeSignedPeerRecord(rec.PeerID, recordEnvelope, rec)
+	if err != nil {
+		return false, err
+	}
+	return true, nil
+}
+
+func (ab *dsAddrBook) latestPeerRecordSeq(p peer.ID) uint64 {
+	pr, err := ab.loadRecord(p, true, false)
+	if err != nil {
+		// We ignore the error because we don't want to fail storing a new record in this
+		// case.
+		log.Errorw("unable to load record", "peer", p, "error", err)
+		return 0
+	}
+	pr.RLock()
+	defer pr.RUnlock()
+
+	if len(pr.Addrs) == 0 || pr.CertifiedRecord == nil || len(pr.CertifiedRecord.Raw) == 0 {
+		return 0
+	}
+	return pr.CertifiedRecord.Seq
+}
+
+func (ab *dsAddrBook) storeSignedPeerRecord(p peer.ID, envelope *record.Envelope, rec *peer.PeerRecord) error {
+	envelopeBytes, err := envelope.Marshal()
+	if err != nil {
+		return err
+	}
+	// reload record and add routing state
+	// this has to be done after we add the addresses, since if
+	// we try to flush a datastore record with no addresses,
+	// it will just get deleted
+	pr, err := ab.loadRecord(p, true, false)
+	if err != nil {
+		return err
+	}
+	pr.Lock()
+	defer pr.Unlock()
+	pr.CertifiedRecord = &pb.AddrBookRecord_CertifiedRecord{
+		Seq: rec.Seq,
+		Raw: envelopeBytes,
+	}
+	pr.dirty = true
+	err = pr.flush(ab.ds)
+	return err
+}
+
+// GetPeerRecord returns a record.Envelope containing a peer.PeerRecord for the
+// given peer id, if one exists.
+// Returns nil if no signed PeerRecord exists for the peer.
+func (ab *dsAddrBook) GetPeerRecord(p peer.ID) *record.Envelope {
+	pr, err := ab.loadRecord(p, true, false)
+	if err != nil {
+		log.Errorf("unable to load record for peer %s: %v", p.Pretty(), err)
+		return nil
+	}
+	pr.RLock()
+	defer pr.RUnlock()
+	if pr.CertifiedRecord == nil || len(pr.CertifiedRecord.Raw) == 0 || len(pr.Addrs) == 0 {
+		return nil
+	}
+	state, _, err := record.ConsumeEnvelope(pr.CertifiedRecord.Raw, peer.PeerRecordEnvelopeDomain)
+	if err != nil {
+		log.Errorf("error unmarshaling stored signed peer record for peer %s: %v", p.Pretty(), err)
+		return nil
+	}
+	return state
+}
+
+// SetAddr will add or update the TTL of an address in the AddrBook.
+func (ab *dsAddrBook) SetAddr(p peer.ID, addr ma.Multiaddr, ttl time.Duration) {
+	ab.SetAddrs(p, []ma.Multiaddr{addr}, ttl)
+}
+
+// SetAddrs will add or update the TTLs of addresses in the AddrBook.
+func (ab *dsAddrBook) SetAddrs(p peer.ID, addrs []ma.Multiaddr, ttl time.Duration) {
+	addrs = cleanAddrs(addrs)
+	if ttl <= 0 {
+		ab.deleteAddrs(p, addrs)
+		return
+	}
+	ab.setAddrs(p, addrs, ttl, ttlOverride, false)
+}
+
+// UpdateAddrs will update any addresses for a given peer and TTL combination to
+// have a new TTL.
+func (ab *dsAddrBook) UpdateAddrs(p peer.ID, oldTTL time.Duration, newTTL time.Duration) {
+	pr, err := ab.loadRecord(p, true, false)
+	if err != nil {
+		log.Errorf("failed to update ttls for peer %s: %s\n", p.Pretty(), err)
+		return
+	}
+
+	pr.Lock()
+	defer pr.Unlock()
+
+	newExp := ab.clock.Now().Add(newTTL).Unix()
+	for _, entry := range pr.Addrs {
+		if entry.Ttl != int64(oldTTL) {
+			continue
+		}
+		entry.Ttl, entry.Expiry = int64(newTTL), newExp
+		pr.dirty = true
+	}
+
+	if pr.clean(ab.clock.Now()) {
+		pr.flush(ab.ds)
+	}
+}
+
+// Addrs returns all of the non-expired addresses for a given peer.
+func (ab *dsAddrBook) Addrs(p peer.ID) []ma.Multiaddr {
+	pr, err := ab.loadRecord(p, true, true)
+	if err != nil {
+		log.Warn("failed to load peerstore entry for peer %v while querying addrs, err: %v", p, err)
+		return nil
+	}
+
+	pr.RLock()
+	defer pr.RUnlock()
+
+	addrs := make([]ma.Multiaddr, len(pr.Addrs))
+	for i, a := range pr.Addrs {
+		addrs[i] = a.Addr
+	}
+	return addrs
+}
+
+// Peers returns all of the peer IDs for which the AddrBook has addresses.
+func (ab *dsAddrBook) PeersWithAddrs() peer.IDSlice {
+	ids, err := uniquePeerIds(ab.ds, addrBookBase, func(result query.Result) string {
+		return ds.RawKey(result.Key).Name()
+	})
+	if err != nil {
+		log.Errorf("error while retrieving peers with addresses: %v", err)
+	}
+	return ids
+}
+
+// AddrStream returns a channel on which all new addresses discovered for a
+// given peer ID will be published.
+func (ab *dsAddrBook) AddrStream(ctx context.Context, p peer.ID) <-chan ma.Multiaddr {
+	initial := ab.Addrs(p)
+	return ab.subsManager.AddrStream(ctx, p, initial)
+}
+
+// ClearAddrs will delete all known addresses for a peer ID.
+func (ab *dsAddrBook) ClearAddrs(p peer.ID) {
+	ab.cache.Remove(p)
+
+	key := addrBookBase.ChildString(b32.RawStdEncoding.EncodeToString([]byte(p)))
+	if err := ab.ds.Delete(context.TODO(), key); err != nil {
+		log.Errorf("failed to clear addresses for peer %s: %v", p.Pretty(), err)
+	}
+}
+
+func (ab *dsAddrBook) setAddrs(p peer.ID, addrs []ma.Multiaddr, ttl time.Duration, mode ttlWriteMode, signed bool) (err error) {
+	if len(addrs) == 0 {
+		return nil
+	}
+
+	pr, err := ab.loadRecord(p, true, false)
+	if err != nil {
+		return fmt.Errorf("failed to load peerstore entry for peer %v while setting addrs, err: %v", p, err)
+	}
+
+	pr.Lock()
+	defer pr.Unlock()
+
+	// // if we have a signed PeerRecord, ignore attempts to add unsigned addrs
+	// if !signed && pr.CertifiedRecord != nil {
+	// 	return nil
+	// }
+
+	newExp := ab.clock.Now().Add(ttl).Unix()
+	addrsMap := make(map[string]*pb.AddrBookRecord_AddrEntry, len(pr.Addrs))
+	for _, addr := range pr.Addrs {
+		addrsMap[string(addr.Addr.Bytes())] = addr
+	}
+
+	updateExisting := func(incoming ma.Multiaddr) *pb.AddrBookRecord_AddrEntry {
+		existingEntry := addrsMap[string(incoming.Bytes())]
+		if existingEntry == nil {
+			return nil
+		}
+
+		switch mode {
+		case ttlOverride:
+			existingEntry.Ttl = int64(ttl)
+			existingEntry.Expiry = newExp
+		case ttlExtend:
+			if int64(ttl) > existingEntry.Ttl {
+				existingEntry.Ttl = int64(ttl)
+			}
+			if newExp > existingEntry.Expiry {
+				existingEntry.Expiry = newExp
+			}
+		default:
+			panic("BUG: unimplemented ttl mode")
+		}
+		return existingEntry
+	}
+
+	var entries []*pb.AddrBookRecord_AddrEntry
+	for _, incoming := range addrs {
+		existingEntry := updateExisting(incoming)
+
+		if existingEntry == nil {
+			// 	if signed {
+			// 		entries = append(entries, existingEntry)
+			// 	}
+			// } else {
+			// new addr, add & broadcast
+			entry := &pb.AddrBookRecord_AddrEntry{
+				Addr:   &pb.ProtoAddr{Multiaddr: incoming},
+				Ttl:    int64(ttl),
+				Expiry: newExp,
+			}
+			entries = append(entries, entry)
+
+			// note: there's a minor chance that writing the record will fail, in which case we would've broadcast
+			// the addresses without persisting them. This is very unlikely and not much of an issue.
+			ab.subsManager.BroadcastAddr(p, incoming)
+		}
+	}
+
+	// if signed {
+	// 	// when adding signed addrs, we want to keep _only_ the incoming addrs
+	// 	pr.Addrs = entries
+	// } else {
+	pr.Addrs = append(pr.Addrs, entries...)
+	// }
+
+	pr.dirty = true
+	pr.clean(ab.clock.Now())
+	return pr.flush(ab.ds)
+}
+
+// deletes addresses in place, avoiding copies until we encounter the first deletion.
+// does not preserve order, but entries are re-sorted before flushing to disk anyway.
+func deleteInPlace(s []*pb.AddrBookRecord_AddrEntry, addrs []ma.Multiaddr) []*pb.AddrBookRecord_AddrEntry {
+	if s == nil || len(addrs) == 0 {
+		return s
+	}
+	survived := len(s)
+Outer:
+	for i, addr := range s {
+		for _, del := range addrs {
+			if !addr.Addr.Equal(del) {
+				continue
+			}
+			survived--
+			// if there are no survivors, bail out
+			if survived == 0 {
+				break Outer
+			}
+			s[i] = s[survived]
+			// we've already dealt with s[i], move to the next
+			continue Outer
+		}
+	}
+	return s[:survived]
+}
+
+func (ab *dsAddrBook) deleteAddrs(p peer.ID, addrs []ma.Multiaddr) (err error) {
+	pr, err := ab.loadRecord(p, false, false)
+	if err != nil {
+		return fmt.Errorf("failed to load peerstore entry for peer %v while deleting addrs, err: %v", p, err)
+	}
+
+	pr.Lock()
+	defer pr.Unlock()
+
+	if pr.Addrs == nil {
+		return nil
+	}
+
+	pr.Addrs = deleteInPlace(pr.Addrs, addrs)
+
+	pr.dirty = true
+	pr.clean(ab.clock.Now())
+	return pr.flush(ab.ds)
+}
+
+func cleanAddrs(addrs []ma.Multiaddr) []ma.Multiaddr {
+	clean := make([]ma.Multiaddr, 0, len(addrs))
+	for _, addr := range addrs {
+		if addr == nil {
+			continue
+		}
+		clean = append(clean, addr)
+	}
+	return clean
+}
diff --git a/p2p/host/peerstore/pstoreds/addr_book_gc.go b/p2p/host/peerstore/pstoreds/addr_book_gc.go
new file mode 100644
index 00000000..06df6489
--- /dev/null
+++ b/p2p/host/peerstore/pstoreds/addr_book_gc.go
@@ -0,0 +1,410 @@
+package pstoreds
+
+import (
+	"context"
+	"fmt"
+	"strconv"
+	"time"
+
+	pb "github.com/libp2p/go-libp2p/p2p/host/peerstore/pb"
+
+	"github.com/libp2p/go-libp2p-core/peer"
+
+	ds "github.com/ipfs/go-datastore"
+	"github.com/ipfs/go-datastore/query"
+	b32 "github.com/multiformats/go-base32"
+)
+
+var (
+	// GC lookahead entries are stored in key pattern:
+	// /peers/gc/addrs/<unix timestamp of next visit>/<peer ID b32> => nil
+	// in databases with lexicographical key order, this time-indexing allows us to visit
+	// only the timeslice we are interested in.
+	gcLookaheadBase = ds.NewKey("/peers/gc/addrs")
+
+	// queries
+	purgeLookaheadQuery = query.Query{
+		Prefix:   gcLookaheadBase.String(),
+		Orders:   []query.Order{query.OrderByFunction(orderByTimestampInKey)},
+		KeysOnly: true,
+	}
+
+	purgeStoreQuery = query.Query{
+		Prefix:   addrBookBase.String(),
+		Orders:   []query.Order{query.OrderByKey{}},
+		KeysOnly: false,
+	}
+
+	populateLookaheadQuery = query.Query{
+		Prefix:   addrBookBase.String(),
+		Orders:   []query.Order{query.OrderByKey{}},
+		KeysOnly: true,
+	}
+)
+
+// dsAddrBookGc is responsible for garbage collection in a datastore-backed address book.
+type dsAddrBookGc struct {
+	ctx              context.Context
+	ab               *dsAddrBook
+	running          chan struct{}
+	lookaheadEnabled bool
+	purgeFunc        func()
+	currWindowEnd    int64
+}
+
+func newAddressBookGc(ctx context.Context, ab *dsAddrBook) (*dsAddrBookGc, error) {
+	if ab.opts.GCPurgeInterval < 0 {
+		return nil, fmt.Errorf("negative GC purge interval provided: %s", ab.opts.GCPurgeInterval)
+	}
+	if ab.opts.GCLookaheadInterval < 0 {
+		return nil, fmt.Errorf("negative GC lookahead interval provided: %s", ab.opts.GCLookaheadInterval)
+	}
+	if ab.opts.GCInitialDelay < 0 {
+		return nil, fmt.Errorf("negative GC initial delay provided: %s", ab.opts.GCInitialDelay)
+	}
+	if ab.opts.GCLookaheadInterval > 0 && ab.opts.GCLookaheadInterval < ab.opts.GCPurgeInterval {
+		return nil, fmt.Errorf("lookahead interval must be larger than purge interval, respectively: %s, %s",
+			ab.opts.GCLookaheadInterval, ab.opts.GCPurgeInterval)
+	}
+
+	lookaheadEnabled := ab.opts.GCLookaheadInterval > 0
+	gc := &dsAddrBookGc{
+		ctx:              ctx,
+		ab:               ab,
+		running:          make(chan struct{}, 1),
+		lookaheadEnabled: lookaheadEnabled,
+	}
+
+	if lookaheadEnabled {
+		gc.purgeFunc = gc.purgeLookahead
+	} else {
+		gc.purgeFunc = gc.purgeStore
+	}
+
+	// do not start GC timers if purge is disabled; this GC can only be triggered manually.
+	if ab.opts.GCPurgeInterval > 0 {
+		gc.ab.childrenDone.Add(1)
+		go gc.background()
+	}
+
+	return gc, nil
+}
+
+// gc prunes expired addresses from the datastore at regular intervals. It should be spawned as a goroutine.
+func (gc *dsAddrBookGc) background() {
+	defer gc.ab.childrenDone.Done()
+
+	select {
+	case <-gc.ab.clock.After(gc.ab.opts.GCInitialDelay):
+	case <-gc.ab.ctx.Done():
+		// yield if we have been cancelled/closed before the delay elapses.
+		return
+	}
+
+	purgeTimer := time.NewTicker(gc.ab.opts.GCPurgeInterval)
+	defer purgeTimer.Stop()
+
+	var lookaheadCh <-chan time.Time
+	if gc.lookaheadEnabled {
+		lookaheadTimer := time.NewTicker(gc.ab.opts.GCLookaheadInterval)
+		lookaheadCh = lookaheadTimer.C
+		gc.populateLookahead() // do a lookahead now
+		defer lookaheadTimer.Stop()
+	}
+
+	for {
+		select {
+		case <-purgeTimer.C:
+			gc.purgeFunc()
+
+		case <-lookaheadCh:
+			// will never trigger if lookahead is disabled (nil Duration).
+			gc.populateLookahead()
+
+		case <-gc.ctx.Done():
+			return
+		}
+	}
+}
+
+// purgeCycle runs a single GC purge cycle. It operates within the lookahead window if lookahead is enabled; else it
+// visits all entries in the datastore, deleting the addresses that have expired.
+func (gc *dsAddrBookGc) purgeLookahead() {
+	select {
+	case gc.running <- struct{}{}:
+		defer func() { <-gc.running }()
+	default:
+		// yield if lookahead is running.
+		return
+	}
+
+	var id peer.ID
+	record := &addrsRecord{AddrBookRecord: &pb.AddrBookRecord{}} // empty record to reuse and avoid allocs.
+	batch, err := newCyclicBatch(gc.ab.ds, defaultOpsPerCyclicBatch)
+	if err != nil {
+		log.Warnf("failed while creating batch to purge GC entries: %v", err)
+	}
+
+	// This function drops an unparseable GC entry; this is for safety. It is an escape hatch in case
+	// we modify the format of keys going forward. If a user runs a new version against an old DB,
+	// if we don't clean up unparseable entries we'll end up accumulating garbage.
+	dropInError := func(key ds.Key, err error, msg string) {
+		if err != nil {
+			log.Warnf("failed while %s record with GC key: %v, err: %v; deleting", msg, key, err)
+		}
+		if err = batch.Delete(context.TODO(), key); err != nil {
+			log.Warnf("failed to delete corrupt GC lookahead entry: %v, err: %v", key, err)
+		}
+	}
+
+	// This function drops a GC key if the entry is cleaned correctly. It may reschedule another visit
+	// if the next earliest expiry falls within the current window again.
+	dropOrReschedule := func(key ds.Key, ar *addrsRecord) {
+		if err := batch.Delete(context.TODO(), key); err != nil {
+			log.Warnf("failed to delete lookahead entry: %v, err: %v", key, err)
+		}
+
+		// re-add the record if it needs to be visited again in this window.
+		if len(ar.Addrs) != 0 && ar.Addrs[0].Expiry <= gc.currWindowEnd {
+			gcKey := gcLookaheadBase.ChildString(fmt.Sprintf("%d/%s", ar.Addrs[0].Expiry, key.Name()))
+			if err := batch.Put(context.TODO(), gcKey, []byte{}); err != nil {
+				log.Warnf("failed to add new GC key: %v, err: %v", gcKey, err)
+			}
+		}
+	}
+
+	results, err := gc.ab.ds.Query(context.TODO(), purgeLookaheadQuery)
+	if err != nil {
+		log.Warnf("failed while fetching entries to purge: %v", err)
+		return
+	}
+	defer results.Close()
+
+	now := gc.ab.clock.Now().Unix()
+
+	// keys: 	/peers/gc/addrs/<unix timestamp of next visit>/<peer ID b32>
+	// values: 	nil
+	for result := range results.Next() {
+		gcKey := ds.RawKey(result.Key)
+		ts, err := strconv.ParseInt(gcKey.Parent().Name(), 10, 64)
+		if err != nil {
+			dropInError(gcKey, err, "parsing timestamp")
+			log.Warnf("failed while parsing timestamp from key: %v, err: %v", result.Key, err)
+			continue
+		} else if ts > now {
+			// this is an ordered cursor; when we hit an entry with a timestamp beyond now, we can break.
+			break
+		}
+
+		idb32, err := b32.RawStdEncoding.DecodeString(gcKey.Name())
+		if err != nil {
+			dropInError(gcKey, err, "parsing peer ID")
+			log.Warnf("failed while parsing b32 peer ID from key: %v, err: %v", result.Key, err)
+			continue
+		}
+
+		id, err = peer.IDFromBytes(idb32)
+		if err != nil {
+			dropInError(gcKey, err, "decoding peer ID")
+			log.Warnf("failed while decoding peer ID from key: %v, err: %v", result.Key, err)
+			continue
+		}
+
+		// if the record is in cache, we clean it and flush it if necessary.
+		if e, ok := gc.ab.cache.Peek(id); ok {
+			cached := e.(*addrsRecord)
+			cached.Lock()
+			if cached.clean(gc.ab.clock.Now()) {
+				if err = cached.flush(batch); err != nil {
+					log.Warnf("failed to flush entry modified by GC for peer: &v, err: %v", id.Pretty(), err)
+				}
+			}
+			dropOrReschedule(gcKey, cached)
+			cached.Unlock()
+			continue
+		}
+
+		record.Reset()
+
+		// otherwise, fetch it from the store, clean it and flush it.
+		entryKey := addrBookBase.ChildString(gcKey.Name())
+		val, err := gc.ab.ds.Get(context.TODO(), entryKey)
+		if err != nil {
+			// captures all errors, including ErrNotFound.
+			dropInError(gcKey, err, "fetching entry")
+			continue
+		}
+		err = record.Unmarshal(val)
+		if err != nil {
+			dropInError(gcKey, err, "unmarshalling entry")
+			continue
+		}
+		if record.clean(gc.ab.clock.Now()) {
+			err = record.flush(batch)
+			if err != nil {
+				log.Warnf("failed to flush entry modified by GC for peer: &v, err: %v", id.Pretty(), err)
+			}
+		}
+		dropOrReschedule(gcKey, record)
+	}
+
+	if err = batch.Commit(context.TODO()); err != nil {
+		log.Warnf("failed to commit GC purge batch: %v", err)
+	}
+}
+
+func (gc *dsAddrBookGc) purgeStore() {
+	select {
+	case gc.running <- struct{}{}:
+		defer func() { <-gc.running }()
+	default:
+		// yield if lookahead is running.
+		return
+	}
+
+	record := &addrsRecord{AddrBookRecord: &pb.AddrBookRecord{}} // empty record to reuse and avoid allocs.
+	batch, err := newCyclicBatch(gc.ab.ds, defaultOpsPerCyclicBatch)
+	if err != nil {
+		log.Warnf("failed while creating batch to purge GC entries: %v", err)
+	}
+
+	results, err := gc.ab.ds.Query(context.TODO(), purgeStoreQuery)
+	if err != nil {
+		log.Warnf("failed while opening iterator: %v", err)
+		return
+	}
+	defer results.Close()
+
+	// keys: 	/peers/addrs/<peer ID b32>
+	for result := range results.Next() {
+		record.Reset()
+		if err = record.Unmarshal(result.Value); err != nil {
+			// TODO log
+			continue
+		}
+
+		id := record.Id.ID
+		if !record.clean(gc.ab.clock.Now()) {
+			continue
+		}
+
+		if err := record.flush(batch); err != nil {
+			log.Warnf("failed to flush entry modified by GC for peer: &v, err: %v", id, err)
+		}
+		gc.ab.cache.Remove(id)
+	}
+
+	if err = batch.Commit(context.TODO()); err != nil {
+		log.Warnf("failed to commit GC purge batch: %v", err)
+	}
+}
+
+// populateLookahead populates the lookahead window by scanning the entire store and picking entries whose earliest
+// expiration falls within the window period.
+//
+// Those entries are stored in the lookahead region in the store, indexed by the timestamp when they need to be
+// visited, to facilitate temporal range scans.
+func (gc *dsAddrBookGc) populateLookahead() {
+	if gc.ab.opts.GCLookaheadInterval == 0 {
+		return
+	}
+
+	select {
+	case gc.running <- struct{}{}:
+		defer func() { <-gc.running }()
+	default:
+		// yield if something's running.
+		return
+	}
+
+	until := gc.ab.clock.Now().Add(gc.ab.opts.GCLookaheadInterval).Unix()
+
+	var id peer.ID
+	record := &addrsRecord{AddrBookRecord: &pb.AddrBookRecord{}}
+	results, err := gc.ab.ds.Query(context.TODO(), populateLookaheadQuery)
+	if err != nil {
+		log.Warnf("failed while querying to populate lookahead GC window: %v", err)
+		return
+	}
+	defer results.Close()
+
+	batch, err := newCyclicBatch(gc.ab.ds, defaultOpsPerCyclicBatch)
+	if err != nil {
+		log.Warnf("failed while creating batch to populate lookahead GC window: %v", err)
+		return
+	}
+
+	for result := range results.Next() {
+		idb32 := ds.RawKey(result.Key).Name()
+		k, err := b32.RawStdEncoding.DecodeString(idb32)
+		if err != nil {
+			log.Warnf("failed while decoding peer ID from key: %v, err: %v", result.Key, err)
+			continue
+		}
+		if id, err = peer.IDFromBytes(k); err != nil {
+			log.Warnf("failed while decoding peer ID from key: %v, err: %v", result.Key, err)
+		}
+
+		// if the record is in cache, use the cached version.
+		if e, ok := gc.ab.cache.Peek(id); ok {
+			cached := e.(*addrsRecord)
+			cached.RLock()
+			if len(cached.Addrs) == 0 || cached.Addrs[0].Expiry > until {
+				cached.RUnlock()
+				continue
+			}
+			gcKey := gcLookaheadBase.ChildString(fmt.Sprintf("%d/%s", cached.Addrs[0].Expiry, idb32))
+			if err = batch.Put(context.TODO(), gcKey, []byte{}); err != nil {
+				log.Warnf("failed while inserting GC entry for peer: %v, err: %v", id.Pretty(), err)
+			}
+			cached.RUnlock()
+			continue
+		}
+
+		record.Reset()
+
+		val, err := gc.ab.ds.Get(context.TODO(), ds.RawKey(result.Key))
+		if err != nil {
+			log.Warnf("failed which getting record from store for peer: %v, err: %v", id.Pretty(), err)
+			continue
+		}
+		if err := record.Unmarshal(val); err != nil {
+			log.Warnf("failed while unmarshalling record from store for peer: %v, err: %v", id.Pretty(), err)
+			continue
+		}
+		if len(record.Addrs) > 0 && record.Addrs[0].Expiry <= until {
+			gcKey := gcLookaheadBase.ChildString(fmt.Sprintf("%d/%s", record.Addrs[0].Expiry, idb32))
+			if err = batch.Put(context.TODO(), gcKey, []byte{}); err != nil {
+				log.Warnf("failed while inserting GC entry for peer: %v, err: %v", id.Pretty(), err)
+			}
+		}
+	}
+
+	if err = batch.Commit(context.TODO()); err != nil {
+		log.Warnf("failed to commit GC lookahead batch: %v", err)
+	}
+
+	gc.currWindowEnd = until
+}
+
+// orderByTimestampInKey orders the results by comparing the timestamp in the
+// key. A lexiographic sort by itself is wrong since "10" is less than "2", but
+// as an int 2 is obviously less than 10.
+func orderByTimestampInKey(a, b query.Entry) int {
+	aKey := ds.RawKey(a.Key)
+	aInt, err := strconv.ParseInt(aKey.Parent().Name(), 10, 64)
+	if err != nil {
+		return -1
+	}
+	bKey := ds.RawKey(b.Key)
+	bInt, err := strconv.ParseInt(bKey.Parent().Name(), 10, 64)
+	if err != nil {
+		return -1
+	}
+	if aInt < bInt {
+		return -1
+	} else if aInt == bInt {
+		return 0
+	}
+	return 1
+}
diff --git a/p2p/host/peerstore/pstoreds/cache.go b/p2p/host/peerstore/pstoreds/cache.go
new file mode 100644
index 00000000..d3d43aae
--- /dev/null
+++ b/p2p/host/peerstore/pstoreds/cache.go
@@ -0,0 +1,40 @@
+package pstoreds
+
+// cache abstracts all methods we access from ARCCache, to enable alternate
+// implementations such as a no-op one.
+type cache interface {
+	Get(key interface{}) (value interface{}, ok bool)
+	Add(key, value interface{})
+	Remove(key interface{})
+	Contains(key interface{}) bool
+	Peek(key interface{}) (value interface{}, ok bool)
+	Keys() []interface{}
+}
+
+// noopCache is a dummy implementation that's used when the cache is disabled.
+type noopCache struct {
+}
+
+var _ cache = (*noopCache)(nil)
+
+func (*noopCache) Get(key interface{}) (value interface{}, ok bool) {
+	return nil, false
+}
+
+func (*noopCache) Add(key, value interface{}) {
+}
+
+func (*noopCache) Remove(key interface{}) {
+}
+
+func (*noopCache) Contains(key interface{}) bool {
+	return false
+}
+
+func (*noopCache) Peek(key interface{}) (value interface{}, ok bool) {
+	return nil, false
+}
+
+func (*noopCache) Keys() (keys []interface{}) {
+	return keys
+}
diff --git a/p2p/host/peerstore/pstoreds/cyclic_batch.go b/p2p/host/peerstore/pstoreds/cyclic_batch.go
new file mode 100644
index 00000000..51f6afb0
--- /dev/null
+++ b/p2p/host/peerstore/pstoreds/cyclic_batch.go
@@ -0,0 +1,78 @@
+package pstoreds
+
+import (
+	"context"
+	"errors"
+	"fmt"
+
+	ds "github.com/ipfs/go-datastore"
+)
+
+// how many operations are queued in a cyclic batch before we flush it.
+var defaultOpsPerCyclicBatch = 20
+
+// cyclicBatch buffers ds write operations and automatically flushes them after defaultOpsPerCyclicBatch (20) have been
+// queued. An explicit `Commit()` closes this cyclic batch, erroring all further operations.
+//
+// It is similar to go-ds autobatch, but it's driven by an actual Batch facility offered by the
+// ds.
+type cyclicBatch struct {
+	threshold int
+	ds.Batch
+	ds      ds.Batching
+	pending int
+}
+
+func newCyclicBatch(ds ds.Batching, threshold int) (ds.Batch, error) {
+	batch, err := ds.Batch(context.TODO())
+	if err != nil {
+		return nil, err
+	}
+	return &cyclicBatch{Batch: batch, ds: ds}, nil
+}
+
+func (cb *cyclicBatch) cycle() (err error) {
+	if cb.Batch == nil {
+		return errors.New("cyclic batch is closed")
+	}
+	if cb.pending < cb.threshold {
+		// we haven't reached the threshold yet.
+		return nil
+	}
+	// commit and renew the batch.
+	if err = cb.Batch.Commit(context.TODO()); err != nil {
+		return fmt.Errorf("failed while committing cyclic batch: %w", err)
+	}
+	if cb.Batch, err = cb.ds.Batch(context.TODO()); err != nil {
+		return fmt.Errorf("failed while renewing cyclic batch: %w", err)
+	}
+	return nil
+}
+
+func (cb *cyclicBatch) Put(ctx context.Context, key ds.Key, val []byte) error {
+	if err := cb.cycle(); err != nil {
+		return err
+	}
+	cb.pending++
+	return cb.Batch.Put(ctx, key, val)
+}
+
+func (cb *cyclicBatch) Delete(ctx context.Context, key ds.Key) error {
+	if err := cb.cycle(); err != nil {
+		return err
+	}
+	cb.pending++
+	return cb.Batch.Delete(ctx, key)
+}
+
+func (cb *cyclicBatch) Commit(ctx context.Context) error {
+	if cb.Batch == nil {
+		return errors.New("cyclic batch is closed")
+	}
+	if err := cb.Batch.Commit(ctx); err != nil {
+		return err
+	}
+	cb.pending = 0
+	cb.Batch = nil
+	return nil
+}
diff --git a/p2p/host/peerstore/pstoreds/keybook.go b/p2p/host/peerstore/pstoreds/keybook.go
new file mode 100644
index 00000000..7ee06c81
--- /dev/null
+++ b/p2p/host/peerstore/pstoreds/keybook.go
@@ -0,0 +1,137 @@
+package pstoreds
+
+import (
+	"context"
+	"errors"
+
+	"github.com/multiformats/go-base32"
+
+	ds "github.com/ipfs/go-datastore"
+	"github.com/ipfs/go-datastore/query"
+
+	ic "github.com/libp2p/go-libp2p-core/crypto"
+	"github.com/libp2p/go-libp2p-core/peer"
+	pstore "github.com/libp2p/go-libp2p-core/peerstore"
+)
+
+// Public and private keys are stored under the following db key pattern:
+// /peers/keys/<b32 peer id no padding>/{pub, priv}
+var (
+	kbBase     = ds.NewKey("/peers/keys")
+	pubSuffix  = ds.NewKey("/pub")
+	privSuffix = ds.NewKey("/priv")
+)
+
+type dsKeyBook struct {
+	ds ds.Datastore
+}
+
+var _ pstore.KeyBook = (*dsKeyBook)(nil)
+
+func NewKeyBook(_ context.Context, store ds.Datastore, _ Options) (*dsKeyBook, error) {
+	return &dsKeyBook{store}, nil
+}
+
+func (kb *dsKeyBook) PubKey(p peer.ID) ic.PubKey {
+	key := peerToKey(p, pubSuffix)
+
+	var pk ic.PubKey
+	if value, err := kb.ds.Get(context.TODO(), key); err == nil {
+		pk, err = ic.UnmarshalPublicKey(value)
+		if err != nil {
+			log.Errorf("error when unmarshalling pubkey from datastore for peer %s: %s\n", p.Pretty(), err)
+		}
+	} else if err == ds.ErrNotFound {
+		pk, err = p.ExtractPublicKey()
+		switch err {
+		case nil:
+		case peer.ErrNoPublicKey:
+			return nil
+		default:
+			log.Errorf("error when extracting pubkey from peer ID for peer %s: %s\n", p.Pretty(), err)
+			return nil
+		}
+		pkb, err := ic.MarshalPublicKey(pk)
+		if err != nil {
+			log.Errorf("error when turning extracted pubkey into bytes for peer %s: %s\n", p.Pretty(), err)
+			return nil
+		}
+		if err := kb.ds.Put(context.TODO(), key, pkb); err != nil {
+			log.Errorf("error when adding extracted pubkey to peerstore for peer %s: %s\n", p.Pretty(), err)
+			return nil
+		}
+	} else {
+		log.Errorf("error when fetching pubkey from datastore for peer %s: %s\n", p.Pretty(), err)
+	}
+
+	return pk
+}
+
+func (kb *dsKeyBook) AddPubKey(p peer.ID, pk ic.PubKey) error {
+	// check it's correct.
+	if !p.MatchesPublicKey(pk) {
+		return errors.New("peer ID does not match public key")
+	}
+
+	val, err := ic.MarshalPublicKey(pk)
+	if err != nil {
+		log.Errorf("error while converting pubkey byte string for peer %s: %s\n", p.Pretty(), err)
+		return err
+	}
+	if err := kb.ds.Put(context.TODO(), peerToKey(p, pubSuffix), val); err != nil {
+		log.Errorf("error while updating pubkey in datastore for peer %s: %s\n", p.Pretty(), err)
+		return err
+	}
+	return nil
+}
+
+func (kb *dsKeyBook) PrivKey(p peer.ID) ic.PrivKey {
+	value, err := kb.ds.Get(context.TODO(), peerToKey(p, privSuffix))
+	if err != nil {
+		return nil
+	}
+	sk, err := ic.UnmarshalPrivateKey(value)
+	if err != nil {
+		return nil
+	}
+	return sk
+}
+
+func (kb *dsKeyBook) AddPrivKey(p peer.ID, sk ic.PrivKey) error {
+	if sk == nil {
+		return errors.New("private key is nil")
+	}
+	// check it's correct.
+	if !p.MatchesPrivateKey(sk) {
+		return errors.New("peer ID does not match private key")
+	}
+
+	val, err := ic.MarshalPrivateKey(sk)
+	if err != nil {
+		log.Errorf("error while converting privkey byte string for peer %s: %s\n", p.Pretty(), err)
+		return err
+	}
+	if err := kb.ds.Put(context.TODO(), peerToKey(p, privSuffix), val); err != nil {
+		log.Errorf("error while updating privkey in datastore for peer %s: %s\n", p.Pretty(), err)
+	}
+	return err
+}
+
+func (kb *dsKeyBook) PeersWithKeys() peer.IDSlice {
+	ids, err := uniquePeerIds(kb.ds, kbBase, func(result query.Result) string {
+		return ds.RawKey(result.Key).Parent().Name()
+	})
+	if err != nil {
+		log.Errorf("error while retrieving peers with keys: %v", err)
+	}
+	return ids
+}
+
+func (kb *dsKeyBook) RemovePeer(p peer.ID) {
+	kb.ds.Delete(context.TODO(), peerToKey(p, privSuffix))
+	kb.ds.Delete(context.TODO(), peerToKey(p, pubSuffix))
+}
+
+func peerToKey(p peer.ID, suffix ds.Key) ds.Key {
+	return kbBase.ChildString(base32.RawStdEncoding.EncodeToString([]byte(p))).Child(suffix)
+}
diff --git a/p2p/host/peerstore/pstoreds/metadata.go b/p2p/host/peerstore/pstoreds/metadata.go
new file mode 100644
index 00000000..14201735
--- /dev/null
+++ b/p2p/host/peerstore/pstoreds/metadata.go
@@ -0,0 +1,81 @@
+package pstoreds
+
+import (
+	"bytes"
+	"context"
+	"encoding/gob"
+
+	pool "github.com/libp2p/go-buffer-pool"
+	"github.com/libp2p/go-libp2p-core/peer"
+	pstore "github.com/libp2p/go-libp2p-core/peerstore"
+
+	ds "github.com/ipfs/go-datastore"
+	"github.com/ipfs/go-datastore/query"
+	"github.com/multiformats/go-base32"
+)
+
+// Metadata is stored under the following db key pattern:
+// /peers/metadata/<b32 peer id no padding>/<key>
+var pmBase = ds.NewKey("/peers/metadata")
+
+type dsPeerMetadata struct {
+	ds ds.Datastore
+}
+
+var _ pstore.PeerMetadata = (*dsPeerMetadata)(nil)
+
+func init() {
+	// Gob registers basic types by default.
+	//
+	// Register complex types used by the peerstore itself.
+	gob.Register(make(map[string]struct{}))
+}
+
+// NewPeerMetadata creates a metadata store backed by a persistent db. It uses gob for serialisation.
+//
+// See `init()` to learn which types are registered by default. Modules wishing to store
+// values of other types will need to `gob.Register()` them explicitly, or else callers
+// will receive runtime errors.
+func NewPeerMetadata(_ context.Context, store ds.Datastore, _ Options) (*dsPeerMetadata, error) {
+	return &dsPeerMetadata{store}, nil
+}
+
+func (pm *dsPeerMetadata) Get(p peer.ID, key string) (interface{}, error) {
+	k := pmBase.ChildString(base32.RawStdEncoding.EncodeToString([]byte(p))).ChildString(key)
+	value, err := pm.ds.Get(context.TODO(), k)
+	if err != nil {
+		if err == ds.ErrNotFound {
+			err = pstore.ErrNotFound
+		}
+		return nil, err
+	}
+
+	var res interface{}
+	if err := gob.NewDecoder(bytes.NewReader(value)).Decode(&res); err != nil {
+		return nil, err
+	}
+	return res, nil
+}
+
+func (pm *dsPeerMetadata) Put(p peer.ID, key string, val interface{}) error {
+	k := pmBase.ChildString(base32.RawStdEncoding.EncodeToString([]byte(p))).ChildString(key)
+	var buf pool.Buffer
+	if err := gob.NewEncoder(&buf).Encode(&val); err != nil {
+		return err
+	}
+	return pm.ds.Put(context.TODO(), k, buf.Bytes())
+}
+
+func (pm *dsPeerMetadata) RemovePeer(p peer.ID) {
+	result, err := pm.ds.Query(context.TODO(), query.Query{
+		Prefix:   pmBase.ChildString(base32.RawStdEncoding.EncodeToString([]byte(p))).String(),
+		KeysOnly: true,
+	})
+	if err != nil {
+		log.Warnw("querying datastore when removing peer failed", "peer", p, "error", err)
+		return
+	}
+	for entry := range result.Next() {
+		pm.ds.Delete(context.TODO(), ds.NewKey(entry.Key))
+	}
+}
diff --git a/p2p/host/peerstore/pstoreds/peerstore.go b/p2p/host/peerstore/pstoreds/peerstore.go
new file mode 100644
index 00000000..df6069b7
--- /dev/null
+++ b/p2p/host/peerstore/pstoreds/peerstore.go
@@ -0,0 +1,192 @@
+package pstoreds
+
+import (
+	"context"
+	"fmt"
+	"io"
+	"time"
+
+	"github.com/libp2p/go-libp2p-core/peer"
+	"github.com/libp2p/go-libp2p-core/peerstore"
+
+	pstore "github.com/libp2p/go-libp2p/p2p/host/peerstore"
+
+	ds "github.com/ipfs/go-datastore"
+	"github.com/ipfs/go-datastore/query"
+	"github.com/multiformats/go-base32"
+)
+
+// Configuration object for the peerstore.
+type Options struct {
+	// The size of the in-memory cache. A value of 0 or lower disables the cache.
+	CacheSize uint
+
+	// MaxProtocols is the maximum number of protocols we store for one peer.
+	MaxProtocols int
+
+	// Sweep interval to purge expired addresses from the datastore. If this is a zero value, GC will not run
+	// automatically, but it'll be available on demand via explicit calls.
+	GCPurgeInterval time.Duration
+
+	// Interval to renew the GC lookahead window. If this is a zero value, lookahead will be disabled and we'll
+	// traverse the entire datastore for every purge cycle.
+	GCLookaheadInterval time.Duration
+
+	// Initial delay before GC processes start. Intended to give the system breathing room to fully boot
+	// before starting GC.
+	GCInitialDelay time.Duration
+
+	Clock clock
+}
+
+// DefaultOpts returns the default options for a persistent peerstore, with the full-purge GC algorithm:
+//
+// * Cache size: 1024.
+// * MaxProtocols: 1024.
+// * GC purge interval: 2 hours.
+// * GC lookahead interval: disabled.
+// * GC initial delay: 60 seconds.
+func DefaultOpts() Options {
+	return Options{
+		CacheSize:           1024,
+		MaxProtocols:        1024,
+		GCPurgeInterval:     2 * time.Hour,
+		GCLookaheadInterval: 0,
+		GCInitialDelay:      60 * time.Second,
+		Clock:               realclock{},
+	}
+}
+
+type pstoreds struct {
+	peerstore.Metrics
+
+	*dsKeyBook
+	*dsAddrBook
+	*dsProtoBook
+	*dsPeerMetadata
+}
+
+var _ peerstore.Peerstore = &pstoreds{}
+
+// NewPeerstore creates a peerstore backed by the provided persistent datastore.
+// It's the caller's responsibility to call RemovePeer to ensure
+// that memory consumption of the peerstore doesn't grow unboundedly.
+func NewPeerstore(ctx context.Context, store ds.Batching, opts Options) (*pstoreds, error) {
+	addrBook, err := NewAddrBook(ctx, store, opts)
+	if err != nil {
+		return nil, err
+	}
+
+	keyBook, err := NewKeyBook(ctx, store, opts)
+	if err != nil {
+		return nil, err
+	}
+
+	peerMetadata, err := NewPeerMetadata(ctx, store, opts)
+	if err != nil {
+		return nil, err
+	}
+
+	protoBook, err := NewProtoBook(peerMetadata, WithMaxProtocols(opts.MaxProtocols))
+	if err != nil {
+		return nil, err
+	}
+
+	return &pstoreds{
+		Metrics:        pstore.NewMetrics(),
+		dsKeyBook:      keyBook,
+		dsAddrBook:     addrBook,
+		dsPeerMetadata: peerMetadata,
+		dsProtoBook:    protoBook,
+	}, nil
+}
+
+// uniquePeerIds extracts and returns unique peer IDs from database keys.
+func uniquePeerIds(ds ds.Datastore, prefix ds.Key, extractor func(result query.Result) string) (peer.IDSlice, error) {
+	var (
+		q       = query.Query{Prefix: prefix.String(), KeysOnly: true}
+		results query.Results
+		err     error
+	)
+
+	if results, err = ds.Query(context.TODO(), q); err != nil {
+		log.Error(err)
+		return nil, err
+	}
+
+	defer results.Close()
+
+	idset := make(map[string]struct{})
+	for result := range results.Next() {
+		k := extractor(result)
+		idset[k] = struct{}{}
+	}
+
+	if len(idset) == 0 {
+		return peer.IDSlice{}, nil
+	}
+
+	ids := make(peer.IDSlice, 0, len(idset))
+	for id := range idset {
+		pid, _ := base32.RawStdEncoding.DecodeString(id)
+		id, _ := peer.IDFromBytes(pid)
+		ids = append(ids, id)
+	}
+	return ids, nil
+}
+
+func (ps *pstoreds) Close() (err error) {
+	var errs []error
+	weakClose := func(name string, c interface{}) {
+		if cl, ok := c.(io.Closer); ok {
+			if err = cl.Close(); err != nil {
+				errs = append(errs, fmt.Errorf("%s error: %s", name, err))
+			}
+		}
+	}
+	weakClose("keybook", ps.dsKeyBook)
+	weakClose("addressbook", ps.dsAddrBook)
+	weakClose("protobook", ps.dsProtoBook)
+	weakClose("peermetadata", ps.dsPeerMetadata)
+
+	if len(errs) > 0 {
+		return fmt.Errorf("failed while closing peerstore; err(s): %q", errs)
+	}
+	return nil
+}
+
+func (ps *pstoreds) Peers() peer.IDSlice {
+	set := map[peer.ID]struct{}{}
+	for _, p := range ps.PeersWithKeys() {
+		set[p] = struct{}{}
+	}
+	for _, p := range ps.PeersWithAddrs() {
+		set[p] = struct{}{}
+	}
+
+	pps := make(peer.IDSlice, 0, len(set))
+	for p := range set {
+		pps = append(pps, p)
+	}
+	return pps
+}
+
+func (ps *pstoreds) PeerInfo(p peer.ID) peer.AddrInfo {
+	return peer.AddrInfo{
+		ID:    p,
+		Addrs: ps.dsAddrBook.Addrs(p),
+	}
+}
+
+// RemovePeer removes entries associated with a peer from:
+// * the KeyBook
+// * the ProtoBook
+// * the PeerMetadata
+// * the Metrics
+// It DOES NOT remove the peer from the AddrBook.
+func (ps *pstoreds) RemovePeer(p peer.ID) {
+	ps.dsKeyBook.RemovePeer(p)
+	ps.dsProtoBook.RemovePeer(p)
+	ps.dsPeerMetadata.RemovePeer(p)
+	ps.Metrics.RemovePeer(p)
+}
diff --git a/p2p/host/peerstore/pstoreds/protobook.go b/p2p/host/peerstore/pstoreds/protobook.go
new file mode 100644
index 00000000..af44722c
--- /dev/null
+++ b/p2p/host/peerstore/pstoreds/protobook.go
@@ -0,0 +1,196 @@
+package pstoreds
+
+import (
+	"errors"
+	"fmt"
+	"sync"
+
+	"github.com/libp2p/go-libp2p-core/peer"
+
+	pstore "github.com/libp2p/go-libp2p-core/peerstore"
+)
+
+type protoSegment struct {
+	sync.RWMutex
+}
+
+type protoSegments [256]*protoSegment
+
+func (s *protoSegments) get(p peer.ID) *protoSegment {
+	return s[byte(p[len(p)-1])]
+}
+
+var errTooManyProtocols = errors.New("too many protocols")
+
+type ProtoBookOption func(*dsProtoBook) error
+
+func WithMaxProtocols(num int) ProtoBookOption {
+	return func(pb *dsProtoBook) error {
+		pb.maxProtos = num
+		return nil
+	}
+}
+
+type dsProtoBook struct {
+	segments  protoSegments
+	meta      pstore.PeerMetadata
+	maxProtos int
+}
+
+var _ pstore.ProtoBook = (*dsProtoBook)(nil)
+
+func NewProtoBook(meta pstore.PeerMetadata, opts ...ProtoBookOption) (*dsProtoBook, error) {
+	pb := &dsProtoBook{
+		meta: meta,
+		segments: func() (ret protoSegments) {
+			for i := range ret {
+				ret[i] = &protoSegment{}
+			}
+			return ret
+		}(),
+		maxProtos: 1024,
+	}
+
+	for _, opt := range opts {
+		if err := opt(pb); err != nil {
+			return nil, err
+		}
+	}
+	return pb, nil
+}
+
+func (pb *dsProtoBook) SetProtocols(p peer.ID, protos ...string) error {
+	if len(protos) > pb.maxProtos {
+		return errTooManyProtocols
+	}
+
+	protomap := make(map[string]struct{}, len(protos))
+	for _, proto := range protos {
+		protomap[proto] = struct{}{}
+	}
+
+	s := pb.segments.get(p)
+	s.Lock()
+	defer s.Unlock()
+
+	return pb.meta.Put(p, "protocols", protomap)
+}
+
+func (pb *dsProtoBook) AddProtocols(p peer.ID, protos ...string) error {
+	s := pb.segments.get(p)
+	s.Lock()
+	defer s.Unlock()
+
+	pmap, err := pb.getProtocolMap(p)
+	if err != nil {
+		return err
+	}
+	if len(pmap)+len(protos) > pb.maxProtos {
+		return errTooManyProtocols
+	}
+
+	for _, proto := range protos {
+		pmap[proto] = struct{}{}
+	}
+
+	return pb.meta.Put(p, "protocols", pmap)
+}
+
+func (pb *dsProtoBook) GetProtocols(p peer.ID) ([]string, error) {
+	s := pb.segments.get(p)
+	s.RLock()
+	defer s.RUnlock()
+
+	pmap, err := pb.getProtocolMap(p)
+	if err != nil {
+		return nil, err
+	}
+
+	res := make([]string, 0, len(pmap))
+	for proto := range pmap {
+		res = append(res, proto)
+	}
+
+	return res, nil
+}
+
+func (pb *dsProtoBook) SupportsProtocols(p peer.ID, protos ...string) ([]string, error) {
+	s := pb.segments.get(p)
+	s.RLock()
+	defer s.RUnlock()
+
+	pmap, err := pb.getProtocolMap(p)
+	if err != nil {
+		return nil, err
+	}
+
+	res := make([]string, 0, len(protos))
+	for _, proto := range protos {
+		if _, ok := pmap[proto]; ok {
+			res = append(res, proto)
+		}
+	}
+
+	return res, nil
+}
+
+func (pb *dsProtoBook) FirstSupportedProtocol(p peer.ID, protos ...string) (string, error) {
+	s := pb.segments.get(p)
+	s.RLock()
+	defer s.RUnlock()
+
+	pmap, err := pb.getProtocolMap(p)
+	if err != nil {
+		return "", err
+	}
+	for _, proto := range protos {
+		if _, ok := pmap[proto]; ok {
+			return proto, nil
+		}
+	}
+
+	return "", nil
+}
+
+func (pb *dsProtoBook) RemoveProtocols(p peer.ID, protos ...string) error {
+	s := pb.segments.get(p)
+	s.Lock()
+	defer s.Unlock()
+
+	pmap, err := pb.getProtocolMap(p)
+	if err != nil {
+		return err
+	}
+
+	if len(pmap) == 0 {
+		// nothing to do.
+		return nil
+	}
+
+	for _, proto := range protos {
+		delete(pmap, proto)
+	}
+
+	return pb.meta.Put(p, "protocols", pmap)
+}
+
+func (pb *dsProtoBook) getProtocolMap(p peer.ID) (map[string]struct{}, error) {
+	iprotomap, err := pb.meta.Get(p, "protocols")
+	switch err {
+	default:
+		return nil, err
+	case pstore.ErrNotFound:
+		return make(map[string]struct{}), nil
+	case nil:
+		cast, ok := iprotomap.(map[string]struct{})
+		if !ok {
+			return nil, fmt.Errorf("stored protocol set was not a map")
+		}
+
+		return cast, nil
+	}
+}
+
+func (pb *dsProtoBook) RemovePeer(p peer.ID) {
+	pb.meta.RemovePeer(p)
+}
diff --git a/p2p/host/peerstore/pstoremem/addr_book.go b/p2p/host/peerstore/pstoremem/addr_book.go
new file mode 100644
index 00000000..7e6a67fa
--- /dev/null
+++ b/p2p/host/peerstore/pstoremem/addr_book.go
@@ -0,0 +1,517 @@
+package pstoremem
+
+import (
+	"context"
+	"fmt"
+	"sort"
+	"sync"
+	"time"
+
+	"github.com/libp2p/go-libp2p-core/peer"
+	pstore "github.com/libp2p/go-libp2p-core/peerstore"
+	"github.com/libp2p/go-libp2p-core/record"
+
+	logging "github.com/ipfs/go-log/v2"
+	ma "github.com/multiformats/go-multiaddr"
+)
+
+var log = logging.Logger("peerstore")
+
+type expiringAddr struct {
+	Addr    ma.Multiaddr
+	TTL     time.Duration
+	Expires time.Time
+}
+
+func (e *expiringAddr) ExpiredBy(t time.Time) bool {
+	return !t.Before(e.Expires)
+}
+
+type peerRecordState struct {
+	Envelope *record.Envelope
+	Seq      uint64
+}
+
+type addrSegments [256]*addrSegment
+
+type addrSegment struct {
+	sync.RWMutex
+
+	// Use pointers to save memory. Maps always leave some fraction of their
+	// space unused. storing the *values* directly in the map will
+	// drastically increase the space waste. In our case, by 6x.
+	addrs map[peer.ID]map[string]*expiringAddr
+
+	signedPeerRecords map[peer.ID]*peerRecordState
+}
+
+func (segments *addrSegments) get(p peer.ID) *addrSegment {
+	return segments[byte(p[len(p)-1])]
+}
+
+type clock interface {
+	Now() time.Time
+}
+
+type realclock struct{}
+
+func (rc realclock) Now() time.Time {
+	return time.Now()
+}
+
+// memoryAddrBook manages addresses.
+type memoryAddrBook struct {
+	segments addrSegments
+
+	refCount sync.WaitGroup
+	cancel   func()
+
+	subManager *AddrSubManager
+	clock      clock
+}
+
+var _ pstore.AddrBook = (*memoryAddrBook)(nil)
+var _ pstore.CertifiedAddrBook = (*memoryAddrBook)(nil)
+
+func NewAddrBook() *memoryAddrBook {
+	ctx, cancel := context.WithCancel(context.Background())
+
+	ab := &memoryAddrBook{
+		segments: func() (ret addrSegments) {
+			for i := range ret {
+				ret[i] = &addrSegment{
+					addrs:             make(map[peer.ID]map[string]*expiringAddr),
+					signedPeerRecords: make(map[peer.ID]*peerRecordState)}
+			}
+			return ret
+		}(),
+		subManager: NewAddrSubManager(),
+		cancel:     cancel,
+		clock:      realclock{},
+	}
+	ab.refCount.Add(1)
+	go ab.background(ctx)
+	return ab
+}
+
+type AddrBookOption func(book *memoryAddrBook) error
+
+func WithClock(clock clock) AddrBookOption {
+	return func(book *memoryAddrBook) error {
+		book.clock = clock
+		return nil
+	}
+}
+
+// background periodically schedules a gc
+func (mab *memoryAddrBook) background(ctx context.Context) {
+	defer mab.refCount.Done()
+	ticker := time.NewTicker(1 * time.Hour)
+	defer ticker.Stop()
+
+	for {
+		select {
+		case <-ticker.C:
+			mab.gc()
+		case <-ctx.Done():
+			return
+		}
+	}
+}
+
+func (mab *memoryAddrBook) Close() error {
+	mab.cancel()
+	mab.refCount.Wait()
+	return nil
+}
+
+// gc garbage collects the in-memory address book.
+func (mab *memoryAddrBook) gc() {
+	now := mab.clock.Now()
+	for _, s := range mab.segments {
+		s.Lock()
+		for p, amap := range s.addrs {
+			for k, addr := range amap {
+				if addr.ExpiredBy(now) {
+					delete(amap, k)
+				}
+			}
+			if len(amap) == 0 {
+				delete(s.addrs, p)
+				delete(s.signedPeerRecords, p)
+			}
+		}
+		s.Unlock()
+	}
+}
+
+func (mab *memoryAddrBook) PeersWithAddrs() peer.IDSlice {
+	// deduplicate, since the same peer could have both signed & unsigned addrs
+	set := make(map[peer.ID]struct{})
+	for _, s := range mab.segments {
+		s.RLock()
+		for pid, amap := range s.addrs {
+			if len(amap) > 0 {
+				set[pid] = struct{}{}
+			}
+		}
+		s.RUnlock()
+	}
+	peers := make(peer.IDSlice, 0, len(set))
+	for pid := range set {
+		peers = append(peers, pid)
+	}
+	return peers
+}
+
+// AddAddr calls AddAddrs(p, []ma.Multiaddr{addr}, ttl)
+func (mab *memoryAddrBook) AddAddr(p peer.ID, addr ma.Multiaddr, ttl time.Duration) {
+	mab.AddAddrs(p, []ma.Multiaddr{addr}, ttl)
+}
+
+// AddAddrs gives memoryAddrBook addresses to use, with a given ttl
+// (time-to-live), after which the address is no longer valid.
+// This function never reduces the TTL or expiration of an address.
+func (mab *memoryAddrBook) AddAddrs(p peer.ID, addrs []ma.Multiaddr, ttl time.Duration) {
+	// if we have a valid peer record, ignore unsigned addrs
+	// peerRec := mab.GetPeerRecord(p)
+	// if peerRec != nil {
+	// 	return
+	// }
+	mab.addAddrs(p, addrs, ttl)
+}
+
+// ConsumePeerRecord adds addresses from a signed peer.PeerRecord (contained in
+// a record.Envelope), which will expire after the given TTL.
+// See https://godoc.org/github.com/libp2p/go-libp2p-core/peerstore#CertifiedAddrBook for more details.
+func (mab *memoryAddrBook) ConsumePeerRecord(recordEnvelope *record.Envelope, ttl time.Duration) (bool, error) {
+	r, err := recordEnvelope.Record()
+	if err != nil {
+		return false, err
+	}
+	rec, ok := r.(*peer.PeerRecord)
+	if !ok {
+		return false, fmt.Errorf("unable to process envelope: not a PeerRecord")
+	}
+	if !rec.PeerID.MatchesPublicKey(recordEnvelope.PublicKey) {
+		return false, fmt.Errorf("signing key does not match PeerID in PeerRecord")
+	}
+
+	// ensure seq is greater than, or equal to, the last received
+	s := mab.segments.get(rec.PeerID)
+	s.Lock()
+	defer s.Unlock()
+	lastState, found := s.signedPeerRecords[rec.PeerID]
+	if found && lastState.Seq > rec.Seq {
+		return false, nil
+	}
+	s.signedPeerRecords[rec.PeerID] = &peerRecordState{
+		Envelope: recordEnvelope,
+		Seq:      rec.Seq,
+	}
+	mab.addAddrsUnlocked(s, rec.PeerID, rec.Addrs, ttl, true)
+	return true, nil
+}
+
+func (mab *memoryAddrBook) addAddrs(p peer.ID, addrs []ma.Multiaddr, ttl time.Duration) {
+	s := mab.segments.get(p)
+	s.Lock()
+	defer s.Unlock()
+
+	mab.addAddrsUnlocked(s, p, addrs, ttl, false)
+}
+
+func (mab *memoryAddrBook) addAddrsUnlocked(s *addrSegment, p peer.ID, addrs []ma.Multiaddr, ttl time.Duration, signed bool) {
+	// if ttl is zero, exit. nothing to do.
+	if ttl <= 0 {
+		return
+	}
+
+	amap, ok := s.addrs[p]
+	if !ok {
+		amap = make(map[string]*expiringAddr)
+		s.addrs[p] = amap
+	}
+
+	exp := mab.clock.Now().Add(ttl)
+	for _, addr := range addrs {
+		if addr == nil {
+			log.Warnw("was passed nil multiaddr", "peer", p)
+			continue
+		}
+
+		// find the highest TTL and Expiry time between
+		// existing records and function args
+		a, found := amap[string(addr.Bytes())] // won't allocate.
+		if !found {
+			// not found, announce it.
+			entry := &expiringAddr{Addr: addr, Expires: exp, TTL: ttl}
+			amap[string(addr.Bytes())] = entry
+			mab.subManager.BroadcastAddr(p, addr)
+		} else {
+			// update ttl & exp to whichever is greater between new and existing entry
+			if ttl > a.TTL {
+				a.TTL = ttl
+			}
+			if exp.After(a.Expires) {
+				a.Expires = exp
+			}
+		}
+	}
+}
+
+// SetAddr calls mgr.SetAddrs(p, addr, ttl)
+func (mab *memoryAddrBook) SetAddr(p peer.ID, addr ma.Multiaddr, ttl time.Duration) {
+	mab.SetAddrs(p, []ma.Multiaddr{addr}, ttl)
+}
+
+// SetAddrs sets the ttl on addresses. This clears any TTL there previously.
+// This is used when we receive the best estimate of the validity of an address.
+func (mab *memoryAddrBook) SetAddrs(p peer.ID, addrs []ma.Multiaddr, ttl time.Duration) {
+	s := mab.segments.get(p)
+	s.Lock()
+	defer s.Unlock()
+
+	amap, ok := s.addrs[p]
+	if !ok {
+		amap = make(map[string]*expiringAddr)
+		s.addrs[p] = amap
+	}
+
+	exp := mab.clock.Now().Add(ttl)
+	for _, addr := range addrs {
+		if addr == nil {
+			log.Warnw("was passed nil multiaddr", "peer", p)
+			continue
+		}
+		aBytes := addr.Bytes()
+		key := string(aBytes)
+
+		// re-set all of them for new ttl.
+		if ttl > 0 {
+			amap[key] = &expiringAddr{Addr: addr, Expires: exp, TTL: ttl}
+			mab.subManager.BroadcastAddr(p, addr)
+		} else {
+			delete(amap, key)
+		}
+	}
+}
+
+// UpdateAddrs updates the addresses associated with the given peer that have
+// the given oldTTL to have the given newTTL.
+func (mab *memoryAddrBook) UpdateAddrs(p peer.ID, oldTTL time.Duration, newTTL time.Duration) {
+	s := mab.segments.get(p)
+	s.Lock()
+	defer s.Unlock()
+	exp := mab.clock.Now().Add(newTTL)
+	amap, found := s.addrs[p]
+	if !found {
+		return
+	}
+
+	for k, a := range amap {
+		if oldTTL == a.TTL {
+			if newTTL == 0 {
+				delete(amap, k)
+			} else {
+				a.TTL = newTTL
+				a.Expires = exp
+				amap[k] = a
+			}
+		}
+	}
+}
+
+// Addrs returns all known (and valid) addresses for a given peer
+func (mab *memoryAddrBook) Addrs(p peer.ID) []ma.Multiaddr {
+	s := mab.segments.get(p)
+	s.RLock()
+	defer s.RUnlock()
+
+	return validAddrs(mab.clock.Now(), s.addrs[p])
+}
+
+func validAddrs(now time.Time, amap map[string]*expiringAddr) []ma.Multiaddr {
+	good := make([]ma.Multiaddr, 0, len(amap))
+	if amap == nil {
+		return good
+	}
+	for _, m := range amap {
+		if !m.ExpiredBy(now) {
+			good = append(good, m.Addr)
+		}
+	}
+
+	return good
+}
+
+// GetPeerRecord returns a Envelope containing a PeerRecord for the
+// given peer id, if one exists.
+// Returns nil if no signed PeerRecord exists for the peer.
+func (mab *memoryAddrBook) GetPeerRecord(p peer.ID) *record.Envelope {
+	s := mab.segments.get(p)
+	s.RLock()
+	defer s.RUnlock()
+
+	// although the signed record gets garbage collected when all addrs inside it are expired,
+	// we may be in between the expiration time and the GC interval
+	// so, we check to see if we have any valid signed addrs before returning the record
+	if len(validAddrs(mab.clock.Now(), s.addrs[p])) == 0 {
+		return nil
+	}
+
+	state := s.signedPeerRecords[p]
+	if state == nil {
+		return nil
+	}
+	return state.Envelope
+}
+
+// ClearAddrs removes all previously stored addresses
+func (mab *memoryAddrBook) ClearAddrs(p peer.ID) {
+	s := mab.segments.get(p)
+	s.Lock()
+	defer s.Unlock()
+
+	delete(s.addrs, p)
+	delete(s.signedPeerRecords, p)
+}
+
+// AddrStream returns a channel on which all new addresses discovered for a
+// given peer ID will be published.
+func (mab *memoryAddrBook) AddrStream(ctx context.Context, p peer.ID) <-chan ma.Multiaddr {
+	s := mab.segments.get(p)
+	s.RLock()
+	defer s.RUnlock()
+
+	baseaddrslice := s.addrs[p]
+	initial := make([]ma.Multiaddr, 0, len(baseaddrslice))
+	for _, a := range baseaddrslice {
+		initial = append(initial, a.Addr)
+	}
+
+	return mab.subManager.AddrStream(ctx, p, initial)
+}
+
+type addrSub struct {
+	pubch chan ma.Multiaddr
+	ctx   context.Context
+}
+
+func (s *addrSub) pubAddr(a ma.Multiaddr) {
+	select {
+	case s.pubch <- a:
+	case <-s.ctx.Done():
+	}
+}
+
+// An abstracted, pub-sub manager for address streams. Extracted from
+// memoryAddrBook in order to support additional implementations.
+type AddrSubManager struct {
+	mu   sync.RWMutex
+	subs map[peer.ID][]*addrSub
+}
+
+// NewAddrSubManager initializes an AddrSubManager.
+func NewAddrSubManager() *AddrSubManager {
+	return &AddrSubManager{
+		subs: make(map[peer.ID][]*addrSub),
+	}
+}
+
+// Used internally by the address stream coroutine to remove a subscription
+// from the manager.
+func (mgr *AddrSubManager) removeSub(p peer.ID, s *addrSub) {
+	mgr.mu.Lock()
+	defer mgr.mu.Unlock()
+
+	subs := mgr.subs[p]
+	if len(subs) == 1 {
+		if subs[0] != s {
+			return
+		}
+		delete(mgr.subs, p)
+		return
+	}
+
+	for i, v := range subs {
+		if v == s {
+			subs[i] = subs[len(subs)-1]
+			subs[len(subs)-1] = nil
+			mgr.subs[p] = subs[:len(subs)-1]
+			return
+		}
+	}
+}
+
+// BroadcastAddr broadcasts a new address to all subscribed streams.
+func (mgr *AddrSubManager) BroadcastAddr(p peer.ID, addr ma.Multiaddr) {
+	mgr.mu.RLock()
+	defer mgr.mu.RUnlock()
+
+	if subs, ok := mgr.subs[p]; ok {
+		for _, sub := range subs {
+			sub.pubAddr(addr)
+		}
+	}
+}
+
+// AddrStream creates a new subscription for a given peer ID, pre-populating the
+// channel with any addresses we might already have on file.
+func (mgr *AddrSubManager) AddrStream(ctx context.Context, p peer.ID, initial []ma.Multiaddr) <-chan ma.Multiaddr {
+	sub := &addrSub{pubch: make(chan ma.Multiaddr), ctx: ctx}
+	out := make(chan ma.Multiaddr)
+
+	mgr.mu.Lock()
+	mgr.subs[p] = append(mgr.subs[p], sub)
+	mgr.mu.Unlock()
+
+	sort.Sort(addrList(initial))
+
+	go func(buffer []ma.Multiaddr) {
+		defer close(out)
+
+		sent := make(map[string]struct{}, len(buffer))
+		for _, a := range buffer {
+			sent[string(a.Bytes())] = struct{}{}
+		}
+
+		var outch chan ma.Multiaddr
+		var next ma.Multiaddr
+		if len(buffer) > 0 {
+			next = buffer[0]
+			buffer = buffer[1:]
+			outch = out
+		}
+
+		for {
+			select {
+			case outch <- next:
+				if len(buffer) > 0 {
+					next = buffer[0]
+					buffer = buffer[1:]
+				} else {
+					outch = nil
+					next = nil
+				}
+			case naddr := <-sub.pubch:
+				if _, ok := sent[string(naddr.Bytes())]; ok {
+					continue
+				}
+				sent[string(naddr.Bytes())] = struct{}{}
+
+				if next == nil {
+					next = naddr
+					outch = out
+				} else {
+					buffer = append(buffer, naddr)
+				}
+			case <-ctx.Done():
+				mgr.removeSub(p, sub)
+				return
+			}
+		}
+	}(initial)
+
+	return out
+}
diff --git a/p2p/host/peerstore/pstoremem/keybook.go b/p2p/host/peerstore/pstoremem/keybook.go
new file mode 100644
index 00000000..387a5736
--- /dev/null
+++ b/p2p/host/peerstore/pstoremem/keybook.go
@@ -0,0 +1,98 @@
+package pstoremem
+
+import (
+	"errors"
+	"sync"
+
+	ic "github.com/libp2p/go-libp2p-core/crypto"
+	"github.com/libp2p/go-libp2p-core/peer"
+
+	pstore "github.com/libp2p/go-libp2p-core/peerstore"
+)
+
+type memoryKeyBook struct {
+	sync.RWMutex // same lock. wont happen a ton.
+	pks          map[peer.ID]ic.PubKey
+	sks          map[peer.ID]ic.PrivKey
+}
+
+var _ pstore.KeyBook = (*memoryKeyBook)(nil)
+
+func NewKeyBook() *memoryKeyBook {
+	return &memoryKeyBook{
+		pks: map[peer.ID]ic.PubKey{},
+		sks: map[peer.ID]ic.PrivKey{},
+	}
+}
+
+func (mkb *memoryKeyBook) PeersWithKeys() peer.IDSlice {
+	mkb.RLock()
+	ps := make(peer.IDSlice, 0, len(mkb.pks)+len(mkb.sks))
+	for p := range mkb.pks {
+		ps = append(ps, p)
+	}
+	for p := range mkb.sks {
+		if _, found := mkb.pks[p]; !found {
+			ps = append(ps, p)
+		}
+	}
+	mkb.RUnlock()
+	return ps
+}
+
+func (mkb *memoryKeyBook) PubKey(p peer.ID) ic.PubKey {
+	mkb.RLock()
+	pk := mkb.pks[p]
+	mkb.RUnlock()
+	if pk != nil {
+		return pk
+	}
+	pk, err := p.ExtractPublicKey()
+	if err == nil {
+		mkb.Lock()
+		mkb.pks[p] = pk
+		mkb.Unlock()
+	}
+	return pk
+}
+
+func (mkb *memoryKeyBook) AddPubKey(p peer.ID, pk ic.PubKey) error {
+	// check it's correct first
+	if !p.MatchesPublicKey(pk) {
+		return errors.New("ID does not match PublicKey")
+	}
+
+	mkb.Lock()
+	mkb.pks[p] = pk
+	mkb.Unlock()
+	return nil
+}
+
+func (mkb *memoryKeyBook) PrivKey(p peer.ID) ic.PrivKey {
+	mkb.RLock()
+	defer mkb.RUnlock()
+	return mkb.sks[p]
+}
+
+func (mkb *memoryKeyBook) AddPrivKey(p peer.ID, sk ic.PrivKey) error {
+	if sk == nil {
+		return errors.New("sk is nil (PrivKey)")
+	}
+
+	// check it's correct first
+	if !p.MatchesPrivateKey(sk) {
+		return errors.New("ID does not match PrivateKey")
+	}
+
+	mkb.Lock()
+	mkb.sks[p] = sk
+	mkb.Unlock()
+	return nil
+}
+
+func (mkb *memoryKeyBook) RemovePeer(p peer.ID) {
+	mkb.Lock()
+	delete(mkb.sks, p)
+	delete(mkb.pks, p)
+	mkb.Unlock()
+}
diff --git a/p2p/host/peerstore/pstoremem/metadata.go b/p2p/host/peerstore/pstoremem/metadata.go
new file mode 100644
index 00000000..0fd41c07
--- /dev/null
+++ b/p2p/host/peerstore/pstoremem/metadata.go
@@ -0,0 +1,54 @@
+package pstoremem
+
+import (
+	"sync"
+
+	"github.com/libp2p/go-libp2p-core/peer"
+	pstore "github.com/libp2p/go-libp2p-core/peerstore"
+)
+
+type memoryPeerMetadata struct {
+	// store other data, like versions
+	ds     map[peer.ID]map[string]interface{}
+	dslock sync.RWMutex
+}
+
+var _ pstore.PeerMetadata = (*memoryPeerMetadata)(nil)
+
+func NewPeerMetadata() *memoryPeerMetadata {
+	return &memoryPeerMetadata{
+		ds: make(map[peer.ID]map[string]interface{}),
+	}
+}
+
+func (ps *memoryPeerMetadata) Put(p peer.ID, key string, val interface{}) error {
+	ps.dslock.Lock()
+	defer ps.dslock.Unlock()
+	m, ok := ps.ds[p]
+	if !ok {
+		m = make(map[string]interface{})
+		ps.ds[p] = m
+	}
+	m[key] = val
+	return nil
+}
+
+func (ps *memoryPeerMetadata) Get(p peer.ID, key string) (interface{}, error) {
+	ps.dslock.RLock()
+	defer ps.dslock.RUnlock()
+	m, ok := ps.ds[p]
+	if !ok {
+		return nil, pstore.ErrNotFound
+	}
+	val, ok := m[key]
+	if !ok {
+		return nil, pstore.ErrNotFound
+	}
+	return val, nil
+}
+
+func (ps *memoryPeerMetadata) RemovePeer(p peer.ID) {
+	ps.dslock.Lock()
+	delete(ps.ds, p)
+	ps.dslock.Unlock()
+}
diff --git a/p2p/host/peerstore/pstoremem/peerstore.go b/p2p/host/peerstore/pstoremem/peerstore.go
new file mode 100644
index 00000000..7c0d18b9
--- /dev/null
+++ b/p2p/host/peerstore/pstoremem/peerstore.go
@@ -0,0 +1,115 @@
+package pstoremem
+
+import (
+	"fmt"
+	"io"
+
+	pstore "github.com/libp2p/go-libp2p/p2p/host/peerstore"
+
+	"github.com/libp2p/go-libp2p-core/peer"
+	"github.com/libp2p/go-libp2p-core/peerstore"
+)
+
+type pstoremem struct {
+	peerstore.Metrics
+
+	*memoryKeyBook
+	*memoryAddrBook
+	*memoryProtoBook
+	*memoryPeerMetadata
+}
+
+var _ peerstore.Peerstore = &pstoremem{}
+
+type Option interface{}
+
+// NewPeerstore creates an in-memory threadsafe collection of peers.
+// It's the caller's responsibility to call RemovePeer to ensure
+// that memory consumption of the peerstore doesn't grow unboundedly.
+func NewPeerstore(opts ...Option) (ps *pstoremem, err error) {
+	ab := NewAddrBook()
+	defer func() {
+		if err != nil {
+			ab.Close()
+		}
+	}()
+
+	var protoBookOpts []ProtoBookOption
+	for _, opt := range opts {
+		switch o := opt.(type) {
+		case ProtoBookOption:
+			protoBookOpts = append(protoBookOpts, o)
+		case AddrBookOption:
+			o(ab)
+		default:
+			return nil, fmt.Errorf("unexpected peer store option: %v", o)
+		}
+	}
+	pb, err := NewProtoBook(protoBookOpts...)
+	if err != nil {
+		return nil, err
+	}
+	return &pstoremem{
+		Metrics:            pstore.NewMetrics(),
+		memoryKeyBook:      NewKeyBook(),
+		memoryAddrBook:     ab,
+		memoryProtoBook:    pb,
+		memoryPeerMetadata: NewPeerMetadata(),
+	}, nil
+}
+
+func (ps *pstoremem) Close() (err error) {
+	var errs []error
+	weakClose := func(name string, c interface{}) {
+		if cl, ok := c.(io.Closer); ok {
+			if err = cl.Close(); err != nil {
+				errs = append(errs, fmt.Errorf("%s error: %s", name, err))
+			}
+		}
+	}
+	weakClose("keybook", ps.memoryKeyBook)
+	weakClose("addressbook", ps.memoryAddrBook)
+	weakClose("protobook", ps.memoryProtoBook)
+	weakClose("peermetadata", ps.memoryPeerMetadata)
+
+	if len(errs) > 0 {
+		return fmt.Errorf("failed while closing peerstore; err(s): %q", errs)
+	}
+	return nil
+}
+
+func (ps *pstoremem) Peers() peer.IDSlice {
+	set := map[peer.ID]struct{}{}
+	for _, p := range ps.PeersWithKeys() {
+		set[p] = struct{}{}
+	}
+	for _, p := range ps.PeersWithAddrs() {
+		set[p] = struct{}{}
+	}
+
+	pps := make(peer.IDSlice, 0, len(set))
+	for p := range set {
+		pps = append(pps, p)
+	}
+	return pps
+}
+
+func (ps *pstoremem) PeerInfo(p peer.ID) peer.AddrInfo {
+	return peer.AddrInfo{
+		ID:    p,
+		Addrs: ps.memoryAddrBook.Addrs(p),
+	}
+}
+
+// RemovePeer removes entries associated with a peer from:
+// * the KeyBook
+// * the ProtoBook
+// * the PeerMetadata
+// * the Metrics
+// It DOES NOT remove the peer from the AddrBook.
+func (ps *pstoremem) RemovePeer(p peer.ID) {
+	ps.memoryKeyBook.RemovePeer(p)
+	ps.memoryProtoBook.RemovePeer(p)
+	ps.memoryPeerMetadata.RemovePeer(p)
+	ps.Metrics.RemovePeer(p)
+}
diff --git a/p2p/host/peerstore/pstoremem/protobook.go b/p2p/host/peerstore/pstoremem/protobook.go
new file mode 100644
index 00000000..b2cf73e1
--- /dev/null
+++ b/p2p/host/peerstore/pstoremem/protobook.go
@@ -0,0 +1,192 @@
+package pstoremem
+
+import (
+	"errors"
+	"sync"
+
+	"github.com/libp2p/go-libp2p-core/peer"
+
+	pstore "github.com/libp2p/go-libp2p-core/peerstore"
+)
+
+type protoSegment struct {
+	sync.RWMutex
+	protocols map[peer.ID]map[string]struct{}
+}
+
+type protoSegments [256]*protoSegment
+
+func (s *protoSegments) get(p peer.ID) *protoSegment {
+	return s[byte(p[len(p)-1])]
+}
+
+var errTooManyProtocols = errors.New("too many protocols")
+
+type memoryProtoBook struct {
+	segments protoSegments
+
+	maxProtos int
+
+	lk       sync.RWMutex
+	interned map[string]string
+}
+
+var _ pstore.ProtoBook = (*memoryProtoBook)(nil)
+
+type ProtoBookOption func(book *memoryProtoBook) error
+
+func WithMaxProtocols(num int) ProtoBookOption {
+	return func(pb *memoryProtoBook) error {
+		pb.maxProtos = num
+		return nil
+	}
+}
+
+func NewProtoBook(opts ...ProtoBookOption) (*memoryProtoBook, error) {
+	pb := &memoryProtoBook{
+		interned: make(map[string]string, 256),
+		segments: func() (ret protoSegments) {
+			for i := range ret {
+				ret[i] = &protoSegment{
+					protocols: make(map[peer.ID]map[string]struct{}),
+				}
+			}
+			return ret
+		}(),
+		maxProtos: 1024,
+	}
+
+	for _, opt := range opts {
+		if err := opt(pb); err != nil {
+			return nil, err
+		}
+	}
+	return pb, nil
+}
+
+func (pb *memoryProtoBook) internProtocol(proto string) string {
+	// check if it is interned with the read lock
+	pb.lk.RLock()
+	interned, ok := pb.interned[proto]
+	pb.lk.RUnlock()
+
+	if ok {
+		return interned
+	}
+
+	// intern with the write lock
+	pb.lk.Lock()
+	defer pb.lk.Unlock()
+
+	// check again in case it got interned in between locks
+	interned, ok = pb.interned[proto]
+	if ok {
+		return interned
+	}
+
+	pb.interned[proto] = proto
+	return proto
+}
+
+func (pb *memoryProtoBook) SetProtocols(p peer.ID, protos ...string) error {
+	if len(protos) > pb.maxProtos {
+		return errTooManyProtocols
+	}
+
+	newprotos := make(map[string]struct{}, len(protos))
+	for _, proto := range protos {
+		newprotos[pb.internProtocol(proto)] = struct{}{}
+	}
+
+	s := pb.segments.get(p)
+	s.Lock()
+	s.protocols[p] = newprotos
+	s.Unlock()
+
+	return nil
+}
+
+func (pb *memoryProtoBook) AddProtocols(p peer.ID, protos ...string) error {
+	s := pb.segments.get(p)
+	s.Lock()
+	defer s.Unlock()
+
+	protomap, ok := s.protocols[p]
+	if !ok {
+		protomap = make(map[string]struct{})
+		s.protocols[p] = protomap
+	}
+	if len(protomap)+len(protos) > pb.maxProtos {
+		return errTooManyProtocols
+	}
+
+	for _, proto := range protos {
+		protomap[pb.internProtocol(proto)] = struct{}{}
+	}
+	return nil
+}
+
+func (pb *memoryProtoBook) GetProtocols(p peer.ID) ([]string, error) {
+	s := pb.segments.get(p)
+	s.RLock()
+	defer s.RUnlock()
+
+	out := make([]string, 0, len(s.protocols[p]))
+	for k := range s.protocols[p] {
+		out = append(out, k)
+	}
+
+	return out, nil
+}
+
+func (pb *memoryProtoBook) RemoveProtocols(p peer.ID, protos ...string) error {
+	s := pb.segments.get(p)
+	s.Lock()
+	defer s.Unlock()
+
+	protomap, ok := s.protocols[p]
+	if !ok {
+		// nothing to remove.
+		return nil
+	}
+
+	for _, proto := range protos {
+		delete(protomap, pb.internProtocol(proto))
+	}
+	return nil
+}
+
+func (pb *memoryProtoBook) SupportsProtocols(p peer.ID, protos ...string) ([]string, error) {
+	s := pb.segments.get(p)
+	s.RLock()
+	defer s.RUnlock()
+
+	out := make([]string, 0, len(protos))
+	for _, proto := range protos {
+		if _, ok := s.protocols[p][proto]; ok {
+			out = append(out, proto)
+		}
+	}
+
+	return out, nil
+}
+
+func (pb *memoryProtoBook) FirstSupportedProtocol(p peer.ID, protos ...string) (string, error) {
+	s := pb.segments.get(p)
+	s.RLock()
+	defer s.RUnlock()
+
+	for _, proto := range protos {
+		if _, ok := s.protocols[p][proto]; ok {
+			return proto, nil
+		}
+	}
+	return "", nil
+}
+
+func (pb *memoryProtoBook) RemovePeer(p peer.ID) {
+	s := pb.segments.get(p)
+	s.Lock()
+	delete(s.protocols, p)
+	s.Unlock()
+}
diff --git a/p2p/host/peerstore/pstoremem/sorting.go b/p2p/host/peerstore/pstoremem/sorting.go
new file mode 100644
index 00000000..f36ac41b
--- /dev/null
+++ b/p2p/host/peerstore/pstoremem/sorting.go
@@ -0,0 +1,50 @@
+package pstoremem
+
+import (
+	"bytes"
+
+	ma "github.com/multiformats/go-multiaddr"
+	mafmt "github.com/multiformats/go-multiaddr-fmt"
+	manet "github.com/multiformats/go-multiaddr/net"
+)
+
+func isFDCostlyTransport(a ma.Multiaddr) bool {
+	return mafmt.TCP.Matches(a)
+}
+
+type addrList []ma.Multiaddr
+
+func (al addrList) Len() int      { return len(al) }
+func (al addrList) Swap(i, j int) { al[i], al[j] = al[j], al[i] }
+
+func (al addrList) Less(i, j int) bool {
+	a := al[i]
+	b := al[j]
+
+	// dial localhost addresses next, they should fail immediately
+	lba := manet.IsIPLoopback(a)
+	lbb := manet.IsIPLoopback(b)
+	if lba && !lbb {
+		return true
+	}
+
+	// dial utp and similar 'non-fd-consuming' addresses first
+	fda := isFDCostlyTransport(a)
+	fdb := isFDCostlyTransport(b)
+	if !fda {
+		return fdb
+	}
+
+	// if 'b' doesnt take a file descriptor
+	if !fdb {
+		return false
+	}
+
+	// if 'b' is loopback and both take file descriptors
+	if lbb {
+		return false
+	}
+
+	// for the rest, just sort by bytes
+	return bytes.Compare(a.Bytes(), b.Bytes()) > 0
+}
diff --git a/p2p/net/mock/mock_net.go b/p2p/net/mock/mock_net.go
index 54556679..9ec54d54 100644
--- a/p2p/net/mock/mock_net.go
+++ b/p2p/net/mock/mock_net.go
@@ -15,8 +15,8 @@ import (
 	"github.com/libp2p/go-libp2p-core/peerstore"
 
 	bhost "github.com/libp2p/go-libp2p/p2p/host/basic"
+	"github.com/libp2p/go-libp2p/p2p/host/peerstore/pstoremem"
 
-	"github.com/libp2p/go-libp2p-peerstore/pstoremem"
 	ma "github.com/multiformats/go-multiaddr"
 )
 


Test patch:
diff --git a/p2p/host/peerstore/metrics_test.go b/p2p/host/peerstore/metrics_test.go
new file mode 100644
index 00000000..723baad2
--- /dev/null
+++ b/p2p/host/peerstore/metrics_test.go
@@ -0,0 +1,63 @@
+package peerstore
+
+import (
+	"fmt"
+	"math/rand"
+	"testing"
+	"time"
+
+	"github.com/libp2p/go-libp2p-core/test"
+)
+
+func TestLatencyEWMAFun(t *testing.T) {
+	t.Skip("run it for fun")
+
+	m := NewMetrics()
+	id, err := test.RandPeerID()
+	if err != nil {
+		t.Fatal(err)
+	}
+
+	mu := 100.0
+	sig := 10.0
+	next := func() time.Duration {
+		mu = (rand.NormFloat64() * sig) + mu
+		return time.Duration(mu)
+	}
+
+	print := func() {
+		fmt.Printf("%3.f %3.f --> %d\n", sig, mu, m.LatencyEWMA(id))
+	}
+
+	for {
+		time.Sleep(200 * time.Millisecond)
+		m.RecordLatency(id, next())
+		print()
+	}
+}
+
+func TestLatencyEWMA(t *testing.T) {
+	m := NewMetrics()
+	id, err := test.RandPeerID()
+	if err != nil {
+		t.Fatal(err)
+	}
+
+	const exp = 100
+	const mu = exp
+	const sig = 10
+	next := func() time.Duration { return time.Duration(rand.Intn(20) - 10 + mu) }
+
+	for i := 0; i < 10; i++ {
+		m.RecordLatency(id, next())
+	}
+
+	lat := m.LatencyEWMA(id)
+	diff := exp - lat
+	if diff < 0 {
+		diff = -diff
+	}
+	if diff > sig {
+		t.Fatalf("latency outside of expected range. expected %d ± %d, got %d", exp, sig, lat)
+	}
+}
diff --git a/p2p/host/peerstore/pb/pstorepb_test.go b/p2p/host/peerstore/pb/pstorepb_test.go
new file mode 100644
index 00000000..12d29806
--- /dev/null
+++ b/p2p/host/peerstore/pb/pstorepb_test.go
@@ -0,0 +1,183 @@
+// Code generated by protoc-gen-gogo. DO NOT EDIT.
+// source: pstore.proto
+
+package pstore_pb
+
+import (
+	fmt "fmt"
+	_ "github.com/gogo/protobuf/gogoproto"
+	github_com_gogo_protobuf_proto "github.com/gogo/protobuf/proto"
+	proto "github.com/gogo/protobuf/proto"
+	math "math"
+	math_rand "math/rand"
+	testing "testing"
+)
+
+// Reference imports to suppress errors if they are not otherwise used.
+var _ = proto.Marshal
+var _ = fmt.Errorf
+var _ = math.Inf
+
+func BenchmarkAddrBookRecordProtoMarshal(b *testing.B) {
+	popr := math_rand.New(math_rand.NewSource(616))
+	total := 0
+	pops := make([]*AddrBookRecord, 10000)
+	for i := 0; i < 10000; i++ {
+		pops[i] = NewPopulatedAddrBookRecord(popr, false)
+	}
+	b.ResetTimer()
+	for i := 0; i < b.N; i++ {
+		dAtA, err := github_com_gogo_protobuf_proto.Marshal(pops[i%10000])
+		if err != nil {
+			panic(err)
+		}
+		total += len(dAtA)
+	}
+	b.SetBytes(int64(total / b.N))
+}
+
+func BenchmarkAddrBookRecordProtoUnmarshal(b *testing.B) {
+	popr := math_rand.New(math_rand.NewSource(616))
+	total := 0
+	datas := make([][]byte, 10000)
+	for i := 0; i < 10000; i++ {
+		dAtA, err := github_com_gogo_protobuf_proto.Marshal(NewPopulatedAddrBookRecord(popr, false))
+		if err != nil {
+			panic(err)
+		}
+		datas[i] = dAtA
+	}
+	msg := &AddrBookRecord{}
+	b.ResetTimer()
+	for i := 0; i < b.N; i++ {
+		total += len(datas[i%10000])
+		if err := github_com_gogo_protobuf_proto.Unmarshal(datas[i%10000], msg); err != nil {
+			panic(err)
+		}
+	}
+	b.SetBytes(int64(total / b.N))
+}
+
+func BenchmarkAddrBookRecord_AddrEntryProtoMarshal(b *testing.B) {
+	popr := math_rand.New(math_rand.NewSource(616))
+	total := 0
+	pops := make([]*AddrBookRecord_AddrEntry, 10000)
+	for i := 0; i < 10000; i++ {
+		pops[i] = NewPopulatedAddrBookRecord_AddrEntry(popr, false)
+	}
+	b.ResetTimer()
+	for i := 0; i < b.N; i++ {
+		dAtA, err := github_com_gogo_protobuf_proto.Marshal(pops[i%10000])
+		if err != nil {
+			panic(err)
+		}
+		total += len(dAtA)
+	}
+	b.SetBytes(int64(total / b.N))
+}
+
+func BenchmarkAddrBookRecord_AddrEntryProtoUnmarshal(b *testing.B) {
+	popr := math_rand.New(math_rand.NewSource(616))
+	total := 0
+	datas := make([][]byte, 10000)
+	for i := 0; i < 10000; i++ {
+		dAtA, err := github_com_gogo_protobuf_proto.Marshal(NewPopulatedAddrBookRecord_AddrEntry(popr, false))
+		if err != nil {
+			panic(err)
+		}
+		datas[i] = dAtA
+	}
+	msg := &AddrBookRecord_AddrEntry{}
+	b.ResetTimer()
+	for i := 0; i < b.N; i++ {
+		total += len(datas[i%10000])
+		if err := github_com_gogo_protobuf_proto.Unmarshal(datas[i%10000], msg); err != nil {
+			panic(err)
+		}
+	}
+	b.SetBytes(int64(total / b.N))
+}
+
+func BenchmarkAddrBookRecord_CertifiedRecordProtoMarshal(b *testing.B) {
+	popr := math_rand.New(math_rand.NewSource(616))
+	total := 0
+	pops := make([]*AddrBookRecord_CertifiedRecord, 10000)
+	for i := 0; i < 10000; i++ {
+		pops[i] = NewPopulatedAddrBookRecord_CertifiedRecord(popr, false)
+	}
+	b.ResetTimer()
+	for i := 0; i < b.N; i++ {
+		dAtA, err := github_com_gogo_protobuf_proto.Marshal(pops[i%10000])
+		if err != nil {
+			panic(err)
+		}
+		total += len(dAtA)
+	}
+	b.SetBytes(int64(total / b.N))
+}
+
+func BenchmarkAddrBookRecord_CertifiedRecordProtoUnmarshal(b *testing.B) {
+	popr := math_rand.New(math_rand.NewSource(616))
+	total := 0
+	datas := make([][]byte, 10000)
+	for i := 0; i < 10000; i++ {
+		dAtA, err := github_com_gogo_protobuf_proto.Marshal(NewPopulatedAddrBookRecord_CertifiedRecord(popr, false))
+		if err != nil {
+			panic(err)
+		}
+		datas[i] = dAtA
+	}
+	msg := &AddrBookRecord_CertifiedRecord{}
+	b.ResetTimer()
+	for i := 0; i < b.N; i++ {
+		total += len(datas[i%10000])
+		if err := github_com_gogo_protobuf_proto.Unmarshal(datas[i%10000], msg); err != nil {
+			panic(err)
+		}
+	}
+	b.SetBytes(int64(total / b.N))
+}
+
+func BenchmarkAddrBookRecordSize(b *testing.B) {
+	popr := math_rand.New(math_rand.NewSource(616))
+	total := 0
+	pops := make([]*AddrBookRecord, 1000)
+	for i := 0; i < 1000; i++ {
+		pops[i] = NewPopulatedAddrBookRecord(popr, false)
+	}
+	b.ResetTimer()
+	for i := 0; i < b.N; i++ {
+		total += pops[i%1000].Size()
+	}
+	b.SetBytes(int64(total / b.N))
+}
+
+func BenchmarkAddrBookRecord_AddrEntrySize(b *testing.B) {
+	popr := math_rand.New(math_rand.NewSource(616))
+	total := 0
+	pops := make([]*AddrBookRecord_AddrEntry, 1000)
+	for i := 0; i < 1000; i++ {
+		pops[i] = NewPopulatedAddrBookRecord_AddrEntry(popr, false)
+	}
+	b.ResetTimer()
+	for i := 0; i < b.N; i++ {
+		total += pops[i%1000].Size()
+	}
+	b.SetBytes(int64(total / b.N))
+}
+
+func BenchmarkAddrBookRecord_CertifiedRecordSize(b *testing.B) {
+	popr := math_rand.New(math_rand.NewSource(616))
+	total := 0
+	pops := make([]*AddrBookRecord_CertifiedRecord, 1000)
+	for i := 0; i < 1000; i++ {
+		pops[i] = NewPopulatedAddrBookRecord_CertifiedRecord(popr, false)
+	}
+	b.ResetTimer()
+	for i := 0; i < b.N; i++ {
+		total += pops[i%1000].Size()
+	}
+	b.SetBytes(int64(total / b.N))
+}
+
+//These tests are generated by github.com/gogo/protobuf/plugin/testgen
diff --git a/p2p/host/peerstore/pstoreds/addr_book_gc_test.go b/p2p/host/peerstore/pstoreds/addr_book_gc_test.go
new file mode 100644
index 00000000..3a2cab0b
--- /dev/null
+++ b/p2p/host/peerstore/pstoreds/addr_book_gc_test.go
@@ -0,0 +1,265 @@
+package pstoreds
+
+import (
+	"context"
+	"testing"
+	"time"
+
+	"github.com/libp2p/go-libp2p/p2p/host/peerstore/test"
+
+	pstore "github.com/libp2p/go-libp2p-core/peerstore"
+
+	mockClock "github.com/benbjohnson/clock"
+	"github.com/ipfs/go-datastore/query"
+	ma "github.com/multiformats/go-multiaddr"
+	"github.com/stretchr/testify/require"
+)
+
+var lookaheadQuery = query.Query{Prefix: gcLookaheadBase.String(), KeysOnly: true}
+
+type testProbe struct {
+	t  *testing.T
+	ab pstore.AddrBook
+}
+
+func (tp *testProbe) countLookaheadEntries() (i int) {
+	results, err := tp.ab.(*dsAddrBook).ds.Query(context.Background(), lookaheadQuery)
+	if err != nil {
+		tp.t.Fatal(err)
+	}
+
+	defer results.Close()
+	for range results.Next() {
+		i++
+	}
+	return i
+}
+
+func (tp *testProbe) clearCache() {
+	for _, k := range tp.ab.(*dsAddrBook).cache.Keys() {
+		tp.ab.(*dsAddrBook).cache.Remove(k)
+	}
+}
+
+func TestGCLookahead(t *testing.T) {
+	opts := DefaultOpts()
+
+	// effectively disable automatic GC for this test.
+	opts.GCInitialDelay = 90 * time.Hour
+	opts.GCLookaheadInterval = 10 * time.Second
+	opts.GCPurgeInterval = 1 * time.Second
+
+	factory := addressBookFactory(t, leveldbStore, opts)
+	ab, closeFn := factory()
+	gc := ab.(*dsAddrBook).gc
+	defer closeFn()
+
+	tp := &testProbe{t, ab}
+
+	ids := test.GeneratePeerIDs(10)
+	addrs := test.GenerateAddrs(100)
+
+	// lookahead is 10 seconds, so these entries will be outside the lookahead window.
+	ab.AddAddrs(ids[0], addrs[:10], time.Hour)
+	ab.AddAddrs(ids[1], addrs[10:20], time.Hour)
+	ab.AddAddrs(ids[2], addrs[20:30], time.Hour)
+
+	gc.populateLookahead()
+	if i := tp.countLookaheadEntries(); i != 0 {
+		t.Errorf("expected no GC lookahead entries, got: %v", i)
+	}
+
+	// change addresses of a peer to have TTL 1 second, placing them in the lookahead window.
+	ab.UpdateAddrs(ids[1], time.Hour, time.Second)
+
+	// Purge the cache, to exercise a different path in the lookahead cycle.
+	tp.clearCache()
+
+	gc.populateLookahead()
+	if i := tp.countLookaheadEntries(); i != 1 {
+		t.Errorf("expected 1 GC lookahead entry, got: %v", i)
+	}
+
+	// change addresses of another to have TTL 5 second, placing them in the lookahead window.
+	ab.UpdateAddrs(ids[2], time.Hour, 5*time.Second)
+	gc.populateLookahead()
+	if i := tp.countLookaheadEntries(); i != 2 {
+		t.Errorf("expected 2 GC lookahead entries, got: %v", i)
+	}
+}
+
+func TestGCPurging(t *testing.T) {
+	opts := DefaultOpts()
+
+	// effectively disable automatic GC for this test.
+	opts.GCInitialDelay = 90 * time.Hour
+	opts.GCLookaheadInterval = 20 * time.Second
+	opts.GCPurgeInterval = 1 * time.Second
+	clk := mockClock.NewMock()
+	opts.Clock = clk
+
+	factory := addressBookFactory(t, leveldbStore, opts)
+	ab, closeFn := factory()
+	gc := ab.(*dsAddrBook).gc
+	defer closeFn()
+
+	tp := &testProbe{t, ab}
+
+	ids := test.GeneratePeerIDs(10)
+	addrs := test.GenerateAddrs(100)
+
+	// stagger addresses within the lookahead window, but stagger them.
+	ab.AddAddrs(ids[0], addrs[:10], 1*time.Second)
+	ab.AddAddrs(ids[1], addrs[30:40], 1*time.Second)
+	ab.AddAddrs(ids[2], addrs[60:70], 1*time.Second)
+
+	ab.AddAddrs(ids[0], addrs[10:20], 4*time.Second)
+	ab.AddAddrs(ids[1], addrs[40:50], 4*time.Second)
+
+	ab.AddAddrs(ids[0], addrs[20:30], 10*time.Second)
+	ab.AddAddrs(ids[1], addrs[50:60], 10*time.Second)
+
+	// this is inside the window, but it will survive the purges we do in the test.
+	ab.AddAddrs(ids[3], addrs[70:80], 15*time.Second)
+
+	gc.populateLookahead()
+	if i := tp.countLookaheadEntries(); i != 4 {
+		t.Errorf("expected 4 GC lookahead entries, got: %v", i)
+	}
+
+	clk.Add(2 * time.Second)
+	gc.purgeLookahead()
+	if i := tp.countLookaheadEntries(); i != 3 {
+		t.Errorf("expected 3 GC lookahead entries, got: %v", i)
+	}
+
+	// Purge the cache, to exercise a different path in the purge cycle.
+	tp.clearCache()
+
+	clk.Add(5 * time.Second)
+	gc.purgeLookahead()
+	if i := tp.countLookaheadEntries(); i != 3 {
+		t.Errorf("expected 3 GC lookahead entries, got: %v", i)
+	}
+
+	clk.Add(5 * time.Second)
+	gc.purgeLookahead()
+	if i := tp.countLookaheadEntries(); i != 1 {
+		t.Errorf("expected 1 GC lookahead entries, got: %v", i)
+	}
+	if i := len(ab.PeersWithAddrs()); i != 1 {
+		t.Errorf("expected 1 entries in database, got: %v", i)
+	}
+	if p := ab.PeersWithAddrs()[0]; p != ids[3] {
+		t.Errorf("expected remaining peer to be #3, got: %v, expected: %v", p, ids[3])
+	}
+}
+
+func TestGCDelay(t *testing.T) {
+	ids := test.GeneratePeerIDs(10)
+	addrs := test.GenerateAddrs(100)
+
+	clk := mockClock.NewMock()
+	opts := DefaultOpts()
+	opts.GCInitialDelay = 2 * time.Second
+	opts.GCLookaheadInterval = 1 * time.Minute
+	opts.GCPurgeInterval = 30 * time.Second
+	opts.Clock = clk
+
+	factory := addressBookFactory(t, leveldbStore, opts)
+	ab, closeFn := factory()
+	defer closeFn()
+	// give the background Go routine some time to start
+	time.Sleep(100 * time.Millisecond)
+
+	tp := &testProbe{t, ab}
+
+	ab.AddAddrs(ids[0], addrs, 1*time.Second)
+
+	// immediately after we should be having no lookahead entries.
+	if i := tp.countLookaheadEntries(); i != 0 {
+		t.Fatalf("expected no lookahead entries, got: %d", i)
+	}
+
+	// after the initial delay has passed.
+	clk.Add(3 * time.Second)
+	require.Eventually(t, func() bool { return tp.countLookaheadEntries() == 1 }, 3000*time.Millisecond, 10*time.Millisecond, "expected 1 lookahead entry")
+}
+
+func TestGCLookaheadDisabled(t *testing.T) {
+	ids := test.GeneratePeerIDs(10)
+	addrs := test.GenerateAddrs(100)
+
+	opts := DefaultOpts()
+
+	// effectively disable automatic GC for this test.
+	opts.GCInitialDelay = 90 * time.Hour
+	opts.GCLookaheadInterval = 0 // disable lookahead
+	opts.GCPurgeInterval = 9 * time.Hour
+	clk := mockClock.NewMock()
+	opts.Clock = clk
+
+	factory := addressBookFactory(t, leveldbStore, opts)
+	ab, closeFn := factory()
+	defer closeFn()
+
+	tp := &testProbe{t, ab}
+
+	// four peers:
+	//   ids[0] has 10 addresses, all of which expire in 500ms.
+	//   ids[1] has 20 addresses; 50% expire in 500ms and 50% in 10 hours.
+	//   ids[2] has 10 addresses; all expire in 10 hours.
+	//   ids[3] has 60 addresses; all expire in 10 hours.
+	ab.AddAddrs(ids[0], addrs[:10], 500*time.Millisecond)
+	ab.AddAddrs(ids[1], addrs[10:20], 500*time.Millisecond)
+	ab.AddAddrs(ids[1], addrs[20:30], 10*time.Hour)
+	ab.AddAddrs(ids[2], addrs[30:40], 10*time.Hour)
+	ab.AddAddrs(ids[3], addrs[40:], 10*time.Hour)
+
+	clk.Add(100 * time.Millisecond)
+
+	if i := tp.countLookaheadEntries(); i != 0 {
+		t.Errorf("expected no GC lookahead entries, got: %v", i)
+	}
+
+	clk.Add(500 * time.Millisecond)
+	gc := ab.(*dsAddrBook).gc
+	gc.purgeFunc()
+
+	var empty []ma.Multiaddr
+	test.AssertAddressesEqual(t, empty, ab.Addrs(ids[0]))
+	test.AssertAddressesEqual(t, addrs[20:30], ab.Addrs(ids[1]))
+	test.AssertAddressesEqual(t, addrs[30:40], ab.Addrs(ids[2]))
+	test.AssertAddressesEqual(t, addrs[40:], ab.Addrs(ids[3]))
+}
+
+func BenchmarkLookaheadCycle(b *testing.B) {
+	ids := test.GeneratePeerIDs(100)
+	addrs := test.GenerateAddrs(100)
+
+	opts := DefaultOpts()
+
+	opts.GCInitialDelay = 2 * time.Hour
+	opts.GCLookaheadInterval = 2 * time.Hour
+	opts.GCPurgeInterval = 6 * time.Hour
+
+	factory := addressBookFactory(b, leveldbStore, opts)
+	ab, closeFn := factory()
+	defer closeFn()
+
+	inside, outside := 1*time.Minute, 48*time.Hour
+	for i, id := range ids {
+		var ttl time.Duration
+		if i%2 == 0 {
+			ttl = inside
+		} else {
+			ttl = outside
+		}
+		ab.AddAddrs(id, addrs, ttl)
+	}
+
+	b.ResetTimer()
+	for i := 0; i < b.N; i++ {
+		ab.(*dsAddrBook).gc.populateLookahead()
+	}
+}
diff --git a/p2p/host/peerstore/pstoreds/ds_test.go b/p2p/host/peerstore/pstoreds/ds_test.go
new file mode 100644
index 00000000..cc1a8ec5
--- /dev/null
+++ b/p2p/host/peerstore/pstoreds/ds_test.go
@@ -0,0 +1,175 @@
+package pstoreds
+
+import (
+	"context"
+	"io/ioutil"
+	"os"
+	"testing"
+	"time"
+
+	pt "github.com/libp2p/go-libp2p/p2p/host/peerstore/test"
+
+	pstore "github.com/libp2p/go-libp2p-core/peerstore"
+
+	mockClock "github.com/benbjohnson/clock"
+	ds "github.com/ipfs/go-datastore"
+	badger "github.com/ipfs/go-ds-badger"
+	leveldb "github.com/ipfs/go-ds-leveldb"
+	"github.com/stretchr/testify/require"
+)
+
+type datastoreFactory func(tb testing.TB) (ds.Batching, func())
+
+var dstores = map[string]datastoreFactory{
+	// "Badger": badgerStore,
+	"Leveldb": leveldbStore,
+}
+
+func TestDsPeerstore(t *testing.T) {
+	for name, dsFactory := range dstores {
+		t.Run(name, func(t *testing.T) {
+			pt.TestPeerstore(t, peerstoreFactory(t, dsFactory, DefaultOpts()))
+		})
+
+		t.Run("protobook limits", func(t *testing.T) {
+			const limit = 10
+			opts := DefaultOpts()
+			opts.MaxProtocols = limit
+			ds, close := dsFactory(t)
+			defer close()
+			ps, err := NewPeerstore(context.Background(), ds, opts)
+			require.NoError(t, err)
+			defer ps.Close()
+			pt.TestPeerstoreProtoStoreLimits(t, ps, limit)
+		})
+	}
+}
+
+func TestDsAddrBook(t *testing.T) {
+	for name, dsFactory := range dstores {
+		t.Run(name+" Cacheful", func(t *testing.T) {
+			opts := DefaultOpts()
+			opts.GCPurgeInterval = 1 * time.Second
+			opts.CacheSize = 1024
+			clk := mockClock.NewMock()
+			opts.Clock = clk
+
+			pt.TestAddrBook(t, addressBookFactory(t, dsFactory, opts), clk)
+		})
+
+		t.Run(name+" Cacheless", func(t *testing.T) {
+			opts := DefaultOpts()
+			opts.GCPurgeInterval = 1 * time.Second
+			opts.CacheSize = 0
+			clk := mockClock.NewMock()
+			opts.Clock = clk
+
+			pt.TestAddrBook(t, addressBookFactory(t, dsFactory, opts), clk)
+		})
+	}
+}
+
+func TestDsKeyBook(t *testing.T) {
+	for name, dsFactory := range dstores {
+		t.Run(name, func(t *testing.T) {
+			pt.TestKeyBook(t, keyBookFactory(t, dsFactory, DefaultOpts()))
+		})
+	}
+}
+
+func BenchmarkDsKeyBook(b *testing.B) {
+	for name, dsFactory := range dstores {
+		b.Run(name, func(b *testing.B) {
+			pt.BenchmarkKeyBook(b, keyBookFactory(b, dsFactory, DefaultOpts()))
+		})
+	}
+}
+
+func BenchmarkDsPeerstore(b *testing.B) {
+	caching := DefaultOpts()
+	caching.CacheSize = 1024
+
+	cacheless := DefaultOpts()
+	cacheless.CacheSize = 0
+
+	for name, dsFactory := range dstores {
+		b.Run(name, func(b *testing.B) {
+			pt.BenchmarkPeerstore(b, peerstoreFactory(b, dsFactory, caching), "Caching")
+		})
+		b.Run(name, func(b *testing.B) {
+			pt.BenchmarkPeerstore(b, peerstoreFactory(b, dsFactory, cacheless), "Cacheless")
+		})
+	}
+}
+
+// Doesn't work on 32bit because badger.
+//
+//lint:ignore U1000 disabled for now
+func badgerStore(tb testing.TB) (ds.Batching, func()) {
+	dataPath, err := ioutil.TempDir(os.TempDir(), "badger")
+	if err != nil {
+		tb.Fatal(err)
+	}
+	store, err := badger.NewDatastore(dataPath, nil)
+	if err != nil {
+		tb.Fatal(err)
+	}
+	closer := func() {
+		store.Close()
+		os.RemoveAll(dataPath)
+	}
+	return store, closer
+}
+
+func leveldbStore(tb testing.TB) (ds.Batching, func()) {
+	// Intentionally test in-memory because disks suck, especially in CI.
+	store, err := leveldb.NewDatastore("", nil)
+	if err != nil {
+		tb.Fatal(err)
+	}
+	closer := func() {
+		store.Close()
+	}
+	return store, closer
+}
+
+func peerstoreFactory(tb testing.TB, storeFactory datastoreFactory, opts Options) pt.PeerstoreFactory {
+	return func() (pstore.Peerstore, func()) {
+		store, storeCloseFn := storeFactory(tb)
+		ps, err := NewPeerstore(context.Background(), store, opts)
+		if err != nil {
+			tb.Fatal(err)
+		}
+		closer := func() {
+			ps.Close()
+			storeCloseFn()
+		}
+		return ps, closer
+	}
+}
+
+func addressBookFactory(tb testing.TB, storeFactory datastoreFactory, opts Options) pt.AddrBookFactory {
+	return func() (pstore.AddrBook, func()) {
+		store, closeFunc := storeFactory(tb)
+		ab, err := NewAddrBook(context.Background(), store, opts)
+		if err != nil {
+			tb.Fatal(err)
+		}
+		closer := func() {
+			ab.Close()
+			closeFunc()
+		}
+		return ab, closer
+	}
+}
+
+func keyBookFactory(tb testing.TB, storeFactory datastoreFactory, opts Options) pt.KeyBookFactory {
+	return func() (pstore.KeyBook, func()) {
+		store, storeCloseFn := storeFactory(tb)
+		kb, err := NewKeyBook(context.Background(), store, opts)
+		if err != nil {
+			tb.Fatal(err)
+		}
+		return kb, storeCloseFn
+	}
+}
diff --git a/p2p/host/peerstore/pstoremem/inmem_test.go b/p2p/host/peerstore/pstoremem/inmem_test.go
new file mode 100644
index 00000000..fdb50b20
--- /dev/null
+++ b/p2p/host/peerstore/pstoremem/inmem_test.go
@@ -0,0 +1,84 @@
+package pstoremem
+
+import (
+	"testing"
+
+	pt "github.com/libp2p/go-libp2p/p2p/host/peerstore/test"
+
+	pstore "github.com/libp2p/go-libp2p-core/peerstore"
+
+	mockClock "github.com/benbjohnson/clock"
+	"github.com/stretchr/testify/require"
+	"go.uber.org/goleak"
+)
+
+func TestInvalidOption(t *testing.T) {
+	_, err := NewPeerstore(1337)
+	require.EqualError(t, err, "unexpected peer store option: 1337")
+}
+
+func TestFuzzInMemoryPeerstore(t *testing.T) {
+	// Just create and close a bunch of peerstores. If this leaks, we'll
+	// catch it in the leak check below.
+	for i := 0; i < 100; i++ {
+		ps, err := NewPeerstore()
+		require.NoError(t, err)
+		ps.Close()
+	}
+}
+
+func TestInMemoryPeerstore(t *testing.T) {
+	pt.TestPeerstore(t, func() (pstore.Peerstore, func()) {
+		ps, err := NewPeerstore()
+		require.NoError(t, err)
+		return ps, func() { ps.Close() }
+	})
+}
+
+func TestPeerstoreProtoStoreLimits(t *testing.T) {
+	const limit = 10
+	ps, err := NewPeerstore(WithMaxProtocols(limit))
+	require.NoError(t, err)
+	defer ps.Close()
+	pt.TestPeerstoreProtoStoreLimits(t, ps, limit)
+}
+
+func TestInMemoryAddrBook(t *testing.T) {
+	clk := mockClock.NewMock()
+	pt.TestAddrBook(t, func() (pstore.AddrBook, func()) {
+		ps, err := NewPeerstore(WithClock(clk))
+		require.NoError(t, err)
+		return ps, func() { ps.Close() }
+	}, clk)
+}
+
+func TestInMemoryKeyBook(t *testing.T) {
+	pt.TestKeyBook(t, func() (pstore.KeyBook, func()) {
+		ps, err := NewPeerstore()
+		require.NoError(t, err)
+		return ps, func() { ps.Close() }
+	})
+}
+
+func BenchmarkInMemoryPeerstore(b *testing.B) {
+	pt.BenchmarkPeerstore(b, func() (pstore.Peerstore, func()) {
+		ps, err := NewPeerstore()
+		require.NoError(b, err)
+		return ps, func() { ps.Close() }
+	}, "InMem")
+}
+
+func BenchmarkInMemoryKeyBook(b *testing.B) {
+	pt.BenchmarkKeyBook(b, func() (pstore.KeyBook, func()) {
+		ps, err := NewPeerstore()
+		require.NoError(b, err)
+		return ps, func() { ps.Close() }
+	})
+}
+
+func TestMain(m *testing.M) {
+	goleak.VerifyTestMain(
+		m,
+		goleak.IgnoreTopFunction("github.com/ipfs/go-log/v2/writer.(*MirrorWriter).logRoutine"),
+	)
+}
diff --git a/p2p/host/peerstore/pstoremem/sorting_test.go b/p2p/host/peerstore/pstoremem/sorting_test.go
new file mode 100644
index 00000000..8ea52d13
--- /dev/null
+++ b/p2p/host/peerstore/pstoremem/sorting_test.go
@@ -0,0 +1,20 @@
+package pstoremem
+
+import (
+	"sort"
+	"testing"
+
+	ma "github.com/multiformats/go-multiaddr"
+	"github.com/stretchr/testify/require"
+)
+
+func TestAddressSorting(t *testing.T) {
+	u1 := ma.StringCast("/ip4/152.12.23.53/udp/1234/utp")
+	u2l := ma.StringCast("/ip4/127.0.0.1/udp/1234/utp")
+	local := ma.StringCast("/ip4/127.0.0.1/tcp/1234")
+	norm := ma.StringCast("/ip4/6.5.4.3/tcp/1234")
+
+	l := addrList{local, u1, u2l, norm}
+	sort.Sort(l)
+	require.Equal(t, l, addrList{u2l, u1, local, norm})
+}
diff --git a/p2p/host/peerstore/test/addr_book_suite.go b/p2p/host/peerstore/test/addr_book_suite.go
new file mode 100644
index 00000000..5bcf8820
--- /dev/null
+++ b/p2p/host/peerstore/test/addr_book_suite.go
@@ -0,0 +1,506 @@
+package test
+
+import (
+	"testing"
+	"time"
+
+	mockClock "github.com/benbjohnson/clock"
+	"github.com/libp2p/go-libp2p-core/crypto"
+	"github.com/libp2p/go-libp2p-core/peer"
+	"github.com/libp2p/go-libp2p-core/record"
+	"github.com/libp2p/go-libp2p-core/test"
+	"github.com/multiformats/go-multiaddr"
+
+	pstore "github.com/libp2p/go-libp2p-core/peerstore"
+)
+
+var addressBookSuite = map[string]func(book pstore.AddrBook, clk *mockClock.Mock) func(*testing.T){
+	"AddAddress":           testAddAddress,
+	"Clear":                testClearWorks,
+	"SetNegativeTTLClears": testSetNegativeTTLClears,
+	"UpdateTTLs":           testUpdateTTLs,
+	"NilAddrsDontBreak":    testNilAddrsDontBreak,
+	"AddressesExpire":      testAddressesExpire,
+	"ClearWithIter":        testClearWithIterator,
+	"PeersWithAddresses":   testPeersWithAddrs,
+	"CertifiedAddresses":   testCertifiedAddresses,
+}
+
+type AddrBookFactory func() (pstore.AddrBook, func())
+
+func TestAddrBook(t *testing.T, factory AddrBookFactory, clk *mockClock.Mock) {
+	for name, test := range addressBookSuite {
+		// Create a new peerstore.
+		ab, closeFunc := factory()
+
+		// Run the test.
+		t.Run(name, test(ab, clk))
+
+		// Cleanup.
+		if closeFunc != nil {
+			closeFunc()
+		}
+	}
+}
+
+func testAddAddress(ab pstore.AddrBook, clk *mockClock.Mock) func(*testing.T) {
+	return func(t *testing.T) {
+		t.Run("add a single address", func(t *testing.T) {
+			id := GeneratePeerIDs(1)[0]
+			addrs := GenerateAddrs(1)
+
+			ab.AddAddr(id, addrs[0], time.Hour)
+
+			AssertAddressesEqual(t, addrs, ab.Addrs(id))
+		})
+
+		t.Run("idempotent add single address", func(t *testing.T) {
+			id := GeneratePeerIDs(1)[0]
+			addrs := GenerateAddrs(1)
+
+			ab.AddAddr(id, addrs[0], time.Hour)
+			ab.AddAddr(id, addrs[0], time.Hour)
+
+			AssertAddressesEqual(t, addrs, ab.Addrs(id))
+		})
+
+		t.Run("add multiple addresses", func(t *testing.T) {
+			id := GeneratePeerIDs(1)[0]
+			addrs := GenerateAddrs(3)
+
+			ab.AddAddrs(id, addrs, time.Hour)
+			AssertAddressesEqual(t, addrs, ab.Addrs(id))
+		})
+
+		t.Run("idempotent add multiple addresses", func(t *testing.T) {
+			id := GeneratePeerIDs(1)[0]
+			addrs := GenerateAddrs(3)
+
+			ab.AddAddrs(id, addrs, time.Hour)
+			ab.AddAddrs(id, addrs, time.Hour)
+
+			AssertAddressesEqual(t, addrs, ab.Addrs(id))
+		})
+
+		t.Run("adding an existing address with a later expiration extends its ttl", func(t *testing.T) {
+			id := GeneratePeerIDs(1)[0]
+			addrs := GenerateAddrs(3)
+
+			ab.AddAddrs(id, addrs, time.Second)
+
+			// same address as before but with a higher TTL
+			ab.AddAddrs(id, addrs[2:], time.Hour)
+
+			// after the initial TTL has expired, check that only the third address is present.
+			clk.Add(1200 * time.Millisecond)
+			AssertAddressesEqual(t, addrs[2:], ab.Addrs(id))
+
+			// make sure we actually set the TTL
+			ab.UpdateAddrs(id, time.Hour, 0)
+			AssertAddressesEqual(t, nil, ab.Addrs(id))
+		})
+
+		t.Run("adding an existing address with an earlier expiration never reduces the expiration", func(t *testing.T) {
+			id := GeneratePeerIDs(1)[0]
+			addrs := GenerateAddrs(3)
+
+			ab.AddAddrs(id, addrs, time.Hour)
+
+			// same address as before but with a lower TTL
+			ab.AddAddrs(id, addrs[2:], time.Second)
+
+			// after the initial TTL has expired, check that all three addresses are still present (i.e. the TTL on
+			// the modified one was not shortened).
+			clk.Add(2100 * time.Millisecond)
+			AssertAddressesEqual(t, addrs, ab.Addrs(id))
+		})
+
+		t.Run("adding an existing address with an earlier expiration never reduces the TTL", func(t *testing.T) {
+			id := GeneratePeerIDs(1)[0]
+			addrs := GenerateAddrs(1)
+
+			ab.AddAddrs(id, addrs, 4*time.Second)
+			// 4 seconds left
+			clk.Add(2 * time.Second)
+			// 2 second left
+			ab.AddAddrs(id, addrs, 3*time.Second)
+			// 3 seconds left
+			clk.Add(1 * time.Second)
+			// 2 seconds left.
+
+			// We still have the address.
+			AssertAddressesEqual(t, addrs, ab.Addrs(id))
+
+			// The TTL wasn't reduced
+			ab.UpdateAddrs(id, 4*time.Second, 0)
+			AssertAddressesEqual(t, nil, ab.Addrs(id))
+		})
+	}
+}
+
+func testClearWorks(ab pstore.AddrBook, clk *mockClock.Mock) func(t *testing.T) {
+	return func(t *testing.T) {
+		ids := GeneratePeerIDs(2)
+		addrs := GenerateAddrs(5)
+
+		ab.AddAddrs(ids[0], addrs[0:3], time.Hour)
+		ab.AddAddrs(ids[1], addrs[3:], time.Hour)
+
+		AssertAddressesEqual(t, addrs[0:3], ab.Addrs(ids[0]))
+		AssertAddressesEqual(t, addrs[3:], ab.Addrs(ids[1]))
+
+		ab.ClearAddrs(ids[0])
+		AssertAddressesEqual(t, nil, ab.Addrs(ids[0]))
+		AssertAddressesEqual(t, addrs[3:], ab.Addrs(ids[1]))
+
+		ab.ClearAddrs(ids[1])
+		AssertAddressesEqual(t, nil, ab.Addrs(ids[0]))
+		AssertAddressesEqual(t, nil, ab.Addrs(ids[1]))
+	}
+}
+
+func testSetNegativeTTLClears(m pstore.AddrBook, clk *mockClock.Mock) func(t *testing.T) {
+	return func(t *testing.T) {
+		id := GeneratePeerIDs(1)[0]
+		addrs := GenerateAddrs(100)
+
+		m.SetAddrs(id, addrs, time.Hour)
+		AssertAddressesEqual(t, addrs, m.Addrs(id))
+
+		// remove two addresses.
+		m.SetAddr(id, addrs[50], -1)
+		m.SetAddr(id, addrs[75], -1)
+
+		// calculate the survivors
+		survivors := append(addrs[0:50], addrs[51:]...)
+		survivors = append(survivors[0:74], survivors[75:]...)
+
+		AssertAddressesEqual(t, survivors, m.Addrs(id))
+
+		// remove _all_ the addresses
+		m.SetAddrs(id, survivors, -1)
+		if len(m.Addrs(id)) != 0 {
+			t.Error("expected empty address list after clearing all addresses")
+		}
+
+		// add half, but try to remove more than we added
+		m.SetAddrs(id, addrs[:50], time.Hour)
+		m.SetAddrs(id, addrs, -1)
+		if len(m.Addrs(id)) != 0 {
+			t.Error("expected empty address list after clearing all addresses")
+		}
+
+		// try to remove the same addr multiple times
+		m.SetAddrs(id, addrs[:5], time.Hour)
+		repeated := make([]multiaddr.Multiaddr, 10)
+		for i := 0; i < len(repeated); i++ {
+			repeated[i] = addrs[0]
+		}
+		m.SetAddrs(id, repeated, -1)
+		if len(m.Addrs(id)) != 4 {
+			t.Errorf("expected 4 addrs after removing one, got %d", len(m.Addrs(id)))
+		}
+	}
+}
+
+func testUpdateTTLs(m pstore.AddrBook, clk *mockClock.Mock) func(t *testing.T) {
+	return func(t *testing.T) {
+		t.Run("update ttl of peer with no addrs", func(t *testing.T) {
+			id := GeneratePeerIDs(1)[0]
+
+			// Shouldn't panic.
+			m.UpdateAddrs(id, time.Hour, time.Minute)
+		})
+
+		t.Run("update to 0 clears addrs", func(t *testing.T) {
+			id := GeneratePeerIDs(1)[0]
+			addrs := GenerateAddrs(1)
+
+			// Shouldn't panic.
+			m.SetAddrs(id, addrs, time.Hour)
+			m.UpdateAddrs(id, time.Hour, 0)
+			if len(m.Addrs(id)) != 0 {
+				t.Error("expected no addresses")
+			}
+		})
+
+		t.Run("update ttls successfully", func(t *testing.T) {
+			ids := GeneratePeerIDs(2)
+			addrs1, addrs2 := GenerateAddrs(2), GenerateAddrs(2)
+
+			// set two keys with different ttls for each peer.
+			m.SetAddr(ids[0], addrs1[0], time.Hour)
+			m.SetAddr(ids[0], addrs1[1], time.Minute)
+			m.SetAddr(ids[1], addrs2[0], time.Hour)
+			m.SetAddr(ids[1], addrs2[1], time.Minute)
+
+			// Sanity check.
+			AssertAddressesEqual(t, addrs1, m.Addrs(ids[0]))
+			AssertAddressesEqual(t, addrs2, m.Addrs(ids[1]))
+
+			// Will only affect addrs1[0].
+			// Badger does not support subsecond TTLs.
+			// https://github.com/dgraph-io/badger/issues/339
+			m.UpdateAddrs(ids[0], time.Hour, 1*time.Second)
+
+			// No immediate effect.
+			AssertAddressesEqual(t, addrs1, m.Addrs(ids[0]))
+			AssertAddressesEqual(t, addrs2, m.Addrs(ids[1]))
+
+			// After a wait, addrs[0] is gone.
+			clk.Add(2 * time.Second)
+			AssertAddressesEqual(t, addrs1[1:2], m.Addrs(ids[0]))
+			AssertAddressesEqual(t, addrs2, m.Addrs(ids[1]))
+
+			// Will only affect addrs2[0].
+			m.UpdateAddrs(ids[1], time.Hour, 1*time.Second)
+
+			// No immediate effect.
+			AssertAddressesEqual(t, addrs1[1:2], m.Addrs(ids[0]))
+			AssertAddressesEqual(t, addrs2, m.Addrs(ids[1]))
+
+			clk.Add(2 * time.Second)
+
+			// First addrs is gone in both.
+			AssertAddressesEqual(t, addrs1[1:], m.Addrs(ids[0]))
+			AssertAddressesEqual(t, addrs2[1:], m.Addrs(ids[1]))
+		})
+
+	}
+}
+
+func testNilAddrsDontBreak(m pstore.AddrBook, clk *mockClock.Mock) func(t *testing.T) {
+	return func(t *testing.T) {
+		id := GeneratePeerIDs(1)[0]
+
+		m.SetAddr(id, nil, time.Hour)
+		m.AddAddr(id, nil, time.Hour)
+	}
+}
+
+func testAddressesExpire(m pstore.AddrBook, clk *mockClock.Mock) func(t *testing.T) {
+	return func(t *testing.T) {
+		ids := GeneratePeerIDs(2)
+		addrs1 := GenerateAddrs(3)
+		addrs2 := GenerateAddrs(2)
+
+		m.AddAddrs(ids[0], addrs1, time.Hour)
+		m.AddAddrs(ids[1], addrs2, time.Hour)
+
+		AssertAddressesEqual(t, addrs1, m.Addrs(ids[0]))
+		AssertAddressesEqual(t, addrs2, m.Addrs(ids[1]))
+
+		m.AddAddrs(ids[0], addrs1, 2*time.Hour)
+		m.AddAddrs(ids[1], addrs2, 2*time.Hour)
+
+		AssertAddressesEqual(t, addrs1, m.Addrs(ids[0]))
+		AssertAddressesEqual(t, addrs2, m.Addrs(ids[1]))
+
+		m.SetAddr(ids[0], addrs1[0], 100*time.Microsecond)
+		clk.Add(100 * time.Millisecond)
+		AssertAddressesEqual(t, addrs1[1:3], m.Addrs(ids[0]))
+		AssertAddressesEqual(t, addrs2, m.Addrs(ids[1]))
+
+		m.SetAddr(ids[0], addrs1[2], 100*time.Microsecond)
+		clk.Add(100 * time.Millisecond)
+		AssertAddressesEqual(t, addrs1[1:2], m.Addrs(ids[0]))
+		AssertAddressesEqual(t, addrs2, m.Addrs(ids[1]))
+
+		m.SetAddr(ids[1], addrs2[0], 100*time.Microsecond)
+		clk.Add(100 * time.Millisecond)
+		AssertAddressesEqual(t, addrs1[1:2], m.Addrs(ids[0]))
+		AssertAddressesEqual(t, addrs2[1:], m.Addrs(ids[1]))
+
+		m.SetAddr(ids[1], addrs2[1], 100*time.Microsecond)
+		clk.Add(100 * time.Millisecond)
+		AssertAddressesEqual(t, addrs1[1:2], m.Addrs(ids[0]))
+		AssertAddressesEqual(t, nil, m.Addrs(ids[1]))
+
+		m.SetAddr(ids[0], addrs1[1], 100*time.Microsecond)
+		clk.Add(100 * time.Millisecond)
+		AssertAddressesEqual(t, nil, m.Addrs(ids[0]))
+		AssertAddressesEqual(t, nil, m.Addrs(ids[1]))
+	}
+}
+
+func testClearWithIterator(m pstore.AddrBook, clk *mockClock.Mock) func(t *testing.T) {
+	return func(t *testing.T) {
+		ids := GeneratePeerIDs(2)
+		addrs := GenerateAddrs(100)
+
+		// Add the peers with 50 addresses each.
+		m.AddAddrs(ids[0], addrs[:50], pstore.PermanentAddrTTL)
+		m.AddAddrs(ids[1], addrs[50:], pstore.PermanentAddrTTL)
+
+		if all := append(m.Addrs(ids[0]), m.Addrs(ids[1])...); len(all) != 100 {
+			t.Fatal("expected pstore to contain both peers with all their maddrs")
+		}
+
+		// Since we don't fetch these peers, they won't be present in cache.
+
+		m.ClearAddrs(ids[0])
+		if all := append(m.Addrs(ids[0]), m.Addrs(ids[1])...); len(all) != 50 {
+			t.Fatal("expected pstore to contain only addrs of peer 2")
+		}
+
+		m.ClearAddrs(ids[1])
+		if all := append(m.Addrs(ids[0]), m.Addrs(ids[1])...); len(all) != 0 {
+			t.Fatal("expected pstore to contain no addresses")
+		}
+	}
+}
+
+func testPeersWithAddrs(m pstore.AddrBook, clk *mockClock.Mock) func(t *testing.T) {
+	return func(t *testing.T) {
+		// cannot run in parallel as the store is modified.
+		// go runs sequentially in the specified order
+		// see https://blog.golang.org/subtests
+
+		t.Run("empty addrbook", func(t *testing.T) {
+			if peers := m.PeersWithAddrs(); len(peers) != 0 {
+				t.Fatal("expected to find no peers")
+			}
+		})
+
+		t.Run("non-empty addrbook", func(t *testing.T) {
+			ids := GeneratePeerIDs(2)
+			addrs := GenerateAddrs(10)
+
+			m.AddAddrs(ids[0], addrs[:5], pstore.PermanentAddrTTL)
+			m.AddAddrs(ids[1], addrs[5:], pstore.PermanentAddrTTL)
+
+			if peers := m.PeersWithAddrs(); len(peers) != 2 {
+				t.Fatal("expected to find 2 peers")
+			}
+		})
+	}
+}
+
+func testCertifiedAddresses(m pstore.AddrBook, clk *mockClock.Mock) func(*testing.T) {
+	return func(t *testing.T) {
+		cab := m.(pstore.CertifiedAddrBook)
+
+		priv, _, err := test.RandTestKeyPair(crypto.Ed25519, 256)
+		if err != nil {
+			t.Errorf("error generating testing keys: %v", err)
+		}
+
+		id, _ := peer.IDFromPrivateKey(priv)
+		allAddrs := GenerateAddrs(10)
+		certifiedAddrs := allAddrs[:5]
+		uncertifiedAddrs := allAddrs[5:]
+		rec1 := peer.NewPeerRecord()
+		rec1.PeerID = id
+		rec1.Addrs = certifiedAddrs
+		signedRec1, err := record.Seal(rec1, priv)
+		if err != nil {
+			t.Errorf("error creating signed routing record: %v", err)
+		}
+
+		rec2 := peer.NewPeerRecord()
+		rec2.PeerID = id
+		rec2.Addrs = certifiedAddrs
+		signedRec2, err := record.Seal(rec2, priv)
+		if err != nil {
+			t.Errorf("error creating signed routing record: %v", err)
+		}
+
+		// add a few non-certified addrs
+		m.AddAddrs(id, uncertifiedAddrs, time.Hour)
+
+		// make sure they're present
+		AssertAddressesEqual(t, uncertifiedAddrs, m.Addrs(id))
+
+		// add the signed record to addr book
+		accepted, err := cab.ConsumePeerRecord(signedRec2, time.Hour)
+		if err != nil {
+			t.Errorf("error adding signed routing record to addrbook: %v", err)
+		}
+		if !accepted {
+			t.Errorf("should have accepted signed peer record")
+		}
+
+		// the non-certified addrs should be gone & we should get only certified addrs back from Addrs
+		// AssertAddressesEqual(t, certifiedAddrs, m.Addrs(id))
+		AssertAddressesEqual(t, allAddrs, m.Addrs(id))
+
+		// PeersWithAddrs should return a single peer
+		if len(m.PeersWithAddrs()) != 1 {
+			t.Errorf("expected PeersWithAddrs to return 1, got %d", len(m.PeersWithAddrs()))
+		}
+
+		// Adding an old record should fail
+		accepted, err = cab.ConsumePeerRecord(signedRec1, time.Hour)
+		if accepted {
+			t.Error("We should have failed to accept a record with an old sequence number")
+		}
+		if err != nil {
+			t.Errorf("expected no error, got: %s", err)
+		}
+
+		// once certified addrs exist, trying to add non-certified addrs should have no effect
+		// m.AddAddrs(id, uncertifiedAddrs, time.Hour)
+		// AssertAddressesEqual(t, certifiedAddrs, m.Addrs(id))
+		// XXX: Disabled until signed records are required
+		m.AddAddrs(id, uncertifiedAddrs, time.Hour)
+		AssertAddressesEqual(t, allAddrs, m.Addrs(id))
+
+		// we should be able to retrieve the signed peer record
+		rec3 := cab.GetPeerRecord(id)
+		if rec3 == nil || !signedRec2.Equal(rec3) {
+			t.Error("unable to retrieve signed routing record from addrbook")
+		}
+
+		// Adding a new envelope should clear existing certified addresses.
+		// Only the newly-added ones should remain
+		certifiedAddrs = certifiedAddrs[:3]
+		rec4 := peer.NewPeerRecord()
+		rec4.PeerID = id
+		rec4.Addrs = certifiedAddrs
+		signedRec4, err := record.Seal(rec4, priv)
+		test.AssertNilError(t, err)
+		accepted, err = cab.ConsumePeerRecord(signedRec4, time.Hour)
+		test.AssertNilError(t, err)
+		if !accepted {
+			t.Error("expected peer record to be accepted")
+		}
+		// AssertAddressesEqual(t, certifiedAddrs, m.Addrs(id))
+		AssertAddressesEqual(t, allAddrs, m.Addrs(id))
+
+		// update TTL on signed addrs to -1 to remove them.
+		// the signed routing record should be deleted
+		// m.SetAddrs(id, certifiedAddrs, -1)
+		// XXX: Disabled until signed records are required
+		m.SetAddrs(id, allAddrs, -1)
+		if len(m.Addrs(id)) != 0 {
+			t.Error("expected zero certified addrs after setting TTL to -1")
+		}
+		if cab.GetPeerRecord(id) != nil {
+			t.Error("expected signed peer record to be removed when addresses expire")
+		}
+
+		// Test that natural TTL expiration clears signed peer records
+		accepted, err = cab.ConsumePeerRecord(signedRec4, time.Second)
+		if !accepted {
+			t.Error("expected peer record to be accepted")
+		}
+		test.AssertNilError(t, err)
+		AssertAddressesEqual(t, certifiedAddrs, m.Addrs(id))
+
+		clk.Add(2 * time.Second)
+		if cab.GetPeerRecord(id) != nil {
+			t.Error("expected signed peer record to be removed when addresses expire")
+		}
+
+		// adding a peer record that's signed with the wrong key should fail
+		priv2, _, err := test.RandTestKeyPair(crypto.Ed25519, 256)
+		test.AssertNilError(t, err)
+		env, err := record.Seal(rec4, priv2)
+		test.AssertNilError(t, err)
+
+		accepted, err = cab.ConsumePeerRecord(env, time.Second)
+		if accepted || err == nil {
+			t.Error("expected adding a PeerRecord that's signed with the wrong key to fail")
+		}
+	}
+}
diff --git a/p2p/host/peerstore/test/benchmarks_suite.go b/p2p/host/peerstore/test/benchmarks_suite.go
new file mode 100644
index 00000000..c67303b1
--- /dev/null
+++ b/p2p/host/peerstore/test/benchmarks_suite.go
@@ -0,0 +1,124 @@
+package test
+
+import (
+	"context"
+	"fmt"
+	"sort"
+	"testing"
+
+	pstore "github.com/libp2p/go-libp2p-core/peerstore"
+)
+
+var peerstoreBenchmarks = map[string]func(pstore.Peerstore, chan *peerpair) func(*testing.B){
+	"AddAddrs": benchmarkAddAddrs,
+	"SetAddrs": benchmarkSetAddrs,
+	"GetAddrs": benchmarkGetAddrs,
+	// The in-between get allows us to benchmark the read-through cache.
+	"AddGetAndClearAddrs": benchmarkAddGetAndClearAddrs,
+	// Calls PeersWithAddr on a peerstore with 1000 peers.
+	"Get1000PeersWithAddrs": benchmarkGet1000PeersWithAddrs,
+}
+
+func BenchmarkPeerstore(b *testing.B, factory PeerstoreFactory, variant string) {
+	// Parameterises benchmarks to tackle peers with 1, 10, 100 multiaddrs.
+	params := []struct {
+		n  int
+		ch chan *peerpair
+	}{
+		{1, make(chan *peerpair, 100)},
+		{10, make(chan *peerpair, 100)},
+		{100, make(chan *peerpair, 100)},
+	}
+
+	ctx, cancel := context.WithCancel(context.Background())
+	defer cancel()
+
+	// Start all test peer producing goroutines, where each produces peers with as many
+	// multiaddrs as the n field in the param struct.
+	for _, p := range params {
+		go AddressProducer(ctx, b, p.ch, p.n)
+	}
+
+	// So tests are always run in the same order.
+	ordernames := make([]string, 0, len(peerstoreBenchmarks))
+	for name := range peerstoreBenchmarks {
+		ordernames = append(ordernames, name)
+	}
+	sort.Strings(ordernames)
+
+	for _, name := range ordernames {
+		bench := peerstoreBenchmarks[name]
+		for _, p := range params {
+			// Create a new peerstore.
+			ps, closeFunc := factory()
+
+			// Run the test.
+			b.Run(fmt.Sprintf("%s-%dAddrs-%s", name, p.n, variant), bench(ps, p.ch))
+
+			// Cleanup.
+			if closeFunc != nil {
+				closeFunc()
+			}
+		}
+	}
+}
+
+func benchmarkAddAddrs(ps pstore.Peerstore, addrs chan *peerpair) func(*testing.B) {
+	return func(b *testing.B) {
+		b.ResetTimer()
+		for i := 0; i < b.N; i++ {
+			pp := <-addrs
+			ps.AddAddrs(pp.ID, pp.Addr, pstore.PermanentAddrTTL)
+		}
+	}
+}
+
+func benchmarkSetAddrs(ps pstore.Peerstore, addrs chan *peerpair) func(*testing.B) {
+	return func(b *testing.B) {
+		b.ResetTimer()
+		for i := 0; i < b.N; i++ {
+			pp := <-addrs
+			ps.SetAddrs(pp.ID, pp.Addr, pstore.PermanentAddrTTL)
+		}
+	}
+}
+
+func benchmarkGetAddrs(ps pstore.Peerstore, addrs chan *peerpair) func(*testing.B) {
+	return func(b *testing.B) {
+		pp := <-addrs
+		ps.SetAddrs(pp.ID, pp.Addr, pstore.PermanentAddrTTL)
+
+		b.ResetTimer()
+		for i := 0; i < b.N; i++ {
+			_ = ps.Addrs(pp.ID)
+		}
+	}
+}
+
+func benchmarkAddGetAndClearAddrs(ps pstore.Peerstore, addrs chan *peerpair) func(*testing.B) {
+	return func(b *testing.B) {
+		b.ResetTimer()
+		for i := 0; i < b.N; i++ {
+			pp := <-addrs
+			ps.AddAddrs(pp.ID, pp.Addr, pstore.PermanentAddrTTL)
+			ps.Addrs(pp.ID)
+			ps.ClearAddrs(pp.ID)
+		}
+	}
+}
+
+func benchmarkGet1000PeersWithAddrs(ps pstore.Peerstore, addrs chan *peerpair) func(*testing.B) {
+	return func(b *testing.B) {
+		var peers = make([]*peerpair, 1000)
+		for i := range peers {
+			pp := <-addrs
+			ps.AddAddrs(pp.ID, pp.Addr, pstore.PermanentAddrTTL)
+			peers[i] = pp
+		}
+
+		b.ResetTimer()
+		for i := 0; i < b.N; i++ {
+			_ = ps.PeersWithAddrs()
+		}
+	}
+}
diff --git a/p2p/host/peerstore/test/keybook_suite.go b/p2p/host/peerstore/test/keybook_suite.go
new file mode 100644
index 00000000..2774b3df
--- /dev/null
+++ b/p2p/host/peerstore/test/keybook_suite.go
@@ -0,0 +1,338 @@
+package test
+
+import (
+	"sort"
+	"testing"
+
+	"github.com/stretchr/testify/require"
+
+	ic "github.com/libp2p/go-libp2p-core/crypto"
+	"github.com/libp2p/go-libp2p-core/peer"
+	pt "github.com/libp2p/go-libp2p-core/test"
+
+	pstore "github.com/libp2p/go-libp2p-core/peerstore"
+)
+
+var keyBookSuite = map[string]func(kb pstore.KeyBook) func(*testing.T){
+	"AddGetPrivKey":         testKeybookPrivKey,
+	"AddGetPubKey":          testKeyBookPubKey,
+	"PeersWithKeys":         testKeyBookPeers,
+	"PubKeyAddedOnRetrieve": testInlinedPubKeyAddedOnRetrieve,
+	"Delete":                testKeyBookDelete,
+}
+
+type KeyBookFactory func() (pstore.KeyBook, func())
+
+func TestKeyBook(t *testing.T, factory KeyBookFactory) {
+	for name, test := range keyBookSuite {
+		// Create a new peerstore.
+		kb, closeFunc := factory()
+
+		// Run the test.
+		t.Run(name, test(kb))
+
+		// Cleanup.
+		if closeFunc != nil {
+			closeFunc()
+		}
+	}
+}
+
+func testKeybookPrivKey(kb pstore.KeyBook) func(t *testing.T) {
+	return func(t *testing.T) {
+		if peers := kb.PeersWithKeys(); len(peers) > 0 {
+			t.Error("expected peers to be empty on init")
+		}
+
+		priv, _, err := pt.RandTestKeyPair(ic.RSA, 2048)
+		if err != nil {
+			t.Fatal(err)
+		}
+
+		id, err := peer.IDFromPrivateKey(priv)
+		if err != nil {
+			t.Error(err)
+		}
+
+		if res := kb.PrivKey(id); res != nil {
+			t.Error("retrieving private key should have failed")
+		}
+
+		err = kb.AddPrivKey(id, priv)
+		if err != nil {
+			t.Error(err)
+		}
+
+		if res := kb.PrivKey(id); !priv.Equals(res) {
+			t.Error("retrieved private key did not match stored private key")
+		}
+
+		if peers := kb.PeersWithKeys(); len(peers) != 1 || peers[0] != id {
+			t.Error("list of peers did not include test peer")
+		}
+	}
+}
+
+func testKeyBookPubKey(kb pstore.KeyBook) func(t *testing.T) {
+	return func(t *testing.T) {
+		if peers := kb.PeersWithKeys(); len(peers) > 0 {
+			t.Error("expected peers to be empty on init")
+		}
+
+		_, pub, err := pt.RandTestKeyPair(ic.RSA, 2048)
+		if err != nil {
+			t.Fatal(err)
+		}
+
+		id, err := peer.IDFromPublicKey(pub)
+		if err != nil {
+			t.Fatal(err)
+		}
+
+		if res := kb.PubKey(id); res != nil {
+			t.Error("retrieving public key should have failed")
+		}
+
+		err = kb.AddPubKey(id, pub)
+		if err != nil {
+			t.Error(err)
+		}
+
+		if res := kb.PubKey(id); !pub.Equals(res) {
+			t.Error("retrieved public key did not match stored public key")
+		}
+
+		if peers := kb.PeersWithKeys(); len(peers) != 1 || peers[0] != id {
+			t.Error("list of peers did not include test peer")
+		}
+	}
+}
+
+func testKeyBookPeers(kb pstore.KeyBook) func(t *testing.T) {
+	return func(t *testing.T) {
+		if peers := kb.PeersWithKeys(); len(peers) > 0 {
+			t.Error("expected peers to be empty on init")
+		}
+
+		var peers peer.IDSlice
+		for i := 0; i < 10; i++ {
+			// Add a public key.
+			_, pub, err := pt.RandTestKeyPair(ic.RSA, 2048)
+			if err != nil {
+				t.Fatal(err)
+			}
+			p1, err := peer.IDFromPublicKey(pub)
+			if err != nil {
+				t.Fatal(err)
+			}
+			kb.AddPubKey(p1, pub)
+
+			// Add a private key.
+			priv, _, err := pt.RandTestKeyPair(ic.RSA, 2048)
+			if err != nil {
+				t.Fatal(err)
+			}
+			p2, err := peer.IDFromPrivateKey(priv)
+			if err != nil {
+				t.Fatal(err)
+			}
+			kb.AddPrivKey(p2, priv)
+
+			peers = append(peers, []peer.ID{p1, p2}...)
+		}
+
+		kbPeers := kb.PeersWithKeys()
+		sort.Sort(kbPeers)
+		sort.Sort(peers)
+
+		for i, p := range kbPeers {
+			if p != peers[i] {
+				t.Errorf("mismatch of peer at index %d", i)
+			}
+		}
+	}
+}
+
+func testInlinedPubKeyAddedOnRetrieve(kb pstore.KeyBook) func(t *testing.T) {
+	return func(t *testing.T) {
+		t.Skip("key inlining disabled for now: see libp2p/specs#111")
+
+		if peers := kb.PeersWithKeys(); len(peers) > 0 {
+			t.Error("expected peers to be empty on init")
+		}
+
+		// Key small enough for inlining.
+		_, pub, err := ic.GenerateKeyPair(ic.Ed25519, 256)
+		if err != nil {
+			t.Error(err)
+		}
+
+		id, err := peer.IDFromPublicKey(pub)
+		if err != nil {
+			t.Error(err)
+		}
+
+		pubKey := kb.PubKey(id)
+		if !pubKey.Equals(pub) {
+			t.Error("mismatch between original public key and keybook-calculated one")
+		}
+	}
+}
+
+func testKeyBookDelete(kb pstore.KeyBook) func(t *testing.T) {
+	return func(t *testing.T) {
+		// don't use an ed25519 key here, otherwise the key book might try to derive the pubkey from the peer ID
+		priv, pub, err := ic.GenerateKeyPair(ic.RSA, 2048)
+		require.NoError(t, err)
+		p, err := peer.IDFromPublicKey(pub)
+		require.NoError(t, err)
+		require.NoError(t, kb.AddPubKey(p, pub))
+		require.NoError(t, kb.AddPrivKey(p, priv))
+		require.NotNil(t, kb.PrivKey(p))
+		require.NotNil(t, kb.PubKey(p))
+		kb.RemovePeer(p)
+		require.Nil(t, kb.PrivKey(p))
+		require.Nil(t, kb.PubKey(p))
+	}
+}
+
+var keybookBenchmarkSuite = map[string]func(kb pstore.KeyBook) func(*testing.B){
+	"PubKey":        benchmarkPubKey,
+	"AddPubKey":     benchmarkAddPubKey,
+	"PrivKey":       benchmarkPrivKey,
+	"AddPrivKey":    benchmarkAddPrivKey,
+	"PeersWithKeys": benchmarkPeersWithKeys,
+}
+
+func BenchmarkKeyBook(b *testing.B, factory KeyBookFactory) {
+	ordernames := make([]string, 0, len(keybookBenchmarkSuite))
+	for name := range keybookBenchmarkSuite {
+		ordernames = append(ordernames, name)
+	}
+	sort.Strings(ordernames)
+	for _, name := range ordernames {
+		bench := keybookBenchmarkSuite[name]
+		kb, closeFunc := factory()
+
+		b.Run(name, bench(kb))
+
+		if closeFunc != nil {
+			closeFunc()
+		}
+	}
+}
+
+func benchmarkPubKey(kb pstore.KeyBook) func(*testing.B) {
+	return func(b *testing.B) {
+		_, pub, err := pt.RandTestKeyPair(ic.RSA, 2048)
+		if err != nil {
+			b.Fatal(err)
+		}
+
+		id, err := peer.IDFromPublicKey(pub)
+		if err != nil {
+			b.Fatal(err)
+		}
+
+		err = kb.AddPubKey(id, pub)
+		if err != nil {
+			b.Fatal(err)
+		}
+
+		b.ResetTimer()
+		for i := 0; i < b.N; i++ {
+			kb.PubKey(id)
+		}
+	}
+}
+
+func benchmarkAddPubKey(kb pstore.KeyBook) func(*testing.B) {
+	return func(b *testing.B) {
+		_, pub, err := pt.RandTestKeyPair(ic.RSA, 2048)
+		if err != nil {
+			b.Fatal(err)
+		}
+
+		id, err := peer.IDFromPublicKey(pub)
+		if err != nil {
+			b.Fatal(err)
+		}
+
+		b.ResetTimer()
+		for i := 0; i < b.N; i++ {
+			kb.AddPubKey(id, pub)
+		}
+	}
+}
+
+func benchmarkPrivKey(kb pstore.KeyBook) func(*testing.B) {
+	return func(b *testing.B) {
+		priv, _, err := pt.RandTestKeyPair(ic.RSA, 2048)
+		if err != nil {
+			b.Fatal(err)
+		}
+
+		id, err := peer.IDFromPrivateKey(priv)
+		if err != nil {
+			b.Fatal(err)
+		}
+
+		err = kb.AddPrivKey(id, priv)
+		if err != nil {
+			b.Fatal(err)
+		}
+
+		b.ResetTimer()
+		for i := 0; i < b.N; i++ {
+			kb.PrivKey(id)
+		}
+	}
+}
+
+func benchmarkAddPrivKey(kb pstore.KeyBook) func(*testing.B) {
+	return func(b *testing.B) {
+		priv, _, err := pt.RandTestKeyPair(ic.RSA, 2048)
+		if err != nil {
+			b.Fatal(err)
+		}
+
+		id, err := peer.IDFromPrivateKey(priv)
+		if err != nil {
+			b.Fatal(err)
+		}
+
+		b.ResetTimer()
+		for i := 0; i < b.N; i++ {
+			kb.AddPrivKey(id, priv)
+		}
+	}
+}
+
+func benchmarkPeersWithKeys(kb pstore.KeyBook) func(*testing.B) {
+	return func(b *testing.B) {
+		for i := 0; i < 10; i++ {
+			priv, pub, err := pt.RandTestKeyPair(ic.RSA, 2048)
+			if err != nil {
+				b.Fatal(err)
+			}
+
+			id, err := peer.IDFromPublicKey(pub)
+			if err != nil {
+				b.Fatal(err)
+			}
+
+			err = kb.AddPubKey(id, pub)
+			if err != nil {
+				b.Fatal(err)
+			}
+			err = kb.AddPrivKey(id, priv)
+			if err != nil {
+				b.Fatal(err)
+			}
+		}
+		b.ResetTimer()
+		for i := 0; i < b.N; i++ {
+			kb.PeersWithKeys()
+		}
+	}
+}
diff --git a/p2p/host/peerstore/test/peerstore_suite.go b/p2p/host/peerstore/test/peerstore_suite.go
new file mode 100644
index 00000000..38f9a495
--- /dev/null
+++ b/p2p/host/peerstore/test/peerstore_suite.go
@@ -0,0 +1,402 @@
+package test
+
+import (
+	"context"
+	"fmt"
+	"math/rand"
+	"reflect"
+	"sort"
+	"testing"
+	"time"
+
+	"github.com/libp2p/go-libp2p-core/crypto"
+	"github.com/libp2p/go-libp2p-core/peer"
+	ma "github.com/multiformats/go-multiaddr"
+
+	pstore "github.com/libp2p/go-libp2p-core/peerstore"
+	"github.com/stretchr/testify/require"
+)
+
+var peerstoreSuite = map[string]func(pstore.Peerstore) func(*testing.T){
+	"AddrStream":               testAddrStream,
+	"GetStreamBeforePeerAdded": testGetStreamBeforePeerAdded,
+	"AddStreamDuplicates":      testAddrStreamDuplicates,
+	"PeerstoreProtoStore":      testPeerstoreProtoStore,
+	"BasicPeerstore":           testBasicPeerstore,
+	"Metadata":                 testMetadata,
+	"CertifiedAddrBook":        testCertifiedAddrBook,
+}
+
+type PeerstoreFactory func() (pstore.Peerstore, func())
+
+func TestPeerstore(t *testing.T, factory PeerstoreFactory) {
+	for name, test := range peerstoreSuite {
+		// Create a new peerstore.
+		ps, closeFunc := factory()
+
+		// Run the test.
+		t.Run(name, test(ps))
+
+		// Cleanup.
+		if closeFunc != nil {
+			closeFunc()
+		}
+	}
+}
+
+func testAddrStream(ps pstore.Peerstore) func(t *testing.T) {
+	return func(t *testing.T) {
+		addrs, pid := getAddrs(t, 100), peer.ID("testpeer")
+		ps.AddAddrs(pid, addrs[:10], time.Hour)
+
+		ctx, cancel := context.WithCancel(context.Background())
+		addrch := ps.AddrStream(ctx, pid)
+
+		// while that subscription is active, publish ten more addrs
+		// this tests that it doesnt hang
+		for i := 10; i < 20; i++ {
+			ps.AddAddr(pid, addrs[i], time.Hour)
+		}
+
+		// now receive them (without hanging)
+		timeout := time.After(time.Second * 10)
+		for i := 0; i < 20; i++ {
+			select {
+			case <-addrch:
+			case <-timeout:
+				t.Fatal("timed out")
+			}
+		}
+
+		// start a second stream
+		ctx2, cancel2 := context.WithCancel(context.Background())
+		addrch2 := ps.AddrStream(ctx2, pid)
+
+		done := make(chan struct{})
+		go func() {
+			defer close(done)
+			// now send the rest of the addresses
+			for _, a := range addrs[20:80] {
+				ps.AddAddr(pid, a, time.Hour)
+			}
+		}()
+
+		// receive some concurrently with the goroutine
+		timeout = time.After(time.Second * 10)
+		for i := 0; i < 40; i++ {
+			select {
+			case <-addrch:
+			case <-timeout:
+			}
+		}
+
+		<-done
+
+		// receive some more after waiting for that goroutine to complete
+		timeout = time.After(time.Second * 10)
+		for i := 0; i < 20; i++ {
+			select {
+			case <-addrch:
+			case <-timeout:
+			}
+		}
+
+		// now cancel it
+		cancel()
+
+		// now check the *second* subscription. We should see 80 addresses.
+		for i := 0; i < 80; i++ {
+			<-addrch2
+		}
+
+		cancel2()
+
+		// and add a few more addresses it doesnt hang afterwards
+		for _, a := range addrs[80:] {
+			ps.AddAddr(pid, a, time.Hour)
+		}
+	}
+}
+
+func testGetStreamBeforePeerAdded(ps pstore.Peerstore) func(t *testing.T) {
+	return func(t *testing.T) {
+		addrs, pid := getAddrs(t, 10), peer.ID("testpeer")
+
+		ctx, cancel := context.WithCancel(context.Background())
+		defer cancel()
+
+		ach := ps.AddrStream(ctx, pid)
+		for i := 0; i < 10; i++ {
+			ps.AddAddr(pid, addrs[i], time.Hour)
+		}
+
+		received := make(map[string]bool)
+		var count int
+
+		for i := 0; i < 10; i++ {
+			a, ok := <-ach
+			if !ok {
+				t.Fatal("channel shouldnt be closed yet")
+			}
+			if a == nil {
+				t.Fatal("got a nil address, thats weird")
+			}
+			count++
+			if received[a.String()] {
+				t.Fatal("received duplicate address")
+			}
+			received[a.String()] = true
+		}
+
+		select {
+		case <-ach:
+			t.Fatal("shouldnt have received any more addresses")
+		default:
+		}
+
+		if count != 10 {
+			t.Fatal("should have received exactly ten addresses, got ", count)
+		}
+
+		for _, a := range addrs {
+			if !received[a.String()] {
+				t.Log(received)
+				t.Fatalf("expected to receive address %s but didnt", a)
+			}
+		}
+	}
+}
+
+func testAddrStreamDuplicates(ps pstore.Peerstore) func(t *testing.T) {
+	return func(t *testing.T) {
+		addrs, pid := getAddrs(t, 10), peer.ID("testpeer")
+
+		ctx, cancel := context.WithCancel(context.Background())
+		defer cancel()
+
+		ach := ps.AddrStream(ctx, pid)
+		go func() {
+			for i := 0; i < 10; i++ {
+				ps.AddAddr(pid, addrs[i], time.Hour)
+				ps.AddAddr(pid, addrs[rand.Intn(10)], time.Hour)
+			}
+
+			// make sure that all addresses get processed before context is cancelled
+			time.Sleep(time.Millisecond * 50)
+			cancel()
+		}()
+
+		received := make(map[string]bool)
+		var count int
+		for a := range ach {
+			if a == nil {
+				t.Fatal("got a nil address, thats weird")
+			}
+			count++
+			if received[a.String()] {
+				t.Fatal("received duplicate address")
+			}
+			received[a.String()] = true
+		}
+
+		if count != 10 {
+			t.Fatal("should have received exactly ten addresses")
+		}
+	}
+}
+
+func testPeerstoreProtoStore(ps pstore.Peerstore) func(t *testing.T) {
+	return func(t *testing.T) {
+		t.Run("adding and removing protocols", func(t *testing.T) {
+			p1 := peer.ID("TESTPEER")
+			protos := []string{"a", "b", "c", "d"}
+
+			require.NoError(t, ps.AddProtocols(p1, protos...))
+			out, err := ps.GetProtocols(p1)
+			require.NoError(t, err)
+			require.Len(t, out, len(protos), "got wrong number of protocols back")
+
+			sort.Strings(out)
+			for i, p := range protos {
+				if out[i] != p {
+					t.Fatal("got wrong protocol")
+				}
+			}
+
+			supported, err := ps.SupportsProtocols(p1, "q", "w", "a", "y", "b")
+			require.NoError(t, err)
+			require.Len(t, supported, 2, "only expected 2 supported")
+
+			if supported[0] != "a" || supported[1] != "b" {
+				t.Fatal("got wrong supported array: ", supported)
+			}
+
+			b, err := ps.FirstSupportedProtocol(p1, "q", "w", "a", "y", "b")
+			require.NoError(t, err)
+			require.Equal(t, "a", b)
+
+			b, err = ps.FirstSupportedProtocol(p1, "q", "x", "z")
+			require.NoError(t, err)
+			require.Empty(t, b)
+
+			b, err = ps.FirstSupportedProtocol(p1, "a")
+			require.NoError(t, err)
+			require.Equal(t, "a", b)
+
+			protos = []string{"other", "yet another", "one more"}
+			require.NoError(t, ps.SetProtocols(p1, protos...))
+
+			supported, err = ps.SupportsProtocols(p1, "q", "w", "a", "y", "b")
+			require.NoError(t, err)
+			require.Empty(t, supported, "none of those protocols should have been supported")
+
+			supported, err = ps.GetProtocols(p1)
+			require.NoError(t, err)
+
+			sort.Strings(supported)
+			sort.Strings(protos)
+			if !reflect.DeepEqual(supported, protos) {
+				t.Fatalf("expected previously set protos; expected: %v, have: %v", protos, supported)
+			}
+
+			require.NoError(t, ps.RemoveProtocols(p1, protos[:2]...))
+
+			supported, err = ps.GetProtocols(p1)
+			require.NoError(t, err)
+			if !reflect.DeepEqual(supported, protos[2:]) {
+				t.Fatal("expected only one protocol to remain")
+			}
+		})
+
+		t.Run("removing peer", func(t *testing.T) {
+			p := peer.ID("foobar")
+			protos := []string{"a", "b"}
+
+			require.NoError(t, ps.SetProtocols(p, protos...))
+			out, err := ps.GetProtocols(p)
+			require.NoError(t, err)
+			require.Len(t, out, 2)
+			ps.RemovePeer(p)
+			out, err = ps.GetProtocols(p)
+			require.NoError(t, err)
+			require.Empty(t, out)
+		})
+	}
+}
+
+func testBasicPeerstore(ps pstore.Peerstore) func(t *testing.T) {
+	return func(t *testing.T) {
+		var pids []peer.ID
+		addrs := getAddrs(t, 10)
+
+		for _, a := range addrs {
+			priv, _, err := crypto.GenerateKeyPair(crypto.RSA, 2048)
+			if err != nil {
+				t.Fatal(err)
+			}
+			p, err := peer.IDFromPrivateKey(priv)
+			if err != nil {
+				t.Fatal(err)
+			}
+			pids = append(pids, p)
+			ps.AddAddr(p, a, pstore.PermanentAddrTTL)
+		}
+
+		peers := ps.Peers()
+		if len(peers) != 10 {
+			t.Fatal("expected ten peers, got", len(peers))
+		}
+
+		pinfo := ps.PeerInfo(pids[0])
+		if !pinfo.Addrs[0].Equal(addrs[0]) {
+			t.Fatal("stored wrong address")
+		}
+	}
+}
+
+func testMetadata(ps pstore.Peerstore) func(t *testing.T) {
+	return func(t *testing.T) {
+		t.Run("putting and getting", func(t *testing.T) {
+			pids := make([]peer.ID, 3)
+			for i := range pids {
+				priv, _, err := crypto.GenerateKeyPair(crypto.RSA, 2048)
+				require.NoError(t, err)
+				p, err := peer.IDFromPrivateKey(priv)
+				require.NoError(t, err)
+				pids[i] = p
+			}
+			for _, p := range pids {
+				require.NoError(t, ps.Put(p, "AgentVersion", "string"), "failed to put AgentVersion")
+				require.NoError(t, ps.Put(p, "bar", 1), "failed to put bar")
+			}
+			for _, p := range pids {
+				v, err := ps.Get(p, "AgentVersion")
+				require.NoError(t, err)
+				require.Equal(t, v, "string")
+
+				v, err = ps.Get(p, "bar")
+				require.NoError(t, err)
+				require.Equal(t, v, 1)
+			}
+		})
+
+		t.Run("removing a peer", func(t *testing.T) {
+			p := peer.ID("foo")
+			otherP := peer.ID("foobar")
+			require.NoError(t, ps.Put(otherP, "AgentVersion", "v1"))
+			require.NoError(t, ps.Put(p, "AgentVersion", "v1"))
+			require.NoError(t, ps.Put(p, "bar", 1))
+			ps.RemovePeer(p)
+			_, err := ps.Get(p, "AgentVersion")
+			require.ErrorIs(t, err, pstore.ErrNotFound)
+			_, err = ps.Get(p, "bar")
+			require.ErrorIs(t, err, pstore.ErrNotFound)
+			// make sure that entries for otherP were not deleted
+			val, err := ps.Get(otherP, "AgentVersion")
+			require.NoError(t, err)
+			require.Equal(t, val, "v1")
+		})
+	}
+}
+
+func testCertifiedAddrBook(ps pstore.Peerstore) func(*testing.T) {
+	return func(t *testing.T) {
+		_, ok := ps.(pstore.CertifiedAddrBook)
+		if !ok {
+			t.Error("expected peerstore to implement CertifiedAddrBook interface")
+		}
+	}
+}
+
+func getAddrs(t *testing.T, n int) []ma.Multiaddr {
+	var addrs []ma.Multiaddr
+	for i := 0; i < n; i++ {
+		a, err := ma.NewMultiaddr(fmt.Sprintf("/ip4/127.0.0.1/tcp/%d", i))
+		if err != nil {
+			t.Fatal(err)
+		}
+
+		addrs = append(addrs, a)
+	}
+	return addrs
+}
+
+func TestPeerstoreProtoStoreLimits(t *testing.T, ps pstore.Peerstore, limit int) {
+	p := peer.ID("foobar")
+	protocols := make([]string, limit)
+	for i := 0; i < limit; i++ {
+		protocols[i] = fmt.Sprintf("protocol %d", i)
+	}
+
+	t.Run("setting protocols", func(t *testing.T) {
+		require.NoError(t, ps.SetProtocols(p, protocols...))
+		require.EqualError(t, ps.SetProtocols(p, append(protocols, "proto")...), "too many protocols")
+	})
+	t.Run("adding protocols", func(t *testing.T) {
+		p1 := protocols[:limit/2]
+		p2 := protocols[limit/2:]
+		require.NoError(t, ps.SetProtocols(p, p1...))
+		require.NoError(t, ps.AddProtocols(p, p2...))
+		require.EqualError(t, ps.AddProtocols(p, "proto"), "too many protocols")
+	})
+}
diff --git a/p2p/host/peerstore/test/utils.go b/p2p/host/peerstore/test/utils.go
new file mode 100644
index 00000000..c169894b
--- /dev/null
+++ b/p2p/host/peerstore/test/utils.go
@@ -0,0 +1,96 @@
+package test
+
+import (
+	"context"
+	"fmt"
+	"testing"
+
+	peer "github.com/libp2p/go-libp2p-core/peer"
+	pt "github.com/libp2p/go-libp2p-core/test"
+	ma "github.com/multiformats/go-multiaddr"
+)
+
+func Multiaddr(m string) ma.Multiaddr {
+	maddr, err := ma.NewMultiaddr(m)
+	if err != nil {
+		panic(err)
+	}
+	return maddr
+}
+
+type peerpair struct {
+	ID   peer.ID
+	Addr []ma.Multiaddr
+}
+
+func RandomPeer(b *testing.B, addrCount int) *peerpair {
+	var (
+		pid   peer.ID
+		err   error
+		addrs = make([]ma.Multiaddr, addrCount)
+		aFmt  = "/ip4/127.0.0.1/tcp/%d/ipfs/%s"
+	)
+
+	b.Helper()
+	if pid, err = pt.RandPeerID(); err != nil {
+		b.Fatal(err)
+	}
+
+	for i := 0; i < addrCount; i++ {
+		if addrs[i], err = ma.NewMultiaddr(fmt.Sprintf(aFmt, i, pid.Pretty())); err != nil {
+			b.Fatal(err)
+		}
+	}
+	return &peerpair{pid, addrs}
+}
+
+func AddressProducer(ctx context.Context, b *testing.B, addrs chan *peerpair, addrsPerPeer int) {
+	b.Helper()
+	defer close(addrs)
+	for {
+		p := RandomPeer(b, addrsPerPeer)
+		select {
+		case addrs <- p:
+		case <-ctx.Done():
+			return
+		}
+	}
+}
+
+func GenerateAddrs(count int) []ma.Multiaddr {
+	var addrs = make([]ma.Multiaddr, count)
+	for i := 0; i < count; i++ {
+		addrs[i] = Multiaddr(fmt.Sprintf("/ip4/1.1.1.%d/tcp/1111", i))
+	}
+	return addrs
+}
+
+func GeneratePeerIDs(count int) []peer.ID {
+	var ids = make([]peer.ID, count)
+	for i := 0; i < count; i++ {
+		ids[i], _ = pt.RandPeerID()
+	}
+	return ids
+}
+
+func AssertAddressesEqual(t *testing.T, exp, act []ma.Multiaddr) {
+	t.Helper()
+	if len(exp) != len(act) {
+		t.Fatalf("lengths not the same. expected %d, got %d\n", len(exp), len(act))
+	}
+
+	for _, a := range exp {
+		found := false
+
+		for _, b := range act {
+			if a.Equal(b) {
+				found = true
+				break
+			}
+		}
+
+		if !found {
+			t.Fatalf("expected address %s not found", a)
+		}
+	}
+}
diff --git a/p2p/net/swarm/dial_worker_test.go b/p2p/net/swarm/dial_worker_test.go
index a0752720..80235a74 100644
--- a/p2p/net/swarm/dial_worker_test.go
+++ b/p2p/net/swarm/dial_worker_test.go
@@ -8,6 +8,7 @@ import (
 	"testing"
 	"time"
 
+	"github.com/libp2p/go-libp2p/p2p/host/peerstore/pstoremem"
 	msmux "github.com/libp2p/go-libp2p/p2p/muxer/muxer-multistream"
 	"github.com/libp2p/go-libp2p/p2p/muxer/yamux"
 	csms "github.com/libp2p/go-libp2p/p2p/net/conn-security-multistream"
@@ -19,7 +20,6 @@ import (
 	"github.com/libp2p/go-libp2p-core/sec/insecure"
 	"github.com/libp2p/go-libp2p-core/transport"
 
-	"github.com/libp2p/go-libp2p-peerstore/pstoremem"
 	tnet "github.com/libp2p/go-libp2p-testing/net"
 	ma "github.com/multiformats/go-multiaddr"
 
diff --git a/p2p/net/swarm/testing/testing.go b/p2p/net/swarm/testing/testing.go
index bb470f11..b250fff5 100644
--- a/p2p/net/swarm/testing/testing.go
+++ b/p2p/net/swarm/testing/testing.go
@@ -4,6 +4,7 @@ import (
 	"testing"
 	"time"
 
+	"github.com/libp2p/go-libp2p/p2p/host/peerstore/pstoremem"
 	msmux "github.com/libp2p/go-libp2p/p2p/muxer/muxer-multistream"
 	"github.com/libp2p/go-libp2p/p2p/muxer/yamux"
 	csms "github.com/libp2p/go-libp2p/p2p/net/conn-security-multistream"
@@ -22,7 +23,6 @@ import (
 	"github.com/libp2p/go-libp2p-core/sec/insecure"
 	"github.com/libp2p/go-libp2p-core/transport"
 
-	"github.com/libp2p/go-libp2p-peerstore/pstoremem"
 	tnet "github.com/libp2p/go-libp2p-testing/net"
 	ma "github.com/multiformats/go-multiaddr"
 	"github.com/stretchr/testify/require"
diff --git a/p2p/protocol/circuitv2/relay/relay_test.go b/p2p/protocol/circuitv2/relay/relay_test.go
index b14271e5..78ed022c 100644
--- a/p2p/protocol/circuitv2/relay/relay_test.go
+++ b/p2p/protocol/circuitv2/relay/relay_test.go
@@ -10,6 +10,7 @@ import (
 	"time"
 
 	bhost "github.com/libp2p/go-libp2p/p2p/host/blank"
+	"github.com/libp2p/go-libp2p/p2p/host/peerstore/pstoremem"
 	"github.com/libp2p/go-libp2p/p2p/net/swarm"
 	swarmt "github.com/libp2p/go-libp2p/p2p/net/swarm/testing"
 	"github.com/libp2p/go-libp2p/p2p/protocol/circuitv2/client"
@@ -23,7 +24,6 @@ import (
 	"github.com/libp2p/go-libp2p-core/peer"
 	"github.com/libp2p/go-libp2p-core/transport"
 
-	"github.com/libp2p/go-libp2p-peerstore/pstoremem"
 	ma "github.com/multiformats/go-multiaddr"
 )
 
diff --git a/p2p/protocol/identify/id_test.go b/p2p/protocol/identify/id_test.go
index bc9474bb..b4411dbc 100644
--- a/p2p/protocol/identify/id_test.go
+++ b/p2p/protocol/identify/id_test.go
@@ -11,6 +11,7 @@ import (
 
 	"github.com/libp2p/go-libp2p"
 	blhost "github.com/libp2p/go-libp2p/p2p/host/blank"
+	"github.com/libp2p/go-libp2p/p2p/host/peerstore/pstoremem"
 	mocknet "github.com/libp2p/go-libp2p/p2p/net/mock"
 	"github.com/libp2p/go-libp2p/p2p/net/swarm"
 	swarmt "github.com/libp2p/go-libp2p/p2p/net/swarm/testing"
@@ -28,7 +29,6 @@ import (
 	coretest "github.com/libp2p/go-libp2p-core/test"
 
 	"github.com/libp2p/go-eventbus"
-	"github.com/libp2p/go-libp2p-peerstore/pstoremem"
 
 	mockClock "github.com/benbjohnson/clock"
 	logging "github.com/ipfs/go-log/v2"