Перейти sync.Map посмотреть

Go

Случайно наткнулся на эту статью:Вопрос интервью с golang о параллелизме и блокировке. Несмотря на то, что он старый, он все еще немного интересен.

Недавно мне довелось увидеть sync.Map, поэтому я хотел посмотреть, смогу ли я использовать sync.Map для достижения вышеуказанных функций.

Я также нашел чужие реализации sync.Mutex на gayhub,【Кликните сюда】.

Подвести итог

Требования следующие:

На веб-сервере с высокой степенью параллелизма необходимо ограничить частый доступ по IP. Теперь смоделируйте 100 IP-адресов, одновременно обращающихся к серверу, и каждый IP-адрес должен быть доступен 1000 раз. Доступ к каждому IP-адресу возможен только один раз в течение трех минут. Измените следующий код, чтобы завершить процесс, и он необходим для успешного вывода: 100.

и учитывая исходный код:

package main

import (
    "fmt"
    "time"
)

type Ban struct {
    visitIPs map[string]time.Time
}

func NewBan() *Ban {
    return &Ban{visitIPs: make(map[string]time.Time)}
}

func (o *Ban) visit(ip string) bool {
    if _, ok := o.visitIPs[ip]; ok {
        return true
    }
    o.visitIPs[ip] = time.Now()
    return false
}

func main() {
    success := 0
    ban := NewBan()
    for i := 0; i < 1000; i++ {
        for j := 0; j < 100; j++ {
            go func() {
                ip := fmt.Sprintf("192.168.1.%d", j)
                if !ban.visit(ip) {
                    success++
                }
            }()
        }
    }
    fmt.Println("success: ", success)
}

Ого, увидев исходный код, я хочу сказать, что могу просто оставитьpackage mainОстальные переписаны? (закрывает лицо)

Вы умны, вы обнаружили, что ключом к этой проблеме является желание, чтобы вы добавили блокировку чтения-записи в Бан. И три минуты в условиях совсем не помешали, потому что этот день программа вообще бы не выдержала.

идеи

На самом деле первоначальная идея не изменилась, и BanList по-прежнему используется для отображения временно недоступных идентификаторов пользователей. Затем каждый раз при посещении определяйте, есть ли пользователь в списке.

Исправлять

Хорошо, теперь нам нужна структура, потому что мы будем читать карту одновременно, поэтому мы используем sync.Map напрямую:

type Ban struct {
    M sync.Map
}

Если вы нажмете на sync.Map, вы обнаружите, что на самом деле данные хранятся вatomic.Value. Интерфейс{} с атомарными свойствами.

В то же время структура Бана также будет иметьIsInМетод используется для определения того, находится ли идентификатор пользователя на карте.

func (b *Ban) IsIn(user string) bool {
    fmt.Printf("%s 进来了\n", user)
    // Load 方法返回两个值，一个是如果能拿到的 key 的 value
    // 还有一个是否能够拿到这个值的 bool 结果
    v, ok := b.M.Load(user) // sync.Map.Load 去查询对应 key 的值
    if !ok {
        // 如果没有，说明可以访问
        fmt.Printf("名单里没有 %s，可以访问\n", user)
        // 将用户名存入到 Ban List 中
        b.M.Store(ip, time.Now())
        return false
    }
    // 如果有，则判断用户的时间距离现在是否已经超过了 180 秒，也就是3分钟
    if time.Now().Second() - v.(time.Time).Second() > 180 {
        // 超过则可以继续访问
        fmt.Printf("时间为：%d-%d\n", v.(time.Time).Second(), time.Now().Second())
        // 同时重新存入时间
        b.M.Store(ip, time.Now())
        return false
    }
    // 否则不能访问
    fmt.Printf("名单里有 %s，拒绝访问\n", user)
    return true
}

Вот посмотрите на протестированную функцию:

func main() {
    var success int64 = 0
    ban := new(Ban)
    wg := sync.WaitGroup{} // 保证程序运行完成
    for i := 0; i < 2; i++ { // 我们大循环两次，每个user 连续访问两次
        for j := 0; j < 10; j++ { // 人数预先设定为 10 个人
            wg.Add(1)
            go func(c int) {
                defer wg.Done()
                ip := fmt.Sprintf("%d", c)
                if !ban.IsIn(ip) {
                    // 原子操作增加计数器，用来统计我们人数的
                    atomic.AddInt64(&success, 1)
                }
            }(j)
        }
    }
    wg.Wait()
    fmt.Println("此次访问量：", success)
}

