The Search-Insert-Delete Problem

The Search-Insert-Delete Problem extends the classic Readers-Writers problem with three different access patterns instead of two. It demonstrates how to coordinate multiple operation types with different compatibility requirements - a common challenge in database systems and data structures.

The Scenario

Three types of goroutines access a shared list:

Searchers - Read the list without modifying it
Inserters - Add new elements to the list
Deleters - Remove elements from the list

Compatibility rules:

✓ Searchers can work concurrently with each other
✓ Searchers can work concurrently with Inserters
✗ Inserters cannot work with other Inserters (may corrupt structure)
✗ Deleters need exclusive access (no Searchers, Inserters, or other Deleters)

The Challenge: Three-Way Coordination

This is more nuanced than readers-writers:

Not symmetric like readers-writers!

Readers-Writers: Read||Read, Write needs exclusive
This problem: Search||Search||Insert, but Insert needs partial exclusive

Real-World Applications

This pattern models many systems:

Database indexes: Search concurrent, insert serialized, delete exclusive
B-trees: Reads concurrent, inserts locked at node level, deletes exclusive
Hash tables: Lookups parallel, inserts may conflict, deletes need exclusion
File systems: Directory listing || file create, but file delete exclusive
Caches: Get concurrent, put may conflict, evict needs exclusive

Access Pattern Visualization

stateDiagram-v2 [*] --> Idle Idle --> Searching: Searcher arrives Idle --> Inserting: Inserter arrives (no other inserters) Idle --> Deleting: Deleter arrives Searching --> Searching: Another searcher Searching --> SearchingWithInserter: Inserter arrives Searching --> Searching: Searcher leaves Searching --> Idle: Last searcher leaves SearchingWithInserter --> SearchingWithInserter: Searcher arrives/leaves SearchingWithInserter --> Searching: Inserter finishes SearchingWithInserter --> Idle: All finish Inserting --> Idle: Inserter finishes Deleting --> Idle: Deleter finishes note right of Searching Multiple searchers OK Inserters can join end note note right of Inserting Only ONE inserter No searchers end note note right of Deleting Complete exclusion Nobody else allowed end note

Implementation in Go

package main

import (
	"fmt"
	"math/rand"
	"sync"
	"sync/atomic"
	"time"
)

type DataStore struct {
	data            []int
	activeSearchers int32
	activeInserters int32
	activeDeleters  int32

	// Synchronization
	mu              sync.Mutex
	canSearch       *sync.Cond
	canInsert       *sync.Cond
	canDelete       *sync.Cond

	// Statistics
	totalSearches atomic.Int64
	totalInserts  atomic.Int64
	totalDeletes  atomic.Int64
}

func NewDataStore() *DataStore {
	ds := &DataStore{
		data: make([]int, 0),
	}
	ds.canSearch = sync.NewCond(&ds.mu)
	ds.canInsert = sync.NewCond(&ds.mu)
	ds.canDelete = sync.NewCond(&ds.mu)
	return ds
}

// Search performs a read operation (compatible with other searches and inserts)
func (ds *DataStore) Search(id, target int) bool {
	// Request search access
	ds.mu.Lock()
	for !ds.canSearchNow() {
		ds.canSearch.Wait()
	}

	atomic.AddInt32(&ds.activeSearchers, 1)
	searchers := atomic.LoadInt32(&ds.activeSearchers)
	inserters := atomic.LoadInt32(&ds.activeInserters)

	fmt.Printf("🔍 [Searcher %d] Started (active: %d searchers, %d inserters) - looking for %d\n",
		id, searchers, inserters, target)

	ds.mu.Unlock()

	// Perform search (outside critical section)
	time.Sleep(time.Duration(50+rand.Intn(100)) * time.Millisecond)

	found := false
	ds.mu.Lock()
	for _, v := range ds.data {
		if v == target {
			found = true
			break
		}
	}
	ds.mu.Unlock()

	// Release search access
	ds.mu.Lock()
	atomic.AddInt32(&ds.activeSearchers, -1)
	ds.totalSearches.Add(1)

	fmt.Printf("🔍 [Searcher %d] Done (found: %v)\n", id, found)

	// Wake up waiting operations
	ds.canInsert.Broadcast()
	ds.canDelete.Broadcast()
	ds.mu.Unlock()

	return found
}

