Bug: Integer underflow in Index::size() during concurrent add/remove.

[knowack1]

Describe the bug

When performing concurrent add and remove operations, the Index::size() method can return an extremely large value (e.g., 18446744073709551614).
This occurs because the underlying C++ implementation calculates size as: return typed_->size() - free_keys_.size();.
Under high concurrency, it is possible for the free_keys_ size to be larger than the typed_ size, causing a std::size_t underflow.

Debugging reveals the following state during the crash:

• typed_->size(): 88
• free_keys_.size(): 91
• Result: 88 - 91 = -3 -> 18446744073709551613 (approx).

Steps to reproduce

This issue was reproduced using the Rust bindings with the tokio multi-threaded runtime. Note that even when using index.read() (assuming internal thread-safety of usearch), the inconsistency between the two internal counters is exposed.

#[tokio::test(flavor = "multi_thread")]
async fn test_concurrent_usearch_add_remove_size() {
    let options = IndexOptions {
        dimensions: 3,
        ..Default::default()
    };

    let index = Arc::new(RwLock::new(
        usearch::Index::new(&options).expect("failed to create index"),
    ));

    const VECTORS: usize = 50;
    let threads = tokio::runtime::Handle::current().metrics().num_workers();

    index.write().unwrap().reserve(VECTORS * 10).expect("failed to reserve");

    let mut handles = vec![];

    for _ in 0..threads {
        let idx = Arc::clone(&index);
        // Task 1: Concurrent Adds
        handles.push(tokio::spawn(async move {
            for i in 0..VECTORS {
                let _ = idx.read().unwrap().add(i as u64, &[i as f32; 3]);
            }
        }));

        // Task 2: Concurrent Removes
        let idx = Arc::clone(&index);
        handles.push(tokio::spawn(async move {
            for i in 0..VECTORS {
                let _ = idx.read().unwrap().remove(i as u64);
            }
        }));

        // Task 3: Monitor Size
        let idx = Arc::clone(&index);
        handles.push(tokio::spawn(async move {
            for _ in 0..VECTORS * 10 {
                let size = idx.read().unwrap().size();
                assert!(size <= VECTORS * threads, "Underflow detected! Size: {}", size);
                tokio::task::yield_now().await;
            }
        }));
    }

    for handle in handles {
        handle.await.expect("Task failed");
    }
}

Expected behavior

Index::size() to always return valid number of vectors inside the index.

USearch version

2.23.0

Operating System

Fedora release 42 (Adams)

Hardware architecture

x86

Which interface are you using?

Other bindings

Contact Details

No response

Are you open to being tagged as a contributor?

• I am open to being mentioned in the project .git history as a contributor

Is there an existing issue for this?

• I have searched the existing issues

Code of Conduct

• I agree to follow this project's Code of Conduct

[ashvardanian]

Hi @knowack1! Concurrent removals are heavily discouraged in USearch v2 - it's one of my design mistakes - exposing an API for this. You can either, concurrently insert, concurrently search, or do other operations - but not mix these 3 families of operations. The v3 will do this differently.

[knowack1]

Hi @knowack1! Concurrent removals are heavily discouraged in USearch v2 - it's one of my design mistakes - exposing an API for this. You can either, concurrently insert, concurrently search, or do other operations - but not mix these 3 families of operations. The v3 will do this differently.

@ashvardanian thanks for the quick response! In that case, we likely need to refactor how we handle removals/replacements in our code: https://github.com/scylladb/vector-store/blob/master/crates/vector-store/src/index/usearch.rs

[swasik]

The v3 will do this differently.

@ashvardanian do you have any ETA for v3?

[ashvardanian]

Don't want to promise an ETA just yet. I need to release the complete rewrite of SimSIMD first (planned for next week) to continue work on USearch v3. It's already ~100'000 lines of new code and has been accumulating since 2024. It will have a profound impact on the v3 design and will help unlock a new level of speeds & scale.

[knowack1]

It looks like the problem exists even when removals are handled via exclusive locks. The primary factor in reproducing this behavior is performing concurrent adds on the same key:

    #[tokio::test(flavor = "multi_thread")]
    async fn test_concurrent_usearch_add_remove_size() {
        let options = IndexOptions {
            dimensions: 3,
            ..Default::default()
        };

        let index = Arc::new(RwLock::new(
            usearch::Index::new(&options).expect("failed to create index"),
        ));

        const VECTORS: usize = 50;
        let threads = tokio::runtime::Handle::current().metrics().num_workers();

        index
            .write()
            .unwrap()
            .reserve(VECTORS * 10)
            .expect("failed to reserve");

        let mut handles = vec![];
        const KEY: u64 = 1;

        for _ in 0..threads {
            let idx = Arc::clone(&index);
            // Task 1: Concurrent Adds
            handles.push(tokio::spawn(async move {
                let _ = idx.read().unwrap().add(KEY, &[1 as f32; 3]);
            }));

            // Task 2: Concurrent Removes
            let idx = Arc::clone(&index);
            handles.push(tokio::spawn(async move {
                let _ = idx.write().unwrap().remove(KEY);
            }));

            // Task 3: Monitor Size
            let idx = Arc::clone(&index);
            handles.push(tokio::spawn(async move {
                loop {
                    let size = idx.write().unwrap().size();
                    println!("Current size: {}", size);
                    assert!(
                        size <= VECTORS * threads,
                        "Underflow detected! Size: {}",
                        size
                    );
                    tokio::task::yield_now().await;
                }
            }));
        }

        for handle in handles {
            handle.await.expect("Task failed");
        }
    }
}

This isn't a particularly 'interesting' use case, but it is what is happening in our production code.