{"action":"created","comment":{"url":"https://api.github.com/repos/influxdb/influxdb/pulls/comments/47963006","id":47963006,"diff_hunk":"@@ -443,110 +445,188 @@ type tsmKeyIterator struct {\n \t// err is any error we received while iterating values.\n \terr error\n \n+\tsize int\n \t// key is the current key lowest key across all readers that has not be fully exhausted\n \t// of values.\n \tkey string\n+\n+\titerators []*BlockIterator\n+\tblocks    blocks\n+\n+\tbuf blocks\n+}\n+\n+type block struct {\n+\tkey              string\n+\tminTime, maxTime time.Time\n+\tb                []byte\n+}\n+\n+type blocks []*block\n+\n+func (a blocks) Len() int { return len(a) }\n+\n+func (a blocks) Less(i, j int) bool {\n+\tif a[i].key == a[j].key {\n+\t\treturn a[i].minTime.Before(a[j].minTime)\n+\t}\n+\treturn a[i].key < a[j].key\n }\n \n-func NewTSMKeyIterator(readers ...*TSMReader) (KeyIterator, error) {\n+func (a blocks) Swap(i, j int) { a[i], a[j] = a[j], a[i] }\n+\n+func NewTSMKeyIterator(size int, readers ...*TSMReader) (KeyIterator, error) {\n+\tvar iter []*BlockIterator\n+\tfor _, r := range readers {\n+\t\titer = append(iter, r.BlockIterator())\n+\t}\n+\n \treturn &tsmKeyIterator{\n-\t\treaders: readers,\n-\t\tvalues:  map[string][]Value{},\n-\t\tpos:     make([]int, len(readers)),\n-\t\tkeys:    make([]string, len(readers)),\n+\t\treaders:   readers,\n+\t\tvalues:    map[string][]Value{},\n+\t\tpos:       make([]int, len(readers)),\n+\t\tkeys:      make([]string, len(readers)),\n+\t\tsize:      size,\n+\t\titerators: iter,\n+\t\tbuf:       make([]*block, len(iter)),\n \t}, nil\n }\n \n func (k *tsmKeyIterator) Next() bool {\n-\t// If we have a key from the prior iteration, purge it and it's values from the\n-\t// values map.  We're done with it.\n-\tif k.key != \"\" {\n-\t\tdelete(k.values, k.key)\n-\t\tfor i, readerKey := range k.keys {\n-\t\t\tif readerKey == k.key {\n-\t\t\t\tk.keys[i] = \"\"\n+\t// If we still have blocks from the last read, slice off the current one\n+\t// and return\n+\tif len(k.blocks) > 0 {\n+\t\tk.blocks = k.blocks[1:]\n+\t\tif len(k.blocks) > 0 {\n+\t\t\treturn true\n+\t\t}\n+\t}\n+\n+\t// Read the next block from each TSM iterator\n+\tfor i, v := range k.buf {\n+\t\tif v == nil {\n+\t\t\titer := k.iterators[i]\n+\t\t\tif iter.Next() {\n+\t\t\t\tkey, minTime, maxTime, b, err := iter.Read()\n+\t\t\t\tif err != nil {\n+\t\t\t\t\tk.err = err\n+\t\t\t\t}\n+\n+\t\t\t\tk.buf[i] = &block{\n+\t\t\t\t\tminTime: minTime,\n+\t\t\t\t\tmaxTime: maxTime,\n+\t\t\t\t\tkey:     key,\n+\t\t\t\t\tb:       b,\n+\t\t\t\t}\n \t\t\t}\n \t\t}\n \t}\n \n-\tvar skipSearch bool\n-\t// For each iterator, group up all the values for their current key.\n-\tfor i, r := range k.readers {\n-\t\tif k.keys[i] != \"\" {\n+\t// Each reader could have a different key that it's currently at, need to find\n+\t// the next smallest one to keep the sort ordering.\n+\tvar minKey string\n+\tfor _, b := range k.buf {\n+\t\t// block could be nil if the iterator has been exhausted for that file\n+\t\tif b == nil {\n \t\t\tcontinue\n \t\t}\n+\t\tif minKey == \"\" || b.key < minKey {\n+\t\t\tminKey = b.key\n+\t\t}\n+\t}\n \n-\t\t// Grab the key for this reader\n-\t\tkey, entries := r.Key(k.pos[i])\n-\t\tk.keys[i] = key\n+\t// Now we need to find all blocks that match the min key so we can combine and dedup","path":"tsdb/engine/tsm1/compact.go","position":165,"original_position":165,"commit_id":"825296ddd8c4e971a92f2d50784c574d674c5666","original_commit_id":"825296ddd8c4e971a92f2d50784c574d674c5666","user":{"login":"otoolep","id":536312,"avatar_url":"https://avatars.githubusercontent.com/u/536312?v=3","gravatar_id":"","url":"https://api.github.com/users/otoolep","html_url":"https://github.com/otoolep","followers_url":"https://api.github.com/users/otoolep/followers","following_url":"https://api.github.com/users/otoolep/following{/other_user}","gists_url":"https://api.github.com/users/otoolep/gists{/gist_id}","starred_url":"https://api.github.com/users/otoolep/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/otoolep/subscriptions","organizations_url":"https://api.github.com/users/otoolep/orgs","repos_url":"https://api.github.com/users/otoolep/repos","events_url":"https://api.github.com/users/otoolep/events{/privacy}","received_events_url":"https://api.github.com/users/otoolep/received_events","type":"User","site_admin":false},"body":"dedup -> dedupe","created_at":"2015-12-17T21:23:59Z","updated_at":"2015-12-17T21:23:59Z","html_url":"https://github.com/influxdb/influxdb/pull/5142#discussion_r47963006","pull_request_url":"https://api.github.com/repos/influxdb/influxdb/pulls/5142","_links":{"self":{"href":"https://api.github.com/repos/influxdb/influxdb/pulls/comments/47963006"},"html":{"href":"https://github.com/influxdb/influxdb/pull/5142#discussion_r47963006"},"pull_request":{"href":"https://api.github.com/repos/influxdb/influxdb/pulls/5142"}}},"pull_request":{"url":"https://api.github.com/repos/influxdb/influxdb/pulls/5142","id":53866466,"html_url":"https://github.com/influxdb/influxdb/pull/5142","diff_url":"https://github.com/influxdb/influxdb/pull/5142.diff","patch_url":"https://github.com/influxdb/influxdb/pull/5142.patch","issue_url":"https://api.github.com/repos/influxdb/influxdb/issues/5142","number":5142,"state":"open","locked":false,"title":"Optimize TSM compaction","user":{"login":"jwilder","id":219935,"avatar_url":"https://avatars.githubusercontent.com/u/219935?v=3","gravatar_id":"","url":"https://api.github.com/users/jwilder","html_url":"https://github.com/jwilder","followers_url":"https://api.github.com/users/jwilder/followers","following_url":"https://api.github.com/users/jwilder/following{/other_user}","gists_url":"https://api.github.com/users/jwilder/gists{/gist_id}","starred_url":"https://api.github.com/users/jwilder/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jwilder/subscriptions","organizations_url":"https://api.github.com/users/jwilder/orgs","repos_url":"https://api.github.com/users/jwilder/repos","events_url":"https://api.github.com/users/jwilder/events{/privacy}","received_events_url":"https://api.github.com/users/jwilder/received_events","type":"User","site_admin":false},"body":"This PR optimizes the TSM compactions so that they can keep up with the cache compactions.  It does this re-working the `KeyIterator` interface to return encoded blocks instead of `[]Value` which allows the TSM compaction to skip decoding for consecutive blocks that don't overlap in time.  Another change is that the compaction process now just iterates over each block in order instead of searching the index and reading all the values for a key.  This also reduces the memory footprint for larger compactions.\r\n\r\nSome other changes that are part of the PR are:\r\n\r\n* Optimized TSM file loading to not allocate as much when initializing the `indirectIndex`\r\n* Load TSM files concurrently when the file store is opened\r\n* Fixed a bug where TSM files would be out of order in the file store causing incorrect query results\r\n* Fixed a decoding bug in `influx_inspect` that would report string blocks as corrupt\r\n* Added max value block size chunking back (was removed when `MergeIterator` was deleted)\r\n\r\nThere are more optimizations that could be made to avoid decoding blocks in some cases, but have left those for another time since this PR seems to resolve the TSM compaction slowness as is.\r\n\r\n@otoolep @pauldix ","created_at":"2015-12-16T16:45:05Z","updated_at":"2015-12-17T21:23:59Z","closed_at":null,"merged_at":null,"merge_commit_sha":"ef4965bbced0e737b4092e4867abe69ebd9447ab","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/influxdb/influxdb/pulls/5142/commits","review_comments_url":"https://api.github.com/repos/influxdb/influxdb/pulls/5142/comments","review_comment_url":"https://api.github.com/repos/influxdb/influxdb/pulls/comments{/number}","comments_url":"https://api.github.com/repos/influxdb/influxdb/issues/5142/comments","statuses_url":"https://api.github.com/repos/influxdb/influxdb/statuses/825296ddd8c4e971a92f2d50784c574d674c5666","head":{"label":"influxdb:jw-tsm-migrate","ref":"jw-tsm-migrate","sha":"825296ddd8c4e971a92f2d50784c574d674c5666","user":{"login":"influxdb","id":5713248,"avatar_url":"https://avatars.githubusercontent.com/u/5713248?v=3","gravatar_id":"","url":"https://api.github.com/users/influxdb","html_url":"https://github.com/influxdb","followers_url":"https://api.github.com/users/influxdb/followers","following_url":"https://api.github.com/users/influxdb/following{/other_user}","gists_url":"https://api.github.com/users/influxdb/gists{/gist_id}","starred_url":"https://api.github.com/users/influxdb/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/influxdb/subscriptions","organizations_url":"https://api.github.com/users/influxdb/orgs","repos_url":"https://api.github.com/users/influxdb/repos","events_url":"https://api.github.com/users/influxdb/events{/privacy}","received_events_url":"https://api.github.com/users/influxdb/received_events","type":"Organization","site_admin":false},"repo":{"id":13124802,"name":"influxdb","full_name":"influxdb/influxdb","owner":{"login":"influxdb","id":5713248,"avatar_url":"https://avatars.githubusercontent.com/u/5713248?v=3","gravatar_id":"","url":"https://api.github.com/users/influxdb","html_url":"https://github.com/influxdb","followers_url":"https://api.github.com/users/influxdb/followers","following_url":"https://api.github.com/users/influxdb/following{/other_user}","gists_url":"https://api.github.com/users/influxdb/gists{/gist_id}","starred_url":"https://api.github.com/users/influxdb/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/influxdb/subscriptions","organizations_url":"https://api.github.com/users/influxdb/orgs","repos_url":"https://api.github.com/users/influxdb/repos","events_url":"https://api.github.com/users/influxdb/events{/privacy}","received_events_url":"https://api.github.com/users/influxdb/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/influxdb/influxdb","description":"Scalable datastore for metrics, events, and real-time analytics","fork":false,"url":"https://api.github.com/repos/influxdb/influxdb","forks_url":"https://api.github.com/repos/influxdb/influxdb/forks","keys_url":"https://api.github.com/repos/influxdb/influxdb/keys{/key_id}","collaborators_url":"https://api.github.com/repos/influxdb/influxdb/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/influxdb/influxdb/teams","hooks_url":"https://api.github.com/repos/influxdb/influxdb/hooks","issue_events_url":"https://api.github.com/repos/influxdb/influxdb/issues/events{/number}","events_url":"https://api.github.com/repos/influxdb/influxdb/events","assignees_url":"https://api.github.com/repos/influxdb/influxdb/assignees{/user}","branches_url":"https://api.github.com/repos/influxdb/influxdb/branches{/branch}","tags_url":"https://api.github.com/repos/influxdb/influxdb/tags","blobs_url":"https://api.github.com/repos/influxdb/influxdb/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/influxdb/influxdb/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/influxdb/influxdb/git/refs{/sha}","trees_url":"https://api.github.com/repos/influxdb/influxdb/git/trees{/sha}","statuses_url":"https://api.github.com/repos/influxdb/influxdb/statuses/{sha}","languages_url":"https://api.github.com/repos/influxdb/influxdb/languages","stargazers_url":"https://api.github.com/repos/influxdb/influxdb/stargazers","contributors_url":"https://api.github.com/repos/influxdb/influxdb/contributors","subscribers_url":"https://api.github.com/repos/influxdb/influxdb/subscribers","subscription_url":"https://api.github.com/repos/influxdb/influxdb/subscription","commits_url":"https://api.github.com/repos/influxdb/influxdb/commits{/sha}","git_commits_url":"https://api.github.com/repos/influxdb/influxdb/git/commits{/sha}","comments_url":"https://api.github.com/repos/influxdb/influxdb/comments{/number}","issue_comment_url":"https://api.github.com/repos/influxdb/influxdb/issues/comments{/number}","contents_url":"https://api.github.com/repos/influxdb/influxdb/contents/{+path}","compare_url":"https://api.github.com/repos/influxdb/influxdb/compare/{base}...{head}","merges_url":"https://api.github.com/repos/influxdb/influxdb/merges","archive_url":"https://api.github.com/repos/influxdb/influxdb/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/influxdb/influxdb/downloads","issues_url":"https://api.github.com/repos/influxdb/influxdb/issues{/number}","pulls_url":"https://api.github.com/repos/influxdb/influxdb/pulls{/number}","milestones_url":"https://api.github.com/repos/influxdb/influxdb/milestones{/number}","notifications_url":"https://api.github.com/repos/influxdb/influxdb/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/influxdb/influxdb/labels{/name}","releases_url":"https://api.github.com/repos/influxdb/influxdb/releases{/id}","created_at":"2013-09-26T14:31:10Z","updated_at":"2015-12-17T18:14:25Z","pushed_at":"2015-12-17T20:56:47Z","git_url":"git://github.com/influxdb/influxdb.git","ssh_url":"git@github.com:influxdb/influxdb.git","clone_url":"https://github.com/influxdb/influxdb.git","svn_url":"https://github.com/influxdb/influxdb","homepage":"http://www.influxdata.com","size":39395,"stargazers_count":6981,"watchers_count":6981,"language":"Go","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":861,"mirror_url":null,"open_issues_count":507,"forks":861,"open_issues":507,"watchers":6981,"default_branch":"master"}},"base":{"label":"influxdb:master","ref":"master","sha":"47317d73b4654a3bc62cc4e2ab95237ceb26fa40","user":{"login":"influxdb","id":5713248,"avatar_url":"https://avatars.githubusercontent.com/u/5713248?v=3","gravatar_id":"","url":"https://api.github.com/users/influxdb","html_url":"https://github.com/influxdb","followers_url":"https://api.github.com/users/influxdb/followers","following_url":"https://api.github.com/users/influxdb/following{/other_user}","gists_url":"https://api.github.com/users/influxdb/gists{/gist_id}","starred_url":"https://api.github.com/users/influxdb/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/influxdb/subscriptions","organizations_url":"https://api.github.com/users/influxdb/orgs","repos_url":"https://api.github.com/users/influxdb/repos","events_url":"https://api.github.com/users/influxdb/events{/privacy}","received_events_url":"https://api.github.com/users/influxdb/received_events","type":"Organization","site_admin":false},"repo":{"id":13124802,"name":"influxdb","full_name":"influxdb/influxdb","owner":{"login":"influxdb","id":5713248,"avatar_url":"https://avatars.githubusercontent.com/u/5713248?v=3","gravatar_id":"","url":"https://api.github.com/users/influxdb","html_url":"https://github.com/influxdb","followers_url":"https://api.github.com/users/influxdb/followers","following_url":"https://api.github.com/users/influxdb/following{/other_user}","gists_url":"https://api.github.com/users/influxdb/gists{/gist_id}","starred_url":"https://api.github.com/users/influxdb/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/influxdb/subscriptions","organizations_url":"https://api.github.com/users/influxdb/orgs","repos_url":"https://api.github.com/users/influxdb/repos","events_url":"https://api.github.com/users/influxdb/events{/privacy}","received_events_url":"https://api.github.com/users/influxdb/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/influxdb/influxdb","description":"Scalable datastore for metrics, events, and real-time analytics","fork":false,"url":"https://api.github.com/repos/influxdb/influxdb","forks_url":"https://api.github.com/repos/influxdb/influxdb/forks","keys_url":"https://api.github.com/repos/influxdb/influxdb/keys{/key_id}","collaborators_url":"https://api.github.com/repos/influxdb/influxdb/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/influxdb/influxdb/teams","hooks_url":"https://api.github.com/repos/influxdb/influxdb/hooks","issue_events_url":"https://api.github.com/repos/influxdb/influxdb/issues/events{/number}","events_url":"https://api.github.com/repos/influxdb/influxdb/events","assignees_url":"https://api.github.com/repos/influxdb/influxdb/assignees{/user}","branches_url":"https://api.github.com/repos/influxdb/influxdb/branches{/branch}","tags_url":"https://api.github.com/repos/influxdb/influxdb/tags","blobs_url":"https://api.github.com/repos/influxdb/influxdb/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/influxdb/influxdb/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/influxdb/influxdb/git/refs{/sha}","trees_url":"https://api.github.com/repos/influxdb/influxdb/git/trees{/sha}","statuses_url":"https://api.github.com/repos/influxdb/influxdb/statuses/{sha}","languages_url":"https://api.github.com/repos/influxdb/influxdb/languages","stargazers_url":"https://api.github.com/repos/influxdb/influxdb/stargazers","contributors_url":"https://api.github.com/repos/influxdb/influxdb/contributors","subscribers_url":"https://api.github.com/repos/influxdb/influxdb/subscribers","subscription_url":"https://api.github.com/repos/influxdb/influxdb/subscription","commits_url":"https://api.github.com/repos/influxdb/influxdb/commits{/sha}","git_commits_url":"https://api.github.com/repos/influxdb/influxdb/git/commits{/sha}","comments_url":"https://api.github.com/repos/influxdb/influxdb/comments{/number}","issue_comment_url":"https://api.github.com/repos/influxdb/influxdb/issues/comments{/number}","contents_url":"https://api.github.com/repos/influxdb/influxdb/contents/{+path}","compare_url":"https://api.github.com/repos/influxdb/influxdb/compare/{base}...{head}","merges_url":"https://api.github.com/repos/influxdb/influxdb/merges","archive_url":"https://api.github.com/repos/influxdb/influxdb/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/influxdb/influxdb/downloads","issues_url":"https://api.github.com/repos/influxdb/influxdb/issues{/number}","pulls_url":"https://api.github.com/repos/influxdb/influxdb/pulls{/number}","milestones_url":"https://api.github.com/repos/influxdb/influxdb/milestones{/number}","notifications_url":"https://api.github.com/repos/influxdb/influxdb/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/influxdb/influxdb/labels{/name}","releases_url":"https://api.github.com/repos/influxdb/influxdb/releases{/id}","created_at":"2013-09-26T14:31:10Z","updated_at":"2015-12-17T18:14:25Z","pushed_at":"2015-12-17T20:56:47Z","git_url":"git://github.com/influxdb/influxdb.git","ssh_url":"git@github.com:influxdb/influxdb.git","clone_url":"https://github.com/influxdb/influxdb.git","svn_url":"https://github.com/influxdb/influxdb","homepage":"http://www.influxdata.com","size":39395,"stargazers_count":6981,"watchers_count":6981,"language":"Go","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":861,"mirror_url":null,"open_issues_count":507,"forks":861,"open_issues":507,"watchers":6981,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/influxdb/influxdb/pulls/5142"},"html":{"href":"https://github.com/influxdb/influxdb/pull/5142"},"issue":{"href":"https://api.github.com/repos/influxdb/influxdb/issues/5142"},"comments":{"href":"https://api.github.com/repos/influxdb/influxdb/issues/5142/comments"},"review_comments":{"href":"https://api.github.com/repos/influxdb/influxdb/pulls/5142/comments"},"review_comment":{"href":"https://api.github.com/repos/influxdb/influxdb/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/influxdb/influxdb/pulls/5142/commits"},"statuses":{"href":"https://api.github.com/repos/influxdb/influxdb/statuses/825296ddd8c4e971a92f2d50784c574d674c5666"}}}}