Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Standing on the shoulders of giants - Tomasz Ja...

GoDays
January 23, 2020

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.

GoDays

January 23, 2020
Tweet

More Decks by GoDays

Other Decks in Technology

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. When? $ git show `git rev-list --max-parents=0 HEAD` commit 7a649d1ced34a6fec7904cba51f7db300f14e498

    Author: Adam Dubiel <[email protected]> Date: Wed Mar 23 08:18:52 2016 +0100 Initial commit 5 @janiszt https://talks.godoc.org/github.com/janisz/presentations/bigcache/bigcac...
  5. Does it perform well? YES* * Do your own benchmarks!

    9 @janiszt https://talks.godoc.org/github.com/janisz/presentations/bigcache/bigcac...
  6. 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...
  7. 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...
  8. 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...
  9. 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...
  10. 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...
  11. 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...
  12. 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...
  13. 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...
  14. 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...
  15. 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...
  16. ... 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...
  17. 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...
  18. Thank you Tomasz Janiszewski Software Engineer, D2iQ [email protected] (mailto:[email protected]) @janiszt

    (http://twitter.com/janiszt) @janiszt https://talks.godoc.org/github.com/janisz/presentations/bigcache/bigcac...