// Licensed to the Apache Software Foundation (ASF) under one

// or more contributor license agreements.  See the NOTICE file

// distributed with this work for additional information

// regarding copyright ownership.  The ASF licenses this file

// to you under the Apache License, Version 2.0 (the

// "License"); you may not use this file except in compliance

// with the License.  You may obtain a copy of the License at

//

//   http://www.apache.org/licenses/LICENSE-2.0

//

// Unless required by applicable law or agreed to in writing,

// software distributed under the License is distributed on an

// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY

// KIND, either express or implied.  See the License for the

// specific language governing permissions and limitations

// under the License.

#include "cloud/cloud_tablet_hotspot.h"

#include <algorithm>

#include <chrono>

#include <cmath>

#include <cstdint>

#include <mutex>

#include <vector>

#include "runtime/memory/global_memory_arbitrator.h"

#include "storage/tablet/base_tablet.h"

namespace doris {

namespace {

using HotPartitionSnapshot =

        std::unordered_map<TabletHotspotMapKey, std::unordered_map<int64_t, TabletHotspotMapValue>,

                           MapKeyHash>;

constexpr uint64_t kCountHeartbeatInterval = 500000;

constexpr uint64_t kNewCounterLogInterval = 4096;

constexpr size_t kCompactBucketMultiplier = 4;

constexpr size_t kCompactEraseRatioDivisor = 4;

using SystemTimePoint = std::chrono::system_clock::time_point;

using SteadyClock = std::chrono::steady_clock;

double bytes_to_mb(int64_t bytes) {

    return static_cast<double>(bytes) / (1024.0 * 1024.0);

}

double ratio_or_zero(uint64_t numerator, uint64_t denominator) {

    if (denominator == 0) {

        return 0.0;

    }

    return static_cast<double>(numerator) / static_cast<double>(denominator);

}

int64_t process_memory_usage_for_diag() {

#ifdef BE_TEST

    return 0;

#else

    return GlobalMemoryArbitrator::process_memory_usage();

#endif

}

uint64_t count_hot_partition_entries(const HotPartitionSnapshot& snapshot) {

    uint64_t entries = 0;

    for (const auto& [_, partition_to_value] : snapshot) {

        entries += partition_to_value.size();

    }

    return entries;

}

bool should_compact_slot(size_t slot_size_before, size_t slot_size_after, size_t bucket_count_after,

                         size_t erased_count) {

    if (erased_count == 0) {

        return false;

    }

    if (slot_size_after == 0) {

        return true;

    }

    return bucket_count_after > (kCompactBucketMultiplier * slot_size_after) ||

           (slot_size_before > 0 && erased_count * kCompactEraseRatioDivisor >= slot_size_before);

}

} // namespace

void TabletHotspot::count(const BaseTablet& tablet) {

    count(tablet.tablet_id(), tablet.table_id(), tablet.index_id(), tablet.partition_id());

}

void TabletHotspot::count(int64_t tablet_id, int64_t table_id, int64_t index_id,

                          int64_t partition_id) {

    const uint64_t count_calls_total =

            _count_calls_total.fetch_add(1, std::memory_order_relaxed) + 1;

    size_t slot_idx = tablet_id % s_slot_size;

    auto& slot = _tablets_hotspot[slot_idx];

    bool should_log_new_counter = false;

    uint64_t new_counter_total = 0;

    {

        std::lock_guard lock(slot.mtx);

        HotspotCounterPtr counter;

        if (auto iter = slot.map.find(tablet_id); iter == slot.map.end()) {

            counter = std::make_shared<HotspotCounter>(table_id, index_id, partition_id);

            slot.map.insert(std::make_pair(tablet_id, counter));

            new_counter_total = _new_counter_total.fetch_add(1, std::memory_order_relaxed) + 1;

            should_log_new_counter = (new_counter_total % kNewCounterLogInterval == 0);

        } else {

            counter = iter->second;

            _existing_hit_total.fetch_add(1, std::memory_order_relaxed);

        }

        counter->last_access_time = std::chrono::system_clock::now();

        counter->cur_counter.fetch_add(1, std::memory_order_relaxed);

    }

    if (should_log_new_counter) {

        LOG(INFO) << "tablet_hotspot_diag new_counter_total=" << new_counter_total

                  << " count_calls_total=" << count_calls_total

                  << " existing_hit_total=" << _existing_hit_total.load(std::memory_order_relaxed);

    }

    if (count_calls_total % kCountHeartbeatInterval == 0) {

        LOG(INFO) << "tablet_hotspot_diag count_heartbeat count_calls_total=" << count_calls_total

                  << " existing_hit_total=" << _existing_hit_total.load(std::memory_order_relaxed)

                  << " new_counter_total=" << _new_counter_total.load(std::memory_order_relaxed);

    }

}

TabletHotspot::TabletHotspot(bool start_counter_thread) {

    if (start_counter_thread) {

        _counter_thread = std::thread(&TabletHotspot::make_dot_point, this);

    }

}

TabletHotspot::~TabletHotspot() {

    {

        std::lock_guard lock(_mtx);

        _closed = true;

    }

    _cond.notify_all();

    if (_counter_thread.joinable()) {

        _counter_thread.join();

    }

}

void get_return_partitions(

        const std::unordered_map<TabletHotspotMapKey,

                                 std::unordered_map<int64_t, TabletHotspotMapValue>, MapKeyHash>&

                hot_partition,

        const std::unordered_map<TabletHotspotMapKey,

                                 std::unordered_map<int64_t, TabletHotspotMapValue>, MapKeyHash>&

                last_hot_partition,

        std::vector<THotTableMessage>* hot_tables, int& return_partitions, int N) {

    for (const auto& [key, partition_to_value] : hot_partition) {

        THotTableMessage msg;

        msg.table_id = key.first;

        msg.index_id = key.second;

        for (const auto& [partition_id, value] : partition_to_value) {

            if (return_partitions > N) {

                return;

            }

            auto last_value_iter = last_hot_partition.find(key);

            if (last_value_iter != last_hot_partition.end()) {

                auto last_partition_iter = last_value_iter->second.find(partition_id);

                if (last_partition_iter != last_value_iter->second.end()) {

                    const auto& last_value = last_partition_iter->second;

                    if (std::abs(static_cast<int64_t>(value.qpd) -

                                 static_cast<int64_t>(last_value.qpd)) < 5 &&

                        std::abs(static_cast<int64_t>(value.qpw) -

                                 static_cast<int64_t>(last_value.qpw)) < 10 &&

                        std::abs(static_cast<int64_t>(value.last_access_time) -

                                 static_cast<int64_t>(last_value.last_access_time)) < 60) {

                        LOG(INFO) << "skip partition_id=" << partition_id << " qpd=" << value.qpd

                                  << " qpw=" << value.qpw

                                  << " last_access_time=" << value.last_access_time

                                  << " last_qpd=" << last_value.qpd

                                  << " last_qpw=" << last_value.qpw

                                  << " last_access_time=" << last_value.last_access_time;

                        continue;

                    }

                }

            }

            THotPartition new_hot_partition;

            new_hot_partition.__set_partition_id(partition_id);

            new_hot_partition.__set_query_per_day(value.qpd);

            new_hot_partition.__set_query_per_week(value.qpw);

            new_hot_partition.__set_last_access_time(value.last_access_time);

            msg.hot_partitions.push_back(new_hot_partition);

            return_partitions++;

        }

        msg.__isset.hot_partitions = !msg.hot_partitions.empty();

        hot_tables->push_back(std::move(msg));

    }

}

void TabletHotspot::get_top_n_hot_partition(std::vector<THotTableMessage>* hot_tables) {

    const uint64_t call_id =

            _get_top_n_hot_partition_call_total.fetch_add(1, std::memory_order_relaxed) + 1;

    uint64_t last_day_tables_before = 0;

    uint64_t last_day_entries_before = 0;

    uint64_t last_week_tables_before = 0;

    uint64_t last_week_entries_before = 0;

    {

        std::lock_guard lock(_last_partitions_mtx);

        last_day_tables_before = _last_day_hot_partitions.size();

        last_day_entries_before = count_hot_partition_entries(_last_day_hot_partitions);

        last_week_tables_before = _last_week_hot_partitions.size();

        last_week_entries_before = count_hot_partition_entries(_last_week_hot_partitions);

    }

    const int64_t process_mem_before = process_memory_usage_for_diag();

    // map<pair<table_id, index_id>, map<partition_id, value>> for day

    std::unordered_map<TabletHotspotMapKey, std::unordered_map<int64_t, TabletHotspotMapValue>,

                       MapKeyHash>

            day_hot_partitions;

    // map<pair<table_id, index_id>, map<partition_id, value>> for week

    std::unordered_map<TabletHotspotMapKey, std::unordered_map<int64_t, TabletHotspotMapValue>,

                       MapKeyHash>

            week_hot_partitions;

    std::for_each(_tablets_hotspot.begin(), _tablets_hotspot.end(), [&](HotspotMap& map) {

        std::lock_guard lock(map.mtx);

        for (auto& [_, counter] : map.map) {

            if (counter->qpd() != 0) {

                auto& hot_partition = day_hot_partitions[std::make_pair(

                        counter->table_id, counter->index_id)][counter->partition_id];

                hot_partition.qpd = std::max(hot_partition.qpd, counter->qpd());

                hot_partition.qpw = std::max(hot_partition.qpw, counter->qpw());

                hot_partition.last_access_time =

                        std::max<int64_t>(hot_partition.last_access_time,

                                          std::chrono::duration_cast<std::chrono::seconds>(

                                                  counter->last_access_time.time_since_epoch())

                                                  .count());

            } else if (counter->qpw() != 0) {

                auto& hot_partition = week_hot_partitions[std::make_pair(

                        counter->table_id, counter->index_id)][counter->partition_id];

                hot_partition.qpd = 0;

                hot_partition.qpw = std::max(hot_partition.qpw, counter->qpw());

                hot_partition.last_access_time =

                        std::max<int64_t>(hot_partition.last_access_time,

                                          std::chrono::duration_cast<std::chrono::seconds>(

                                                  counter->last_access_time.time_since_epoch())

                                                  .count());

            }

        }

    });

    constexpr int N = 50;

    int return_partitions = 0;

    const uint64_t day_tables_built = day_hot_partitions.size();

    const uint64_t day_entries_built = count_hot_partition_entries(day_hot_partitions);

    const uint64_t week_tables_built = week_hot_partitions.size();

    const uint64_t week_entries_built = count_hot_partition_entries(week_hot_partitions);

    uint64_t last_day_tables_after = 0;

    uint64_t last_day_entries_after = 0;

    uint64_t last_week_tables_after = 0;

    uint64_t last_week_entries_after = 0;

    {

        std::unique_lock lock(_last_partitions_mtx);

        get_return_partitions(day_hot_partitions, _last_day_hot_partitions, hot_tables,

                              return_partitions, N);

        get_return_partitions(week_hot_partitions, _last_week_hot_partitions, hot_tables,

                              return_partitions, N);

        _last_day_hot_partitions = std::move(day_hot_partitions);

        _last_week_hot_partitions = std::move(week_hot_partitions);

        last_day_tables_after = _last_day_hot_partitions.size();

        last_day_entries_after = count_hot_partition_entries(_last_day_hot_partitions);

        last_week_tables_after = _last_week_hot_partitions.size();

        last_week_entries_after = count_hot_partition_entries(_last_week_hot_partitions);

    }

    const int64_t process_mem_after = process_memory_usage_for_diag();

    LOG(INFO) << "tablet_hotspot_diag get_top_n_hot_partition call_id=" << call_id

              << " day_tables_built=" << day_tables_built

              << " day_entries_built=" << day_entries_built

              << " week_tables_built=" << week_tables_built

              << " week_entries_built=" << week_entries_built

              << " returned_partitions=" << return_partitions

              << " last_day_tables_before=" << last_day_tables_before

              << " last_day_entries_before=" << last_day_entries_before

              << " last_day_tables_after=" << last_day_tables_after

              << " last_day_entries_after=" << last_day_entries_after

              << " last_week_tables_before=" << last_week_tables_before

              << " last_week_entries_before=" << last_week_entries_before

              << " last_week_tables_after=" << last_week_tables_after

              << " last_week_entries_after=" << last_week_entries_after

              << " process_mem_before_mb=" << bytes_to_mb(process_mem_before)

              << " process_mem_after_mb=" << bytes_to_mb(process_mem_after);

}

void HotspotCounter::make_dot_point() {

    uint64_t value = cur_counter.exchange(0, std::memory_order_acq_rel);

    if (history_counters.size() == week_counters_size) {

        uint64_t week_counter_remove = history_counters.back();

        uint64_t day_counter_remove = history_counters[day_counters_size - 1];

        week_history_counter = week_history_counter - week_counter_remove + value;

        day_history_counter = day_history_counter - day_counter_remove + value;

        history_counters.pop_back();

    } else if (history_counters.size() < day_counters_size) {

        week_history_counter += value;

        day_history_counter += value;

    } else {

        week_history_counter += value;

        uint64_t day_counter_remove = history_counters[day_counters_size - 1];

        day_history_counter = day_history_counter - day_counter_remove + value;

    }

    history_counters.push_front(value);

}

uint64_t HotspotCounter::qpd() {

    return day_history_counter + cur_counter.load();

}

uint64_t HotspotCounter::qpw() {

    return week_history_counter + cur_counter.load();

}

bool TabletHotspot::is_gc_eligible(const HotspotCounter& counter, SystemTimePoint now) {

    const auto week_window = std::chrono::seconds((HotspotCounter::week_counters_size + 1) *

                                                  HotspotCounter::time_interval);

    return counter.last_access_time < now - week_window &&

           counter.cur_counter.load(std::memory_order_relaxed) == 0 &&

           counter.day_history_counter.load(std::memory_order_relaxed) == 0 &&

           counter.week_history_counter.load(std::memory_order_relaxed) == 0;

}

TabletHotspot::MaintenanceStats TabletHotspot::run_maintenance_once(SystemTimePoint now) {

    MaintenanceStats stats;

    auto gc_elapsed = SteadyClock::duration::zero();

    for (size_t slot_idx = 0; slot_idx < s_slot_size; ++slot_idx) {

        auto& slot = _tablets_hotspot[slot_idx];

        std::vector<HotspotCounterPtr> counters;

        size_t slot_size_before = 0;

        size_t slot_bucket_count_before = 0;

        {

            std::lock_guard lock(slot.mtx);

            slot_size_before = slot.map.size();

            slot_bucket_count_before = slot.map.bucket_count();

            stats.total_counters_before_gc += slot_size_before;

            if (slot_size_before > 0) {

                ++stats.non_empty_slots_before_gc;

            }

            stats.max_slot_size_before_gc =

                    std::max<uint64_t>(stats.max_slot_size_before_gc, slot_size_before);

            stats.sum_bucket_count_before_gc += slot_bucket_count_before;

            counters.reserve(slot_size_before);

            for (auto& [_, counter] : slot.map) {

                counters.push_back(counter);

            }

        }

        stats.copied_counters += counters.size();

        std::for_each(counters.begin(), counters.end(),

                      [](HotspotCounterPtr& counter) { counter->make_dot_point(); });

        size_t erased_count = 0;

        bool compacted = false;

        size_t slot_size_after = 0;

        size_t slot_bucket_count_after = 0;

        auto gc_start = SteadyClock::now();

        {

            std::lock_guard lock(slot.mtx);

            for (auto iter = slot.map.begin(); iter != slot.map.end();) {

                if (is_gc_eligible(*iter->second, now)) {

                    iter = slot.map.erase(iter);

                    ++erased_count;

                } else {

                    ++iter;

                }

            }

            if (should_compact_slot(slot_size_before, slot.map.size(), slot.map.bucket_count(),

                                    erased_count)) {

                decltype(slot.map) compacted_map;

                compacted_map.max_load_factor(slot.map.max_load_factor());

                compacted_map.reserve(slot.map.size());

                for (const auto& [tablet_id, counter] : slot.map) {

                    compacted_map.emplace(tablet_id, counter);

                }

                slot.map.swap(compacted_map);

                compacted = true;

            }

            slot_size_after = slot.map.size();

            slot_bucket_count_after = slot.map.bucket_count();

            stats.total_counters_after_gc += slot_size_after;

            if (slot_size_after > 0) {

                ++stats.non_empty_slots_after_gc;

            }

            stats.max_slot_size_after_gc =

                    std::max<uint64_t>(stats.max_slot_size_after_gc, slot_size_after);

            stats.sum_bucket_count_after_gc += slot_bucket_count_after;

        }

        gc_elapsed += SteadyClock::now() - gc_start;

        stats.evicted_counters += erased_count;

        if (compacted) {

            ++stats.compacted_slots;

        }

        if (erased_count > 0 || compacted) {

            LOG(INFO) << "tablet_hotspot_diag gc_slot"

                      << " slot_idx=" << slot_idx << " slot_size_before=" << slot_size_before

                      << " slot_size_after=" << slot_size_after

                      << " bucket_count_before=" << slot_bucket_count_before

                      << " bucket_count_after=" << slot_bucket_count_after

                      << " erased_count=" << erased_count << " compacted=" << compacted;

        }

    }

    stats.gc_elapsed_ms = std::chrono::duration_cast<std::chrono::milliseconds>(gc_elapsed).count();

    return stats;

}

void TabletHotspot::make_dot_point() {

    while (true) {

        {

            std::unique_lock lock(_mtx);

            _cond.wait_for(lock, std::chrono::seconds(HotspotCounter::time_interval),

                           [this]() { return _closed; });

            if (_closed) {

                break;

            }

        }

        const uint64_t round =

                _make_dot_point_round_total.fetch_add(1, std::memory_order_relaxed) + 1;

        const uint64_t count_calls_total = _count_calls_total.load(std::memory_order_relaxed);

        const uint64_t existing_hit_total = _existing_hit_total.load(std::memory_order_relaxed);

        const uint64_t new_counter_total_before =

                _new_counter_total.load(std::memory_order_relaxed);

        const int64_t process_mem_before = process_memory_usage_for_diag();

        const auto now = std::chrono::system_clock::now();

        const MaintenanceStats stats = run_maintenance_once(now);

        const int64_t process_mem_after = process_memory_usage_for_diag();

        const uint64_t new_counter_total_after = _new_counter_total.load(std::memory_order_relaxed);

        const uint64_t prev_round_new_counter_total = _last_round_new_counter_total.exchange(

                new_counter_total_after, std::memory_order_relaxed);

        const uint64_t new_counter_delta =

                new_counter_total_after >= prev_round_new_counter_total

                        ? (new_counter_total_after - prev_round_new_counter_total)

                        : 0;

        LOG(INFO) << "tablet_hotspot_diag make_dot_point round=" << round

                  << " total_counters=" << stats.total_counters_before_gc

                  << " total_counters_before_gc=" << stats.total_counters_before_gc

                  << " total_counters_after_gc=" << stats.total_counters_after_gc

                  << " non_empty_slots=" << stats.non_empty_slots_before_gc

                  << " non_empty_slots_before_gc=" << stats.non_empty_slots_before_gc

                  << " non_empty_slots_after_gc=" << stats.non_empty_slots_after_gc

                  << " max_slot_size=" << stats.max_slot_size_before_gc

                  << " max_slot_size_before_gc=" << stats.max_slot_size_before_gc

                  << " max_slot_size_after_gc=" << stats.max_slot_size_after_gc

                  << " sum_bucket_count=" << stats.sum_bucket_count_before_gc

                  << " sum_bucket_count_before_gc=" << stats.sum_bucket_count_before_gc

                  << " sum_bucket_count_after_gc=" << stats.sum_bucket_count_after_gc

                  << " copied_counters=" << stats.copied_counters

                  << " evicted_counters=" << stats.evicted_counters << " evicted_ratio="

                  << ratio_or_zero(stats.evicted_counters, stats.total_counters_before_gc)

                  << " compacted_slots=" << stats.compacted_slots << " bucket_reclaim_ratio="

                  << ratio_or_zero(

                             stats.sum_bucket_count_before_gc >= stats.sum_bucket_count_after_gc

                                     ? (stats.sum_bucket_count_before_gc -

                                        stats.sum_bucket_count_after_gc)

                                     : 0,

                             stats.sum_bucket_count_before_gc)

                  << " gc_elapsed_ms=" << stats.gc_elapsed_ms

                  << " count_calls_total=" << count_calls_total

                  << " existing_hit_total=" << existing_hit_total

                  << " new_counter_total_before=" << new_counter_total_before

                  << " new_counter_total_after=" << new_counter_total_after

                  << " new_counter_delta=" << new_counter_delta

                  << " process_mem_before_mb=" << bytes_to_mb(process_mem_before)

                  << " process_mem_after_mb=" << bytes_to_mb(process_mem_after);

    }

}

} // namespace doris