Core Data Structures

Entry Structure

type slot struct {
    valuePointer atomic.Pointer[interface{}]
}

The slot struct represents a key-value storage location within the concurrent map. It uses an atomic pointer to ensure thread-safe access to stored values without requiring external synchronization.

Read-Only View

type snapshot struct {
    data      map[interface{}]*slot
    outdated  bool
}

This structure maintains a read-only copy of map data for fast concurrent reads. The outdated flag indicates when the primary storage contains keys missing from this snapshot.

Concurrent Map

type ConcurrentMap struct {
    lock    sync.Mutex
    snapshot atomic.Pointer[snapshot]
    primary map[interface{}]*slot
    cacheMisses int
}

The main structure employs dual storage: a lock-free snapshot for reads and a locked primary map for writes. This design optimizes for frequent read operations while maintaining write consistency.

Key Operations

Retrieving Values

func (cm *ConcurrentMap) Get(key interface{}) (value interface{}, found bool) {
    snap := cm.getSnapshot()
    s, exists := snap.data[key]
    if !exists && snap.outdated {
        cm.lock.Lock()
        snap = cm.getSnapshot()
        s, exists = snap.data[key]
        if !exists && snap.outdated {
            s, exists = cm.primary[key]
            cm.recordMiss()
        }
        cm.lock.Unlock()
    }
    if !exists {
        return nil, false
    }
    return s.loadValue()
}

Value retrieval first checks the snapshot without locking. If the key isn't found and the snapshot is outdated, it acquires the lock and searches the primary map.

Storing Values

func (cm *ConcurrentMap) Put(key, val interface{}) (previous interface{}, existed bool) {
    snap := cm.getSnapshot()
    if s, ok := snap.data[key]; ok {
        if oldVal, swapped := s.attemptSwap(&val); swapped {
            if oldVal == nil {
                return nil, false
            }
            return *oldVal, true
        }
    }

    cm.lock.Lock()
    snap = cm.getSnapshot()
    if s, ok := snap.data[key]; ok {
        if s.reactivate() {
            cm.primary[key] = s
        }
        if oldVal := s.swapValue(&val); oldVal != nil {
            existed = true
            previous = *oldVal
        }
    } else if s, ok := cm.primary[key]; ok {
        if oldVal := s.swapValue(&val); oldVal != nil {
            existed = true
            previous = *oldVal
        }
    } else {
        if !snap.outdated {
            cm.initializePrimary()
            cm.snapshot.Store(&snapshot{data: snap.data, outdated: true})
        }
        cm.primary[key] = newSlot(val)
    }
    cm.lock.Unlock()
    return previous, existed
}

Value storage attempts lock-free updates via the snapshot first. When necessary, it acquires the lock to update the primary storage and manages state transitions between snapshot and primary maps.

State Management

Entry States

Antries can exist in three states:

• Active: Contains a valid value pointer
• Cleared: Pointer is nil, indicating deletion
• Removed: Special marker indicating permanent removal from primary storage

State Transition Example

func (s *slot) attemptSwap(newVal *interface{}) (*interface{}, bool) {
    for {
        current := s.valuePointer.Load()
        if current == removedMarker {
            return nil, false
        }
        if s.valuePointer.CompareAndSwap(current, newVal) {
            return current, true
        }
    }
}

This method demonstratse how atomic operations prevent updates to permanently removed entries while allowing updates to temporarily cleared ones.

Performance Characteristics

This implementation excels in read-heavy workloads with infrequent writes. For scenarios involving frequent key updates, performance may approach that of a standard map protected by a mutex due to increased lock contention.

The distinction between cleared and removed states is critical for maintaining consistency between snapshot and primary storage during map reorganization.