Интерпретация исходного кода Принцип реализации sync.Map в Golang

Go
Интерпретация исходного кода Принцип реализации sync.Map в Golang

Введение

встроенный в GomapПараллельные операции записи не поддерживаются, посколькуmapОперации записи не являются безопасными для параллелизма, когда вы пытаетесь использовать несколько горутин для работы с одним и тем жеmap, выдаст ошибку:fatal error: concurrent map writes.

Таким образом, официальное введениеsync.MapДля удовлетворения применения параллельного программирования.

sync.MapПринцип реализации можно резюмировать следующим образом:

  • Чтение и запись разделены двумя полями: чтение и грязный.Прочитанные данные хранятся в поле только для чтения, а последние записанные данные хранятся в грязном поле.
  • При чтении он сначала будет запрашивать чтение, а затем запрашивать грязные данные, если он не существует, и записывать грязные данные только при записи.
  • Чтение чтения не требует блокировки, а чтение или запись грязного требует блокировки
  • Кроме того, имеется поле промахов для подсчета количества попыток чтения (проникновение относится к необходимости чтения грязных данных), и если оно превышает определенное количество раз, грязные данные будут синхронизированы для чтения.
  • Для удаленных данных удаление откладывается непосредственно путем пометки

структура данных

MapСтруктура данных следующая:

type Map struct {
    // 加锁作用，保护 dirty 字段
    mu Mutex
    // 只读的数据，实际数据类型为 readOnly
    read atomic.Value
    // 最新写入的数据
    dirty map[interface{}]*entry
    // 计数器，每次需要读 dirty 则 +1
    misses int
}

Структура данных readOnly:

type readOnly struct {
    // 内建 map
    m  map[interface{}]*entry
    // 表示 dirty 里存在 read 里没有的 key，通过该字段决定是否加锁读 dirty
    amended bool
}

entryСтруктуры данных используются для хранения указателей на значения:

type entry struct {
    p unsafe.Pointer  // 等同于 *interface{}
}

Свойство p имеет три состояния:

  • p == nil: значение ключа было удалено, иm.dirty == nil
  • p == expunged: значение ключа было удалено, ноm.dirty!=nilиm.dirtyЗначение ключа не существует (expunged на самом деле является нулевым указателем интерфейса)
  • За исключением вышеуказанных случаев, пара ключ-значение существует и существует вm.read.m, еслиm.dirty!=nilтакже существует вm.dirty

MapОбычно используются следующие методы:

  • Load: прочитать указанный ключ и вернуть значение
  • Store: сохранить (добавить или изменить) ключ-значение
  • Delete: удалить указанный ключ

Анализ исходного кода

Load

func (m *Map) Load(key interface{}) (value interface{}, ok bool) {
    // 首先尝试从 read 中读取 readOnly 对象
    read, _ := m.read.Load().(readOnly)
    e, ok := read.m[key]

    // 如果不存在则尝试从 dirty 中获取
    if !ok && read.amended {
        m.mu.Lock()
        // 由于上面 read 获取没有加锁，为了安全再检查一次
        read, _ = m.read.Load().(readOnly)
        e, ok = read.m[key]

        // 确实不存在则从 dirty 获取
        if !ok && read.amended {
            e, ok = m.dirty[key]
            // 调用 miss 的逻辑
            m.missLocked()
        }
        m.mu.Unlock()
    }

    if !ok {
        return nil, false
    }
    // 从 entry.p 读取值
    return e.load()
}

func (m *Map) missLocked() {
    m.misses++
    if m.misses < len(m.dirty) {
        return
    }
    // 当 miss 积累过多，会将 dirty 存入 read，然后 将 amended = false，且 m.dirty = nil
    m.read.Store(readOnly{m: m.dirty})
    m.dirty = nil
    m.misses = 0
}

Store

