{"action":"created","comment":{"url":"https://api.github.com/repos/facebook/rocksdb/pulls/comments/56098221","id":56098221,"diff_hunk":"@@ -0,0 +1,193 @@\n+//  Copyright (c) 2013, Facebook, Inc.  All rights reserved.\n+//  This source code is licensed under the BSD-style license found in the\n+//  LICENSE file in the root directory of this source tree. An additional grant\n+//  of patent rights can be found in the PATENTS file in the same directory.\n+//\n+// Copyright (c) 2011 The LevelDB Authors. All rights reserved.\n+// Use of this source code is governed by a BSD-style license that can be\n+// found in the LICENSE file. See the AUTHORS file for names of contributors.\n+\n+#include \"util/histogram.h\"\n+#include \"util/histogram_windowing.h\"\n+\n+#include <algorithm>\n+\n+namespace rocksdb {\n+\n+namespace {\n+  const HistogramBucketMapper bucketMapper;\n+}\n+\n+HistogramWindowingImpl::HistogramWindowingImpl() {\n+  env_ = Env::Default();\n+  window_stats_.reset(new HistogramStat[num_windows_]);\n+  Clear();\n+}\n+\n+HistogramWindowingImpl::HistogramWindowingImpl(\n+    uint64_t num_windows,\n+    uint64_t micros_per_window,\n+    uint64_t min_num_per_window) :\n+      num_windows_(num_windows),\n+      micros_per_window_(micros_per_window),\n+      min_num_per_window_(min_num_per_window) {\n+  env_ = Env::Default();\n+  window_stats_.reset(new HistogramStat[num_windows_]);\n+  Clear();\n+}\n+\n+HistogramWindowingImpl::~HistogramWindowingImpl(){\n+  window_stats_.release();\n+}\n+\n+void HistogramWindowingImpl::Clear() {\n+  std::lock_guard<std::mutex> lock(mutex_);\n+\n+  stats_.Clear();\n+  for (size_t i = 0; i < num_windows_; i++) {\n+    window_stats_[i].Clear();\n+  }\n+  current_window_.store(0, std::memory_order_relaxed);\n+  last_swap_time_.store(env_->NowMicros(), std::memory_order_relaxed);\n+}\n+\n+bool HistogramWindowingImpl::Empty() const { return stats_.Empty(); }\n+\n+// This function is designed to be lock free, as it's in the critical path\n+// of any operation.\n+// Each individual value is atomic, it is just that some samples can go\n+// in the older bucket which is tolerable.\n+void HistogramWindowingImpl::Add(uint64_t value){\n+  TimerTick();\n+\n+  // Parent (global) member update\n+  stats_.Add(value);\n+\n+  // Current window update\n+  window_stats_[current_window()].Add(value);\n+}\n+\n+void HistogramWindowingImpl::Merge(const Histogram& other) {\n+  if (strcmp(Name(), other.Name()) == 0) {\n+    Merge(dynamic_cast<const HistogramWindowingImpl&>(other));\n+  }\n+}\n+\n+void HistogramWindowingImpl::Merge(const HistogramWindowingImpl& other) {\n+  std::lock_guard<std::mutex> lock(mutex_);\n+  stats_.Merge(other.stats_);\n+\n+  if (stats_.num_buckets_ != other.stats_.num_buckets_ ||\n+      micros_per_window_ != other.micros_per_window_) {\n+    return;\n+  }\n+\n+  uint64_t cur_window = current_window();\n+  uint64_t other_cur_window = other.current_window();\n+  // going backwards for alignment\n+  for (unsigned int i = 0; \n+                    i < std::min(num_windows_, other.num_windows_); i++) {\n+    uint64_t window_index =\n+        (cur_window + num_windows_ - i) % num_windows_;\n+    uint64_t other_window_index =\n+        (other_cur_window + other.num_windows_ - i) % other.num_windows_;\n+\n+    window_stats_[window_index].Merge(other.window_stats_[other_window_index]);\n+  }\n+}\n+\n+std::string HistogramWindowingImpl::ToString() const {\n+  return stats_.ToString();\n+}\n+\n+double HistogramWindowingImpl::Median() const {\n+  return Percentile(50.0);\n+}\n+\n+double HistogramWindowingImpl::Percentile(double p) const {\n+  // Retry 3 times in total\n+  for (int retry = 0; retry < 3; retry++) {\n+    uint64_t start_num = stats_.num();\n+    double result = stats_.Percentile(p);\n+    // Detect if swap buckets or Clear() was called during calculation\n+    if (stats_.num() >= start_num) {\n+      return result;\n+    }\n+  }\n+  return 0.0;\n+}\n+\n+double HistogramWindowingImpl::Average() const {\n+  return stats_.Average();\n+}\n+\n+double HistogramWindowingImpl::StandardDeviation() const {\n+  return stats_.StandardDeviation();\n+}\n+\n+void HistogramWindowingImpl::Data(HistogramData * const data) const {\n+  stats_.Data(data);\n+}\n+\n+void HistogramWindowingImpl::TimerTick() {\n+  uint64_t curr_time = env_->NowMicros();\n+  if (curr_time - last_swap_time() > micros_per_window_ &&\n+      window_stats_[current_window()].num() >= min_num_per_window_) {\n+    SwapHistoryBucket();\n+  }\n+}\n+\n+void HistogramWindowingImpl::SwapHistoryBucket() {\n+  // Threads executing Add() would be competing for this mutex, the first one\n+  // who got the metex would take care of the bucket swap, other threads\n+  // can skip this.\n+  // If mutex is held by Merge() or Clear(), next Add() will take care of the\n+  // swap, if needed.\n+  if (mutex_.try_lock()) {\n+    last_swap_time_.store(env_->NowMicros(), std::memory_order_relaxed);\n+\n+    uint64_t next_window = (current_window() + 1) % num_windows_;\n+\n+    // subtract next buckets from totals and swap to next buckets\n+    HistogramStat& stats_to_drop = window_stats_[next_window];\n+\n+    if (!stats_to_drop.Empty()) {\n+      for (size_t b = 0; b < stats_.num_buckets_; b++){\n+        stats_.buckets_[b].fetch_sub(\n+            stats_to_drop.bucket_at(b), std::memory_order_relaxed);\n+      }\n+\n+      if (stats_.min() == stats_to_drop.min()) {\n+        uint64_t new_min = bucketMapper.LastValue();\n+        for (unsigned int i = 1; i < num_windows_; i++) {\n+          uint64_t m = window_stats_[(next_window + i) % num_windows_].min();","path":"util/histogram_windowing.cc","position":163,"original_position":163,"commit_id":"fd664a27b5174a0b6197ddbbdad28c5f4db7db22","original_commit_id":"fd664a27b5174a0b6197ddbbdad28c5f4db7db22","user":{"login":"siying","id":5334567,"avatar_url":"https://avatars.githubusercontent.com/u/5334567?v=3","gravatar_id":"","url":"https://api.github.com/users/siying","html_url":"https://github.com/siying","followers_url":"https://api.github.com/users/siying/followers","following_url":"https://api.github.com/users/siying/following{/other_user}","gists_url":"https://api.github.com/users/siying/gists{/gist_id}","starred_url":"https://api.github.com/users/siying/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/siying/subscriptions","organizations_url":"https://api.github.com/users/siying/orgs","repos_url":"https://api.github.com/users/siying/repos","events_url":"https://api.github.com/users/siying/events{/privacy}","received_events_url":"https://api.github.com/users/siying/received_events","type":"User","site_admin":false},"body":"Yes, that is what I mean.\r\n\r\nMy second comment was to say that maybe it was not necessary. We can just do:\r\n\r\n        unsigned int cur_window = next_window + 1;\r\n        for (unsigned int i = 1; i < num_windows_; i++) {\r\n          uint64_t m = window_stats_[cur_window].min();\r\n          if (++cur_window == num_windows_) {\r\n            cur_window = 0;\r\n          }\r\n          if (m < new_min) new_min = m;\r\n        }","created_at":"2016-03-15T00:16:21Z","updated_at":"2016-03-15T00:16:21Z","html_url":"https://github.com/facebook/rocksdb/pull/1026#discussion_r56098221","pull_request_url":"https://api.github.com/repos/facebook/rocksdb/pulls/1026","_links":{"self":{"href":"https://api.github.com/repos/facebook/rocksdb/pulls/comments/56098221"},"html":{"href":"https://github.com/facebook/rocksdb/pull/1026#discussion_r56098221"},"pull_request":{"href":"https://api.github.com/repos/facebook/rocksdb/pulls/1026"}}},"pull_request":{"url":"https://api.github.com/repos/facebook/rocksdb/pulls/1026","id":61648783,"html_url":"https://github.com/facebook/rocksdb/pull/1026","diff_url":"https://github.com/facebook/rocksdb/pull/1026.diff","patch_url":"https://github.com/facebook/rocksdb/pull/1026.patch","issue_url":"https://api.github.com/repos/facebook/rocksdb/issues/1026","number":1026,"state":"open","locked":false,"title":"Histogram Concurrency Improvement and Time-Windowing Support","user":{"login":"SherlockNoMad","id":9906745,"avatar_url":"https://avatars.githubusercontent.com/u/9906745?v=3","gravatar_id":"","url":"https://api.github.com/users/SherlockNoMad","html_url":"https://github.com/SherlockNoMad","followers_url":"https://api.github.com/users/SherlockNoMad/followers","following_url":"https://api.github.com/users/SherlockNoMad/following{/other_user}","gists_url":"https://api.github.com/users/SherlockNoMad/gists{/gist_id}","starred_url":"https://api.github.com/users/SherlockNoMad/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/SherlockNoMad/subscriptions","organizations_url":"https://api.github.com/users/SherlockNoMad/orgs","repos_url":"https://api.github.com/users/SherlockNoMad/repos","events_url":"https://api.github.com/users/SherlockNoMad/events{/privacy}","received_events_url":"https://api.github.com/users/SherlockNoMad/received_events","type":"User","site_admin":false},"body":"Link to Issue https://github.com/facebook/rocksdb/issues/1009 \r\n\r\n@kradhakrishnan @siying @igorcanadi\r\n\r\nChanges in this patch\r\n- Replaced histogram counter type uint64_t with std::atomic_uint_fast64_t to support update atomicity\r\n- Extracted an interface (class Histogram) for HistogramImpl and HistogramWindowingImpl and wrapped the data in struct HistogramStat \r\n- Introduced HistogramWindowingImpl class for supporting real-time histogram caculation\r\n- Extended histogram_test for better coverage\r\n\r\nI had run performance tests to verify no regression is introduced. \r\n\r\nLet me know if there is anything I can do to make it easier for your review. ","created_at":"2016-03-04T00:22:06Z","updated_at":"2016-03-15T00:16:21Z","closed_at":null,"merged_at":null,"merge_commit_sha":"d77581d7ec817e9571a6c50d6e5fc1103c7cdd84","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/facebook/rocksdb/pulls/1026/commits","review_comments_url":"https://api.github.com/repos/facebook/rocksdb/pulls/1026/comments","review_comment_url":"https://api.github.com/repos/facebook/rocksdb/pulls/comments{/number}","comments_url":"https://api.github.com/repos/facebook/rocksdb/issues/1026/comments","statuses_url":"https://api.github.com/repos/facebook/rocksdb/statuses/fd664a27b5174a0b6197ddbbdad28c5f4db7db22","head":{"label":"SherlockNoMad:Hist","ref":"Hist","sha":"fd664a27b5174a0b6197ddbbdad28c5f4db7db22","user":{"login":"SherlockNoMad","id":9906745,"avatar_url":"https://avatars.githubusercontent.com/u/9906745?v=3","gravatar_id":"","url":"https://api.github.com/users/SherlockNoMad","html_url":"https://github.com/SherlockNoMad","followers_url":"https://api.github.com/users/SherlockNoMad/followers","following_url":"https://api.github.com/users/SherlockNoMad/following{/other_user}","gists_url":"https://api.github.com/users/SherlockNoMad/gists{/gist_id}","starred_url":"https://api.github.com/users/SherlockNoMad/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/SherlockNoMad/subscriptions","organizations_url":"https://api.github.com/users/SherlockNoMad/orgs","repos_url":"https://api.github.com/users/SherlockNoMad/repos","events_url":"https://api.github.com/users/SherlockNoMad/events{/privacy}","received_events_url":"https://api.github.com/users/SherlockNoMad/received_events","type":"User","site_admin":false},"repo":{"id":35702628,"name":"rocksdb","full_name":"SherlockNoMad/rocksdb","owner":{"login":"SherlockNoMad","id":9906745,"avatar_url":"https://avatars.githubusercontent.com/u/9906745?v=3","gravatar_id":"","url":"https://api.github.com/users/SherlockNoMad","html_url":"https://github.com/SherlockNoMad","followers_url":"https://api.github.com/users/SherlockNoMad/followers","following_url":"https://api.github.com/users/SherlockNoMad/following{/other_user}","gists_url":"https://api.github.com/users/SherlockNoMad/gists{/gist_id}","starred_url":"https://api.github.com/users/SherlockNoMad/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/SherlockNoMad/subscriptions","organizations_url":"https://api.github.com/users/SherlockNoMad/orgs","repos_url":"https://api.github.com/users/SherlockNoMad/repos","events_url":"https://api.github.com/users/SherlockNoMad/events{/privacy}","received_events_url":"https://api.github.com/users/SherlockNoMad/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/SherlockNoMad/rocksdb","description":"A library that provides an embeddable, persistent key-value store for fast storage.","fork":true,"url":"https://api.github.com/repos/SherlockNoMad/rocksdb","forks_url":"https://api.github.com/repos/SherlockNoMad/rocksdb/forks","keys_url":"https://api.github.com/repos/SherlockNoMad/rocksdb/keys{/key_id}","collaborators_url":"https://api.github.com/repos/SherlockNoMad/rocksdb/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/SherlockNoMad/rocksdb/teams","hooks_url":"https://api.github.com/repos/SherlockNoMad/rocksdb/hooks","issue_events_url":"https://api.github.com/repos/SherlockNoMad/rocksdb/issues/events{/number}","events_url":"https://api.github.com/repos/SherlockNoMad/rocksdb/events","assignees_url":"https://api.github.com/repos/SherlockNoMad/rocksdb/assignees{/user}","branches_url":"https://api.github.com/repos/SherlockNoMad/rocksdb/branches{/branch}","tags_url":"https://api.github.com/repos/SherlockNoMad/rocksdb/tags","blobs_url":"https://api.github.com/repos/SherlockNoMad/rocksdb/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/SherlockNoMad/rocksdb/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/SherlockNoMad/rocksdb/git/refs{/sha}","trees_url":"https://api.github.com/repos/SherlockNoMad/rocksdb/git/trees{/sha}","statuses_url":"https://api.github.com/repos/SherlockNoMad/rocksdb/statuses/{sha}","languages_url":"https://api.github.com/repos/SherlockNoMad/rocksdb/languages","stargazers_url":"https://api.github.com/repos/SherlockNoMad/rocksdb/stargazers","contributors_url":"https://api.github.com/repos/SherlockNoMad/rocksdb/contributors","subscribers_url":"https://api.github.com/repos/SherlockNoMad/rocksdb/subscribers","subscription_url":"https://api.github.com/repos/SherlockNoMad/rocksdb/subscription","commits_url":"https://api.github.com/repos/SherlockNoMad/rocksdb/commits{/sha}","git_commits_url":"https://api.github.com/repos/SherlockNoMad/rocksdb/git/commits{/sha}","comments_url":"https://api.github.com/repos/SherlockNoMad/rocksdb/comments{/number}","issue_comment_url":"https://api.github.com/repos/SherlockNoMad/rocksdb/issues/comments{/number}","contents_url":"https://api.github.com/repos/SherlockNoMad/rocksdb/contents/{+path}","compare_url":"https://api.github.com/repos/SherlockNoMad/rocksdb/compare/{base}...{head}","merges_url":"https://api.github.com/repos/SherlockNoMad/rocksdb/merges","archive_url":"https://api.github.com/repos/SherlockNoMad/rocksdb/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/SherlockNoMad/rocksdb/downloads","issues_url":"https://api.github.com/repos/SherlockNoMad/rocksdb/issues{/number}","pulls_url":"https://api.github.com/repos/SherlockNoMad/rocksdb/pulls{/number}","milestones_url":"https://api.github.com/repos/SherlockNoMad/rocksdb/milestones{/number}","notifications_url":"https://api.github.com/repos/SherlockNoMad/rocksdb/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/SherlockNoMad/rocksdb/labels{/name}","releases_url":"https://api.github.com/repos/SherlockNoMad/rocksdb/releases{/id}","deployments_url":"https://api.github.com/repos/SherlockNoMad/rocksdb/deployments","created_at":"2015-05-16T00:03:31Z","updated_at":"2016-01-30T20:49:55Z","pushed_at":"2016-03-12T06:58:21Z","git_url":"git://github.com/SherlockNoMad/rocksdb.git","ssh_url":"git@github.com:SherlockNoMad/rocksdb.git","clone_url":"https://github.com/SherlockNoMad/rocksdb.git","svn_url":"https://github.com/SherlockNoMad/rocksdb","homepage":"http://rocksdb.org","size":54703,"stargazers_count":0,"watchers_count":0,"language":"C++","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":"facebook:master","ref":"master","sha":"790252805d7fa18d5e7ff04cceb0053ad8590c85","user":{"login":"facebook","id":69631,"avatar_url":"https://avatars.githubusercontent.com/u/69631?v=3","gravatar_id":"","url":"https://api.github.com/users/facebook","html_url":"https://github.com/facebook","followers_url":"https://api.github.com/users/facebook/followers","following_url":"https://api.github.com/users/facebook/following{/other_user}","gists_url":"https://api.github.com/users/facebook/gists{/gist_id}","starred_url":"https://api.github.com/users/facebook/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/facebook/subscriptions","organizations_url":"https://api.github.com/users/facebook/orgs","repos_url":"https://api.github.com/users/facebook/repos","events_url":"https://api.github.com/users/facebook/events{/privacy}","received_events_url":"https://api.github.com/users/facebook/received_events","type":"Organization","site_admin":false},"repo":{"id":6934395,"name":"rocksdb","full_name":"facebook/rocksdb","owner":{"login":"facebook","id":69631,"avatar_url":"https://avatars.githubusercontent.com/u/69631?v=3","gravatar_id":"","url":"https://api.github.com/users/facebook","html_url":"https://github.com/facebook","followers_url":"https://api.github.com/users/facebook/followers","following_url":"https://api.github.com/users/facebook/following{/other_user}","gists_url":"https://api.github.com/users/facebook/gists{/gist_id}","starred_url":"https://api.github.com/users/facebook/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/facebook/subscriptions","organizations_url":"https://api.github.com/users/facebook/orgs","repos_url":"https://api.github.com/users/facebook/repos","events_url":"https://api.github.com/users/facebook/events{/privacy}","received_events_url":"https://api.github.com/users/facebook/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/facebook/rocksdb","description":"A library that provides an embeddable, persistent key-value store for fast storage.","fork":false,"url":"https://api.github.com/repos/facebook/rocksdb","forks_url":"https://api.github.com/repos/facebook/rocksdb/forks","keys_url":"https://api.github.com/repos/facebook/rocksdb/keys{/key_id}","collaborators_url":"https://api.github.com/repos/facebook/rocksdb/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/facebook/rocksdb/teams","hooks_url":"https://api.github.com/repos/facebook/rocksdb/hooks","issue_events_url":"https://api.github.com/repos/facebook/rocksdb/issues/events{/number}","events_url":"https://api.github.com/repos/facebook/rocksdb/events","assignees_url":"https://api.github.com/repos/facebook/rocksdb/assignees{/user}","branches_url":"https://api.github.com/repos/facebook/rocksdb/branches{/branch}","tags_url":"https://api.github.com/repos/facebook/rocksdb/tags","blobs_url":"https://api.github.com/repos/facebook/rocksdb/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/facebook/rocksdb/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/facebook/rocksdb/git/refs{/sha}","trees_url":"https://api.github.com/repos/facebook/rocksdb/git/trees{/sha}","statuses_url":"https://api.github.com/repos/facebook/rocksdb/statuses/{sha}","languages_url":"https://api.github.com/repos/facebook/rocksdb/languages","stargazers_url":"https://api.github.com/repos/facebook/rocksdb/stargazers","contributors_url":"https://api.github.com/repos/facebook/rocksdb/contributors","subscribers_url":"https://api.github.com/repos/facebook/rocksdb/subscribers","subscription_url":"https://api.github.com/repos/facebook/rocksdb/subscription","commits_url":"https://api.github.com/repos/facebook/rocksdb/commits{/sha}","git_commits_url":"https://api.github.com/repos/facebook/rocksdb/git/commits{/sha}","comments_url":"https://api.github.com/repos/facebook/rocksdb/comments{/number}","issue_comment_url":"https://api.github.com/repos/facebook/rocksdb/issues/comments{/number}","contents_url":"https://api.github.com/repos/facebook/rocksdb/contents/{+path}","compare_url":"https://api.github.com/repos/facebook/rocksdb/compare/{base}...{head}","merges_url":"https://api.github.com/repos/facebook/rocksdb/merges","archive_url":"https://api.github.com/repos/facebook/rocksdb/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/facebook/rocksdb/downloads","issues_url":"https://api.github.com/repos/facebook/rocksdb/issues{/number}","pulls_url":"https://api.github.com/repos/facebook/rocksdb/pulls{/number}","milestones_url":"https://api.github.com/repos/facebook/rocksdb/milestones{/number}","notifications_url":"https://api.github.com/repos/facebook/rocksdb/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/facebook/rocksdb/labels{/name}","releases_url":"https://api.github.com/repos/facebook/rocksdb/releases{/id}","deployments_url":"https://api.github.com/repos/facebook/rocksdb/deployments","created_at":"2012-11-30T06:16:18Z","updated_at":"2016-03-14T23:46:11Z","pushed_at":"2016-03-14T23:22:02Z","git_url":"git://github.com/facebook/rocksdb.git","ssh_url":"git@github.com:facebook/rocksdb.git","clone_url":"https://github.com/facebook/rocksdb.git","svn_url":"https://github.com/facebook/rocksdb","homepage":"http://rocksdb.org","size":90379,"stargazers_count":4950,"watchers_count":4950,"language":"C++","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":true,"forks_count":984,"mirror_url":null,"open_issues_count":200,"forks":984,"open_issues":200,"watchers":4950,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/facebook/rocksdb/pulls/1026"},"html":{"href":"https://github.com/facebook/rocksdb/pull/1026"},"issue":{"href":"https://api.github.com/repos/facebook/rocksdb/issues/1026"},"comments":{"href":"https://api.github.com/repos/facebook/rocksdb/issues/1026/comments"},"review_comments":{"href":"https://api.github.com/repos/facebook/rocksdb/pulls/1026/comments"},"review_comment":{"href":"https://api.github.com/repos/facebook/rocksdb/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/facebook/rocksdb/pulls/1026/commits"},"statuses":{"href":"https://api.github.com/repos/facebook/rocksdb/statuses/fd664a27b5174a0b6197ddbbdad28c5f4db7db22"}}}}