You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@doris.apache.org by he...@apache.org on 2026/04/16 12:55:34 UTC
(doris) branch master updated: [improvement](be) Add stampede protection for AnnIndexIVFListCache (#62442)
This is an automated email from the ASF dual-hosted git repository.
hellostephen 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 4952cad5ebf [improvement](be) Add stampede protection for AnnIndexIVFListCache (#62442)
4952cad5ebf is described below
commit 4952cad5ebf3a676775df558d7c87a1a411adbdc
Author: zhiqiang <se...@163.com>
AuthorDate: Thu Apr 16 20:55:22 2026 +0800
[improvement](be) Add stampede protection for AnnIndexIVFListCache (#62442)
## Summary
- Add double-check locking pattern to
`CachedRandomAccessReader::borrow()` to prevent concurrent threads from
redundantly reading the same IVF list data from disk (cache stampede)
- Eliminate ghost memory caused by LRU cache entry replacement under
high concurrency, reducing usage ratio fluctuations
- Zero overhead on the fast path (cache hit); reuses the existing
`_io_mutex` without introducing new synchronization primitives
## Proposed Changes
When multiple threads concurrently miss the `AnnIndexIVFListCache` for
the same key, they all independently read the same data from disk and
insert it into the cache. The LRU cache silently replaces duplicate
entries (counted as "stampede"), causing:
1. **Redundant disk I/O**: N concurrent misses produce N identical reads
instead of 1
2. **Ghost memory**: replaced entries whose handles are still pinned
consume memory not tracked by cache `_usage`, leading to usage ratio
fluctuations (observed 87%→50% under high concurrency)
3. **Lower cache hit ratio**: unnecessary evictions caused by inflated
insertion volume
The fix leverages the existing `_io_mutex` (required because CLucene
`IndexInput` is stateful) by moving its acquisition before the disk read
and adding a cache re-check after acquiring the lock. If a preceding
thread already loaded the same key, subsequent threads skip the disk I/O
entirely.
### What problem does this PR solve?
Problem Summary: Under high concurrency (e.g., vectordb_bench with 10-90
concurrent threads), the AnnIndexIVFListCache exhibits excessive
stampede events, redundant disk I/O, and usage ratio fluctuations due to
the TOCTOU gap between cache lookup and insert.
### Release note
Reduced redundant disk I/O and memory waste for IVF on-disk vector index
cache under concurrent queries by adding stampede protection
(double-check locking pattern) to CachedRandomAccessReader::borrow().
### Check List (For Author)
- Test: Manual test with vectordb_bench concurrency benchmark
- Behavior changed: No
- Does this need documentation: No
---
be/src/storage/index/ann/faiss_ann_index.cpp | 35 ++-
.../cache/ann_index_ivf_list_cache_test.cpp | 238 +++++++++++++++++++++
.../storage/index/ann/faiss_vector_index_test.cpp | 124 +++++++++++
3 files changed, 390 insertions(+), 7 deletions(-)
diff --git a/be/src/storage/index/ann/faiss_ann_index.cpp b/be/src/storage/index/ann/faiss_ann_index.cpp
index 0fad44c9d4d..330e7385a9c 100644
--- a/be/src/storage/index/ann/faiss_ann_index.cpp
+++ b/be/src/storage/index/ann/faiss_ann_index.cpp
@@ -300,6 +300,12 @@ public:
* Thread-safety: cache lookups / inserts are lock-free (the LRU cache is
* internally sharded). Disk reads are serialised by _io_mutex because
* the CLucene IndexInput is stateful (seek + readBytes).
+ *
+ * Stampede protection: when multiple threads concurrently miss the cache
+ * for the same key, borrow() acquires _io_mutex and re-checks the cache
+ * (double-check pattern). The first thread reads from disk and inserts
+ * into the cache; subsequent threads find the entry on re-check and skip
+ * the redundant disk I/O.
*/
struct CachedRandomAccessReader : faiss::RandomAccessReader {
CachedRandomAccessReader(lucene::store::IndexInput* input, std::string cache_key_prefix,
@@ -351,8 +357,25 @@ struct CachedRandomAccessReader : faiss::RandomAccessReader {
return _make_pinned_ref(std::move(handle), nbytes);
}
- // Slow path: cache miss — read from disk, then insert.
- auto page = _fetch_from_disk(offset, nbytes, cache->mem_tracker());
+ // Slow path: cache miss — acquire I/O lock, then double-check cache.
+ //
+ // Multiple threads may concurrently miss the fast-path lookup for the
+ // same key. Since _io_mutex already serialises all CLucene reads for
+ // this reader (IndexInput is stateful), we simply re-check the cache
+ // after acquiring the lock. If a preceding thread loaded this key
+ // while we were waiting, we get a cache hit and skip the redundant
+ // disk I/O entirely (stampede protection).
+ std::lock_guard<std::mutex> lock(_io_mutex);
+
+ // Double-check: a preceding thread may have loaded this key while
+ // we waited on _io_mutex.
+ if (cache->lookup(key, &handle)) {
+ ++g_ivf_on_disk_cache_stats.hit_cnt;
+ return _make_pinned_ref(std::move(handle), nbytes);
+ }
+
+ // Still a miss — we are the first thread to reach here; read from disk.
+ auto page = _fetch_from_disk_locked(offset, nbytes, cache->mem_tracker());
cache->insert(key, page.get(), &handle);
page.release(); // ownership transferred to cache
return _make_pinned_ref(std::move(handle), nbytes);
@@ -381,15 +404,13 @@ private:
// ---- Disk I/O + metrics ----
/// Read a region from CLucene, wrapped in a DataPage, and record fetch metrics.
- std::unique_ptr<DataPage> _fetch_from_disk(
+ /// Caller must already hold _io_mutex.
+ std::unique_ptr<DataPage> _fetch_from_disk_locked(
size_t offset, size_t nbytes, std::shared_ptr<MemTrackerLimiter> mem_tracker) const {
auto page = std::make_unique<DataPage>(nbytes, std::move(mem_tracker));
const int64_t start_ns = MonotonicNanos();
- {
- std::lock_guard<std::mutex> lock(_io_mutex);
- _read_clucene(offset, page->data(), nbytes);
- }
+ _read_clucene(offset, page->data(), nbytes);
const int64_t cost_ns = MonotonicNanos() - start_ns;
++g_ivf_on_disk_cache_stats.miss_cnt;
diff --git a/be/test/storage/cache/ann_index_ivf_list_cache_test.cpp b/be/test/storage/cache/ann_index_ivf_list_cache_test.cpp
new file mode 100644
index 00000000000..99c18fc534a
--- /dev/null
+++ b/be/test/storage/cache/ann_index_ivf_list_cache_test.cpp
@@ -0,0 +1,238 @@
+// 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 "storage/cache/ann_index_ivf_list_cache.h"
+
+#include <gtest/gtest-message.h>
+#include <gtest/gtest-test-part.h>
+
+#include <atomic>
+#include <barrier>
+#include <cstring>
+#include <thread>
+#include <vector>
+
+#include "gtest/gtest_pred_impl.h"
+
+namespace doris {
+
+static constexpr uint32_t kNumShards = AnnIndexIVFListCache::kDefaultNumShards;
+
+class AnnIndexIVFListCacheTest : public testing::Test {
+public:
+ AnnIndexIVFListCacheTest() {
+ mem_tracker = MemTrackerLimiter::create_shared(MemTrackerLimiter::Type::GLOBAL,
+ "AnnIndexIVFListCacheTest");
+ }
+
+protected:
+ void SetUp() override {
+ cache_ = std::make_unique<AnnIndexIVFListCache>(kNumShards * 1024 * 1024, kNumShards);
+ }
+
+ void TearDown() override { cache_.reset(); }
+
+ std::shared_ptr<MemTrackerLimiter> mem_tracker;
+ std::unique_ptr<AnnIndexIVFListCache> cache_;
+};
+
+TEST_F(AnnIndexIVFListCacheTest, basic_insert_and_lookup) {
+ AnnIndexIVFListCache::CacheKey key("test_file", 4096, 0);
+
+ PageCacheHandle handle;
+ EXPECT_FALSE(cache_->lookup(key, &handle));
+
+ auto* page = new DataPage(1024, mem_tracker);
+ std::memset(page->data(), 0xAB, 1024);
+
+ cache_->insert(key, page, &handle);
+ Slice data = handle.data();
+ EXPECT_EQ(data.data, page->data());
+
+ PageCacheHandle lookup_handle;
+ EXPECT_TRUE(cache_->lookup(key, &lookup_handle));
+ Slice lookup_data = lookup_handle.data();
+ EXPECT_EQ(static_cast<unsigned char>(lookup_data.data[0]), 0xAB);
+}
+
+TEST_F(AnnIndexIVFListCacheTest, cache_miss_different_key) {
+ AnnIndexIVFListCache::CacheKey key("file_a", 4096, 0);
+
+ auto* page = new DataPage(512, mem_tracker);
+ PageCacheHandle handle;
+ cache_->insert(key, page, &handle);
+
+ {
+ PageCacheHandle miss_handle;
+ AnnIndexIVFListCache::CacheKey miss_key("file_b", 4096, 0);
+ EXPECT_FALSE(cache_->lookup(miss_key, &miss_handle));
+ }
+
+ {
+ PageCacheHandle miss_handle;
+ AnnIndexIVFListCache::CacheKey miss_key("file_a", 8192, 0);
+ EXPECT_FALSE(cache_->lookup(miss_key, &miss_handle));
+ }
+
+ {
+ PageCacheHandle miss_handle;
+ AnnIndexIVFListCache::CacheKey miss_key("file_a", 4096, 100);
+ EXPECT_FALSE(cache_->lookup(miss_key, &miss_handle));
+ }
+}
+
+TEST_F(AnnIndexIVFListCacheTest, multiple_entries) {
+ constexpr int kCount = 32;
+ std::vector<PageCacheHandle> handles(kCount);
+ for (int i = 0; i < kCount; ++i) {
+ AnnIndexIVFListCache::CacheKey key("multi", 4096, i * 1024);
+ auto* page = new DataPage(256, mem_tracker);
+ std::memset(page->data(), static_cast<char>(i), 256);
+ cache_->insert(key, page, &handles[i]);
+ }
+
+ for (int i = 0; i < kCount; ++i) {
+ AnnIndexIVFListCache::CacheKey key("multi", 4096, i * 1024);
+ PageCacheHandle handle;
+ EXPECT_TRUE(cache_->lookup(key, &handle));
+ Slice data = handle.data();
+ EXPECT_EQ(static_cast<unsigned char>(data.data[0]), static_cast<unsigned char>(i));
+ }
+}
+
+// Simulates the stampede protection pattern from CachedRandomAccessReader::borrow().
+//
+// The test exercises the double-check locking path: N threads concurrently
+// miss the fast-path cache lookup for the same key; only the first thread
+// through the mutex performs the "disk I/O" (here: allocate + fill a DataPage);
+// the remaining N-1 threads find the entry on re-check and skip the I/O.
+TEST_F(AnnIndexIVFListCacheTest, stampede_protection) {
+ constexpr int kThreads = 8;
+ const AnnIndexIVFListCache::CacheKey key("stampede_file", 4096, 0);
+
+ std::atomic<int> io_count {0};
+ std::mutex io_mutex;
+ std::barrier sync_point(kThreads);
+
+ auto simulate_borrow = [&]() {
+ PageCacheHandle handle;
+ if (cache_->lookup(key, &handle)) {
+ return;
+ }
+
+ sync_point.arrive_and_wait();
+
+ std::lock_guard<std::mutex> lock(io_mutex);
+
+ if (cache_->lookup(key, &handle)) {
+ return;
+ }
+
+ auto* page = new DataPage(1024, mem_tracker);
+ std::memset(page->data(), 0xCD, 1024);
+ io_count.fetch_add(1, std::memory_order_relaxed);
+ cache_->insert(key, page, &handle);
+ };
+
+ std::vector<std::thread> threads;
+ threads.reserve(kThreads);
+ for (int i = 0; i < kThreads; ++i) {
+ threads.emplace_back(simulate_borrow);
+ }
+ for (auto& t : threads) {
+ t.join();
+ }
+
+ EXPECT_EQ(io_count.load(), 1);
+
+ PageCacheHandle verify_handle;
+ EXPECT_TRUE(cache_->lookup(key, &verify_handle));
+ Slice data = verify_handle.data();
+ EXPECT_EQ(static_cast<unsigned char>(data.data[0]), 0xCD);
+}
+
+// Variant: multiple distinct keys under contention. Each key should be
+// loaded exactly once even when many threads race on each key.
+TEST_F(AnnIndexIVFListCacheTest, stampede_protection_multiple_keys) {
+ constexpr int kKeys = 4;
+ constexpr int kThreadsPerKey = 4;
+ constexpr int kTotalThreads = kKeys * kThreadsPerKey;
+
+ std::atomic<int> io_counts[kKeys];
+ for (auto& c : io_counts) {
+ c.store(0);
+ }
+
+ std::mutex io_mutex;
+ std::barrier sync_point(kTotalThreads);
+
+ auto simulate_borrow = [&](int key_idx) {
+ AnnIndexIVFListCache::CacheKey key("multi_stampede", 4096, key_idx * 1024);
+
+ PageCacheHandle handle;
+ if (cache_->lookup(key, &handle)) {
+ return;
+ }
+
+ sync_point.arrive_and_wait();
+
+ std::lock_guard<std::mutex> lock(io_mutex);
+
+ if (cache_->lookup(key, &handle)) {
+ return;
+ }
+
+ auto* page = new DataPage(512, mem_tracker);
+ std::memset(page->data(), static_cast<char>(key_idx), 512);
+ io_counts[key_idx].fetch_add(1, std::memory_order_relaxed);
+ cache_->insert(key, page, &handle);
+ };
+
+ std::vector<std::thread> threads;
+ threads.reserve(kTotalThreads);
+ for (int k = 0; k < kKeys; ++k) {
+ for (int t = 0; t < kThreadsPerKey; ++t) {
+ threads.emplace_back(simulate_borrow, k);
+ }
+ }
+ for (auto& th : threads) {
+ th.join();
+ }
+
+ for (int k = 0; k < kKeys; ++k) {
+ EXPECT_EQ(io_counts[k].load(), 1) << "key_idx=" << k;
+
+ AnnIndexIVFListCache::CacheKey key("multi_stampede", 4096, k * 1024);
+ PageCacheHandle handle;
+ EXPECT_TRUE(cache_->lookup(key, &handle));
+ Slice data = handle.data();
+ EXPECT_EQ(static_cast<unsigned char>(data.data[0]), static_cast<unsigned char>(k));
+ }
+}
+
+TEST_F(AnnIndexIVFListCacheTest, singleton_lifecycle) {
+ EXPECT_EQ(AnnIndexIVFListCache::instance(), nullptr);
+
+ auto* inst = AnnIndexIVFListCache::create_global_cache(kNumShards * 2048, kNumShards);
+ EXPECT_NE(inst, nullptr);
+ EXPECT_EQ(AnnIndexIVFListCache::instance(), inst);
+
+ AnnIndexIVFListCache::destroy_global_cache();
+ EXPECT_EQ(AnnIndexIVFListCache::instance(), nullptr);
+}
+
+} // namespace doris
diff --git a/be/test/storage/index/ann/faiss_vector_index_test.cpp b/be/test/storage/index/ann/faiss_vector_index_test.cpp
index d9a61adcaeb..60c89951cb5 100644
--- a/be/test/storage/index/ann/faiss_vector_index_test.cpp
+++ b/be/test/storage/index/ann/faiss_vector_index_test.cpp
@@ -22,6 +22,7 @@
#include <algorithm>
#include <atomic>
+#include <barrier>
#include <chrono>
#include <cstddef>
#include <limits>
@@ -37,6 +38,7 @@
#include "storage/index/ann/ann_search_params.h"
#include "storage/index/ann/faiss_ann_index.h"
// metrics.h not used directly here
+#include "storage/cache/ann_index_ivf_list_cache.h"
#include "storage/index/ann/vector_search_utils.h"
#include "util/defer_op.h"
@@ -1415,4 +1417,126 @@ TEST_F(VectorSearchTest, InnerProductRangeSearchZeroAndNegativeRadius) {
ASSERT_GE(res_gen.roaring->cardinality(), static_cast<size_t>(n * 0.9));
}
+TEST_F(VectorSearchTest, IVFOnDiskSaveLoadAndSearch) {
+ AnnIndexIVFListCache::create_global_cache(64 * 1024 * 1024);
+ Defer destroy_cache([] { AnnIndexIVFListCache::destroy_global_cache(); });
+
+ auto index1 = std::make_unique<FaissVectorIndex>();
+ FaissBuildParameter params;
+ params.dim = 32;
+ params.ivf_nlist = 4;
+ params.quantizer = FaissBuildParameter::Quantizer::FLAT;
+ params.index_type = FaissBuildParameter::IndexType::IVF_ON_DISK;
+ index1->build(params);
+
+ const int num_vectors = 200;
+ std::vector<float> vectors;
+ vectors.reserve(static_cast<size_t>(num_vectors) * params.dim);
+ for (int i = 0; i < num_vectors; i++) {
+ auto tmp = vector_search_utils::generate_random_vector(params.dim);
+ vectors.insert(vectors.end(), tmp.begin(), tmp.end());
+ }
+ ASSERT_TRUE(index1->train(num_vectors, vectors.data()).ok());
+ ASSERT_TRUE(index1->add(num_vectors, vectors.data()).ok());
+
+ auto dir = std::make_shared<lucene::store::RAMDirectory>();
+ ASSERT_TRUE(index1->save(dir.get()).ok());
+
+ auto index2 = std::make_unique<FaissVectorIndex>();
+ index2->set_type(AnnIndexType::IVF_ON_DISK);
+ index2->set_ivfdata_cache_key_prefix("ut_stampede_test");
+ ASSERT_TRUE(index2->load(dir.get()).ok());
+
+ auto query_vec = vector_search_utils::generate_random_vector(params.dim);
+ IVFSearchParameters search_params;
+ search_params.nprobe = 4;
+ auto roaring = std::make_unique<roaring::Roaring>();
+ for (int i = 0; i < num_vectors; ++i) roaring->add(i);
+ search_params.roaring = roaring.get();
+ search_params.rows_of_segment = num_vectors;
+
+ IndexSearchResult result;
+ ASSERT_TRUE(index2->ann_topn_search(query_vec.data(), 10, search_params, result).ok());
+ EXPECT_GT(result.roaring->cardinality(), 0u);
+ EXPECT_GT(result.ivf_on_disk_cache_miss_cnt, 0);
+}
+
+// All threads share a single FaissVectorIndex (and thus a single
+// CachedRandomAccessReader with its _io_mutex). On the first round
+// (cold cache) threads contend on the same _io_mutex; the first thread
+// through loads from "disk" while the rest hit the double-check cache
+// lookup path (lines 372-375 in faiss_ann_index.cpp).
+TEST_F(VectorSearchTest, IVFOnDiskConcurrentSearchStampedeProtection) {
+ AnnIndexIVFListCache::create_global_cache(64 * 1024 * 1024);
+ Defer destroy_cache([] { AnnIndexIVFListCache::destroy_global_cache(); });
+
+ auto index_builder = std::make_unique<FaissVectorIndex>();
+ FaissBuildParameter params;
+ params.dim = 32;
+ params.ivf_nlist = 4;
+ params.quantizer = FaissBuildParameter::Quantizer::FLAT;
+ params.index_type = FaissBuildParameter::IndexType::IVF_ON_DISK;
+ index_builder->build(params);
+
+ const int num_vectors = 200;
+ std::vector<float> vectors;
+ vectors.reserve(static_cast<size_t>(num_vectors) * params.dim);
+ for (int i = 0; i < num_vectors; i++) {
+ auto tmp = vector_search_utils::generate_random_vector(params.dim);
+ vectors.insert(vectors.end(), tmp.begin(), tmp.end());
+ }
+ ASSERT_TRUE(index_builder->train(num_vectors, vectors.data()).ok());
+ ASSERT_TRUE(index_builder->add(num_vectors, vectors.data()).ok());
+
+ auto dir = std::make_shared<lucene::store::RAMDirectory>();
+ ASSERT_TRUE(index_builder->save(dir.get()).ok());
+
+ auto shared_index = std::make_shared<FaissVectorIndex>();
+ shared_index->set_type(AnnIndexType::IVF_ON_DISK);
+ shared_index->set_ivfdata_cache_key_prefix("ut_stampede_shared");
+ ASSERT_TRUE(shared_index->load(dir.get()).ok());
+
+ constexpr int kThreads = 8;
+ auto query_vec = vector_search_utils::generate_random_vector(params.dim);
+
+ std::barrier sync_point(kThreads);
+ std::vector<IndexSearchResult> results(kThreads);
+ std::vector<Status> statuses(kThreads);
+
+ auto search_fn = [&](int tid) {
+ IVFSearchParameters search_params;
+ search_params.nprobe = 4;
+ auto thread_roaring = std::make_unique<roaring::Roaring>();
+ for (int i = 0; i < num_vectors; ++i) thread_roaring->add(i);
+ search_params.roaring = thread_roaring.get();
+ search_params.rows_of_segment = num_vectors;
+
+ sync_point.arrive_and_wait();
+
+ statuses[tid] =
+ shared_index->ann_topn_search(query_vec.data(), 10, search_params, results[tid]);
+ };
+
+ std::vector<std::thread> threads;
+ threads.reserve(kThreads);
+ for (int i = 0; i < kThreads; ++i) {
+ threads.emplace_back(search_fn, i);
+ }
+ for (auto& t : threads) {
+ t.join();
+ }
+
+ int64_t total_hits = 0;
+ int64_t total_misses = 0;
+ for (int i = 0; i < kThreads; ++i) {
+ ASSERT_TRUE(statuses[i].ok()) << "Thread " << i << ": " << statuses[i].to_string();
+ EXPECT_GT(results[i].roaring->cardinality(), 0u) << "Thread " << i;
+ total_hits += results[i].ivf_on_disk_cache_hit_cnt;
+ total_misses += results[i].ivf_on_disk_cache_miss_cnt;
+ }
+
+ EXPECT_GT(total_hits, 0) << "Expected cache hits from stampede double-check path";
+ EXPECT_GT(total_misses, 0) << "Expected cache misses from first-thread disk reads";
+}
+
} // namespace doris
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org