На самом деле в тестируемую функцию не было внесено никаких серьезных изменений, но поскольку мы работаем одновременно, нам нужно добавить sync.WaitGroup(), чтобы гарантировать, что программа полностью запустится перед выходом.

Я специально скорректировал текущее значение на меньшее значение, чтобы облегчить тестирование. Пучок1000запросить, изменить на2Второсортный.100человек изменился на10люди.

Таким образом, весь код должен быть таким:

package main

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

type Ban struct {
    M sync.Map
}

func (b *Ban) IsIn(user string) bool {
    ...
}

func main() {
    ...
}

запустить его...

Эй, это кажется неправильным, я обнаружил, что будет 10-15 посещений от 10 до 15 раз. Зачем? Если подумать, это на самом деле вызвано параллелизмом, видите здесь?

func (b *Ban) IsIn(user string) bool {
    ...
    v, ok := b.M.Load(user)
    if !ok {
        fmt.Printf("名单里没有 %s，可以访问\n", user)
        b.M.Store(ip, time.Now())
        return false
    }
    ...
}

одновременно инициированныйsync.Map.LoadНа самом деле не сsync.Map.StoreОбъединены для формирования атомарных операций. Таким образом, если три пользователя входят одновременно и программа выполняет запросы одновременно, все три возвращаемых результата будут ложными (не в списке). Таким образом, это также увеличивает количество посещений.

На самом деле, sync.Map тоже учёл эту ситуацию, так что у него будетLoadOrStoreАтомарный метод -- Если не выходит Load, просто сохраняйте напрямую, если выходит Load, ничего не делайте.

Итак, давайте внесем небольшое изменение в код IsIn:

func (b *Ban) IsIn(user string) bool {
    ...
    v, ok := b.M.LoadOrStore(user, time.Now())
    if !ok {
        fmt.Printf("名单里没有 %s，可以访问\n", user)
        // 删除b.M.Store(ip, time.Now())
        return false
    }
    ...
}

Затем запускаем его снова, несколько раз. Выясняется, что на этот раз посещений будет не больше 10.

присмотрись повнимательнее

До сих пор реализация кода в этом сценарии была успешной. Однако требования сценария, которые действительно ограничивают доступ пользователей, не могут быть воспроизведены таким образом и обычно реализуются с помощью базы данных в памяти.

Итак, если вы просто хотите понять применение sync.Map, вот оно. Однако любопытство заставило меня взглянуть на реализацию sync.Map, так что давайте двигаться дальше.

производственные проблемы

Что, если бы вам пришлось одновременно читать и писать карту? попытайся:

Сначала идет главный герой А.

type A map[string]int

Мы определяем наш собственный тип A, который по сути остается картой.

type A map[string]int

func main() {
    // 初始化一个 A
    m := make(A)
    m.SetMap("one", 1)
    m.SetMap("two", 3)

    // 读取 one
    go m.ReadMap("one")
    // 设置 two 值为 2
    go m.SetMap("two", 2)

    time.Sleep(1*time.Second)
}

// A 有个读取某个 Key 的方法
func (a *A)ReadMap(key string) {
    fmt.Printf("Get Key %s: %d",key, a[key])
}
// A 有个设置某个 Key 的方法
func (a *A)SetMap(key string, value int) {
    a[key] = value
    fmt.Printf("Set Key %s: %d",key, a[key]) // 同协程的读写不会出问题
}

Эй, выглядит хорошо. Мы определили методы get и set для карты типа A. Если golang не разрешает одновременное чтение и запись карт, он должен сообщить об ошибке. Давайте запустим.

> Get Key one: 1
> Set Key two: 2

Мяу-мяу-мяу??? Почему выводится нормально? Как насчет одновременных ошибок чтения и записи? Ну на самом деле причина в вышеприведенной карте чтения и записи, хоть мы и настроили сопрограмму, но все равно есть разница во времени для компьютера. Пока существует небольшая последовательность, она не вызовет аномального чтения и записи данных карты, поэтому давайте изменим ее.

func main() {
    m := make(A)
    m["one"] = 1
    m["two"] = 3

    go func() {
        for {
            m.ReadMap("one")
        }
    }()

    go func(){
        for {
            m.SetMap("two", 2)
        }
    }()

    time.Sleep(1*time.Second)
}

Чтобы сделать операции чтения и записи максимально конфликтными, мы добавляем циклы. Теперь мы можем видеть:

> fatal error: concurrent map read and map write

* Причина паники здесь в том, что это сделано в реализации карты并发读写的检查.

Решать проблему

На самом деле приведенный выше пример очень похож на вводное руководство go по блокировкам sync.Mutex. Мы подтвердили проблему параллельного чтения и записи карты и теперь пытаемся ее решить.

