Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

first pass at provide many mechanism #2011

Closed
wants to merge 589 commits into from
Closed

first pass at provide many mechanism #2011

wants to merge 589 commits into from
+13,795 −175,589

Conversation

whyrusleeping
Copy link
Member

Provide multiple keys at a time, more efficient as we combine RPCs where possible, savings also made during the initial 'find closest peers' step.

The basic tests i added show a savings of over 90% total network bandwidth (100k on new code, 1.5MB old code). It also takes about half the time (though the tests are performed over the loopback, so no latency is involved)

License: MIT
Signed-off-by: Jeromy jeromyj@gmail.com

@jbenet jbenet added the status/in-progress In progress label Nov 27, 2015
@whyrusleeping
Copy link
Member Author

The new code also does a lot better job of distributing providers, i couldnt get the same test i wrote for my new code to pass using the old code, so i had to change the Fatals to Logs

jbenet
jbenet reviewed Dec 1, 2015
View reviewed changes
exchange/bitswap/network/interface.go
@@ -48,4 +48,7 @@ type Routing interface {

// Provide provides the key to the network
Provide(context.Context, key.Key) error

// Provide multiple keys to the network at the same time, sharing RPCs
ProvideMany(context.Context, []key.Key) error
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

wonder if that should be a key channel, to allow providing from a single dag in one call, and then do the stack thing this way

@jbenet
Copy link
Member

jbenet commented Dec 1, 2015

reminder: kademlia is an algorithm designed and proved to scale to very large numbers with logarithmic complexity, and it is designed around the concept of an iterative (and concurrent) query that gets closer to a distance target. this changeset goes against that.

think about it like this: it is critical to consider a lot of peers every time (routing tables will get large, hundreds of peers) and pick only the best towards the goal based on the most current information (priority queue), which will come as a result as the query's messages return peers.[0]

the large constant factor problems we see now in our small networks are much more due to our own problems in:

  • the large number of provides
  • very large key-space
  • very slow dials/handshakes
  • not using udp-based transports yet
  • not coalescing messages while we can (i.e. while the dial hasnt completed and an additional message is getting queued for a peer it can be coalesced)

important in this kind of algorithmic change to reason through why your approach here is giving you such better numbers, plot out what nodes are getting requested instead, and come up with an algorithmic argument as to why the model still holds (i strongly suspect it does not).

@jbenet
Copy link
Member

jbenet commented Dec 1, 2015

[0]in fact, one thing to try that may get the same or even better speed up is:

  • to do the message coalescing, and then
  • to coalesce keys into closeness clusters (picking num_clusters > num_kbuckets)
  • to coalesce the priority-sorting function of the queues themselves -- i.e. instead of using a priority queue per query seeded with closest peers and only using the peers found through that query, instead use:
    • a set to keep track of peers queried in this given query (avoid double querying)
    • keep stats (low, high, avg, n) on distances queried (avoid querying "bad peers" altogether)
    • add new found peers to routing table, and then re-sample from the entire routing table each time. (leverage concurrent queries finding better peers) --- this last one may not work that well with very small kbucket sizes + the preference for long-lived nodes. the case where this can break down is the "most distant to peer-id" kbucket, which will cover the largest id space, but still only have a regular number of nodes-- in this case may be worth considering "recently found" peers as part of routing table for the duration of their query)

jbenet
jbenet reviewed Dec 1, 2015
View reviewed changes
routing/dht/provide_many.go
next, ok := pmreq.getNextTarget()
if ok {
result.closerPeers = []peer.PeerInfo{{ID: next}}
}
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

this is breaking assumptions as to how the query runner is meant to work. this should be returning a set of closer peers found through this one peer, not the next best through everyone. instead, the entire query runner should be sampling from everyone found -- see #2011 (comment)

@ghost ghost added topic/dht Topic dht topic/perf Performance labels Dec 22, 2015
@whyrusleeping whyrusleeping force-pushed the dev0.4.0 branch 2 times, most recently from 68b9745 to b0a8591 Compare December 28, 2015 14:36
@whyrusleeping whyrusleeping self-assigned this Jan 29, 2016
atomgardner and others added 16 commits March 2, 2016 08:08
@atomgardner @daviddias
Humanize byte size

