предисловие
Сегодня в технической группе есть небольшие партнеры, которые обсуждают параллелизм и безопасность.На самом деле, я уже писал статьи, связанные с картами:Давайте поговорим о карте Голанга от простого к сложному. Но в нем не указано, что такое sync.Map. Оглядываясь назад, я могу сказать, что в моей памяти остались только «две карты, одна только для чтения и одна для чтения и записи, ххххх» и другие ключевые слова. Если у вас есть впечатление, вы можете его осуществить, но это немного сумбурно, так что давайте запишем его и кратко запишем.
1. Зачем вам sync.Map? 2. Как пользоваться sync.Map? 3. Каков исходный код реализации sync.Map? 4. Преимущества и недостатки sync.Map? 5. Распространение мышления?
текст
1. Зачем вам sync.Map?
О карте можно посмотреть напрямуюДавайте поговорим о карте Голанга от простого к сложному,Больше никогда.
Зачем тебе это? Причина очень проста, а именно: карта является виртуальной в параллелизме, доступ только для чтения является потокобезопасным, а запись не является потокобезопасной, поэтому для того, чтобыБезопасный и эффективный параллелизм, официальная реализация.
1.1 Какие проблемы с одновременным написанием карт?
Давайте посмотрим, как карта без sync.Map безопасна для параллелизма:
func main() {
m := map[int]int {1:1}
go do(m)
go do(m)
time.Sleep(1*time.Second)
fmt.Println(m)
}
func do (m map[int]int) {
i := 0
for i < 10000 {
m[1]=1
i++
}
}
вывод:
fatal error: concurrent map writes
о нет. Ошибка очень очевидна, этот приятель не может писать одновременно.
1.2 Младшая версия решения
добавить большой замок.
// 大家好，我是那把大锁
var s sync.RWMutex
func main() {
m := map[int]int {1:1}
go do(m)
go do(m)
time.Sleep(1*time.Second)
fmt.Println(m)
}
func do (m map[int]int) {
i := 0
for i < 10000 {
// 加锁
s.Lock()
m[1]=1
// 解锁
s.Unlock()
i++
}
}
вывод:
map[1:1]
На этот раз, наконец, нормально, но в чем проблема? Увеличение вероятности блокировки не является оптимальным решением, как правило,Вопросы эффективности. С точки зрения непрофессионалаБлокировка увеличения влияет на другие операции элемента.
解决思路：减少加锁时间。
方法： 1.空间换时间。 2.降低影响范围。
sync.Map использует вышеуказанные идеи. Продолжайте смотреть вниз.
2. Как пользоваться sync.Map?
Над кодом:
func main() {
// 关键人物出场
m := sync.Map{}
m.Store(1,1)
go do(m)
go do(m)
time.Sleep(1*time.Second)
fmt.Println(m.Load(1))
}
func do (m sync.Map) {
i := 0
for i < 10000 {
m.Store(1,1)
i++
}
}
вывод:
1 true
беги нормально. Это шоу.
3. Каков исходный код реализации sync.Map?
Сначала поговорим о логике. Пусть следующее читается быстрее. (Возможно, это единственный выход)Пишите: Пишите прямо. Читайте: сначала прочитайте, а не грязно снова.
Давайте подробно пройдемся по исходному коду от идеи «инфраструктура + CRUD».
3.1 Инфраструктура
Основная структура данных sync.Map:
type Map struct {
mu Mutex
read atomic.Value // readOnly
dirty map[interface{}]*entry
misses int
}
| инструкция | тип | эффект |
|---|---|---|
| mu | Mutex | запирающий эффект. Защитите грязное поле следующих |
| read | atomic.Value | читать данные. Поскольку он имеет тип atomic.Value и доступен только для чтения, параллелизм безопасен. На самом деле сохраняется структура данных readOnly. |
| misses | int | счетный эффект. Каждый раз, когда чтение из чтения завершается ошибкой, счетчик равен +1. |
| dirty | map[interface{}]*entry | Содержит самые последние записанные данные. Когда количество промахов достигает определенного значения, ему назначается чтение. |
Здесь необходимо кратко описать общую логику.
Структура данных readOnly:
type readOnly struct {
m map[interface{}]*entry
amended bool
}
| инструкция | тип | эффект |
|---|---|---|
| m | map[interface{}]*entry | Простая структура карты |
| amended | bool | Когда данные Map.dirty отличаются от данных m здесь, это правда |
Структура данных записи:
type entry struct {
//可见value是个指针类型，虽然read和dirty存在冗余情况（amended=false），但是由于是指针类型，存储的空间应该不是问题
p unsafe.Pointer // *interface{}
}
Эта структура в основном предназначена для иллюстрации. Хотя предыдущие read и dirty являются избыточными, поскольку все значения имеют тип указателя, пространство для хранения на самом деле не сильно увеличилось.
3.2 Запрос
func (m *Map) Load(key interface{}) (value interface{}, ok bool) {
// 因read只读，线程安全，优先读取
read, _ := m.read.Load().(readOnly)
e, ok := read.m[key]
// 如果read没有，并且dirty有新数据，那么去dirty中查找
if !ok && read.amended {
m.mu.Lock()
// 双重检查（原因是前文的if判断和加锁非原子的，害怕这中间发生故事）
read, _ = m.read.Load().(readOnly)
e, ok = read.m[key]
// 如果read中还是不存在，并且dirty中有新数据
if !ok && read.amended {
e, ok = m.dirty[key]
// m计数+1
m.missLocked()
}
m.mu.Unlock()
}
if !ok {
return nil, false
}
return e.load()
}
func (m *Map) missLocked() {
m.misses++
if m.misses < len(m.dirty) {
return
}
// 将dirty置给read，因为穿透概率太大了(原子操作，耗时很小)
m.read.Store(readOnly{m: m.dirty})
m.dirty = nil
m.misses = 0
}
блок-схема:
Как установить порог?
используется здесьпропустить счет и грязную длинусравнения, чтобы установить порог.
Почему грязный можно напрямую изменить на чтение?
Поскольку операции записи работают только с грязными, гарантируется, что грязные данные актуальны, а набор данных должен содержать операции чтения. (У некоторых учащихся могут возникнуть вопросы, на следующем шаге грязный не обнуляется, почему он все еще включен? Объяснение будет позже.)
Почему для dirty установлено значение nil?
Я не уверен в этой причине. Догадайтесь: С одной стороны, когда чтение полностью равно грязному, если нет чтения, нет чтения, даже если оно проникает, результат тот же, поэтому сохранять его бесполезно. С другой стороны, при сохранении, если элементов больше, это повлияет на эффективность вставки.
3.3 Удалить
func (m *Map) Delete(key interface{}) {
// 读出read，断言为readOnly类型
read, _ := m.read.Load().(readOnly)
e, ok := read.m[key]
// 如果read中没有，并且dirty中有新元素，那么就去dirty中去找。这里用到了amended，当read与dirty不同时为true，说明dirty中有read没有的数据。
if !ok && read.amended {
m.mu.Lock()
// 再检查一次，因为前文的判断和锁不是原子操作，防止期间发生了变化。
read, _ = m.read.Load().(readOnly)
e, ok = read.m[key]
if !ok && read.amended {
// 直接删除
delete(m.dirty, key)
}
m.mu.Unlock()
}
if ok {
// 如果read中存在该key，则将该value 赋值nil（采用标记的方式删除！）
e.delete()
}
}
func (e *entry) delete() (hadValue bool) {
for {
// 再次再一把数据的指针
p := atomic.LoadPointer(&e.p)
if p == nil || p == expunged {
return false
}
// 原子操作
if atomic.CompareAndSwapPointer(&e.p, p, nil) {
return true
}
}
}
блок-схема:
Здесь следует подчеркнуть несколько моментов:
1. Почему грязные удаляются напрямую, а прочитанные помечаются как удаление?
Роль чтения заключается в том, чтобы иметь приоритет перед грязным, при встрече с одним и тем же элементом, чтобы не проникнуть в грязный, используется метод маркировки. В то же время именно благодаря этому механизму + исправленная метка можно гарантировать, что при чтении не может найти &&amended=false, не должно быть найдено в грязных
2. Почему грязные можно удалять напрямую, не читая существование перед прочтением?
Низкая стоимость удаления. Вам нужно искать один раз, чтобы прочитать, и вам нужно искать удаление, поэтому нет необходимости повторять операцию.
3. Как отметить?
Установите значение на ноль. (это очень важно)
3.4 Добавлено (изменено)
func (m *Map) Store(key, value interface{}) {
// 如果m.read存在这个key，并且没有被标记删除，则尝试更新。
read, _ := m.read.Load().(readOnly)
if e, ok := read.m[key]; ok && e.tryStore(&value) {
return
}
// 如果read不存在或者已经被标记删除
m.mu.Lock()
read, _ = m.read.Load().(readOnly)
if e, ok := read.m[key]; ok { // read 存在该key
// 如果entry被标记expunge，则表明dirty没有key，可添加入dirty，并更新entry。
if e.unexpungeLocked() {
// 加入dirty中，这儿是指针
m.dirty[key] = e
}
// 更新value值
e.storeLocked(&value)
} else if e, ok := m.dirty[key]; ok { // dirty 存在该key，更新
e.storeLocked(&value)
} else { // read 和 dirty都没有
// 如果read与dirty相同，则触发一次dirty刷新（因为当read重置的时候，dirty已置为nil了）
if !read.amended {
// 将read中未删除的数据加入到dirty中
m.dirtyLocked()
// amended标记为read与dirty不相同，因为后面即将加入新数据。
m.read.Store(readOnly{m: read.m, amended: true})
}
m.dirty[key] = newEntry(value)
}
m.mu.Unlock()
}
// 将read中未删除的数据加入到dirty中
func (m *Map) dirtyLocked() {
if m.dirty != nil {
return
}
read, _ := m.read.Load().(readOnly)
m.dirty = make(map[interface{}]*entry, len(read.m))
// 遍历read。
for k, e := range read.m {
// 通过此次操作，dirty中的元素都是未被删除的，可见标记为expunged的元素不在dirty中！！！
if !e.tryExpungeLocked() {
m.dirty[k] = e
}
}
}
// 判断entry是否被标记删除，并且将标记为nil的entry更新标记为expunge
func (e *entry) tryExpungeLocked() (isExpunged bool) {
p := atomic.LoadPointer(&e.p)
for p == nil {
// 将已经删除标记为nil的数据标记为expunged
if atomic.CompareAndSwapPointer(&e.p, nil, expunged) {
return true
}
p = atomic.LoadPointer(&e.p)
}
return p == expunged
}
// 对entry尝试更新 （原子cas操作）
func (e *entry) tryStore(i *interface{}) bool {
p := atomic.LoadPointer(&e.p)
if p == expunged {
return false
}
for {
if atomic.CompareAndSwapPointer(&e.p, p, unsafe.Pointer(i)) {
return true
}
p = atomic.LoadPointer(&e.p)
if p == expunged {
return false
}
}
}
// read里 将标记为expunge的更新为nil
func (e *entry) unexpungeLocked() (wasExpunged bool) {
return atomic.CompareAndSwapPointer(&e.p, expunged, nil)
}
// 更新entry
func (e *entry) storeLocked(i *interface{}) {
atomic.StorePointer(&e.p, unsafe.Pointer(i))
}
блок-схема:
- Пометить как удаленную разницу в прочтении?
Он помечен как nil, что указывает на то, что это обычная операция удаления, и в настоящее время она может не существовать в грязном состоянии. А. После того, как грязные данные назначены для чтения, грязные в настоящее время не существуют. б) после грязной инициализации он должен существовать
Он помечен как expunged, указывая на то, что он работает при инициализации dirty, и в это время он не должен существовать в dirty.
- Может проблема в производительности?
При инициализации dirty, хотя все назначения указателя выполняются, если чтение больше, это может иметь некоторое влияние.
4. Преимущества и недостатки sync.Map?
Сначала делай выводы, потом доказывай.
Достоинства: Официально выдан, и это про-сын, за счет разделения чтения и записи время блокировки сокращается для повышения эффективности; Недостатки: Не подходит для большого количества сценариев записи, что приведет к тому, что карта чтения не сможет прочитать данные и дополнительно заблокирует чтение, при этом грязная карта всегда будет повышена до карты чтения. , и общая производительность оставляет желать лучшего. Применимые сценарии: много читать, мало писать
Здесь в основном, чтобы доказать, почему он подходит дляМного читай, мало пиши. Общая идея кода: Сравнивая простую карту и sync.Map, в случае безопасности параллелизма эффективность только записи и чтения и записи
var s sync.RWMutex
var w sync.WaitGroup
func main() {
mapTest()
syncMapTest()
}
func mapTest() {
m := map[int]int {1:1}
startTime := time.Now().Nanosecond()
w.Add(1)
go writeMap(m)
w.Add(1)
go writeMap(m)
//w.Add(1)
//go readMap(m)
w.Wait()
endTime := time.Now().Nanosecond()
timeDiff := endTime-startTime
fmt.Println("map:",timeDiff)
}
func writeMap (m map[int]int) {
defer w.Done()
i := 0
for i < 10000 {
// 加锁
s.Lock()
m[1]=1
// 解锁
s.Unlock()
i++
}
}
func readMap (m map[int]int) {
defer w.Done()
i := 0
for i < 10000 {
s.RLock()
_ = m[1]
s.RUnlock()
i++
}
}
func syncMapTest() {
m := sync.Map{}
m.Store(1,1)
startTime := time.Now().Nanosecond()
w.Add(1)
go writeSyncMap(m)
w.Add(1)
go writeSyncMap(m)
//w.Add(1)
//go readSyncMap(m)
w.Wait()
endTime := time.Now().Nanosecond()
timeDiff := endTime-startTime
fmt.Println("sync.Map:",timeDiff)
}
func writeSyncMap (m sync.Map) {
defer w.Done()
i := 0
for i < 10000 {
m.Store(1,1)
i++
}
}
func readSyncMap (m sync.Map) {
defer w.Done()
i := 0
for i < 10000 {
m.Load(1)
i++
}
}
| состояние | результат |
|---|---|
| просто пиши | map: 1,022,000 sync.Map: 2,164,000 |
| прочти и напиши | map: 8,696,000 sync.Map: 2,047,000 |
Выяснится, что в сценарии с большим количеством записей, поскольку операций в sync.Map больше, эффективность не так высока, как у чистой карты+metux.
5. Распространение мышления?
Подумайте о том, есть ли у блокировок MySQL блокировки на уровне таблицы и блокировки на уровне строки.Приведенный выше метод блокировки sync.RWMutex эквивалентен блокировкам на уровне таблицы.
А sync.Map фактически эквивалентен блокировке на уровне таблицы, за исключением того, что есть еще две карты для чтения и записи, а суть все та же. В этом случае естественно знать направление оптимизации: максимально уменьшить гранулярность блокировки, чтобы повысить скорость работы.
Идея: Хешировать большую карту, которая содержит n маленьких карт, и определить конкретную маленькую карту путем хэширования по ключу, чтобы степень детализации блокировки стала 1/n. Я нашел это в Интернете, и есть действительно большие ребята, которые поняли это:кликните сюда
(Да, я ленивый, ха-ха, это копия статьи, которую я написал ранее)
Если вы думаете, что у вас есть что-то, чтобы получить ~ вы можете обратить внимание на публичный аккаунт «Коричневая альпака» и получить мой опыт обмена и интервью как можно скорее ~