1.Linux内核源码解析---万字解析从设计模式推演per-cpu实现原理
2.Golang并发map？

Linux内核源码解析---万字解析从设计模式推演per-cpu实现原理

       引子

       在如今的底层p底大型服务器中，NUMA架构扮演着关键角色。源码它允许系统拥有多个物理CPU，层实不同NUMA节点之间通过QPI通信。底层p底虽然硬件连接细节在此不作深入讨论，源码但需明白每个CPU优先访问本节点内存，层实巴山财经源码当本地内存不足时，底层p底可向其他节点申请。源码从传统的层实SMP架构转向NUMA架构，主要是底层p底为了解决随着CPU数量增多而带来的总线压力问题。

       分配物理内存时，源码numa_node_id() 方法用于查询当前CPU所在的层实NUMA节点。频繁的底层p底内存申请操作促使Linux内核采用per-cpu实现，将CPU访问的源码变量复制到每个CPU中，以减少缓存行竞争和False Sharing，层实类似于Java中的Thread Local。

       分配物理页

       尽管我们不必关注底层实现，buddy system负责分配物理页，关键在于使用了numa_node_id方法。接下来，我们将深入探索整个Linux内核的per-cpu体系。

       numa_node_id源码分析获取数据

       在topology.h中，我们发现使用了raw_cpu_read函数，传入了numa_node参数。接下来，我们来了解numa_node的定义。

       在topology.h中定义了numa_node。我们继续跟踪DECLARE_PER_CPU_SECTION的定义，最终揭示numa_node是一个共享全局变量，类型为int，存储在.data..percpu段中。

       在percpu-defs.h中，numa_node被放置在ELF文件的.data..percpu段中，这些段在运行阶段即为段。接下来，我们返回raw_cpu_read方法。

       在percpu-defs.h中，我们继续跟进__pcpu_size_call_return方法，此方法根据per-cpu变量的大小生成回调函数。对于numa_node的int类型，最终拼接得到的是raw_cpu_read_4方法。

       在percpu.h中，调用了一般的read方法。在percpu.h中，获取numa_node的绝对地址，并通过raw_cpu_ptr方法。

       在percpu-defs.h中，我们略过验证指针的环节，追踪arch_raw_cpu_ptr方法。接下来，我们来看x架构的实现。

       在percpu.h中，使用汇编获取this_cpu_off的地址，代表此CPU内存副本到".data..percpu"的偏移量。加上numa_node相对于原始内存副本的偏移量，最终通过解引用获得真正内存地址内的值。

       对于其他架构，实现方式相似，通过获取自己CPU的javawebCRM系统源码偏移量，最终通过相对偏移得到pcp变量的地址。

       放入数据

       讨论Linux内核启动过程时，我们不得不关注per-cpu的值是如何被放入的。

       在main.c中，我们以x实现为例进行分析。通过setup_percpu.c文件中的代码，我们将node值赋给每个CPU的numa_node地址处。具体计算方法通过early_cpu_to_node实现，此处不作展开。

       在percpu-defs.h中，我们来看看如何获取每个CPU的numa_node地址，最终还是通过简单的偏移获取。需要注意如何获取每个CPU的副本偏移地址。

       在percpu.h中，我们发现一个关键数组__per_cpu_offset，其中保存了每个CPU副本的偏移值，通过CPU的索引来查找。

       接下来，我们来设计PER CPU模块。

       设计一个全面的PER CPU架构，它支持UMA或NUMA架构。我们设计了一个包含NUMA节点的结构体，内部管理所有CPU。为每个CPU创建副本，其中存储所有per-cpu变量。静态数据在编译时放入原始数据段，动态数据在运行时生成。

       最后，我们回到setup_per_cpu_areas方法的分析。在setup_percpu.c中，我们详细探讨了关键方法pcpu_embed_first_chunk。此方法管理group、unit、静态、保留、动态区域。

       通过percpu.c中的关键变量__per_cpu_load和vmlinux.lds.S的链接脚本，我们了解了per-cpu加载时的地址符号。PERCPU_INPUT宏定义了静态原始数据的起始和结束符号。

       接下来，我们关注如何分配per-cpu元数据信息pcpu_alloc_info。percpu.c中的方法执行后，元数据分配如下图所示。

       接着，我们分析pcpu_alloc_alloc_info的方法，完成元数据分配。

       在pcpu_setup_first_chunk方法中，我们看到分配的smap和dmap在后期将通过slab再次分配。

       在main.c的mm_init中，我们关注重点区域，完成map数组的slab分配。

       至此，我们探讨了Linux内核中per-cpu实现的原理，从设计到源码分析，全面展现了这一关键机制在现代服务器架构中的作用。