Unverified

This commit is not signed, but one or more authors requires that any commit attributed to them is signed.
Learn about vigilant mode
288f7bc 
License: MIT
Signed-off-by: Thomas Gardner <tmg@fastmail.com>
@whyrusleeping
introduce low memory flag

Unverified

This commit is not signed, but one or more authors requires that any commit attributed to them is signed.
Learn about vigilant mode
7d0c46a 
License: MIT
Signed-off-by: Jeromy <jeromyj@gmail.com>
@whyrusleeping
remove trailing whitespace

Unverified

This commit is not signed, but one or more authors requires that any commit attributed to them is signed.
Learn about vigilant mode
64c6943 
License: MIT
Signed-off-by: Jeromy <jeromyj@gmail.com>
@whyrusleeping
Merge pull request #2399 from ipfs/fix/assert-gopath

Unverified

This commit is not signed, but one or more authors requires that any commit attributed to them is signed.
Learn about vigilant mode
6d4da61 
assert that you must build from inside your gopath
@whyrusleeping
make t0060 use port zero

Unverified

This commit is not signed, but one or more authors requires that any commit attributed to them is signed.
Learn about vigilant mode
63a9ed2 
License: MIT
Signed-off-by: Jeromy <jeromyj@gmail.com>
@RichardLitt
Fix spelling error

Unverified

This commit is not signed, but one or more authors requires that any commit attributed to them is signed.
Learn about vigilant mode
96204b5 
My bad. Introduced in #2366

License: MIT
Signed-off-by: Richard Littauer <richard.littauer@gmail.com>
@whyrusleeping
Merge pull request #2432 from ipfs/docs/spelling-error

Unverified

This commit is not signed, but one or more authors requires that any commit attributed to them is signed.
Learn about vigilant mode
16c08a3 
Fix spelling error
@whyrusleeping
Merge pull request #2429 from ipfs/feat/low-mem-experiment

Unverified

This commit is not signed, but one or more authors requires that any commit attributed to them is signed.
Learn about vigilant mode
9a923b4 
introduce a low memory flag
@adrian-bl @hackergrrl
Use net/url to escape paths in web-ui

Unverified

This commit is not signed, but one or more authors requires that any commit attributed to them is signed.
Learn about vigilant mode
ec7623b 
License: MIT
Signed-off-by: Adrian Ulrich <adrian@blinkenlights.ch>
@hackergrrl
adds tests for gateway url escaping

Unverified

This commit is not signed, but one or more authors requires that any commit attributed to them is signed.
Learn about vigilant mode
1ee3645 
License: MIT
Signed-off-by: Stephen Whitmore <noffle@ipfs.io>
@hackergrrl
re-vendors dir-index-html
8fe12ef 
License: MIT
Signed-off-by: Stephen Whitmore <noffle@ipfs.io>
@hackergrrl
dir-index-html unescaping
8d5e327 
License: MIT
Signed-off-by: Stephen Whitmore <noffle@ipfs.io>
@whyrusleeping
Merge pull request #2435 from noffle/use-net-url-escaping
c3204a6 
use net/url to escape paths in web-ui
dns: update dns command docs
89b233e 
License: MIT
Signed-off-by: Lars Gierth <larsg@systemli.org>
@whyrusleeping
Merge pull request #2438 from ipfs/dns-docs
47643fe 
dns: update dns command docs
@Neurone
added sudo to usermod;
f6e1bb1 
added --json to "ipfs config" command;
added modification to fuse.conf;

License: MIT
Signed-off-by: Giuseppe Bertone <bertone.giuseppe@gmail.com>
whyrusleeping and others added 27 commits May 5, 2016 10:10
@whyrusleeping
Merge pull request #2581 from RealImage/default-config
2862e58 
Implements repository initialization with default config
@whyrusleeping
Merge pull request #2632 from hsanjuan/issue_2434
fbf745f 
"ipfs log ls" command
@kevina
Make blocks.Block an interface.
b84cbec 
License: MIT
Signed-off-by: Kevin Atkinson <k@kevina.org>
@whyrusleeping
Merge pull request #2633 from ipfs-filestore/blocks-interface
d30966a 
Make blocks.Block an interface.
@RichardLitt
Marshal log ls better
23108aa 
This uses a stringList to output each log command as an item in an array in an object called Strings, instead of using the MessageOutput func.

