This is an automated email from the ASF dual-hosted git repository.
w41ter pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/doris.git
The following commit(s) were added to refs/heads/master by this push:
new fe0fb6a55aa [fix](txnkv) avoid skip keys during reverse full range
iteration (#52800)
fe0fb6a55aa is described below
commit fe0fb6a55aa4296d68534ea8a7ffd57a0564a157
Author: walter <[email protected]>
AuthorDate: Mon Jul 7 14:34:12 2025 +0800
[fix](txnkv) avoid skip keys during reverse full range iteration (#52800)
It was introduced by #52730. When switching to the next batch,
FullRangeGetIterator should not continue to use the RangeKeySelector
provided by the user; otherwise, it will lead to inaccurate key bounds.
---
cloud/src/meta-store/mem_txn_kv.cpp | 197 +++++++++++++++++---
cloud/src/meta-store/mem_txn_kv.h | 17 +-
cloud/src/meta-store/txn_kv.cpp | 11 +-
cloud/src/meta-store/txn_kv.h | 24 +--
cloud/test/mem_txn_kv_test.cpp | 358 ++++++++++++++++++++++++++++++++++++
cloud/test/txn_kv_test.cpp | 110 ++++++++++-
6 files changed, 655 insertions(+), 62 deletions(-)
diff --git a/cloud/src/meta-store/mem_txn_kv.cpp
b/cloud/src/meta-store/mem_txn_kv.cpp
index 3ab7cab16d3..db0850b0c1c 100644
--- a/cloud/src/meta-store/mem_txn_kv.cpp
+++ b/cloud/src/meta-store/mem_txn_kv.cpp
@@ -25,6 +25,7 @@
#include <mutex>
#include <optional>
#include <ostream>
+#include <ranges>
#include <string>
#include "cpp/sync_point.h"
@@ -63,12 +64,14 @@ TxnErrorCode MemTxnKv::get_kv(const std::string& key,
std::string* val, int64_t
}
TxnErrorCode MemTxnKv::get_kv(const std::string& begin, const std::string&
end, int64_t version,
- int limit, bool* more, std::map<std::string,
std::string>* kv_list) {
+ const RangeGetOptions& opts, bool* more,
+ std::vector<std::pair<std::string,
std::string>>* kv_list) {
if (begin >= end) {
return TxnErrorCode::TXN_OK;
}
bool use_limit = true;
+ int limit = opts.batch_limit;
if (limit < 0) {
return TxnErrorCode::TXN_UNIDENTIFIED_ERROR;
@@ -79,30 +82,105 @@ TxnErrorCode MemTxnKv::get_kv(const std::string& begin,
const std::string& end,
std::unique_lock<std::mutex> l(lock_);
- *more = false;
- auto begin_iter = mem_kv_.lower_bound(begin);
- auto end_iter = mem_kv_.lower_bound(end);
- for (; begin_iter != mem_kv_.end() && begin_iter != end_iter;
begin_iter++) {
- for (auto&& entry : begin_iter->second) {
- if (entry.commit_version > version) {
- continue;
+ auto apply_key_selector = [&](RangeKeySelector selector,
+ const std::string& key) ->
decltype(mem_kv_.lower_bound(key)) {
+ auto iter = mem_kv_.lower_bound(key);
+ switch (selector) {
+ case RangeKeySelector::FIRST_GREATER_OR_EQUAL:
+ break;
+ case RangeKeySelector::FIRST_GREATER_THAN:
+ if (iter != mem_kv_.end() && iter->first == key) {
+ ++iter;
+ }
+ break;
+ case RangeKeySelector::LAST_LESS_OR_EQUAL:
+ if (iter != mem_kv_.begin() && iter->first != key) {
+ --iter;
+ }
+ break;
+ case RangeKeySelector::LAST_LESS_THAN:
+ if (iter != mem_kv_.begin()) {
+ --iter;
}
+ break;
+ }
+ return iter;
+ };
- if (!entry.value.has_value()) {
+ *more = false;
+
+ bool reverse = opts.reverse;
+ std::vector<std::pair<std::string, std::string>> temp_results;
+
+ if (!reverse) {
+ // Forward iteration
+ auto begin_iter = apply_key_selector(opts.begin_key_selector, begin);
+ auto end_iter = apply_key_selector(opts.end_key_selector, end);
+ if (begin_iter == mem_kv_.end() ||
+ (end_iter != mem_kv_.end() && end_iter->first <
begin_iter->first)) {
+ // If the begin iterator is at the end or the end iterator is
before begin, return empty
+ kv_list->clear();
+ *more = false;
+ return TxnErrorCode::TXN_OK;
+ }
+
+ for (; begin_iter != end_iter; begin_iter++) {
+ // Find the appropriate version
+ for (auto&& entry : begin_iter->second) {
+ if (entry.commit_version > version) {
+ continue;
+ }
+
+ if (!entry.value.has_value()) {
+ break;
+ }
+
+ temp_results.emplace_back(begin_iter->first, *entry.value);
break;
}
- kv_list->insert_or_assign(begin_iter->first, *entry.value);
- limit--;
- break;
+ if (use_limit && temp_results.size() >=
static_cast<size_t>(limit)) {
+ *more = true;
+ break;
+ }
}
- if (use_limit && limit == 0) {
- break;
+ } else {
+ // Reverse iteration
+ auto end_iter = apply_key_selector(opts.end_key_selector, end);
+ auto begin_iter = apply_key_selector(opts.begin_key_selector, begin);
+ if (begin_iter == mem_kv_.end() ||
+ (end_iter != mem_kv_.end() && end_iter->first <=
begin_iter->first)) {
+ kv_list->clear();
+ *more = false;
+ return TxnErrorCode::TXN_OK;
}
+
+ do {
+ --end_iter; // end always excludes the last key
+
+ // Find the appropriate version (use reverse iterator for versions)
+ for (auto iter = end_iter->second.rbegin(); iter !=
end_iter->second.rend(); ++iter) {
+ if (iter->commit_version > version) {
+ continue;
+ }
+
+ if (!iter->value.has_value()) {
+ break;
+ }
+
+ temp_results.emplace_back(end_iter->first, *iter->value);
+ break;
+ }
+
+ if (use_limit && temp_results.size() >=
static_cast<size_t>(limit)) {
+ *more = true;
+ break;
+ }
+ } while (end_iter != begin_iter);
}
- if (use_limit && limit == 0 && ++begin_iter != end_iter) {
- *more = true;
- }
+
+ kv_list->swap(temp_results);
+
return TxnErrorCode::TXN_OK;
}
@@ -330,10 +408,9 @@ TxnErrorCode Transaction::inner_get(const std::string&
begin, const std::string&
std::unique_ptr<cloud::RangeGetIterator>*
iter,
const RangeGetOptions& opts) {
bool more = false;
- std::map<std::string, std::string> kv_map;
- int limit = opts.batch_limit;
bool snapshot = opts.snapshot;
- TxnErrorCode err = kv_->get_kv(begin, end, read_version_, limit, &more,
&kv_map);
+ std::vector<std::pair<std::string, std::string>> kv_list;
+ TxnErrorCode err = kv_->get_kv(begin, end, read_version_, opts, &more,
&kv_list);
if (err != TxnErrorCode::TXN_OK) {
return err;
}
@@ -347,28 +424,81 @@ TxnErrorCode Transaction::inner_get(const std::string&
begin, const std::string&
}
return false;
};
- for (auto it = kv_map.begin(), last = kv_map.end(); it != last;) {
+ for (auto it = kv_list.begin(), last = kv_list.end(); it != last;) {
if (pred(*it)) {
- it = kv_map.erase(it);
+ it = kv_list.erase(it);
} else {
++it;
}
}
if (!snapshot) {
- for (auto&& [key, _] : kv_map) {
+ for (auto&& [key, _] : kv_list) {
read_set_.insert(key);
}
}
- auto begin_iter = writes_.lower_bound(begin);
- auto end_iter = writes_.lower_bound(end);
- while (begin_iter != end_iter) {
- kv_map.insert_or_assign(begin_iter->first, begin_iter->second);
- begin_iter++;
+ std::map<std::string, std::string> kv_map;
+ for (const auto& [key, value] : kv_list) {
+ kv_map[key] = value;
+ }
+
+ // Get writes in the range and apply key selectors
+ auto apply_key_selector = [&](RangeKeySelector selector,
+ const std::string& key) ->
decltype(writes_.lower_bound(key)) {
+ auto iter = writes_.lower_bound(key);
+ switch (selector) {
+ case RangeKeySelector::FIRST_GREATER_OR_EQUAL:
+ break;
+ case RangeKeySelector::FIRST_GREATER_THAN:
+ if (iter != writes_.end() && iter->first == key) {
+ ++iter;
+ }
+ break;
+ case RangeKeySelector::LAST_LESS_OR_EQUAL:
+ if (iter != writes_.begin() && iter->first != key) {
+ --iter;
+ }
+ break;
+ case RangeKeySelector::LAST_LESS_THAN:
+ if (iter != writes_.begin()) {
+ --iter;
+ }
+ break;
+ }
+ return iter;
+ };
+
+ auto begin_iter = apply_key_selector(opts.begin_key_selector, begin);
+ auto end_iter = apply_key_selector(opts.end_key_selector, end);
+
+ // The end_iter is exclusive, so we need to check if it is valid:
+ // 1. end_iter is in the end
+ // 2. or the begin_iter is less than the end_iter
+ for (; begin_iter != end_iter &&
+ (end_iter == writes_.end() || begin_iter->first < end_iter->first);
+ ++begin_iter) {
+ const auto& key = begin_iter->first;
+ const auto& value = begin_iter->second;
+ kv_map[key] = value;
+ }
+
+ kv_list.clear();
+ if (!opts.reverse) {
+ for (const auto& [key, value] : kv_map) {
+ kv_list.emplace_back(key, value);
+ }
+ } else {
+ for (auto& it : std::ranges::reverse_view(kv_map)) {
+ kv_list.emplace_back(it.first, it.second);
+ }
+ }
+
+ if (opts.batch_limit > 0 && kv_list.size() >
static_cast<size_t>(opts.batch_limit)) {
+ more = true;
+ kv_list.resize(opts.batch_limit);
}
- std::vector<std::pair<std::string, std::string>> kv_list(kv_map.begin(),
kv_map.end());
num_get_keys_ += kv_list.size();
kv_->get_count_ += kv_list.size();
*iter = std::make_unique<memkv::RangeGetIterator>(std::move(kv_list),
more);
@@ -576,7 +706,14 @@ bool FullRangeGetIterator::has_next() {
txn = txn_.get();
}
- TxnErrorCode err = txn->get(begin_, end_, &inner_iter_,
opts_.snapshot, 0);
+ // For simplicity, we always get the entire range without batch limit.
+ RangeGetOptions opts;
+ opts.snapshot = opts_.snapshot;
+ opts.batch_limit = 0;
+ opts.reverse = opts_.reverse;
+ opts.begin_key_selector = opts_.begin_key_selector;
+ opts.end_key_selector = opts_.end_key_selector;
+ TxnErrorCode err = txn->get(begin_, end_, &inner_iter_, opts);
if (err != TxnErrorCode::TXN_OK) {
is_valid_ = false;
code_ = err;
diff --git a/cloud/src/meta-store/mem_txn_kv.h
b/cloud/src/meta-store/mem_txn_kv.h
index 3e7de0d2636..58f1ff59b82 100644
--- a/cloud/src/meta-store/mem_txn_kv.h
+++ b/cloud/src/meta-store/mem_txn_kv.h
@@ -56,7 +56,8 @@ public:
TxnErrorCode get_kv(const std::string& key, std::string* val, int64_t
version);
TxnErrorCode get_kv(const std::string& begin, const std::string& end,
int64_t version,
- int limit, bool* more, std::map<std::string,
std::string>* kv_list);
+ const RangeGetOptions& opts, bool* more,
+ std::vector<std::pair<std::string, std::string>>*
kv_list);
size_t total_kvs() const {
std::lock_guard<std::mutex> l(lock_);
@@ -299,19 +300,9 @@ public:
return k;
}
- std::string prev_end_key() const override {
+ std::string_view last_key() const override {
if (!more()) return {};
- std::string k(kvs_[kvs_size_ - 1].first);
- if (k.empty()) {
- // The minimum key, return an empty string
- } else if (k.back() == '\x00') {
- // If the last byte is a null byte, we should remove it
- k.pop_back();
- } else {
- // Otherwise, we should decrement the last byte
- k.back() -= 1;
- }
- return k;
+ return kvs_[kvs_size_ - 1].first;
}
private:
diff --git a/cloud/src/meta-store/txn_kv.cpp b/cloud/src/meta-store/txn_kv.cpp
index eb4054ac705..c858750d089 100644
--- a/cloud/src/meta-store/txn_kv.cpp
+++ b/cloud/src/meta-store/txn_kv.cpp
@@ -873,9 +873,16 @@ void
FullRangeGetIterator::async_inner_get(std::string_view begin, std::string_v
void FullRangeGetIterator::async_get_next_batch() {
if (opts_.reverse) {
- async_inner_get(begin_, inner_iter_->prev_end_key());
+ // Change the end key to the previous last key. The key selector will
be
+ // FIRST_GREATER_OR_EQUAL, so we need to use the last key of the inner
iterator as the
+ // end key, since the end key is exclusive.
+ opts_.end_key_selector = RangeKeySelector::FIRST_GREATER_OR_EQUAL;
+ std::string_view end_key = inner_iter_->last_key();
+ async_inner_get(begin_, end_key);
} else {
- async_inner_get(inner_iter_->next_begin_key(), end_);
+ opts_.begin_key_selector = RangeKeySelector::FIRST_GREATER_OR_EQUAL;
+ std::string begin_key = inner_iter_->next_begin_key();
+ async_inner_get(begin_key, end_);
}
}
diff --git a/cloud/src/meta-store/txn_kv.h b/cloud/src/meta-store/txn_kv.h
index 01eaf1486ef..00091ed1b2c 100644
--- a/cloud/src/meta-store/txn_kv.h
+++ b/cloud/src/meta-store/txn_kv.h
@@ -395,10 +395,12 @@ public:
virtual std::string next_begin_key() const = 0;
/**
- * Get the end key of the next iterator if `more()` is true, otherwise
returns empty string.
- * This is used for reverse range get.
+ * Get the last key of the iterator, it can be used as the end key of the
next iterator when
+ * the key selector is FIRST_GREATER_OR_EQUAL.
+ *
+ * ATTN: This is ONLY used for reverse range get.
*/
- virtual std::string prev_end_key() const = 0;
+ virtual std::string_view last_key() const = 0;
RangeGetIterator(const RangeGetIterator&) = delete;
RangeGetIterator& operator=(const RangeGetIterator&) = delete;
@@ -572,20 +574,10 @@ public:
return k;
}
- std::string prev_end_key() const override {
- if (!more()) return {};
+ std::string_view last_key() const override {
+ if (kvs_size_ <= 0) return {};
const auto& kv = kvs_[kvs_size_ - 1];
- std::string k((char*)kv.key, (size_t)kv.key_length);
- if (k.empty()) {
- // The minimum key, return an empty string
- } else if (k.back() == '\x00') {
- // If the last byte is a null byte, we should remove it
- k.pop_back();
- } else {
- // Otherwise, we should decrement the last byte
- k.back() -= 1;
- }
- return k;
+ return {(char*)kv.key, (size_t)kv.key_length};
}
RangeGetIterator(const RangeGetIterator&) = delete;
diff --git a/cloud/test/mem_txn_kv_test.cpp b/cloud/test/mem_txn_kv_test.cpp
index e5f9aa8736f..5dea50ca05d 100644
--- a/cloud/test/mem_txn_kv_test.cpp
+++ b/cloud/test/mem_txn_kv_test.cpp
@@ -25,6 +25,7 @@
#include "common/config.h"
#include "common/util.h"
#include "meta-service/doris_txn.h"
+#include "meta-store/codec.h"
#include "meta-store/txn_kv.h"
#include "meta-store/txn_kv_error.h"
@@ -980,3 +981,360 @@ TEST(TxnMemKvTest, MaybeUnusedFunctionTest) {
}
}
}
+
+TEST(TxnMemKvTest, RangeGetKeySelector) {
+ using namespace doris::cloud;
+ auto txn_kv = std::make_shared<MemTxnKv>();
+ ASSERT_EQ(txn_kv->init(), 0);
+
+ constexpr std::string_view prefix = "range_get_key_selector_";
+
+ {
+ // Remove the existing keys and insert some new keys.
+ std::unique_ptr<Transaction> txn;
+ TxnErrorCode err = txn_kv->create_txn(&txn);
+ ASSERT_EQ(err, TxnErrorCode::TXN_OK);
+
+ std::string last_key = fmt::format("{}{}", prefix, 9);
+ encode_int64(INT64_MAX, &last_key);
+ txn->remove(prefix, last_key);
+ for (int i = 0; i < 5; ++i) {
+ std::string key = fmt::format("{}{}", prefix, i);
+ txn->put(key, std::to_string(i));
+ }
+ err = txn->commit();
+ ASSERT_EQ(err, TxnErrorCode::TXN_OK);
+ }
+
+ struct TestCase {
+ RangeKeySelector begin_key_selector, end_key_selector;
+ std::vector<std::string> expected_keys;
+ };
+
+ std::string range_begin = fmt::format("{}{}", prefix, 1);
+ std::string range_end = fmt::format("{}{}", prefix, 3);
+ std::vector<TestCase> test_case {
+ {
+ RangeKeySelector::FIRST_GREATER_OR_EQUAL,
+ RangeKeySelector::FIRST_GREATER_OR_EQUAL,
+ {fmt::format("{}{}", prefix, 1), fmt::format("{}{}",
prefix, 2)},
+ },
+ {
+ RangeKeySelector::FIRST_GREATER_OR_EQUAL,
+ RangeKeySelector::FIRST_GREATER_THAN,
+ {
+ fmt::format("{}{}", prefix, 1),
+ fmt::format("{}{}", prefix, 2),
+ fmt::format("{}{}", prefix, 3),
+ },
+ },
+ {
+ RangeKeySelector::FIRST_GREATER_OR_EQUAL,
+ RangeKeySelector::LAST_LESS_OR_EQUAL,
+ {fmt::format("{}{}", prefix, 1), fmt::format("{}{}",
prefix, 2)},
+ },
+ {
+ RangeKeySelector::FIRST_GREATER_OR_EQUAL,
+ RangeKeySelector::LAST_LESS_THAN,
+ {fmt::format("{}{}", prefix, 1)},
+ },
+ {
+ RangeKeySelector::FIRST_GREATER_THAN,
+ RangeKeySelector::FIRST_GREATER_OR_EQUAL,
+ {fmt::format("{}{}", prefix, 2)},
+ },
+ {
+ RangeKeySelector::FIRST_GREATER_THAN,
+ RangeKeySelector::FIRST_GREATER_THAN,
+ {fmt::format("{}{}", prefix, 2), fmt::format("{}{}",
prefix, 3)},
+ },
+ {
+ RangeKeySelector::FIRST_GREATER_THAN,
+ RangeKeySelector::LAST_LESS_OR_EQUAL,
+ {fmt::format("{}{}", prefix, 2)},
+ },
+ {
+ RangeKeySelector::FIRST_GREATER_THAN,
+ RangeKeySelector::LAST_LESS_THAN,
+ {},
+ },
+ {
+ RangeKeySelector::LAST_LESS_OR_EQUAL,
+ RangeKeySelector::FIRST_GREATER_OR_EQUAL,
+ {fmt::format("{}{}", prefix, 1), fmt::format("{}{}",
prefix, 2)},
+ },
+ {
+ RangeKeySelector::LAST_LESS_OR_EQUAL,
+ RangeKeySelector::FIRST_GREATER_THAN,
+ {
+ fmt::format("{}{}", prefix, 1),
+ fmt::format("{}{}", prefix, 2),
+ fmt::format("{}{}", prefix, 3),
+ },
+ },
+ {
+ RangeKeySelector::LAST_LESS_OR_EQUAL,
+ RangeKeySelector::LAST_LESS_OR_EQUAL,
+ {fmt::format("{}{}", prefix, 1), fmt::format("{}{}",
prefix, 2)},
+ },
+ {
+ RangeKeySelector::LAST_LESS_OR_EQUAL,
+ RangeKeySelector::LAST_LESS_THAN,
+ {fmt::format("{}{}", prefix, 1)},
+ },
+ {
+ RangeKeySelector::LAST_LESS_THAN,
+ RangeKeySelector::FIRST_GREATER_OR_EQUAL,
+ {
+ fmt::format("{}{}", prefix, 0),
+ fmt::format("{}{}", prefix, 1),
+ fmt::format("{}{}", prefix, 2),
+ },
+ },
+ {
+ RangeKeySelector::LAST_LESS_THAN,
+ RangeKeySelector::FIRST_GREATER_THAN,
+ {
+ fmt::format("{}{}", prefix, 0),
+ fmt::format("{}{}", prefix, 1),
+ fmt::format("{}{}", prefix, 2),
+ fmt::format("{}{}", prefix, 3),
+ },
+ },
+ {
+ RangeKeySelector::LAST_LESS_THAN,
+ RangeKeySelector::LAST_LESS_OR_EQUAL,
+ {
+ fmt::format("{}{}", prefix, 0),
+ fmt::format("{}{}", prefix, 1),
+ fmt::format("{}{}", prefix, 2),
+ },
+ },
+ {
+ RangeKeySelector::LAST_LESS_THAN,
+ RangeKeySelector::LAST_LESS_THAN,
+ {fmt::format("{}{}", prefix, 0), fmt::format("{}{}",
prefix, 1)},
+ },
+ };
+
+ // Scan range with different key selectors
+ for (const auto& tc : test_case) {
+ std::unique_ptr<Transaction> txn;
+ TxnErrorCode err = txn_kv->create_txn(&txn);
+ ASSERT_EQ(err, TxnErrorCode::TXN_OK);
+
+ RangeGetOptions options;
+ options.batch_limit = 1000;
+ options.begin_key_selector = tc.begin_key_selector;
+ options.end_key_selector = tc.end_key_selector;
+ std::unique_ptr<RangeGetIterator> it;
+ err = txn->get(range_begin, range_end, &it, options);
+ ASSERT_EQ(err, TxnErrorCode::TXN_OK);
+
+ std::vector<std::string> actual_keys;
+ while (it->has_next()) {
+ auto [k, v] = it->next();
+ actual_keys.emplace_back(k);
+ }
+ EXPECT_EQ(actual_keys, tc.expected_keys)
+ << "Failed for begin_key_selector=" <<
static_cast<int>(tc.begin_key_selector)
+ << ", end_key_selector=" <<
static_cast<int>(tc.end_key_selector);
+ }
+}
+
+TEST(TxnMemKvTest, ReverseRangeGet) {
+ using namespace doris::cloud;
+ auto txn_kv = std::make_shared<MemTxnKv>();
+ ASSERT_EQ(txn_kv->init(), 0);
+
+ constexpr std::string_view prefix = "reverse_range_get_";
+
+ {
+ // Remove the existing keys and insert some new keys.
+ std::unique_ptr<Transaction> txn;
+ TxnErrorCode err = txn_kv->create_txn(&txn);
+ ASSERT_EQ(err, TxnErrorCode::TXN_OK);
+
+ std::string last_key = fmt::format("{}{}", prefix, 9);
+ encode_int64(INT64_MAX, &last_key);
+ txn->remove(prefix, last_key);
+ for (int i = 0; i < 5; ++i) {
+ std::string key = fmt::format("{}{}", prefix, i);
+ txn->put(key, std::to_string(i));
+ }
+ err = txn->commit();
+ ASSERT_EQ(err, TxnErrorCode::TXN_OK);
+ }
+
+ std::string range_begin = fmt::format("{}{}", prefix, 1);
+ std::string range_end = fmt::format("{}{}", prefix, 3);
+
+ struct TestCase {
+ RangeKeySelector begin_key_selector, end_key_selector;
+ std::vector<std::string> expected_keys;
+ };
+
+ std::vector<TestCase> test_case {
+ // 1. [begin, end)
+ {
+ RangeKeySelector::FIRST_GREATER_OR_EQUAL,
+ RangeKeySelector::FIRST_GREATER_OR_EQUAL,
+ {fmt::format("{}{}", prefix, 2), fmt::format("{}{}",
prefix, 1)},
+ },
+ // 2. [begin, end]
+ {
+ RangeKeySelector::FIRST_GREATER_OR_EQUAL,
+ RangeKeySelector::FIRST_GREATER_THAN,
+ {
+ fmt::format("{}{}", prefix, 3),
+ fmt::format("{}{}", prefix, 2),
+ fmt::format("{}{}", prefix, 1),
+ },
+ },
+ // 3. (begin, end)
+ {
+ RangeKeySelector::FIRST_GREATER_THAN,
+ RangeKeySelector::FIRST_GREATER_OR_EQUAL,
+ {fmt::format("{}{}", prefix, 2)},
+ },
+ // 4. (begin, end]
+ {
+ RangeKeySelector::FIRST_GREATER_THAN,
+ RangeKeySelector::FIRST_GREATER_THAN,
+ {fmt::format("{}{}", prefix, 3), fmt::format("{}{}",
prefix, 2)},
+ },
+ };
+ for (const auto& tc : test_case) {
+ std::unique_ptr<Transaction> txn;
+ TxnErrorCode err = txn_kv->create_txn(&txn);
+ ASSERT_EQ(err, TxnErrorCode::TXN_OK);
+
+ RangeGetOptions options;
+ options.batch_limit = 1000;
+ options.begin_key_selector = tc.begin_key_selector;
+ options.end_key_selector = tc.end_key_selector;
+ options.reverse = true; // Reserve range get
+ std::unique_ptr<RangeGetIterator> it;
+ err = txn->get(range_begin, range_end, &it, options);
+ ASSERT_EQ(err, TxnErrorCode::TXN_OK);
+
+ std::vector<std::string> actual_keys;
+ while (it->has_next()) {
+ auto [k, v] = it->next();
+ actual_keys.emplace_back(k);
+ }
+ EXPECT_EQ(actual_keys, tc.expected_keys)
+ << "Failed for begin_key_selector=" <<
static_cast<int>(tc.begin_key_selector)
+ << ", end_key_selector=" <<
static_cast<int>(tc.end_key_selector);
+ }
+}
+
+TEST(TxnMemKvTest, ReverseFullRangeGet) {
+ using namespace doris::cloud;
+ auto txn_kv = std::make_shared<MemTxnKv>();
+ ASSERT_EQ(txn_kv->init(), 0);
+
+ constexpr std::string_view prefix = "reverse_full_range_get_";
+
+ {
+ // Remove the existing keys and insert some new keys.
+ std::unique_ptr<Transaction> txn;
+ TxnErrorCode err = txn_kv->create_txn(&txn);
+ ASSERT_EQ(err, TxnErrorCode::TXN_OK);
+
+ std::string last_key = fmt::format("{}{:03}", prefix, 99);
+ encode_int64(INT64_MAX, &last_key);
+ txn->remove(prefix, last_key);
+ for (int i = 0; i < 100; ++i) {
+ std::string key = fmt::format("{}{:03}", prefix, i);
+ txn->put(key, std::to_string(i));
+ }
+ err = txn->commit();
+ ASSERT_EQ(err, TxnErrorCode::TXN_OK);
+ }
+
+ std::string range_begin = fmt::format("{}{:03}", prefix, 1);
+ std::string range_end = fmt::format("{}{:03}", prefix, 98);
+
+ struct TestCase {
+ RangeKeySelector begin_key_selector, end_key_selector;
+ };
+
+ std::vector<TestCase> test_case {
+ // 1. [begin, end)
+ {
+ RangeKeySelector::FIRST_GREATER_OR_EQUAL,
+ RangeKeySelector::FIRST_GREATER_OR_EQUAL,
+ },
+ // 2. [begin, end]
+ {
+ RangeKeySelector::FIRST_GREATER_OR_EQUAL,
+ RangeKeySelector::FIRST_GREATER_THAN,
+ },
+ // 3. (begin, end)
+ {
+ RangeKeySelector::FIRST_GREATER_THAN,
+ RangeKeySelector::FIRST_GREATER_OR_EQUAL,
+ },
+ // 4. (begin, end]
+ {
+ RangeKeySelector::FIRST_GREATER_THAN,
+ RangeKeySelector::FIRST_GREATER_THAN,
+ },
+ };
+
+ for (const auto& tc : test_case) {
+ std::vector<std::string> expected_keys;
+ {
+ // Read the expected keys via range_get
+ std::unique_ptr<Transaction> txn;
+ TxnErrorCode err = txn_kv->create_txn(&txn);
+ ASSERT_EQ(err, TxnErrorCode::TXN_OK);
+
+ RangeGetOptions options;
+ options.batch_limit = 11;
+ options.begin_key_selector = tc.begin_key_selector;
+ options.end_key_selector = tc.end_key_selector;
+ options.reverse = true; // Reserve range get
+ std::string begin = range_begin, end = range_end;
+
+ std::unique_ptr<RangeGetIterator> it;
+ do {
+ err = txn->get(begin, end, &it, options);
+ ASSERT_EQ(err, TxnErrorCode::TXN_OK);
+
+ while (it->has_next()) {
+ auto [k, v] = it->next();
+ expected_keys.emplace_back(k);
+ }
+ // Get next begin key for reverse range get
+ end = it->last_key();
+ options.end_key_selector =
RangeKeySelector::FIRST_GREATER_OR_EQUAL;
+ } while (it->more());
+ }
+
+ std::vector<std::string> actual_keys;
+ {
+ // Read the actual keys via full_range_get
+ FullRangeGetOptions opts(txn_kv);
+ opts.batch_limit = 11;
+ opts.begin_key_selector = tc.begin_key_selector;
+ opts.end_key_selector = tc.end_key_selector;
+ opts.reverse = true; // Reserve full range get
+
+ auto it = txn_kv->full_range_get(range_begin, range_end, opts);
+ ASSERT_TRUE(it->is_valid());
+
+ while (it->has_next()) {
+ auto kvp = it->next();
+ ASSERT_TRUE(kvp.has_value());
+ auto [k, v] = *kvp;
+ actual_keys.emplace_back(k);
+ }
+ }
+
+ EXPECT_EQ(actual_keys, expected_keys)
+ << "Failed for begin_key_selector=" <<
static_cast<int>(tc.begin_key_selector)
+ << ", end_key_selector=" <<
static_cast<int>(tc.end_key_selector);
+ }
+}
diff --git a/cloud/test/txn_kv_test.cpp b/cloud/test/txn_kv_test.cpp
index 85bef04f9c9..b0412f51e1a 100644
--- a/cloud/test/txn_kv_test.cpp
+++ b/cloud/test/txn_kv_test.cpp
@@ -1259,7 +1259,115 @@ TEST(TxnKvTest, ReverseFullRangeGet) {
expected_keys.emplace_back(k);
}
// Get next begin key for reverse range get
- end = it->prev_end_key();
+ end = it->last_key();
+ options.end_key_selector =
RangeKeySelector::FIRST_GREATER_OR_EQUAL;
+ } while (it->more());
+ }
+
+ std::vector<std::string> actual_keys;
+ {
+ // Read the actual keys via full_range_get
+ FullRangeGetOptions opts(txn_kv);
+ opts.batch_limit = 11;
+ opts.begin_key_selector = tc.begin_key_selector;
+ opts.end_key_selector = tc.end_key_selector;
+ opts.reverse = true; // Reserve full range get
+
+ auto it = txn_kv->full_range_get(range_begin, range_end, opts);
+ ASSERT_TRUE(it->is_valid());
+
+ while (it->has_next()) {
+ auto kvp = it->next();
+ ASSERT_TRUE(kvp.has_value());
+ auto [k, v] = *kvp;
+ actual_keys.emplace_back(k);
+ }
+ }
+
+ EXPECT_EQ(actual_keys, expected_keys)
+ << "Failed for begin_key_selector=" <<
static_cast<int>(tc.begin_key_selector)
+ << ", end_key_selector=" <<
static_cast<int>(tc.end_key_selector);
+ }
+}
+
+TEST(TxnKvTest, ReverseFullRangeGet2) {
+ constexpr std::string_view prefix = "reverse_full_range_get_2_";
+
+ {
+ // Remove the existing keys and insert some new keys.
+ std::unique_ptr<Transaction> txn;
+ TxnErrorCode err = txn_kv->create_txn(&txn);
+ ASSERT_EQ(err, TxnErrorCode::TXN_OK);
+
+ std::string last_key = fmt::format("{}b", prefix);
+ encode_int64(INT64_MAX, &last_key);
+ txn->remove(prefix, last_key);
+ std::string key(prefix);
+ for (int i = 0; i < 100; ++i) {
+ key += 'a';
+ txn->put(key, std::to_string(i));
+ }
+ err = txn->commit();
+ ASSERT_EQ(err, TxnErrorCode::TXN_OK);
+ }
+
+ std::string range_begin(prefix);
+ std::string range_end = fmt::format("{}b", prefix);
+
+ struct TestCase {
+ RangeKeySelector begin_key_selector, end_key_selector;
+ };
+
+ std::vector<TestCase> test_case {
+ // 1. [begin, end)
+ {
+ RangeKeySelector::FIRST_GREATER_OR_EQUAL,
+ RangeKeySelector::FIRST_GREATER_OR_EQUAL,
+ },
+ // 2. [begin, end]
+ {
+ RangeKeySelector::FIRST_GREATER_OR_EQUAL,
+ RangeKeySelector::FIRST_GREATER_THAN,
+ },
+ // 3. (begin, end)
+ {
+ RangeKeySelector::FIRST_GREATER_THAN,
+ RangeKeySelector::FIRST_GREATER_OR_EQUAL,
+ },
+ // 4. (begin, end]
+ {
+ RangeKeySelector::FIRST_GREATER_THAN,
+ RangeKeySelector::FIRST_GREATER_THAN,
+ },
+ };
+
+ for (const auto& tc : test_case) {
+ std::vector<std::string> expected_keys;
+ {
+ // Read the expected keys via range_get
+ std::unique_ptr<Transaction> txn;
+ TxnErrorCode err = txn_kv->create_txn(&txn);
+ ASSERT_EQ(err, TxnErrorCode::TXN_OK);
+
+ RangeGetOptions options;
+ options.batch_limit = 11;
+ options.begin_key_selector = tc.begin_key_selector;
+ options.end_key_selector = tc.end_key_selector;
+ options.reverse = true; // Reserve range get
+ std::string begin = range_begin, end = range_end;
+
+ std::unique_ptr<RangeGetIterator> it;
+ do {
+ err = txn->get(begin, end, &it, options);
+ ASSERT_EQ(err, TxnErrorCode::TXN_OK);
+
+ while (it->has_next()) {
+ auto [k, v] = it->next();
+ expected_keys.emplace_back(k);
+ }
+ // Get next begin key for reverse range get
+ end = it->last_key();
+ options.end_key_selector =
RangeKeySelector::FIRST_GREATER_OR_EQUAL;
} while (it->more());
}
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
