Re: [Bitcoin-development] Speeding up "getbalance <account>" calls

["Jan Vornberger" <jan@uos.de>]

[-- Attachment #1: Type: text/plain, Size: 1741 bytes --]

Hey!

John Smith wrote:
> I think the easiest way to speed this up would be to scan the wallet every
> time a block comes in or something else changes in the block chain (or, if
> you prefer, some pre-set interval of N minutes). Then go over the entire
> wallet and the accumulate balances for all accounts. This could be done in
> amortized linear time using a hash_map.

That was a good suggestion - thanks! I implemented it along these lines
and now the Instawallet server can breath again. Well, more or less at
least, as now "sendfrom" starts acting up and I have to look into that
next.

Here is a branch with the code for the cache:
https://github.com/javgh/bitcoin/tree/balancecache . It's currently based
on a somewhat old version of the codebase as I'm running with a number of
other modifications. So it won't easily apply to something newer. I hope
to be able to switch to a recent version at some point (mostly hoping for
some improvements in the fee handling area before I do that) and then I
can hopefully provide a cleaner version of this patch. For now, I just
document it here for anyone who might need this as well and can piece it
together themselves (I attached a patch file).

Basically I create a list of all account balances every time a new a new
block comes in or a transaction that affects my wallet appears. The list
is stored in a "map" right now. This seems fast enough for me. I didn't
use a hash map for now, because I'm fairly new to C++ and was a little
confused on what to use (is there a "standard" hash map to use in the STL?
or do people use boost or what?). But my VPS is low on memory anyway, so I
guess that's kind of a justification as well to go for a tree-based
implementation of map.

Cheers!
Jan

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: balancecache.patch --]
[-- Type: text/x-patch; name="balancecache.patch", Size: 8184 bytes --]

diff --git a/init.cpp b/init.cpp
index bac4b28..948c11e 100644
--- a/init.cpp
+++ b/init.cpp
@@ -503,6 +503,9 @@ bool AppInit2(int argc, char* argv[])
 
     RandAddSeedPerfmon();
 
+    // build initial balance cache
+    CreateAccountBalanceCache();
+
     if (!CreateThread(StartNode, NULL))
         wxMessageBox("Error: CreateThread(StartNode) failed", "Bitcoin");
 
diff --git a/main.cpp b/main.cpp
index cebe97b..3e66bb9 100644
--- a/main.cpp
+++ b/main.cpp
@@ -52,6 +52,9 @@ CCriticalSection cs_mapRequestCount;
 map<string, string> mapAddressBook;
 CCriticalSection cs_mapAddressBook;
 
+map<pair<string, int>, int64> mapAccountBalanceCache;
+CCriticalSection cs_mapAccountBalanceCache;
+
 vector<unsigned char> vchDefaultKey;
 
 CCriticalSection cs_mapMonitored;
@@ -109,6 +112,55 @@ vector<unsigned char> GenerateNewKey()
 }
 
 
+//////////////////////////////////////////////////////////////////////////////
+//
+// mapAccountBalanceCache
+//
+
+void CreateAccountBalanceCache() 
+{
+    CRITICAL_BLOCK(cs_mapAccountBalanceCache)
+    {
+        printf("Rebuilding balance cache...\n");
+
+        CWalletDB walletdb;
+        mapAccountBalanceCache.clear();
+
+        CRITICAL_BLOCK(cs_mapAddressBook)
+        {
+            // find all accounts
+            foreach(const PAIRTYPE(string, string)& addressBookItem, mapAddressBook)
+            {
+                if (addressBookItem.second.empty())
+                    continue;
+
+                for (int nMinDepth = 0; nMinDepth <= ACCOUNT_BALANCE_CACHE_DEPTH; nMinDepth++)
+                {
+                    mapAccountBalanceCache[make_pair(addressBookItem.second, nMinDepth)] = 0;
+                }
+            }
+
+            CRITICAL_BLOCK(cs_mapWallet)
+            {
+                // Tally wallet transactions
+                for (map<uint256, CWalletTx>::iterator it = mapWallet.begin(); it != mapWallet.end(); ++it)
+                {
+                    const CWalletTx& wtx = (*it).second;
+                    if (!wtx.IsFinal())
+                        continue;
+
+                    wtx.UpdateAccountBalanceCache();
+                }
+
+                // Tally internal accounting entries
+                foreach(const PAIRTYPE(const PAIRTYPE (string, int)&, int64)& item, mapAccountBalanceCache)
+                {
+                    mapAccountBalanceCache[item.first] += walletdb.GetAccountCreditDebit(item.first.first);
+                }
+            }
+        }
+    }
+}
 
 
 //////////////////////////////////////////////////////////////////////////////
@@ -179,6 +231,9 @@ bool AddToWallet(const CWalletTx& wtxIn)
         // Notify any urls monitoring
         if (!setMonitorTx.empty())
             monitorTx(wtx);
+
+        // Rebuild balance cache
+        CreateAccountBalanceCache();
     }
 
     // Refresh UI
@@ -519,7 +574,38 @@ void CWalletTx::GetAccountAmounts(const string& strAccount, int64& nGenerated, i
     }
 }
 