Поскольку это конфликт, вызванный чтением и записью, первое, что мы рассматриваем, — это блокировка. Даем блокировку на чтение и блокировку на запись. Теперь нам нужно преобразовать простую карту A в структуру с замком:

type A struct {
    Value map[string]int
    mu sync.Mutex
}

Ценность становится местом для фактического хранения нашей ценности. мы также должны изменитьReadMapа такжеSetMapдва метода.

func (a *A)ReadMap(key string) {
    a.mu.Lock()
    fmt.Printf("Get Key %s: %d",key, a.Value[key])
    a.mu.Unlock()
}
func (a *A)SetMap(key string, value int) {
    a.mu.Lock()
    a.Value[key] = value
    a.mu.Unlock()
    fmt.Printf("Set Key %s: %d",key, a.Value[key])
}

Обратите внимание, что ни один из двух методов не будет работать без блокировки и разблокировки.

Давайте снова запустим код и обнаружим, что он в порядке, и об ошибке не будет сообщено.

Это конец?

Мы решили насущную проблему самым простым способом, но действительно ли это нормально? Если вы будете внимательны, то обнаружите, что у нас есть блокировки для чтения и записи, и нет особых условий, поэтому, когда мы хотим прочитать данные в карте несколько раз, он заблокируется! Даже если я вообще не хочу менять значение на карте... Хотя сейчас это не кажется медленным, это яма производительности для интенсивного чтения.

Чтобы избежать ненужных блокировок, нам, похоже, придется сделать наш код «умнее».

разделение чтения-записи

Да, разделение чтения и записи — очень применимая дизайнерская идея. Мы готовим карту чтения и карту записи.

Но разделение чтения и записи здесь не то, что мы обычно говорим (помните, что наш сценарий всегда параллельное чтение и запись), мы не можем синхронизировать (добавлять, удалять и изменять) записанную карту с картой чтения в реальном времени. или регулярно. Потому что... это ничем не отличается от операции с картой выше, потому что нет блокировки для чтения карты, все равно будет конфликт параллелизма.

Что нам нужно решить, так это не «отображать» значение, соответствующее ключу на карте. Переклассифицируем проблему:

  1. Изменить (удалить) значение существующего ключа
  2. Добавить несуществующий ключ и значение

第一个问题：Как насчет того, чтобы превратить значение ключа в указатель? Один и тот же ключ указывает на тот же адрес указателя, который, в свою очередь, указывает на адрес реального значения.

ключ -> и адрес -> и адрес реального значения

Значения карты чтения и записи указывают на&地址, кто бы ни изменился, изменятся все. Когда нам нужно изменить значение, соответствующее существующему ключу, мы изменяем следующее:&真正的值地址Значение , не изменяет соответствующий ключ&地址или значение. В то же время черезatomicpackage, мы можем добиться атомарности модификации указателя. Отлично, проблема модификации существующего ключа решена.

第二个问题：Поскольку этого ключа не существует, мы должны добавить новый ключ, Теперь, когда у нас есть карта чтения и записи, мы можем ее использовать. Блокируем и увеличиваем ключ и соответствующее значение в карте Write, чтобы это не влияло на чтение карты Read.

Однако Read map мы все-таки хотим обновить, поэтому добавляем счетчикmisses, при достижении определенного условия безопасно синхронизируем карту Write с картой Read и очищаем карту Write.

Карта чтения может рассматриваться как доступная только для чтения копия карты записи, нельзя добавлять новые ключи отдельно, а можно только читать или изменять.

Приведенная выше идея на самом деле очень близка к реализации sync.Map. Просто sync.Map берет нашеWrite mapназываетсяdirty, поставить карту Write同步на карту чтения, называемуюpromote（升级）. Добавлена ​​некоторая инкапсуляция структуры и флаги состояния.

На самом деле, если вы погуглите, вы найдете много статей, анализирующих исходный код sync.Map, и все они хорошо написаны. Я не буду вдаваться в подробности здесь, но я хочу обобщить это с моим пониманием Идеи метода в sync.Map.

Он вкуснее в сочетании с исходным кодом sync.Map.

читать карту.Загрузить

  1. Может ли Read map читать напрямую?
  2. Есть ли? Хорошо, давайте заблокируем и снова прочитаем карту Read
  3. Еще нет? Тогда я могу только читать Грязную карту
  4. Читать, да, мы записываем, это чтение принадлежит未命中(промахивается +1), кстати, посмотрите, можно ли нашу пакость проапгрейдить до Read
  5. разблокировать

