{"action":"created","comment":{"url":"https://api.github.com/repos/influxdata/influxdb/pulls/comments/75516976","id":75516976,"diff_hunk":"@@ -0,0 +1,87 @@\n+# TSI Proposal\n+\n+## Overview\n+\n+This is a proposal for a TSI (Time-Series Index) file format to provide fast, memory-mapped access to an inverted index of measurement, series and tag data. It operates at a per-shard level and can be appended to as new series are added.\n+\n+\n+## Block types\n+\n+The file contains multiple block types:\n+\n+- Series Block - This block stores a series block ID and a list of series ids that map to series keys. The list is sorted by series key. The series id is only used internally within the index file and no guarantees are provided about preserving keys after a compaction.\n+\n+- Measurement Block - This block stores the measurement name and a list of tag keys. Each tag key points to a tag value block.\n+\n+- Tag Value Block - This block stores a list of values for a tag key that points to a sorted list of series ids. The series ids are used instead of series keys because the IDs are much smaller than the keys and sorted integer sets can be operated on more quickly.\n+\n+- WAL Block - This block stores a list of series keys that have not been compacted yet.\n+\n+## Usage\n+\n+Initially, series are appended to a WAL block and the series information is held in-memory. Once this reaches a threshold, the WAL block is compacted to a set of series, measurement, & tag value blocks. The WAL is discarded and these new blocks will serve as the index and will be operated upon through an mmap.\n+\n+Series keys can be queried by measurement and tag value by first jumping to the appropriate measurement block. References to measurement blocks will be held in-memory once the files are read in. From the measurement block, a binary search on the tag keys will allow you to find a particular key. Once the key is found, you can jump to the key's tag value block and perform a binary search to find a particular value and a list of associated series IDs.\n+\n+_One future optimization may be to maintain an in-memory histogram to limit the number of pages searched during tag key and tag value traversal._\n+\n+### Tiered storage\n+\n+Once the series, measurement, and tag value blocks are written for a WAL block, a new WAL block can be started at the end of the file. Once this WAL block reaches a threshold size, it can be rewritten as a new set of series, measurement, and tag value blocks.\n+\n+These measurement blocks may duplicate measurement blocks created earlier by other WAL blocks so looking up measurements will involve first searching the new measurement block and then falling back to older measurement blocks and merging the data at query time.\n+\n+### Compaction","path":"doc/tsm/tsi.md","position":32,"original_position":34,"commit_id":"008dc1ef0074e6ad137a7386fa6bc7cb8eb8061c","original_commit_id":"9b7742e2c3e4e1bc863209e0b37725ded0ab1d3a","user":{"login":"benbjohnson","id":118015,"avatar_url":"https://avatars.githubusercontent.com/u/118015?v=3","gravatar_id":"","url":"https://api.github.com/users/benbjohnson","html_url":"https://github.com/benbjohnson","followers_url":"https://api.github.com/users/benbjohnson/followers","following_url":"https://api.github.com/users/benbjohnson/following{/other_user}","gists_url":"https://api.github.com/users/benbjohnson/gists{/gist_id}","starred_url":"https://api.github.com/users/benbjohnson/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/benbjohnson/subscriptions","organizations_url":"https://api.github.com/users/benbjohnson/orgs","repos_url":"https://api.github.com/users/benbjohnson/repos","events_url":"https://api.github.com/users/benbjohnson/events{/privacy}","received_events_url":"https://api.github.com/users/benbjohnson/received_events","type":"User","site_admin":false},"body":"Removed file appending and specified compaction types in 008dc1e.","created_at":"2016-08-19T17:05:21Z","updated_at":"2016-08-19T17:05:21Z","html_url":"https://github.com/influxdata/influxdb/pull/7174#discussion_r75516976","pull_request_url":"https://api.github.com/repos/influxdata/influxdb/pulls/7174","_links":{"self":{"href":"https://api.github.com/repos/influxdata/influxdb/pulls/comments/75516976"},"html":{"href":"https://github.com/influxdata/influxdb/pull/7174#discussion_r75516976"},"pull_request":{"href":"https://api.github.com/repos/influxdata/influxdb/pulls/7174"}}},"pull_request":{"url":"https://api.github.com/repos/influxdata/influxdb/pulls/7174","id":81727922,"html_url":"https://github.com/influxdata/influxdb/pull/7174","diff_url":"https://github.com/influxdata/influxdb/pull/7174.diff","patch_url":"https://github.com/influxdata/influxdb/pull/7174.patch","issue_url":"https://api.github.com/repos/influxdata/influxdb/issues/7174","number":7174,"state":"open","locked":false,"title":"TSI Proposal","user":{"login":"benbjohnson","id":118015,"avatar_url":"https://avatars.githubusercontent.com/u/118015?v=3","gravatar_id":"","url":"https://api.github.com/users/benbjohnson","html_url":"https://github.com/benbjohnson","followers_url":"https://api.github.com/users/benbjohnson/followers","following_url":"https://api.github.com/users/benbjohnson/following{/other_user}","gists_url":"https://api.github.com/users/benbjohnson/gists{/gist_id}","starred_url":"https://api.github.com/users/benbjohnson/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/benbjohnson/subscriptions","organizations_url":"https://api.github.com/users/benbjohnson/orgs","repos_url":"https://api.github.com/users/benbjohnson/repos","events_url":"https://api.github.com/users/benbjohnson/events{/privacy}","received_events_url":"https://api.github.com/users/benbjohnson/received_events","type":"User","site_admin":false},"body":"Proposal for implementing #7151.\r\n\r\n/cc @jwilder @pauldix @e-dard \r\n","created_at":"2016-08-17T22:24:36Z","updated_at":"2016-08-19T17:05:21Z","closed_at":null,"merged_at":null,"merge_commit_sha":"3401e142311eb734238b35bc810cd9e8d1943439","assignee":null,"assignees":[],"milestone":{"url":"https://api.github.com/repos/influxdata/influxdb/milestones/56","html_url":"https://github.com/influxdata/influxdb/milestones/1.1.0","labels_url":"https://api.github.com/repos/influxdata/influxdb/milestones/56/labels","id":1807337,"number":56,"title":"1.1.0","description":"Point release to come 2 months after 1.0","creator":{"login":"pauldix","id":4331,"avatar_url":"https://avatars.githubusercontent.com/u/4331?v=3","gravatar_id":"","url":"https://api.github.com/users/pauldix","html_url":"https://github.com/pauldix","followers_url":"https://api.github.com/users/pauldix/followers","following_url":"https://api.github.com/users/pauldix/following{/other_user}","gists_url":"https://api.github.com/users/pauldix/gists{/gist_id}","starred_url":"https://api.github.com/users/pauldix/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/pauldix/subscriptions","organizations_url":"https://api.github.com/users/pauldix/orgs","repos_url":"https://api.github.com/users/pauldix/repos","events_url":"https://api.github.com/users/pauldix/events{/privacy}","received_events_url":"https://api.github.com/users/pauldix/received_events","type":"User","site_admin":false},"open_issues":21,"closed_issues":11,"state":"open","created_at":"2016-06-03T14:53:39Z","updated_at":"2016-08-19T16:10:51Z","due_on":null,"closed_at":null},"commits_url":"https://api.github.com/repos/influxdata/influxdb/pulls/7174/commits","review_comments_url":"https://api.github.com/repos/influxdata/influxdb/pulls/7174/comments","review_comment_url":"https://api.github.com/repos/influxdata/influxdb/pulls/comments{/number}","comments_url":"https://api.github.com/repos/influxdata/influxdb/issues/7174/comments","statuses_url":"https://api.github.com/repos/influxdata/influxdb/statuses/008dc1ef0074e6ad137a7386fa6bc7cb8eb8061c","head":{"label":"benbjohnson:tsi","ref":"tsi","sha":"008dc1ef0074e6ad137a7386fa6bc7cb8eb8061c","user":{"login":"benbjohnson","id":118015,"avatar_url":"https://avatars.githubusercontent.com/u/118015?v=3","gravatar_id":"","url":"https://api.github.com/users/benbjohnson","html_url":"https://github.com/benbjohnson","followers_url":"https://api.github.com/users/benbjohnson/followers","following_url":"https://api.github.com/users/benbjohnson/following{/other_user}","gists_url":"https://api.github.com/users/benbjohnson/gists{/gist_id}","starred_url":"https://api.github.com/users/benbjohnson/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/benbjohnson/subscriptions","organizations_url":"https://api.github.com/users/benbjohnson/orgs","repos_url":"https://api.github.com/users/benbjohnson/repos","events_url":"https://api.github.com/users/benbjohnson/events{/privacy}","received_events_url":"https://api.github.com/users/benbjohnson/received_events","type":"User","site_admin":false},"repo":{"id":36954584,"name":"influxdb","full_name":"benbjohnson/influxdb","owner":{"login":"benbjohnson","id":118015,"avatar_url":"https://avatars.githubusercontent.com/u/118015?v=3","gravatar_id":"","url":"https://api.github.com/users/benbjohnson","html_url":"https://github.com/benbjohnson","followers_url":"https://api.github.com/users/benbjohnson/followers","following_url":"https://api.github.com/users/benbjohnson/following{/other_user}","gists_url":"https://api.github.com/users/benbjohnson/gists{/gist_id}","starred_url":"https://api.github.com/users/benbjohnson/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/benbjohnson/subscriptions","organizations_url":"https://api.github.com/users/benbjohnson/orgs","repos_url":"https://api.github.com/users/benbjohnson/repos","events_url":"https://api.github.com/users/benbjohnson/events{/privacy}","received_events_url":"https://api.github.com/users/benbjohnson/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/benbjohnson/influxdb","description":"Scalable datastore for metrics, events, and real-time analytics","fork":true,"url":"https://api.github.com/repos/benbjohnson/influxdb","forks_url":"https://api.github.com/repos/benbjohnson/influxdb/forks","keys_url":"https://api.github.com/repos/benbjohnson/influxdb/keys{/key_id}","collaborators_url":"https://api.github.com/repos/benbjohnson/influxdb/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/benbjohnson/influxdb/teams","hooks_url":"https://api.github.com/repos/benbjohnson/influxdb/hooks","issue_events_url":"https://api.github.com/repos/benbjohnson/influxdb/issues/events{/number}","events_url":"https://api.github.com/repos/benbjohnson/influxdb/events","assignees_url":"https://api.github.com/repos/benbjohnson/influxdb/assignees{/user}","branches_url":"https://api.github.com/repos/benbjohnson/influxdb/branches{/branch}","tags_url":"https://api.github.com/repos/benbjohnson/influxdb/tags","blobs_url":"https://api.github.com/repos/benbjohnson/influxdb/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/benbjohnson/influxdb/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/benbjohnson/influxdb/git/refs{/sha}","trees_url":"https://api.github.com/repos/benbjohnson/influxdb/git/trees{/sha}","statuses_url":"https://api.github.com/repos/benbjohnson/influxdb/statuses/{sha}","languages_url":"https://api.github.com/repos/benbjohnson/influxdb/languages","stargazers_url":"https://api.github.com/repos/benbjohnson/influxdb/stargazers","contributors_url":"https://api.github.com/repos/benbjohnson/influxdb/contributors","subscribers_url":"https://api.github.com/repos/benbjohnson/influxdb/subscribers","subscription_url":"https://api.github.com/repos/benbjohnson/influxdb/subscription","commits_url":"https://api.github.com/repos/benbjohnson/influxdb/commits{/sha}","git_commits_url":"https://api.github.com/repos/benbjohnson/influxdb/git/commits{/sha}","comments_url":"https://api.github.com/repos/benbjohnson/influxdb/comments{/number}","issue_comment_url":"https://api.github.com/repos/benbjohnson/influxdb/issues/comments{/number}","contents_url":"https://api.github.com/repos/benbjohnson/influxdb/contents/{+path}","compare_url":"https://api.github.com/repos/benbjohnson/influxdb/compare/{base}...{head}","merges_url":"https://api.github.com/repos/benbjohnson/influxdb/merges","archive_url":"https://api.github.com/repos/benbjohnson/influxdb/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/benbjohnson/influxdb/downloads","issues_url":"https://api.github.com/repos/benbjohnson/influxdb/issues{/number}","pulls_url":"https://api.github.com/repos/benbjohnson/influxdb/pulls{/number}","milestones_url":"https://api.github.com/repos/benbjohnson/influxdb/milestones{/number}","notifications_url":"https://api.github.com/repos/benbjohnson/influxdb/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/benbjohnson/influxdb/labels{/name}","releases_url":"https://api.github.com/repos/benbjohnson/influxdb/releases{/id}","deployments_url":"https://api.github.com/repos/benbjohnson/influxdb/deployments","created_at":"2015-06-05T20:45:47Z","updated_at":"2016-03-22T13:18:01Z","pushed_at":"2016-08-19T16:59:56Z","git_url":"git://github.com/benbjohnson/influxdb.git","ssh_url":"git@github.com:benbjohnson/influxdb.git","clone_url":"https://github.com/benbjohnson/influxdb.git","svn_url":"https://github.com/benbjohnson/influxdb","homepage":"http://influxdb.com","size":43805,"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":"master"}},"base":{"label":"influxdata:master","ref":"master","sha":"65536676a46c720deed6b4afe8d6b9ef13431e65","user":{"login":"influxdata","id":5713248,"avatar_url":"https://avatars.githubusercontent.com/u/5713248?v=3","gravatar_id":"","url":"https://api.github.com/users/influxdata","html_url":"https://github.com/influxdata","followers_url":"https://api.github.com/users/influxdata/followers","following_url":"https://api.github.com/users/influxdata/following{/other_user}","gists_url":"https://api.github.com/users/influxdata/gists{/gist_id}","starred_url":"https://api.github.com/users/influxdata/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/influxdata/subscriptions","organizations_url":"https://api.github.com/users/influxdata/orgs","repos_url":"https://api.github.com/users/influxdata/repos","events_url":"https://api.github.com/users/influxdata/events{/privacy}","received_events_url":"https://api.github.com/users/influxdata/received_events","type":"Organization","site_admin":false},"repo":{"id":13124802,"name":"influxdb","full_name":"influxdata/influxdb","owner":{"login":"influxdata","id":5713248,"avatar_url":"https://avatars.githubusercontent.com/u/5713248?v=3","gravatar_id":"","url":"https://api.github.com/users/influxdata","html_url":"https://github.com/influxdata","followers_url":"https://api.github.com/users/influxdata/followers","following_url":"https://api.github.com/users/influxdata/following{/other_user}","gists_url":"https://api.github.com/users/influxdata/gists{/gist_id}","starred_url":"https://api.github.com/users/influxdata/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/influxdata/subscriptions","organizations_url":"https://api.github.com/users/influxdata/orgs","repos_url":"https://api.github.com/users/influxdata/repos","events_url":"https://api.github.com/users/influxdata/events{/privacy}","received_events_url":"https://api.github.com/users/influxdata/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/influxdata/influxdb","description":"Scalable datastore for metrics, events, and real-time analytics","fork":false,"url":"https://api.github.com/repos/influxdata/influxdb","forks_url":"https://api.github.com/repos/influxdata/influxdb/forks","keys_url":"https://api.github.com/repos/influxdata/influxdb/keys{/key_id}","collaborators_url":"https://api.github.com/repos/influxdata/influxdb/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/influxdata/influxdb/teams","hooks_url":"https://api.github.com/repos/influxdata/influxdb/hooks","issue_events_url":"https://api.github.com/repos/influxdata/influxdb/issues/events{/number}","events_url":"https://api.github.com/repos/influxdata/influxdb/events","assignees_url":"https://api.github.com/repos/influxdata/influxdb/assignees{/user}","branches_url":"https://api.github.com/repos/influxdata/influxdb/branches{/branch}","tags_url":"https://api.github.com/repos/influxdata/influxdb/tags","blobs_url":"https://api.github.com/repos/influxdata/influxdb/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/influxdata/influxdb/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/influxdata/influxdb/git/refs{/sha}","trees_url":"https://api.github.com/repos/influxdata/influxdb/git/trees{/sha}","statuses_url":"https://api.github.com/repos/influxdata/influxdb/statuses/{sha}","languages_url":"https://api.github.com/repos/influxdata/influxdb/languages","stargazers_url":"https://api.github.com/repos/influxdata/influxdb/stargazers","contributors_url":"https://api.github.com/repos/influxdata/influxdb/contributors","subscribers_url":"https://api.github.com/repos/influxdata/influxdb/subscribers","subscription_url":"https://api.github.com/repos/influxdata/influxdb/subscription","commits_url":"https://api.github.com/repos/influxdata/influxdb/commits{/sha}","git_commits_url":"https://api.github.com/repos/influxdata/influxdb/git/commits{/sha}","comments_url":"https://api.github.com/repos/influxdata/influxdb/comments{/number}","issue_comment_url":"https://api.github.com/repos/influxdata/influxdb/issues/comments{/number}","contents_url":"https://api.github.com/repos/influxdata/influxdb/contents/{+path}","compare_url":"https://api.github.com/repos/influxdata/influxdb/compare/{base}...{head}","merges_url":"https://api.github.com/repos/influxdata/influxdb/merges","archive_url":"https://api.github.com/repos/influxdata/influxdb/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/influxdata/influxdb/downloads","issues_url":"https://api.github.com/repos/influxdata/influxdb/issues{/number}","pulls_url":"https://api.github.com/repos/influxdata/influxdb/pulls{/number}","milestones_url":"https://api.github.com/repos/influxdata/influxdb/milestones{/number}","notifications_url":"https://api.github.com/repos/influxdata/influxdb/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/influxdata/influxdb/labels{/name}","releases_url":"https://api.github.com/repos/influxdata/influxdb/releases{/id}","deployments_url":"https://api.github.com/repos/influxdata/influxdb/deployments","created_at":"2013-09-26T14:31:10Z","updated_at":"2016-08-19T14:28:27Z","pushed_at":"2016-08-19T16:59:58Z","git_url":"git://github.com/influxdata/influxdb.git","ssh_url":"git@github.com:influxdata/influxdb.git","clone_url":"https://github.com/influxdata/influxdb.git","svn_url":"https://github.com/influxdata/influxdb","homepage":"https://influxdata.com","size":60329,"stargazers_count":8645,"watchers_count":8645,"language":"Go","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":1222,"mirror_url":null,"open_issues_count":419,"forks":1222,"open_issues":419,"watchers":8645,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/influxdata/influxdb/pulls/7174"},"html":{"href":"https://github.com/influxdata/influxdb/pull/7174"},"issue":{"href":"https://api.github.com/repos/influxdata/influxdb/issues/7174"},"comments":{"href":"https://api.github.com/repos/influxdata/influxdb/issues/7174/comments"},"review_comments":{"href":"https://api.github.com/repos/influxdata/influxdb/pulls/7174/comments"},"review_comment":{"href":"https://api.github.com/repos/influxdata/influxdb/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/influxdata/influxdb/pulls/7174/commits"},"statuses":{"href":"https://api.github.com/repos/influxdata/influxdb/statuses/008dc1ef0074e6ad137a7386fa6bc7cb8eb8061c"}}}}
{"actor":{"display_login":"benbjohnson"}}