一、Golang 的 slice、map、channel

1.1 slice vs array

a := make([]int, 100) //切片
b := [100]int{} //数组

array需指明长度，长度为常量且不可改变
array长度为其类型中的组成部分（给参数为长度100的数组的方法传长度为101的会报错）
array在作为函数参数时会产生copy
golang所有函数参数都是值传递

array扩容：cap<1024时乘2，否则乘1.25，预先分配内存可以提升性能，直接使用index赋值而不是append可以提升性能

slice作为参数被修改时，如果没有发生扩容，修改在原来的内存中；如果发生了扩容，修改会在新的内存中。

使用[]Type{}或者make([]Type)初始化后，slice不为nil；使用var x[]Type后，slice为nil

1.2 Map：

map的值其实是指针，传map传的是指针，所以修改会影响整个map。
map的k、v都不可取地址，随着map的扩容地址会改变。map存的是值，会发生copy，因此不要在map里放很大的数组，很大的可以用指针来代替
map赋值会自动扩容，但删除时不会自动缩容。
map非线程安全，不能同时读写。

1.3 Channel

有锁
缓冲channel和非缓冲的区别，缓冲会发生两次copy，非缓冲发生一次
for+select closed channel会造成死循环，select中的break无法跳出for循环

二、GOTT best practices

2.1 可读性

  • if else 和 happy path：有错误应该提前返回，尽量在正确返回时，不加 indents（缩进）。
  • init() 使用规范：在一些 package 中尽量不要使用 init()，定义一个可以被调用的 Initxxx() 函数显示调用，防止运行一些使用方不知道的代码段。
  • Comments：尽量写函数做了什么，而不是怎么做的。

2.2 健壮性

  • panic: 在 defer 中进行 recover()
  • Errors：使用 errors.Is() 和 errors.As() 来判断 error 和断言 error
    相关文档

2.3 效率

  1. 指针：函数修改参数，应该传递指针；参数中含有大量的内容，避免拷贝可以传递指针；代码风格对齐，其他函数都是传递指针的；
    Tricks：结构体默认传递指针；对于 for 中定义的变量在循环中会变，取其地址得到的值永远是最后一个。
  2. Deprecation：对于要废弃的函数，使用以下注释格式，从而使得 golintci-lint 能够检测而出来。
// comments for the function
//
// Deprecated: use $funcName instead.
func funcToBeDeprecated(){
}
三、Golang 的强人锁难

锁的重要性：并发场景通过 goroutine 和 channel 来实现，但是 goroutine 之间可以共享内存和变量，导致直接修改变量的时候，会存在冲突。使用锁需要考虑的：性能、重入、公平

3.1 强人：最佳实践

  • 减少持有时间，缩小临界区
    可以的情况下尽量提前释放，或者新定义一个函数，函数内部执行临界区，以及上锁释放锁，函数后进行其他的逻辑操作
  • 优化锁的粒度
    空间换时间，分片操作，每个片加锁。
  • 读写分离
    RWMutex；sync.Map(空间换时间)
  • 使用原子操作，避免使用锁
    atomic

3.2 锁难：避免踩坑

go test\run\build\install -race xxx

3.3 暗黑：锁的进化

  • 原子操作
    • 古代：英特尔 80386 处理器，因为是单核处理器，所以只需要锁CPU，关闭中断开关，这样操作就不会被中断，操作完再打开中断开关。低效：需要内核态来操作中断开关
    • 近代：汇编代码提供了 CMPXCHGL 指令，在该指令前加一个 Lock 前缀，会锁定内存总线。低效：内存总线称为瓶颈
    • 现代：MESI 缓存一致性协议（降低锁的粒度：总线锁->缓存行锁）。缓存行的状态，由硬件同步。MESI 为 Modified, Exclusive, Shared, Invalid 缩写。
      • Invalid：无效。初始化状态，或者内存不可用（被其他CPU修改，需要更新缓存）
      • Exclusive：独占。仅当前CPU缓存了该内存。
      • Shared：共享。多个CPU缓存了该内存。
      • Modified：已修改、未写回。需要其他CPU的缓存失效。某个CPU更新了缓存，但是还没写回内存，其他CPU缓存的该内存信息更新为 Invalid。
