Map和sync.Map及并发处理

 1// runtime/map.go
 2// A header for a Go map.
 3type hmap struct {
 4	// Note: the format of the hmap is also encoded in cmd/compile/internal/reflectdata/reflect.go.
 5	// Make sure this stays in sync with the compiler's definition.
 6	count     int // # live cells == size of map.  Must be first (used by len() builtin) //键值对数 
 7	flags     uint8
 8	B         uint8  // log_2 of # of buckets (can hold up to loadFactor * 2^B items) //  8个桶这里就是3  4个桶就是2 
 9	noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details
10	hash0     uint32 // hash seed   //hash算法的种子  or 计算 key 的哈希的时候会传入哈希函数
11
12	//  bmap数组       Bucket 数组 个数为     2^B  个 。 
13	buckets    unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.
14	
15	//  扩容的时候用 
16    // 等量扩容的时候，buckets 长度和 oldbuckets 相等
17    // 双倍扩容的时候，buckets 长度会是 oldbuckets 的两倍
18	oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing
19	
20	//  指示扩容进度，小于此地址的 buckets 迁移完成
21	nevacuate  uintptr        // progress counter for evacuation (buckets less than this have been evacuated)
22
23	extra *mapextra // optional fields //溢出桶的信息
24}

 1// A bucket for a Go map.  
 2type bmap struct {
 3	// tophash generally contains the top byte of the hash value
 4	// for each key in this bucket. If tophash[0] < minTopHash,
 5	// tophash[0] is a bucket evacuation state instead.
 6	tophash [bucketCnt]uint8    //key hash后的高8位值   ,bucketCnt = 常量 8 
 7	// Followed by bucketCnt keys and then bucketCnt elems.
 8	// NOTE: packing all the keys together and then all the elems together makes the
 9	// code a bit more complicated than alternating key/elem/key/elem/... but it allows
10  
11  //编译的时候放把 key和 value 放进去
12  
13	// us to eliminate padding which would be needed for, e.g., map[int64]int8.
14  
15  //溢出指针  
16	// Followed by an overflow pointer.
17}
18
19
20// 编译后会变这样。 
21// 这个结构体会在运行后被动态重建，重建后的样子: ，因为key,value 类型是动态的。 
22type bmap struct {
23topbits  [8]uint8		//topbits: 是存储高八位的hash用于定位key在桶中的位置
24keys     [8]keytype		//keys: 所有的key 存放在一起 values
25values   [8]valuetype	//values: 所有的value 存放在一起
26pad      uintptr
27// bmap中最多放8个key8个value 多出的 用溢出指针，放到另外的bmap中 
28overflow uintptr		//overflow： 下一个桶的指针 这里一个桶只能存八个元素，就会存在overlow 中
29}
30//一个结构中只能放八个元素,超过八个则通过overflow连接到一个新的bmap 结构中超过8个会极大影响性能。
31// extra 会存溢出桶的信息， 下一个溢出桶的 指针 

 1type Map struct {
 2    // 加锁作用，保护 dirty 字段
 3    mu Mutex
 4    // 只读的数据，实际数据类型为 readOnly
 5    read atomic.Value
 6    // 最新写入的数据
 7    dirty map[interface{}]*entry
 8    // 计数器，每次需要读 dirty 则 +1
 9    misses int
10}
11
12type readOnly struct {
13// 内建 map
14m  map[interface{}]*entry
15// 表示 dirty 里存在 read 里没有的 key，通过该字段决定是否加锁读 dirty
16amended bool
17}

 1package main
 2
 3import (
 4	"sync"
 5)
 6
 7
 8func main() {
 9  type m2 struct {
10    num int
11  }
12  var mu sync.RWMutex
13  var m1 = make(map[int]*m2)
14  for i := 0; i < 10000; i++ {
15    go func(num int) {
16      mu.Lock()
17      m1[num] = &m2{num: num}
18      mu.Unlock()
19    }(i)
20  }
21  //var copyMap = make(map[int]*m2)
22  //
23  //mu.RLock()
24  //for key, value := range m1 {
25  //	copyMap[key] = value
26  //}
27  //mu.RUnlock()
28  for i := 0; i < 10000; i++ {
29    go func() {
30      for key, value := range m1 {
31        fmt.Println(key, value)
32      }
33    }()
34  }
35  select {}
36}

 1package main
 2
 3import (
 4  "sync"
 5)
 6
 7func main() {
 8  type m2 struct {
 9    num int
10  }
11  var mu sync.RWMutex
12  var m1 = make(map[int]*m2)
13  for i := 0; i < 10000; i++ {
14    go func(num int) {
15      mu.Lock()
16      m1[num] = &m2{num: num}
17      mu.Unlock()
18    }(i)
19  }
20  var copyMap = make(map[int]*m2)
21
22  mu.RLock()
23  for key, value := range m1 {
24    copyMap[key] = value
25  }
26  mu.RUnlock()
27  for i := 0; i < 10000; i++ {
28    go func() {
29      for key, value := range copyMap {
30        fmt.Println(key, value)
31      }
32    }()
33  }
34  select{}
35}

  1package cache
  2
  3// 分片加锁
  4
  5import (
  6	"sync"
  7)
  8
  9var ShardCount int64 = 32
 10
 11// ShardLockMaps A "thread" safe map of type string:Anything.
 12// To avoid lock bottlenecks this map is dived to several (ShardCount) map shards.
 13type ShardLockMaps struct {
 14	shards []*SingleShardMap
 15}
 16
 17// SingleShardMap A "thread" safe string to anything map.
 18type SingleShardMap struct {
 19	items map[int64]*UserCacheData
 20	sync.RWMutex
 21}
 22
 23// createShardLockMaps Creates a new concurrent map.
 24func createShardLockMaps() ShardLockMaps {
 25	slm := ShardLockMaps{
 26		shards: make([]*SingleShardMap, ShardCount),
 27	}
 28	for i := 0; i < int(ShardCount); i++ {
 29		slm.shards[i] = &SingleShardMap{items: make(map[int64]*UserCacheData)}
 30	}
 31	return slm
 32}
 33
 34// NewShardLockMaps Creates a new ShardLockMaps.
 35func NewShardLockMaps() ShardLockMaps {
 36	return createShardLockMaps()
 37}
 38
 39// GetShard returns shard under given key
 40func (slm ShardLockMaps) GetShard(key int64) *SingleShardMap {
 41	return slm.shards[key%ShardCount]
 42}
 43
 44// Count returns the number of elements within the map.
 45func (slm ShardLockMaps) Count() int {
 46	count := 0
 47	for i := int64(0); i < ShardCount; i++ {
 48		shard := slm.shards[i]
 49		shard.RLock()
 50		count += len(shard.items)
 51		shard.RUnlock()
 52	}
 53	return count
 54}
 55
 56// Get retrieves an element from map under given key.
 57func (slm ShardLockMaps) Get(key int64) (*UserCacheData, bool) {
 58	if key <= 0 {
 59		return nil, false
 60	}
 61	shard := slm.GetShard(key)
 62	shard.RLock()
 63	val, ok := shard.items[key]
 64	shard.RUnlock()
 65	return val, ok
 66}
 67
 68// Set Sets the given value under the specified key.
 69func (slm ShardLockMaps) Set(userData *UserCacheData) {
 70	if userData == nil {
 71		return
 72	}
 73	shard := slm.GetShard(userData.UserId)
 74	shard.Lock()
 75	shard.items[userData.UserId] = userData
 76	shard.Unlock()
 77}
 78
 79// Remove removes an element from the map.
 80func (slm ShardLockMaps) Remove(key int64) {
 81	if key <= 0 {
 82		return
 83	}
 84	shard := slm.GetShard(key)
 85	shard.Lock()
 86	delete(shard.items, key)
 87	shard.Unlock()
 88}
 89
 90// IsEmpty checks if map is empty.
 91func (slm ShardLockMaps) IsEmpty() bool {
 92	return slm.Count() == 0
 93}
 94
 95// Keys returns all keys as []int64
 96func (slm ShardLockMaps) Keys() []int64 {
 97	count := slm.Count()
 98	ch := make(chan int64, count)
 99	go func() {
100		wg := sync.WaitGroup{}
101		wg.Add(int(ShardCount))
102		for _, shard := range slm.shards {
103			go func(shard *SingleShardMap) {
104				shard.RLock()
105				for key := range shard.items {
106					ch <- key
107				}
108				shard.RUnlock()
109				wg.Done()
110			}(shard)
111		}
112		wg.Wait()
113		close(ch)
114	}()
115
116	keys := make([]int64, 0, count)
117	for k := range ch {
118		keys = append(keys, k)
119	}
120	return keys
121}
122
123// IterCb Iterator callback,called for every key,value found in maps.
124// RLock is held for all calls for a given shard
125// therefore callback sess consistent view of a shard,
126// but not across the shards
127type IterCb func(key int64, v *UserCacheData)
128
129// IterCb Callback based iterator, cheapest way to read
130// all elements in a map.
131func (slm ShardLockMaps) IterCb(fn IterCb) {
132	for idx := range slm.shards {
133		shard := slm.shards[idx]
134		shard.RLock()
135		for key, value := range shard.items {
136			fn(key, value)
137		}
138		shard.RUnlock()
139	}
140}