Golang并发map？

       Golang中sync.Map的实现原理

       前面，我们讲了map的用法以及原理Golang中map的实现原理，但我们知道，模块jar源码map在并发读写的情况下是不安全。需要并发读写时，一般的做法是加锁，但这样性能并不高，Go语言在1.9版本中提供了一种效率较高的并发安全的sync.Map，今天，我们就来讲讲sync.Map的用法以及原理

       sync.Map与map不同，不是以语言原生形态提供，而是在sync包下的特殊结构：

       我们下来看下sync.Map结构体

       结构体之间的关系如下图所示：

       总结一下：

       Load方法比较简单，总结一下：

       总结如下：

       golandmap底层原理

       map是Go语言中基础的数据结构，在日常的使用中经常被用到。但是它底层是如何实现的呢？

       总体来说golang的map是hashmap，是使用数组+链表的形式实现的，使用拉链法消除hash冲突。

       golang的map由两种重要的结构，hmap和bmap(下文中都有解释)，主要就是hmap中包含一个指向bmap数组的指针，key经过hash函数之后得到一个数，这个数低位用于选择bmap(当作bmap数组指针的下表)，高位用于放在bmap的[8]uint8数组中，用于快速试错。然后一个bmap可以指向下一个bmap(拉链)。

       Golang中map的底层实现是一个散列表，因此实现map的过程实际上就是实现散表的过程。在这个散列表中，主要出现的结构体有两个，一个叫hmap(aheaderforagomap)，一个叫bmap(abucketforaGomap，通常叫其bucket)。这两种结构的样子分别如下所示：

       hmap:

       图中有很多字段，但是便于理解map的架构，你只需要关心的只有一个，就是标红的字段：buckets数组。Golang的map中用于存储的结构是bucket数组。而bucket(即bmap)的结构是怎样的呢？

       bucket：

       相比于hmap，bucket的结构显得简单一些，标红的字段依然是“核心”，我们使用的map中的key和value就存储在这里。“高位哈希值”数组记录的是当前bucket中key相关的“索引”，稍后会详细叙述。还有一个字段是一个指向扩容后的bucket的指针，使得bucket会形成一个链表结构。例如下图：

       由此看出hmap和bucket的关系是这样的：

       而bucket又是一个链表，所以，整体的结构应该是这样的：

       哈希表的特点是会有一个哈希函数，对你传来的key进行哈希运算，得到唯一的值，一般情况下都是一个数值。Golang的map中也有这么一个哈希函数，也会算出唯一的值，对于这个值的使用，Golang也是很有意思。

       Golang把求得的值按照用途一分为二：高位和低位。

       如图所示，蓝色为高位，红色为低位。然后低位用于寻找当前key属于hmap中的哪个bucket，而高位用于寻找bucket中的追剧源码哪个key。上文中提到：bucket中有个属性字段是“高位哈希值”数组，这里存的就是蓝色的高位值，用来声明当前bucket中有哪些“key”，便于搜索查找。需要特别指出的一点是：我们map中的key/value值都是存到同一个数组中的。数组中的顺序是这样的:

       并不是key0/value0/key1/value1的形式，这样做的好处是：在key和value的长度不同的时候，可以消除padding(内存对齐)带来的空间浪费。

       现在，我们可以得到Go语言map的整个的结构图了：(hash结果的低位用于选择把KV放在bmap数组中的哪一个bmap中，高位用于key的快速预览，用于快速试错)

       map的扩容

       当以上的哈希表增长的时候，Go语言会将bucket数组的数量扩充一倍，产生一个新的bucket数组，并将旧数组的数据迁移至新数组。

       加载因子

       判断扩充的条件，就是哈希表中的加载因子(即loadFactor)。

       加载因子是一个阈值，一般表示为：散列包含的元素数除以位置总数。是一种“产生冲突机会”和“空间使用”的平衡与折中：加载因子越小，说明空间空置率高，空间使用率小，但是加载因子越大，说明空间利用率上去了，但是“产生冲突机会”高了。

       每种哈希表的都会有一个加载因子，数值超过加载因子就会为哈希表扩容。

       Golang的map的加载因子的公式是：map长度/2^B(这是代表bmap数组的长度，B是取的低位的位数)阈值是6.5。其中B可以理解为已扩容的次数。

       当Go的map长度增长到大于加载因子所需的map长度时，Go语言就会将产生一个新的bucket数组，然后把旧的bucket数组移到一个属性字段oldbucket中。注意：并不是立刻把旧的数组中的元素转义到新的bucket当中，而是，只有当访问到具体的某个bucket的时候，会把bucket中的数据转移到新的bucket中。

       如下图所示：当扩容的时候，Go的map结构体中，会保存旧的数据，和新生成的数组

       上面部分代表旧的有数据的bucket，下面部分代表新生成的新的bucket。蓝色代表存有数据的bucket，橘**代表空的bucket。

       扩容时map并不会立即把新数据做迁移，而是当访问原来旧bucket的数据的时候，才把旧数据做迁移，如下图：

       注意：这里并不会直接删除旧的bucket，而是把原来的引用去掉，利用GC清除内存。

       map中数据的删除

       如果理解了map的整体结构，那么查找、更新、删除的基本步骤应该都很清楚了。这里不再赘述。

       值得注意的是，找到了map中的数据之后，针对key和value分别做如下操作：

       1

       2

       3

       4

       1、AE手脚源码如果``key``是一个指针类型的，则直接将其置为空，等待GC清除；

       2、如果是值类型的，则清除相关内存。

       3、同理，对``value``做相同的操作。

       4、最后把key对应的高位值对应的数组index置为空。

       下面先写一段测试程序，然后看下运行结果：

       运行结果：

       发生了错误，提示：fatalerror:concurrentmapreadandmapwrite，map发生了同时读和写了；但是这个错误并不是每次运行都会出现，就是有的时候会出现，有的时候并不会出现，根据笔者多次运行结果(其他例子，读者可以自己尝试下)来看还会有另外一种报错就是：fatalerror:concurrentmapwrites，就是map发生了同时写，但是只是读是不会有问题的。关于不同的运行结果小伙伴们可以自己写几个例子去测试下。下面就这两个错误的发生，笔者给出如下解释：

       （1）fatalerror:concurrentmapreadandmapwrite

       就是当一个goroutine在写数据，而同时另外一个goroutine要读数据就会报错，不过这个报错也很好理解：还没写完就读，读的数据会有问题，或者反过来还没读完就开始写了，同样会导致读取的数据有问题；

       （2）fatalerror:concurrentmapwrites

       两个goroutine同时写一个内存地址，这种操作也是不允许的，会导致一些比较奇怪的问题；

       总体来看其实就是写map的操作和其他的读或者写同时发生了，导致的报错，做过几年开发的人可能会想到使用锁来解决，比如写map某个key的时候，通过锁来保证其他goroutine不能再对其写或者读了。

       实现思路：

       （1）当写map的某个key时，通过锁来保证其他goroutine不能再对其写或者读了。

       （2）当读map的某个key时，通过锁来保证其他的goroutine不能再对其写，但是可以读。

       于是我们马上想到golang的读写锁貌似符合需求，下面来实现下：

       再来看下运行结果：

       发现没有报错了，并且多次运行的结果都不会报错，说明这个方法是有用的，不过在go1.9版本后就有sync.Map了，不过这个适用场景是读多写少的场景，如果写很多的话效率比较差，具体的原因在这里笔者就不介绍了，后面会写篇文章详细介绍下。

       今天的文章就到这里了，如果有不对的地方欢迎小伙伴给我留言，看到会即时回复的。

       本文目录如下，阅读本文后，将一网打尽下面GolangMap相关面试题

       Go中的map是一个指针，占用8个字节，指向hmap结构体;源码src/runtime/map.go中可以看到map的底层结构

       每个map的底层结构是hmap，hmap包含若干个结构为bmap的bucket数组。每个bucket底层都采用链表结构。接下来，我们来详细看下map的结构

       bmap就是我们常说的“桶”，一个桶里面会最多装8个key，这些key之所以会落入同一个桶，是因为它们经过哈希计算后，哈希结果是“一类”的，关于key的定位我们在map的查询和插入中详细说明。在桶内，又会根据key计算出来的hash值的高8位来决定key到底落入桶内的哪个位置（一个桶内最多有8个位置)。

       bucket内存数据结构可视化如下：

       注意到key和value是各自放在一起的，并不是key/value/key/value/...这样的形式。源码里说明这样的好处是在某些情况下可以省略掉padding字段，节省内存空间。

       当map的key和value都不是指针，并且size都小于字节的情况下，会把bmap标记为不含指针，这样可以避免gc时扫描整个hmap。但是，我们看bmap其实有一个overflow的字段，是指针类型的，破坏了bmap不含指针的设想，这时会把overflow移动到extra字段来。

       map是个指针，底层指向hmap，所以是个引用类型

       golang有三个常用的高级类型slice、map、channel,它们都是引用类型，当引用类型作为函数参数时，可能会修改原内容数据。

       golang中没有引用传递，只有值和指针传递。所以map作为函数实参传递时本质上也是值传递，只不过因为map底层数据结构是通过指针指向实际的元素存储空间，在被调函数中修改map，对调用者同样可见，所以map作为函数实参传递时表现出了引用传递的效果。

       因此，传递map时，如果想修改map的内容而不是map本身，函数形参无需使用指针

       map底层数据结构是通过指针指向实际的元素存储空间，这种情况下，对其中一个map的更改，会影响到其他map

       map在没有被修改的情况下，使用range多次遍历map时输出的key和value的顺序可能不同。这是Go语言的设计者们有意为之，在每次range时的顺序被随机化，旨在提示开发者们，Go底层实现并不保证map遍历顺序稳定，请大家不要依赖range遍历结果顺序。

       map本身是无序的，且遍历时顺序还会被随机化，如果想顺序遍历map，需要对mapkey先排序，再按照key的顺序遍历map。

       map默认是并发不安全的，原因如下：

       Go官方在经过了长时间的讨论后，认为Gomap更应适配典型使用场景（不需要从多个goroutine中进行安全访问），而不是为了小部分情况（并发访问），导致大部分程序付出加锁代价（性能），决定了不支持。

       场景:2个协程同时读和写，以下程序会出现致命错误：fatalerror:concurrentmapwrites

       如果想实现map线程安全，有两种方式：

       方式一：使用读写锁map+sync.RWMutex

       方式二：使用golang提供的sync.Map

       sync.map是用读写分离实现的，其思想是空间换时间。和map+RWLock的实现方式相比，它做了一些优化：可以无锁访问readmap，而且会优先操作readmap，倘若只操作readmap就可以满足要求(增删改查遍历)，那就不用去操作writemap(它的读写都要加锁)，所以在某些特定场景中它发生锁竞争的频率会远远小于map+RWLock的实现方式。

       golang中map是一个kv对集合。底层使用hashtable，用链表来解决冲突，出现冲突时，不是每一个key都申请一个结构通过链表串起来，而是以bmap为最小粒度挂载，一个bmap可以放8个kv。在哈希函数的选择上，会在程序启动时，检测cpu是否支持aes，如果支持，则使用aeshash，否则使用memhash。

       map有3钟初始化方式，一般通过make方式创建

       map的创建通过生成汇编码可以知道，make创建map时调用的底层函数是runtime.makemap。如果你的map初始容量小于等于8会发现走的是runtime.fastrand是因为容量小于8时不需要生成多个桶，一个桶的容量就可以满足

       makemap函数会通过fastrand创建一个随机的哈希种子，然后根据传入的hint计算出需要的最小需要的桶的数量，最后再使用makeBucketArray创建用于保存桶的数组，这个方法其实就是根据传入的B计算出的需要创建的桶数量在内存中分配一片连续的空间用于存储数据，在创建桶的过程中还会额外创建一些用于保存溢出数据的桶，数量是2^(B-4)个。初始化完成返回hmap指针。

       找到一个B，使得map的装载因子在正常范围内

       Go语言中读取map有两种语法：带comma和不带comma。当要查询的key不在map里，带comma的用法会返回一个bool型变量提示key是否在map中；而不带comma的语句则会返回一个value类型的零值。如果value是int型就会返回0，如果value是string类型，就会返回空字符串。

       map的查找通过生成汇编码可以知道，根据key的不同类型，编译器会将查找函数用更具体的函数替换，以优化效率：

       函数首先会检查map的标志位flags。如果flags的写标志位此时被置1了，说明有其他协程在执行“写”操作，进而导致程序panic。这也说明了map对协程是不安全的。

       key经过哈希函数计算后，得到的哈希值如下（主流位机下共个bit位）：

       m:桶的个数

       从buckets通过hashm得到对应的bucket，如果bucket正在扩容，并且没有扩容完成，则从oldbuckets得到对应的bucket

       计算hash所在桶编号：

       用上一步哈希值最后的5个bit位，也就是，值为，也就是号桶（范围是0~号桶）

       计算hash所在的槽位:

       用上一步哈希值哈希值的高8个bit位，也就是，转化为十进制，也就是，在号bucket中寻找**tophash值（HOBhash）为*的槽位**，即为key所在位置，找到了2号槽位，这样整个查找过程就结束了。

       如果在bucket中没找到，并且overflow不为空，还要继续去overflowbucket中寻找，直到找到或是所有的key槽位都找遍了，包括所有的overflowbucket。

       通过上面找到了对应的槽位，这里我们再详细分析下key/value值是如何获取的：

       bucket里key的起始地址就是unsafe.Pointer(b)+dataOffset。第i个key的地址就要在此基础上跨过i个key的大小；而我们又知道，value的地址是在所有key之后，因此第i个value的地址还需要加上所有key的偏移。

       通过汇编语言可以看到，向map中插入或者修改key，最终调用的是mapassign函数。

       实际上插入或修改key的语法是一样的，只不过前者操作的key在map中不存在，而后者操作的key存在map中。

       mapassign有一个系列的函数，根据key类型的不同，编译器会将其优化为相应的“快速函数”。

       我们只用研究最一般的赋值函数mapassign。

       map的赋值会附带着map的扩容和迁移，map的扩容只是将底层数组扩大了一倍，并没有进行数据的转移，数据的转移是在扩容后逐步进行的，在迁移的过程中每进行一次赋值（access或者delete）会至少做一次迁移工作。

       1.判断map是否为nil

       每一次进行赋值/删除操作时，只要oldbuckets!=nil则认为正在扩容，会做一次迁移工作，下面会详细说下迁移过程

       根据上面查找过程，查找key所在位置，如果找到则更新，没找到则找空位插入即可

       经过前面迭代寻找动作，若没有找到可插入的位置，意味着需要扩容进行插入，下面会详细说下扩容过程

       通过汇编语言可以看到，向map中删除key，最终调用的是mapdelete函数

       删除的逻辑相对比较简单，大多函数在赋值操作中已经用到过，核心还是找到key的具体位置。寻找过程都是类似的，在bucket中挨个cell寻找。找到对应位置后，对key或者value进行“清零”操作，将count值减1，将对应位置的tophash值置成Empty

       再来说触发map扩容的时机：在向map插入新key的时候，会进行条件检测，符合下面这2个条件，就会触发扩容：

       1、装载因子超过阈值

       源码里定义的阈值是6.5(loadFactorNum/loadFactorDen)，是经过测试后取出的一个比较合理的因子

       我们知道，每个bucket有8个空位，在没有溢出，且所有的桶都装满了的情况下，装载因子算出来的结果是8。因此当装载因子超过6.5时，表明很多bucket都快要装满了，查找效率和插入效率都变低了。在这个时候进行扩容是有必要的。

       对于条件1，元素太多，而bucket数量太少，很简单：将B加1，bucket最大数量(2^B)直接变成原来bucket数量的2倍。于是，就有新老bucket了。注意，这时候元素都在老bucket里，还没迁移到新的bucket来。新bucket只是最大数量变为原来最大数量的2倍(2^B*2)。

       2、overflow的bucket数量过多

       在装载因子比较小的情况下，这时候map的查找和插入效率也很低，而第1点识别不出来这种情况。表面现象就是计算装载因子的分子比较小，即map里元素总数少，但是bucket数量多（真实分配的bucket数量多，包括大量的overflowbucket）

       不难想像造成这种情况的原因：不停地插入、删除元素。先插入很多元素，导致创建了很多bucket，但是装载因子达不到第1点的临界值，未触发扩容来缓解这种情况。之后，删除元素降低元素总数量，再插入很多元素，导致创建很多的overflowbucket，但就是不会触发第1点的规定，你能拿我怎么办？overflowbucket数量太多，导致key会很分散，查找插入效率低得吓人，因此出台第2点规定。这就像是一座空城，房子很多，但是住户很少，都分散了，找起人来很困难

       对于条件2，其实元素没那么多，但是overflowbucket数特别多，说明很多bucket都没装满。解决办法就是开辟一个新bucket空间，将老bucket中的元素移动到新bucket，使得同一个bucket中的key排列地更紧密。这样，原来，在overflowbucket中的key可以移动到bucket中来。结果是节省空间，提高bucket利用率，map的查找和插入效率自然就会提升。

       由于map扩容需要将原有的key/value重新搬迁到新的内存地址，如果有大量的key/value需要搬迁，会非常影响性能。因此Gomap的扩容采取了一种称为“渐进式”的方式，原有的key并不会一次性搬迁完毕，每次最多只会搬迁2个bucket。

       上面说的hashGrow()函数实际上并没有真正地“搬迁”，它只是分配好了新的buckets，并将老的buckets挂到了oldbuckets字段上。真正搬迁buckets的动作在growWork()函数中，而调用growWork()函数的动作是在mapassign和mapdelete函数中。也就是插入或修改、删除key的时候，都会尝试进行搬迁buckets的工作。先检查oldbuckets是否搬迁完毕，具体来说就是检查oldbuckets是否为nil。

       如果未迁移完毕，赋值/删除的时候，扩容完毕后（预分配内存），不会马上就进行迁移。而是采取增量扩容的方式，当有访问到具体bukcet时，才会逐渐的进行迁移（将oldbucket迁移到bucket）

       nevacuate标识的是当前的进度，如果都搬迁完，应该和2^B的长度是一样的

       在evacuate方法实现是把这个位置对应的bucket，以及其冲突链上的数据都转移到新的buckets上。

       转移的判断直接通过tophash就可以，判断tophash中第一个hash值即可

       遍历的过程，就是按顺序遍历bucket，同时按顺序遍历bucket中的key。

       map遍历是无序的，如果想实现有序遍历，可以先对key进行排序

       为什么遍历map是无序的？

       如果发生过迁移，key的位置发生了重大的变化，有些key飞上高枝，有些key则原地不动。这样，遍历map的结果就不可能按原来的顺序了。

       如果就一个写死的map，不会向map进行插入删除的操作，按理说每次遍历这样的map都会返回一个固定顺序的key/value序列吧。但是Go杜绝了这种做法，因为这样会给新手程序员带来误解，以为这是一定会发生的事情，在某些情况下，可能会酿成大错。

       Go做得更绝，当我们在遍历map时，并不是固定地从0号bucket开始遍历，每次都是从一个**随机值序号的bucket开始遍历，并且是从这个bucket的一个随机序号的cell**开始遍历。这样，即使你是一个写死的map，仅仅只是遍历它，也不太可能会返回一个固定序列的key/value对了。