{"action":"created","comment":{"url":"https://api.github.com/repos/paritytech/parity/pulls/comments/196707660","pull_request_review_id":130310101,"id":196707660,"node_id":"MDI0OlB1bGxSZXF1ZXN0UmV2aWV3Q29tbWVudDE5NjcwNzY2MA==","diff_hunk":"@@ -0,0 +1,13 @@\n+[package]\n+name = \"blooms-db\"\n+version = \"0.1.0\"\n+authors = [\"debris <marek.kotewicz@gmail.com>\"]","path":"util/blooms-db/Cargo.toml","position":4,"original_position":4,"commit_id":"f37f5e749ed8c1e372f2eb34dc81be236c0b8819","original_commit_id":"447950e7c160b8ee2c886d3659007fc7cf50567f","user":{"login":"debris","id":2613714,"node_id":"MDQ6VXNlcjI2MTM3MTQ=","avatar_url":"https://avatars2.githubusercontent.com/u/2613714?v=4","gravatar_id":"","url":"https://api.github.com/users/debris","html_url":"https://github.com/debris","followers_url":"https://api.github.com/users/debris/followers","following_url":"https://api.github.com/users/debris/following{/other_user}","gists_url":"https://api.github.com/users/debris/gists{/gist_id}","starred_url":"https://api.github.com/users/debris/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/debris/subscriptions","organizations_url":"https://api.github.com/users/debris/orgs","repos_url":"https://api.github.com/users/debris/repos","events_url":"https://api.github.com/users/debris/events{/privacy}","received_events_url":"https://api.github.com/users/debris/received_events","type":"User","site_admin":false},"body":"actually, you are right. We usually have a `license` field so I'll also add it :)","created_at":"2018-06-20T09:29:04Z","updated_at":"2018-06-20T09:29:04Z","html_url":"https://github.com/paritytech/parity/pull/8712#discussion_r196707660","pull_request_url":"https://api.github.com/repos/paritytech/parity/pulls/8712","author_association":"MEMBER","_links":{"self":{"href":"https://api.github.com/repos/paritytech/parity/pulls/comments/196707660"},"html":{"href":"https://github.com/paritytech/parity/pull/8712#discussion_r196707660"},"pull_request":{"href":"https://api.github.com/repos/paritytech/parity/pulls/8712"}},"in_reply_to_id":196487619},"pull_request":{"url":"https://api.github.com/repos/paritytech/parity/pulls/8712","id":190470317,"node_id":"MDExOlB1bGxSZXF1ZXN0MTkwNDcwMzE3","html_url":"https://github.com/paritytech/parity/pull/8712","diff_url":"https://github.com/paritytech/parity/pull/8712.diff","patch_url":"https://github.com/paritytech/parity/pull/8712.patch","issue_url":"https://api.github.com/repos/paritytech/parity/issues/8712","number":8712,"state":"open","locked":false,"title":"new blooms database","user":{"login":"debris","id":2613714,"node_id":"MDQ6VXNlcjI2MTM3MTQ=","avatar_url":"https://avatars2.githubusercontent.com/u/2613714?v=4","gravatar_id":"","url":"https://api.github.com/users/debris","html_url":"https://github.com/debris","followers_url":"https://api.github.com/users/debris/followers","following_url":"https://api.github.com/users/debris/following{/other_user}","gists_url":"https://api.github.com/users/debris/gists{/gist_id}","starred_url":"https://api.github.com/users/debris/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/debris/subscriptions","organizations_url":"https://api.github.com/users/debris/orgs","repos_url":"https://api.github.com/users/debris/repos","events_url":"https://api.github.com/users/debris/events{/privacy}","received_events_url":"https://api.github.com/users/debris/received_events","type":"User","site_admin":false},"body":"This pr introduces new database for header blooms.\r\n\r\n#### Why?\r\nThe only time when we access blooms is when we are filtering logs. Filtering logs requires iteration over all blooms in a database and this is very inefficient with RocksDB. As blockchain got bigger and bigger it took more and more time to effectively filter all blooms starting from the genesis block.\r\n\r\n#### How?\r\nI built increment only, sequential database for storing blooms. It consists of three database layers. `top`, `mid`, `bot`.\r\n\r\n- `bot` layer contains all header blooms\r\n- `mid` layer contains blooms created from 16 consecutive blooms of the `bot` layer. \r\n- `top` layer contains blooms from 16 consecutive blooms from the `mid` layer. \r\n\r\nBlooms at each layer are placed next to each other on a disk. So it's very efficient to find `O(1)~` and iterate `O(1)~` over them. It's a huge improvement compared to the previous database implementation where every lookup and step of iteration was probably `O(log n)`.\r\n\r\nsize of a database (for 1000000 blocks)\r\n- `bot` layer - *256mb* (1000000 * size_of_bloom (256b))\r\n- `mid` layer - *16mb* (`bot` / 16)\r\n- `top` layer - *1mb* (`mid` /  16)\r\n\r\n#### Other issues addressed\r\n- #8552 - this pr also addresses #8552 by simply **not recomputing** blooms at higher levels. Why? Because in case of a fork, it's likely that the same transaction on a different chain will be included in block of the same number or in one of the following blocks. As long as the distance between block on chain a, and block on chain b, is on average significantly lower than 128, false-positive ration of bloom filter should not increase. And even if the `top` and `mid` bloom return the false-positive, the underlying bottom bloom is replaced with a new one, so this will not lead to incorrect results.\r\n\r\n  https://github.com/paritytech/parity/blob/343b29866c4cc592afa9038995217b6ba99e70fa/util/blooms-db/src/db.rs#L96-L98\r\n\r\n- this pr also addresses all issues with bloom recomputation on forks. Recomputation does not happen and there is no in-memory cache, so blooms are always valid\r\n\r\n#### todo list (in this pr)\r\n- [x] new blooms-db\r\n- [x] new database interface for parity (aka `BlockChainDB`)\r\n- [x] integrate new db interface with parity and tests (😓 )\r\n- [x] `BlockChainDB` should not expose `&RwLock` in the interface\r\n- [x] fix and tests for blooms-db flushing\r\n- [x] migrate traces to the new blooms-db\r\n- [x] remove old `bloomchain` crate\r\n- [x] filter multiple bloom possibilities at the same time\r\n- [x] restore blooms after snapshot\r\n- [x] write database migration script\r\n\r\n#### benchmarks\r\n\r\n- So far I run only a single benchmark for blooms-db. The results are promising, but I believe that they do not fully show how much everything has improved.\r\n\r\n  benchmark from old [stackoverflow thread](https://ethereum.stackexchange.com/questions/2190/is-searching-data-stored-in-event-logs-prohibitively-slow/2195#2195)\r\n\r\n  ```\r\n  time curl -X POST --data '{\"id\":8,\"jsonrpc\":\"2.0\",\"method\":\"eth_getLogs\",\"params\":[{\"fromBlock\":\"0x0\",\"toBlock\":\"0xf0be2\", \"address\": \"0x33990122638b9132ca29c723bdf037f1a891a70c\"}]}' -H \"Content-Type: application/json\" http://127.0.0.1:8545 >> /dev/null\r\n  ```\r\n\r\n  old parity:\r\n\r\n  ```\r\n  0.77s\r\n  ```\r\n\r\n  this branch:\r\n\r\n  ```\r\n  0.01s\r\n  ```\r\n\r\n---\r\n\r\nThis pr, should also reduce disk writes by roughly **70gb** when doing full sync\r\n\r\n```\r\n3 * 5670000 * 16 * 256 bytes = 69.67296 gigabytes\r\n```\r\n\r\n- 3 - bloom levels\r\n- 5670000 - number of blocks\r\n- 16 - currently blooms are stored in groups containing 16 blooms\r\n- 256 - size of a bloom","created_at":"2018-05-25T03:04:14Z","updated_at":"2018-06-20T09:29:04Z","closed_at":null,"merged_at":null,"merge_commit_sha":"af945dbabbfa24ca0f2f9ca95dbace3df9cf3b7d","assignee":null,"assignees":[],"requested_reviewers":[],"requested_teams":[],"labels":[{"id":309708100,"node_id":"MDU6TGFiZWwzMDk3MDgxMDA=","url":"https://api.github.com/repos/paritytech/parity/labels/A0-pleasereview","name":"A0-pleasereview","color":"666666","default":false},{"id":441816407,"node_id":"MDU6TGFiZWw0NDE4MTY0MDc=","url":"https://api.github.com/repos/paritytech/parity/labels/M4-core","name":"M4-core","color":"F5FCE6","default":false}],"milestone":{"url":"https://api.github.com/repos/paritytech/parity/milestones/21","html_url":"https://github.com/paritytech/parity/milestone/21","labels_url":"https://api.github.com/repos/paritytech/parity/milestones/21/labels","id":3057411,"node_id":"MDk6TWlsZXN0b25lMzA1NzQxMQ==","number":21,"title":"1.12","description":"","creator":{"login":"5chdn","id":15729797,"node_id":"MDQ6VXNlcjE1NzI5Nzk3","avatar_url":"https://avatars3.githubusercontent.com/u/15729797?v=4","gravatar_id":"","url":"https://api.github.com/users/5chdn","html_url":"https://github.com/5chdn","followers_url":"https://api.github.com/users/5chdn/followers","following_url":"https://api.github.com/users/5chdn/following{/other_user}","gists_url":"https://api.github.com/users/5chdn/gists{/gist_id}","starred_url":"https://api.github.com/users/5chdn/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/5chdn/subscriptions","organizations_url":"https://api.github.com/users/5chdn/orgs","repos_url":"https://api.github.com/users/5chdn/repos","events_url":"https://api.github.com/users/5chdn/events{/privacy}","received_events_url":"https://api.github.com/users/5chdn/received_events","type":"User","site_admin":false},"open_issues":143,"closed_issues":420,"state":"open","created_at":"2018-01-23T13:30:50Z","updated_at":"2018-06-20T09:28:40Z","due_on":"2018-06-25T07:00:00Z","closed_at":null},"commits_url":"https://api.github.com/repos/paritytech/parity/pulls/8712/commits","review_comments_url":"https://api.github.com/repos/paritytech/parity/pulls/8712/comments","review_comment_url":"https://api.github.com/repos/paritytech/parity/pulls/comments{/number}","comments_url":"https://api.github.com/repos/paritytech/parity/issues/8712/comments","statuses_url":"https://api.github.com/repos/paritytech/parity/statuses/f37f5e749ed8c1e372f2eb34dc81be236c0b8819","head":{"label":"paritytech:new-blooms-db","ref":"new-blooms-db","sha":"f37f5e749ed8c1e372f2eb34dc81be236c0b8819","user":{"login":"paritytech","id":14176906,"node_id":"MDEyOk9yZ2FuaXphdGlvbjE0MTc2OTA2","avatar_url":"https://avatars2.githubusercontent.com/u/14176906?v=4","gravatar_id":"","url":"https://api.github.com/users/paritytech","html_url":"https://github.com/paritytech","followers_url":"https://api.github.com/users/paritytech/followers","following_url":"https://api.github.com/users/paritytech/following{/other_user}","gists_url":"https://api.github.com/users/paritytech/gists{/gist_id}","starred_url":"https://api.github.com/users/paritytech/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/paritytech/subscriptions","organizations_url":"https://api.github.com/users/paritytech/orgs","repos_url":"https://api.github.com/users/paritytech/repos","events_url":"https://api.github.com/users/paritytech/events{/privacy}","received_events_url":"https://api.github.com/users/paritytech/received_events","type":"Organization","site_admin":false},"repo":{"id":46714939,"node_id":"MDEwOlJlcG9zaXRvcnk0NjcxNDkzOQ==","name":"parity","full_name":"paritytech/parity","owner":{"login":"paritytech","id":14176906,"node_id":"MDEyOk9yZ2FuaXphdGlvbjE0MTc2OTA2","avatar_url":"https://avatars2.githubusercontent.com/u/14176906?v=4","gravatar_id":"","url":"https://api.github.com/users/paritytech","html_url":"https://github.com/paritytech","followers_url":"https://api.github.com/users/paritytech/followers","following_url":"https://api.github.com/users/paritytech/following{/other_user}","gists_url":"https://api.github.com/users/paritytech/gists{/gist_id}","starred_url":"https://api.github.com/users/paritytech/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/paritytech/subscriptions","organizations_url":"https://api.github.com/users/paritytech/orgs","repos_url":"https://api.github.com/users/paritytech/repos","events_url":"https://api.github.com/users/paritytech/events{/privacy}","received_events_url":"https://api.github.com/users/paritytech/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/paritytech/parity","description":"Fast, light, robust Ethereum implementation.","fork":false,"url":"https://api.github.com/repos/paritytech/parity","forks_url":"https://api.github.com/repos/paritytech/parity/forks","keys_url":"https://api.github.com/repos/paritytech/parity/keys{/key_id}","collaborators_url":"https://api.github.com/repos/paritytech/parity/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/paritytech/parity/teams","hooks_url":"https://api.github.com/repos/paritytech/parity/hooks","issue_events_url":"https://api.github.com/repos/paritytech/parity/issues/events{/number}","events_url":"https://api.github.com/repos/paritytech/parity/events","assignees_url":"https://api.github.com/repos/paritytech/parity/assignees{/user}","branches_url":"https://api.github.com/repos/paritytech/parity/branches{/branch}","tags_url":"https://api.github.com/repos/paritytech/parity/tags","blobs_url":"https://api.github.com/repos/paritytech/parity/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/paritytech/parity/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/paritytech/parity/git/refs{/sha}","trees_url":"https://api.github.com/repos/paritytech/parity/git/trees{/sha}","statuses_url":"https://api.github.com/repos/paritytech/parity/statuses/{sha}","languages_url":"https://api.github.com/repos/paritytech/parity/languages","stargazers_url":"https://api.github.com/repos/paritytech/parity/stargazers","contributors_url":"https://api.github.com/repos/paritytech/parity/contributors","subscribers_url":"https://api.github.com/repos/paritytech/parity/subscribers","subscription_url":"https://api.github.com/repos/paritytech/parity/subscription","commits_url":"https://api.github.com/repos/paritytech/parity/commits{/sha}","git_commits_url":"https://api.github.com/repos/paritytech/parity/git/commits{/sha}","comments_url":"https://api.github.com/repos/paritytech/parity/comments{/number}","issue_comment_url":"https://api.github.com/repos/paritytech/parity/issues/comments{/number}","contents_url":"https://api.github.com/repos/paritytech/parity/contents/{+path}","compare_url":"https://api.github.com/repos/paritytech/parity/compare/{base}...{head}","merges_url":"https://api.github.com/repos/paritytech/parity/merges","archive_url":"https://api.github.com/repos/paritytech/parity/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/paritytech/parity/downloads","issues_url":"https://api.github.com/repos/paritytech/parity/issues{/number}","pulls_url":"https://api.github.com/repos/paritytech/parity/pulls{/number}","milestones_url":"https://api.github.com/repos/paritytech/parity/milestones{/number}","notifications_url":"https://api.github.com/repos/paritytech/parity/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/paritytech/parity/labels{/name}","releases_url":"https://api.github.com/repos/paritytech/parity/releases{/id}","deployments_url":"https://api.github.com/repos/paritytech/parity/deployments","created_at":"2015-11-23T11:07:32Z","updated_at":"2018-06-20T06:49:34Z","pushed_at":"2018-06-20T09:26:58Z","git_url":"git://github.com/paritytech/parity.git","ssh_url":"git@github.com:paritytech/parity.git","clone_url":"https://github.com/paritytech/parity.git","svn_url":"https://github.com/paritytech/parity","homepage":"https://parity.io","size":53834,"stargazers_count":4423,"watchers_count":4423,"language":"Rust","has_issues":true,"has_projects":true,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":892,"mirror_url":null,"archived":false,"open_issues_count":206,"license":{"key":"other","name":"Other","spdx_id":null,"url":null,"node_id":"MDc6TGljZW5zZTA="},"forks":892,"open_issues":206,"watchers":4423,"default_branch":"master"}},"base":{"label":"paritytech:master","ref":"master","sha":"08e46432c5e66b0088ecd5cf235cd943a0f12122","user":{"login":"paritytech","id":14176906,"node_id":"MDEyOk9yZ2FuaXphdGlvbjE0MTc2OTA2","avatar_url":"https://avatars2.githubusercontent.com/u/14176906?v=4","gravatar_id":"","url":"https://api.github.com/users/paritytech","html_url":"https://github.com/paritytech","followers_url":"https://api.github.com/users/paritytech/followers","following_url":"https://api.github.com/users/paritytech/following{/other_user}","gists_url":"https://api.github.com/users/paritytech/gists{/gist_id}","starred_url":"https://api.github.com/users/paritytech/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/paritytech/subscriptions","organizations_url":"https://api.github.com/users/paritytech/orgs","repos_url":"https://api.github.com/users/paritytech/repos","events_url":"https://api.github.com/users/paritytech/events{/privacy}","received_events_url":"https://api.github.com/users/paritytech/received_events","type":"Organization","site_admin":false},"repo":{"id":46714939,"node_id":"MDEwOlJlcG9zaXRvcnk0NjcxNDkzOQ==","name":"parity","full_name":"paritytech/parity","owner":{"login":"paritytech","id":14176906,"node_id":"MDEyOk9yZ2FuaXphdGlvbjE0MTc2OTA2","avatar_url":"https://avatars2.githubusercontent.com/u/14176906?v=4","gravatar_id":"","url":"https://api.github.com/users/paritytech","html_url":"https://github.com/paritytech","followers_url":"https://api.github.com/users/paritytech/followers","following_url":"https://api.github.com/users/paritytech/following{/other_user}","gists_url":"https://api.github.com/users/paritytech/gists{/gist_id}","starred_url":"https://api.github.com/users/paritytech/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/paritytech/subscriptions","organizations_url":"https://api.github.com/users/paritytech/orgs","repos_url":"https://api.github.com/users/paritytech/repos","events_url":"https://api.github.com/users/paritytech/events{/privacy}","received_events_url":"https://api.github.com/users/paritytech/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/paritytech/parity","description":"Fast, light, robust Ethereum implementation.","fork":false,"url":"https://api.github.com/repos/paritytech/parity","forks_url":"https://api.github.com/repos/paritytech/parity/forks","keys_url":"https://api.github.com/repos/paritytech/parity/keys{/key_id}","collaborators_url":"https://api.github.com/repos/paritytech/parity/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/paritytech/parity/teams","hooks_url":"https://api.github.com/repos/paritytech/parity/hooks","issue_events_url":"https://api.github.com/repos/paritytech/parity/issues/events{/number}","events_url":"https://api.github.com/repos/paritytech/parity/events","assignees_url":"https://api.github.com/repos/paritytech/parity/assignees{/user}","branches_url":"https://api.github.com/repos/paritytech/parity/branches{/branch}","tags_url":"https://api.github.com/repos/paritytech/parity/tags","blobs_url":"https://api.github.com/repos/paritytech/parity/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/paritytech/parity/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/paritytech/parity/git/refs{/sha}","trees_url":"https://api.github.com/repos/paritytech/parity/git/trees{/sha}","statuses_url":"https://api.github.com/repos/paritytech/parity/statuses/{sha}","languages_url":"https://api.github.com/repos/paritytech/parity/languages","stargazers_url":"https://api.github.com/repos/paritytech/parity/stargazers","contributors_url":"https://api.github.com/repos/paritytech/parity/contributors","subscribers_url":"https://api.github.com/repos/paritytech/parity/subscribers","subscription_url":"https://api.github.com/repos/paritytech/parity/subscription","commits_url":"https://api.github.com/repos/paritytech/parity/commits{/sha}","git_commits_url":"https://api.github.com/repos/paritytech/parity/git/commits{/sha}","comments_url":"https://api.github.com/repos/paritytech/parity/comments{/number}","issue_comment_url":"https://api.github.com/repos/paritytech/parity/issues/comments{/number}","contents_url":"https://api.github.com/repos/paritytech/parity/contents/{+path}","compare_url":"https://api.github.com/repos/paritytech/parity/compare/{base}...{head}","merges_url":"https://api.github.com/repos/paritytech/parity/merges","archive_url":"https://api.github.com/repos/paritytech/parity/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/paritytech/parity/downloads","issues_url":"https://api.github.com/repos/paritytech/parity/issues{/number}","pulls_url":"https://api.github.com/repos/paritytech/parity/pulls{/number}","milestones_url":"https://api.github.com/repos/paritytech/parity/milestones{/number}","notifications_url":"https://api.github.com/repos/paritytech/parity/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/paritytech/parity/labels{/name}","releases_url":"https://api.github.com/repos/paritytech/parity/releases{/id}","deployments_url":"https://api.github.com/repos/paritytech/parity/deployments","created_at":"2015-11-23T11:07:32Z","updated_at":"2018-06-20T06:49:34Z","pushed_at":"2018-06-20T09:26:58Z","git_url":"git://github.com/paritytech/parity.git","ssh_url":"git@github.com:paritytech/parity.git","clone_url":"https://github.com/paritytech/parity.git","svn_url":"https://github.com/paritytech/parity","homepage":"https://parity.io","size":53834,"stargazers_count":4423,"watchers_count":4423,"language":"Rust","has_issues":true,"has_projects":true,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":892,"mirror_url":null,"archived":false,"open_issues_count":206,"license":{"key":"other","name":"Other","spdx_id":null,"url":null,"node_id":"MDc6TGljZW5zZTA="},"forks":892,"open_issues":206,"watchers":4423,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/paritytech/parity/pulls/8712"},"html":{"href":"https://github.com/paritytech/parity/pull/8712"},"issue":{"href":"https://api.github.com/repos/paritytech/parity/issues/8712"},"comments":{"href":"https://api.github.com/repos/paritytech/parity/issues/8712/comments"},"review_comments":{"href":"https://api.github.com/repos/paritytech/parity/pulls/8712/comments"},"review_comment":{"href":"https://api.github.com/repos/paritytech/parity/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/paritytech/parity/pulls/8712/commits"},"statuses":{"href":"https://api.github.com/repos/paritytech/parity/statuses/f37f5e749ed8c1e372f2eb34dc81be236c0b8819"}},"author_association":"MEMBER"}}
{"actor":{"display_login":"debris"}}