* Причина повторной блокировки в 2 здесь заключается в двойной проверке для предотвращения грязного чтения (грязное внезапное обновление чтения) в течение очень небольшой разницы во времени.

написать в Map.Store

  1. Есть ли на карте чтения этот ключ?
  2. Да, тогда мы атомарно модифицируем указатель значения напрямую.
  3. нет? Все еще заблокированы и посмотрите, есть ли они?
  4. Еще нет, ну посмотрите на Грязную карту
  5. Да! Затем измените указатель значения ключа Dirty map.
  6. нет? Затем нам нужно добавить новый ключ к карте Dirty.Для удобства обновления карты Dirty до карты Read нам также необходимо скопировать исходную карту Read.
  7. разблокировать

удалить карту.удалить

  1. У чтения карты есть этот ключ?
  2. Да, тогда меняем значение сразу на nil (чтобы предотвратить последующее чтение без ключа и нужно его заблокировать, что повлияет на производительность)
  3. нет? Просто удалите ключ в грязном

Чтение или сохранение Map.LoadOrStore

emmmm......

  • Map.Load + Map.Store

я не могу это исправить

Примерно так я и думаю. Я порекомендую здесь некоторые ортодоксальные анализы исходного кода и тесты производительности. Я думаю, что после прочтения sync.Map станет яснее.

Кроме того, если вы заметили шаг 6 в Map.Store全部复制Если это так, у вас будет предчувствие, что сценарий использования sync.Map на самом деле не подходит для логики высокой параллельной записи. Действительно, в официальных инструкциях также четко указаны сценарии, в которых применим sync.Map:

// Map is like a Go map[interface{}]interface{} but is safe for concurrent use
// by multiple goroutines without additional locking or coordination.
...
// The Map type is specialized. Most code should use a plain Go map instead,
// with separate locking or coordination, for better type safety and to make it
// easier to maintain other invariants along with the map content.
//
// The Map type is optimized for two common use cases: (1) when the entry for a given
// key is only ever written once but read many times, as in caches that only grow,
// or (2) when multiple goroutines read, write, and overwrite entries for disjoint
// sets of keys. In these two cases, use of a Map may significantly reduce lock
// contention compared to a Go map paired with a separate Mutex or RWMutex.

sync.Map просто помогает оптимизировать два сценария использования:

  1. Больше читайте и меньше пишите
  2. Значение ключа операции с несколькими горутинами

На самом деле, sync.Map все еще находит подходящий баланс между производительностью и безопасностью, как и в случае в начале, sync.Map неприменим. Кроме того, вот[Расширенная версия sync.Map].

*атомный и мьютекс

На самом деле, когда я давным-давно просматривал исходный код sync Map, я часто задавал вопросы: если atomic можно использовать для решения проблем безопасности параллелизма, зачем нам мьютекс? Более того, в процессе map.Store значение, соответствующее ключу чтения (и состоянию блокировки), все равно будет напрямую изменено, чем это отличается от обычного изменения значения ключа?

Если атомарность может гарантировать атомарность, чем она отличается от мьютекса? Просмотрев некоторые источники, я узнал:

Mutexes are slow, due to the setup and teardown, and due to the fact that they block other goroutines for the duration of the lock.

Atomic operations are fast because they use an atomic CPU instruction, rather than relying on external locks to.

Мьютексы фактически функционируют как атомарные операции, блокируя другие сопрограммы, но атомарность обеспечивает атомарность операций со значениями, управляя инструкциями ЦП более низкого уровня.

Так что atomic и mutex не одного уровня, и они не совпадают в штатной точке.Mutex тоже во многих местах реализован atomic.

А sync Map умело сочетает эти две функции для обеспечения безопасности параллелизма.

  1. Он использует указатель для хранения значения, соответствующего ключу. Когда его нужно изменить, он изменяет только адрес значения (и является операцией копирования значения адреса). Это может быть достигнуто с помощью операции атомарного указателя, и не будет конфликтов.

  2. Кроме того, для управления операцией добавления, удаления, изменения и проверки ключей для предотвращения конфликтов используется разделение чтения-записи + блокировка взаимного исключения мьютекса.

Первый пункт часто упоминается во многих интерпретациях исходного кода, но Mengxin я думаю, что это очень важный навык (закрытие лица).

*некоторые вопросы

не соответствует условию

Я никогда не понимал, почему условием перехода с грязной карты на чтение карты являетсяmisses 次数大于等于 len(m.dirty)?

Почему карта Go не блокируется?

Мы можем увидеть следующие два утверждения о разблокировке:

  1. golang.org/doc/ инициировал #Ati Oh…
  2. blog.golang.org/go-maps-in-…

*Ссылаться на

Категории