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