{"action":"created","issue":{"url":"https://api.github.com/repos/druid-io/druid/issues/2972","repository_url":"https://api.github.com/repos/druid-io/druid","labels_url":"https://api.github.com/repos/druid-io/druid/issues/2972/labels{/name}","comments_url":"https://api.github.com/repos/druid-io/druid/issues/2972/comments","events_url":"https://api.github.com/repos/druid-io/druid/issues/2972/events","html_url":"https://github.com/druid-io/druid/pull/2972","id":155142595,"number":2972,"title":"new interval based cost function","user":{"login":"xvrl","id":815147,"avatar_url":"https://avatars.githubusercontent.com/u/815147?v=3","gravatar_id":"","url":"https://api.github.com/users/xvrl","html_url":"https://github.com/xvrl","followers_url":"https://api.github.com/users/xvrl/followers","following_url":"https://api.github.com/users/xvrl/following{/other_user}","gists_url":"https://api.github.com/users/xvrl/gists{/gist_id}","starred_url":"https://api.github.com/users/xvrl/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/xvrl/subscriptions","organizations_url":"https://api.github.com/users/xvrl/orgs","repos_url":"https://api.github.com/users/xvrl/repos","events_url":"https://api.github.com/users/xvrl/events{/privacy}","received_events_url":"https://api.github.com/users/xvrl/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/druid-io/druid/labels/Bug","name":"Bug","color":"fc2929"},{"url":"https://api.github.com/repos/druid-io/druid/labels/Discuss","name":"Discuss","color":"ff00ff"}],"state":"open","locked":false,"assignee":null,"milestone":{"url":"https://api.github.com/repos/druid-io/druid/milestones/18","html_url":"https://github.com/druid-io/druid/milestones/0.9.1","labels_url":"https://api.github.com/repos/druid-io/druid/milestones/18/labels","id":1526819,"number":18,"title":"0.9.1","description":"","creator":{"login":"fjy","id":428325,"avatar_url":"https://avatars.githubusercontent.com/u/428325?v=3","gravatar_id":"","url":"https://api.github.com/users/fjy","html_url":"https://github.com/fjy","followers_url":"https://api.github.com/users/fjy/followers","following_url":"https://api.github.com/users/fjy/following{/other_user}","gists_url":"https://api.github.com/users/fjy/gists{/gist_id}","starred_url":"https://api.github.com/users/fjy/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/fjy/subscriptions","organizations_url":"https://api.github.com/users/fjy/orgs","repos_url":"https://api.github.com/users/fjy/repos","events_url":"https://api.github.com/users/fjy/events{/privacy}","received_events_url":"https://api.github.com/users/fjy/received_events","type":"User","site_admin":false},"open_issues":6,"closed_issues":258,"state":"open","created_at":"2016-01-20T19:04:22Z","updated_at":"2016-05-16T23:17:44Z","due_on":null,"closed_at":null},"comments":1,"created_at":"2016-05-16T23:09:36Z","updated_at":"2016-05-16T23:20:07Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/druid-io/druid/pulls/2972","html_url":"https://github.com/druid-io/druid/pull/2972","diff_url":"https://github.com/druid-io/druid/pull/2972.diff","patch_url":"https://github.com/druid-io/druid/pull/2972.patch"},"body":"Our current segment balancing algorithm uses a cost function which had some unintended effects on the distribution of segments in the cluster. While it keeps the total number of segments roughly balanced across nodes, it does not evenly distribute segments within a given intervals. This leads to many queries hitting only a fraction of the historical nodes in the cluster.\r\n\r\nThis is a proposal to revamp the cost function to address those shortcoming and improve overall segment distribution.\r\n\r\nTL;DR here's how segment distribution has improved in the days since we rolled out this improved cost function to one of our Druid clusters (each dot is a segment, each color represents a different data source).\r\n\r\n![c](https://cloud.githubusercontent.com/assets/815147/15304742/e477a38e-1b73-11e6-8386-ae5bc0ea78a9.gif)\r\n\r\n### Issues with our existing cost function\r\n\r\nHere is a breakdown of the issues with the current cost function\r\n\r\n1. Segments tend to form clusters with large gaps in between\r\n\r\n  If you have take segments roughly 30 days apart, the existing `gapPenalty` causes the cost of putting a segment anywhere between those two to be higher than adding a segment that overlaps with them. This causes the balancing to converge to form clusters of segments as seen below.\r\n\r\n  ![c_t_000](https://cloud.githubusercontent.com/assets/815147/15303719/0bf09de0-1b6e-11e6-9c47-f0eae4ca08a5.jpg)\r\n\r\n2. Segments for recent time intervals tend to be distributed unevenly\r\n\r\n The recencyPenalty, in combination with the gapPenalty, makes the cost function non-trivial for recent segments and causes strange gaps of data within the most recent 7 days worth of data.\r\n\r\n  ![h_t_000](https://cloud.githubusercontent.com/assets/815147/15303999/b321cb2e-1b6f-11e6-9651-4e031baefc76.jpg)\r\n\r\n3. The base joint cost between two segments is tied to segment byte sizes. This causes cost to be affected by different levels compression, and not necessarily tied to the actual cost of scanning a segment. \r\n\r\n### Improved cost function\r\n\r\nOur improved cost function is designed to be simple and have the following properties:\r\n\r\n1. Our cost function reflect the cost of scanning a segment.\r\n2. The joint cost should reflect the likelihood of segments being scanned simultaneously, i.e. the joint cost of querying two time-slices should decrease based on how far apart they are.\r\n3. Our cost function should be additive, i.e. given three intervals A, B, and C, cost(A, B union C) = cost(A, B) + cost(A, C)\r\n\r\nTo satisfy 1. we will assume that the cost of scanning a unit time-slice of data is constant. This means our cost function will only depend on segment intervals.\r\n\r\n  > Note: In practice, this means that if all segments in a cluster have the same segment granularity, then the cpu time spent scanning each partition should be roughly constant. Ensuring the unit of computation is constant is also good practice to reduce variance in segment scan times across the cluster.\r\n\r\nTo model the joint cost of querying two time-slices and satisfy 2., we use an exponential decay `exp(-lambda * t)`, where lambda defines the rate at which the interaction decays, and t is the relative time differences between two to time slices. Currently lambda is set to give the decay a half-life of 24 hours.\r\n\r\nSince we assume the cost of querying each time-slice is constant, we can compute the joint cost of two segments by simply integrating over the segment intervals, i.e. for two segments X and Y covering intervals [x_0, x_1) and [y_0, y_1) respectively, our joint cost becomes:\r\n\r\n<img width=\"245\" alt=\"screen shot 2016-05-16 at 3 41 55 pm\" src=\"https://cloud.githubusercontent.com/assets/815147/15306118/c52cdf72-1b7c-11e6-981c-923336ee554b.png\">\r\n\r\nThis has the nice property of being additive as in 3. and of having a closed form solution.\r\n\r\nOne nice side-effect of additivity is that re-indexing the same data at different segment granularities (e.g. going form hourly segments to daily segments) will not affect the joint cost, assuming the cost of scanning a unit of time stays the same per shard.\r\n\r\nHopefully this all makes sense, but comments are of course welcome.\r\n\r\nRegarding performance, the new cost function is more expensive to compute than the existing one, but thanks to the optimizations in #2910 it will not be worse than what we have in our current release, and maybe even a little bit faster still.\r\n\r\nThe results of rolling out this new cost function speak for themselves. You can see how segment distribution has massively improved in our Druid cluster for the problem cases depicted above.  \r\n\r\n![h](https://cloud.githubusercontent.com/assets/815147/15306407/34381466-1b7f-11e6-9728-34937581ba62.gif)\r\n\r\n![c](https://cloud.githubusercontent.com/assets/815147/15304742/e477a38e-1b73-11e6-8386-ae5bc0ea78a9.gif)\r\n"},"comment":{"url":"https://api.github.com/repos/druid-io/druid/issues/comments/219577001","html_url":"https://github.com/druid-io/druid/pull/2972#issuecomment-219577001","issue_url":"https://api.github.com/repos/druid-io/druid/issues/2972","id":219577001,"user":{"login":"fjy","id":428325,"avatar_url":"https://avatars.githubusercontent.com/u/428325?v=3","gravatar_id":"","url":"https://api.github.com/users/fjy","html_url":"https://github.com/fjy","followers_url":"https://api.github.com/users/fjy/followers","following_url":"https://api.github.com/users/fjy/following{/other_user}","gists_url":"https://api.github.com/users/fjy/gists{/gist_id}","starred_url":"https://api.github.com/users/fjy/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/fjy/subscriptions","organizations_url":"https://api.github.com/users/fjy/orgs","repos_url":"https://api.github.com/users/fjy/repos","events_url":"https://api.github.com/users/fjy/events{/privacy}","received_events_url":"https://api.github.com/users/fjy/received_events","type":"User","site_admin":false},"created_at":"2016-05-16T23:20:07Z","updated_at":"2016-05-16T23:20:07Z","body":"👍  if we have more comments about how the algorithm works"}}