Merge pull request #5941

1d21ba2 Scale up addrman (Pieter Wuille)
c6a63ce Always use a 50% chance to choose between tried and new entries (Pieter Wuille)
f68ba3f Do not bias outgoing connections towards fresh addresses (Pieter Wuille)
a8ff7c6 Simplify hashing code (Pieter Wuille)
e6b343d Make addrman's bucket placement deterministic. (Pieter Wuille)
b23add5 Switch addrman key from vector to uint256 (Pieter Wuille)

3 files changed, 260 insertions, 244 deletions

diff --git a/src/addrman.cpp b/src/addrman.cpp
index 4b7e4d51b9..5d9527f0e1 100644
--- a/src/addrman.cpp
+++ b/src/addrman.cpp
@@ -10,34 +10,27 @@
 
 using namespace std;
 
-int CAddrInfo::GetTriedBucket(const std::vector<unsigned char>& nKey) const
+int CAddrInfo::GetTriedBucket(const uint256& nKey) const
 {
-    CDataStream ss1(SER_GETHASH, 0);
-    std::vector<unsigned char> vchKey = GetKey();
-    ss1 << nKey << vchKey;
-    uint64_t hash1 = Hash(ss1.begin(), ss1.end()).GetCheapHash();
-
-    CDataStream ss2(SER_GETHASH, 0);
-    std::vector<unsigned char> vchGroupKey = GetGroup();
-    ss2 << nKey << vchGroupKey << (hash1 % ADDRMAN_TRIED_BUCKETS_PER_GROUP);
-    uint64_t hash2 = Hash(ss2.begin(), ss2.end()).GetCheapHash();
+    uint64_t hash1 = (CHashWriter(SER_GETHASH, 0) << nKey << GetKey()).GetHash().GetCheapHash();
+    uint64_t hash2 = (CHashWriter(SER_GETHASH, 0) << nKey << GetGroup() << (hash1 % ADDRMAN_TRIED_BUCKETS_PER_GROUP)).GetHash().GetCheapHash();
     return hash2 % ADDRMAN_TRIED_BUCKET_COUNT;
 }
 
-int CAddrInfo::GetNewBucket(const std::vector<unsigned char>& nKey, const CNetAddr& src) const
+int CAddrInfo::GetNewBucket(const uint256& nKey, const CNetAddr& src) const
 {
-    CDataStream ss1(SER_GETHASH, 0);
-    std::vector<unsigned char> vchGroupKey = GetGroup();
     std::vector<unsigned char> vchSourceGroupKey = src.GetGroup();
-    ss1 << nKey << vchGroupKey << vchSourceGroupKey;
-    uint64_t hash1 = Hash(ss1.begin(), ss1.end()).GetCheapHash();
-
-    CDataStream ss2(SER_GETHASH, 0);
-    ss2 << nKey << vchSourceGroupKey << (hash1 % ADDRMAN_NEW_BUCKETS_PER_SOURCE_GROUP);
-    uint64_t hash2 = Hash(ss2.begin(), ss2.end()).GetCheapHash();
+    uint64_t hash1 = (CHashWriter(SER_GETHASH, 0) << nKey << GetGroup() << vchSourceGroupKey).GetHash().GetCheapHash();
+    uint64_t hash2 = (CHashWriter(SER_GETHASH, 0) << nKey << vchSourceGroupKey << (hash1 % ADDRMAN_NEW_BUCKETS_PER_SOURCE_GROUP)).GetHash().GetCheapHash();
     return hash2 % ADDRMAN_NEW_BUCKET_COUNT;
 }
 
+int CAddrInfo::GetBucketPosition(const uint256 &nKey, bool fNew, int nBucket) const
+{
+    uint64_t hash1 = (CHashWriter(SER_GETHASH, 0) << nKey << (fNew ? 'N' : 'K') << nBucket << GetKey()).GetHash().GetCheapHash();
+    return hash1 % ADDRMAN_BUCKET_SIZE;
+}
+
 bool CAddrInfo::IsTerrible(int64_t nNow) const
 {
     if (nLastTry && nLastTry >= nNow - 60) // never remove things tried in the last minute
@@ -70,8 +63,6 @@ double CAddrInfo::GetChance(int64_t nNow) const
     if (nSinceLastTry < 0)
         nSinceLastTry = 0;
 
-    fChance *= 600.0 / (600.0 + nSinceLastSeen);
-
     // deprioritize very recent attempts away
     if (nSinceLastTry < 60 * 10)
         fChance *= 0.01;
@@ -128,85 +119,44 @@ void CAddrMan::SwapRandom(unsigned int nRndPos1, unsigned int nRndPos2)
     vRandom[nRndPos2] = nId1;
 }
 