// Insert adds an element (compatible with searches, not with other inserts)
func (ds *DataStore) Insert(id, value int) {
	// Request insert access
	ds.mu.Lock()
	for !ds.canInsertNow() {
		ds.canInsert.Wait()
	}

	atomic.AddInt32(&ds.activeInserters, 1)
	searchers := atomic.LoadInt32(&ds.activeSearchers)

	fmt.Printf("➕ [Inserter %d] Started (active: %d searchers) - inserting %d\n",
		id, searchers, value)

	// Perform insertion
	ds.data = append(ds.data, value)
	time.Sleep(time.Duration(100+rand.Intn(150)) * time.Millisecond)

	atomic.AddInt32(&ds.activeInserters, -1)
	ds.totalInserts.Add(1)

	fmt.Printf("➕ [Inserter %d] Done (data size: %d)\n", id, len(ds.data))

	// Wake up waiting operations
	ds.canInsert.Broadcast()
	ds.canDelete.Broadcast()
	ds.mu.Unlock()
}

// Delete removes an element (needs exclusive access)
func (ds *DataStore) Delete(id, value int) bool {
	// Request delete access
	ds.mu.Lock()
	for !ds.canDeleteNow() {
		ds.canDelete.Wait()
	}

	atomic.AddInt32(&ds.activeDeleters, 1)

	fmt.Printf("🗑️  [Deleter %d] Started (exclusive access) - deleting %d\n", id, value)

	// Perform deletion
	deleted := false
	for i, v := range ds.data {
		if v == value {
			ds.data = append(ds.data[:i], ds.data[i+1:]...)
			deleted = true
			break
		}
	}

	time.Sleep(time.Duration(150+rand.Intn(200)) * time.Millisecond)

	atomic.AddInt32(&ds.activeDeleters, -1)
	ds.totalDeletes.Add(1)

	fmt.Printf("🗑️  [Deleter %d] Done (deleted: %v, data size: %d)\n",
		id, deleted, len(ds.data))

	// Wake up all waiting operations
	ds.canSearch.Broadcast()
	ds.canInsert.Broadcast()
	ds.canDelete.Broadcast()
	ds.mu.Unlock()

	return deleted
}

// Compatibility checks
func (ds *DataStore) canSearchNow() bool {
	// No deletes in progress
	return atomic.LoadInt32(&ds.activeDeleters) == 0
}

func (ds *DataStore) canInsertNow() bool {
	// No deletes and no other inserts
	return atomic.LoadInt32(&ds.activeDeleters) == 0 &&
		atomic.LoadInt32(&ds.activeInserters) == 0
}

func (ds *DataStore) canDeleteNow() bool {
	// Complete exclusion - nobody else active
	return atomic.LoadInt32(&ds.activeSearchers) == 0 &&
		atomic.LoadInt32(&ds.activeInserters) == 0 &&
		atomic.LoadInt32(&ds.activeDeleters) == 0
}

// Stats prints statistics
func (ds *DataStore) Stats() {
	ds.mu.Lock()
	defer ds.mu.Unlock()

	fmt.Println("\n📊 Data Store Statistics:")
	fmt.Printf("   Final data size:   %d\n", len(ds.data))
	fmt.Printf("   Total searches:    %d\n", ds.totalSearches.Load())
	fmt.Printf("   Total inserts:     %d\n", ds.totalInserts.Load())
	fmt.Printf("   Total deletes:     %d\n", ds.totalDeletes.Load())
	fmt.Printf("   Operations:        %d\n",
		ds.totalSearches.Load()+ds.totalInserts.Load()+ds.totalDeletes.Load())
}

