[BTC-dev] Taming the mempool

Sat Dec 19 20:45:23 UTC 2015

URL: <http://therealbitcoin.org/ml/btc-dev/attachments/20151219/attachment_905aefee703f2c008326d5ecb15615625ac074c7.txt>
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA512

Enclosed patch is just a development snapshot (*ask asciilifeform to
insert smiley here*), a throwaway. It *will* crash at or before block
400000. If you run it, compile it unstripped and run under gdb.

It's a combination of:

(a) JettisonMempool [1]
(b) igprof support [2]
(c) tracks transactions by fee and deallocates lowest fee-for-Kb tx data
(d) custom allocator for blocks and all related data that is never
deallocated so that it won't clobber the heap
(e) malloc tuning

Applies on top of 0.5.4-TEST1 + stator.

(c) Transaction priority is computed as (tx fee)/(memory size in
kB). This "memory size" is a guess of live memory used, not
transaction serialized size and it's spurious, as it's not easy to
know true C++ object graph size. For testing purposes I considered
sufficient that the changes in my mempoolSize roughly corresponded to
changes in LIVE_MEM reported by igprof. The transactions are ordered
by this priority in mapTxFees. Volume of transaction, days
destroyed,etc... are not considered, this should be added if developed
further. Or to be explicitly said "user provides this function".
Removal from mapTxFees is perceptibly slow - O(N), I added
a hack to defer it, but this needs to be completely redone in any
case.

Testing with mempoolMaxSize = 40M

The graphs shows test on amd64 with 12G of RAM and negligible memory
pressure. "Original" means only (c) part is there, "patch" is with all parts.
Since I have removed any other tx fee checks, mempool always
filled up quickly in 1-2 hours every time, connected to 8 peers.

At first, despite deallocating transactions either by (a) or (c), and
igprof reporting this does have effect on LIVE_MEM, RSS memory usage
(as reported by 'ps -o rss -C bitcoind') grew steadily without
bounds. The next idea was,that heap is sprinkled with permanently
allocated blocks data causing inability for malloc to release the
memory back to the OS. I went to try and allocate these
separately... and boy does that rabbit hole go deep - had to add
custom allocator to several places and a bypass for openssl's BIGNUM
aka CBigNum.

The outcome is with all objects on heap having similar lifetimes,
malloc able to do its job better, but the growth is still
unbounded. Memory (on x86_64) roughly consists of 20M code, 80M
CBlockIndex array, 32M buffer for other permanent objects (mbiMem) and
rest is the heap (basically the mempool), total 250M as seen from the
graph. This means that while the patch estimates mempool memory usage
at 40M it's really about twice. Looking at its igprof results, it's
mostly std::map overhead. Throwing std::map (it is red-black tree) out
and using even a simple hash table instead with, say, fill factor 0.7
should improve the situation.  Malloc tuning (mallopt and malloc_trim
calls) had no discernible effect. The noise at 42 hour mark is
zapmempool call, which shows it's still not really working.

So if we are to continue in this direction, if anyone knows of simple
and proven C++ code for hash table or other suitable mempool
datastructure (best if std::map drop in replacement), we're game. And
obviously instead of using static array of 400000 blocks and related
data, allocate/mmap these several megabytes at a time. If the blocks
with related data are laid out by height, old rarely used ones can be
swapped out by OS, which would finally enable bitcoind to run fine on
128M RAM device without further extensive changes.

Also, needs to test if it deallocates mutated transactions.

[1] http://therealbitcoin.org/ml/btc-dev/2015-August/000142.html -
Note that if you take reference of CTransaction straight from
mapTransactions and call RemoveFromMemoryPool on it, it will
deallocate itself in the middle of the call and crash. You're supposed
to call such functions on a *copy* of CTransaction object.

[2] http://therealbitcoin.org/ml/btc-dev/2015-May/000095.html - disabled
static linking for the 2nd linker stage is necessary for igprof to
work.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.12 (GNU/Linux)