func (m *Map) Store(key, value interface{}) {
    read, _ := m.read.Load().(readOnly)
    // 如果 read 里存在，则尝试存到 entry 里
    if e, ok := read.m[key]; ok && e.tryStore(&value) {
        return
    }

    // 如果上一步没执行成功，则要分情况处理
    m.mu.Lock()
    read, _ = m.read.Load().(readOnly)
    // 和 Load 一样，重新从 read 获取一次
    if e, ok := read.m[key]; ok {
        // 情况 1：read 里存在
        if e.unexpungeLocked() {
            // 如果 p == expunged，则需要先将 entry 赋值给 dirty（因为 expunged 数据不会留在 dirty）
            m.dirty[key] = e
        }
        // 用值更新 entry
        e.storeLocked(&value)
    } else if e, ok := m.dirty[key]; ok {
        // 情况 2：read 里不存在，但 dirty 里存在，则用值更新 entry
        e.storeLocked(&value)
    } else {
        // 情况 3：read 和 dirty 里都不存在
        if !read.amended {
            // 如果 amended == false，则调用 dirtyLocked 将 read 拷贝到 dirty（除了被标记删除的数据）
            m.dirtyLocked()
            // 然后将 amended 改为 true
            m.read.Store(readOnly{m: read.m, amended: true})
        }
        // 将新的键值存入 dirty
        m.dirty[key] = newEntry(value)
    }
    m.mu.Unlock()
}

func (e *entry) tryStore(i *interface{}) bool {
    for {
        p := atomic.LoadPointer(&e.p)
        if p == expunged {
            return false
        }
        if atomic.CompareAndSwapPointer(&e.p, p, unsafe.Pointer(i)) {
            return true
        }
    }
}

func (e *entry) unexpungeLocked() (wasExpunged bool) {
    return atomic.CompareAndSwapPointer(&e.p, expunged, nil)
}

func (e *entry) storeLocked(i *interface{}) {
    atomic.StorePointer(&e.p, unsafe.Pointer(i))
}

func (m *Map) dirtyLocked() {
    if m.dirty != nil {
        return
    }

    read, _ := m.read.Load().(readOnly)
    m.dirty = make(map[interface{}]*entry, len(read.m))
    for k, e := range read.m {
        // 判断 entry 是否被删除，否则就存到 dirty 中
        if !e.tryExpungeLocked() {
            m.dirty[k] = e
        }
    }
}

func (e *entry) tryExpungeLocked() (isExpunged bool) {
    p := atomic.LoadPointer(&e.p)
    for p == nil {
        // 如果有 p == nil（即键值对被 delete），则会在这个时机被置为 expunged
        if atomic.CompareAndSwapPointer(&e.p, nil, expunged) {
            return true
        }
        p = atomic.LoadPointer(&e.p)
    }
    return p == expunged
}

Delete

func (m *Map) Delete(key interface{}) {
    m.LoadAndDelete(key)
}

// LoadAndDelete 作用等同于 Delete，并且会返回值与是否存在
func (m *Map) LoadAndDelete(key interface{}) (value interface{}, loaded bool) {
    // 获取逻辑和 Load 类似，read 不存在则查询 dirty
    read, _ := m.read.Load().(readOnly)
    e, ok := read.m[key]
    if !ok && read.amended {
        m.mu.Lock()
        read, _ = m.read.Load().(readOnly)
        e, ok = read.m[key]
        if !ok && read.amended {
            e, ok = m.dirty[key]
            m.missLocked()
        }
        m.mu.Unlock()
    }
    // 查询到 entry 后执行删除
    if ok {
        // 将 entry.p 标记为 nil，数据并没有实际删除
        // 真正删除数据并被被置为 expunged，是在 Store 的 tryExpungeLocked 中
        return e.delete()
    }
    return nil, false
}

Суммировать

Видно, что благодаря такому дизайну разделения чтения и записи решается проблема безопасности записи в параллельных ситуациях, а скорость чтения в большинстве случаев может быть близка к встроенной.map, который очень подходит для того, чтобы больше читать и меньше писать.

sync.MapЕсть и другие методы:

  • Range: Обход всех пар ключ-значение, параметр является функцией обратного вызова.
  • LoadOrStore: Прочитайте данные, если они не существуют, сохраните их и прочитайте снова

Это не будет подробно объясняться здесь, пожалуйста, обратитесь кисходный код.

Эта статья принадлежит к оригиналу, впервые опубликованному в публичном аккаунте WeChat.программирование на всю жизнь», если вам нужно перепечатать, пожалуйста, оставьте сообщение в фоновом режиме.

Подпишитесь и ответьте на следующую информацию для получения дополнительных ресурсов
Ответить на [Информация] Получить учебные ресурсы, такие как Python/Java
Ответить на [Плагины] Получить плагины Chrome, обычно используемые поисковыми роботами
Ответить на [Zhihu] Получить последнюю версию входа в симуляцию Zhihu

Категории