状态转移图
  • 自旋锁（Spin Lock）
    • Linux 内核中常见，适合等待时间比较小的场景
    • Go 1.14 版本之前，没有实现抢占式调度，必须某个 goroutine 交出控制权，因此自旋锁会导致死锁。如下图：A等待B释放锁，但是执行了GC，然后B被挂起，runtime需要等待A挂起，但是A在执行自旋锁，就发生了死锁。需要在自旋锁内部调用一次 runtime.GoSched 来交出 CPU 控制权
自旋锁死锁样例
  • Go's Mutex
    • 效率优先，兼顾公平。

    • Mutex 有自己的一个等待队列，有自己的状态 state（正常模式和饥饿模式）。正常模式保证效率，饥饿模式保证公平。state是一个共用字段，由锁标志位，唤醒标志位，饥饿标志位和阻塞的goroutine个数组成。


      Go's Mutex State 字段组成（mutexLocked mutexWoken mutexStarving 位为 1 分别表示锁占用、锁唤醒、饥饿模式、mutexWaiterShift 表示偏移量，默认为3，state>>=mutexWaiterShift，state的值就表示当前阻塞等待锁的goroutine个数。最多可以阻塞2^29个goroutine）
    • 正常模式：goroutine等待队列先进先出；新来的goroutine先去抢占锁，失败了再进入等待队列；如果发现某个抢到锁的 goroutine 等待时长 > 1ms，则切换到饥饿模式。
    • 饥饿模式：严格排队，队首接盘；牺牲效率，保证Pct99；适时回归正常模式，保证效率。如果某个goroutine加锁成功后，如果发现这个goroutine位于队尾，或者等待时间小于1ms，那么就切换回正常模式。
    • 提高效率的点：1. 新来的先去抢锁，减少了调度开销。2. 充分利用缓存，提高执行效率。
加锁流程
state位定义
自旋流程
加锁流程
解锁流程1(Slow)
解锁流程2
总结
  • Go's Once
type Once struct {
    done uint32
    m    Mutex
}

func (o *Once) Do(f func()) {
    if atomic.LoadUint32(&o.done) == 0 {
        // Outlined slow-path to allow inlining of the fast-path.
        o.doSlow(f)
    }
}
func (o *Once) doSlow(f func()) {
    o.m.Lock()
    defer o.m.Unlock()
    if o.done == 0 {
        defer atomic.StoreUint32(&o.done, 1)
        f()
    }
}

  • 源码很简单，如上：

    • 问题：1. 为什么 Do 里面用 atomic，doSlow 里面用 o.done==0？2. 为什么 doSlow 里面用 atomic 来设置 done？3. 为什么 doSlow 里面用 defer 设置值？可否直接设置？
    • 解答：1. Do 里面没有加锁，如果直接 o.done == 0 可能观测到非常规值，使用 atomic 保证操作有序。而 doSlow 里面已经是锁内部，不可能存在其他的 goroutine 修改值，因此可以直接观测。2. 由于可能存在其他 goroutine 在 Do 内观测 done 的值，因此需要 atomic 设置值来保证有序性。3. 不可以直接设置，如果直接设置值再执行f，那么可能 f 还没执行，别的 goroutine 已经观测到 done 为 1，直接 Do 中返回，但是由于 f 的初始化函数还没完成，从而导致 panic（空指针等）。因此在 f 未执行完的过程中，所有执行 once.Do 的 goroutine 都被阻塞在 doSlow 的 Lock 阶段，等待 f 执行完成才可以返回。
    • 异常：假设 Do 使用 o.done == 0 来观测值，读取的同时当 atomic 正在修改值时，读取到的值可能是异常值；假设使用 o.done=1 来设定值，执行的同时当其他 goroutine 在 Do 中读取 o.done 时，可能看到异常值。
    • 总结：这里的两个 atomic 是为了保证多个 goroutine 观测和设定同时发生的有序性。而锁操作的临界区内可以直接观测变量值。

  • Go's WaitGroup
    下文 第八部分。巧妙地避免了锁的使用。

  • 锁的进化总结
    单核：关中断->CAS指令
    多核：LOCK内存总线->MESI协议
    自旋锁：效率和公平不够好
    Go Mutex：效率优先，兼顾公平。

  • 思考探索

