{"action":"created","comment":{"url":"https://api.github.com/repos/ethereum/go-ethereum/pulls/comments/62814667","id":62814667,"diff_hunk":"@@ -304,6 +310,13 @@ func (d *Downloader) synchronise(id string, hash common.Hash, td *big.Int, mode\n \t\tdefault:\n \t\t}\n \t}\n+\tfor empty := false; !empty; {","path":"eth/downloader/downloader.go","position":122,"original_position":122,"commit_id":"b46d2a1ff139556941d68e541f059573129a78cb","original_commit_id":"b46d2a1ff139556941d68e541f059573129a78cb","user":{"login":"karalabe","id":129561,"avatar_url":"https://avatars.githubusercontent.com/u/129561?v=3","gravatar_id":"","url":"https://api.github.com/users/karalabe","html_url":"https://github.com/karalabe","followers_url":"https://api.github.com/users/karalabe/followers","following_url":"https://api.github.com/users/karalabe/following{/other_user}","gists_url":"https://api.github.com/users/karalabe/gists{/gist_id}","starred_url":"https://api.github.com/users/karalabe/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/karalabe/subscriptions","organizations_url":"https://api.github.com/users/karalabe/orgs","repos_url":"https://api.github.com/users/karalabe/repos","events_url":"https://api.github.com/users/karalabe/events{/privacy}","received_events_url":"https://api.github.com/users/karalabe/received_events","type":"User","site_admin":false},"body":"Though maybe we could have just added it to the above cycle which empties the wake channels.","created_at":"2016-05-11T09:10:17Z","updated_at":"2016-05-11T09:10:17Z","html_url":"https://github.com/ethereum/go-ethereum/pull/2315#discussion_r62814667","pull_request_url":"https://api.github.com/repos/ethereum/go-ethereum/pulls/2315","_links":{"self":{"href":"https://api.github.com/repos/ethereum/go-ethereum/pulls/comments/62814667"},"html":{"href":"https://github.com/ethereum/go-ethereum/pull/2315#discussion_r62814667"},"pull_request":{"href":"https://api.github.com/repos/ethereum/go-ethereum/pulls/2315"}}},"pull_request":{"url":"https://api.github.com/repos/ethereum/go-ethereum/pulls/2315","id":62237563,"html_url":"https://github.com/ethereum/go-ethereum/pull/2315","diff_url":"https://github.com/ethereum/go-ethereum/pull/2315.diff","patch_url":"https://github.com/ethereum/go-ethereum/pull/2315.patch","issue_url":"https://api.github.com/repos/ethereum/go-ethereum/issues/2315","number":2315,"state":"open","locked":false,"title":"eth/downloader: concurrent header downloads","user":{"login":"karalabe","id":129561,"avatar_url":"https://avatars.githubusercontent.com/u/129561?v=3","gravatar_id":"","url":"https://api.github.com/users/karalabe","html_url":"https://github.com/karalabe","followers_url":"https://api.github.com/users/karalabe/followers","following_url":"https://api.github.com/users/karalabe/following{/other_user}","gists_url":"https://api.github.com/users/karalabe/gists{/gist_id}","starred_url":"https://api.github.com/users/karalabe/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/karalabe/subscriptions","organizations_url":"https://api.github.com/users/karalabe/orgs","repos_url":"https://api.github.com/users/karalabe/repos","events_url":"https://api.github.com/users/karalabe/events{/privacy}","received_events_url":"https://api.github.com/users/karalabe/received_events","type":"User","site_admin":false},"body":"Geth currently uses a single peer to pull all the headers of the blockchain from, and uses all of its peers to fill in the block bodies, receipts, state, etc that the header chain defined. This unfortunately introduces a serious bottleneck for newly joining peers, where if they select a shitty peer to pull the headers from, the entire sync takes ages.\r\n\r\nThe obvious solution is to download headers from multiple peers concurrently, but that also has its gotchas, specifically that consecutive headers downloaded from different peers might not match up to each other. This might happen due to malicious peers deliberately feeding junk or simply due to a large enough fork (e.g. homestead transition)... and actually this was specifically something the C++ codebase was bitten with causing hard crashes during the testnet homestead fork. **The important lesson is that we need a mechanism to easily check if a batch of headers (seemingly) fits into our chain or not, without needing to actually import it.**\r\n\r\nAnother important feature that we need to maintain is that even if we have pad peers, we should be able to sync in a reasonable time. If we keep piecing together malicious header batches and throwing them away, valid downloaded data will also be lost and inherently sync time would suffer. This currently is avoided by the single-peer header-download which ensure that if we \"happen upon\" a good peer, bad peers cannot affect us any more (and bad peers get thrown out quite quickly). **The important takeaway is that if a single peer drives the header downloads, and it is good, bad peers cannot screw us any more, so it's essential to retain this capability even with concurrent headers.**\r\n\r\n## Algorithm\r\n\r\nThe solution implemented by this PR is based on the concept of a **header skeleton**:\r\n\r\n * A single master-peer is used to retrieve a skeleton of the header chain: only every Nth header is retrieved, forming gaps of N-1 headers.\r\n * Concurrently all the peers are used to fill in the missing N-1 headers, each batch consisting of the N-1 unknown headers, and also the Nth known header as the last one.\r\n\r\nThis this algorithms the concurrently pulled headers are guaranteed to fit the skeleton:\r\n\r\n * The batch of headers must define a proper parent->child number and hash progression.\r\n * The first header of the batch must have the correct starting number of the header gap.\r\n * The last header of the batch must be the one already defined by the skeleton.\r\n\r\nWith the above algorithm, we can guarantee that only headers that map cleanly onto the master-peer's skeleton will be accepted, and we can do this with only lightweight hasing and don't need to process anything. Thus if the master-peer is good, sync completes fast and clean.\r\n\r\nOn the other hand if the master peer is bad and tries to feed an invalid skeleton chain, either no peers can send us the correct data to fill the gaps (in the case of which we assume an attacker and from the master-peer), or the master peer itself does feed us junk, which we can detect later during processing and drop the master-peer.\r\n\r\n## Caveats\r\n\r\nThe `eth` protocol doesn't support request/response IDs, so we can only issue one request of a single type (e.g. header request) to be able and still match up the replies with the requests. This means that we cannot isolate the master-peer to only retrieve skeleton headers and use others to fill the gaps, since we might only have one peer (e.g. private network setting). To work around this, the PR retrieves headers in batches:\r\n\r\n * Fetch a small skeleton (e.g. N headers, with N-1 gaps in between = ~N^2 sized skeleton)\r\n * Fill in the gaps will every peer, including the chosen master-peer that defined the skeleton\r\n * Deliver the entire filled skeleton (i.e. proper header chain) for processing\r\n * Repeat with the next batch if everything went well\r\n\r\nAlthough the above batching solution works, it also introduces an annoying latency when one batch is finished and another is started, whereby during the filling of a skeleton batch, other parts of the downloader might starve (e.g. receipts aren't being pulled). This however can be solved quite easily by checking if a header delivery fills in a prefix of the skeleton and immediately stream the already completed parts to the rest of the downloader, without waiting for all the subsequent gaps to be done.\r\n\r\n## Performance\r\n\r\nThis this PR syncing the current testnet (~781K blocks) took 7 minutes and 50 seconds.","created_at":"2016-03-09T14:39:21Z","updated_at":"2016-05-11T09:10:17Z","closed_at":null,"merged_at":null,"merge_commit_sha":"6e2e684c9e9cfe8d9820b84e73f282bc28a2d4be","assignee":null,"milestone":{"url":"https://api.github.com/repos/ethereum/go-ethereum/milestones/26","html_url":"https://github.com/ethereum/go-ethereum/milestones/1.5.0","labels_url":"https://api.github.com/repos/ethereum/go-ethereum/milestones/26/labels","id":1593424,"number":26,"title":"1.5.0","description":"","creator":{"login":"karalabe","id":129561,"avatar_url":"https://avatars.githubusercontent.com/u/129561?v=3","gravatar_id":"","url":"https://api.github.com/users/karalabe","html_url":"https://github.com/karalabe","followers_url":"https://api.github.com/users/karalabe/followers","following_url":"https://api.github.com/users/karalabe/following{/other_user}","gists_url":"https://api.github.com/users/karalabe/gists{/gist_id}","starred_url":"https://api.github.com/users/karalabe/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/karalabe/subscriptions","organizations_url":"https://api.github.com/users/karalabe/orgs","repos_url":"https://api.github.com/users/karalabe/repos","events_url":"https://api.github.com/users/karalabe/events{/privacy}","received_events_url":"https://api.github.com/users/karalabe/received_events","type":"User","site_admin":false},"open_issues":28,"closed_issues":5,"state":"open","created_at":"2016-02-19T15:55:33Z","updated_at":"2016-05-11T08:10:28Z","due_on":null,"closed_at":null},"commits_url":"https://api.github.com/repos/ethereum/go-ethereum/pulls/2315/commits","review_comments_url":"https://api.github.com/repos/ethereum/go-ethereum/pulls/2315/comments","review_comment_url":"https://api.github.com/repos/ethereum/go-ethereum/pulls/comments{/number}","comments_url":"https://api.github.com/repos/ethereum/go-ethereum/issues/2315/comments","statuses_url":"https://api.github.com/repos/ethereum/go-ethereum/statuses/b46d2a1ff139556941d68e541f059573129a78cb","head":{"label":"karalabe:concurrent-headers-2","ref":"concurrent-headers-2","sha":"b46d2a1ff139556941d68e541f059573129a78cb","user":{"login":"karalabe","id":129561,"avatar_url":"https://avatars.githubusercontent.com/u/129561?v=3","gravatar_id":"","url":"https://api.github.com/users/karalabe","html_url":"https://github.com/karalabe","followers_url":"https://api.github.com/users/karalabe/followers","following_url":"https://api.github.com/users/karalabe/following{/other_user}","gists_url":"https://api.github.com/users/karalabe/gists{/gist_id}","starred_url":"https://api.github.com/users/karalabe/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/karalabe/subscriptions","organizations_url":"https://api.github.com/users/karalabe/orgs","repos_url":"https://api.github.com/users/karalabe/repos","events_url":"https://api.github.com/users/karalabe/events{/privacy}","received_events_url":"https://api.github.com/users/karalabe/received_events","type":"User","site_admin":false},"repo":{"id":33668567,"name":"go-ethereum","full_name":"karalabe/go-ethereum","owner":{"login":"karalabe","id":129561,"avatar_url":"https://avatars.githubusercontent.com/u/129561?v=3","gravatar_id":"","url":"https://api.github.com/users/karalabe","html_url":"https://github.com/karalabe","followers_url":"https://api.github.com/users/karalabe/followers","following_url":"https://api.github.com/users/karalabe/following{/other_user}","gists_url":"https://api.github.com/users/karalabe/gists{/gist_id}","starred_url":"https://api.github.com/users/karalabe/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/karalabe/subscriptions","organizations_url":"https://api.github.com/users/karalabe/orgs","repos_url":"https://api.github.com/users/karalabe/repos","events_url":"https://api.github.com/users/karalabe/events{/privacy}","received_events_url":"https://api.github.com/users/karalabe/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/karalabe/go-ethereum","description":"Jeffrey Wilcke's Go implementation of the Ethereum y/w paper","fork":true,"url":"https://api.github.com/repos/karalabe/go-ethereum","forks_url":"https://api.github.com/repos/karalabe/go-ethereum/forks","keys_url":"https://api.github.com/repos/karalabe/go-ethereum/keys{/key_id}","collaborators_url":"https://api.github.com/repos/karalabe/go-ethereum/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/karalabe/go-ethereum/teams","hooks_url":"https://api.github.com/repos/karalabe/go-ethereum/hooks","issue_events_url":"https://api.github.com/repos/karalabe/go-ethereum/issues/events{/number}","events_url":"https://api.github.com/repos/karalabe/go-ethereum/events","assignees_url":"https://api.github.com/repos/karalabe/go-ethereum/assignees{/user}","branches_url":"https://api.github.com/repos/karalabe/go-ethereum/branches{/branch}","tags_url":"https://api.github.com/repos/karalabe/go-ethereum/tags","blobs_url":"https://api.github.com/repos/karalabe/go-ethereum/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/karalabe/go-ethereum/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/karalabe/go-ethereum/git/refs{/sha}","trees_url":"https://api.github.com/repos/karalabe/go-ethereum/git/trees{/sha}","statuses_url":"https://api.github.com/repos/karalabe/go-ethereum/statuses/{sha}","languages_url":"https://api.github.com/repos/karalabe/go-ethereum/languages","stargazers_url":"https://api.github.com/repos/karalabe/go-ethereum/stargazers","contributors_url":"https://api.github.com/repos/karalabe/go-ethereum/contributors","subscribers_url":"https://api.github.com/repos/karalabe/go-ethereum/subscribers","subscription_url":"https://api.github.com/repos/karalabe/go-ethereum/subscription","commits_url":"https://api.github.com/repos/karalabe/go-ethereum/commits{/sha}","git_commits_url":"https://api.github.com/repos/karalabe/go-ethereum/git/commits{/sha}","comments_url":"https://api.github.com/repos/karalabe/go-ethereum/comments{/number}","issue_comment_url":"https://api.github.com/repos/karalabe/go-ethereum/issues/comments{/number}","contents_url":"https://api.github.com/repos/karalabe/go-ethereum/contents/{+path}","compare_url":"https://api.github.com/repos/karalabe/go-ethereum/compare/{base}...{head}","merges_url":"https://api.github.com/repos/karalabe/go-ethereum/merges","archive_url":"https://api.github.com/repos/karalabe/go-ethereum/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/karalabe/go-ethereum/downloads","issues_url":"https://api.github.com/repos/karalabe/go-ethereum/issues{/number}","pulls_url":"https://api.github.com/repos/karalabe/go-ethereum/pulls{/number}","milestones_url":"https://api.github.com/repos/karalabe/go-ethereum/milestones{/number}","notifications_url":"https://api.github.com/repos/karalabe/go-ethereum/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/karalabe/go-ethereum/labels{/name}","releases_url":"https://api.github.com/repos/karalabe/go-ethereum/releases{/id}","deployments_url":"https://api.github.com/repos/karalabe/go-ethereum/deployments","created_at":"2015-04-09T12:51:45Z","updated_at":"2016-02-23T11:27:22Z","pushed_at":"2016-05-11T08:59:09Z","git_url":"git://github.com/karalabe/go-ethereum.git","ssh_url":"git@github.com:karalabe/go-ethereum.git","clone_url":"https://github.com/karalabe/go-ethereum.git","svn_url":"https://github.com/karalabe/go-ethereum","homepage":"","size":58702,"stargazers_count":0,"watchers_count":0,"language":"Go","has_issues":false,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":0,"forks":0,"open_issues":0,"watchers":0,"default_branch":"develop"}},"base":{"label":"ethereum:develop","ref":"develop","sha":"a6ca8fd26884807c80b649bd2a0e780aa93ced22","user":{"login":"ethereum","id":6250754,"avatar_url":"https://avatars.githubusercontent.com/u/6250754?v=3","gravatar_id":"","url":"https://api.github.com/users/ethereum","html_url":"https://github.com/ethereum","followers_url":"https://api.github.com/users/ethereum/followers","following_url":"https://api.github.com/users/ethereum/following{/other_user}","gists_url":"https://api.github.com/users/ethereum/gists{/gist_id}","starred_url":"https://api.github.com/users/ethereum/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ethereum/subscriptions","organizations_url":"https://api.github.com/users/ethereum/orgs","repos_url":"https://api.github.com/users/ethereum/repos","events_url":"https://api.github.com/users/ethereum/events{/privacy}","received_events_url":"https://api.github.com/users/ethereum/received_events","type":"Organization","site_admin":false},"repo":{"id":15452919,"name":"go-ethereum","full_name":"ethereum/go-ethereum","owner":{"login":"ethereum","id":6250754,"avatar_url":"https://avatars.githubusercontent.com/u/6250754?v=3","gravatar_id":"","url":"https://api.github.com/users/ethereum","html_url":"https://github.com/ethereum","followers_url":"https://api.github.com/users/ethereum/followers","following_url":"https://api.github.com/users/ethereum/following{/other_user}","gists_url":"https://api.github.com/users/ethereum/gists{/gist_id}","starred_url":"https://api.github.com/users/ethereum/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ethereum/subscriptions","organizations_url":"https://api.github.com/users/ethereum/orgs","repos_url":"https://api.github.com/users/ethereum/repos","events_url":"https://api.github.com/users/ethereum/events{/privacy}","received_events_url":"https://api.github.com/users/ethereum/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/ethereum/go-ethereum","description":"Official golang implementation of the Ethereum protocol","fork":false,"url":"https://api.github.com/repos/ethereum/go-ethereum","forks_url":"https://api.github.com/repos/ethereum/go-ethereum/forks","keys_url":"https://api.github.com/repos/ethereum/go-ethereum/keys{/key_id}","collaborators_url":"https://api.github.com/repos/ethereum/go-ethereum/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/ethereum/go-ethereum/teams","hooks_url":"https://api.github.com/repos/ethereum/go-ethereum/hooks","issue_events_url":"https://api.github.com/repos/ethereum/go-ethereum/issues/events{/number}","events_url":"https://api.github.com/repos/ethereum/go-ethereum/events","assignees_url":"https://api.github.com/repos/ethereum/go-ethereum/assignees{/user}","branches_url":"https://api.github.com/repos/ethereum/go-ethereum/branches{/branch}","tags_url":"https://api.github.com/repos/ethereum/go-ethereum/tags","blobs_url":"https://api.github.com/repos/ethereum/go-ethereum/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/ethereum/go-ethereum/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/ethereum/go-ethereum/git/refs{/sha}","trees_url":"https://api.github.com/repos/ethereum/go-ethereum/git/trees{/sha}","statuses_url":"https://api.github.com/repos/ethereum/go-ethereum/statuses/{sha}","languages_url":"https://api.github.com/repos/ethereum/go-ethereum/languages","stargazers_url":"https://api.github.com/repos/ethereum/go-ethereum/stargazers","contributors_url":"https://api.github.com/repos/ethereum/go-ethereum/contributors","subscribers_url":"https://api.github.com/repos/ethereum/go-ethereum/subscribers","subscription_url":"https://api.github.com/repos/ethereum/go-ethereum/subscription","commits_url":"https://api.github.com/repos/ethereum/go-ethereum/commits{/sha}","git_commits_url":"https://api.github.com/repos/ethereum/go-ethereum/git/commits{/sha}","comments_url":"https://api.github.com/repos/ethereum/go-ethereum/comments{/number}","issue_comment_url":"https://api.github.com/repos/ethereum/go-ethereum/issues/comments{/number}","contents_url":"https://api.github.com/repos/ethereum/go-ethereum/contents/{+path}","compare_url":"https://api.github.com/repos/ethereum/go-ethereum/compare/{base}...{head}","merges_url":"https://api.github.com/repos/ethereum/go-ethereum/merges","archive_url":"https://api.github.com/repos/ethereum/go-ethereum/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/ethereum/go-ethereum/downloads","issues_url":"https://api.github.com/repos/ethereum/go-ethereum/issues{/number}","pulls_url":"https://api.github.com/repos/ethereum/go-ethereum/pulls{/number}","milestones_url":"https://api.github.com/repos/ethereum/go-ethereum/milestones{/number}","notifications_url":"https://api.github.com/repos/ethereum/go-ethereum/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/ethereum/go-ethereum/labels{/name}","releases_url":"https://api.github.com/repos/ethereum/go-ethereum/releases{/id}","deployments_url":"https://api.github.com/repos/ethereum/go-ethereum/deployments","created_at":"2013-12-26T13:05:46Z","updated_at":"2016-05-11T08:01:18Z","pushed_at":"2016-05-11T09:01:08Z","git_url":"git://github.com/ethereum/go-ethereum.git","ssh_url":"git@github.com:ethereum/go-ethereum.git","clone_url":"https://github.com/ethereum/go-ethereum.git","svn_url":"https://github.com/ethereum/go-ethereum","homepage":"http://ethereum.github.io/go-ethereum/","size":160823,"stargazers_count":1436,"watchers_count":1436,"language":"Go","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":true,"forks_count":455,"mirror_url":null,"open_issues_count":210,"forks":455,"open_issues":210,"watchers":1436,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/ethereum/go-ethereum/pulls/2315"},"html":{"href":"https://github.com/ethereum/go-ethereum/pull/2315"},"issue":{"href":"https://api.github.com/repos/ethereum/go-ethereum/issues/2315"},"comments":{"href":"https://api.github.com/repos/ethereum/go-ethereum/issues/2315/comments"},"review_comments":{"href":"https://api.github.com/repos/ethereum/go-ethereum/pulls/2315/comments"},"review_comment":{"href":"https://api.github.com/repos/ethereum/go-ethereum/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/ethereum/go-ethereum/pulls/2315/commits"},"statuses":{"href":"https://api.github.com/repos/ethereum/go-ethereum/statuses/b46d2a1ff139556941d68e541f059573129a78cb"}}}}