-int CAddrMan::SelectTried(int nKBucket)
+void CAddrMan::Delete(int nId)
 {
-    std::vector<int>& vTried = vvTried[nKBucket];
-
-    // randomly shuffle the first few elements (using the entire list)
-    // find the least recently tried among them
-    int64_t nOldest = -1;
-    int nOldestPos = -1;
-    for (unsigned int i = 0; i < ADDRMAN_TRIED_ENTRIES_INSPECT_ON_EVICT && i < vTried.size(); i++) {
-        int nPos = GetRandInt(vTried.size() - i) + i;
-        int nTemp = vTried[nPos];
-        vTried[nPos] = vTried[i];
-        vTried[i] = nTemp;
-        assert(nOldest == -1 || mapInfo.count(nTemp) == 1);
-        if (nOldest == -1 || mapInfo[nTemp].nLastSuccess < mapInfo[nOldest].nLastSuccess) {
-            nOldest = nTemp;
-            nOldestPos = nPos;
-        }
-    }
+    assert(mapInfo.count(nId) != 0);
+    CAddrInfo& info = mapInfo[nId];
+    assert(!info.fInTried);
+    assert(info.nRefCount == 0);
 
-    return nOldestPos;
+    SwapRandom(info.nRandomPos, vRandom.size() - 1);
+    vRandom.pop_back();
+    mapAddr.erase(info);
+    mapInfo.erase(nId);
+    nNew--;
 }
 