iQIcBAEBCgAGBQJWdcl5AAoJEGd6vWLQrufXRYQP/R4+z7y7ocQoylvvHPyRb4T9
HDnkI3+6n/yB6AEf2Ff5AT5tDZRymqWj+Qx9kB2H+3MouGld3cMyhnfMsmAITK2N
/WLQW9e1keazOf/vQxYIIb7HniM6RQxUoJoSEMh/3z9TB+DvICskhoNJsntTxmtz
cXEjLLhALIoBzvAuGi1v0m+7LDAdoouGVwCdkaS4gVLJ+SrB93cpALqu1OUeupJC
7lLhhNtajn+6Ck1FT1s3drlbvqMPfaEZRKgNuh7VMRu3qWdSnRdXHz6DZhENQ0EJ
q4hyftBz6BfJPkImUgfsvVDNK2ypkBFoSFuFOhD8CmjrJoRozCapDXos1WgfBg+0
8QeCz5pLLSqs3bbMxfNm9+JMRofwByHkbe+lgeVVZx1Vp6ARektRVe2MquDqKLtc
79Hg7jAa+dBninrOmrSazgFGdpav02+PqzPi5AB1p+hU4tEdo0tFwD3M/hCeSV/B
+MwkW1RMpEpCjfr+CuTCK7GyesQ1Jt5ptRsQd0KNgwNtuw9kCph/HMvqAXHL3MFn
nP4dNdqej61KOU03qQfpm4qj8I+4K50OpGcEPtYSY3pEe80C77smT050F0QdFXvX
LlF683XZIW7N63W2NdrVaga8dT8hT+XPKvufmgqweh+BjLZiJ3DvkgUKTEtfA961
osiOJZsoYrP2PCQUg/Xf
=nIvr
-----END PGP SIGNATURE-----
-------------- next part --------------
A non-text attachment was scrubbed...
Name: mempool_dev2.patch
Type: text/x-patch
Size: 39326 bytes
Desc: not available
URL: <http://therealbitcoin.org/ml/btc-dev/attachments/20151219/mempool_dev2_a654caa4f28ed6f78906fef28060c2f46470f067.patch>
-------------- next part --------------
Name: mempool_dev2.patch.asc
URL: <http://therealbitcoin.org/ml/btc-dev/attachments/20151219/mempool_dev2_fdec69076b14a651815c87823423d3c3ca931a3f.patch.asc>
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.12 (GNU/Linux)

iQIcBAABCgAGBQJWdcnwAAoJEGd6vWLQrufXE40P/23lYGchown0wb7I6552LKU1
mTgJM7zrYsynK7gkP7R/l9qlOoJXnGk1/gavrVD3YimFkKfCdnkYneUiELMdyM6W
ok3vgSDCyLvJLGjfTNuVmj5fu8G47/evlhxSK4ZPJ7SXyZZHagNjxWMzqpEZ/N82
PUZDlH4C6fFPpwW8rjzSGxJE5o3sn6U1/AxcXHprc/pnwLoCdwJNRS5xRZTYGJcb
agUQmGbeYJ762958QJwmUD+XR52IUfo08SCzvrZYBpSeDaCwWSLWvCbhO0uCIop4
Ilcgl94A1Qku5abM4a+Ndz4ptRgrrFX18ClGYJbfHyQiEgJffsxV7u++veCPiNTc
4B/oNxrFFSrXPz1KaU0J112BfWC0jVPYgfCgalcaHdeb54n8ZmdQ8ktMT1KNOAuB
dgOObPjlSFStHJSNPjHSApCqrv0YS92KpZu+PGtFaGRuYelYs3rzpb34358nSB7o
PgkQ6ZE6kbqBFlfRjF7mctwunTzcSqjGxOv3MUZI1/FY8BWA2Xs22od58FUUhNYA
0rvf+n1XIyBculsnJGf/TdOtE+3QxQNX5S3gHzhkKwd/vl8a4qZ1PbRnXfkeDHPR
Pt/5IMxSMK6OB6MM6skGxy+rdJlpd9NkN3TLjuUrTHny+N2acJoJIhnajJCR9rJt
TrNAmWYl4WFU2v9x9dZN
=Yzb/
-----END PGP SIGNATURE-----
-------------- next part --------------
A non-text attachment was scrubbed...
Name: memgraph2-fs8.png
Type: image/png
Size: 22467 bytes
Desc: not available
URL: <http://therealbitcoin.org/ml/btc-dev/attachments/20151219/memgraph2-fs8_93abd1de1cf2398a58ae4fdbc9c83c69cb359b33.png>