rocksdb

//  Copyright (c) 2011-present, Facebook, Inc.  All rights reserved.
//  This source code is licensed under both the GPLv2 (found in the
//  COPYING file in the root directory) and Apache 2.0 License
//  (found in the LICENSE.Apache file in the root directory).
//

#pragma once
#include <algorithm>

#include "db/version_edit.h"

namespace ROCKSDB_NAMESPACE {
// We boost files that are closer to TTL limit. This boosting could be
// through FileMetaData.compensated_file_size but this compensated size
// is widely used as something similar to file size so dramatically boost
// the value might cause unintended consequences.
//
// This boosting algorithm can go very fancy, but here we use a simple
// formula which can satisify:
// (1) Different levels are triggered slightly differently to avoid
//     too many cascading cases
// (2) Files in the same level get boosting more when TTL gets closer.
//
// Don't do any boosting before TTL has past by half. This is to make
// sure lower write amp for most of the case. And all levels should be
// fully boosted when total TTL compaction threshold triggers.
// Differientiate boosting ranges of each level by 1/2. This will make
// range for each level exponentially increasing. We could do it by
// having them to be equal, or go even fancier. We can adjust it after
// we observe the behavior in production.
// The threshold starting boosting:
// +------------------------------------------------------------------ +
// ^                            ^   ^     ^       ^                 ^
// Age 0                        ... |     |    second last level    thresold
//                                  |     |
//                                  |  third last level
//                                  |
//                            forth last level
//
// We arbitrarily set with 0 when a file is aged boost_age_start and
// grow linearly. The ratio is arbitrarily set so that when the next level
// starts to boost, the previous level's boosting amount is 16.
class FileTtlBooster {
 public:
  FileTtlBooster(uint64_t current_time, uint64_t ttl, int num_non_empty_levels,
                 int level)
      : current_time_(current_time) {
    if (ttl == 0 || level == 0 || level >= num_non_empty_levels - 1) {
      enabled_ = false;
      boost_age_start_ = 0;
      boost_step_ = 1;
    } else {
      enabled_ = true;
      uint64_t all_boost_start_age = ttl / 2;
      uint64_t all_boost_age_range = (ttl / 32) * 31 - all_boost_start_age;
      // TODO(cbi): more reasonable algorithm that gives different values
      //   when num_non_empty_levels - level - 1 > 63.
      uint64_t boost_age_range =
          all_boost_age_range >> std::min(63, num_non_empty_levels - level - 1);
      boost_age_start_ = all_boost_start_age + boost_age_range;
      const uint64_t kBoostRatio = 16;
      // prevent 0 value to avoid divide 0 error.
      boost_step_ = std::max(boost_age_range / kBoostRatio, uint64_t{1});
    }
  }

  uint64_t GetBoostScore(FileMetaData* f) {
    if (!enabled_) {
      return 1;
    }
    uint64_t oldest_ancester_time = f->TryGetOldestAncesterTime();
    if (oldest_ancester_time >= current_time_) {
      return 1;
    }
    uint64_t age = current_time_ - oldest_ancester_time;
    if (age > boost_age_start_) {
      // Use integer just for convenience.
      // We could make all file_to_order double if we want.
      // Technically this can overflow if users override timing and
      // give a very high current time. Ignore the case for simplicity.
      // Boosting is addition to current value, so +1. This will effectively
      // make boosting to kick in after the first boost_step_ is reached.
      return (age - boost_age_start_) / boost_step_ + 1;
    }
    return 1;
  }

 private:
  bool enabled_;
  uint64_t current_time_;
  uint64_t boost_age_start_;
  uint64_t boost_step_;
};
}  // namespace ROCKSDB_NAMESPACE