diff options
Diffstat (limited to '')
-rw-r--r-- | src/rocksdb/db/seqno_to_time_mapping.h | 189 |
1 files changed, 189 insertions, 0 deletions
diff --git a/src/rocksdb/db/seqno_to_time_mapping.h b/src/rocksdb/db/seqno_to_time_mapping.h new file mode 100644 index 000000000..4ffc9c199 --- /dev/null +++ b/src/rocksdb/db/seqno_to_time_mapping.h @@ -0,0 +1,189 @@ +// Copyright (c) Meta Platforms, Inc. and affiliates. +// +// 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 <cinttypes> +#include <deque> +#include <functional> +#include <iterator> +#include <string> + +#include "rocksdb/status.h" +#include "rocksdb/types.h" + +namespace ROCKSDB_NAMESPACE { + +constexpr uint64_t kUnknownSeqnoTime = 0; + +// SeqnoToTimeMapping stores the sequence number to time mapping, so given a +// sequence number it can estimate the oldest possible time for that sequence +// number. For example: +// 10 -> 100 +// 50 -> 300 +// then if a key has seqno 19, the OldestApproximateTime would be 100, for 51 it +// would be 300. +// As it's a sorted list, the new entry is inserted from the back. The old data +// will be popped from the front if they're no longer used. +// +// Note: the data struct is not thread safe, both read and write need to be +// synchronized by caller. +class SeqnoToTimeMapping { + public: + // Maximum number of entries can be encoded into SST. The data is delta encode + // so the maximum data usage for each SST is < 0.3K + static constexpr uint64_t kMaxSeqnoTimePairsPerSST = 100; + + // Maximum number of entries per CF. If there's only CF with this feature on, + // the max duration divided by this number, so for example, if + // preclude_last_level_data_seconds = 100000 (~1day), then it will sample the + // seqno -> time every 1000 seconds (~17minutes). Then the maximum entry it + // needs is 100. + // When there are multiple CFs having this feature on, the sampling cadence is + // determined by the smallest setting, the capacity is determined the largest + // setting, also it's caped by kMaxSeqnoTimePairsPerCF * 10. + static constexpr uint64_t kMaxSeqnoTimePairsPerCF = 100; + + // A simple struct for sequence number to time pair + struct SeqnoTimePair { + SequenceNumber seqno = 0; + uint64_t time = 0; + + SeqnoTimePair() = default; + SeqnoTimePair(SequenceNumber _seqno, uint64_t _time) + : seqno(_seqno), time(_time) {} + + // Encode to dest string + void Encode(std::string& dest) const; + + // Decode the value from input Slice and remove it from the input + Status Decode(Slice& input); + + // subtraction of 2 SeqnoTimePair + SeqnoTimePair operator-(const SeqnoTimePair& other) const; + + // Add 2 values together + void Add(const SeqnoTimePair& obj) { + seqno += obj.seqno; + time += obj.time; + } + + // Compare SeqnoTimePair with a sequence number, used for binary search a + // sequence number in a list of SeqnoTimePair + bool operator<(const SequenceNumber& other) const { return seqno < other; } + + // Compare 2 SeqnoTimePair + bool operator<(const SeqnoTimePair& other) const { + return std::tie(seqno, time) < std::tie(other.seqno, other.time); + } + + // Check if 2 SeqnoTimePair is the same + bool operator==(const SeqnoTimePair& other) const { + return std::tie(seqno, time) == std::tie(other.seqno, other.time); + } + }; + + // constractor of SeqnoToTimeMapping + // max_time_duration is the maximum time it should track. For example, if + // preclude_last_level_data_seconds is 1 day, then if an entry is older than 1 + // day, then it can be removed. + // max_capacity is the maximum number of entry it can hold. For single CF, + // it's caped at 100 (kMaxSeqnoTimePairsPerCF), otherwise + // kMaxSeqnoTimePairsPerCF * 10. + // If it's set to 0, means it won't truncate any old data. + explicit SeqnoToTimeMapping(uint64_t max_time_duration = 0, + uint64_t max_capacity = 0) + : max_time_duration_(max_time_duration), max_capacity_(max_capacity) {} + + // Append a new entry to the list. The new entry should be newer than the + // existing ones. It maintains the internal sorted status. + bool Append(SequenceNumber seqno, uint64_t time); + + // Given a sequence number, estimate it's oldest time + uint64_t GetOldestApproximateTime(SequenceNumber seqno) const; + + // Truncate the old entries based on the current time and max_time_duration_ + void TruncateOldEntries(uint64_t now); + + // Given a time, return it's oldest possible sequence number + SequenceNumber GetOldestSequenceNum(uint64_t time); + + // Encode to a binary string + void Encode(std::string& des, SequenceNumber start, SequenceNumber end, + uint64_t now, + uint64_t output_size = kMaxSeqnoTimePairsPerSST) const; + + // Add a new random entry, unlike Append(), it can be any data, but also makes + // the list un-sorted. + void Add(SequenceNumber seqno, uint64_t time); + + // Decode and add the entries to the current obj. The list will be unsorted + Status Add(const std::string& seqno_time_mapping_str); + + // Return the number of entries + size_t Size() const { return seqno_time_mapping_.size(); } + + // Reduce the size of internal list + bool Resize(uint64_t min_time_duration, uint64_t max_time_duration); + + // Override the max_time_duration_ + void SetMaxTimeDuration(uint64_t max_time_duration) { + max_time_duration_ = max_time_duration; + } + + uint64_t GetCapacity() const { return max_capacity_; } + + // Sort the list, which also remove the redundant entries, useless entries, + // which makes sure the seqno is sorted, but also the time + Status Sort(); + + // copy the current obj from the given smallest_seqno. + SeqnoToTimeMapping Copy(SequenceNumber smallest_seqno) const; + + // If the internal list is empty + bool Empty() const { return seqno_time_mapping_.empty(); } + + // clear all entries + void Clear() { seqno_time_mapping_.clear(); } + + // return the string for user message + // Note: Not efficient, okay for print + std::string ToHumanString() const; + +#ifndef NDEBUG + const std::deque<SeqnoTimePair>& TEST_GetInternalMapping() const { + return seqno_time_mapping_; + } +#endif + + private: + static constexpr uint64_t kMaxSeqnoToTimeEntries = + kMaxSeqnoTimePairsPerCF * 10; + + uint64_t max_time_duration_; + uint64_t max_capacity_; + + std::deque<SeqnoTimePair> seqno_time_mapping_; + + bool is_sorted_ = true; + + static uint64_t CalculateMaxCapacity(uint64_t min_time_duration, + uint64_t max_time_duration); + + SeqnoTimePair& Last() { + assert(!Empty()); + return seqno_time_mapping_.back(); + } +}; + +// for searching the sequence number from SeqnoToTimeMapping +inline bool operator<(const SequenceNumber& seqno, + const SeqnoToTimeMapping::SeqnoTimePair& other) { + return seqno < other.seqno; +} + +} // namespace ROCKSDB_NAMESPACE |