Golang小技巧

小对象存储

对于小对象，直接将数据交由 map 保存，远比用指针高效。这不但减少了堆内存分配，关键还在于垃圾回收器不会扫描非指针类型 key/value 对象。

Map空间回收

map 不会收缩 “不再使用” 的空间。就算把所有键值删除，它依然保留内存空间以待后用。
如果一个非常大的map里面的元素很少的话，可以考虑新建一个map将老的map元素手动复制到新的map中。

update if not exists

可以使用遍历的方式，但是时间复杂度会是哈希进行存储及操作，时间复杂度是O(1)，样例如下

set := make(map[int]struct{})
set[1] = struct{}{}
set[2] = struct{}{}
set[1] = struct{}{}
// ...

for key := range(set) {
  fmt.Println(key)
}
// each value will be printed only once, in no particular order

// you can use the ,ok idiom to check for existing keys
if _, ok := set[1]; ok {
  fmt.Println("element found")
} else {
  fmt.Println("element not found")
}

其中使用空的struct可以规避空间分配，int可以替换为其他类型。

Slice是否相等比较

reflect方法

func StringSliceReflectEqual(a, b []string) bool {
    return reflect.DeepEqual(a, b)
}

使用反射的方法进行对比，效率低下，但是代码简单

循环遍历进行比较

func StringSliceEqual(a, b []string) bool {
    if len(a) != len(b) {
        return false
    }
    if (a == nil) != (b == nil) {
        return false
    }
    for i, v := range a {
        if v != b[i] {
            return false
        }
    }
    return true
}

BCE 优化版

func StringSliceEqualBCE(a, b []string) bool {
	if len(a) != len(b) {
		return false
	}
	if (a == nil) != (b == nil) {
		return false
	}
	b = b[:len(a)]
	for i, v := range a {
		if v != b[i] {
			return false
		}
	}
	return true
}

分布式锁

基于redis的setnx锁

package main
import (
    "fmt"
    "sync"
    "time"

    "github.com/go-redis/redis"
)

func incr() {
    client := redis.NewClient(&redis.Options{
        Addr:     "localhost:6379",
        Password: "", // no password set
        DB:       0,  // use default DB
    })

    var lockKey = "counter_lock"
    var counterKey = "counter"

    // lock
    resp := client.SetNX(lockKey, 1, time.Second*5)
    lockSuccess, err := resp.Result()

    if err != nil || !lockSuccess {
        fmt.Println(err, "lock result: ", lockSuccess)
        return
    }

    // counter ++
    getResp := client.Get(counterKey)
    cntValue, err := getResp.Int64()
    if err == nil || err == redis.Nil {
        cntValue++
        resp := client.Set(counterKey, cntValue, 0)
        _, err := resp.Result()
        if err != nil {
            // log err
            println("set value error!")
        }
    }
    println("current counter is ", cntValue)

    delResp := client.Del(lockKey)
    unlockSuccess, err := delResp.Result()
    if err == nil && unlockSuccess > 0 {
        println("unlock success!")
    } else {
        println("unlock failed", err)
    }
}

func main() {
    var wg sync.WaitGroup
    for i := 0; i < 10; i++ {
        wg.Add(1)
        go func() {
            defer wg.Done()
            incr()
        }()
    }
    wg.Wait()
}

竞争型的锁，不阻塞，失败时不执行。setnx很适合在高并发场景下，用来争抢一些“唯一”的资源。

基于ZK的锁

package main

import (
    "time"

    "github.com/samuel/go-zookeeper/zk"
)

func main() {
    c, _, err := zk.Connect([]string{"127.0.0.1"}, time.Second) //*10)
    if err != nil {
        panic(err)
    }
    l := zk.NewLock(c, "/lock", zk.WorldACL(zk.PermAll))
    err = l.Lock()
    if err != nil {
        panic(err)
    }
    println("lock succ, do your business logic")

    time.Sleep(time.Second * 10)

    // do some thing
    l.Unlock()
    println("unlock succ, finish business logic")
}

这种分布式的阻塞锁比较适合分布式任务调度场景，但不适合高频次持锁时间短的抢锁场景。

ETCD锁

package main

import (
    "log"

    "github.com/zieckey/etcdsync"
)