+void CWalletTx::UpdateAccountBalanceCache() const
+{
+    int64 allGeneratedImmature, allGeneratedMature, allFee;
+    allGeneratedImmature = allGeneratedMature = allFee = 0;
+    string strSentAccount;
+    list<pair<string, int64> > listReceived;
+    list<pair<string, int64> > listSent;
+    GetAmounts(allGeneratedImmature, allGeneratedMature, listReceived, listSent, allFee, strSentAccount);
 
+    for (int nMinDepth = 0; nMinDepth <= ACCOUNT_BALANCE_CACHE_DEPTH; nMinDepth++)
+    {
+        // see if an account was affected by sending money somewhere
+        if (mapAccountBalanceCache.count(make_pair(strSentAccount, nMinDepth)))
+        {
+            foreach(const PAIRTYPE(string,int64)& s, listSent)
+                mapAccountBalanceCache[make_pair(strSentAccount, nMinDepth)] -= s.second;
+            mapAccountBalanceCache[make_pair(strSentAccount, nMinDepth)] -= allFee;
+        }
+
+        // go through listReceived and update accounts that are affected
+        if (GetDepthInMainChain() >= nMinDepth)
+        {
+            foreach(const PAIRTYPE(string,int64)& r, listReceived)
+            {
+                if (mapAddressBook.count(r.first) && mapAccountBalanceCache.count(make_pair(mapAddressBook[r.first], nMinDepth)))
+                {
+                    mapAccountBalanceCache[make_pair(mapAddressBook[r.first], nMinDepth)] += r.second;
+                }
+            }
+        }
+    }
+}
 
 int CMerkleTx::SetMerkleBranch(const CBlock* pblock)
 {
@@ -2769,6 +2855,9 @@ bool ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv)
 
         if (ProcessBlock(pfrom, &block))
             mapAlreadyAskedFor.erase(inv);
+
+        // Rebuild balance cache
+        CreateAccountBalanceCache();
     }
 
 
diff --git a/main.h b/main.h
index 8f9345e..6dfab90 100644
--- a/main.h
+++ b/main.h
@@ -27,7 +27,7 @@ static const int fHaveUPnP = true;
 #else
 static const int fHaveUPnP = false;
 #endif
-
+static const int ACCOUNT_BALANCE_CACHE_DEPTH = 2;
 
 
 
@@ -56,6 +56,9 @@ extern CCriticalSection cs_mapMonitored;
 extern std::set<std::string> setMonitorTx; // set of urls listening for new transactions
 extern std::set<std::string> setMonitorBlocks; // set of urls listening for new blocks
 
+extern map<pair<string, int>, int64> mapAccountBalanceCache;
+extern CCriticalSection cs_mapAccountBalanceCache;
+
 // Settings
 extern int fGenerateBitcoins;
 extern int64 nTransactionFee;
@@ -103,6 +106,7 @@ void BitcoinMiner();
 bool CheckProofOfWork(uint256 hash, unsigned int nBits);
 bool IsInitialBlockDownload();
 string GetWarnings(string strFor);
+void CreateAccountBalanceCache();
 
 
 
@@ -1006,6 +1010,8 @@ public:
     void GetAccountAmounts(const string& strAccount, int64& nGenerated, int64& nReceived, 
                            int64& nSent, int64& nFee) const;
 
+    void UpdateAccountBalanceCache() const;
+
     bool IsFromMe() const
     {
         return (GetDebit() > 0);
diff --git a/rpc.cpp b/rpc.cpp
index 3807aa7..bd89fc9 100644
--- a/rpc.cpp
+++ b/rpc.cpp
@@ -358,6 +358,13 @@ string GetAccountAddress(string strAccount, bool bForceNew=false)
         string strAddress = PubKeyToAddress(account.vchPubKey);
         SetAddressBookName(strAddress, strAccount);
         walletdb.WriteAccount(strAccount, account);
+
+        // Update balance cache
+        CRITICAL_BLOCK(cs_mapAccountBalanceCache)
+        {
+            for (int nMinDepth = 0; nMinDepth <= ACCOUNT_BALANCE_CACHE_DEPTH; nMinDepth++)
+                mapAccountBalanceCache[make_pair(strAccount, nMinDepth)] = 0;
+        }
     }
 
     walletdb.TxnCommit();
@@ -603,9 +610,17 @@ Value getreceivedbyaccount(const Array& params, bool fHelp)
     return (double)nAmount / (double)COIN;
 }
 
-
-int64 GetAccountBalance(CWalletDB& walletdb, const string& strAccount, int nMinDepth)
+int64 GetAccountBalance(CWalletDB& walletdb, const string& strAccount, int nMinDepth, bool fUseCache = true)
 {
+    // check the cache first
+    CRITICAL_BLOCK(cs_mapAccountBalanceCache)
+    {
+        map<pair<string, int>, int64>::iterator it = mapAccountBalanceCache.find(make_pair(strAccount, nMinDepth));
+        if (fUseCache && it != mapAccountBalanceCache.end())
+            return (*it).second;
+    }
+
+    // in case of cache miss: calculate from scratch
     int64 nBalance = 0;
     CRITICAL_BLOCK(cs_mapWallet)
     {
@@ -631,13 +646,12 @@ int64 GetAccountBalance(CWalletDB& walletdb, const string& strAccount, int nMinD
     return nBalance;
 }
 
-int64 GetAccountBalance(const string& strAccount, int nMinDepth)
+int64 GetAccountBalance(const string& strAccount, int nMinDepth, bool fUseCache = true)
 {
     CWalletDB walletdb;
-    return GetAccountBalance(walletdb, strAccount, nMinDepth);
+    return GetAccountBalance(walletdb, strAccount, nMinDepth, fUseCache);
 }
 
-
 Value getbalance(const Array& params, bool fHelp)
 {
     if (fHelp || params.size() < 0 || params.size() > 2)
@@ -683,7 +697,7 @@ Value getbalance(const Array& params, bool fHelp)
 
     string strAccount = AccountFromValue(params[0]);
 
-    int64 nBalance = GetAccountBalance(strAccount, nMinDepth);
+    int64 nBalance= GetAccountBalance(strAccount, nMinDepth);
 
     return ValueFromAmount(nBalance);
 }