Standing on the shoulders of giants - Tomasz Janiszewski - D2IQ

How to improve application performance with no code – just update Go version.
This talk will focus on Go GC and maps. In 2016 I started https://github.com/allegro/bigcache to avoid GC pauses. At that time full GC took 10s now it's 10ms. I'll present story behind Bigcache and talk about it's architecture.

Transcript

1. BigCache after 4 years 23 January 2020 Tomasz Janiszewski Software Engineer, D2iQ @janiszt https://talks.godoc.org/github.com/janisz/presentations/bigcache/bigcac...
2. What is BigCache? fast concurent hashmap minimal GC footprint super simple – not LRU func (c *BigCache) Get(key string) ([]byte, error) func (c *BigCache) Set(key string, entry []byte) error 2 @janiszt https://talks.godoc.org/github.com/janisz/presentations/bigcache/bigcac...
3. Why? Initially: to store request metadata for short period Now: for fun :) 3 @janiszt https://talks.godoc.org/github.com/janisz/presentations/bigcache/bigcac...
4. Why? 4 @janiszt https://talks.godoc.org/github.com/janisz/presentations/bigcache/bigcac...
5. @janiszt https://talks.godoc.org/github.com/janisz/presentations/bigcache/bigcac...
6. When? $ git show `git rev-list --max-parents=0 HEAD` commit 7a649d1ced34a6fec7904cba51f7db300f14e498 Author: Adam Dubiel <adamdubiel@users.noreply.github.com> Date: Wed Mar 23 08:18:52 2016 +0100 Initial commit 5 @janiszt https://talks.godoc.org/github.com/janisz/presentations/bigcache/bigcac...
7. Does it perform well? https://blog.dgraph.io/post/caching-in-go/ 6 @janiszt https://talks.godoc.org/github.com/janisz/presentations/bigcache/bigcac...
8. Does it perform well? https://blog.dgraph.io/post/caching-in-go/ 7 @janiszt https://talks.godoc.org/github.com/janisz/presentations/bigcache/bigcac...
9. Does it perform well? https://blog.dgraph.io/post/caching-in-go/ 8 @janiszt https://talks.godoc.org/github.com/janisz/presentations/bigcache/bigcac...
10. Does it perform well? YES* * Do your own benchmarks! 9 @janiszt https://talks.godoc.org/github.com/janisz/presentations/bigcache/bigcac...
11. How? RWMutex Shards Bytes queue No defer Bitwise modulo Buffer no alloc A little copying Zero dependency 10 @janiszt https://talks.godoc.org/github.com/janisz/presentations/bigcache/bigcac...
12. Start with single map with Mutex type BigCache struct { cache map[string][]byte mutex sync.Mutex } func (c *BigCache) Get(key string) ([]byte, error) { c.mutex.Lock() defer c.mutex.Unlock() v, ok := c.cache[key] if !ok { return nil, fmt.Errorf("NOT FOUND") } return v, nil } func (c *BigCache) Set(key string, entry []byte) { c.mutex.Lock() defer c.mutex.Unlock() c.cache[key] = entry } 11 @janiszt https://talks.godoc.org/github.com/janisz/presentations/bigcache/bigcac...
13. RWMutex type RWMutex struct { w Mutex // held if there are pending writers writerSem uint32 // semaphore for writers to wait for completing readers readerSem uint32 // semaphore for readers to wait for completing writers readerCount int32 // number of pending readers readerWait int32 // number of departing readers } concurrent reads are nearly blocking free writes wait for all reads and other writes // Wait for active readers. if r != 0 && atomic.AddInt32(&rw.readerWait, r) != 0 { runtime_SemacquireMutex(&rw.writerSem, false, 0) } 12 @janiszt https://talks.godoc.org/github.com/janisz/presentations/bigcache/bigcac...
14. Start with single map with RWMutex type BigCache struct { cache map[string][]byte mutex sync.RWMutex } func (c *BigCache) Get(key string) ([]byte, error) { mutex.RLock() defer mutex.RUnlock() v, ok := c.cache[key] if !ok { return nil, fmt.Errorf("NOT FOUND") } return v, nil } func (c *BigCache) Set(key string, entry []byte) { mutex.Lock() defer mutex.Unlock() c.cache[key] = entry } 13 @janiszt https://talks.godoc.org/github.com/janisz/presentations/bigcache/bigcac...
15. Shards – improve concurrency type BigCache struct { cache map[string]shard Hasher Hasher } type shard struct { mutex sync.RWMutex cache map[string][]byte } // Hasher is responsible for generating unsigned, 64 bit hash of provided string. // Hasher should minimize collisions (generating same hash for different strings) // and while performance is also important fast functions are preferable // (i.e. you can use FarmHash family). type Hasher interface { Sum64(string) uint64 } 14 @janiszt https://talks.godoc.org/github.com/janisz/presentations/bigcache/bigcac...
16. Shards – improve concurrency type BigCache struct { cache []shard Hasher Hasher } type shard struct { mutex sync.RWMutex cache map[string][]byte } aka map of maps (implemented with array) split single map into smaller maps hash(key)%len(shards) 15 @janiszt https://talks.godoc.org/github.com/janisz/presentations/bigcache/bigcac...
17. Bitwise operation instead of modulo // x % (2 << n) == x & (2 << n - 1) func (c *BigCache) getShard(hashedKey uint64) (shard *cacheShard) { return c.shards[hashedKey&c.shardMask] } github.com/allegro/bigcache/pull/5 (https://github.com/allegro/bigcache/pull/5) 16 @janiszt https://talks.godoc.org/github.com/janisz/presentations/bigcache/bigcac...
18. Bitwise operation instead of modulo package bigcache import "testing" var sink = 0 func BenchmarkMod(b *testing.B) { for n := 0; n < b.N; n++ { sink = n % 1024 } } func BenchmarkBit(b *testing.B) { for n := 0; n < b.N; n++ { sink = n & 1023 } } 17 @janiszt https://talks.godoc.org/github.com/janisz/presentations/bigcache/bigcac...
19. Bitwise operation instead of modulo 18 @janiszt https://talks.godoc.org/github.com/janisz/presentations/bigcache/bigcac...
20. @janiszt https://talks.godoc.org/github.com/janisz/presentations/bigcache/bigcac...
21. Bytes queue – reduce GC github.com/golang/go/issues/9477 (https://github.com/golang/go/issues/9477) 19 @janiszt https://talks.godoc.org/github.com/janisz/presentations/bigcache/bigcac...
22. @janiszt https://talks.godoc.org/github.com/janisz/presentations/bigcache/bigcac...
23. GC pasue time for maps... 20 @janiszt https://talks.godoc.org/github.com/janisz/presentations/bigcache/bigcac...
24. @janiszt https://talks.godoc.org/github.com/janisz/presentations/bigcache/bigcac...
25. Bytes queue – reduce GC type shard struct { mutex sync.RWMutex cache map[int]int queue BytesQueue } // BytesQueue is a non-thread safe queue type of fifo based on bytes array. // For every push operation index of entry is returned. It can be used to read the entry later type BytesQueue struct { ... } shard is map[int]int (map[hash(key)]index) array of maps ([]map[int]int) instead of map of maps (map[int]map[int]int) values are stored in huge array (queue) 21 @janiszt https://talks.godoc.org/github.com/janisz/presentations/bigcache/bigcac...
26. Architecture 22 @janiszt https://talks.godoc.org/github.com/janisz/presentations/bigcache/bigcac...
27. Never defer... github.com/allegro/bigcache/pull/37 (https://github.com/allegro/bigcache/pull/37) 23 @janiszt https://talks.godoc.org/github.com/janisz/presentations/bigcache/bigcac...
28. ..but 24 @janiszt https://talks.godoc.org/github.com/janisz/presentations/bigcache/bigcac...
29. Never defer... 25 @janiszt https://talks.godoc.org/github.com/janisz/presentations/bigcache/bigcac...
30. @janiszt https://talks.godoc.org/github.com/janisz/presentations/bigcache/bigcac...
31. No alloc... func bytesToString(b []byte) string { bytesHeader := (*reflect.SliceHeader)(unsafe.Pointer(&b)) strHeader := reflect.StringHeader{Data: bytesHeader.Data, Len: bytesHeader.Len} return *(*string)(unsafe.Pointer(&strHeader)) } github.com/allegro/bigcache/pull/24 (https://github.com/allegro/bigcache/pull/24) 26 @janiszt https://talks.godoc.org/github.com/janisz/presentations/bigcache/bigcac...
32. ... but go-app-builder: Failed parsing input: parser: bad import "unsafe" in github.com/allegro/bigcache/bigcache.go from GOPATH Clear is better than clever. Reflection is never clear. go-proverbs.github.io/ (https://go-proverbs.github.io/) 27 @janiszt https://talks.godoc.org/github.com/janisz/presentations/bigcache/bigcac...
33. A little copying Copy FNV hash code to reduce allocation github.com/allegro/bigcache/pull/19 (https://github.com/allegro/bigcache/pull/19) 28 @janiszt https://talks.godoc.org/github.com/janisz/presentations/bigcache/bigcac...
34. Zero dependency 29 @janiszt https://talks.godoc.org/github.com/janisz/presentations/bigcache/bigcac...
35. Thank you Tomasz Janiszewski Software Engineer, D2iQ janiszt@gmail.com (mailto:janiszt@gmail.com) @janiszt (http://twitter.com/janiszt) @janiszt https://talks.godoc.org/github.com/janisz/presentations/bigcache/bigcac...