func main() {
    m, err := etcdsync.New("/lock", 10, []string{"http://127.0.0.1:2379"})
    if m == nil || err != nil {
        log.Printf("etcdsync.New failed")
        return
    }
    err = m.Lock()
    if err != nil {
        log.Printf("etcdsync.Lock failed")
        return
    }

    log.Printf("etcdsync.Lock OK")
    log.Printf("Get the lock. Do something here.")

    err = m.Unlock()
    if err != nil {
        log.Printf("etcdsync.Unlock failed")
    } else {
        log.Printf("etcdsync.Unlock OK")
    }
}

扩展：基于 Etcd 的分布式锁实现原理及方案.md

三种锁的区别

由上图可以看出三种组件各自的特点，其中对于分布式锁来说至关重要的一点是要求CP。但是，Redis集群却不支持CP，而是支持AP。虽然，官方也给出了redlock的方案，但由于需要部署多个实例(超过一半实例成功才视为成功)，部署、维护比较复杂。所以在对一致性要求很高的业务场景下(电商、银行支付)，一般选择使用zookeeper或者etcd。对比zookeeper与etcd，如果考虑性能、并发量、维护成本来看。由于etcd是用Go语言开发，直接编译为二进制可执行文件，并不依赖其他任何东西，则更具有优势。

Sync.Map

Struct

type Map struct {
    // 保护dirty的锁
    mu Mutex                        
    // 只读数据（修改采用原子操作)
    read atomic.Value                
    // 包含只读中所有数据（冗余），写入新数据时也在dirty中操作
    dirty map[interface{}]*entry  
    // 当原子操作访问只读read时找不到数据时会去dirty中寻找，此时misses+1，dirty及作为存储新写入的数据，又冗余了只读结构中的数据，所以当misses > dirty 的长度时， 会将dirty升级为read，同时将老的dirty置nil
    misses int 
}

// Map struct 中的 read 就是readOnly 的指针
type readOnly struct {
    // 基础Map
    m   map[interface{}]*entry 
    // 用于表示当前dirty中是否有read中不存在的数据， 在写入数据时， 如果发现dirty中没有新数据且dirty为nil时，会将read中未被删除的数据拷贝一份冗余到dirty中， 过程与Map struct中的 misses相呼应
    amended bool 
}

// 数据项
type entry struct {
    p unsafe.Pointer 
}

// 用于标记数据项已被删除（主要保证数据冗余时的并发安全）
// 上述Map结构中说到有一个将read数据拷贝冗余至dirty的过程， 因为删除数据项是将*entry置nil, 为了避免冗余过程中因并发问题导致*entry改变而影响到拷贝后的dirty正确性，所以sync.Map使用expunged来标记entry是否被删除
var expunged = unsafe.Pointer(new(interface{}))

Store

func (m *Map) Store(key, value interface{}) {
    // 先不上锁，而是从只读数据中按key读取， 如果已存在以compareAndSwap操作进行覆盖(update)
    read, _ := m.read.Load().(readOnly)
    if e, ok := read.m[key]; ok && e.tryStore(&value) {
        return
    }
    
    m.mu.Lock()
    // 双检查获取read
    read, _ = m.read.Load().(readOnly)
    // 如果data在read中，更新entry
    if e, ok := read.m[key]; ok {
        // 如果原子操作读到的数据是被标记删除的， 则视为新数据写入dirty
        if e.unexpungeLocked() {
            m.dirty[key] = e
        }
        // 原子操作写新数据
        e.storeLocked(&value)
    } else if e, ok := m.dirty[key]; ok {
        // 原子操作写新数据
        e.storeLocked(&value)
    } else {
        // 新数据 
        // 当dirty中没有新数据时，将read中数据冗余到dirty
        if !read.amended {
            m.dirtyLocked()
            m.read.Store(readOnly{m: read.m, amended: true})
        }
        
        m.dirty[key] = newEntry(value)
    }
    m.mu.Unlock()
}

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
        }
    }
}


// 在dirty中没有比read多出的新数据时触发冗余
func (m *Map) dirtyLocked() {
    if m.dirty != nil {
        return
    }

    read, _ := m.read.Load().(readOnly)
    m.dirty = make(map[interface{}]*entry, len(read.m))
    for k, e := range read.m {
        // 检查entry是否被删除， 被删除的数据不冗余
        if !e.tryExpungeLocked() {
            m.dirty[k] = e
        }
    }
}