思考探索
  • 延伸阅读
四、Golang 并发数据结构和算法实践

引言

scalable：当计算资源更多时，性能会有提升


Golang数据结构并发测试(-x代表使用的CPU数)

4.1 并发安全问题

  • Data Race
    原因：多个 goroutine 同时接触一个变量，行为不可预知。
    认定条件：两个及以上 goroutine
    一写多读：atomic
    多写一读：Lock + atomic
    多写多读：Lock + atomic

4.2 实践一：有序链表并行化

定义插入删除的多个步骤，举例不同场景，考虑并发情况下是否满足，如何调整步骤。

4.3 实践二：skiplist并行化

从 4.2 延伸过来，每一层的 list 都可以使用 4.2 的实现。

4.4 总结

五、Golang 并发数据结构和算法实践

5.1 调度循环的建立

  • GM 模型和 GMP 模型
  • 调度循环的建立
调度循环的建立

5.2 协作与抢占

  • 调度器的坑
    go 运行一个死循环在 go1.13 版本会被卡死，go1.14 引入基于信号的抢占，从而不会被卡死。

  • Go 的调度方式
    协作式调度：依靠被调度放主动弃权
    抢占式调度：依靠调度器强制将被调度方中断
    s


    Go的调度方式
基于信号的抢占
  • 小结
协作与抢占小结
六、垃圾回收和Golang内存管理

6.1 GC基本理论

  • 自动内存管理：Reference Counting 引用计数法；Tracing GC
  • Tracing GC：
    • 目标：找出活的对象，剩下的就是垃圾。
    • 两部分：GC root 和 GC heap。
    • 风格：Copying GC 和 Mark-Sweep GC。
    • 并发：Concurrent GC(GC过程用户代码不需要停下来) 和 Parallel GC(GC过程中用户代码暂停)

6.2 Go内存管理

Go GC简史

历史

  • Go 1.10 版本以前采用的方式是线性内存。所有申请的内存以Page方式分割，每个Span管理一个或者多个Page。Golang垃圾回收的时候，会通过判断指针的地址来判断对象是否在堆中。之后弃用原因：1. 在C,Go混用时,分配的内存地址会发生冲突,导致堆得初始化和扩容失败；2. 没有被预留的大块内存可能会被分配给 C 语言，导致扩容后的堆不连续。
  • Go 1.10 之后采用稀疏内存管理。

分配

  • 关键词
    • Tcmalloc 风格分配器：thread cache 分配器、三级内存管理
    • 按照不同大小分类：Tiny(8), Small(16~32K), Huge(>32K)
    • mcache 来减轻锁的开销（每个处理器 P 维护一段内存）
    • 内外部碎片
    • Object 定位
    • Bitmap 标记
  • 总览
    • Go在程序启动时，会向操作系统申请一大块内存，之后自行管理。
    • Go内存管理的基本单元是mspan，它由若干个页组成，每种mspan可以分配特定大小的object。
      mcache, mcentral, mheap是Go内存管理的三大组件，层层递进。mcache管理线程在本地缓存的mspan；mcentral管理全局的mspan供所有线程使用；mheap管理Go的所有动态分配内存。
    • 极小对象(小于16字节)会分配在一个object中，以节省资源，使用tiny分配器分配内存；一般小对象(16字节到32768字节)通过mspan分配内存，根据对象大小选择对应的额mspan；大对象(大于32768字节)则直接由mheap分配内存，并记录 spanClass=0。
      • 微对象 (0, 16B) — 先使用微型分配器，再依次尝试线程缓存、中心缓存和堆分配内存；（注：对于(0, 16B) 的指针对象，直接归类为小对象。微型分配器不分配指针类型对象）
      • 小对象 [16B, 32KB] — 依次尝试使用线程缓存、中心缓存和堆分配内存；
      • 大对象 (32KB, +∞) — 直接在堆上分配内存；
  • 详解
    与TCMalloc非常类似.Golang内存分配由mspan,mcache,mcentral,mheap组成。可以说基本对应了TCMalloc中的Span,Pre-Thread,Central Free List,以及Page Heap。分配逻辑也很像TCMalloc中依次向前端,中端,后端请求内存。