This closes #2636.

License: MIT
Signed-off-by: Richard Littauer <richard.littauer@gmail.com>
@whyrusleeping
Merge pull request #2637 from ipfs/feature/2636-marshal-log-ls
f4a5bf5 
Marshal log ls better
@chriscool
t0170: put startup_cluster() call outside test_expect_success
01bf209 
startup_cluster() already contains some test_expect_success, so
it should not be inside one.

License: MIT
Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
@chriscool
t0170: remove useless 'echo' and add '&&'
e8bc591 
License: MIT
Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
@chriscool
test-lib: make checking for docker silent
c54c045 
License: MIT
Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
@whyrusleeping
Merge pull request #2639 from ipfs/silence-docker-check
00f9ce6 
test-lib: make checking for docker silent
@RichardLitt
Update shell link to allow wget
0f21dcb 
The link to the commit file shell link should be to the raw file. That makes it easier for peopel to wget it without caring about using GitHubs interface. Perhaps this should also be hosted on IPFS

License: MIT
Signed-off-by: Richard Littauer <richard.littauer@gmail.com>
@whyrusleeping
add a dist_get script for getting bins from dist.ipfs.io
284bb18 
License: MIT
Signed-off-by: Jeromy <why@ipfs.io>
@whyrusleeping
debugging travisCI
cd11a48 
License: MIT
Signed-off-by: Jeromy <why@ipfs.io>
@whyrusleeping
stricter makefile targets
4b6828e 
License: MIT
Signed-off-by: Jeromy <why@ipfs.io>
@whyrusleeping
update dist_get script to be more cross platform
4a08827 
License: MIT
Signed-off-by: Jeromy <why@ipfs.io>
@whyrusleeping
use gx-go 1.2.0
06a8a5b 
License: MIT
Signed-off-by: Jeromy <why@ipfs.io>
@whyrusleeping
address some CR feedback
3c7fad8 
License: MIT
Signed-off-by: Jeromy <why@ipfs.io>
@whyrusleeping
fix up dist_get script
5f624ef 
License: MIT
Signed-off-by: Jeromy <why@ipfs.io>
@whyrusleeping
Merge pull request #2644 from RichardLitt/feature/update-sh-link
a45cbad 
Update shell link to allow wget
@whyrusleeping
Merge pull request #2638 from ipfs/t0170-misc-fixes
2c8fdab 
t0170 misc fixes
@whyrusleeping
fix travis.yml
f2aa109 
License: MIT
Signed-off-by: Jeromy <why@ipfs.io>
@whyrusleeping
use repo level bins in test Makefile
1e31839 
License: MIT
Signed-off-by: Jeromy <why@ipfs.io>
@whyrusleeping
bump gx version to 0.7.0
db5d730 
License: MIT
Signed-off-by: Jeromy <why@ipfs.io>
@whyrusleeping
Merge pull request #2584 from ipfs/fix/build-process
1a6f8c6 
add a dist_get script for getting bins from dist.ipfs.io
@whyrusleeping
first pass at provide many mechanism
73c8a87 
License: MIT
Signed-off-by: Jeromy <jeromyj@gmail.com>
@whyrusleeping
make the rest of the code work with provideMany
2d28720 
License: MIT
Signed-off-by: Jeromy <jeromyj@gmail.com>
@whyrusleeping
make bitswap use provide many
74a0e03 
License: MIT
Signed-off-by: Jeromy <jeromyj@gmail.com>
@Kubuxu Kubuxu closed this May 13, 2016
@Kubuxu Kubuxu deleted the feat/provide-many branch February 27, 2017 20:37
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers
No reviews
Assignees

@whyrusleeping whyrusleeping

Labels
status/in-progress In progress topic/dht Topic dht topic/perf Performance
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.

None yet