func (e *entry) tryExpungeLocked() (isExpunged bool) {
    p := atomic.LoadPointer(&e.p)
    for p == nil {
        // 将被删除（置nil）的数据以cas原子操作标记为expunged（防止因并发情况下其他操作导致冗余进dirty的数据不正确）
        if atomic.CompareAndSwapPointer(&e.p, nil, expunged) {
            return true
        }
        p = atomic.LoadPointer(&e.p)
    }
    return p == expunged
}

Load/Read

func (m *Map) Load(key interface{}) (value interface{}, ok bool) {
    read, _ := m.read.Load().(readOnly)
    e, ok := read.m[key]

    // 只读数据中没有，并且dirty有比read多的数据，加锁在dirty中找
    if !ok && read.amended {
        m.mu.Lock()
        // 双检查， 因为上锁之前的语句是非原子性的
        read, _ = m.read.Load().(readOnly)
        e, ok = read.m[key]
        if !ok && read.amended {
            // 只读中没有读取到的次数+1
            e, ok = m.dirty[key]
            // 检查是否达到触发dirty升级read的条件
            m.missLocked()
        }
        m.mu.Unlock()
    }
    if !ok {
        return nil, false
    }
    // atomic.Load 但被标记为删除的会返回nil
    return e.load()
}

func (m *Map) missLocked() {
    m.misses++
    if m.misses < len(m.dirty) {
        return
    }
    m.read.Store(readOnly{m: m.dirty})
    m.dirty = nil
    m.misses = 0
}

Delete

func (m *Map) Delete(key interface{}) {
    read, _ := m.read.Load().(readOnly)
    e, ok := read.m[key]
    // 只读中不存在需要到dirty中去删除
    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 {
        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
        }
    }
}

Go 字符串查找效率问题

问题描述

Golang从字符串查找时，strings.Contains 与 正则对比
以下为查找函数

# strings.Contains
func stringsMatch(str string, subStr string) bool {
	return strings.Contains(str, subStr)
}
# 正则查找
func regexMatch(str string, subStr string) bool {
	reg := regexp.MustCompile("(" + subStr + ")")
	return reg.MatchString(str)
}

以下为benchmark函数

const letterBytes = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

func randomString(n int) string {
	b := make([]byte, n)
	for i := range b {
		b[i] = letterBytes[rand.Intn(len(letterBytes))]
	}
	return string(b)
}

func benchmark(b *testing.B, f func(string, string) bool) {
	var str = "测试test"
	for i := 0; i < b.N; i++ {
		f(randomString(10)+str+randomString(10), str)
	}
}

正则Benchmark

goos: windows
goarch: amd64
pkg: gotest
cpu: AMD Ryzen 5 5600X 6-Core Processor             
BenchmarkRegexMatch-12    	  595849	      1916 ns/op	    2327 B/op	      27 allocs/op
PASS
ok  	gotest	1.188s

strings.Contains Benchmark输出

goos: windows
goarch: amd64
pkg: gotest
cpu: AMD Ryzen 5 5600X 6-Core Processor             
BenchmarkStringsMatch-12    	 5357433	       227.2 ns/op	      96 B/op	       5 allocs/op
PASS
ok  	gotest	1.584s

可见strings.Contains性能好于使用这种方式的正则匹配判断。
由上面的代码又引发出一个可能更为常见的对比场景，那就是所需的正则是固定的，而所进行对比的字符串不固定，即*regexp.Regexp只生成一次，由此再次进行对比
此时的正则查找函数变为

var reg = regexp.MustCompile("(" + "测试test" + ")")

func regexMatch(str string, _ string) bool {
	return reg.MatchString(str)
}

得结果如下

goos: windows
goarch: amd64
pkg: gotest
cpu: AMD Ryzen 5 5600X 6-Core Processor             
BenchmarkRegexMatch-12    	 3832815	       301.7 ns/op	      97 B/op	       5 allocs/op
PASS
ok  	gotest	1.614s

可见strings.Contains性能仍然占上风，因此推荐只在做严格匹配时使用正则，其他场合能用strings.Contains解决尽量不采用正则，以提高效率。