func main() {
	fmt.Println("=== The Search-Insert-Delete Problem ===")
	fmt.Println("Three-way access coordination\n")

	const (
		numSearchers = 6
		numInserters = 4
		numDeleters  = 2
	)

	store := NewDataStore()

	var wg sync.WaitGroup

	// Searchers
	for i := 0; i < numSearchers; i++ {
		wg.Add(1)
		go func(id int) {
			defer wg.Done()
			time.Sleep(time.Duration(id*50) * time.Millisecond)
			target := rand.Intn(10)
			store.Search(id, target)
		}(i)
	}

	// Inserters
	for i := 0; i < numInserters; i++ {
		wg.Add(1)
		go func(id int) {
			defer wg.Done()
			time.Sleep(time.Duration(id*50) * time.Millisecond)
			value := rand.Intn(100)
			store.Insert(id, value)
		}(i)
	}

	// Deleters
	for i := 0; i < numDeleters; i++ {
		wg.Add(1)
		go func(id int) {
			defer wg.Done()
			time.Sleep(time.Duration(id*100) * time.Millisecond)
			value := rand.Intn(10)
			store.Delete(id, value)
		}(i)
	}

	wg.Wait()

	store.Stats()
	fmt.Println("\n✓ Simulation complete!")
}

How It Works

1. Three Condition Variables

canSearch *sync.Cond  // Searchers wait here
canInsert *sync.Cond  // Inserters wait here
canDelete *sync.Cond  // Deleters wait here

Each operation type has its own condition variable for fine-grained control.

2. Compatibility Matrix

func canSearchNow() bool {
    return activeDeleters == 0  // Only conflicts with deletes
}

func canInsertNow() bool {
    return activeDeleters == 0 && activeInserters == 0
    // Conflicts with deletes and other inserts
}

func canDeleteNow() bool {
    return activeSearchers == 0 && activeInserters == 0 && activeDeleters == 0
    // Needs complete exclusion
}

Asymmetric compatibility rules encoded in predicates.

3. Wait-Acquire-Release Pattern

// Acquire
mu.Lock()
for !canProceedNow() {
    condition.Wait()
}
activeCount++
mu.Unlock()

// Critical section
doWork()

// Release
mu.Lock()
activeCount--
wakeUpWaiters()
mu.Unlock()

Standard monitor pattern with condition variables.

Advanced: Priority-Based Access

Let’s add priorities to prevent starvation:

package main

import (
	"fmt"
	"sync"
	"sync/atomic"
	"time"
)

type PriorityStore struct {
	data []int

	activeSearchers int32
	activeInserters int32
	activeDeleters  int32

	waitingSearchers int32
	waitingInserters int32
	waitingDeleters  int32

	mu        sync.Mutex
	condition *sync.Cond

	// Priority: Deleters > Inserters > Searchers
}

func NewPriorityStore() *PriorityStore {
	ps := &PriorityStore{
		data: make([]int, 0),
	}
	ps.condition = sync.NewCond(&ps.mu)
	return ps
}

func (ps *PriorityStore) Search(id, target int) {
	ps.mu.Lock()
	atomic.AddInt32(&ps.waitingSearchers, 1)

	// Wait with priority awareness
	for !ps.canSearchWithPriority() {
		ps.condition.Wait()
	}

	atomic.AddInt32(&ps.waitingSearchers, -1)
	atomic.AddInt32(&ps.activeSearchers, 1)

	fmt.Printf("🔍 [Searcher %d] Searching (waiters: S:%d I:%d D:%d)\n",
		id, atomic.LoadInt32(&ps.waitingSearchers),
		atomic.LoadInt32(&ps.waitingInserters),
		atomic.LoadInt32(&ps.waitingDeleters))

	ps.mu.Unlock()

	// Search
	time.Sleep(50 * time.Millisecond)

	ps.mu.Lock()
	atomic.AddInt32(&ps.activeSearchers, -1)
	ps.condition.Broadcast()
	ps.mu.Unlock()
}

