钱文翔的博客

go-cache源码阅读笔记

发表于 | 分类于 |

自己经常使用 map 加上互斥锁来处理缓存， 很久之前就在 github 上发现 go-cache 这个项目，今天重新看到它，发现它已经 2000+star 了。 扫了一下代码，发现代码量很少，就 clone 下来看看。

go-cache 实际代码就两个文件–cache.go 和 shared.go,其中 shared.go 是作者打算在大缓存数据下使用 hash 算法提升缓存的读写速度的，实际上也未对外 export，创建 sharedCache 的函数名也是小写的。

cache 很简单，只有 map[string]Item 和锁。其中 Item 的结构为

1
2
3
4
type Item struct {
	Object     interface{}
	Expiration int64
}

Object 存储数据，Expiration 存储数据过期时间。创建 cache 的时候会创建一个清理器来清理过期的数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func newCacheWithJanitor(de time.Duration, ci time.Duration, m map[string]Item) *Cache {
	c := newCache(de, m)
	// This trick ensures that the janitor goroutine (which--granted it
	// was enabled--is running DeleteExpired on c forever) does not keep
	// the returned C object from being garbage collected. When it is
	// garbage collected, the finalizer stops the janitor goroutine, after
	// which c can be collected.
	C := &Cache{c}
	if ci > 0 {
		runJanitor(c, ci)
		runtime.SetFinalizer(C, stopJanitor)
	}
	return C
}

注意 runtime.SetFinalizer()这个函数，之前没用过。这是是在  程序垃圾回收(garbage collection)时执行指定函数。

shared.go 是创建一个 shardedCache， 包含多个 cache，通过 hash 算法(djb33)选择 cache 存取数据.

1
2
3
4
5
6
type shardedCache struct {
	seed    uint32
	m       uint32
	cs      []*cache
	janitor *shardedJanitor
}

sharedCache 没有使用 go 的”hash/fnv”中的 hash.Hash 函数，使用的是自己写的 hash 算法，并称自己的 hash 算法 djb33 比 fnv 的快 5 倍 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// djb2 with better shuffling. 5x faster than FNV with the hash.Hash overhead.
func djb33(seed uint32, k string) uint32 {
	var (
		l = uint32(len(k))
		d = 5381 + seed + l
		i = uint32(0)
	)
	// Why is all this 5x faster than a for loop?
	if l >= 4 {
		for i < l-4 {
			d = (d * 33) ^ uint32(k[i])
			d = (d * 33) ^ uint32(k[i+1])
			d = (d * 33) ^ uint32(k[i+2])
			d = (d * 33) ^ uint32(k[i+3])
			i += 4
		}
	}
	switch l - i {
	case 1:
	case 2:
		d = (d * 33) ^ uint32(k[i])
	case 3:
		d = (d * 33) ^ uint32(k[i])
		d = (d * 33) ^ uint32(k[i+1])
	case 4:
		d = (d * 33) ^ uint32(k[i])
		d = (d * 33) ^ uint32(k[i+1])
		d = (d * 33) ^ uint32(k[i+2])
	}
	return d ^ (d >> 16)
}

注意，创建 seed 代码

1
2
3
4
5
6
7
8
9
10

max := big.NewInt(0).SetUint64(uint64(math.MaxUint32))
rnd, err := rand.Int(rand.Reader, max)
var seed uint32
if err != nil {
	os.Stderr.Write([]byte("WARNING: go-cache's newShardedCache failed to read from the system CSPRNG (/dev/urandom or equivalent.) Your system's security may be compromised. Continuing with an insecure seed.\n"))
	seed = insecurerand.Uint32()
} else {
	seed = uint32(rnd.Uint64())
}

引入的包是”crypto/rand” 和 insecurerand “math/rand”。 记得以后使用”crypto/rand” 来  构造随机数，安全些。