Golang内存管理组件
type spanClass uint8alloc [numSpanClasses]*mspanmheap_.central[spc].mcentral.cacheSpan()

回收

Go GC
  • STW Mark
  • Concurrent mark
  • Mark-Sweep
    • 三色法 黑灰白：黑 标活且内容全部扫描完；灰 标活且内容未扫描完；白 未扫描到
  • Non-generational
何时触发回收
  • GOGC threshold。阈值，假设设定 export GOGC=100，那么每次GC结束后，剩余活对象的内存占用空间的两倍(1+$(GOGC)%)作为下次GC的阈值，达到或者超过，则启动GC
  • runtime.GC()
  • runtime.forcegcperiod(2min)

3.编程者指南

六、性能 pprof 工具
pprof工具
go tool pprof -http=:8080/profile/heap
七、缓存相关

1. local cache

local cache 对比
local 选型

大key问题：

  1. 考虑拆分成多个key来存储
    • 比如用hash取余/位掩码的方式决定放在哪个key中
    • 对于需要全量数据的场景，会增加一定数据请求和组装的成本
  2. 考虑拆分冷热数据
    • redis中只存储热数据，对于命中率不高的冷数据，使用其他异构数据库
    • 如粉丝列表场景使用zset，只缓存前10页数据，后续走db/hbase
八、内存对齐

依次看：Golang 是否有必要做内存对齐？、Golang 内存对齐
简单总结：对齐是因为CPU不是支持任意字节获取内存的，而是一块一块获取，所以对齐的好处是防止CPU需要两次操作才能读取数据，从而降低效率。如果未对齐，则通过padding来补齐未对齐部分。x86 是4字节对齐，现在的64位系统通常是8字节对齐（比如 int64 刚好够，int8 int32 单独的就需要补齐，同时出现的话可以将 int32 补在 int8 后面，形成1字节int8,3字节padding,4字节int32的8字节对齐格式）。
Go Struct 偏移量还会内存分配的知识点：比如 SpanClass 的选定也会影响到数据分配的偏移量。(32, 48] 字节的 struct 会使用 48 字节的 Span。因此即使是顺序分配，也是 48 字节的 offset 间隔。

  • 内存对齐使用举例：Go WaitGroup
    state函数会判断编译器是否是8字节对齐来决定 waiter 计数器、counter 计数器以及信号量的排列顺序。
type WaitGroup struct {
   noCopy noCopy      // 辅助vet工具检查是否通过copy赋值WaitGroup
   state1 [3]uint32   // 数组，组成 waiter 计数器、counter 计数器以及信号量
// counter 代表目前尚未完成的个数。WaitGroup.Add(n) 将会导致 counter += n, 而 WaitGroup.Done() 将导致 counter--。
// waiter 代表目前已调用 WaitGroup.Wait 的 goroutine 的个数。
// sema 对应于 golang 中 runtime 内部的信号量的实现。
//   WaitGroup 中会用到 sema 的两个相关函数，runtime_Semacquire 和 runtime_Semrelease。
//   runtime_Semacquire 表示增加一个信号量，并挂起 当前 goroutine。
//   runtime_Semrelease 表示减少一个信号量，并唤醒 sema 上其中一个正在等待的 goroutine
}
func (wg *WaitGroup) state() (statep *uint64, semap *uint32) {
   if uintptr(unsafe.Pointer(&wg.state1))%8 == 0 { // 8字节对齐
      return (*uint64)(unsafe.Pointer(&wg.state1)), &wg.state1[2]
   } else { // 4字节对齐
      return (*uint64)(unsafe.Pointer(&wg.state1[1])), &wg.state1[0]
   }
}
Go WaitGroup state 字段含义（如果是8字节对齐，也就是满足第一个 if，那么使用前两个 uint32 组成一个 uint64 来返回，根据移位操作确认 waiter 和 counter 值，如果是4字节对齐，那么 if 条件判断失败，使用后两个 uint32 组成一个 uint64 返回。当然，这里 4 字节对齐的时候，也可能 state1 刚好处于 8 字节对齐的位置，那么会按照 8 字节对齐处理，这主要取决于内存分配时的具体情况。）
  1. Add 操作
    使用规范：默认使用者传入的 delta 为正数，使用者不应该传入 Add 函数一个负数
