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

Question

Для потокобезопасности префиксного дерева можно использовать: мьютексы для блокировки операций, read-write блокировки для оптимизации чтения, или immutable-подход с копированием при изменении. Выбор зависит от частоты операций чтения/записи.

YeaHub · Accepted Answer

1. Основные подходы к потокобезопасностиПолная блокировка (Coarse-grained locking)Используется один мьютекс для всей структурыПростая реализация, но плохая производительностьtype SafeTrie struct {
    mu    sync.Mutex
    trie  *Trie
}Тонкая блокировка (Fine-grained locking)Блокировка на уровне узлов дереваЛучшая параллельность, но сложнее реализацияtype TrieNode struct {
    mu       sync.RWMutex
    children map[rune]*TrieNode
}Read-Write блокировки (sync.RWMutex)Множество читателей или один писательОптимально для частого чтенияfunc (t *SafeTrie) Search(word string) bool {
    t.mu.RLock()
    defer t.mu.RUnlock()
    return t.trie.Search(word)
}2. Специальные техникиCopy-on-Write (Immutable структуры)При изменении создаётся новая версияБез блокировок для чтенияfunc (t *Trie) Insert(word string) *Trie {
    newTrie := t.Clone()
    // Вставка в newTrie
    return newTrie
}Каналы в 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 для изоляции состояния