Speeding up "getbalance <account>" calls

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

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

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

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