Go语言sync.Map实现
Go语言sync.Map实现
Go语言原生map并不是线程安全的，对它进行并发读写操作的时候，需要加锁。
而sync.map则是一种并发安全的map，在Go1.9引入。
sync.map是线程安全的，读取，插入，删除也都保持着常数级的时间复杂度。
sync.map的零值是有效的，并且零值是一个空的map。在第一次使用之后，不允许被拷贝。
一般情况下解决并发读写map的思路是加一把大锁，或者把一个map分成若干个小map，对key进行哈希，只操作相应的小map。前者锁的粒度比较大，影响效率；后者实现起来比较复杂，容易出错。
而使用sync.map之后，对map的读写，不需要加锁。并且它通过空间换时间的方式，使用read和dirty两个map来进行读写分离，降低锁时间来提高效率。
数据结构：
互斥量mu保护read和dirty。
read是atomic.Value类型，可以并发地读。但如果需要更新read，则需要加锁保护。对于read中存储的entry字段，可能会被并发地CAS更新。但是如果要更新一个之前已被删除的entry，则需要先将其状态从expunged改为nil，再拷贝到dirty中，然后再更新。
dirty是一个非线程安全的原始map。包含新写入的key，并且包含read中的所有未被删除的key。这样，可以快速地将dirty提升为read对外提供服务。如果dirty为nil，那么下一次写入时，会新建一个新的dirty，这个初始的dirty是read的一个拷贝，但除掉了其中已被删除的key。
每当从read中读取失败，都会将misses的计数值加1，当加到一定阈值以后，需要将dirty提升为read，以期减少miss的情形。
readmap和dirtymap的存储方式是不一致的。
前者使用atomic.Value，后者只是单纯的使用map。
原因是readmap使用lockfree操作，必须保证load/store的原子性；而dirtymap的load+store操作是由lock（就是mu）来保护的。
它是一个指针，指向value。
read和dirty各自维护一套key，key指向的都是同一个value。也就是说，只要修改了这个entry，对read和dirty都是可见的。这个指针的状态有三种：
当p==nil时，说明这个键值对已被删除，并且m.dirty==nil，或m.dirty[k]指向该entry。
当p==expunged时，说明这条键值对已被删除，并且m.dirty!=nil，且m.dirty中没有这个key。
其他情况，p指向一个正常的值，表示实际interface{}的地址，并且被记录在m.read.m[key]中。如果这时m.dirty不为nil，那么它也被记录在m.dirty[key]中。两者实际上指向的是同一个值。
当删除key时，并不实际删除。一个entry可以通过原子地（CAS操作）设置p为nil被删除。如果之后创建m.dirty，nil又会被原子地设置为expunged，且不会拷贝到dirty中。
如果p不为expunged，和entry相关联的这个value可以被原子地更新；如果p==expunged，那么仅当它初次被设置到m.dirty之后，才可以被更新。
expunged：varexpunged=unsafe.Pointer(new(interface{}))
它是一个指向任意类型的指针，用来标记从dirtymap中删除的entry。
Store流程：
①read中未找到待存储的key，且p!=expunged→未被删除，直接更新对应的entry。
②若①未成功：要么read中不存在这个key，要么key被标记为删除。则先加锁，再操作。
③再在read中查找key，doublecheck一下。
A.存在key，p==expunged，说明m.dirty!=nil且m.dirty中不存在该key值。此时:
a. 将p的状态由expunged更改为nil；
b. dirtymap插入key。然后，直接更新对应的value。
B.不存在key，查看dirty中是否有此key，如果有，则直接更新对应的value，这时read中还是没有此key。
④如果read和dirty中都不存在该key，则：
a. 如果dirty为空，则需要创建dirty，并从read中拷贝未被删除的元素；
b. 更新amended字段，标识dirtymap中存在readmap中没有的key；
c. 将k-v写入dirtymap中，read.m不变。最后，更新此key对应的value。
tryStore在Store函数最开始的时候就会调用，是比较常见的for循环加CAS操作，尝试更新entry，让p指向新的值。
unexpungeLocked函数确保了entry没有被标记成已被清除。
Load：
处理路径分为fastpath和slowpath，整体流程如下：
①首先是fastpath，直接在read中找，如果找到了直接调用entry的load方法，取出其中的值。
②如果read中没有这个key，且amended为fase，说明dirty为空，那直接返回空和false。
③如果read中没有这个key，且amended为true，说明dirty中可能存在我们要找的key。当然要先上锁，再尝试去dirty中查找。在这之前，仍然有一个doublecheck的操作。若还是没有在read中找到，那么就从dirty中找。不管dirty中有没有找到，都要"记一笔"，因为在dirty被提升为read之前，都会进入这条路径。
Delete：
先从read里查是否有这个key，如果有则执行entry.delete方法，将p置为nil，这样read和dirty都能看到这个变化。
如果没在read中找到这个key，并且dirty不为空，那么就要操作dirty了，操作之前，还是要先上锁。然后进行doublecheck，如果仍然没有在read里找到此key，则从dirty中删掉这个key。但不是真正地从dirty中删除，而是更新entry的状态。
tryExpungeLocked是在新创建dirty时调用的，会将已被删除的entry.p从nil改成expunged，这个entry就不会写入dirty了。
注意到如果key同时存在于read和dirty中时，删除只是做了一个标记，将p置为nil；而如果仅在dirty中含有这个key时，会直接删除这个key。原因在于，若两者都存在这个key，仅做标记删除，可以在下次查找这个key时，命中read，提升效率。若只有在dirty中存在时，read起不到“缓存”的作用，直接删除。
LoadOrStore
这个函数结合了Load和Store的功能，如果map中存在这个key，那么返回这个key对应的value；否则，将key-value存入map。这在需要先执行Load查看某个key是否存在，之后再更新此key对应的value时很有效，因为LoadOrStore可以并发执行。
Range：
Range将遍历调用时刻map中的所有k-v对，将它们传给f函数，如果f返回false，将停止遍历。
当amended为true时，说明dirty中含有read中没有的key，因为Range会遍历所有的key，是一个O(n)操作。将dirty提升为read，会将开销分摊开来，所以这里直接就提升了。
之后，遍历read，取出entry中的值，调用f(k,v)。
总结
除了Load/Store/Delete之外，sync.Map还提供了LoadOrStore/Range操作，但没有提供Len()方法，这是因为要统计有效的键值对只能先提升dirtymap(dirtymap中可能有readmap中没有的键值对)，再遍历m.read(由于延迟删除，不是所有的键值对都有效)，这其实就是Range做的事情，因此在不添加新数据结构支持的情况下，sync.Map的长度获取和Range操作是同一复杂度的。这部分只能看官方后续支持。
sync.Map实现上并不是特别复杂，但仍有很多值得借鉴的地方:
①通过entry隔离map变更和value变更，并且readmap和dirtymap指向同一个entry,这样更新readmap已有值无需加锁
②doublechecking
③延迟删除key，通过标记避免修改readmap，同时极大提升了删除key的效率(删除readmap中存在的key是无锁操作)
④延迟创建dirtymap，并且通过p的nil和expunged，amended字段来加强对dirtymap状态的把控，减少对dirtymap不必要的使用。