func (ps *PriorityStore) Insert(id, value int) {
	ps.mu.Lock()
	atomic.AddInt32(&ps.waitingInserters, 1)

	// Wait with priority awareness
	for !ps.canInsertWithPriority() {
		ps.condition.Wait()
	}

	atomic.AddInt32(&ps.waitingInserters, -1)
	atomic.AddInt32(&ps.activeInserters, 1)

	fmt.Printf("➕ [Inserter %d] Inserting (waiters: S:%d I:%d D:%d)\n",
		id, atomic.LoadInt32(&ps.waitingSearchers),
		atomic.LoadInt32(&ps.waitingInserters),
		atomic.LoadInt32(&ps.waitingDeleters))

	ps.data = append(ps.data, value)
	ps.mu.Unlock()

	// Insert
	time.Sleep(100 * time.Millisecond)

	ps.mu.Lock()
	atomic.AddInt32(&ps.activeInserters, -1)
	ps.condition.Broadcast()
	ps.mu.Unlock()
}

func (ps *PriorityStore) Delete(id, value int) {
	ps.mu.Lock()
	atomic.AddInt32(&ps.waitingDeleters, 1)

	// Wait with priority awareness
	for !ps.canDeleteWithPriority() {
		ps.condition.Wait()
	}

	atomic.AddInt32(&ps.waitingDeleters, -1)
	atomic.AddInt32(&ps.activeDeleters, 1)

	fmt.Printf("🗑️  [Deleter %d] Deleting (PRIORITY - exclusive access)\n", id)

	// Delete
	for i, v := range ps.data {
		if v == value {
			ps.data = append(ps.data[:i], ps.data[i+1:]...)
			break
		}
	}

	ps.mu.Unlock()

	time.Sleep(150 * time.Millisecond)

	ps.mu.Lock()
	atomic.AddInt32(&ps.activeDeleters, -1)
	ps.condition.Broadcast()
	ps.mu.Unlock()
}

// Priority-aware compatibility checks
func (ps *PriorityStore) canSearchWithPriority() bool {
	// Can't search if deleter waiting (higher priority)
	if atomic.LoadInt32(&ps.waitingDeleters) > 0 {
		return false
	}

	// Can't search if deleter active
	return atomic.LoadInt32(&ps.activeDeleters) == 0
}

func (ps *PriorityStore) canInsertWithPriority() bool {
	// Can't insert if deleter waiting (higher priority)
	if atomic.LoadInt32(&ps.waitingDeleters) > 0 {
		return false
	}

	// Normal insert rules
	return atomic.LoadInt32(&ps.activeDeleters) == 0 &&
		atomic.LoadInt32(&ps.activeInserters) == 0
}

func (ps *PriorityStore) canDeleteWithPriority() bool {
	// Highest priority - just needs exclusive access
	return atomic.LoadInt32(&ps.activeSearchers) == 0 &&
		atomic.LoadInt32(&ps.activeInserters) == 0 &&
		atomic.LoadInt32(&ps.activeDeleters) == 0
}

func RunPriorityStore() {
	fmt.Println("\n=== Priority-Based Access ===\n")

	store := NewPriorityStore()

	var wg sync.WaitGroup

	// Many searchers and inserters
	for i := 0; i < 8; i++ {
		wg.Add(1)
		go func(id int) {
			defer wg.Done()
			store.Search(id, 42)
		}(i)

		wg.Add(1)
		go func(id int) {
			defer wg.Done()
			store.Insert(id, id*10)
		}(i)
	}

	// One high-priority deleter
	time.Sleep(100 * time.Millisecond)
	wg.Add(1)
	go func() {
		defer wg.Done()
		store.Delete(0, 42)
	}()

	wg.Wait()
	fmt.Println("\n✓ Priority demonstration complete!")
}

func main() {
	RunPriorityStore()
}

Comparison with Readers-Writers

Aspect	Readers-Writers	Search-Insert-Delete
Operation types	2 (Read, Write)	3 (Search, Insert, Delete)
Read compatibility	All readers concurrent	Searchers concurrent
Write compatibility	Exclusive	Insert = partial, Delete = exclusive
Symmetry	Symmetric	Asymmetric
Complexity	Simple	More nuanced

The extra operation type creates intermediate compatibility.