-int CAddrMan::ShrinkNew(int nUBucket)
+void CAddrMan::ClearNew(int nUBucket, int nUBucketPos)
 {
-    assert(nUBucket >= 0 && (unsigned int)nUBucket < vvNew.size());
-    std::set<int>& vNew = vvNew[nUBucket];
-
-    // first look for deletable items
-    for (std::set<int>::iterator it = vNew.begin(); it != vNew.end(); it++) {
-        assert(mapInfo.count(*it));
-        CAddrInfo& info = mapInfo[*it];
-        if (info.IsTerrible()) {
-            if (--info.nRefCount == 0) {
-                SwapRandom(info.nRandomPos, vRandom.size() - 1);
-                vRandom.pop_back();
-                mapAddr.erase(info);
-                mapInfo.erase(*it);
-                nNew--;
-            }
-            vNew.erase(it);
-            return 0;
-        }
-    }
-
-    // otherwise, select four randomly, and pick the oldest of those to replace
-    int n[4] = {GetRandInt(vNew.size()), GetRandInt(vNew.size()), GetRandInt(vNew.size()), GetRandInt(vNew.size())};
-    int nI = 0;
-    int nOldest = -1;
-    for (std::set<int>::iterator it = vNew.begin(); it != vNew.end(); it++) {
-        if (nI == n[0] || nI == n[1] || nI == n[2] || nI == n[3]) {
-            assert(nOldest == -1 || mapInfo.count(*it) == 1);
-            if (nOldest == -1 || mapInfo[*it].nTime < mapInfo[nOldest].nTime)
-                nOldest = *it;
+    // if there is an entry in the specified bucket, delete it.
+    if (vvNew[nUBucket][nUBucketPos] != -1) {
+        int nIdDelete = vvNew[nUBucket][nUBucketPos];
+        CAddrInfo& infoDelete = mapInfo[nIdDelete];
+        assert(infoDelete.nRefCount > 0);
+        infoDelete.nRefCount--;
+        vvNew[nUBucket][nUBucketPos] = -1;
+        if (infoDelete.nRefCount == 0) {
+            Delete(nIdDelete);
         }
-        nI++;
-    }
-    assert(mapInfo.count(nOldest) == 1);
-    CAddrInfo& info = mapInfo[nOldest];
-    if (--info.nRefCount == 0) {
-        SwapRandom(info.nRandomPos, vRandom.size() - 1);
-        vRandom.pop_back();
-        mapAddr.erase(info);
-        mapInfo.erase(nOldest);
-        nNew--;
     }
-    vNew.erase(nOldest);
-
-    return 1;
 }
 
-void CAddrMan::MakeTried(CAddrInfo& info, int nId, int nOrigin)
+void CAddrMan::MakeTried(CAddrInfo& info, int nId)
 {
-    assert(vvNew[nOrigin].count(nId) == 1);
-
     // remove the entry from all new buckets
-    for (std::vector<std::set<int> >::iterator it = vvNew.begin(); it != vvNew.end(); it++) {
-        if ((*it).erase(nId))
+    for (int bucket = 0; bucket < ADDRMAN_NEW_BUCKET_COUNT; bucket++) {
+        int pos = info.GetBucketPosition(nKey, true, bucket);
+        if (vvNew[bucket][pos] == nId) {
+            vvNew[bucket][pos] = -1;
             info.nRefCount--;
+        }
     }
     nNew--;
 
@@ -214,44 +164,36 @@ void CAddrMan::MakeTried(CAddrInfo& info, int nId, int nOrigin)
 
     // which tried bucket to move the entry to
     int nKBucket = info.GetTriedBucket(nKey);
-    std::vector<int>& vTried = vvTried[nKBucket];
-
-    // first check whether there is place to just add it
-    if (vTried.size() < ADDRMAN_TRIED_BUCKET_SIZE) {
-        vTried.push_back(nId);
-        nTried++;
-        info.fInTried = true;
-        return;
-    }
-
-    // otherwise, find an item to evict
-    int nPos = SelectTried(nKBucket);
-
-    // find which new bucket it belongs to
-    assert(mapInfo.count(vTried[nPos]) == 1);
-    int nUBucket = mapInfo[vTried[nPos]].GetNewBucket(nKey);
-    std::set<int>& vNew = vvNew[nUBucket];
-
-    // remove the to-be-replaced tried entry from the tried set
-    CAddrInfo& infoOld = mapInfo[vTried[nPos]];
-    infoOld.fInTried = false;
-    infoOld.nRefCount = 1;
-    // do not update nTried, as we are going to move something else there immediately
-
-    // check whether there is place in that one,
-    if (vNew.size() < ADDRMAN_NEW_BUCKET_SIZE) {
-        // if so, move it back there
-        vNew.insert(vTried[nPos]);
-    } else {
-        // otherwise, move it to the new bucket nId came from (there is certainly place there)
-        vvNew[nOrigin].insert(vTried[nPos]);
+    int nKBucketPos = info.GetBucketPosition(nKey, false, nKBucket);
+
+    // first make space to add it (the existing tried entry there is moved to new, deleting whatever is there).
+    if (vvTried[nKBucket][nKBucketPos] != -1) {
+        // find an item to evict
+        int nIdEvict = vvTried[nKBucket][nKBucketPos];
+        assert(mapInfo.count(nIdEvict) == 1);
+        CAddrInfo& infoOld = mapInfo[nIdEvict];
+
+        // Remove the to-be-evicted item from the tried set.
+        infoOld.fInTried = false;
+        vvTried[nKBucket][nKBucketPos] = -1;
+        nTried--;
+
+        // find which new bucket it belongs to
+        int nUBucket = infoOld.GetNewBucket(nKey);
+        int nUBucketPos = infoOld.GetBucketPosition(nKey, true, nUBucket);
+        ClearNew(nUBucket, nUBucketPos);
+        assert(vvNew[nUBucket][nUBucketPos] == -1);
+
+        // Enter it into the new set again.
+        infoOld.nRefCount = 1;
+        vvNew[nUBucket][nUBucketPos] = nIdEvict;
+        nNew++;
     }
-    nNew++;
+    assert(vvTried[nKBucket][nKBucketPos] == -1);
 
-    vTried[nPos] = nId;
-    // we just overwrote an entry in vTried; no need to update nTried
+    vvTried[nKBucket][nKBucketPos] = nId;
+    nTried++;
     info.fInTried = true;
-    return;
 }
 
 void CAddrMan::Good_(const CService& addr, int64_t nTime)
@@ -281,12 +223,12 @@ void CAddrMan::Good_(const CService& addr, int64_t nTime)
         return;
 
     // find a bucket it is in now
-    int nRnd = GetRandInt(vvNew.size());
+    int nRnd = GetRandInt(ADDRMAN_NEW_BUCKET_COUNT);
     int nUBucket = -1;
-    for (unsigned int n = 0; n < vvNew.size(); n++) {
-        int nB = (n + nRnd) % vvNew.size();
-        std::set<int>& vNew = vvNew[nB];
-        if (vNew.count(nId)) {
+    for (unsigned int n = 0; n < ADDRMAN_NEW_BUCKET_COUNT; n++) {
+        int nB = (n + nRnd) % ADDRMAN_NEW_BUCKET_COUNT;
+        int nBpos = info.GetBucketPosition(nKey, true, nB);
+        if (vvNew[nB][nBpos] == nId) {
             nUBucket = nB;
             break;
         }
@@ -300,7 +242,7 @@ void CAddrMan::Good_(const CService& addr, int64_t nTime)
     LogPrint("addrman", "Moving %s to tried\n", addr.ToString());
 
     // move nId to the tried tables
-    MakeTried(info, nId, nUBucket);
+    MakeTried(info, nId);
 }
 
 bool CAddrMan::Add_(const CAddress& addr, const CNetAddr& source, int64_t nTimePenalty)
@@ -348,12 +290,25 @@ bool CAddrMan::Add_(const CAddress& addr, const CNetAddr& source, int64_t nTimeP
     }
 
     int nUBucket = pinfo->GetNewBucket(nKey, source);
-    std::set<int>& vNew = vvNew[nUBucket];
-    if (!vNew.count(nId)) {
-        pinfo->nRefCount++;
-        if (vNew.size() == ADDRMAN_NEW_BUCKET_SIZE)
-            ShrinkNew(nUBucket);
-        vvNew[nUBucket].insert(nId);
+    int nUBucketPos = pinfo->GetBucketPosition(nKey, true, nUBucket);
+    if (vvNew[nUBucket][nUBucketPos] != nId) {
+        bool fInsert = vvNew[nUBucket][nUBucketPos] == -1;
+        if (!fInsert) {
+            CAddrInfo& infoExisting = mapInfo[vvNew[nUBucket][nUBucketPos]];
+            if (infoExisting.IsTerrible() || (infoExisting.nRefCount > 1 && pinfo->nRefCount == 0)) {
+                // Overwrite the existing new table entry.
+                fInsert = true;
+            }
+        }
+        if (fInsert) {
+            ClearNew(nUBucket, nUBucketPos);
+            pinfo->nRefCount++;
+            vvNew[nUBucket][nUBucketPos] = nId;
+        } else {
+            if (pinfo->nRefCount == 0) {
+                Delete(nId);
+            }
+        }
     }
     return fNew;
 }
@@ -377,24 +332,23 @@ void CAddrMan::Attempt_(const CService& addr, int64_t nTime)
     info.nAttempts++;
 }
 
-CAddress CAddrMan::Select_(int nUnkBias)
+CAddress CAddrMan::Select_()
 {
     if (size() == 0)
         return CAddress();
 
-    double nCorTried = sqrt(nTried) * (100.0 - nUnkBias);
-    double nCorNew = sqrt(nNew) * nUnkBias;
-    if ((nCorTried + nCorNew) * GetRandInt(1 << 30) / (1 << 30) < nCorTried) {
+    // Use a 50% chance for choosing between tried and new table entries.
+    if (nTried > 0 && (nNew == 0 || GetRandInt(2) == 0)) {
         // use a tried node
         double fChanceFactor = 1.0;
         while (1) {
-            int nKBucket = GetRandInt(vvTried.size());
-            std::vector<int>& vTried = vvTried[nKBucket];
-            if (vTried.size() == 0)
+            int nKBucket = GetRandInt(ADDRMAN_TRIED_BUCKET_COUNT);
+            int nKBucketPos = GetRandInt(ADDRMAN_BUCKET_SIZE);
+            if (vvTried[nKBucket][nKBucketPos] == -1)
                 continue;
-            int nPos = GetRandInt(vTried.size());
-            assert(mapInfo.count(vTried[nPos]) == 1);
-            CAddrInfo& info = mapInfo[vTried[nPos]];
+            int nId = vvTried[nKBucket][nKBucketPos];
+            assert(mapInfo.count(nId) == 1);
+            CAddrInfo& info = mapInfo[nId];
             if (GetRandInt(1 << 30) < fChanceFactor * info.GetChance() * (1 << 30))
                 return info;
             fChanceFactor *= 1.2;
@@ -403,16 +357,13 @@ CAddress CAddrMan::Select_(int nUnkBias)
         // use a new node
         double fChanceFactor = 1.0;
         while (1) {
-            int nUBucket = GetRandInt(vvNew.size());
-            std::set<int>& vNew = vvNew[nUBucket];
-            if (vNew.size() == 0)
+            int nUBucket = GetRandInt(ADDRMAN_NEW_BUCKET_COUNT);
+            int nUBucketPos = GetRandInt(ADDRMAN_BUCKET_SIZE);
+            if (vvNew[nUBucket][nUBucketPos] == -1)
                 continue;
-            int nPos = GetRandInt(vNew.size());
-            std::set<int>::iterator it = vNew.begin();
-            while (nPos--)
-                it++;
-            assert(mapInfo.count(*it) == 1);
-            CAddrInfo& info = mapInfo[*it];
+            int nId = vvNew[nUBucket][nUBucketPos];
+            assert(mapInfo.count(nId) == 1);
+            CAddrInfo& info = mapInfo[nId];
             if (GetRandInt(1 << 30) < fChanceFactor * info.GetChance() * (1 << 30))
                 return info;
             fChanceFactor *= 1.2;
@@ -460,22 +411,30 @@ int CAddrMan::Check_()
     if (mapNew.size() != nNew)
         return -10;
 
-    for (int n = 0; n < vvTried.size(); n++) {
-        std::vector<int>& vTried = vvTried[n];
-        for (std::vector<int>::iterator it = vTried.begin(); it != vTried.end(); it++) {
-            if (!setTried.count(*it))
-                return -11;
-            setTried.erase(*it);
+    for (int n = 0; n < ADDRMAN_TRIED_BUCKET_COUNT; n++) {
+        for (int i = 0; i < ADDRMAN_BUCKET_SIZE; i++) {
+             if (vvTried[n][i] != -1) {
+                 if (!setTried.count(vvTried[n][i]))
+                     return -11;
+                 if (mapInfo[vvTried[n][i]].GetTriedBucket(nKey) != n)
+                     return -17;
+                 if (mapInfo[vvTried[n][i]].GetBucketPosition(nKey, false, n) != i)
+                     return -18;
+                 setTried.erase(vvTried[n][i]);
+             }
         }
     }
 
-    for (int n = 0; n < vvNew.size(); n++) {
-        std::set<int>& vNew = vvNew[n];
-        for (std::set<int>::iterator it = vNew.begin(); it != vNew.end(); it++) {
-            if (!mapNew.count(*it))
-                return -12;
-            if (--mapNew[*it] == 0)
-                mapNew.erase(*it);
+    for (int n = 0; n < ADDRMAN_NEW_BUCKET_COUNT; n++) {
+        for (int i = 0; i < ADDRMAN_BUCKET_SIZE; i++) {
+            if (vvNew[n][i] != -1) {
+                if (!mapNew.count(vvNew[n][i]))
+                    return -12;
+                if (mapInfo[vvNew[n][i]].GetBucketPosition(nKey, true, n) != i)
+                    return -19;
+                if (--mapNew[vvNew[n][i]] == 0)
+                    mapNew.erase(vvNew[n][i]);
+            }
         }
     }
 
@@ -483,6 +442,8 @@ int CAddrMan::Check_()
         return -13;
     if (mapNew.size())
         return -15;
+    if (nKey.IsNull())
+        return -16;
 
     return 0;
 }
diff --git a/src/addrman.h b/src/addrman.h
index d47217683c..8116d0b763 100644
--- a/src/addrman.h
+++ b/src/addrman.h
@@ -79,17 +79,20 @@ public:
     }
 
     //! Calculate in which "tried" bucket this entry belongs
-    int GetTriedBucket(const std::vector<unsigned char> &nKey) const;
+    int GetTriedBucket(const uint256 &nKey) const;
 
     //! Calculate in which "new" bucket this entry belongs, given a certain source
-    int GetNewBucket(const std::vector<unsigned char> &nKey, const CNetAddr& src) const;
+    int GetNewBucket(const uint256 &nKey, const CNetAddr& src) const;
 
     //! Calculate in which "new" bucket this entry belongs, using its default source
-    int GetNewBucket(const std::vector<unsigned char> &nKey) const
+    int GetNewBucket(const uint256 &nKey) const
     {
         return GetNewBucket(nKey, source);
     }
 
+    //! Calculate in which position of a bucket to store this entry.
+    int GetBucketPosition(const uint256 &nKey, bool fNew, int nBucket) const;
+
     //! Determine whether the statistics about this entry are bad enough so that it can just be deleted
     bool IsTerrible(int64_t nNow = GetAdjustedTime()) const;
 
@@ -106,15 +109,15 @@ public:
  *
  * To that end:
  *  * Addresses are organized into buckets.
- *    * Address that have not yet been tried go into 256 "new" buckets.
- *      * Based on the address range (/16 for IPv4) of source of the information, 32 buckets are selected at random
+ *    * Address that have not yet been tried go into 1024 "new" buckets.
+ *      * Based on the address range (/16 for IPv4) of source of the information, 64 buckets are selected at random
  *      * The actual bucket is chosen from one of these, based on the range the address itself is located.
- *      * One single address can occur in up to 4 different buckets, to increase selection chances for addresses that
+ *      * One single address can occur in up to 8 different buckets, to increase selection chances for addresses that
  *        are seen frequently. The chance for increasing this multiplicity decreases exponentially.
  *      * When adding a new address to a full bucket, a randomly chosen entry (with a bias favoring less recently seen
  *        ones) is removed from it first.
- *    * Addresses of nodes that are known to be accessible go into 64 "tried" buckets.
- *      * Each address range selects at random 4 of these buckets.
+ *    * Addresses of nodes that are known to be accessible go into 256 "tried" buckets.
+ *      * Each address range selects at random 8 of these buckets.
  *      * The actual bucket is chosen from one of these, based on the full address.
  *      * When adding a new good address to a full bucket, a randomly chosen entry (with a bias favoring less recently
  *        tried ones) is evicted from it, back to the "new" buckets.
@@ -125,28 +128,22 @@ public:
  */
 
 //! total number of buckets for tried addresses
-#define ADDRMAN_TRIED_BUCKET_COUNT 64
-
-//! maximum allowed number of entries in buckets for tried addresses
-#define ADDRMAN_TRIED_BUCKET_SIZE 64
+#define ADDRMAN_TRIED_BUCKET_COUNT 256
 
 //! total number of buckets for new addresses
-#define ADDRMAN_NEW_BUCKET_COUNT 256
+#define ADDRMAN_NEW_BUCKET_COUNT 1024
 
-//! maximum allowed number of entries in buckets for new addresses
-#define ADDRMAN_NEW_BUCKET_SIZE 64
+//! maximum allowed number of entries in buckets for new and tried addresses
+#define ADDRMAN_BUCKET_SIZE 64
 
 //! over how many buckets entries with tried addresses from a single group (/16 for IPv4) are spread
-#define ADDRMAN_TRIED_BUCKETS_PER_GROUP 4
+#define ADDRMAN_TRIED_BUCKETS_PER_GROUP 8
 
 //! over how many buckets entries with new addresses originating from a single group are spread
-#define ADDRMAN_NEW_BUCKETS_PER_SOURCE_GROUP 32
+#define ADDRMAN_NEW_BUCKETS_PER_SOURCE_GROUP 64
 
 //! in how many buckets for entries with new addresses a single address may occur
-#define ADDRMAN_NEW_BUCKETS_PER_ADDRESS 4
-
-//! how many entries in a bucket with tried addresses are inspected, when selecting one to replace
-#define ADDRMAN_TRIED_ENTRIES_INSPECT_ON_EVICT 4
+#define ADDRMAN_NEW_BUCKETS_PER_ADDRESS 8
 
 //! how old addresses can maximally be
 #define ADDRMAN_HORIZON_DAYS 30
@@ -176,7 +173,7 @@ private:
     mutable CCriticalSection cs;
 
     //! secret key to randomize bucket select with
-    std::vector<unsigned char> nKey;
+    uint256 nKey;
 
     //! last used nId
     int nIdCount;
@@ -194,13 +191,13 @@ private:
     int nTried;
 
     //! list of "tried" buckets
-    std::vector<std::vector<int> > vvTried;
+    int vvTried[ADDRMAN_TRIED_BUCKET_COUNT][ADDRMAN_BUCKET_SIZE];
 
     //! number of (unique) "new" entries
     int nNew;
 
     //! list of "new" buckets
-    std::vector<std::set<int> > vvNew;
+    int vvNew[ADDRMAN_NEW_BUCKET_COUNT][ADDRMAN_BUCKET_SIZE];
 
 protected:
 
@@ -214,17 +211,14 @@ protected:
     //! Swap two elements in vRandom.
     void SwapRandom(unsigned int nRandomPos1, unsigned int nRandomPos2);
 
-    //! Return position in given bucket to replace.
-    int SelectTried(int nKBucket);
+    //! Move an entry from the "new" table(s) to the "tried" table
+    void MakeTried(CAddrInfo& info, int nId);
 
-    //! Remove an element from a "new" bucket.
-    //! This is the only place where actual deletions occur.
-    //! Elements are never deleted while in the "tried" table, only possibly evicted back to the "new" table.
-    int ShrinkNew(int nUBucket);
+    //! Delete an entry. It must not be in tried, and have refcount 0.
+    void Delete(int nId);
 
-    //! Move an entry from the "new" table(s) to the "tried" table
-    //! @pre vvUnkown[nOrigin].count(nId) != 0
-    void MakeTried(CAddrInfo& info, int nId, int nOrigin);
+    //! Clear a position in a "new" table. This is the only place where entries are actually deleted.
+    void ClearNew(int nUBucket, int nUBucketPos);
 
     //! Mark an entry "good", possibly moving it from "new" to "tried".
     void Good_(const CService &addr, int64_t nTime);
@@ -237,7 +231,7 @@ protected:
 
     //! Select an address to connect to.
     //! nUnkBias determines how much to favor new addresses over tried ones (min=0, max=100)
-    CAddress Select_(int nUnkBias);
+    CAddress Select_();
 
 #ifdef DEBUG_ADDRMAN
     //! Perform consistency check. Returns an error code or zero.
@@ -253,17 +247,21 @@ protected:
 public:
     /**
      * serialized format:
-     * * version byte (currently 0)
-     * * nKey
+     * * version byte (currently 1)
+     * * 0x20 + nKey (serialized as if it were a vector, for backward compatibility)
      * * nNew
      * * nTried
-     * * number of "new" buckets
+     * * number of "new" buckets XOR 2**30
      * * all nNew addrinfos in vvNew
      * * all nTried addrinfos in vvTried
      * * for each bucket:
      *   * number of elements
      *   * for each element: index
      *
+     * 2**30 is xorred with the number of buckets to make addrman deserializer v0 detect it
+     * as incompatible. This is necessary because it did not check the version number on
+     * deserialization.
+     *
      * Notice that vvTried, mapAddr and vVector are never encoded explicitly;
      * they are instead reconstructed from the other information.
      *
@@ -275,48 +273,53 @@ public:
      *
      * We don't use ADD_SERIALIZE_METHODS since the serialization and deserialization code has
      * very little in common.
-     *
      */
     template<typename Stream>
     void Serialize(Stream &s, int nType, int nVersionDummy) const
     {
         LOCK(cs);
 
-        unsigned char nVersion = 0;
+        unsigned char nVersion = 1;
         s << nVersion;
+        s << ((unsigned char)32);
         s << nKey;
         s << nNew;
         s << nTried;
 
-        int nUBuckets = ADDRMAN_NEW_BUCKET_COUNT;
+        int nUBuckets = ADDRMAN_NEW_BUCKET_COUNT ^ (1 << 30);
         s << nUBuckets;
         std::map<int, int> mapUnkIds;
         int nIds = 0;
         for (std::map<int, CAddrInfo>::const_iterator it = mapInfo.begin(); it != mapInfo.end(); it++) {
-            if (nIds == nNew) break; // this means nNew was wrong, oh ow
             mapUnkIds[(*it).first] = nIds;
             const CAddrInfo &info = (*it).second;
             if (info.nRefCount) {
+                assert(nIds != nNew); // this means nNew was wrong, oh ow
                 s << info;
                 nIds++;
             }
         }
         nIds = 0;
         for (std::map<int, CAddrInfo>::const_iterator it = mapInfo.begin(); it != mapInfo.end(); it++) {
-            if (nIds == nTried) break; // this means nTried was wrong, oh ow
             const CAddrInfo &info = (*it).second;
             if (info.fInTried) {
+                assert(nIds != nTried); // this means nTried was wrong, oh ow
                 s << info;
                 nIds++;
             }
         }
-        for (std::vector<std::set<int> >::const_iterator it = vvNew.begin(); it != vvNew.end(); it++) {
-            const std::set<int> &vNew = (*it);
-            int nSize = vNew.size();
+        for (int bucket = 0; bucket < ADDRMAN_NEW_BUCKET_COUNT; bucket++) {
+            int nSize = 0;
+            for (int i = 0; i < ADDRMAN_BUCKET_SIZE; i++) {
+                if (vvNew[bucket][i] != -1)
+                    nSize++;
+            }
             s << nSize;
-            for (std::set<int>::const_iterator it2 = vNew.begin(); it2 != vNew.end(); it2++) {
-                int nIndex = mapUnkIds[*it2];
-                s << nIndex;
+            for (int i = 0; i < ADDRMAN_BUCKET_SIZE; i++) {
+                if (vvNew[bucket][i] != -1) {
+                    int nIndex = mapUnkIds[vvNew[bucket][i]];
+                    s << nIndex;
+                }
             }
         }
     }
@@ -326,64 +329,97 @@ public:
     {
         LOCK(cs);
 
+        Clear();
+
         unsigned char nVersion;
         s >> nVersion;
+        unsigned char nKeySize;
+        s >> nKeySize;
+        if (nKeySize != 32) throw std::ios_base::failure("Incorrect keysize in addrman deserialization");
         s >> nKey;
         s >> nNew;
         s >> nTried;
-
         int nUBuckets = 0;
         s >> nUBuckets;
-        nIdCount = 0;
-        mapInfo.clear();
-        mapAddr.clear();
-        vRandom.clear();
-        vvTried = std::vector<std::vector<int> >(ADDRMAN_TRIED_BUCKET_COUNT, std::vector<int>(0));
-        vvNew = std::vector<std::set<int> >(ADDRMAN_NEW_BUCKET_COUNT, std::set<int>());
+        if (nVersion != 0) {
+            nUBuckets ^= (1 << 30);
+        }
+
+        // Deserialize entries from the new table.
         for (int n = 0; n < nNew; n++) {
             CAddrInfo &info = mapInfo[n];
             s >> info;
             mapAddr[info] = n;
             info.nRandomPos = vRandom.size();
             vRandom.push_back(n);
-            if (nUBuckets != ADDRMAN_NEW_BUCKET_COUNT) {
-                vvNew[info.GetNewBucket(nKey)].insert(n);
-                info.nRefCount++;
+            if (nVersion != 1 || nUBuckets != ADDRMAN_NEW_BUCKET_COUNT) {
+                // In case the new table data cannot be used (nVersion unknown, or bucket count wrong),
+                // immediately try to give them a reference based on their primary source address.
+                int nUBucket = info.GetNewBucket(nKey);
+                int nUBucketPos = info.GetBucketPosition(nKey, true, nUBucket);
+                if (vvNew[nUBucket][nUBucketPos] == -1) {
+                    vvNew[nUBucket][nUBucketPos] = n;
+                    info.nRefCount++;
+                }
             }
         }
         nIdCount = nNew;
+
+        // Deserialize entries from the tried table.
         int nLost = 0;
         for (int n = 0; n < nTried; n++) {
             CAddrInfo info;
             s >> info;
-            std::vector<int> &vTried = vvTried[info.GetTriedBucket(nKey)];
-            if (vTried.size() < ADDRMAN_TRIED_BUCKET_SIZE) {
+            int nKBucket = info.GetTriedBucket(nKey);
+            int nKBucketPos = info.GetBucketPosition(nKey, false, nKBucket);
+            if (vvTried[nKBucket][nKBucketPos] == -1) {
                 info.nRandomPos = vRandom.size();
                 info.fInTried = true;
                 vRandom.push_back(nIdCount);
                 mapInfo[nIdCount] = info;
                 mapAddr[info] = nIdCount;
-                vTried.push_back(nIdCount);
+                vvTried[nKBucket][nKBucketPos] = nIdCount;
                 nIdCount++;
             } else {
                 nLost++;
             }
         }
         nTried -= nLost;
-        for (int b = 0; b < nUBuckets; b++) {
-            std::set<int> &vNew = vvNew[b];
+
+        // Deserialize positions in the new table (if possible).
+        for (int bucket = 0; bucket < nUBuckets; bucket++) {
             int nSize = 0;
             s >> nSize;
             for (int n = 0; n < nSize; n++) {
                 int nIndex = 0;
                 s >> nIndex;
-                CAddrInfo &info = mapInfo[nIndex];
-                if (nUBuckets == ADDRMAN_NEW_BUCKET_COUNT && info.nRefCount < ADDRMAN_NEW_BUCKETS_PER_ADDRESS) {
-                    info.nRefCount++;
-                    vNew.insert(nIndex);
+                if (nIndex >= 0 && nIndex < nNew) {
+                    CAddrInfo &info = mapInfo[nIndex];
+                    int nUBucketPos = info.GetBucketPosition(nKey, true, bucket);
+                    if (nVersion == 1 && nUBuckets == ADDRMAN_NEW_BUCKET_COUNT && vvNew[bucket][nUBucketPos] == -1 && info.nRefCount < ADDRMAN_NEW_BUCKETS_PER_ADDRESS) {
+                        info.nRefCount++;
+                        vvNew[bucket][nUBucketPos] = nIndex;
+                    }
                 }
             }
         }
+
+        // Prune new entries with refcount 0 (as a result of collisions).
+        int nLostUnk = 0;
+        for (std::map<int, CAddrInfo>::const_iterator it = mapInfo.begin(); it != mapInfo.end(); ) {
+            if (it->second.fInTried == false && it->second.nRefCount == 0) {
+                std::map<int, CAddrInfo>::const_iterator itCopy = it++;
+                Delete(itCopy->first);
+                nLostUnk++;
+            } else {
+                it++;
+            }
+        }
+        if (nLost + nLostUnk > 0) {
+            LogPrint("addrman", "addrman lost %i new and %i tried addresses due to collisions\n", nLostUnk, nLost);
+        }
+
+        Check();
     }
 
     unsigned int GetSerializeSize(int nType, int nVersion) const
@@ -391,14 +427,34 @@ public:
         return (CSizeComputer(nType, nVersion) << *this).size();
     }
 
-    CAddrMan() : vRandom(0), vvTried(ADDRMAN_TRIED_BUCKET_COUNT, std::vector<int>(0)), vvNew(ADDRMAN_NEW_BUCKET_COUNT, std::set<int>())
+    void Clear()
     {
-         nKey.resize(32);
-         GetRandBytes(&nKey[0], 32);
+        std::vector<int>().swap(vRandom);
+        nKey = GetRandHash();
+        for (size_t bucket = 0; bucket < ADDRMAN_NEW_BUCKET_COUNT; bucket++) {
+            for (size_t entry = 0; entry < ADDRMAN_BUCKET_SIZE; entry++) {
+                vvNew[bucket][entry] = -1;
+            }
+        }
+        for (size_t bucket = 0; bucket < ADDRMAN_TRIED_BUCKET_COUNT; bucket++) {
+            for (size_t entry = 0; entry < ADDRMAN_BUCKET_SIZE; entry++) {
+                vvTried[bucket][entry] = -1;
+            }
+        }
+
+        nIdCount = 0;
+        nTried = 0;
+        nNew = 0;
+    }
 
-         nIdCount = 0;
-         nTried = 0;
-         nNew = 0;
+    CAddrMan()
+    {
+        Clear();
+    }
+
+    ~CAddrMan()
+    {
+        nKey.SetNull();
     }
 
     //! Return the number of (unique) addresses in all tables.
@@ -477,13 +533,13 @@ public:
      * Choose an address to connect to.
      * nUnkBias determines how much "new" entries are favored over "tried" ones (0-100).
      */
-    CAddress Select(int nUnkBias = 50)
+    CAddress Select()
     {
         CAddress addrRet;
         {
             LOCK(cs);
             Check();
-            addrRet = Select_(nUnkBias);
+            addrRet = Select_();
             Check();
         }
         return addrRet;
diff --git a/src/net.cpp b/src/net.cpp
index 11c2cd07d9..48e6367f20 100644
--- a/src/net.cpp
+++ b/src/net.cpp
@@ -1221,8 +1221,7 @@ void ThreadOpenConnections()
         int nTries = 0;
         while (true)
         {
-            // use an nUnkBias between 10 (no outgoing connections) and 90 (8 outgoing connections)
-            CAddress addr = addrman.Select(10 + min(nOutbound,8)*10);
+            CAddress addr = addrman.Select();
 
             // if we selected an invalid address, restart
             if (!addr.IsValid() || setConnected.count(addr.GetGroup()) || IsLocal(addr))