func (wg *WaitGroup) Add(delta int) {
   statep, semap := wg.state()
   // delta左移32位，将delta原子添加到高位计数器上
   state := atomic.AddUint64(statep, uint64(delta)<<32) 
   v := int32(state >> 32)    // 右移32位，获取高32位计数器，因为 v 存在被 delta 操作，所以可能为负数。
   w := uint32(state)         // 高位截断，获取低32位Waiter计数器，w 只可能在 Wait 函数中被 atomic +1，不可能为负数
   if v < 0 {                 // 计数器不能小于0（使用者非预估：调用 Add 加了负数）
      panic("sync: negative WaitGroup counter")
   }
   // 计数器数据不一致，计数器和delta一样的情况下，waiter 不是 0（使用者非预估：调用 Add 且调用 Wait 时，又调用 Add，导致并发问题）
   if w != 0 && delta > 0 && v == int32(delta) {
      panic("sync: WaitGroup misuse: Add called concurrently with Wait")
   }
   if v > 0 || w == 0 { // 正确add，return
      return
   }
   // 走到这里，说明 v==0 && w>0 （v<0被panic，v>0被返回，w==0被返回）
   if *statep != state { // state数值发生不一致（使用者非预估：v==0时，w发生变化，说明在Add调用过程中，Wait或者Add被非预估调用）
      panic("sync: WaitGroup misuse: Add called concurrently with Wait")
   }
   *statep = 0 // 直接至零，表明 v==0 且 w==0，同时唤醒所有的 wait 状态的 goroutine，只有最后一个 Done 的 goroutine 会这么做
   for ; w != 0; w-- { // 依次唤醒
      runtime_Semrelease(semap, false, 0) // 释放信号量
   }
}
  1. Done 操作
    预期内只有调用 Done 时，才会调用 Add 并传入负值
// Done decrements the WaitGroup counter by one.
func (wg *WaitGroup) Done() {
    wg.Add(-1)
}
  1. Wait 操作
    通过自旋和乐观锁，保证计数器正确被更新
func (wg *WaitGroup) Wait() {
   statep, semap := wg.state()
   for { // 自旋循环
      state := atomic.LoadUint64(statep)
      v := int32(state >> 32)  // 右移32位，获取高32位计数器
      w := uint32(state)       // 高位截断，获取低32位Waiter计数器
      if v == 0 {              // 计数器为0，不需要继续等待
         return
      }
      // 如果计数器不为0，调用wait方法的goroutine需要等待，等待计数器+1，并发调用安全
      // 如果 state 发生了变化，则自旋，并重新观测 counter 并更新 waiter
      if atomic.CompareAndSwapUint64(statep, state, state+1) {
         runtime_Semacquire(semap) // 获取信号量
         // 被唤醒时，肯定是最后一个 goroutine Done，并依次唤醒所有的在 Wait 的 goroutine，此过程中不期望 state 发生变化（即存在并发的 Done 操作或者 Add 操作或者 Wait 操作）
         if *statep != 0 {         // 在wait返回前，WaitGroup被重用了（不期望的事情发生了）
            panic("sync: WaitGroup is reused before previous Wait has returned")
         }
         return
      }
   }
}
  • 思考：
    • 把 waiter 和 counter 合并成一个变量：
      为了避免使用锁，直接利用 atomic 操作，保证两者的改动是同时的。比如Wait时通过乐观锁进行操作，如果同时Done或者Wait被调用，那么会自旋重新观测v，如果v==0则直接返回，否则 waiter 计数+1且进入挂起等待。
    • 冲突考虑（这里的 Add 表示 Add正值，Add负值的情况视为Done）：Add 和 Wait 不能并发，Add 和 Done 可以并发，Wait 和 Done 可以并发。
  • 使用规范：
    • Add 不能和 Wait 并发调用，必须由一个 goroutine 调用这两个函数。
    • 不应该 Add 一个负值。Done 即为 Add(-1)。
    • 不能在 Add 之前调用 Done。