Access Patterns Visualization

gantt title Operation Timeline (Demonstrating Compatibility) dateFormat ss axisFormat %S section Searchers Search 1 :s1, 00, 3s Search 2 :s2, 01, 3s Search 3 :s3, 02, 2s section Inserters Insert 1 :i1, 02, 2s Insert 2 :i2, 05, 2s section Deleters Delete 1 :d1, 04, 1s Delete 2 :d2, 07, 1s

Notice:

Searchers overlap with each other
Inserters are serialized
Deleters run exclusively

Key Go Patterns

1. Multiple Condition Variables

canSearch := sync.NewCond(&mu)
canInsert := sync.NewCond(&mu)
canDelete := sync.NewCond(&mu)

// Wake up specific type
canSearch.Broadcast()  // Only searchers wake up

2. Atomic Counters for Active Operations

var activeSearchers int32
atomic.AddInt32(&activeSearchers, 1)
count := atomic.LoadInt32(&activeSearchers)

Safe concurrent reads without holding lock!

3. Predicate-Based Waiting

for !canProceedNow() {
    condition.Wait()
}

Loop handles spurious wakeups and state changes.

Performance Considerations

Contention Analysis

High search load:

Searches mostly concurrent
Good throughput

High insert load:

Inserts serialized
Bottleneck appears

High delete load:

Deletes block everything
Severe bottleneck

Optimization Strategies

Batch deletes - Collect multiple deletions
Lazy deletion - Mark as deleted, clean up later
Partition data - Reduce contention on separate partitions
Read-copy-update - Copy-on-write for reads

Variations

1. Read-Copy-Update (RCU)

type RCUStore struct {
    data atomic.Value  // Immutable slice pointer
}

func (rs *RCUStore) Search(target int) bool {
    // No lock needed!
    data := rs.data.Load().([]int)
    for _, v := range data {
        if v == target {
            return true
        }
    }
    return false
}

func (rs *RCUStore) Insert(value int) {
    // Copy-on-write
    oldData := rs.data.Load().([]int)
    newData := append([]int{}, oldData...)
    newData = append(newData, value)
    rs.data.Store(newData)
}

2. Segment-Based Locking

type SegmentedStore struct {
    segments [16]*Segment  // Hash to segment
}

// Operations only lock relevant segment
func (ss *SegmentedStore) Search(target int) {
    seg := ss.segments[hash(target) % 16]
    seg.Lock()
    defer seg.Unlock()
    // Search in segment
}

Advantages of This Pattern

✓ Nuanced control - Three different access levels ✓ Optimistic reads - Searches highly concurrent ✓ Safety - Deletes get exclusive access ✓ Flexibility - Can add more operation types

When to Use

✓ Use when:

Multiple operation types with different requirements
Some operations can overlap
Others need exclusion
Database or data structure implementation

✗ Avoid when:

Simple read/write sufficient
All operations need exclusion
Lock-free possible
Performance critical (use RCU)

Try It Yourself

Add priorities - Deleters > Inserters > Searchers
Measure contention - Track wait times per operation
Test starvation - Can searchers starve inserters?
Partition data - Split into multiple locked segments
Lock-free version - Use atomic operations and CAS

This is part 15 of “Golang Experiments: Classic Concurrency Problems”

The Search-Insert-Delete Problem#

The Scenario#

The Challenge: Three-Way Coordination#

Real-World Applications#

Access Pattern Visualization#

Implementation in Go#

How It Works#

1. Three Condition Variables#

2. Compatibility Matrix#

3. Wait-Acquire-Release Pattern#

Advanced: Priority-Based Access#

Comparison with Readers-Writers#

Access Patterns Visualization#

Key Go Patterns#

1. Multiple Condition Variables#

2. Atomic Counters for Active Operations#

3. Predicate-Based Waiting#

Performance Considerations#

Contention Analysis#

Optimization Strategies#

Variations#

1. Read-Copy-Update (RCU)#

2. Segment-Based Locking#

Advantages of This Pattern#

When to Use#

Try It Yourself#