Yuxu Ge
Article · 2026-02-26

Concurrent Lock Policies in Index Merging

In a search engine, the merge process runs continuously in the background. When merge completes, old index segments must be replaced with a new, unified segment. This switching operation seems straightforward but presents a sharp concurrency challenge: without locking, readers may see inconsistent data or encounter prematurely deleted files; with coarse, long-held locks, queries stall.

The solution hinges on choosing when to lock. We examine two strategies—OnStart (pessimistic) and OnSwitch (optimistic)—then implement a working OnSwitch approach in Modern C++ (C++20).

The Strategy Game: OnStart vs. OnSwitch

When designing merge locks, two main choices present themselves:

  1. OnStart Policy (Pessimistic Lock):

    • Acquire the lock at the very beginning of the merge task to prevent other processes from modifying these segments.
    • Pros: Simple implementation, high safety.
    • Cons: Extremely low concurrency. Merging is time-consuming (potentially minutes), and holding a lock this long blocks all structural changes.

  2. OnSwitch Policy (Optimistic/Late Lock):

    • Do not hold a lock for the majority of the merge time (reading old segments, writing new ones to a temporary directory).
    • Acquire the write lock only at the very last moment to "flip" the pointers.
    • Pros: Drastically reduces critical section time, with almost zero impact on queries.
    • Cons: Complex implementation. What if an old segment was deleted by another task during the merge? Requires complex reference counting or version checking mechanisms.

Modern C++ Implementation: RAII and Late-Locking

We will use C++20's std::shared_mutex to simulate a reader-writer lock and demonstrate how to implement a safe OnSwitch logic.

#include <iostream>
#include <vector>
#include <string>
#include <thread>
#include <mutex>
#include <shared_mutex>
#include <chrono>
#include <atomic>
#include <memory>

// Simulate an index segment
struct Segment {
    std::string id;
    size_t doc_count;
};

// Core state of the search system
class SearchIndex {
    std::vector<Segment> active_segments;
    mutable std::shared_mutex index_mutex; // Reader-Writer lock

public:
    SearchIndex() {
        active_segments = {{"seg_1", 100}, {"seg_2", 200}};
    }

    // Simulate query operation (Reader): Requires shared lock
    void search(const std::string& query) const {
        std::shared_lock lock(index_mutex);
        std::cout << "[Query] Searching for '" << query << "' in segments: ";
        for (const auto& seg : active_segments) {
            std::cout << seg.id << " ";
        }
        std::cout << std::endl;
        // Simulate query latency
        std::this_thread::sleep_for(std::chrono::milliseconds(50));
    }

    // Get a snapshot of current segments (preparation for merge)
    std::vector<Segment> get_segments_snapshot() const {
        std::shared_lock lock(index_mutex);
        return active_segments;
    }

    // Key: Atomic Switch (OnSwitch Policy)
    // Acquire exclusive lock only at this final step
    bool apply_merge_result(const std::vector<std::string>& old_ids, const Segment& new_merged_segment) {
        std::unique_lock lock(index_mutex); // Acquire write lock

        // Double-Check:
        // Ensure old segments still exist and haven't been deleted by other threads
        for (const auto& old_id : old_ids) {
            bool found = false;
            for (const auto& seg : active_segments) {
                if (seg.id == old_id) {
                    found = true;
                    break;
                }
            }
            if (!found) {
                std::cerr << "[Merge] Failed! Target segments disappeared." << std::endl;
                return false;
            }
        }

        // Execute Swap: Remove old segments, add new segment
        std::cout << "[Merge] Critical Section: Swapping segments..." << std::endl;
        auto it = active_segments.begin();
        while (it != active_segments.end()) {
            bool is_old = false;
            for (const auto& old_id : old_ids) {
                if (it->id == old_id) {
                    is_old = true;
                    break;
                }
            }
            if (is_old) {
                it = active_segments.erase(it);
            } else {
                ++it;
            }
        }
        active_segments.push_back(new_merged_segment);
        return true;
    }
};

// Simulate background merge task
void background_merge_task(SearchIndex& index) {
    // 1. Preparation Phase (No lock or short lock)
    auto snapshot = index.get_segments_snapshot();
    std::vector<std::string> target_ids;
    for (const auto& seg : snapshot) target_ids.push_back(seg.id);

    std::cout << "[Merge] Background merging started for " << target_ids.size() << " segments..." << std::endl;
    
    // Simulate expensive merge calculation (Holding NO locks!)
    std::this_thread::sleep_for(std::chrono::milliseconds(200)); 
    Segment new_seg{"seg_merged_v1", 300};

    // 2. Switch Phase (OnSwitch - Short Write Lock)
    if (index.apply_merge_result(target_ids, new_seg)) {
        std::cout << "[Merge] Success! Index updated." << std::endl;
    }
}

int main() {
    SearchIndex index;

    // Start background merge thread
    std::jthread merger(background_merge_task, std::ref(index));

    // Simulate foreground high-concurrency queries
    for (int i = 0; i < 5; ++i) {
        index.search("user_query_" + std::to_string(i));
        std::this_thread::sleep_for(std::chrono::milliseconds(60));
    }

    return 0;
}

Code Walkthrough

This C++ example demonstrates the essence of the OnSwitch policy:

  1. Lock-Free Calculation: The majority of the time in background_merge_task (the simulated sleep_for) is spent without holding any locks. Query threads (search) run unimpeded while the merge progresses.
  2. Atomic Switch: apply_merge_result uses std::unique_lock. This is the only place in the entire process that blocks readers, but the operations are extremely fast (in-memory vector manipulation), typically in the microsecond range.
  3. Safety Check: After acquiring the write lock, we must verify the state again ("Double-Check"). During the lock-free computation period, the outside world may have changed (e.g., an admin deleted an old index).

Conclusion

In high-concurrency systems, locking is fundamentally a concurrency trade-off. The OnSwitch (Late-Locking) policy drastically improves system concurrency by minimizing the scope of critical sections.

Although implementing it is more complex than a global lock—you must handle state invalidation and version conflicts—in search systems demanding ultra-low latency, this complexity is justified. Modern C++'s shared_mutex and RAII patterns enable these synchronization semantics to be expressed cleanly and safely.

© 2026 Yuxu Ge ·