Как сделать структуру данных (например, префиксное дерево) потокобезопасной?

1. Основные подходы к потокобезопасности

1. Полная блокировка (Coarse-grained locking)

   • Используется один мьютекс для всей структуры

   • Простая реализация, но плохая производительность

   type SafeTrie struct {
       mu    sync.Mutex
       trie  *Trie
   }

2. Тонкая блокировка (Fine-grained locking)

   • Блокировка на уровне узлов дерева

   • Лучшая параллельность, но сложнее реализация

   type TrieNode struct {
       mu       sync.RWMutex
       children map[rune]*TrieNode
   }

3. Read-Write блокировки (sync.RWMutex)

   • Множество читателей или один писатель

   • Оптимально для частого чтения

   func (t *SafeTrie) Search(word string) bool {
       t.mu.RLock()
       defer t.mu.RUnlock()
       return t.trie.Search(word)
   }

2. Специальные техники

1. Copy-on-Write (Immutable структуры)

   • При изменении создаётся новая версия

   • Без блокировок для чтения

   func (t *Trie) Insert(word string) *Trie {
       newTrie := t.Clone()
       // Вставка в newTrie
       return newTrie
   }

2. Каналы в Go (Actor model)

   • Все операции через channel-менеджер

   func (m *TrieManager) process() {
       for op := range m.ops {
           op.Execute(m.trie)
       }
   }

3. Пример реализации для префиксного дерева

type ConcurrentTrie struct {
    root *TrieNode
}

type TrieNode struct {
    mu       sync.RWMutex
    children map[rune]*TrieNode
    isEnd    bool
}

func (t *ConcurrentTrie) Insert(word string) {
    current := t.root
    for _, char := range word {
        current.mu.Lock()
        if current.children[char] == nil {
            current.children[char] = &TrieNode{
                children: make(map[rune]*TrieNode),
            }
        }
        next := current.children[char]
        current.mu.Unlock()
        current = next
    }
    current.mu.Lock()
    current.isEnd = true
    current.mu.Unlock()
}

Когда использовать:

• Мьютексы: когда операции записи редки

• RWMutex: когда много операций чтения

• Immutable: для почти не изменяемых данных

• Каналы: в Go для изоляции состояния