improve addr/inv trickle logic

pstratem commented at 7:21 pm on April 9, 2015: contributor

The addr/msg_tx logic currently assumes that ProcessMEssage/SendMessage are called on a regular timer.

This was (sort of) true in the past but is not longer true after #5971

Critical analysis of this PR would be helpful as this goes beyond just fixing the timing issue.

jgarzik commented at 9:02 pm on April 9, 2015: contributor

Any possibility to use the timer stuff being added in #5964 ?

pstratem commented at 3:38 am on April 10, 2015: contributor

@jgarzik maybe later, porting wont be difficult

in src/main.cpp: in 2abc256a82 outdated

4540-        if (fSendTrickle)
4541-        {
4542+
4543+        if (pto->nNextLocalAddrSend < GetTime()) {
4544+            AdvertizeLocal(pto);
4545+            pto->nNextLocalAddrSend = GetTime() + GetRand(24 * 60 * 60);

Diapolo commented at 6:13 am on April 10, 2015:

Could that magic number be defined somehwere as constant? IMHO it’s used quite often in this pull.

pstratem commented at 9:11 pm on April 10, 2015:

At a later date in a different PR

in src/main.cpp: in 85efde3c61 outdated

4630 
4631-                    if (fTrickleWait)
4632+        {
4633+            LOCK(pto->cs_inventory);
4634+            
4635+            // TODO it would be sufficient to walk vInventoryToSend randomly, shuffling is relatively inefficient

sipa commented at 9:41 am on April 11, 2015:

In a random walk, it is hard to efficiently avoid processing the same element twice. If shuffling is slow, create an array of indexes, and shuffle that. Also, where does std::random_shuffle() get its randomness?

Suggested code:

0std::vector<int> vRandInv;
1vRandInv.resize(pto->vInventoryToSend.size());
2for (int i = 0; i < pto->vRandInv.size(); i++) vRandInv[i] = i;
3for (int i = 0; i < pto->vRandInv.size(); i++) std::swap(vRandInv[i], vRandInv[i + GetRand(vRandInv.size() - i]);
4
5for (int i = 0; i < pto->vRandInv.size(); i++) {
6    const CInv& inv = pto->vInventoryToSend[vRandInv[i]];
7
8    ...

in src/main.cpp: in 85efde3c61 outdated

4695+            pto->nNextInvSend = nNowMicros + GetRand(10 * 1000000);
4696+
4697         // Detect whether we're stalling
4698-        int64_t nNow = GetTimeMicros();
4699-        if (!pto->fDisconnect && state.nStallingSince && state.nStallingSince < nNow - 1000000 * BLOCK_STALLING_TIMEOUT) {
4700+        nNowMicros = GetTimeMicros();

sipa commented at 9:45 am on April 11, 2015:

You already have an initialized nNowMicros variable. No need to request the current time again?

pstratem commented at 2:41 pm on April 11, 2015:

There’s a certain amount of error from caching the value.

The value is updated twice to reduce this error.

sipa commented at 4:57 pm on April 22, 2015:

If the difference in time between them is more than a few milliseconds, we have different problems :)

pstratem commented at 5:54 pm on April 22, 2015:

I want to avoid changing the logic of anything im not explicitly touching.

sipa commented at 5:55 pm on April 22, 2015:

Fair enough.

in src/main.cpp: in 85efde3c61 outdated

4640+                    case MSG_BLOCK:
4641+                    case MSG_FILTERED_BLOCK:
4642                     {
4643-                        vInvWait.push_back(inv);
4644-                        continue;
4645+                        // Aggressively push MSG_BLOCK/MSG_FILTERED_BLOCK

sipa commented at 9:54 am on April 11, 2015:

Maybe it is more efficient to keep a separate vInventoryToSend for MSG_BLOCK and MSG_FILTERED_BLOCK, and only shuffle/process the normal one when nNextInvSend is exceeded.

sipa commented at 9:55 am on April 11, 2015: member

Concept ACK. I love getting rid of the vSendTrickle logic…

gavinandresen commented at 3:18 pm on April 24, 2015: contributor

I’m with @jgarzik: this could be much cleaner built on top of #5964. All of the pnode->nNext* variables could go away; just schedule a task that takes a NodeId and Does The Right Thing at some (random) time in the future.

(the tasks would lock cs_vNodes and do the NodeId to CNode* lookup… probably don’t need to optimize that lookup, looping through even a 1,000-peer vector isn’t a significant amount of CPU time).

sipa commented at 3:29 pm on April 24, 2015: member

Unsure. I don’t think running the scheduled operations makes sense if there is nothing else to do for a node, and there almost always is, at which time we already hold the necessary locks.

Small benefit, small cost.

gavinandresen commented at 5:18 pm on April 24, 2015: contributor

@sipa : benefit would be clearer logic. I find the “set a variable here, test it over there and then do something” hard to review/follow.

pstratem commented at 5:55 pm on April 24, 2015: contributor

@gavinandresen As I said to @jgarzik it’s easy enough to back port this logic into CSchedule.

I would rather not tie the two PR’s together.

in src/main.cpp: in d807bdcbc5 outdated

4565-        {
4566+
4567+        int64_t nNowMicros = GetTimeMicros();
4568+        if (pto->nNextLocalAddrSend < nNowMicros) {
4569+            AdvertizeLocal(pto);
4570+            pto->nNextLocalAddrSend = nNowMicros + GetRand(24 * 60 * 60 * 1000000);

sipa commented at 10:04 pm on April 25, 2015:

Integer overflow on this line. You probably want to cast to int64_t first.

sipa commented at 10:06 pm on April 25, 2015: member

@gavinandresen Yes, that’s the small benefit. The small cost is extra locking/work. Not opposed to it, but it’s not as clear an advantage as replacing the several pieces of code we had that were already using their own thread. This one doesn’t need it.

sipa commented at 1:07 pm on April 27, 2015: member

Can you fix the integer overflow, and perhaps rebase on top of #6066?

laanwj added the label Improvement on Apr 29, 2015

sipa commented at 1:25 pm on May 5, 2015: member

Rebase please?

sipa commented at 2:16 pm on June 14, 2015: member

Needs rebase, and fixing the integer overflow.

sipa commented at 2:38 pm on June 14, 2015: member

Did a rebase and fix: https://github.com/sipa/bitcoin/commits/trickle_fix

sipa commented at 8:57 pm on July 9, 2015: member

@pstratem ping

pstratem commented at 8:58 pm on July 9, 2015: contributor

@sipa pong

modify local address broadcast to reduce correlation between peers 6a1b004211

switch addr message trickling logic to use timestamps 3504948dc5

put setAddrKnown.clear() on it's own timer to prevent a coorelation 51f6665df9

do not broadcast local addr on connect to outbound peers b8dc779e6a

micro memory optimization 57a82dbd31

Modify MSG_TX trickle logic to use timestamps

clarify expression

remove fSendTrickle flag

shuffle inventory list to send (for good measure)

slight peak memory improvement

user timestamps for transaction trickle logic

always send MSG_TX to whitelisted nodes

cc7c8576b0

walk vInventoryToSend in random order to further obscure timing information f7cb9b25ce

restructure as switch statement 61ef89fabf

call GetTime() once, simplifies reasoning around timestamp based operations 875669d177

switch to microseconds

improves the reoslution to the polling frequency from 1 second

35464e4560

remove unused pnodeTrickle 2f6308ea34

separate block inv queue with no trickle 59f2b32ec8

secure random walk of vInventoryToSend 507cd8bcaa

collect block inv messages f2cb99e318

setAddrKnown was replaced with addrKnown f55c978cd8

pstratem commented at 11:17 pm on July 12, 2015: contributor

setAddrKnown was replaced with a CRollingBloomFilter d81cff32e50fe5f686f985d0af2e74219f328ed0

Given this it seems reasonable to slowly unset bits of the bloomfilter rather than clearing the filter entirely every 24 hours.

Thoughts?

pstratem commented at 0:44 am on July 13, 2015: contributor

Scratch that. There’s no need to clear the filter explicitly with the rolling bloom filter.

dcousens commented at 8:52 am on October 30, 2015: contributor

@pstratem rebase/close?

sipa commented at 3:49 pm on October 30, 2015: member

rebase please…

sipa commented at 3:09 pm on November 28, 2015: member

See #7125.

pstratem commented at 1:08 am on December 8, 2015: contributor

we have better ideas on how to achieve the properties of the trickle logic (such as mempool sync at random interval)

pstratem closed this on Dec 8, 2015

DrahtBot locked this on Sep 8, 2021

improve addr/inv trickle logic #5989