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

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

[jan]

Hi there!

Instawallet has enjoyed steady growth and I'm running into a bottleneck
now with "getbalance <someaccounthere>" taking quite some time to
complete. My understanding is, that this is because bitcoind runs
through all relevant transactions each time anew to compute the balance.
I was hoping the list could give me some pointers/ideas on how I can
improve this.

I might start to do account handling completely in my application at
some point, but for now I would like to continue letting bitcoind handle
this, so I don't have to worry about thinks like block chain reorgs.

Basically I don't have enough familiarity with the source code to feel
confident about doing fairly invasive changes. So right now I'm planning
to implement a very simple cache (directly in bitcoind), which just
caches calls to getbalance and simply invalidates the whole cache as
soon as a new block or a transaction that affects the wallet comes in.
I'm hoping this will help a little bit, although with blocks arriving
every 10 minutes on average it's not really the perfect solution.

Maybe one step better would be to only invalidate cache entries that are
affected by a new transaction or by transactions arriving in a block.
This would need to take block chain reorgs into account though, which
seems fairly complicated. Maybe I could simply invalidate the whole
cache on reorgs, which should be seldom enough that it's not a big
problem. Where would be a good place in the source code to hook into to
notice block chain reorgs?

The perfect solution would be, of course, if bitcoind could keep running
balances of all accounts and update them as new information becomes
available. But as I said, I don't feel that I have a good overview of
all the corner cases to make such an improvement. I guess an extensive
test suite testing all sorts of esoteric block chain reorgs would really
be a nice thing to have. :-)

Regards!
Jan

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

[John Smith]

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

Jan,

On Thu, Jun 23, 2011 at 9:51 PM, <jan@uos.de> wrote:

> Hi there!
>
> Instawallet has enjoyed steady growth and I'm running into a bottleneck
> now with "getbalance <someaccounthere>" taking quite some time to
> complete. My understanding is, that this is because bitcoind runs
> through all relevant transactions each time anew to compute the balance.
> I was hoping the list could give me some pointers/ideas on how I can
> improve this.
>

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.

1) This reduces the time the API takes to return the balance for an account
to a predictable, very short time. Just the time to look up the balance in
the hash table (and return 0 on miss). The number crunching happens in the
network thread, not while you're waiting on the API.

2) Less bug-prone than "incremental caching" as you propose, and doesn't
require determining which accounts are influenced by a new block

3) Block chain reorgs are no problem.

JS

[-- Attachment #2: Type: text/html, Size: 1596 bytes --]

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

[Jan Vornberger]

[-- 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);
 }

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

[jan]

Another quick update:

On Sun, Jul 03, 2011 at 06:29:05PM +0200, Jan Vornberger wrote:
> as now "sendfrom" starts acting up and I have to look into that
> next.

I realized why this happens: Sendfrom triggers a rebuild of the cache
and couldn't return before the rebuild was complete.

So I changed the approach slightly: A complete rebuild of the cache will
only happen on new blocks (in case reorgs happen) whereas on new wallet
transactions the cache will just be adjusted incrementally. Seems to
work fine so far (every 4000 calls or so I double check the cache by
running a full calculation and compare the results. No mismatch happened
so far). The changes are pushed to the github branch I linked to.

One caveat I realized: The cache will not work correctly with the RPC
command "move" as I haven't implemented the necessary adjustments.
Shouldn't be too difficult, but since I don't use that command, I
haven't done this (yet).

Regards!
Jan